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