Return to rsagen.c CVS log

Up to [PGP] / pgp / src

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

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

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