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

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