I live in South Africa, formally registered as the Republic of South Africa (RSA). These headlines always grab my attention before I click they mean Really Secure Algorithm. Why are you like this, brain?
I don’t see how this attack is specific to primes close to √N.
It is specific to knowing (or guessing) the relative sizes of the primes. For example, if, with a target product of around N, you always search for primes of size n^0.25 and n^0.75, and the attacker knows this, the attacker, knowing this, could exploit that.
It seems the lesson isn’t to not pick two primes that are close together, but to avoid giving away information that helps an attacker get an estimate of your primes.
Choosing your primes uniformly seems the best solution, even if that means sometimes picking ones close to each other, or a very small and a very large one. You only will want to avoid those to avoid the embarrassment when you are found out, when a would-be attacker (stupidly, in some sense) starts his search from zero or from numbers close to √N.
> Choosing your primes uniformly seems the best solution, even if that means sometimes picking ones close to each other
I can't agree with this because it's sounds too much like "choosing four random dictionary words for a password is best, even if it it happens to be be the phrase 'let me in please'".
If there are some known weak points in the space that attackers look for, it's probably good to avoid those.
> If there are some known weak points in the space that attackers look for, it's probably good to avoid those.
Presuming attempts to discriminate don't introduce greater risks, like even larger biases, introduction of side channels, more bug-prone code, etc. Modern crypto seems to try to balance both concerns. For example, by provably reducing the space of problematic values to something so miniscule that it can be ignored in implementations.
Yikes, doesn't Rambus own Cryptography Research? CR has good cryptographers. I'd have hoped Rambus had CR people who knew what they were doing examine their keygen.
On the other hand, I remember some DJB software for Rabin signatures, that for some reason intentionally generated primes that were close together (idr if they were THIS close). That always made me suspicious, even though DJB is a lot more clueful than almost anyone here.
> For security purposes, the integers p and q should be chosen at random and should be similar in magnitude but differ in length by a few digits to make factoring harder.
Every cryptography expert recommends against RSA so I'm not sure where you are getting "only governments" arguing against it.
Problems with RSA include the core algorithm being extremely difficult to ensure constant timing for (even using Montgomery ladders); padding being super easy to do wrong, which breaks the security; Different keys have drastically different security properties (see this article for example, but numerous others exist); The required key size for a secure connection is at least 2kb, preferably 4
etc, etc
ECC cryptography does not have the padding problems; despite being technically slower, constant-ish time RSA rapidly matches or exceeds the ECC time; You don't have the same "bad keys" problem; A secure key is only 256 bits.
