Subject: [Cfrg] Random primes

From: Ben Laurie <[email-masked]>
Date: Mon, 2 Jun 2014 20:26:17 +0100

On 2 June 2014 18:13, Paterson, Kenny <[email-masked]> wrote:
> Specifically, GCHQ is
> funding a PhD studentship under my supervision from 2013 to 2017 on the
> topic of randomness in cryptography

That brings me nicely to a question I've recently been musing about:
random prime generation.

My son and I were recently playing with a way to improve the speed of
OpenSSL's random primes. Happy to discuss how, but that's beside the
point. While we were doing this, we realised that OpenSSL generates
biased primes - the core algorithm is "pick a random number, see if it
or (it - 1)/2 is divisible by any small primes, if it is, add 2 and
try again, once you get one that isn't, do Miller-Rabin (kinda) and if
that fails, restart".

It has various ideas on what primes might be used for - and clearly
the (it - 1)/2 thing is a good idea if you're trying to generate a
safe prime, but it _always_ does that, for no apparent reason.

Also, of course, this algorithm favours primes that have long runs of
non-primes before them.

So ... OpenSSL generates primes with a bias.

Does this matter?

What kind of primes should be used when?

I've found a fair amount of contradictory opinion on this so far.
Reasoned judgement would be nice. OpenSSL patches even nicer (we
already have one in to experiment with unbiased primes, btw).

---

From: Ilya Mironov <[email-masked]>
Date: Mon, 2 Jun 2014 20:43:44 +0000

For the record: OpenSSL behavior and analysis of the bias induced by its method of sampling prime numbers was documented in 2012 in the following blog post from May 2012: http://windowsontheory.org/2012/05/17/factoring-rsa-moduli-part-ii/ 

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Ben Laurie
Sent: Monday, June 02, 2014 12:26 PM
To: Paterson, Kenny
Cc: [email-masked]
Subject: [Cfrg] Random primes

On 2 June 2014 18:13, Paterson, Kenny <[email-masked]> wrote:
> Specifically, GCHQ is
> funding a PhD studentship under my supervision from 2013 to 2017 on 
> the topic of randomness in cryptography

My son and I were recently playing with a way to improve the speed of OpenSSL's random primes. Happy to discuss how, but that's beside the point. While we were doing this, we realised that OpenSSL generates biased primes - the core algorithm is "pick a random number, see if it or (it - 1)/2 is divisible by any small primes, if it is, add 2 and try again, once you get one that isn't, do Miller-Rabin (kinda) and if that fails, restart".

It has various ideas on what primes might be used for - and clearly the (it - 1)/2 thing is a good idea if you're trying to generate a safe prime, but it _always_ does that, for no apparent reason.

Also, of course, this algorithm favours primes that have long runs of non-primes before them.

Does this matter?

I've found a fair amount of contradictory opinion on this so far.
Reasoned judgement would be nice. OpenSSL patches even nicer (we already have one in to experiment with unbiased primes, btw).

_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg