chiark - git - mdw - catacomb/blob - pub/rsa-gen.c

   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 -------------------------------------------------*/