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