From: Felix Dörre <felix@dogcraft.de>
Date: Wed, 13 Dec 2017 19:34:15 +0000 (+0100)
Subject: fix: the "generateBrokenKeypair" can sometimes hang indefinitely
X-Git-Url: https://code.wpia.club/?p=gigi.git;a=commitdiff_plain;h=056e2d36653e0dfdfa520651c1aa4e70df82ea1a

fix: the "generateBrokenKeypair" can sometimes hang indefinitely

The value of "p" can be too small so no value for "q" can be found.

The problem can be resolved by re-choosing both p and q when the result
is too small. The old "swap and only re-generate the smaller prime" does
not work anymore as p and q are not generated with equal length.

Change-Id: I9fc533ac6ece769b15deeb4186385f2a72188e72
---

diff --git a/tests/club/wpia/gigi/testUtils/ConfiguredTest.java b/tests/club/wpia/gigi/testUtils/ConfiguredTest.java
index 16abb06c..d8bb2ebf 100644
--- a/tests/club/wpia/gigi/testUtils/ConfiguredTest.java
+++ b/tests/club/wpia/gigi/testUtils/ConfiguredTest.java
@@ -210,6 +210,16 @@ public abstract class ConfiguredTest {
             int keySize = 4096;
             long r_lv = 7331;
 
+            // The generated numbers p q and r fall into the
+            // following ranges:
+            // - p: 2^(lp-1) < p < 2^lp
+            // - q: 2^(lq-1) < q < 2^lq
+            // - r: 2^12 < r < 2^13
+            // Thus the generated number has at least lp+lq+11 bit and
+            // can have at most lp+lq+13 bit.
+            // Thus for random selection of p and q the algorithm will
+            // at some point select a number of length n=n/2+lr+(n-n/2-lr)=>n
+            // bit.
             int lp = (keySize + 1) >> 1;
             int lr = BigInteger.valueOf(r_lv).bitLength();
             int lq = keySize - lp - lr;
@@ -221,24 +231,17 @@ public abstract class ConfiguredTest {
                 // generate two random primes of size lp/lq
                 BigInteger p, q, r, n;
 
-                p = BigInteger.probablePrime(lp, random);
                 r = BigInteger.valueOf(r_lv);
                 do {
+                    p = BigInteger.probablePrime(lp, random);
                     q = BigInteger.probablePrime(lq, random);
 
-                    // convention is for p > q > r
-                    if (p.compareTo(q) < 0) {
-                        BigInteger tmp = p;
-                        p = q;
-                        q = tmp;
-                    }
-
                     // modulus n = p * q * r
                     n = p.multiply(q).multiply(r);
 
                     // even with correctly sized p, q and r, there is a chance
-                    // that n will be one bit short. re-generate the smaller
-                    // prime if so.
+                    // that n will be one bit short. re-generate the
+                    // primes if so.
                 } while (n.bitLength() < keySize);
 
                 // phi = (p - 1) * (q - 1) * (r - 1) must be relative prime to e