/* -*-c-*-
*
- * $Id: rsa-recover.c,v 1.1 1999/12/22 15:50:45 mdw Exp $
+ * $Id: rsa-recover.c,v 1.6 2001/06/16 12:56:38 mdw Exp $
*
* Recover RSA parameters
*
/*----- Revision history --------------------------------------------------*
*
* $Log: rsa-recover.c,v $
+ * Revision 1.6 2001/06/16 12:56:38 mdw
+ * Fixes for interface change to @mpmont_expr@ and @mpmont_mexpr@.
+ *
+ * Revision 1.5 2000/10/08 12:11:22 mdw
+ * Use @MP_EQ@ instead of @MP_CMP@.
+ *
+ * Revision 1.4 2000/07/01 11:22:22 mdw
+ * Remove bad type name `rsa_param'.
+ *
+ * Revision 1.3 2000/06/22 19:03:14 mdw
+ * Use the new @mp_odd@ function.
+ *
+ * Revision 1.2 2000/06/17 12:07:19 mdw
+ * Fix a bug in argument validation. Force %$p > q$% in output. Use
+ * %$\lambda(n) = \lcm(p - 1, q - 1)$% rather than the more traditional
+ * %$\phi(n) = (p - 1)(q - 1)$% when computing the decryption exponent.
+ *
* Revision 1.1 1999/12/22 15:50:45 mdw
* Initial RSA support.
*
/* --- @rsa_recover@ --- *
*
- * Arguments: @rsa_param *rp@ = pointer to parameter block
+ * 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_param *rp)
+int rsa_recover(rsa_priv *rp)
{
/* --- If there is no modulus, calculate it --- */
mp_div(&rp->q, &r, rp->n, rp->p);
else
mp_div(&rp->p, &r, rp->n, rp->q);
- if (MP_CMP(r, !=, MP_ZERO)) {
+ if (!MP_EQ(r, MP_ZERO)) {
mp_drop(r);
return (-1);
}
/* --- Otherwise use the public and private moduli --- */
- else if (rp->e && rp->d) {
+ else if (!rp->e || !rp->d)
+ return (-1);
+ else {
mp *t;
- unsigned s;
- mpscan ms;
+ size_t s;
mp a; mpw aw;
mp *m1;
mpmont mm;
t = mp_mul(MP_NEW, rp->e, rp->d);
t = mp_sub(t, t, MP_ONE);
- s = 0;
- mp_scan(&ms, t);
- for (;;) {
- MP_STEP(&ms);
- if (MP_BIT(&ms))
- break;
- s++;
- }
- t = mp_lsr(t, t, s);
+ t = mp_odd(t, t, &s);
/* --- Set up for the exponentiation --- */
*/
aw = primetab[i++];
- z = mpmont_expr(&mm, z, &a, t);
- if (MP_CMP(z, ==, mm.r) || MP_CMP(z, ==, m1))
+ 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 --- *
for (;;) {
mp *zz = mp_sqr(MP_NEW, z);
zz = mpmont_reduce(&mm, zz, zz);
- if (MP_CMP(zz, ==, mm.r)) {
+ if (MP_EQ(zz, mm.r)) {
mp_drop(zz);
goto done;
- } else if (MP_CMP(zz, ==, m1)) {
+ } else if (MP_EQ(zz, m1)) {
mp_drop(zz);
goto again;
}
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 (!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 --- */
mp_gcd(&g, 0, &rp->e, phi, rp->d);
else {
mp_drop(phi);
+ mp_drop(g);
return (-1);
}
mp_drop(phi);
- if (MP_CMP(g, !=, MP_ONE)) {
+ if (!MP_EQ(g, MP_ONE)) {
mp_drop(g);
return (-1);
}