Return to rsagen.c CVS log

Up to [PGP] / pgp / src

Annotation of pgp/src/rsagen.c, revision 1.1.1.5

1.1.1.5 ! root        1: /*     rsagen.c - C source code for RSA public-key key generation routines.
        !             2:        First version 17 Mar 87
        !             3: 
        !             4:         (c) Copyright 1987 by Philip Zimmermann.  All rights reserved.
        !             5:         The author assumes no liability for damages resulting from the use
        !             6:         of this software, even if the damage results from defects in this
        !             7:         software.  No warranty is expressed or implied.
        !             8: 
        !             9:        RSA-specific routines follow.  These are the only functions that 
        !            10:        are specific to the RSA public key cryptosystem.  The other
        !            11:        multiprecision integer math functions may be used for non-RSA
        !            12:        applications.  Without these functions that follow, the rest of 
        !            13:        the software cannot perform the RSA public key algorithm.  
        !            14: 
        !            15:        The RSA public key cryptosystem is patented by the Massachusetts
        !            16:        Institute of Technology (U.S. patent #4,405,829).  This patent does
        !            17:        not apply outside the USA.  Public Key Partners (PKP) holds the
        !            18:        exclusive commercial license to sell and sub-license the RSA public
        !            19:        key cryptosystem.  The author of this software implementation of the
        !            20:        RSA algorithm is providing this software for educational use only. 
        !            21:        Licensing this algorithm from PKP is the responsibility of you, the
        !            22:        user, not Philip Zimmermann, the author of this software.  The author
        !            23:        assumes no liability for any breach of patent law resulting from the
        !            24:        unlicensed use of this software by the user.
        !            25: */
        !            26: 
        !            27: #include "mpilib.h"
        !            28: #include "genprime.h"
        !            29: #include "rsagen.h"
        !            30: #include "random.h"
        !            31: #include "rsaglue.h"
        !            32: 
        !            33: static void derive_rsakeys(unitptr n,unitptr e,unitptr d,
        !            34:        unitptr p,unitptr q,unitptr u,short ebits);
        !            35:        /* Given primes p and q, derive RSA key components n, e, d, and u. */
        !            36: 
        !            37: 
        !            38: /* Define some error status returns for RSA keygen... */
        !            39: #define KEYFAILED -15          /* key failed final test */
        !            40: 
        !            41: 
        !            42: #define swap(p,q)  { unitptr t; t = p;  p = q;  q = t; }
        !            43: 
        !            44: 
        !            45: static void derive_rsakeys(unitptr n, unitptr e, unitptr d,
        !            46:        unitptr p, unitptr q, unitptr u, short ebits)
        !            47: /*
        !            48:  * Given primes p and q, derive RSA key components n, e, d, and u. 
        !            49:  * The global_precision must have already been set large enough for n.
        !            50:  * Note that p must be < q.
        !            51:  * Primes p and q must have been previously generated elsewhere.
        !            52:  * The bit precision of e will be >= ebits.  The search for a usable
        !            53:  * exponent e will begin with an ebits-sized number.  The recommended 
        !            54:  * value for ebits is 5, for efficiency's sake.  This could yield 
        !            55:  * an e as small as 17.
        !            56:  */
        !            57: {
        !            58:        unit F[MAX_UNIT_PRECISION];
        !            59:        unitptr ptemp, qtemp, phi, G;   /* scratchpads */
        !            60: 
        !            61:        /*      For strong prime generation only, latitude is the amount 
        !            62:                which the modulus may differ from the desired bit precision.  
        !            63:                It must be big enough to allow primes to be generated by 
        !            64:                goodprime reasonably fast. 
        !            65:        */
        !            66: #define latitude(bits) (max(min(bits/16,12),4))        /* between 4 and 12 bits */
        !            67:        
        !            68:        ptemp = d;      /* use d for temporary scratchpad array */
        !            69:        qtemp = u;      /* use u for temporary scratchpad array */
        !            70:        phi = n;        /* use n for temporary scratchpad array */
        !            71:        G = F;          /* use F for both G and F */
        !            72:        
        !            73:        if (mp_compare(p,q) >= 0)       /* ensure that p<q for computing u */
        !            74:                swap(p,q);              /* swap the pointers p and q */
        !            75: 
        !            76:        /*      phi(n) is the Euler totient function of n, or the number of
        !            77:                positive integers less than n that are relatively prime to n.
        !            78:                G is the number of "spare key sets" for a given modulus n. 
        !            79:                The smaller G is, the better.  The smallest G can get is 2. 
        !            80:        */
        !            81:        mp_move(ptemp,p); mp_move(qtemp,q);
        !            82:        mp_dec(ptemp); mp_dec(qtemp);
        !            83:        mp_mult(phi,ptemp,qtemp);       /*  phi(n) = (p-1)*(q-1)  */
        !            84:        mp_gcd(G,ptemp,qtemp);          /*  G(n) = gcd(p-1,q-1)  */
        !            85: #ifdef DEBUG
        !            86:        if (countbits(G) > 12)          /* G shouldn't get really big. */
        !            87:                mp_display("\007G = ",G);       /* Worry the user. */
        !            88: #endif /* DEBUG */
        !            89:        mp_udiv(ptemp,qtemp,phi,G);     /* F(n) = phi(n)/G(n)  */
        !            90:        mp_move(F,qtemp);
        !            91: 
        !            92:        /*
        !            93:         * We now have phi and F.  Next, compute e...
        !            94:         * Strictly speaking, we might get slightly faster results by
        !            95:         * testing all small prime e's greater than 2 until we hit a 
        !            96:         * good e.  But we can do just about as well by testing all 
        !            97:         * odd e's greater than 2.
        !            98:         * We could begin searching for a candidate e anywhere, perhaps
        !            99:         * using a random 16-bit starting point value for e, or even
        !           100:         * larger values.  But the most efficient value for e would be 3, 
        !           101:         * if it satisfied the gcd test with phi.
        !           102:         * Parameter ebits specifies the number of significant bits e
        !           103:         * should have to begin search for a workable e.
        !           104:         * Make e at least 2 bits long, and no longer than one bit 
        !           105:         * shorter than the length of phi.
        !           106:         */
        !           107:        ebits = min(ebits,countbits(phi)-1);
        !           108:        if (ebits==0) ebits=5;  /* default is 5 bits long */
        !           109:        ebits = max(ebits,2);
        !           110:        mp_init(e,0);
        !           111:        mp_setbit(e,ebits-1);
        !           112:        lsunit(e) |= 1;         /* set e candidate's lsb - make it odd */
        !           113:        mp_dec(e);  mp_dec(e); /* precompensate for preincrements of e */
        !           114:        do {
        !           115:                mp_inc(e); mp_inc(e);   /* try odd e's until we get it. */
        !           116:                mp_gcd(ptemp,e,phi); /* look for e such that gcd(e,phi(n)) = 1 */
        !           117:        } while (testne(ptemp,1));
        !           118: 
        !           119:        /*      Now we have e.  Next, compute d, then u, then n.
        !           120:                d is the multiplicative inverse of e, mod F(n).
        !           121:                u is the multiplicative inverse of p, mod q, if p<q.
        !           122:                n is the public modulus p*q.
        !           123:        */
        !           124:        mp_inv(d,e,F);          /* compute d such that (e*d) mod F(n) = 1 */
        !           125:        mp_inv(u,p,q);                  /* (p*u) mod q = 1, assuming p<q */
        !           126:        mp_mult(n,p,q); /*  n = p*q  */
        !           127:        mp_burn(F);             /* burn the evidence on the stack */
        !           128: }      /* derive_rsakeys */
        !           129: 
        !           130: 
        !           131: int rsa_keygen(unitptr n, unitptr e, unitptr d,
        !           132:        unitptr p, unitptr q, unitptr u, short keybits, short ebits)
        !           133: /*
        !           134:  * Generate RSA key components p, q, n, e, d, and u. 
        !           135:  * This routine sets the global_precision appropriate for n,
        !           136:  * where keybits is desired precision of modulus n.
        !           137:  * The precision of exponent e will be >= ebits.
        !           138:  * It will generate a p that is < q.
        !           139:  * Returns 0 for succcessful keygen, negative status otherwise.
        !           140:  */
        !           141: {
        !           142:        short pbits, qbits;
        !           143:        boolean too_close_together; /* TRUE iff p and q are too close */
        !           144:        int status;
        !           145:        int slop;
        !           146: 
        !           147:        /*
        !           148:         * Don't let keybits get any smaller than 2 units, because      
        !           149:         * some parts of the math package require at least 2 units 
        !           150:         * for global_precision.
        !           151:         * Nor any smaller than the 32 bits of preblocking overhead.
        !           152:         * Nor any bigger than MAX_BIT_PRECISION - SLOP_BITS.
        !           153:         * Also, if generating "strong" primes, don't let keybits get
        !           154:         * any smaller than 64 bits, because of the search latitude.
        !           155:         */
        !           156:        slop = max(SLOP_BITS,1); /* allow at least 1 slop bit for sign bit */
        !           157:        keybits = min(keybits,(MAX_BIT_PRECISION-slop));
        !           158:        keybits = max(keybits,UNITSIZE*2);
        !           159:        keybits = max(keybits,32); /* minimum preblocking overhead */
        !           160: #ifdef STRONGPRIMES
        !           161:        keybits = max(keybits,64); /* for strong prime search latitude */
        !           162: #endif /* STRONGPRIMES */
        !           163: 
        !           164:        set_precision(bits2units(keybits + slop));
        !           165: 
        !           166:        /*      We will need a series of truly random bits to generate the 
        !           167:                primes.  We need enough random bits for keybits, plus two 
        !           168:                random units for combined discarded bit losses in randombits. 
        !           169:                Since we now know how many random bits we will need,
        !           170:                this is the place to prefill the pool of random bits. 
        !           171:        */
        !           172:        trueRandAccum(keybits+2*UNITSIZE);
        !           173: 
        !           174: #if 0
        !           175:        /*
        !           176:         * If you want primes of different lengths ("separation" bits apart),
        !           177:         * do the following:
        !           178:         */
        !           179:        pbits = (keybits-separation)/2;
        !           180:        qbits = keybits - pbits;
        !           181: #else
        !           182:        pbits = keybits/2;
        !           183:        qbits = keybits - pbits;
        !           184: #endif
        !           185: 
        !           186:        trueRandConsume(pbits); /* "use up" this many bits */
        !           187: 
        !           188: #ifdef STRONGPRIMES    /* make a good strong prime for the key */
        !           189:        status = goodprime(p,pbits,pbits-latitude(pbits));
        !           190: #else  /* just any random prime will suffice for the key */
        !           191:        status = randomprime(p,pbits);
        !           192: #endif /* else not STRONGPRIMES */
        !           193:        if (status < 0) 
        !           194:                return(status); /* failed to find a suitable prime */
        !           195: 
        !           196:        /* We now have prime p.  Now generate q such that q>p... */
        !           197: 
        !           198:        qbits = keybits - countbits(p);
        !           199: 
        !           200:        trueRandConsume(qbits); /* "use up" this many bits */
        !           201:        /*      This load of random bits will be stirred and recycled until 
        !           202:                a good q is generated. */
        !           203: 
        !           204:        do {    /* Generate a q until we get one that isn't too close to p. */
        !           205: #ifdef STRONGPRIMES    /* make a good strong prime for the key */
        !           206:                status = goodprime(q,qbits,qbits-latitude(qbits));
        !           207: #else  /* just any random prime will suffice for the key */
        !           208:                status = randomprime(q,qbits);
        !           209: #endif /* else not STRONGPRIMES */
        !           210:                if (status < 0) 
        !           211:                        return(status); /* failed to find a suitable prime */
        !           212: 
        !           213:                /* Note that at this point we can't be sure that q>p. */
        !           214:                if (mp_compare(p,q) >= 0) { /* ensure that p<q for computing u */
        !           215:                        mp_move(u,p);
        !           216:                        mp_move(p,q);
        !           217:                        mp_move(q,u);
        !           218:                }
        !           219:                /* See if p and q are far enough apart.  Is q-p big enough? */
        !           220:                mp_move(u,q);   /* use u as scratchpad */
        !           221:                mp_sub(u,p);    /* compute q-p */
        !           222:                too_close_together = (countbits(u) < (countbits(q)-7));
        !           223: 
        !           224:                /* Keep trying q's until we get one far enough from p... */
        !           225:        } while (too_close_together);
        !           226: 
        !           227:        derive_rsakeys(n,e,d,p,q,u,ebits);
        !           228:        trueRandFlush();        /* ensure recycled random pool is destroyed */
        !           229: 
        !           230:        /* Now test key just to make sure --this had better work! */
        !           231:        {
        !           232:                unit C[MAX_UNIT_PRECISION];
        !           233:                int i;
        !           234: 
        !           235: /* Create a dummy signature */
        !           236:                for (i = 0; i < 16; i++)
        !           237:                        ((byte *)C)[i] = 3*i+7;
        !           238: /* Encrypt it */
        !           239:                status = rsa_private_encrypt(C,(byte *)C,16,e,d,p,q,u,n);
        !           240:                if (status < 0) /* modexp error? */
        !           241:                        return status;  /* return error status */
        !           242: /* Extract the signature */
        !           243:                status = rsa_public_decrypt((byte *)C,C,e,n);
        !           244:                if (status < 0) /* modexp error? */
        !           245:                        return status;  /* return error status */
        !           246: /* Verify that we got the same thing back. */
        !           247:                if (status != 16)
        !           248:                        return KEYFAILED;
        !           249:                for (i = 0; i < 16; i++)
        !           250:                        if (((byte *)C)[i] != 3*i+7)
        !           251:                                return KEYFAILED;
        !           252:        }
        !           253:        return 0;       /* normal return */
        !           254: }      /* rsa_keygen */
        !           255: 
        !           256: /****************** End of RSA-specific routines  *******************/
        !           257: 
        !           258: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.