Use Knuth algorithm Y for computing DSA "w = inv(s) mod q".

CVS patchset: 5339
CVS date: 2002/02/28 15:48:39

1 files changed, 142 insertions, 178 deletions

diff --git a/rpmio/tinv.c b/rpmio/tinv.c
index 81eec2d71..9ecf43fc2 100644
--- a/rpmio/tinv.c
+++ b/rpmio/tinv.c
@@ -26,7 +26,6 @@ static int Zmp32binv_w(const mp32barrett* b, uint32 xsize, const uint32* xdata,
 	mp32zero(ysize, C);
 	mp32setw(ysize, D, 1);
 
-#ifdef	NOTYET
 	for (k = 0; mp32even(ysize, u) && mp32even(ysize, v); k++) {
 		mp32divtwo(ysize, u);
 		mp32divtwo(ysize, v);
@@ -34,19 +33,18 @@ static int Zmp32binv_w(const mp32barrett* b, uint32 xsize, const uint32* xdata,
 
 	if (mp32even(ysize, u))
 		(void) mp32add(ysize, u, v);
-#endif
 
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       u: "), mp32println(stderr, ysize, u);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       v: "), mp32println(stderr, ysize, v);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       A: "), mp32println(stderr, ysize, A);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       B: "), mp32println(stderr, ysize, B);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       C: "), mp32println(stderr, ysize, C);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       D: "), mp32println(stderr, ysize, D);
 
 	ubits = vbits = 32 * (ysize);
@@ -61,7 +59,7 @@ fprintf(stderr, "       D: "), mp32println(stderr, ysize, D);
 			}
 			mp32sdivtwo(ysize, C);
 			mp32sdivtwo(ysize, D);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "-->>   v: "), mp32println(stderr, ysize, v);
 		}
 
@@ -69,7 +67,7 @@ fprintf(stderr, "-->>   v: "), mp32println(stderr, ysize, v);
 			uint32* swapu;
 			uint32  swapi;
 
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "--> (swap u <-> v)\n");
 			swapu = u;	u = v;		v = swapu;
 			swapi = ubits;	ubits = vbits;	vbits = swapi;
@@ -78,37 +76,40 @@ fprintf(stderr, "--> (swap u <-> v)\n");
 		}
 
 		if (!((u[ysize-1] + v[ysize-1]) & 0x3)) {
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "--> (even parity)\n");
 			mp32add(ysize, v, u);
 			mp32add(ysize, C, A);
 			mp32add(ysize, D, B);
 		} else {
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "--> (odd parity)\n");
 			mp32sub(ysize, v, u);
 			mp32sub(ysize, C, A);
 			mp32sub(ysize, D, B);
 		}
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       v: "), mp32println(stderr, ysize, v);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       C: "), mp32println(stderr, ysize, C);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       D: "), mp32println(stderr, ysize, D);
 		vbits++;
 	} while (mp32nz(ysize, v));
 
