+++ /dev/null
-/* -*-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 -------------------------------------------------*/
projects / u / mdw / catacomb / blobdiff