4 ms·

Someone asked: > Is there an elegant way to eliminate bad pairs? Or do you have to enumerate all the reasons they could be bad and check after generation, rege

Someone asked: > Is there an elegant way to eliminate bad pairs? Or do you have to enumerate all the reasons they could be bad and check after generation, regenerate if fail? They've since deleted the question, but here is the reply I typed: Broadly, you want p and q to differ in length by a few digits, and you want each of p-1 and q-1 to have large factors. So once you choose p and q literally at random, with no special structure, then you use Pollard Rho to strip small factors from each of p-1 and q-1 to make sure there's a large(ish) factor in each. Then that's about the best you can do. Factoring integers is a heavily studied subject - for obvious reasons - so there are unexpected "gotchas" here and there, but the above is a reasonable compromise. There are those who advise never to use RSA at all, and they are probably better qualified than I. Even so, using the above heuristics, and large keys, it still seems a reasonable choice for some applications. Also, others will say you should always use Elliptic Curves, but I have no personal knowledge about what makes a particular curve good or bad, and all my reading tells me nothing specific, so I'm relying on experts saying "Use this curve, it's a good one". I have no way of knowing if they're telling me the truth, or if there is some magic, cleverly disguised backdoor of which I am unaware. TL;TD - Yes, you have to enumerate all the reasons your choice of (p,q) might be bad and simply try again if your choice fails.

WhitneyLand 5y ago
Do people ask/answer this question out of instinct, curiously or practically? The article says the chances of a problem with independent randomization are approximately 1 in 2^500. Recall a UUID is 128 bits. Am I thinking right, this would be the odds of roughly duplicating UUIDs multiple times in a row? At what limit is the additional code complexity warranted?
- ColinWright 5y ago
  I don't know why people ask the question, but it's good that it gets asked. It's possible to choose p and q badly, even if you're choosing them randomly, so yes, it's always worth checking. Without the checks there is a chance, even if it's a small one, that your communications are completely insecure. But in truth the answer is : It depends. Always do the analysis, and understand the risks and trade-offs.
  - thomasahle 5y ago
    > yes, it's always worth checking. If the error probabilities are low enough, it's much more likely that your computation is invalidated by atmospheric radiation. On the other hand, some of the code could be wrong, so I agree it's good to have an independent soundness check.
- thomasahle 5y ago
  The issues happen because people cut corners to optimize performance. Even if it's just generating random numbers, they use unproven heuristics that seem "just as good". An example from a few years ago: To find a random prime, the "correct" way is to generate a random number, and check if it's prime. However, for performance, people would instead generate a single random number, n, and then try n+1, n+2, etc. until they got a prime. The result? Too many RSA keys used the same primes, because primes following "a long run of non primes" were much more likely to get picked than say the upper prime in a prime pair. Once two RSA keys share a prime, you can use Euclid's algorithm to find out which. Get a large batch of badly generated RSA key pairs, and you were likely to find some collisions. In conclusion it's not that looking for performance optimizations is inherently bad, but you really have to strictly prove that you don't change anything important.
  - kwantam 5y ago
    The general message here is true, but I suspect that your specific example is not. Do you have a citation for the claim that PRIMEINC (generate random odd value, increment by 2 until you find a prime) caused overlapping prime factors? The work I'm guessing you refer to on colliding prime factors is by Heninger et al., "Mining Your Ps and Qs", USENIX Security 2012 [1]. That paper does not mention anything about PRIMEINC causing this problem. The cases they found all related to bad entropy or extremely bad ways of generating moduli (like, pick two random values from a short list of known primes and use that as the modulus---an IBM product actually did this). In fact, PRIMEINC is provably secure for generating RSA keys (though this was only shown somewhat recently): Abboud and Prest [2] analyze the distribution of outputs from PRIMEINC and show (see Section 4.1) that the security loss is negligible under quite mild conditions. Concretely, generating a reasonably sized RSA key using PRIMEINC rather than uniformly random primes reduces the security of RSA by a few bits at most. But in some sense this reinforces your point---it was definitely not trivial to show that a tweak as seemingly simple as PRIMEINC is actually safe! [1] https://factorable.net/weakkeys12.extended.pdf https://factorable.net/weakkeys12.extended.pdf [2] https://eprint.iacr.org/2020/815.pdf https://eprint.iacr.org/2020/815.pdf
    - thomasahle 5y ago