-	if (result) {
 #ifdef	NOTYET
+	if (!mp32isone(ysize, u))
+		return 0;
+#endif
+
+	if (result) {
+		mp32setx(b->size, result, ysize, A);
 		/*@-usedef@*/
 		if (*A & 0x80000000)
-			(void) mp32neg(ysize, A);
+			(void) mp32neg(b->size, result);
 		/*@=usedef@*/
 		while (--k > 0)
-			mp32add(ysize, A, A);
-#endif
-		mp32setx(b->size, result, ysize, A);
+			mp32add(b->size, result, result);
 	}
 
 fprintf(stderr, "=== EXIT: "), mp32println(stderr, b->size, result);
@@ -147,55 +148,55 @@ static int Ymp32binv_w(const mp32barrett* b, uint32 xsize, const uint32* xdata,
 		mp32divtwo(ysize, v);
 	}
 
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       u: "), mp32println(stderr, ysize, u);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       v: "), mp32println(stderr, ysize, v);
 
 	/* Y2. Initialize. */
 	mp32setw(ysize, u1, 1);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      u1: "), mp32println(stderr, ysize, u1);
 	mp32zero(ysize, u2);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      u2: "), mp32println(stderr, ysize, u2);
 	mp32setx(ysize, u3, ysize, u);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      u3: "), mp32println(stderr, ysize, u3);
 
 	mp32setx(ysize, v1, ysize, v);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      v1: "), mp32println(stderr, ysize, v1);
 	mp32setw(ysize, v2, 1);
 	(void) mp32sub(ysize, v2, u);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      v2: "), mp32println(stderr, ysize, v2);
 	mp32setx(ysize, v3, ysize, v);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      v3: "), mp32println(stderr, ysize, v3);
 
 	if (mp32odd(ysize, u)) {
 		mp32zero(ysize, t1);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      t1: "), mp32println(stderr, ysize, t1);
 		mp32zero(ysize, t2);
 		mp32subw(ysize, t2, 1);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      t2: "), mp32println(stderr, ysize, t2);
 		mp32zero(ysize, t3);
 		mp32sub(ysize, t3, v);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      t3: "), mp32println(stderr, ysize, t3);
 		goto Y4;
 	} else {
 		mp32setw(ysize, t1, 1);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      t1: "), mp32println(stderr, ysize, t1);
 		mp32zero(ysize, t2);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      t2: "), mp32println(stderr, ysize, t2);
 		mp32setx(ysize, t3, ysize, u);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      t3: "), mp32println(stderr, ysize, t3);
 	}
 
@@ -209,38 +210,38 @@ fprintf(stderr, "      t3: "), mp32println(stderr, ysize, t3);
 		mp32sdivtwo(ysize, t2);
 		mp32sdivtwo(ysize, t3);
 Y4:
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "   Y4 t3: "), mp32println(stderr, ysize, t3);
 	    } while (mp32even(ysize, t3));
 
 	    /* Y5. Reset max(u3,v3). */
 	    if (!(*t3 & 0x80000000)) {
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "--> Y5 (t3 > 0)\n");
 		mp32setx(ysize, u1, ysize, t1);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      u1: "), mp32println(stderr, ysize, u1);
 		mp32setx(ysize, u2, ysize, t2);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      u2: "), mp32println(stderr, ysize, u2);
 		mp32setx(ysize, u3, ysize, t3);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      u3: "), mp32println(stderr, ysize, u3);
 	    } else {
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "--> Y5 (t3 <= 0)\n");
 		mp32setx(ysize, v1, ysize, v);
 		mp32sub(ysize, v1, t1);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      v1: "), mp32println(stderr, ysize, v1);
 		mp32setx(ysize, v2, ysize, u);
 		mp32neg(ysize, v2);
 		mp32sub(ysize, v2, t2);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      v2: "), mp32println(stderr, ysize, v2);
 		mp32zero(ysize, v3);
 		mp32sub(ysize, v3, t3);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      v3: "), mp32println(stderr, ysize, v3);
 	    }
 
@@ -257,15 +258,18 @@ fprintf(stderr, "      v3: "), mp32println(stderr, ysize, v3);
 		mp32sub(ysize, t2, u);
 	    }
 
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "-->Y6 t1: "), mp32println(stderr, ysize, t1);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      t2: "), mp32println(stderr, ysize, t2);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "      t3: "), mp32println(stderr, ysize, t3);
 
 	} while (mp32nz(ysize, t3));
 
+	if (!(mp32isone(ysize, u3) && mp32isone(ysize, v3)))
+		return 0;
+
 	if (result) {
 		while (--k > 0)
 			mp32add(ysize, u1, u1);
@@ -316,147 +320,89 @@ static int Xmp32binv_w(const mp32barrett* b, uint32 xsize, const uint32* xdata,
 	mp32zero(ysize, C);
 	mp32setw(ysize, D, 1);
 
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       u: "), mp32println(stderr, ysize, u);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       v: "), mp32println(stderr, ysize, v);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       A: "), mp32println(stderr, ysize, A);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       B: "), mp32println(stderr, ysize, B);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       C: "), mp32println(stderr, ysize, C);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       D: "), mp32println(stderr, ysize, D);
 
