![[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 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.