Re: Prime example of a can of worms

[gremlin () gremlin ru]

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://keys.gnupg.net