Re: Prime generation

2014-05-28 Thread Ben Laurie
On 28 May 2014 01:47, mancha manc...@zoho.com wrote: Fouque and Tibouchi [3] offer the differing view that it's preferable to minimize bias and generate primes that are almost uniform even if it is not immediately clear how such biases can help an adversary. They suggest a few algorithms that

Re: Prime generation

2014-05-28 Thread Joseph Birr-Pixton
On 27 May 2014 11:11, Ben Laurie b...@links.org wrote: On 27 May 2014 09:16, Joseph Birr-Pixton jpix...@gmail.com wrote: To restate: Callers of RAND_pseudo_bytes are either unreliable, or equivalent to RAND_bytes. Do not use it. Have I missed something? What are you referring to here?

Re: Prime generation

2014-05-28 Thread David Jacobson
On 5/27/14 12:56 AM, Stephan Mueller wrote: Am Dienstag, 27. Mai 2014, 17:45:48 schrieb Peter Waltenberg: Hi Peter, Not quite correct, the prime rands shouldn't come from a DRBG, they should come from an NRBG (NIST terminology). There's a considerable difference between the performance of an

Re: Prime generation

2014-05-27 Thread Otto Moerbeek
On Tue, May 27, 2014 at 05:23:45AM +, mancha wrote: On Mon, May 26, 2014 at 09:01:53PM +, mancha wrote: On Mon, May 26, 2014 at 08:49:03PM +, Viktor Dukhovni wrote: On Mon, May 26, 2014 at 08:20:43PM +, mancha wrote: For our purposes, the operative question is

Re: Prime generation

2014-05-27 Thread Otto Moerbeek
On Tue, May 27, 2014 at 08:23:29AM +0200, Otto Moerbeek wrote: On Tue, May 27, 2014 at 05:23:45AM +, mancha wrote: On Mon, May 26, 2014 at 09:01:53PM +, mancha wrote: On Mon, May 26, 2014 at 08:49:03PM +, Viktor Dukhovni wrote: On Mon, May 26, 2014 at 08:20:43PM +,

Re: Prime generation

2014-05-27 Thread David Jacobson
On 5/26/14 2:01 PM, mancha wrote: On Mon, May 26, 2014 at 08:49:03PM +, Viktor Dukhovni wrote: On Mon, May 26, 2014 at 08:20:43PM +, mancha wrote: For our purposes, the operative question is whether the distribution bias created can be leveraged in any way to attack factoring (RSA) or

Re: Prime generation

2014-05-27 Thread Peter Waltenberg
-owner-openssl-...@openssl.org wrote: - To: openssl-dev@openssl.orgFrom: David Jacobson <dmjacob...@sbcglobal.net> Sent by: owner-openssl-...@openssl.orgDate: 05/27/2014 05:16PM Subject: Re: Prime generation On 5/26/14 2:01 PM, mancha wrote: On Mon, May 26, 2014 at 08:49:03PM +, Viktor Du

Re: Prime generation

2014-05-27 Thread Stephan Mueller
Am Dienstag, 27. Mai 2014, 17:45:48 schrieb Peter Waltenberg: Hi Peter, Not quite correct, the prime rands shouldn't come from a DRBG, they should come from an NRBG (NIST terminology). There's a considerable difference between the performance of an entropy source and a DRBG. Not sure where you

Re: Prime generation

2014-05-27 Thread Joseph Birr-Pixton
On 27 May 2014 08:45, Peter Waltenberg pwal...@au1.ibm.com wrote: ... I did change the RNG sources for some of the OpenSSL code in our hacked version to help with the performance problems using the wrong source causes, for example RSA blinding data can safely come from a DRBG

Re: Prime generation

2014-05-27 Thread Peter Waltenberg
: Joseph Birr-Pixton <jpix...@gmail.com> Sent by: owner-openssl-...@openssl.orgDate: 05/27/2014 07:14PM Subject: Re: Prime generation On 27 May 2014 08:45, Peter Waltenberg pwal...@au1.ibm.com wrote: ... I did change the RNG sources for some of the OpenSSL code in our hacked version t

