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
int keySize = 4096;
long r_lv = 7331;
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;
int lp = (keySize + 1) >> 1;
int lr = BigInteger.valueOf(r_lv).bitLength();
int lq = keySize - lp - lr;
// generate two random primes of size lp/lq
BigInteger p, q, r, n;
// generate two random primes of size lp/lq
BigInteger p, q, r, n;
- p = BigInteger.probablePrime(lp, random);
r = BigInteger.valueOf(r_lv);
do {
r = BigInteger.valueOf(r_lv);
do {
+ p = BigInteger.probablePrime(lp, random);
q = BigInteger.probablePrime(lq, 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
// 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
} while (n.bitLength() < keySize);
// phi = (p - 1) * (q - 1) * (r - 1) must be relative prime to e