Return to rsagen.c CVS log

Up to [PGP] / pgp / src

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

1.1.1.2 ! 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: /* Define symbol PSEUDORANDOM in random.h to disable truly random numbers. */
        !            31: #include "random.h"
        !            32: 
        !            33: /* The following #ifdefs determine constraints on key sizes... */
        !            34: 
        !            35: #ifdef WHOLEWORD_KEY /* some modmult algorithms are faster this way */
        !            36: #ifdef MERRITT_KEY
        !            37: #undef MERRITT_KEY     /* ensures MERRITT_KEY is undefined */
        !            38: #endif
        !            39: #endif /* WHOLEWORD_KEY */
        !            40: 
        !            41: #ifdef MERRITT_KEY     /* if using Merritt's modmult algorithm */
        !            42: #ifdef WHOLEWORD_KEY
        !            43: #undef WHOLEWORD_KEY   /* ensures WHOLEWORD_KEY is undefined */
        !            44: #endif
        !            45: #endif /* MERRITT_KEY */
        !            46: 
        !            47: 
        !            48: /* Define some error status returns for RSA keygen... */
        !            49: #define KEYFAILED -15          /* key failed final test */
        !            50: 
        !            51: 
        !            52: #define swap(p,q)  { unitptr t; t = p;  p = q;  q = t; }
        !            53: 
        !            54: 
        !            55: void derive_rsakeys(unitptr n, unitptr e, unitptr d,
        !            56:        unitptr p, unitptr q, unitptr u, short ebits)
        !            57: /*     Given primes p and q, derive RSA key components n, e, d, and u. 
        !            58:        The global_precision must have already been set large enough for n.
        !            59:        Note that p must be < q.
        !            60:        Primes p and q must have been previously generated elsewhere.
        !            61:        The bit precision of e will be >= ebits.  The search for a usable
        !            62:        exponent e will begin with an ebits-sized number.  The recommended 
        !            63:        value for ebits is 5, for efficiency's sake.  This could yield 
        !            64:        an e as small as 17.
        !            65: */
        !            66: {      unit F[MAX_UNIT_PRECISION];
        !            67:        unitptr ptemp, qtemp, phi, G;   /* scratchpads */
        !            68: 
        !            69:        /*      For strong prime generation only, latitude is the amount 
        !            70:                which the modulus may differ from the desired bit precision.  
        !            71:                It must be big enough to allow primes to be generated by 
        !            72:                goodprime reasonably fast. 
        !            73:        */
        !            74: #define latitude(bits) (max(min(bits/16,12),4))        /* between 4 and 12 bits */
        !            75:        
        !            76:        ptemp = d;      /* use d for temporary scratchpad array */
        !            77:        qtemp = u;      /* use u for temporary scratchpad array */
        !            78:        phi = n;        /* use n for temporary scratchpad array */
        !            79:        G = F;          /* use F for both G and F */
        !            80:        
        !            81:        if (mp_compare(p,q) >= 0)       /* ensure that p<q for computing u */
        !            82:                swap(p,q);              /* swap the pointers p and q */
        !            83: 
        !            84:        /*      phi(n) is the Euler totient function of n, or the number of
        !            85:                positive integers less than n that are relatively prime to n.
        !            86:                G is the number of "spare key sets" for a given modulus n. 
        !            87:                The smaller G is, the better.  The smallest G can get is 2. 
        !            88:        */
        !            89:        mp_move(ptemp,p); mp_move(qtemp,q);
        !            90:        mp_dec(ptemp); mp_dec(qtemp);
        !            91:        mp_mult(phi,ptemp,qtemp);       /*  phi(n) = (p-1)*(q-1)  */
        !            92:        mp_gcd(G,ptemp,qtemp);          /*  G(n) = gcd(p-1,q-1)  */
        !            93: #ifdef DEBUG
        !            94:        if (countbits(G) > 12)          /* G shouldn't get really big. */
        !            95:                mp_display("\007G = ",G);       /* Worry the user. */
        !            96: #endif /* DEBUG */
        !            97:        mp_udiv(ptemp,qtemp,phi,G);     /* F(n) = phi(n)/G(n)  */
        !            98:        mp_move(F,qtemp);
        !            99: 
        !           100:        /*      We now have phi and F.  Next, compute e...
        !           101:                Strictly speaking, we might get slightly faster results by
        !           102:                testing all small prime e's greater than 2 until we hit a 
        !           103:                good e.  But we can do just about as well by testing all 
        !           104:                odd e's greater than 2.
        !           105:                We could begin searching for a candidate e anywhere, perhaps
        !           106:                using a random 16-bit starting point value for e, or even
        !           107:                larger values.  But the most efficient value for e would be 3, 
        !           108:                if it satisfied the gcd test with phi.
        !           109:                Parameter ebits specifies the number of significant bits e
        !           110:                should have to begin search for a workable e.
        !           111:                Make e at least 2 bits long, and no longer than one bit 
        !           112:                shorter than the length of phi.
        !           113:        */
        !           114:        ebits = min(ebits,countbits(phi)-1);
        !           115:        if (ebits==0) ebits=5;  /* default is 5 bits long */
        !           116:        ebits = max(ebits,2);
        !           117:        mp_init(e,0);
        !           118:        mp_setbit(e,ebits-1);
        !           119:        lsunit(e) |= 1;         /* set e candidate's lsb - make it odd */
        !           120:        mp_dec(e);  mp_dec(e); /* precompensate for preincrements of e */
        !           121:        do
        !           122:        {       mp_inc(e); mp_inc(e);   /* try odd e's until we get it. */
        !           123:                mp_gcd(ptemp,e,phi); /* look for e such that gcd(e,phi(n)) = 1 */
        !           124:        } while (testne(ptemp,1));
        !           125: 
        !           126:        /*      Now we have e.  Next, compute d, then u, then n.
        !           127:                d is the multiplicative inverse of e, mod F(n).
        !           128:                u is the multiplicative inverse of p, mod q, if p<q.
        !           129:                n is the public modulus p*q.
        !           130:        */
        !           131:        mp_inv(d,e,F);          /* compute d such that (e*d) mod F(n) = 1 */
        !           132:        mp_inv(u,p,q);                  /* (p*u) mod q = 1, assuming p<q */
        !           133:        mp_mult(n,p,q); /*  n = p*q  */
        !           134:        mp_burn(F);             /* burn the evidence on the stack */
        !           135: }      /* derive_rsakeys */
        !           136: 
        !           137: 
        !           138: int rsa_keygen(unitptr n, unitptr e, unitptr d,
        !           139:        unitptr p, unitptr q, unitptr u, short keybits, short ebits)
        !           140: /*     Generate RSA key components p, q, n, e, d, and u. 
        !           141:        This routine sets the global_precision appropriate for n,
        !           142:        where keybits is desired precision of modulus n.
        !           143:        The precision of exponent e will be >= ebits.
        !           144:        It will generate a p that is < q.
        !           145:        Returns 0 for succcessful keygen, negative status otherwise.
        !           146: */
        !           147: {      short pbits,qbits,separation;
        !           148:        boolean too_close_together; /* TRUE iff p and q are too close */
        !           149:        int status;
        !           150:        int slop;
        !           151: 
        !           152:        /*      Don't let keybits get any smaller than 2 units, because 
        !           153:                some parts of the math package require at least 2 units 
        !           154:                for global_precision.
        !           155:                Nor any smaller than the 32 bits of preblocking overhead.
        !           156:                Nor any bigger than MAX_BIT_PRECISION - SLOP_BITS.
        !           157:                Also, if generating "strong" primes, don't let keybits get
        !           158:                any smaller than 64 bits, because of the search latitude.
        !           159:        */
        !           160:        slop = max(SLOP_BITS,1); /* allow at least 1 slop bit for sign bit */
        !           161:        keybits = min(keybits,(MAX_BIT_PRECISION-slop));
        !           162:        keybits = max(keybits,UNITSIZE*2);
        !           163:        keybits = max(keybits,32); /* minimum preblocking overhead */
        !           164: #ifdef STRONGPRIMES
        !           165:        keybits = max(keybits,64); /* for strong prime search latitude */
        !           166: #endif /* STRONGPRIMES */
        !           167: #ifdef WHOLEWORD_KEY   /* some modmults run faster this way */
        !           168:        /*      Some modmult algorithms run faster if both primes and 
        !           169:                the modulus are an exact multiple of UNITSIZE bits long,
        !           170:                in other words, they completely fill the most significant 
        !           171:                unit.  So we will "round up" keybits to the next multiple 
        !           172:                of UNITSIZE*2.
        !           173:        */
        !           174: #define roundup(x,m) (((x)+(m)-1)/(m))*(m)
        !           175:        keybits = roundup(keybits,UNITSIZE*2);
        !           176:        if (keybits==MAX_BIT_PRECISION) /* allow head room for sign bit */
        !           177:                keybits -= UNITSIZE*2;
        !           178: #endif /* WHOLEWORD_KEY */
        !           179: 
        !           180:        set_precision(bits2units(keybits + slop));
        !           181: 
        !           182:        /*      We will need a series of truly random bits to generate the 
        !           183:                primes.  We need enough random bits for keybits, plus two 
        !           184:                random units for combined discarded bit losses in randombits. 
        !           185:                Since we now know how many random bits we will need,
        !           186:                this is the place to prefill the pool of random bits. 
        !           187:        */
        !           188:        randflush();    /* ensure recycled random pool is empty */
        !           189:        randaccum(keybits+2*UNITSIZE); /* get this many raw random bits ready */
        !           190: 
        !           191:        /*      separation is the minimum number bits of difference in the 
        !           192:                sizes of p and q. 
        !           193:        */
        !           194: #ifdef MERRITT_KEY     /* using Merritt's modmult algorithm */
        !           195:        separation = 2;
        !           196: #else  /* not MERRITT_KEY */
        !           197:        separation = 0;
        !           198: #endif /* not MERRITT_KEY */
        !           199:        pbits = (keybits-separation)/2;
        !           200:        qbits = keybits - pbits;
        !           201: 
        !           202: #ifdef MERRITT_KEY
        !           203:        /*      During decrypt, the primes p and q's bit length should 
        !           204:                not be an exact multiple of UNITSIZE, because Merritt's 
        !           205:                modmult algorithm performs slowest in that case, wasting 
        !           206:                an extra unit of precision for overflow.
        !           207:                Other modmult algorithms perform differently.
        !           208:                Some other modmults actually performs fastest when the 
        !           209:                modulus and primes p and q exactly fill the MS unit.
        !           210:        */
        !           211:        {       short qtrim;
        !           212:                qtrim = (qbits % UNITSIZE)+1; /* how many bits to trim from q */
        !           213:                if (qtrim <= (separation/2))
        !           214:                        pbits += qtrim; /* allows qbits to be a bit shorter */
        !           215:        }
        !           216:        if ((pbits % UNITSIZE)==0)      /* inefficient to exactly fill a word */ 
        !           217:                pbits -= 1;     /* one bit shorter speeds up modmult a lot. */
        !           218: #endif /* MERRITT_KEY */
        !           219: 
        !           220:        randload(pbits); /* get fresh load of raw random bits for p */
        !           221: #ifdef STRONGPRIMES    /* make a good strong prime for the key */
        !           222:        status = goodprime(p,pbits,pbits-latitude(pbits));
        !           223:        if (status < 0) 
        !           224:                return(status); /* failed to find a suitable prime */
        !           225: #else  /* just any random prime will suffice for the key */
        !           226:        status = randomprime(p,pbits);
        !           227:        if (status < 0) 
        !           228:                return(status); /* failed to find a random prime */
        !           229: #endif /* else not STRONGPRIMES */
        !           230: 
        !           231:        /* We now have prime p.  Now generate q such that q>p... */
        !           232: 
        !           233:        qbits = keybits - countbits(p);
        !           234: 
        !           235: #ifdef MERRITT_KEY
        !           236:        if ((qbits % UNITSIZE)==0)      /* inefficient to exactly fill a word */ 
        !           237:                qbits -= 1;     /* one bit shorter speeds up modmult a lot. */
        !           238: #endif /* MERRITT_KEY */
        !           239: 
        !           240:        randload(qbits); /* get fresh load of raw random bits for q */
        !           241:        /*      This load of random bits will be stirred and recycled until 
        !           242:                a good q is generated. */
        !           243: 
        !           244:        do      /* Generate a q until we get one that isn't too close to p. */
        !           245:        {       
        !           246: #ifdef STRONGPRIMES    /* make a good strong prime for the key */
        !           247:                status = goodprime(q,qbits,qbits-latitude(qbits));
        !           248:                if (status < 0) 
        !           249:                        return(status); /* failed to find a suitable prime */
        !           250: #else  /* just any random prime will suffice for the key */
        !           251:                status = randomprime(q,qbits);
        !           252:                if (status < 0) 
        !           253:                        return(status); /* failed to find a random prime */
        !           254: #endif /* else not STRONGPRIMES */
        !           255: 
        !           256:                /* Note that at this point we can't be sure that q>p. */
        !           257:                /*      See if p and q are far enough apart.  Is q-p big enough? */
        !           258:                mp_move(u,q);   /* use u as scratchpad */
        !           259:                mp_sub(u,p);    /* compute q-p */
        !           260:                if (mp_tstminus(u))     /* p is bigger */
        !           261:                {       mp_neg(u);
        !           262:                        too_close_together = (countbits(u) < (countbits(p)-7));
        !           263:                }
        !           264:                else            /* q is bigger */
        !           265:                        too_close_together = (countbits(u) < (countbits(q)-7));
        !           266: 
        !           267:                /* Keep trying q's until we get one far enough from p... */
        !           268:        } while (too_close_together);
        !           269: 
        !           270:        /* In case sizes went awry in making p and q... */
        !           271:        if (mp_compare(p,q) >= 0)       /* ensure that p<q for computing u */
        !           272:        {       mp_move(u,p);
        !           273:                mp_move(p,q);
        !           274:                mp_move(q,u);
        !           275:        }
        !           276: 
        !           277:        derive_rsakeys(n,e,d,p,q,u,ebits);
        !           278:        randflush();            /* ensure recycled random pool is destroyed */
        !           279: 
        !           280:        /* Now test key just to make sure --this had better work! */
        !           281:        {       unit M[MAX_UNIT_PRECISION];
        !           282:                unit C[MAX_UNIT_PRECISION];
        !           283:                mp_init(M,0x1234);              /* material to be signed */
        !           284:                mp_init(C,0);
        !           285:                status = rsa_decrypt(C,M,d,p,q,u);      /* create signature C first */
        !           286:                if (status < 0) /* modexp error? */
        !           287:                        return(status); /* return error status */
        !           288:                mp_init(M,0);           /* ensure test pattern M is destroyed */
        !           289:                status = mp_modexp(M,C,e,n);    /* check signature C */
        !           290:                if (status < 0) /* modexp error? */
        !           291:                        return(status); /* return error status */
        !           292:                if (testne(M,0x1234))   /* test pattern M recovered? */
        !           293:                        return(KEYFAILED);      /* error return, bad key or bad math library */
        !           294:        }
        !           295:        return(0);      /* normal return */
        !           296: }      /* rsa_keygen */
        !           297: 
        !           298: /****************** End of RSA-specific routines  *******************/
        !           299: 
        !           300: 

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