3 * Recover RSA parameters
5 * (c) 1999 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
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.
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.
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,
28 /*----- Header files ------------------------------------------------------*/
34 /*----- Main code ---------------------------------------------------------*/
36 /* --- @rsa_recover@ --- *
38 * Arguments: @rsa_priv *rp@ = pointer to parameter block
40 * Returns: Zero if all went well, nonzero if the parameters make no
43 * Use: Derives the full set of RSA parameters given a minimal set.
46 int rsa_recover(rsa_priv *rp)
48 /* --- If there is no modulus, calculate it --- */
53 rp->n = mp_mul(MP_NEW, rp->p, rp->q);
56 /* --- If there are no factors, compute them --- */
58 else if (!rp->p || !rp->q) {
60 /* --- If one is missing, use simple division to recover the other --- */
65 mp_div(&rp->q, &r, rp->n, rp->p);
67 mp_div(&rp->p, &r, rp->n, rp->q);
68 if (!MP_EQ(r, MP_ZERO)) {
75 /* --- Otherwise use the public and private moduli --- */
77 else if (!rp->e || !rp->d)
88 /* --- Work out the appropriate exponent --- *
90 * I need to compute %$s$% and %$t$% such that %$2^s t = e d - 1$%, and
94 t = mp_mul(MP_NEW, rp->e, rp->d);
95 t = mp_sub(t, t, MP_ONE);
98 /* --- Set up for the exponentiation --- */
100 mpmont_create(&mm, rp->n);
101 m1 = mp_sub(MP_NEW, rp->n, mm.r);
103 /* --- Now for the main loop --- *
105 * Choose candidate integers and attempt to factor the modulus.
108 mp_build(&a, &aw, &aw + 1);
113 /* --- Choose a random %$a$% and calculate %$z = a^t \bmod n$% --- *
115 * If %$z \equiv 1$% or %$z \equiv -1 \pmod n$% then this iteration
120 z = mpmont_mul(&mm, z, &a, mm.r2);
121 z = mpmont_expr(&mm, z, z, t);
122 if (MP_EQ(z, mm.r) || MP_EQ(z, m1))
125 /* --- Now square until something interesting happens --- *
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
134 mp *zz = mp_sqr(MP_NEW, z);
135 zz = mpmont_reduce(&mm, zz, zz);
136 if (MP_EQ(zz, mm.r)) {
139 } else if (MP_EQ(zz, m1)) {
148 /* --- Do the factoring --- *
150 * Here's how it actually works. I've found an interesting square
151 * root of %$1 \pmod n$%. Any square root of 1 must be congruent to
152 * %$\pm 1$% modulo both %$p$% and %$q$%. Both congruent to %$1$% is
153 * boring, as is both congruent to %$-1$%. Subtracting one from the
154 * result makes it congruent to %$0$% modulo %$p$% or %$q$% (and
155 * nobody cares which), and hence can be extracted by a GCD
160 z = mpmont_reduce(&mm, z, z);
161 z = mp_sub(z, z, MP_ONE);
163 mp_gcd(&rp->p, 0, 0, rp->n, z);
165 mp_div(&rp->q, 0, rp->n, rp->p);
169 if (MP_CMP(rp->p, <, rp->q)) {
178 /* --- If %$e$% or %$d$% is missing, recalculate it --- */
180 if (!rp->e || !rp->d) {
185 /* --- Compute %$\varphi(n)$% --- */
187 phi = mp_sub(MP_NEW, rp->n, rp->p);
188 phi = mp_sub(phi, phi, rp->q);
189 phi = mp_add(phi, phi, MP_ONE);
190 p1 = mp_sub(MP_NEW, rp->p, MP_ONE);
191 q1 = mp_sub(MP_NEW, rp->q, MP_ONE);
192 mp_gcd(&g, 0, 0, p1, q1);
193 mp_div(&phi, 0, phi, g);
197 /* --- Recover the other exponent --- */
200 mp_gcd(&g, 0, &rp->d, phi, rp->e);
202 mp_gcd(&g, 0, &rp->e, phi, rp->d);
210 if (!MP_EQ(g, MP_ONE)) {
217 /* --- Compute %$q^{-1} \bmod p$% --- */
220 mp_gcd(0, 0, &rp->q_inv, rp->p, rp->q);
222 /* --- Compute %$d \bmod (p - 1)$% and %$d \bmod (q - 1)$% --- */
225 mp *p1 = mp_sub(MP_NEW, rp->p, MP_ONE);
226 mp_div(0, &rp->dp, rp->d, p1);
230 mp *q1 = mp_sub(MP_NEW, rp->q, MP_ONE);
231 mp_div(0, &rp->dq, rp->d, q1);
240 /*----- That's all, folks -------------------------------------------------*/