3 ms·

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

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.

kazinator 5y ago
> 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.
- wahern 5y ago
  > 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.
- postalrat 5y ago
  How about "choosing four random dictionary words for a password is best, even if it it happens to be a complete sentence"

kazinator 5y ago

> 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.

wahern 5y ago
> 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.
postalrat 5y ago
How about "choosing four random dictionary words for a password is best, even if it it happens to be a complete sentence"