-#ifdef	NOTNOW
-	if (mp32odd(b->size, b->modl) && mp32even(xsize, xdata))
-	{
-		/* use simplified binary extended gcd algorithm */
-
-		while (1)
+	do {
+		while (mp32even(ysize, u))
 		{
-			while (mp32even(ysize, u))
-			{
-				mp32divtwo(ysize, u);
+			mp32divtwo(ysize, u);
 
-				if (mp32odd(ysize, B))
-					(void) mp32subx(ysize, B, b->size, b->modl);
-
-				mp32sdivtwo(ysize, B);
-			}
-			while (mp32even(ysize, v))
+			if (mp32odd(ysize, A) || mp32odd(ysize, B))
 			{
-				mp32divtwo(ysize, v);
-
-				if (mp32odd(ysize, D))
-					(void) mp32subx(ysize, D, b->size, b->modl);
-
-				mp32sdivtwo(ysize, D);
-			}
-			if (mp32ge(ysize, u, v))
-			{
-				(void) mp32sub(ysize, u, v);
-				(void) mp32sub(ysize, B, D);
-			}
-			else
-			{
-				(void) mp32sub(ysize, v, u);
-				(void) mp32sub(ysize, D, B);
+				(void) mp32addx(ysize, A, xsize, xdata);
+				(void) mp32subx(ysize, B, b->size, b->modl);
 			}
 
-			if (mp32z(ysize, u))
-			{
-				if (mp32isone(ysize, v))
-				{
-					if (result)
-					{
-						mp32setx(size, result, ysize, D);
-						/*@-usedef@*/
-						if (*D & 0x80000000)
-							(void) mp32add(b->size, result, b->modl);
-						/*@=usedef@*/
-					}
-					return 1;
-				}
-				return 0;
-			}
+			mp32sdivtwo(ysize, A);
+			mp32sdivtwo(ysize, B);
 		}
-	}
-	else
-#endif
-	{
-		/* use full binary extended gcd algorithm */
-
-		while (1)
+		while (mp32even(ysize, v))
 		{
-			while (mp32even(ysize, u))
-			{
-				mp32divtwo(ysize, u);
+			mp32divtwo(ysize, v);
 
-				if (mp32odd(ysize, A) || mp32odd(ysize, B))
-				{
-					(void) mp32addx(ysize, A, xsize, xdata);
-					(void) mp32subx(ysize, B, b->size, b->modl);
-				}
-
-				mp32sdivtwo(ysize, A);
-				mp32sdivtwo(ysize, B);
-			}
-			while (mp32even(ysize, v))
+			if (mp32odd(ysize, C) || mp32odd(ysize, D))
 			{
-				mp32divtwo(ysize, v);
-
-				if (mp32odd(ysize, C) || mp32odd(ysize, D))
-				{
-					(void) mp32addx(ysize, C, xsize, xdata);
-					(void) mp32subx(ysize, D, b->size, b->modl);
-				}
-
-				mp32sdivtwo(ysize, C);
-				mp32sdivtwo(ysize, D);
+				(void) mp32addx(ysize, C, xsize, xdata);
+				(void) mp32subx(ysize, D, b->size, b->modl);
 			}
-			if (mp32ge(ysize, u, v))
-			{
-if (_debug)
+
+			mp32sdivtwo(ysize, C);
+			mp32sdivtwo(ysize, D);
+		}
+		if (mp32ge(ysize, u, v))
+		{
+if (_debug < 0)
 fprintf(stderr, "--> 5 (u >= v)\n");
-				(void) mp32sub(ysize, u, v);
-				(void) mp32sub(ysize, A, C);
-				(void) mp32sub(ysize, B, D);
-if (_debug)
+			(void) mp32sub(ysize, u, v);
+			(void) mp32sub(ysize, A, C);
+			(void) mp32sub(ysize, B, D);
+if (_debug < 0)
 fprintf(stderr, "       u: "), mp32println(stderr, ysize, u);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       A: "), mp32println(stderr, ysize, A);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       B: "), mp32println(stderr, ysize, B);
-			}
-			else
-			{
-if (_debug)
+		}
+		else
+		{
+if (_debug < 0)
 fprintf(stderr, "--> 5 (u < v)\n");
-				(void) mp32sub(ysize, v, u);
-				(void) mp32sub(ysize, C, A);
-				(void) mp32sub(ysize, D, B);
-if (_debug)
+			(void) mp32sub(ysize, v, u);
+			(void) mp32sub(ysize, C, A);
+			(void) mp32sub(ysize, D, B);
+if (_debug < 0)
 fprintf(stderr, "       v: "), mp32println(stderr, ysize, v);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       C: "), mp32println(stderr, ysize, C);
-if (_debug)
+if (_debug < 0)
 fprintf(stderr, "       D: "), mp32println(stderr, ysize, D);
-			}
+		}
+
+	} while (mp32nz(ysize, u));
+
+	if (!mp32isone(ysize, v))
+		return 0;
+
+	if (result)
+	{
+		mp32setx(b->size, result, ysize, D);
+		/*@-usedef@*/
+		if (*D & 0x80000000)
+			(void) mp32add(b->size, result, b->modl);
+		/*@=usedef@*/
+	}
 
