Verification of primes in /etc/ssh/moduli file

[Damien Miller]

On Thu, 26 Aug 2021, Demi Marie Obenour wrote:

> On 8/21/21 6:06 AM, Damien Miller wrote:
> > 
> > Excellent - one question: how do you generate/prove safe primes? I was
> > never able to figure out how to prove that both N and (N-1)/2 are prime
> > (though I thought it might be possible using Pocklington's criteria).
> 
> One can prove primality using the Miller-Ramin test, which will
> detect composites with probability at least 3/4 per round.  After 64
> rounds the likelihood of a composite not being detected is not more
> than 2⁻¹²⁸, even for adversarial choices of moduli.  Note that
> the primality testing APIs in cryptographic libraries are often not
> designed for this, as they perform optimizations that are not valid for
> adversarially chosen numbers.

Yeah, that leads us to the point at which I ended up - you could have
a primality proof for the prime, but have to put up with Miller-Rabin
evidence that it's safe. It didn't seem like a big enough win, given
the ostensible goal was to get away from heuristic methods to begin
with. But like I said, I was limited by my mathematicaly knowledge :)

-d