Thursday, December 11, 2014

[gpjvptsi] Random primes via next prime

To generate a random N-bit prime number, first generate one random N bit number X using a random bit generator, e.g., a stream cipher.  Then search sequentially (X, X+1, X+2,...) for the first prime number after that number.  This method is used in the generation of Brainpool ECC curves.

However, this method is flawed because primes following large prime gaps become preferentially selected.  Such numbers might have some special cryptographically weak properties that a random prime probably will not.

The correct way to do it to keep sampling a completely new N bit number from the stream cipher until a prime is found.  Or, as an optimization, sample N-2 bits, then append a 1 as the LSB (forcing it to be odd) and a 1 as the MSB (avoiding leading zero bits).

No comments :