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, 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 its there nevertheless). Is this wise?
>>>>
>>>> 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
>>> primes with a short run.
>>
>> Ben, this is not the whole story. It is stepping upwards, right, but it
>> jumps also over primes p with small factors of p-1.
>
> That's what I meant by "probable safe primes".
>
>> So you should say that it is more likely to find primes with a long run
>> consisting of non-primes and primes p with small factors of (p-1)/2
>> before than primes with a short run of these numbers.
>> Look for the prime gap of length 21 between 1129 and 1151. If a search
>> arrives at 1129 it jumps over, because 564 is divisible by 4, and the
>> search even doesn't stop at 1151, due to the factor 5 of 575.
>>
>> Regards,
>> Annie.
>>
>> See lines 390-401 in crypto/bn/bn_prime.c
>>
>> loop: for (i=1; i<NUMPRIMES; i++)
>> {
>> /* check that rnd is not a prime and also
>> * that gcd(rnd-1,primes) == 1 (except for 2) */
>> ==> if (((mods[i]+delta)%primes[i]) <= 1)
>
> Exactly. I am not sure why it does this (obviously sometimes it is a
> useful property, but surely not always?).
This is in sources from the very beginning of OpenSSL, I guess that it
comes from Phil Zimmermann's search routine in PGP. The main reason for
doing this, is probably the fact that p-1 must be coprime with exponent
e. Choosing primes p without small factors in p-1 will assure that there
will be in many cases no common divisor of p-1 and e.
As the prime search is costly it is easier to drop candidates mit small
factors in p-1 than to repeat the whole search.
Regards,
Ann.
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-dev@openssl.org
Automated List Manager majord...@openssl.org
