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

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