KMag 5y ago
Note that some algorithms (Rivest's time lock puzzles[0] come to mind) don't have obvious equivalents for elliptic curves, so it's still important to be able to generate good RSA keys. [0]https://people.csail.mit.edu/rivest/pubs/Riv19f.pdf https://people.csail.mit.edu/rivest/pubs/Riv19f.pdf Essentially, you use some high iteration count of the Blum Blum Shub pseudorandom number generator to encrypt some data. If you know the factorization of your modulus, you can randomly seek very far ahead in the Blum Blum Shub output. Others that don't know the factorization will need to sequentially generate random numbers from the known starting seed for several years to find the pseudorandom output needed to decrypt the message. Blum Blum Shub parallelizes very very poorly if the modulus factorization isn't known. Very well financed adversaries can use gallium arsenide/strained silicon on saphire ASICs, etc. to get constant factor speed-ups over a regular desktop machine, but one can make good educated upper limit guesses on these advantages.
abdullahkhalids 5y ago
Is there a book that builds up this knowledge?
- ColinWright 5y ago
  I don't know of a single book that covers this sort of thing. There are lots of on-line resources, and it's very much a case of having to chase down references and read them, and then read the works they refer to, and so on. For RSA weaknesses the Wikipedia page is a fair place to start: https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Padding https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Padding Simply doing a search for RSA attacks will give you several places to start ... this is a good one: https://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf https://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf It's one thing to read about the design and implementation of a cryptosystem, but you really want to search for attacks against them. This is a deep and gnarly area, with lots of people who know enough to be dangerous. Including me.
CaptainNegative 5y ago
> you want p and q to differ in length by a few digits Not exactly; a uniformly random (admissible) p,q pair will suffice with very high probability, but in those cases p and q will likely have the same number of digits. One can avoid the bad case for Fermat's method by explicitly forcing p and q to be a couple orders of magnitude off, but the probability this helps is so low that you're only just reducing your security in aggregate: the bits of entropy you're shaving off by restricting the sample space are more impactful than the resilience gained by avoiding a (very, very) tail event. Assuming, of course, your parameters and (P)RNG are decent. See further discussion here on the history of that recommendation https://crypto.stackexchange.com/questions/35087/should-rsa-primes-p-and-q-differ-in-length-by-a-few-digits https://crypto.stackexchange.com/questions/35087/should-rsa-... .
jwilk 5y ago
> you want each of p-1 and q-1 to have large factors Why?
- ColinWright 5y ago
  At it's simplest, the algebraic structure of the integers modulo (pq) is simpler when p-1 or q-1 are "smooth" (have no big factors for some definition of "big") and that means that algebraic methods of factoring can be more effective. It's a complicated topic. The magic terms to search for are "strong prime" or "Sophie Germain Prime". Disclaimer: I'm not an expert ... someone else might be able to comment more usefully.
  - jwilk 5y ago
    https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes#Cryptography https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes... says: > with the current factorization technology, the advantage of using safe and strong primes appears to be negligible (I'm not an expert either.)
    - ColinWright 5y ago
      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.
    - ColinWright 5y ago
      While doing other rsearch I stumbled across this quotation from Wikipedia: > The numbers p and q should not be "too close", lest the Fermat factorization for n be successful. If p − q is less than 2n^{1/4} (n = p⋅q, which even for "small" 1024-bit values of n is 3×10^{77}), solving for p and q is trivial. Furthermore, if either p − 1 or q − 1 has only small prime factors, n can be factored quickly by Pollard's p − 1 algorithm, and hence such values of p or q should be discarded. Wikipedia is not always right, and certainly shouldn't be trusted implicitly on details in depth, but it's an interesting thing for them to be saying.

WhitneyLand 5y ago

Do people ask/answer this question out of instinct, curiously or practically? The article says the chances of a problem with independent randomization are approximately 1 in 2^500. Recall a UUID is 128 bits. Am I thinking right, this would be the odds of roughly duplicating UUIDs multiple times in a row? At what limit is the additional code complexity warranted?

ColinWright 5y ago
I don't know why people ask the question, but it's good that it gets asked. It's possible to choose p and q badly, even if you're choosing them randomly, so yes, it's always worth checking. Without the checks there is a chance, even if it's a small one, that your communications are completely insecure. But in truth the answer is : It depends. Always do the analysis, and understand the risks and trade-offs.
- thomasahle 5y ago
  > yes, it's always worth checking. If the error probabilities are low enough, it's much more likely that your computation is invalidated by atmospheric radiation. On the other hand, some of the code could be wrong, so I agree it's good to have an independent soundness check.
thomasahle 5y ago
The issues happen because people cut corners to optimize performance. Even if it's just generating random numbers, they use unproven heuristics that seem "just as good". An example from a few years ago: To find a random prime, the "correct" way is to generate a random number, and check if it's prime. However, for performance, people would instead generate a single random number, n, and then try n+1, n+2, etc. until they got a prime. The result? Too many RSA keys used the same primes, because primes following "a long run of non primes" were much more likely to get picked than say the upper prime in a prime pair. Once two RSA keys share a prime, you can use Euclid's algorithm to find out which. Get a large batch of badly generated RSA key pairs, and you were likely to find some collisions. In conclusion it's not that looking for performance optimizations is inherently bad, but you really have to strictly prove that you don't change anything important.
- kwantam 5y ago
  The general message here is true, but I suspect that your specific example is not. Do you have a citation for the claim that PRIMEINC (generate random odd value, increment by 2 until you find a prime) caused overlapping prime factors? The work I'm guessing you refer to on colliding prime factors is by Heninger et al., "Mining Your Ps and Qs", USENIX Security 2012 [1]. That paper does not mention anything about PRIMEINC causing this problem. The cases they found all related to bad entropy or extremely bad ways of generating moduli (like, pick two random values from a short list of known primes and use that as the modulus---an IBM product actually did this). In fact, PRIMEINC is provably secure for generating RSA keys (though this was only shown somewhat recently): Abboud and Prest [2] analyze the distribution of outputs from PRIMEINC and show (see Section 4.1) that the security loss is negligible under quite mild conditions. Concretely, generating a reasonably sized RSA key using PRIMEINC rather than uniformly random primes reduces the security of RSA by a few bits at most. But in some sense this reinforces your point---it was definitely not trivial to show that a tweak as seemingly simple as PRIMEINC is actually safe! [1] https://factorable.net/weakkeys12.extended.pdf https://factorable.net/weakkeys12.extended.pdf [2] https://eprint.iacr.org/2020/815.pdf https://eprint.iacr.org/2020/815.pdf
  - thomasahle 5y ago

KMag 5y ago

Note that some algorithms (Rivest's time lock puzzles[0] come to mind) don't have obvious equivalents for elliptic curves, so it's still important to be able to generate good RSA keys. [0]https://people.csail.mit.edu/rivest/pubs/Riv19f.pdf https://people.csail.mit.edu/rivest/pubs/Riv19f.pdf Essentially, you use some high iteration count of the Blum Blum Shub pseudorandom number generator to encrypt some data. If you know the factorization of your modulus, you can randomly seek very far ahead in the Blum Blum Shub output. Others that don't know the factorization will need to sequentially generate random numbers from the known starting seed for several years to find the pseudorandom output needed to decrypt the message. Blum Blum Shub parallelizes very very poorly if the modulus factorization isn't known. Very well financed adversaries can use gallium arsenide/strained silicon on saphire ASICs, etc. to get constant factor speed-ups over a regular desktop machine, but one can make good educated upper limit guesses on these advantages.

abdullahkhalids 5y ago

Is there a book that builds up this knowledge?

ColinWright 5y ago
I don't know of a single book that covers this sort of thing. There are lots of on-line resources, and it's very much a case of having to chase down references and read them, and then read the works they refer to, and so on. For RSA weaknesses the Wikipedia page is a fair place to start: https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Padding https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Padding Simply doing a search for RSA attacks will give you several places to start ... this is a good one: https://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf https://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf It's one thing to read about the design and implementation of a cryptosystem, but you really want to search for attacks against them. This is a deep and gnarly area, with lots of people who know enough to be dangerous. Including me.

CaptainNegative 5y ago

> you want p and q to differ in length by a few digits Not exactly; a uniformly random (admissible) p,q pair will suffice with very high probability, but in those cases p and q will likely have the same number of digits. One can avoid the bad case for Fermat's method by explicitly forcing p and q to be a couple orders of magnitude off, but the probability this helps is so low that you're only just reducing your security in aggregate: the bits of entropy you're shaving off by restricting the sample space are more impactful than the resilience gained by avoiding a (very, very) tail event. Assuming, of course, your parameters and (P)RNG are decent. See further discussion here on the history of that recommendation https://crypto.stackexchange.com/questions/35087/should-rsa-primes-p-and-q-differ-in-length-by-a-few-digits https://crypto.stackexchange.com/questions/35087/should-rsa-... .

jwilk 5y ago

> you want each of p-1 and q-1 to have large factors Why?

ColinWright 5y ago
At it's simplest, the algebraic structure of the integers modulo (pq) is simpler when p-1 or q-1 are "smooth" (have no big factors for some definition of "big") and that means that algebraic methods of factoring can be more effective. It's a complicated topic. The magic terms to search for are "strong prime" or "Sophie Germain Prime". Disclaimer: I'm not an expert ... someone else might be able to comment more usefully.
- jwilk 5y ago
  https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes#Cryptography https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes... says: > with the current factorization technology, the advantage of using safe and strong primes appears to be negligible (I'm not an expert either.)
  - ColinWright 5y ago
    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.
  - ColinWright 5y ago
    While doing other rsearch I stumbled across this quotation from Wikipedia: > The numbers p and q should not be "too close", lest the Fermat factorization for n be successful. If p − q is less than 2n^{1/4} (n = p⋅q, which even for "small" 1024-bit values of n is 3×10^{77}), solving for p and q is trivial. Furthermore, if either p − 1 or q − 1 has only small prime factors, n can be factored quickly by Pollard's p − 1 algorithm, and hence such values of p or q should be discarded. Wikipedia is not always right, and certainly shouldn't be trusted implicitly on details in depth, but it's an interesting thing for them to be saying.