Modify the new rsa_verify routine. We now also check the integrity of

the private data (verifying that p > q and that iqmp really is the
inverse of q mod p). In addition, we _no longer_ check that e*d == 1
mod (p-1)(q-1): instead we do separate checks mod (p-1) and mod (q-1),
since the order of the multiplicative group mod n is actually equal to
lcm(p-1,q-1) rather than phi(n)=(p-1)(q-1). (In other words, the
Fermat-Euler theorem doesn't point both ways.)

git-svn-id: svn://svn.tartarus.org/sgt/putty@1024 cda61777-01e9-0310-a592-d414129be87e

diff --git a/sshrsa.c b/sshrsa.c
index 9947cef..fa5bfa2 100644 (file)
--- a/sshrsa.c
+++ b/sshrsa.c
@@ -153,10 +153,11 @@ void rsa_fingerprint(char *str, int len, struct RSAKey *key) {
 
 /*
  * Verify that the public data in an RSA key matches the private
- * data.
+ * data. We also check the private data itself: we ensure that p >
+ * q and that iqmp really is the inverse of q mod p.
  */
 int rsa_verify(struct RSAKey *key) {
-    Bignum n, ed, pm1, qm1, pm1qm1;
+    Bignum n, ed, pm1, qm1;
     int cmp;
 
     /* n must equal pq. */
@@ -166,21 +167,38 @@ int rsa_verify(struct RSAKey *key) {
     if (cmp != 0)
        return 0;
 
-    /* e * d must be congruent to 1, modulo (p-1)(q-1). */
+    /* e * d must be congruent to 1, modulo (p-1) and modulo (q-1). */
     pm1 = copybn(key->p);
     decbn(pm1);
+    ed = modmul(key->exponent, key->private_exponent, pm1);
+    cmp = bignum_cmp(ed, One);
+    sfree(ed);
+    if (cmp != 0)
+       return 0;
+
     qm1 = copybn(key->q);
     decbn(qm1);
-    pm1qm1 = bigmul(pm1, qm1);
-    freebn(pm1);
-    freebn(qm1);
-    ed = modmul(key->exponent, key->private_exponent, pm1qm1);
-    sfree(pm1qm1);
+    ed = modmul(key->exponent, key->private_exponent, qm1);
     cmp = bignum_cmp(ed, One);
     sfree(ed);
     if (cmp != 0)
        return 0;
 
+    /*
+     * Ensure p > q.
+     */
+    if (bignum_cmp(key->p, key->q) <= 0)
+        return 0;
+
+    /*
+     * Ensure iqmp * q is congruent to 1, modulo p.
+     */
+    n = modmul(key->iqmp, key->q, key->p);
+    cmp = bignum_cmp(n, One);
+    sfree(n);
+    if (cmp != 0)
+        return 0;
+
     return 1;
 }