DHKeyGenerator comment nit and discussion on minimum random key size

[Bernd Eckenfels]

Hello,

to answer myself, it can be done with setBit. I have discussed it here:

http://crypto.stackexchange.com/questions/39498/generating-dh-key-with-minimum-size

an optimized loop would then look like:

        do {
            // generate random x between 2^(lSize-1) and (2^lSize)-1
            x = new BigInteger(lSize - 1, random);
            x = x.setBit(lSize);
        } while (x.compareTo(pMinus1) >= 0);

BTW: the sentence "Repeat if either of the followings does not hold"
is wrong, this is not mandated in PKCS3. It is different if l is
specified or not and it does not require a loop of the condition can be
satisifed in another way.


Gruss
Bernd


Am Sun, 21 Aug 2016 14:51:05 +0200
schrieb Bernd Eckenfels <ecki at zusammenkunft.net>:

> Hallo,
> 
> I have noticed in DHKeyGenerator, that there is a comment which is not
> totally correct:
> 
> http://hg.openjdk.java.net/jdk9/jdk9/jdk/file/496a116876a3/src/java.base/share/classes/com/sun/crypto/provider/DHKeyPairGenerator.java#l192
> 
> 192            // generate random x up to 2^lSize bits long
> 193            x = new BigInteger(lSize, random);
> 
> I think the comment should read 
> 
>   // generate random x up to lsize bits long
> 
> however, the comment adds more value if it refers to the BigInteger
> spec:
> 
>    // generate random 0 <= x <= (2^lsize)-1
> 
> 
> While finding this, I also noticed that the code has changed in JDK8.
> The old form used the simple rule of applied crypto handbook:
> 
> 
> 170        // Handbook of Applied Cryptography:  Menezes, et.al.
> 171        // Repeat if the following does not hold:
> 172        //     1 <= x <= p-2
> 173        //
> 174        do {
> 175            // generate random x up to 2^lSize bits long
> 176            x = new BigInteger(lSize, random);
> 177        } while ((x.compareTo(BigInteger.ONE) < 0) ||
> 178            ((x.compareTo(pMinus2) > 0)));
> 
> (Which I always wondered if it is not to simple). This code uses p-2
> as the upper bound.
> 
> 
> The current code specifies it uses PKCS rules where 
> 
> 186        // PKCS#3 section 7.1 "Private-value generation"
> 187        // Repeat if either of the followings does not hold:
> 188        //     0 < x < p-1
> 189        //     2^(lSize-1) <= x < 2^(lSize)
> 190        //
> 191        do {
> 192            // generate random x up to 2^lSize bits long
> 193            x = new BigInteger(lSize, random);
> 194        } while ((x.compareTo(BigInteger.ONE) < 0) ||
> 195            ((x.compareTo(pMinus2) > 0)) || (x.bitLength() !=
> lSize));
> 
> IMHO It should either mention that the check is equivalent to x <= p-2
> or use the x.compareTo(pMinus1) >= 0 instead.
> 
> The lower bound 2^(lSize-1) <= x (represented as x.bitLength) is
> always stricter than 0<x, therefore I guess this check can be removed
> in the while condition.
> 
> this results in:
> 
>     while ((x.bitLength() != lSize) || (x.compareTo(pMinus1) >= 0))
> 
> 
> BTW1: would it be a good addition to BigInteger or an helper to
> generate a random number with a minimum number of bitlength as well?
> This way situations where a minimum bit length is mandated it can be
> used instead of an additional loop.
> 
> new BigInteger(minLen, maxLen, random)
> 
> which ensures the higest bit is always set, consequently returning
> random numbers between (2^minLen-1) and (2^maxLen)-1.
> 
> BTW2: I was not aware that the key genration in JDK8 changed
> http://hg.openjdk.java.net/jdk8/jdk8/jdk/rev/6e2a5637b286 - that
> change only talks about interop. MAybe a documentation that key
> generation was changed can be backfilled? (instinctively one can say
> the key generation is stricter, on the other hand it reduces the
> keyspace by one bit).
> 
> Gruss
> Bernd