X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/ba6e6b64033b1f9de49feccb5c9cd438354481f7..0f00dc4c8eb47e67bc0f148c2dd109f73a451e0a:/rsa-recover.c diff --git a/rsa-recover.c b/rsa-recover.c deleted file mode 100644 index 4546cc3..0000000 --- a/rsa-recover.c +++ /dev/null @@ -1,242 +0,0 @@ -/* -*-c-*- - * - * $Id: rsa-recover.c,v 1.7 2004/04/08 01:36:15 mdw Exp $ - * - * Recover RSA parameters - * - * (c) 1999 Straylight/Edgeware - */ - -/*----- Licensing notice --------------------------------------------------* - * - * This file is part of Catacomb. - * - * Catacomb is free software; you can redistribute it and/or modify - * it under the terms of the GNU Library General Public License as - * published by the Free Software Foundation; either version 2 of the - * License, or (at your option) any later version. - * - * Catacomb is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU Library General Public License for more details. - * - * You should have received a copy of the GNU Library General Public - * License along with Catacomb; if not, write to the Free - * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, - * MA 02111-1307, USA. - */ - -/*----- Header files ------------------------------------------------------*/ - -#include "mp.h" -#include "mpmont.h" -#include "rsa.h" - -/*----- Main code ---------------------------------------------------------*/ - -/* --- @rsa_recover@ --- * - * - * Arguments: @rsa_priv *rp@ = pointer to parameter block - * - * Returns: Zero if all went well, nonzero if the parameters make no - * sense. - * - * Use: Derives the full set of RSA parameters given a minimal set. - */ - -int rsa_recover(rsa_priv *rp) -{ - /* --- If there is no modulus, calculate it --- */ - - if (!rp->n) { - if (!rp->p || !rp->q) - return (-1); - rp->n = mp_mul(MP_NEW, rp->p, rp->q); - } - - /* --- If there are no factors, compute them --- */ - - else if (!rp->p || !rp->q) { - - /* --- If one is missing, use simple division to recover the other --- */ - - if (rp->p || rp->q) { - mp *r = MP_NEW; - if (rp->p) - mp_div(&rp->q, &r, rp->n, rp->p); - else - mp_div(&rp->p, &r, rp->n, rp->q); - if (!MP_EQ(r, MP_ZERO)) { - mp_drop(r); - return (-1); - } - mp_drop(r); - } - - /* --- Otherwise use the public and private moduli --- */ - - else if (!rp->e || !rp->d) - return (-1); - else { - mp *t; - size_t s; - mp a; mpw aw; - mp *m1; - mpmont mm; - int i; - mp *z = MP_NEW; - - /* --- Work out the appropriate exponent --- * - * - * I need to compute %$s$% and %$t$% such that %$2^s t = e d - 1$%, and - * %$t$% is odd. - */ - - t = mp_mul(MP_NEW, rp->e, rp->d); - t = mp_sub(t, t, MP_ONE); - t = mp_odd(t, t, &s); - - /* --- Set up for the exponentiation --- */ - - mpmont_create(&mm, rp->n); - m1 = mp_sub(MP_NEW, rp->n, mm.r); - - /* --- Now for the main loop --- * - * - * Choose candidate integers and attempt to factor the modulus. - */ - - mp_build(&a, &aw, &aw + 1); - i = 0; - for (;;) { - again: - - /* --- Choose a random %$a$% and calculate %$z = a^t \bmod n$% --- * - * - * If %$z \equiv 1$% or %$z \equiv -1 \pmod n$% then this iteration - * is a failure. - */ - - aw = primetab[i++]; - z = mpmont_mul(&mm, z, &a, mm.r2); - z = mpmont_expr(&mm, z, z, t); - if (MP_EQ(z, mm.r) || MP_EQ(z, m1)) - continue; - - /* --- Now square until something interesting happens --- * - * - * Compute %$z^{2i} \bmod n$%. Eventually, I'll either get %$-1$% or - * %$1$%. If the former, the number is uninteresting, and I need to - * restart. If the latter, the previous number minus 1 has a common - * factor with %$n$%. - */ - - for (;;) { - mp *zz = mp_sqr(MP_NEW, z); - zz = mpmont_reduce(&mm, zz, zz); - if (MP_EQ(zz, mm.r)) { - mp_drop(zz); - goto done; - } else if (MP_EQ(zz, m1)) { - mp_drop(zz); - goto again; - } - mp_drop(z); - z = zz; - } - } - - /* --- Do the factoring --- * - * - * Here's how it actually works. I've found an interesting square - * root of %$1 \pmod n$%. Any square root of 1 must be congruent to - * %$\pm 1$% modulo both %$p$% and %$q$%. Both congruent to %$1$% is - * boring, as is both congruent to %$-1$%. Subtracting one from the - * result makes it congruent to %$0$% modulo %$p$% or %$q$% (and - * nobody cares which), and hence can be extracted by a GCD - * operation. - */ - - done: - z = mpmont_reduce(&mm, z, z); - z = mp_sub(z, z, MP_ONE); - rp->p = MP_NEW; - mp_gcd(&rp->p, 0, 0, rp->n, z); - rp->q = MP_NEW; - mp_div(&rp->q, 0, rp->n, rp->p); - mp_drop(z); - mp_drop(t); - mp_drop(m1); - if (MP_CMP(rp->p, <, rp->q)) { - z = rp->p; - rp->p = rp->q; - rp->q = z; - } - mpmont_destroy(&mm); - } - } - - /* --- If %$e$% or %$d$% is missing, recalculate it --- */ - - if (!rp->e || !rp->d) { - mp *phi; - mp *g = MP_NEW; - mp *p1, *q1; - - /* --- Compute %$\varphi(n)$% --- */ - - phi = mp_sub(MP_NEW, rp->n, rp->p); - phi = mp_sub(phi, phi, rp->q); - phi = mp_add(phi, phi, MP_ONE); - p1 = mp_sub(MP_NEW, rp->p, MP_ONE); - q1 = mp_sub(MP_NEW, rp->q, MP_ONE); - mp_gcd(&g, 0, 0, p1, q1); - mp_div(&phi, 0, phi, g); - mp_drop(p1); - mp_drop(q1); - - /* --- Recover the other exponent --- */ - - if (rp->e) - mp_gcd(&g, 0, &rp->d, phi, rp->e); - else if (rp->d) - mp_gcd(&g, 0, &rp->e, phi, rp->d); - else { - mp_drop(phi); - mp_drop(g); - return (-1); - } - - mp_drop(phi); - if (!MP_EQ(g, MP_ONE)) { - mp_drop(g); - return (-1); - } - mp_drop(g); - } - - /* --- Compute %$q^{-1} \bmod p$% --- */ - - if (!rp->q_inv) - mp_gcd(0, 0, &rp->q_inv, rp->p, rp->q); - - /* --- Compute %$d \bmod (p - 1)$% and %$d \bmod (q - 1)$% --- */ - - if (!rp->dp) { - mp *p1 = mp_sub(MP_NEW, rp->p, MP_ONE); - mp_div(0, &rp->dp, rp->d, p1); - mp_drop(p1); - } - if (!rp->dq) { - mp *q1 = mp_sub(MP_NEW, rp->q, MP_ONE); - mp_div(0, &rp->dq, rp->d, q1); - mp_drop(q1); - } - - /* --- Done --- */ - - return (0); -} - -/*----- That's all, folks -------------------------------------------------*/