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 _______________________________________________ openssh-unix-dev mailing list openssh-unix-dev@xxxxxxxxxxx https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
