int rsa_recover(rsa_priv *rp)
{
+ int rc = -1;
int i;
size_t s;
mpmont mm;
mp a; mpw aw;
- mp *g = MP_NEW, *r = MP_NEW, *t = MP_NEW;
+ mp *g = MP_NEW, *r = MP_NEW, *t = MP_NEW, *zt;
mp *m1 = MP_NEW, *z = MP_NEW, *zz = MP_NEW;
mp *phi = MP_NEW, *p1 = MP_NEW, *q1 = MP_NEW;
+ mm.r = 0;
+
/* --- If there is no modulus, calculate it --- */
if (!rp->n) {
- if (!rp->p || !rp->q)
- return (-1);
+ if (!rp->p || !rp->q) goto out;
rp->n = mp_mul(MP_NEW, rp->p, rp->q);
}
/* --- If one is missing, use simple division to recover the other --- */
if (rp->p || rp->q) {
- 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);
+ 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)) goto out;
}
/* --- Otherwise use the public and private moduli --- */
else if (!rp->e || !rp->d)
- return (-1);
+ goto out;
else {
/* --- Work out the appropriate exponent --- *
/* --- Set up for the exponentiation --- */
- mpmont_create(&mm, rp->n);
+ if (mpmont_create(&mm, rp->n)) goto out;
m1 = mp_sub(m1, rp->n, mm.r);
/* --- Now for the main loop --- *
mp_build(&a, &aw, &aw + 1);
i = 0;
+
+ 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.
+ */
+
+ if (i > NPRIME) goto out;
+ 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)) goto again;
+
+ /* --- 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 (;;) {
- 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 (;;) {
- zz = mp_sqr(zz, 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;
- zz = MP_NEW;
- }
+ zz = mp_sqr(zz, z);
+ zz = mpmont_reduce(&mm, zz, zz);
+ if (MP_EQ(zz, mm.r)) goto done;
+ else if (MP_EQ(zz, m1)) goto again;
+ zt = z; z = zz; zz = zt;
}
/* --- Do the factoring --- *
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 (MP_CMP(rp->p, <, rp->q))
+ { zt = rp->p; rp->p = rp->q; rp->q = zt; }
}
}
q1 = mp_sub(q1, rp->q, MP_ONE);
mp_gcd(&g, 0, 0, p1, q1);
mp_div(&phi, 0, phi, g);
- mp_drop(p1); p1 = MP_NEW;
- mp_drop(q1); q1 = MP_NEW;
/* --- 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);
+ 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 goto out;
+ if (!MP_EQ(g, MP_ONE)) goto out;
}
/* --- Compute %$q^{-1} \bmod p$% --- */
- if (!rp->q_inv)
- mp_gcd(0, 0, &rp->q_inv, rp->p, rp->q);
+ if (!rp->q_inv) {
+ mp_gcd(&g, 0, &rp->q_inv, rp->p, rp->q);
+ if (!MP_EQ(g, MP_ONE)) goto out;
+ }
/* --- Compute %$d \bmod (p - 1)$% and %$d \bmod (q - 1)$% --- */
if (!rp->dp) {
p1 = mp_sub(p1, rp->p, MP_ONE);
mp_div(0, &rp->dp, rp->d, p1);
- mp_drop(p1);
}
if (!rp->dq) {
q1 = mp_sub(q1, rp->q, MP_ONE);
mp_div(0, &rp->dq, rp->d, q1);
- mp_drop(q1);
}
/* --- Done --- */
- return (0);
+ rc = 0;
+out:
+ mp_drop(g); mp_drop(r); mp_drop(t);
+ mp_drop(m1); mp_drop(z); mp_drop(zz);
+ mp_drop(phi); mp_drop(p1); mp_drop(q1);
+ if (mm.r) mpmont_destroy(&mm);
+ return (rc);
}
/*----- That's all, folks -------------------------------------------------*/