-			if (mp32z(ysize, u))
-			{
-				if (mp32isone(ysize, v))
-				{
-					if (result)
-					{
-						mp32setx(b->size, result, ysize, D);
-						/*@-usedef@*/
-						if (*D & 0x80000000)
-							(void) mp32add(b->size, result, b->modl);
-						/*@=usedef@*/
-					}
 fprintf(stderr, "=== EXIT: "), mp32println(stderr, b->size, result);
 fprintf(stderr, "       u: "), mp32println(stderr, ysize, u);
 fprintf(stderr, "       v: "), mp32println(stderr, ysize, v);
@@ -464,30 +410,49 @@ fprintf(stderr, "       A: "), mp32println(stderr, ysize, A);
 fprintf(stderr, "       B: "), mp32println(stderr, ysize, B);
 fprintf(stderr, "       C: "), mp32println(stderr, ysize, C);
 fprintf(stderr, "       D: "), mp32println(stderr, ysize, D);
-					return 1;
-				}
-				return 0;
-			}
-		}
-	}
+	return 1;
 }
 
 static const char * dsa_q	= "a1b35510319a59825c721e73e41d687ffe351bc9";
 static const char * dsa_s[]	= {
-    "0a73e678141aea7b4e5195afb7db3e9ec00f9f85",	/* time-1.7-14.i386.rpm */
+    "22e917d8a47462c09748e00aebbab5fd93793495",	/* samba-2.2.1a-4.i386.rpm */
+    "0476b30eb86899c6785fad4f7a62e43d59481273",	/* gtkhtml-devel-0.9.2-9.i386.rpm */
+    "8adbca132a0e6a2d2ee5bb2cd837b350c9f8db42",	/* lha-1.00-17.i386.rpm */
+
+    "026efa7a5a60d29921ec93f503b5c483d131d8c4",	/* jed-0.99.14-2.i386.rpm */
+    "2e4ec3c986b5a1f8f77b0b9f911d4e1b0ed8d869",	/* ttfonts-zh_TW-2.11-5.noarch.rpm */
+
     "259e4859e65c2528d3c35eaf2717d8963c834e94",	/* libxml2-2.4.2-1.i386.rpm */
+    "45462b3534c2ff7a13f232a4e6e4460c61b2e232",	/* slang-1.4.4-4.i386.rpm */
+    "0a73e678141aea7b4e5195afb7db3e9ec00f9f85",	/* time-1.7-14.i386.rpm */
     NULL
 };
 
 static const char * dsa_w_good[]= {
-    "2659140a40cb05e85c536a299327addb0a762b8a",	/* time-1.7-14.i386.rpm */
+    "8b2eeda5fd34067c248bc3262e28f5668e64500b",	/* samba-2.2.1a-4.i386.rpm */
+    "98f6a05c5cc17c2e48faad178d2c21c0bcca694b",	/* gtkhtml-devel-0.9.2-9.i386.rpm */
+    "8ec91350f3237ee249ea009143f692d4cc2f8d2e",	/* lha-1.00-17.i386.rpm */
+
+    "7db9e81c6f60fdd29243f67b70af7d1d14c9c703",	/* jed-0.99.14-2.i386.rpm */
+    "6bdc316aef981e45c47dabab904a31747d349eec",	/* ttfonts-zh_TW-2.11-5.noarch.rpm */
+
     "6d1eaa6c78ad945a1de7bc369f7992e9df3735d9",	/* libxml2-2.4.2-1.i386.rpm */
+    "79dc6adee7817e7dc248cfeb4b358e933af6de01",	/* slang-1.4.4-4.i386.rpm */
+    "2659140a40cb05e85c536a299327addb0a762b8a",	/* time-1.7-14.i386.rpm */
     NULL
 };
 
 static const char * dsa_w_bad[]	= {
-    "2659140a40cb05e85c536a299327addb0a762b8a",	/* time-1.7-14.i386.rpm */
+    "e97b9895cb99acf9c819a4b24a0b8ce6902f3442",	/* samba-2.2.1a-4.i386.rpm */
+    "f7434b4c2b2722abec888ea3a90eb940be954d82",	/* gtkhtml-devel-0.9.2-9.i386.rpm */
+    "ed15be40c189255fed77e21d5fd92a54cdfa7165",	/* lha-1.00-17.i386.rpm */
+
+    "dc06930c3dc6a45035d1d8078c92149d1694ab3a",	/* jed-0.99.14-2.i386.rpm */
+    "ca28dc5abdfdc4c3680b8d37ac2cc8f47eff8323",	/* ttfonts-zh_TW-2.11-5.noarch.rpm */
+
     "cb6b555c47133ad7c1759dc2bb5c2a69e1021a10",	/* libxml2-2.4.2-1.i386.rpm */
+    "d82915ceb5e724fb65d6b177671826133cc1c238",	/* slang-1.4.4-4.i386.rpm */
+    "2659140a40cb05e85c536a299327addb0a762b8a",	/* time-1.7-14.i386.rpm */
     NULL
 };
 
