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

   1 /* -*-c-*-
   2  *
   3  * Recover RSA parameters
   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 "mp.h"
  31 #include "mpmont.h"
  32 #include "rsa.h"
  33
  34 /*----- Main code ---------------------------------------------------------*/
  35
  36 /* --- @rsa_recover@ --- *
  37  *
  38  * Arguments:   @rsa_priv *rp@ = pointer to parameter block
  39  *
  40  * Returns:     Zero if all went well, nonzero if the parameters make no
  41  *              sense.
  42  *
  43  * Use:         Derives the full set of RSA parameters given a minimal set.
  44  *
  45  *              On failure, the parameter block might be partially filled in,
  46  *              but the @rsa_privfree@ function will be able to free it
  47  *              successfully.
  48  */
  49
  50 int rsa_recover(rsa_priv *rp)
  51 {
  52   int i;
  53   size_t s;
  54   mpmont mm;
  55   mp a; mpw aw;
  56   mp *g = MP_NEW, *r = MP_NEW, *t = MP_NEW;
  57   mp *m1 = MP_NEW, *z = MP_NEW, *zz = MP_NEW;
  58   mp *phi = MP_NEW, *p1 = MP_NEW, *q1 = MP_NEW;
  59
  60   /* --- If there is no modulus, calculate it --- */
  61
  62   if (!rp->n) {
  63     if (!rp->p || !rp->q)
  64       return (-1);
  65     rp->n = mp_mul(MP_NEW, rp->p, rp->q);
  66   }
  67
  68   /* --- If there are no factors, compute them --- */
  69
  70   else if (!rp->p || !rp->q) {
  71
  72     /* --- If one is missing, use simple division to recover the other --- */
  73
  74     if (rp->p || rp->q) {
  75       if (rp->p)
  76         mp_div(&rp->q, &r, rp->n, rp->p);
  77       else
  78         mp_div(&rp->p, &r, rp->n, rp->q);
  79       if (!MP_EQ(r, MP_ZERO)) {
  80         mp_drop(r);
  81         return (-1);
  82       }
  83       mp_drop(r);
  84     }
  85
  86     /* --- Otherwise use the public and private moduli --- */
  87
  88     else if (!rp->e || !rp->d)
  89       return (-1);
  90     else {
  91
  92       /* --- Work out the appropriate exponent --- *
  93        *
  94        * I need to compute %$s$% and %$t$% such that %$2^s t = e d - 1$%, and
  95        * %$t$% is odd.
  96        */
  97
  98       t = mp_mul(t, rp->e, rp->d);
  99       t = mp_sub(t, t, MP_ONE);
 100       t = mp_odd(t, t, &s);
 101
 102       /* --- Set up for the exponentiation --- */
 103
 104       mpmont_create(&mm, rp->n);
 105       m1 = mp_sub(m1, rp->n, mm.r);
 106
 107       /* --- Now for the main loop --- *
 108        *
 109        * Choose candidate integers and attempt to factor the modulus.
 110        */
 111
 112       mp_build(&a, &aw, &aw + 1);
 113       i = 0;
 114
 115     again:
 116
 117       /* --- Choose a random %$a$% and calculate %$z = a^t \bmod n$% --- *
 118        *
 119        * If %$z \equiv 1$% or %$z \equiv -1 \pmod n$% then this iteration
 120        * is a failure.
 121        */
 122
 123       aw = primetab[i++];
 124       z = mpmont_mul(&mm, z, &a, mm.r2);
 125       z = mpmont_expr(&mm, z, z, t);
 126       if (MP_EQ(z, mm.r) || MP_EQ(z, m1))
 127         goto again;
 128
 129       /* --- Now square until something interesting happens --- *
 130        *
 131        * Compute %$z^{2i} \bmod n$%.  Eventually, I'll either get %$-1$% or
 132        * %$1$%.  If the former, the number is uninteresting, and I need to
 133        * restart.  If the latter, the previous number minus 1 has a common
 134        * factor with %$n$%.
 135        */
 136
 137       for (;;) {
 138         zz = mp_sqr(zz, z);
 139         zz = mpmont_reduce(&mm, zz, zz);
 140         if (MP_EQ(zz, mm.r)) {
 141           mp_drop(zz);
 142           goto done;
 143         } else if (MP_EQ(zz, m1)) {
 144           mp_drop(zz);
 145           goto again;
 146         }
 147         mp_drop(z);
 148         z = zz;
 149         zz = MP_NEW;
 150       }
 151
 152       /* --- Do the factoring --- *
 153        *
 154        * Here's how it actually works.  I've found an interesting square
 155        * root of %$1 \pmod n$%.  Any square root of 1 must be congruent to
 156        * %$\pm 1$% modulo both %$p$% and %$q$%.  Both congruent to %$1$% is
 157        * boring, as is both congruent to %$-1$%.  Subtracting one from the
 158        * result makes it congruent to %$0$% modulo %$p$% or %$q$% (and
 159        * nobody cares which), and hence can be extracted by a GCD
 160        * operation.
 161        */
 162
 163     done:
 164       z = mpmont_reduce(&mm, z, z);
 165       z = mp_sub(z, z, MP_ONE);
 166       rp->p = MP_NEW;
 167       mp_gcd(&rp->p, 0, 0, rp->n, z);
 168       rp->q = MP_NEW;
 169       mp_div(&rp->q, 0, rp->n, rp->p);
 170       mp_drop(z);
 171       mp_drop(t);
 172       mp_drop(m1);
 173       if (MP_CMP(rp->p, <, rp->q)) {
 174         z = rp->p;
 175         rp->p = rp->q;
 176         rp->q = z;
 177       }
 178       mpmont_destroy(&mm);
 179     }
 180   }
 181
 182   /* --- If %$e$% or %$d$% is missing, recalculate it --- */
 183
 184   if (!rp->e || !rp->d) {
 185
 186     /* --- Compute %$\varphi(n)$% --- */
 187
 188     phi = mp_sub(phi, rp->n, rp->p);
 189     phi = mp_sub(phi, phi, rp->q);
 190     phi = mp_add(phi, phi, MP_ONE);
 191     p1 = mp_sub(p1, rp->p, MP_ONE);
 192     q1 = mp_sub(q1, rp->q, MP_ONE);
 193     mp_gcd(&g, 0, 0, p1, q1);
 194     mp_div(&phi, 0, phi, g);
 195     mp_drop(p1); p1 = MP_NEW;
 196     mp_drop(q1); q1 = MP_NEW;
 197
 198     /* --- Recover the other exponent --- */
 199
 200     if (rp->e)
 201       mp_gcd(&g, 0, &rp->d, phi, rp->e);
 202     else if (rp->d)
 203       mp_gcd(&g, 0, &rp->e, phi, rp->d);
 204     else {
 205       mp_drop(phi);
 206       mp_drop(g);
 207       return (-1);
 208     }
 209
 210     mp_drop(phi);
 211     if (!MP_EQ(g, MP_ONE)) {
 212       mp_drop(g);
 213       return (-1);
 214     }
 215     mp_drop(g);
 216   }
 217
 218   /* --- Compute %$q^{-1} \bmod p$% --- */
 219
 220   if (!rp->q_inv)
 221     mp_gcd(0, 0, &rp->q_inv, rp->p, rp->q);
 222
 223   /* --- Compute %$d \bmod (p - 1)$% and %$d \bmod (q - 1)$% --- */
 224
 225   if (!rp->dp) {
 226     p1 = mp_sub(p1, rp->p, MP_ONE);
 227     mp_div(0, &rp->dp, rp->d, p1);
 228     mp_drop(p1);
 229   }
 230   if (!rp->dq) {
 231     q1 = mp_sub(q1, rp->q, MP_ONE);
 232     mp_div(0, &rp->dq, rp->d, q1);
 233     mp_drop(q1);
 234   }
 235
 236   /* --- Done --- */
 237
 238   return (0);
 239 }
 240
 241 /*----- That's all, folks -------------------------------------------------*/