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