| 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 rc = -1; |
| 53 | int i; |
| 54 | size_t s; |
| 55 | mpmont mm; |
| 56 | mp a; mpw aw; |
| 57 | mp *g = MP_NEW, *r = MP_NEW, *t = MP_NEW, *zt; |
| 58 | mp *m1 = MP_NEW, *z = MP_NEW, *zz = MP_NEW; |
| 59 | mp *phi = MP_NEW, *p1 = MP_NEW, *q1 = MP_NEW; |
| 60 | |
| 61 | mm.r = 0; |
| 62 | |
| 63 | /* --- If there is no modulus, calculate it --- */ |
| 64 | |
| 65 | if (!rp->n) { |
| 66 | if (!rp->p || !rp->q) goto out; |
| 67 | rp->n = mp_mul(MP_NEW, rp->p, rp->q); |
| 68 | } |
| 69 | |
| 70 | /* --- If there are no factors, compute them --- */ |
| 71 | |
| 72 | else if (!rp->p || !rp->q) { |
| 73 | |
| 74 | /* --- If one is missing, use simple division to recover the other --- */ |
| 75 | |
| 76 | if (rp->p || rp->q) { |
| 77 | if (rp->p) mp_div(&rp->q, &r, rp->n, rp->p); |
| 78 | else mp_div(&rp->p, &r, rp->n, rp->q); |
| 79 | if (!MP_EQ(r, MP_ZERO)) goto out; |
| 80 | } |
| 81 | |
| 82 | /* --- Otherwise use the public and private moduli --- */ |
| 83 | |
| 84 | else if (!rp->e || !rp->d) |
| 85 | goto out; |
| 86 | else { |
| 87 | |
| 88 | /* --- Work out the appropriate exponent --- * |
| 89 | * |
| 90 | * I need to compute %$s$% and %$t$% such that %$2^s t = e d - 1$%, and |
| 91 | * %$t$% is odd. |
| 92 | */ |
| 93 | |
| 94 | t = mp_mul(t, rp->e, rp->d); |
| 95 | t = mp_sub(t, t, MP_ONE); |
| 96 | t = mp_odd(t, t, &s); |
| 97 | |
| 98 | /* --- Set up for the exponentiation --- */ |
| 99 | |
| 100 | if (mpmont_create(&mm, rp->n)) goto out; |
| 101 | m1 = mp_sub(m1, rp->n, mm.r); |
| 102 | |
| 103 | /* --- Now for the main loop --- * |
| 104 | * |
| 105 | * Choose candidate integers and attempt to factor the modulus. |
| 106 | */ |
| 107 | |
| 108 | mp_build(&a, &aw, &aw + 1); |
| 109 | i = 0; |
| 110 | |
| 111 | again: |
| 112 | |
| 113 | /* --- Choose a random %$a$% and calculate %$z = a^t \bmod n$% --- * |
| 114 | * |
| 115 | * If %$z \equiv 1$% or %$z \equiv -1 \pmod n$% then this iteration |
| 116 | * is a failure. |
| 117 | */ |
| 118 | |
| 119 | if (i > NPRIME) goto out; |
| 120 | aw = primetab[i++]; |
| 121 | z = mpmont_mul(&mm, z, &a, mm.r2); |
| 122 | z = mpmont_expr(&mm, z, z, t); |
| 123 | if (MP_EQ(z, mm.r) || MP_EQ(z, m1)) goto again; |
| 124 | |
| 125 | /* --- Now square until something interesting happens --- * |
| 126 | * |
| 127 | * Compute %$z^{2i} \bmod n$%. Eventually, I'll either get %$-1$% or |
| 128 | * %$1$%. If the former, the number is uninteresting, and I need to |
| 129 | * restart. If the latter, the previous number minus 1 has a common |
| 130 | * factor with %$n$%. |
| 131 | */ |
| 132 | |
| 133 | for (;;) { |
| 134 | zz = mp_sqr(zz, z); |
| 135 | zz = mpmont_reduce(&mm, zz, zz); |
| 136 | if (MP_EQ(zz, mm.r)) goto done; |
| 137 | else if (MP_EQ(zz, m1)) goto again; |
| 138 | zt = z; z = zz; zz = zt; |
| 139 | } |
| 140 | |
| 141 | /* --- Do the factoring --- * |
| 142 | * |
| 143 | * Here's how it actually works. I've found an interesting square |
| 144 | * root of %$1 \pmod n$%. Any square root of 1 must be congruent to |
| 145 | * %$\pm 1$% modulo both %$p$% and %$q$%. Both congruent to %$1$% is |
| 146 | * boring, as is both congruent to %$-1$%. Subtracting one from the |
| 147 | * result makes it congruent to %$0$% modulo %$p$% or %$q$% (and |
| 148 | * nobody cares which), and hence can be extracted by a GCD |
| 149 | * operation. |
| 150 | */ |
| 151 | |
| 152 | done: |
| 153 | z = mpmont_reduce(&mm, z, z); |
| 154 | z = mp_sub(z, z, MP_ONE); |
| 155 | mp_gcd(&rp->p, 0, 0, rp->n, z); |
| 156 | mp_div(&rp->q, 0, rp->n, rp->p); |
| 157 | if (MP_CMP(rp->p, <, rp->q)) |
| 158 | { zt = rp->p; rp->p = rp->q; rp->q = zt; } |
| 159 | } |
| 160 | } |
| 161 | |
| 162 | /* --- If %$e$% or %$d$% is missing, recalculate it --- */ |
| 163 | |
| 164 | if (!rp->e || !rp->d) { |
| 165 | |
| 166 | /* --- Compute %$\varphi(n)$% --- */ |
| 167 | |
| 168 | phi = mp_sub(phi, rp->n, rp->p); |
| 169 | phi = mp_sub(phi, phi, rp->q); |
| 170 | phi = mp_add(phi, phi, MP_ONE); |
| 171 | p1 = mp_sub(p1, rp->p, MP_ONE); |
| 172 | q1 = mp_sub(q1, rp->q, MP_ONE); |
| 173 | mp_gcd(&g, 0, 0, p1, q1); |
| 174 | mp_div(&phi, 0, phi, g); |
| 175 | |
| 176 | /* --- Recover the other exponent --- */ |
| 177 | |
| 178 | if (rp->e) mp_gcd(&g, 0, &rp->d, phi, rp->e); |
| 179 | else if (rp->d) mp_gcd(&g, 0, &rp->e, phi, rp->d); |
| 180 | else goto out; |
| 181 | if (!MP_EQ(g, MP_ONE)) goto out; |
| 182 | } |
| 183 | |
| 184 | /* --- Compute %$q^{-1} \bmod p$% --- */ |
| 185 | |
| 186 | if (!rp->q_inv) { |
| 187 | mp_gcd(&g, 0, &rp->q_inv, rp->p, rp->q); |
| 188 | if (!MP_EQ(g, MP_ONE)) goto out; |
| 189 | } |
| 190 | |
| 191 | /* --- Compute %$d \bmod (p - 1)$% and %$d \bmod (q - 1)$% --- */ |
| 192 | |
| 193 | if (!rp->dp) { |
| 194 | p1 = mp_sub(p1, rp->p, MP_ONE); |
| 195 | mp_div(0, &rp->dp, rp->d, p1); |
| 196 | } |
| 197 | if (!rp->dq) { |
| 198 | q1 = mp_sub(q1, rp->q, MP_ONE); |
| 199 | mp_div(0, &rp->dq, rp->d, q1); |
| 200 | } |
| 201 | |
| 202 | /* --- Done --- */ |
| 203 | |
| 204 | rc = 0; |
| 205 | out: |
| 206 | mp_drop(g); mp_drop(r); mp_drop(t); |
| 207 | mp_drop(m1); mp_drop(z); mp_drop(zz); |
| 208 | mp_drop(phi); mp_drop(p1); mp_drop(q1); |
| 209 | if (mm.r) mpmont_destroy(&mm); |
| 210 | return (rc); |
| 211 | } |
| 212 | |
| 213 | /*----- That's all, folks -------------------------------------------------*/ |