Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Tue, 20 Oct 2015 20:26:55 +0300
Subject: Re: Prime example of a can of worms

On 2015-10-20 10:22:40 -0600, Kurt Seifried wrote:

 > 1) in openssl does the -2/-5 option matter with respect to
 > security?

Actually, no: it's just a "generator", so it can be almost any small
prime number - say, 3 or 7 or whatever. It can even be just co-prime
to group modulo base.

However, the value 2 is the default in OpenSSL, so there may be some
space for experiments with birthdays paradox... especially when the
modulo is small.

 > 2) Openssl/gnutls (and likely others) all apparently have
 > slight variations on how they generate/test primes [...]
 > this worries me, diversity is good, but if not implemented
 > correctly. Do any best practices actually exist?

All implementations I know of simply use the randomized algorithms
with Miller-Rabin primality test.

 > 3) in testing for primeness how sure are we? Reading
[wikipedia: "Miller-Rabin primality test"]
 > and so on these tests are all "probably prime" but I can't find
 > any data to show that e.g. given this set of large primes, tested
 > against the various traditional primality methods, and then brute
 > forced to confirm they are prime/not prime, what % failed?

There's the Agrawal-Kayal-Saxena primality test, but I'm unaware of
any attempts to use it for checking the prime candidates which passed
the Miller-Rabin primality test.

Alexey V. Vissarionov aka Gremlin from Kremlin <gremlin ПРИ gremlin ТЧК ru>
GPG: 8832FE9FA791F7968AC96E4E909DAC45EF3B1FA8 @ hkp://

Powered by blists - more mailing lists

Please check out the Open Source Software Security Wiki, which is counterpart to this mailing list.

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.