author Felix Dörre Wed, 13 Dec 2017 19:34:15 +0000 (20:34 +0100) committer Lucas Werkmeister Mon, 18 Dec 2017 23:02:22 +0000 (00:02 +0100)
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

index 16abb06..d8bb2eb 100644 (file)
@@ -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