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