Re:Researcher uses 379-year-old algorithm to crack crypto ke...
by ColinWright on Wednesday March 23, 2022 @05:22PM
(#30783572)
With a quick skim by my non-expert eye, they are really saying that using the full limit of "strong primes" is unnecessary, and that it suffices to use random primes. But random primes are not such that p-1 is smooth, "random primes" will still have a reasonably large factor, so the comment remains.
If you take it to an extreme, using a prime p of the form 2^k+1 makes pq reasonably easy to factor (I think) using the Pollard P-1 algorithm.
So there's still value in ensuring that p-1 and q-1 both have a reasonably large factor.
But I'm at, and possibly beyond, my actual knowledge, and somewhat into "better safe than sorry" speculation.
If you take it to an extreme, using a prime p of the form 2^k+1 makes pq reasonably easy to factor (I think) using the Pollard P-1 algorithm.
So there's still value in ensuring that p-1 and q-1 both have a reasonably large factor.
But I'm at, and possibly beyond, my actual knowledge, and somewhat into "better safe than sorry" speculation.