From 60fe6ff72f12d19eed807bab77ffbe5ddeb87c66 Mon Sep 17 00:00:00 2001
From: simon <simon@cda61777-01e9-0310-a592-d414129be87e>
Date: Fri, 23 Mar 2001 13:02:39 +0000
Subject: [PATCH] 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
---
 sshrsa.c | 34 ++++++++++++++++++++++++++--------
 1 file changed, 26 insertions(+), 8 deletions(-)

diff --git a/sshrsa.c b/sshrsa.c
index 9947ceff..fa5bfa25 100644
--- 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;
 }
 
-- 
2.11.0