| 1 | /* -*-c-*- |
| 2 | * |
| 3 | * RSA parameter generation |
| 4 | * |
| 5 | * (c) 1999 Straylight/Edgeware |
| 6 | */ |
| 7 | |
| 8 | /*----- Licensing notice --------------------------------------------------* |
| 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. |
| 16 | * |
| 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. |
| 21 | * |
| 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 | |
| 28 | /*----- Header files ------------------------------------------------------*/ |
| 29 | |
| 30 | #include <mLib/dstr.h> |
| 31 | |
| 32 | #include "grand.h" |
| 33 | #include "mp.h" |
| 34 | #include "mpint.h" |
| 35 | #include "pgen.h" |
| 36 | #include "rsa.h" |
| 37 | #include "strongprime.h" |
| 38 | |
| 39 | /*----- Main code ---------------------------------------------------------*/ |
| 40 | |
| 41 | /* --- @rsa_gen@, @rsa_gen_e --- * |
| 42 | * |
| 43 | * Arguments: @rsa_priv *rp@ = pointer to block to be filled in |
| 44 | * @unsigned nbits@ = required modulus size in bits |
| 45 | * @mp *e@ = public exponent |
| 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 | |
| 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) |
| 61 | { |
| 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); |
| 102 | } |
| 103 | |
| 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 | } |
| 126 | |
| 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; |
| 160 | } |
| 161 | |
| 162 | /* Check that the modulus is the right size. */ |
| 163 | n = mp_mul(n, p, q); |
| 164 | if (mp_bits(n) != nbits) RETRY(all); |
| 165 | |
| 166 | /* Now we want to calculate d. The unit-group exponent is λ = lcm(p - 1, |
| 167 | * q - 1), so d == e^-1 (mod λ). |
| 168 | */ |
| 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 | } |
| 188 | |
| 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); |
| 195 | } |
| 196 | |
| 197 | /*----- That's all, folks -------------------------------------------------*/ |