@@ -521,26 +486,25 @@ main(int argc, const char * argv[])
     qtemp = malloc((13*qsize+13) * sizeof(*qtemp));
     qwksp = qtemp+2*qsize;
 
-    for (i = 0; i < 1; i++) {
-fprintf(stderr, "====================================\n");
+    for (i = 0; i < 9; i++) {
+	if (dsa_s[i] == NULL) break;
+fprintf(stderr, "================================================== %d\n", i);
 	fprintf(stderr, "       s: %s\n", dsa_s[i]);
 	mp32nzero(&s); mp32nsethex(&s, dsa_s[i]);
 
-fprintf(stderr, "------------------------------------\n");
+fprintf(stderr, "-------------------------------------------------- %d\n", i);
 	rc = Xmp32binv_w(&q, s.size, s.data, qtemp, qwksp);
 	fprintf(stderr, "beecrypt: "); mp32println(stderr, qsize, qtemp);
 
-#if 0
-fprintf(stderr, "------------------------------------\n");
+fprintf(stderr, "-------------------------------------------------- %d\n", i);
 	rc = Ymp32binv_w(&q, s.size, s.data, qtemp, qwksp);
 	fprintf(stderr, "   Knuth: "); mp32println(stderr, qsize, qtemp);
-#endif
 
-fprintf(stderr, "------------------------------------\n");
+fprintf(stderr, "-------------------------------------------------- %d\n", i);
 	rc = Zmp32binv_w(&q, s.size, s.data, qtemp, qwksp);
 	fprintf(stderr, "   Brent: "); mp32println(stderr, qsize, qtemp);
 
-fprintf(stderr, "------------------------------------\n");
+fprintf(stderr, "-------------------------------------------------- %d\n", i);
 	fprintf(stderr, "       q: %s\n", dsa_q);
 	fprintf(stderr, "       s: %s\n", dsa_s[i]);
 	fprintf(stderr, "    GOOD: %s\n", dsa_w_good[i]);