git.distorted.org.uk Git - u/mdw/catacomb/blob - rsa-recover.c

   1 /* -*-c-*-
   2  *
   3  * $Id: rsa-recover.c,v 1.5 2000/10/08 12:11:22 mdw Exp $
   4  *
   5  * Recover RSA parameters
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: rsa-recover.c,v $
  33  * Revision 1.5  2000/10/08 12:11:22  mdw
  34  * Use @MP_EQ@ instead of @MP_CMP@.
  35  *
  36  * Revision 1.4  2000/07/01 11:22:22  mdw
  37  * Remove bad type name `rsa_param'.
  38  *
  39  * Revision 1.3  2000/06/22 19:03:14  mdw
  40  * Use the new @mp_odd@ function.
  41  *
  42  * Revision 1.2  2000/06/17 12:07:19  mdw
  43  * Fix a bug in argument validation.  Force %$p > q$% in output.  Use
  44  * %$\lambda(n) = \lcm(p - 1, q - 1)$% rather than the more traditional
  45  * %$\phi(n) = (p - 1)(q - 1)$% when computing the decryption exponent.
  46  *
  47  * Revision 1.1  1999/12/22 15:50:45  mdw
  48  * Initial RSA support.
  49  *
  50  */
  51
  52 /*----- Header files ------------------------------------------------------*/
  53
  54 #include "mp.h"
  55 #include "mpmont.h"
  56 #include "rsa.h"
  57
  58 /*----- Main code ---------------------------------------------------------*/
  59
  60 /* --- @rsa_recover@ --- *
  61  *
  62  * Arguments:   @rsa_priv *rp@ = pointer to parameter block
  63  *
  64  * Returns:     Zero if all went well, nonzero if the parameters make no
  65  *              sense.
  66  *
  67  * Use:         Derives the full set of RSA parameters given a minimal set.
  68  */
  69
  70 int rsa_recover(rsa_priv *rp)
  71 {
  72   /* --- If there is no modulus, calculate it --- */
  73
  74   if (!rp->n) {
  75     if (!rp->p || !rp->q)
  76       return (-1);
  77     rp->n = mp_mul(MP_NEW, rp->p, rp->q);
  78   }
  79
  80   /* --- If there are no factors, compute them --- */
  81
  82   else if (!rp->p || !rp->q) {
  83
  84     /* --- If one is missing, use simple division to recover the other --- */
  85
  86     if (rp->p || rp->q) {
  87       mp *r = MP_NEW;
  88       if (rp->p)
  89         mp_div(&rp->q, &r, rp->n, rp->p);
  90       else
  91         mp_div(&rp->p, &r, rp->n, rp->q);
  92       if (!MP_EQ(r, MP_ZERO)) {
  93         mp_drop(r);
  94         return (-1);
  95       }
  96       mp_drop(r);
  97     }
  98
  99     /* --- Otherwise use the public and private moduli --- */
 100
 101     else if (!rp->e || !rp->d)
 102       return (-1);
 103     else {
 104       mp *t;
 105       size_t s;
 106       mp a; mpw aw;
 107       mp *m1;
 108       mpmont mm;
 109       int i;
 110       mp *z = MP_NEW;
 111
 112       /* --- Work out the appropriate exponent --- *
 113        *
 114        * I need to compute %$s$% and %$t$% such that %$2^s t = e d - 1$%, and
 115        * %$t$% is odd.
 116        */
 117
 118       t = mp_mul(MP_NEW, rp->e, rp->d);
 119       t = mp_sub(t, t, MP_ONE);
 120       t = mp_odd(t, t, &s);
 121
 122       /* --- Set up for the exponentiation --- */
 123
 124       mpmont_create(&mm, rp->n);
 125       m1 = mp_sub(MP_NEW, rp->n, mm.r);
 126
 127       /* --- Now for the main loop --- *
 128        *
 129        * Choose candidate integers and attempt to factor the modulus.
 130        */
 131
 132       mp_build(&a, &aw, &aw + 1);
 133       i = 0;
 134       for (;;) {
 135       again:
 136
 137         /* --- Choose a random %$a$% and calculate %$z = a^t \bmod n$% --- *
 138          *
 139          * If %$z \equiv 1$% or %$z \equiv -1 \pmod n$% then this iteration
 140          * is a failure.
 141          */
 142
 143         aw = primetab[i++];
 144         z = mpmont_expr(&mm, z, &a, t);
 145         if (MP_EQ(z, mm.r) || MP_EQ(z, m1))
 146           continue;
 147
 148         /* --- Now square until something interesting happens --- *
 149          *
 150          * Compute %$z^{2i} \bmod n$%.  Eventually, I'll either get %$-1$% or
 151          * %$1$%.  If the former, the number is uninteresting, and I need to
 152          * restart.  If the latter, the previous number minus 1 has a common
 153          * factor with %$n$%.
 154          */
 155
 156         for (;;) {
 157           mp *zz = mp_sqr(MP_NEW, z);
 158           zz = mpmont_reduce(&mm, zz, zz);
 159           if (MP_EQ(zz, mm.r)) {
 160             mp_drop(zz);
 161             goto done;
 162           } else if (MP_EQ(zz, m1)) {
 163             mp_drop(zz);
 164             goto again;
 165           }
 166           mp_drop(z);
 167           z = zz;
 168         }
 169       }
 170
 171       /* --- Do the factoring --- *
 172        *
 173        * Here's how it actually works.  I've found an interesting square
 174        * root of %$1 \pmod n$%.  Any square root of 1 must be congruent to
 175        * %$\pm 1$% modulo both %$p$% and %$q$%.  Both congruent to %$1$% is
 176        * boring, as is both congruent to %$-1$%.  Subtracting one from the
 177        * result makes it congruent to %$0$% modulo %$p$% or %$q$% (and
 178        * nobody cares which), and hence can be extracted by a GCD
 179        * operation.
 180        */
 181
 182     done:
 183       z = mpmont_reduce(&mm, z, z);
 184       z = mp_sub(z, z, MP_ONE);
 185       rp->p = MP_NEW;
 186       mp_gcd(&rp->p, 0, 0, rp->n, z);
 187       rp->q = MP_NEW;
 188       mp_div(&rp->q, 0, rp->n, rp->p);
 189       mp_drop(z);
 190       mp_drop(t);
 191       mp_drop(m1);
 192       if (MP_CMP(rp->p, <, rp->q)) {
 193         z = rp->p;
 194         rp->p = rp->q;
 195         rp->q = z;
 196       }
 197       mpmont_destroy(&mm);
 198     }
 199   }
 200
 201   /* --- If %$e$% or %$d$% is missing, recalculate it --- */
 202
 203   if (!rp->e || !rp->d) {
 204     mp *phi;
 205     mp *g = MP_NEW;
 206     mp *p1, *q1;
 207
 208     /* --- Compute %$\varphi(n)$% --- */
 209
 210     phi = mp_sub(MP_NEW, rp->n, rp->p);
 211     phi = mp_sub(phi, phi, rp->q);
 212     phi = mp_add(phi, phi, MP_ONE);
 213     p1 = mp_sub(MP_NEW, rp->p, MP_ONE);
 214     q1 = mp_sub(MP_NEW, rp->q, MP_ONE);
 215     mp_gcd(&g, 0, 0, p1, q1);
 216     mp_div(&phi, 0, phi, g);
 217     mp_drop(p1);
 218     mp_drop(q1);
 219
 220     /* --- Recover the other exponent --- */
 221
 222     if (rp->e)
 223       mp_gcd(&g, 0, &rp->d, phi, rp->e);
 224     else if (rp->d)
 225       mp_gcd(&g, 0, &rp->e, phi, rp->d);
 226     else {
 227       mp_drop(phi);
 228       mp_drop(g);
 229       return (-1);
 230     }
 231
 232     mp_drop(phi);
 233     if (!MP_EQ(g, MP_ONE)) {
 234       mp_drop(g);
 235       return (-1);
 236     }
 237     mp_drop(g);
 238   }
 239
 240   /* --- Compute %$q^{-1} \bmod p$% --- */
 241
 242   if (!rp->q_inv)
 243     mp_gcd(0, 0, &rp->q_inv, rp->p, rp->q);
 244
 245   /* --- Compute %$d \bmod (p - 1)$% and %$d \bmod (q - 1)$% --- */
 246
 247   if (!rp->dp) {
 248     mp *p1 = mp_sub(MP_NEW, rp->p, MP_ONE);
 249     mp_div(0, &rp->dp, rp->d, p1);
 250     mp_drop(p1);
 251   }
 252   if (!rp->dq) {
 253     mp *q1 = mp_sub(MP_NEW, rp->q, MP_ONE);
 254     mp_div(0, &rp->dq, rp->d, q1);
 255     mp_drop(q1);
 256   }
 257
 258   /* --- Done --- */
 259
 260   return (0);
 261 }
 262
 263 /*----- That's all, folks -------------------------------------------------*/