Commit | Line | Data |
---|---|---|
01898d8e | 1 | /* -*-c-*- |
2 | * | |
01898d8e | 3 | * RSA parameter generation |
4 | * | |
5 | * (c) 1999 Straylight/Edgeware | |
6 | */ | |
7 | ||
45c0fd36 | 8 | /*----- Licensing notice --------------------------------------------------* |
01898d8e | 9 | * |
10 | * This file is part of Catacomb. | |
11 | * | |
12 | * Catacomb is free software; you can redistribute it and/or modify | |
13 | * it under the terms of the GNU Library General Public License as | |
14 | * published by the Free Software Foundation; either version 2 of the | |
15 | * License, or (at your option) any later version. | |
45c0fd36 | 16 | * |
01898d8e | 17 | * Catacomb is distributed in the hope that it will be useful, |
18 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
19 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
20 | * GNU Library General Public License for more details. | |
45c0fd36 | 21 | * |
01898d8e | 22 | * You should have received a copy of the GNU Library General Public |
23 | * License along with Catacomb; if not, write to the Free | |
24 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, | |
25 | * MA 02111-1307, USA. | |
26 | */ | |
27 | ||
01898d8e | 28 | /*----- Header files ------------------------------------------------------*/ |
29 | ||
30 | #include <mLib/dstr.h> | |
31 | ||
32 | #include "grand.h" | |
33 | #include "mp.h" | |
bb2e2fd8 | 34 | #include "mpint.h" |
01898d8e | 35 | #include "pgen.h" |
36 | #include "rsa.h" | |
37 | #include "strongprime.h" | |
38 | ||
39 | /*----- Main code ---------------------------------------------------------*/ | |
40 | ||
8de0fc89 | 41 | /* --- @rsa_gen@, @rsa_gen_e --- * |
01898d8e | 42 | * |
b82ec4e8 | 43 | * Arguments: @rsa_priv *rp@ = pointer to block to be filled in |
01898d8e | 44 | * @unsigned nbits@ = required modulus size in bits |
8de0fc89 | 45 | * @mp *e@ = public exponent |
01898d8e | 46 | * @grand *r@ = random number source |
47 | * @unsigned n@ = number of attempts to make | |
48 | * @pgen_proc *event@ = event handler function | |
49 | * @void *ectx@ = argument for the event handler | |
50 | * | |
51 | * Returns: Zero if all went well, nonzero otherwise. | |
52 | * | |
53 | * Use: Constructs a pair of strong RSA primes and other useful RSA | |
54 | * parameters. A small encryption exponent is chosen if | |
55 | * possible. | |
56 | */ | |
57 | ||
8de0fc89 MW |
58 | static int genprime(mp **pp, mp **dd, const char *name, |
59 | unsigned nbits, mp *e, | |
60 | grand *r, unsigned nsteps, pgen_proc *event, void *ectx) | |
01898d8e | 61 | { |
8de0fc89 MW |
62 | pgen_jumpctx jctx; pfilt j; |
63 | mp *p = MP_NEWSEC, *t = MP_NEW, *u = MP_NEW; | |
64 | rabin rb; | |
65 | mpw p3, j3, a; | |
66 | int rc = -1; | |
67 | ||
68 | j.m = MP_NEW; | |
69 | ||
70 | /* Find a start position for the search. */ | |
71 | p = strongprime_setup(name, p, &j, nbits, r, nsteps, event, ectx); | |
72 | if (!p) goto end; | |
73 | ||
74 | /* Special handling for e = 3. */ | |
75 | if (MP_EQ(e, MP_THREE)) { | |
76 | /* We must have p == 2 (mod 3): if p == 0 (mod 3) then p is not prime; if | |
77 | * p == 1 (mod 3) then e|(p - 1). So fiddle the start position and jump | |
78 | * context to allow for this. | |
79 | */ | |
80 | ||
81 | /* Figure out the residues of the start position and jump. */ | |
82 | mp_div(0, &t, p, MP_THREE); p3 = t->v[0]; | |
83 | mp_div(0, &u, j.m, MP_THREE); j3 = u->v[0]; | |
84 | ||
85 | /* If the jump is a multiple of three already, then we're stuffed unless | |
86 | * the start position is 2 (mod 3). This shouldn't happen, since the | |
87 | * jump should be twice a multiple of two large primes, which will be | |
88 | * nonzero (mod 3). | |
89 | * | |
90 | * Set a = (2 - p) j mod 3. Then p' = p + a j == p (mod j), and p' == | |
91 | * p + (2 - p) j^2 == 2 (mod 3). | |
92 | */ | |
93 | assert(j3 != 0); | |
94 | a = ((2 - p3)*j3)%3; | |
95 | if (a == 1) p = mp_add(p, p, j.m); | |
96 | else if (a == 2) { t = mp_lsl(t, j.m, 1); p = mp_add(p, p, t); } | |
97 | ||
98 | /* Finally, multiply j by three to make sure it preserves this | |
99 | * congruence. | |
100 | */ | |
101 | pfilt_muladd(&j, &j, 3, 0); | |
bb2e2fd8 | 102 | } |
103 | ||
8de0fc89 MW |
104 | /* Set the search going. */ |
105 | jctx.j = &j; | |
106 | p = pgen(name, p, p, event, ectx, | |
107 | nsteps, pgen_jump, &jctx, | |
108 | rabin_iters(nbits), pgen_test, &rb); | |
109 | ||
110 | if (!p) goto end; | |
111 | ||
112 | /* Check the GCD constraint. */ | |
113 | t = mp_sub(t, p, MP_ONE); | |
114 | mp_gcd(&t, &u, 0, e, t); | |
115 | if (!MP_EQ(t, MP_ONE)) goto end; | |
116 | ||
117 | /* All is good. */ | |
118 | mp_drop(*pp); *pp = p; p = 0; | |
119 | mp_drop(*dd); *dd = u; u = 0; | |
120 | rc = 0; | |
121 | end: | |
122 | mp_drop(p); mp_drop(t); mp_drop(u); | |
123 | mp_drop(j.m); | |
124 | return (rc); | |
125 | } | |
bb2e2fd8 | 126 | |
8de0fc89 MW |
127 | int rsa_gen_e(rsa_priv *rp, unsigned nbits, mp *e, |
128 | grand *r, unsigned nsteps, pgen_proc *event, void *ectx) | |
129 | { | |
130 | mp *p = MP_NEWSEC, *q = MP_NEWSEC, *n = MP_NEW; | |
131 | mp *dp = MP_NEWSEC, *dq = MP_NEWSEC; | |
132 | mp *t = MP_NEW, *u = MP_NEW, *v = MP_NEW; | |
133 | mp *tt; | |
134 | int rc = -1; | |
135 | ||
136 | #define RETRY(what) \ | |
137 | do { if (nsteps) goto fail; else goto retry_##what; } while (0) | |
138 | ||
139 | /* Find the first prime. */ | |
140 | retry_all: | |
141 | retry_p: | |
142 | if (genprime(&p, &dp, "p", nbits/2, e, r, nsteps, event, ectx)) | |
143 | RETRY(p); | |
144 | ||
145 | /* Find the second prime. */ | |
146 | retry_q: | |
147 | if (genprime(&q, &dq, "q", nbits/2, e, r, nsteps, event, ectx)) | |
148 | RETRY(q); | |
149 | ||
150 | /* Check that gcd(p - 1, q - 1) is sufficiently large. */ | |
151 | u = mp_sub(u, p, MP_ONE); | |
152 | v = mp_sub(v, q, MP_ONE); | |
153 | mp_gcd(&t, 0, 0, u, v); | |
154 | if (mp_bits(t) >= 8) RETRY(all); | |
155 | ||
156 | /* Arrange for p > q. */ | |
157 | if (MP_CMP(p, <, q)) { | |
158 | tt = p; p = q; q = tt; | |
159 | tt = dp; dp = dq; dq = tt; | |
bb2e2fd8 | 160 | } |
01898d8e | 161 | |
8de0fc89 MW |
162 | /* Check that the modulus is the right size. */ |
163 | n = mp_mul(n, p, q); | |
164 | if (mp_bits(n) != nbits) RETRY(all); | |
01898d8e | 165 | |
8de0fc89 MW |
166 | /* Now we want to calculate d. The unit-group exponent is λ = lcm(p - 1, |
167 | * q - 1), so d == e^-1 (mod λ). | |
01898d8e | 168 | */ |
8de0fc89 MW |
169 | u = mp_mul(u, u, v); |
170 | mp_div(&t, 0, u, t); | |
171 | rp->d = mp_modinv(MP_NEW, e, t); | |
172 | ||
173 | /* All done. */ | |
174 | rp->e = MP_COPY(e); | |
175 | rp->q_inv = mp_modinv(MP_NEW, q, p); | |
176 | rp->p = p; p = 0; rp->dp = dp; dp = 0; | |
177 | rp->q = q; q = 0; rp->dq = dq; dq = 0; | |
178 | rp->n = n; n = 0; | |
179 | rc = 0; | |
180 | ||
181 | fail: | |
182 | mp_drop(p); mp_drop(dp); | |
183 | mp_drop(q); mp_drop(dq); | |
184 | mp_drop(n); | |
185 | mp_drop(t); mp_drop(u); mp_drop(v); | |
186 | return (rc); | |
187 | } | |
01898d8e | 188 | |
8de0fc89 MW |
189 | int rsa_gen(rsa_priv *rp, unsigned nbits, |
190 | grand *r, unsigned nsteps, pgen_proc *event, void *ectx) | |
191 | { | |
192 | mp *f4 = mp_fromulong(MP_NEW, 65537); | |
193 | int rc = rsa_gen_e(rp, nbits, f4, r, nsteps, event, ectx); | |
194 | mp_drop(f4); return (rc); | |
01898d8e | 195 | } |
196 | ||
197 | /*----- That's all, folks -------------------------------------------------*/ |