Re: Prime generation

2014-05-27 Thread Ben Laurie
On 27 May 2014 09:16, Joseph Birr-Pixton jpix...@gmail.com wrote: On 27 May 2014 08:45, Peter Waltenberg pwal...@au1.ibm.com wrote: ... I did change the RNG sources for some of the OpenSSL code in our hacked version to help with the performance problems using the wrong source causes, for

Re: Prime generation

2014-05-27 Thread Annie
Am 27.05.2014 12:04, schrieb Ben Laurie: On 26 May 2014 21:15, Annie a.you...@informatik.hu-berlin.de wrote: Am 26.05.2014 21:23, schrieb Ben Laurie: On 26 May 2014 19:52, Viktor Dukhovni openssl-us...@dukhovni.org wrote: On Mon, May 26, 2014 at 07:24:54PM +0100, Ben Laurie wrote: Finally,

Re: Prime generation

2014-05-27 Thread mancha
On Tue, May 27, 2014 at 08:23:29AM +0200, Otto Moerbeek wrote: On Tue, May 27, 2014 at 05:23:45AM +, mancha wrote: On Mon, May 26, 2014 at 09:01:53PM +, mancha wrote: On Mon, May 26, 2014 at 08:49:03PM +, Viktor Dukhovni wrote: On Mon, May 26, 2014 at 08:20:43PM +,

Re: Prime generation

2014-05-27 Thread Geoffrey Thorpe
I haven't read through the references but am grateful for them. Indeed, I haven't actually followed this mail-thread in detail but I was struck by a strange sense of déjà-vu. There was a similar discussion over 10 years ago; http://marc.info/?t=10705874291r=1w=2 :-) Talk about feeling old...

Re: Prime generation

2014-05-26 Thread Viktor Dukhovni
On Mon, May 26, 2014 at 07:24:54PM +0100, Ben Laurie wrote: Finally, all of them have a bias: they're much more likely to pick a prime with a long run of non-primes before it than one that hasn't (in the case of the DH ones, the condition is slightly more subtle, depending on parameters, but

Re: Prime generation

2014-05-26 Thread Viktor Dukhovni
On Mon, May 26, 2014 at 08:23:07PM +0100, Ben Laurie wrote: Where do you see the bias? They all work by picking a random number and then stepping upwards from that number until a probable prime is found. Clearly, that is more likely to find primes with a long run of non-primes before than

Re: Prime generation

2014-05-26 Thread mancha
On Mon, May 26, 2014 at 08:23:07PM +0100, Ben Laurie wrote: On 26 May 2014 19:52, Viktor Dukhovni openssl-us...@dukhovni.org wrote: On Mon, May 26, 2014 at 07:24:54PM +0100, Ben Laurie wrote: Finally, all of them have a bias: they're much more likely to pick a prime with a long run of

Re: Prime generation

2014-05-26 Thread Viktor Dukhovni
On Mon, May 26, 2014 at 08:20:43PM +, mancha wrote: For our purposes, the operative question is whether the distribution bias created can be leveraged in any way to attack factoring (RSA) or dlog (DH). The maximum gap between primes of size $n$ is conjectured to be around $log(n)^2$. If

Re: Prime generation

2014-05-26 Thread mancha
On Mon, May 26, 2014 at 08:49:03PM +, Viktor Dukhovni wrote: On Mon, May 26, 2014 at 08:20:43PM +, mancha wrote: For our purposes, the operative question is whether the distribution bias created can be leveraged in any way to attack factoring (RSA) or dlog (DH). The maximum gap

Re: Prime generation

2014-05-26 Thread mancha
On Mon, May 26, 2014 at 09:01:53PM +, mancha wrote: On Mon, May 26, 2014 at 08:49:03PM +, Viktor Dukhovni wrote: On Mon, May 26, 2014 at 08:20:43PM +, mancha wrote: For our purposes, the operative question is whether the distribution bias created can be leveraged in any way