Return to rsagen.c CVS log

Up to [PGP] / pgp / src

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

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

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