Weak DH primes and openssh

[mancha]

On Tue, May 26, 2015 at 03:10:01PM -0400, Daniel Kahn Gillmor wrote:
> Does anyone have a pointer to any decent free software for generating
> and verifying primality proofs?
> 
>           --dkg

OpenSSH generates strong pseudoprimes to k random bases (that if prime
would be "safe primes"). I think Darren uses k=100 (confirmation?) so
the way the math works out, each number he generates has at most a
1/(4^100) probability of being composite.  

In comparison, it's estimated the odds of getting crushed to death by a
vending machine are 1 in 112 million.

Death-by-chocolate-bar is about
14,347,661,109,455,270,317,338,947,253,046,094,665,376,812,444,489,221
more likely to happen to you than having a given "Darren-prime" turn out
to be composite.

The take-away, of course, is to always snack responsibly.

Nonetheless, the most we can currently say is the numbers are almost
surely prime. Certainty would be nice.

ECPP is the fastest prime proving algorithm that also provides
certificates (I think) and PRIMO is the king-of-the-hill implementation
(others exist but are significantly slower with bigger numbers).

Though as you mentioned PRIMO's not libre (just free), the math in the
certificates is open-source and that's really the critical part here.

The proofs themselves are sequences of steps that at each step (except
the last) prove a number N is prime if a smaller number R is prime.
Every subsequent step takes its N from the previous step's R and this
continues until we arrive at an R < 34*10^13 because such an R can be
proven prime if it is a strong pseudoprime to the base of the 7 primes
smaller than 19 (i.e. 2, 3, 5, 7, 11, 13, 17)

TL;DR

With PRIMO's help, I've proved the first 200 strong pseudoprimes in
the latest v1.12 moduli file are indeed prime. Darren, so far you're
batting a thousand!

I've uploaded my proofs to factordb.com for independent verification
and complementary confirmation proofs.

For example, check out the 4th prime in Darren's new moduli file: 

https://tinyurl.com/pg66aq5

As I write this I've checked through #209. Those with spare CPU cycles
on 64-bit Linux can help with the 65 strong pseudoprimes remaining
(#210 to #274). 

Those who wish to help should get PRIMO [1] and grab the full set of
input files I made:

http://sf.net/projects/mancha/files/misc/openssh-moduli-20150522_primo.tar.bz2

The 7680-bit moduli (#225 - #248) and 8192-bit moduli (#249 - #274) are
up for grabs. Probably best if you claim your range to avoid effort
duplication.

--mancha

PS In addition to factordb.com, ecpp-dj [2] can verify PRIMO certs.
ecpp-dj also proves primality but it is slower than PRIMO and more
importantly its cert format can't be independently verified.

------

[1] http://www.ellipsa.eu/public/primo/files/primo-411-lx64.7z
[2] http://sti15.com/nt/ecpp-dj-1.04.tar.gz
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL: <http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20150527/2b0d51e4/attachment.bin>