4 ms·

Benchmarking RSA Key Generation

49 points by mfrw 2y ago

throw0101c 2y ago
For new deployments/protocols, is there any reason to use RSA? Is RSA (mostly?) about legacy support nowadays?
- bux93 2y ago
  For new protocols, go with X25519MLKEM768, then it's quantum proof as well.
  - daneel_w 2y ago
    To my understanding, even with Shor's algorithm, RSA is quantum-resistant when applying sufficiently large numbers such that the quantum computer used to locate the prime must be "sufficiently larger", i.e. a cat and mouse game of sorts until some major breakthrough comes along. I agree with simply moving to Ed25519 and X25519/ML-KEM etc.
    - honzaik 2y ago
      well, it depends on the size of the quantum computer. of course you can make large enough RSA keys (depends whats your security margin/assumptions) but the problem is that the size/computational increase is exponential whereas the solving speed scales polynomially. https://eprint.iacr.org/2017/351 https://eprint.iacr.org/2017/351
      - maginx 2y ago
        The size/computational complexity of usage also only grows as a polynomial with RSA. But even with this in mind, a quantum computer that can crack in polynomial time is still problematic. While you can increase the key size, the operator of the quantum computer could enlarge his computer, a true cat-and-mouse game. Unlike the current situation where usage complexity grows as a polynomial, while cracking grows exponentially. This difference is the reason why we can pick key sizes where signing/decryption takes a millisecond while cracking it takes (presumably) billions of years.
- wolf550e 2y ago
  Ed25519 has been recommended over RSA for many years, post-quantum stuff is recent. RSA should only be used to support old protocols like webpki certificates.
- upofadown 2y ago
  RSA is faster than elliptic curves for signature verification and encryption. It is one of the oldest methods (half a century) which suggests that it could be a good choice when you need the lowest possible chance of some discovered weakness. It can be used for both signing and encryption (but not with the same key pair).
- maginx 2y ago
  I still see a lot of RSA especially for encryption. While ECC can be used for encryption it is more convoluted and much less supported in hardware, software etc. than RSA decryption/encryption.
- thayne 2y ago
  FIPS 140-2 Compliance. FIPS 140-3 adds support for ECC, but it is relatively new, and there aren't a lot of modules that have been certified for it yet, so depending on you your environment and requirements you might still need to use RSA. Or you are doing a new deployment that needs to be compatible with something that only supports RSA.
jdewerd 2y ago
> The prime-counting function approximation tells us there are Li(x) primes less than x, which works out[5] to one prime every 354 odd integers of 1024 bits. Rule of thumb: Want a 1024-bit prime? Try 1024 1024-bit candidates and you'll probably find one. Want a 4096-bit prime? Try 4096 4096-bit candidates and you'll probably find one. The approximate spacing of primes around p is ln(p), so ln(2^1024) = 1024*ln(2), and ln(2)=0.693 so if you are willing to absorb 0.693 into your rule of thumb as a safety margin you get the delightfully simple rule of thumb above. Of course, you'll still want to use a sieve to quickly reject numbers divisible by 2, 3, 5, 7, etc, and this easily rejects 90% of numbers, and then do a Fermat primality test on the remainders (which if you squint is sort of like "try RSA, see if it works"), and then do Miller-Rabin test to really smash down the probability that your candidate isn't prime. The probabilities can be made absurdly small, but it still feels a bit scandalous that the whole thing is probabilistic. EDIT: updated rule of thumb to reflect random candidate choice rather than sequential candidate choice.
- rainsford 2y ago
  It's been a while since I've looked at the literature on RSA prime generation, but I seem to remember that picking a random starting point and iterating until you find a prime is discouraged because primes aren't evenly distributed so key generation timing could reveal some information about your starting point and eventual prime choice. I'm not sure how realistic of an issue this is given the size of the primes involved. Even if an attacker can extract sensitive enough timing information to figure out exactly how many iterations were required to find a 1024 bit prime from a 1204 bit random starting point, I'm not aware of a good way to actually find either value. You do also introduce a bias since you're more likely to select prime numbers without a close neighbor in the direction you are iterating from, but again I'm not sure how practical an attack on this bias would be. Still, to avoid any potential risk there I seem to remember best practice being to just randomly generate numbers of the right size until you find a prime one. With the speed of modern RNGs, generating a fresh number each time vs iterating doesn't seem like a significant penalty.
  - honzaik 2y ago
    it might be this https://facthacks.cr.yp.to/fermat.html https://facthacks.cr.yp.to/fermat.html if N=p*q and p-q < sqrt(p) then its easy to factor
JacobiX 2y ago
It is fascinating (to me at least) that almost all RSA implementations rely on a probabilistic primality test, even though the probability of picking a pseudoprime is extremely small.
- FiloSottile 2y ago
  There's extremely small (like 2⁻²⁰, the chance of winning $50 000 with a $2 Powerball ticket [1]), and then there's cryptographically negligible (like 2⁻¹²⁰, the false negative chance of our primality test). The chance of something cryptographically negligible happening is about the same as the chance of the attacker guessing your key on the first try, or of a cosmic ray flipping a CPU flag inverting the result of "if !signature.verified { return err }". [1]: https://www.powerball.com/powerball-prize-chart https://www.powerball.com/powerball-prize-chart
  - mras0 2y ago
    I happened to look at this recently, and while I understand the argument (but not the math) of having to do fewer Miller-Rabain rounds, why would you do so in PRACTICAL settings? Unlike ECC you're likely only generating long term keys, so shorter key generation time seems like a bad tradeoff. Composite candidates are going to be rejected early, so you're (with high probability) not doing expensive calculations for most candidates. My reading of [BSI B.5.2](https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TG02102/BSI-TR-02102-1.pdf https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publicat...) confirms this. Of course random bit flips could interfere, but other measures should thwart this in high-stakes environments (at least to some degree).
    - FiloSottile 2y ago
      The number of Miller-Rabin rounds has to be bounded, so if you're not going to base your bound on reaching a cryptographically negligible change of false positives, what are you going to base it on? Should we do 10? 15? The problem with "x should be enough, but why not do more?" arguments is that they can be applied recursively, and never answer the question "ok so when should we stop?"

49 points by mfrw 2y ago

throw0101c 2y ago

For new deployments/protocols, is there any reason to use RSA? Is RSA (mostly?) about legacy support nowadays?

bux93 2y ago
For new protocols, go with X25519MLKEM768, then it's quantum proof as well.
- daneel_w 2y ago
  To my understanding, even with Shor's algorithm, RSA is quantum-resistant when applying sufficiently large numbers such that the quantum computer used to locate the prime must be "sufficiently larger", i.e. a cat and mouse game of sorts until some major breakthrough comes along. I agree with simply moving to Ed25519 and X25519/ML-KEM etc.
  - honzaik 2y ago
    well, it depends on the size of the quantum computer. of course you can make large enough RSA keys (depends whats your security margin/assumptions) but the problem is that the size/computational increase is exponential whereas the solving speed scales polynomially. https://eprint.iacr.org/2017/351 https://eprint.iacr.org/2017/351
    - maginx 2y ago
      The size/computational complexity of usage also only grows as a polynomial with RSA. But even with this in mind, a quantum computer that can crack in polynomial time is still problematic. While you can increase the key size, the operator of the quantum computer could enlarge his computer, a true cat-and-mouse game. Unlike the current situation where usage complexity grows as a polynomial, while cracking grows exponentially. This difference is the reason why we can pick key sizes where signing/decryption takes a millisecond while cracking it takes (presumably) billions of years.
wolf550e 2y ago
Ed25519 has been recommended over RSA for many years, post-quantum stuff is recent. RSA should only be used to support old protocols like webpki certificates.
upofadown 2y ago
RSA is faster than elliptic curves for signature verification and encryption. It is one of the oldest methods (half a century) which suggests that it could be a good choice when you need the lowest possible chance of some discovered weakness. It can be used for both signing and encryption (but not with the same key pair).
maginx 2y ago
I still see a lot of RSA especially for encryption. While ECC can be used for encryption it is more convoluted and much less supported in hardware, software etc. than RSA decryption/encryption.
thayne 2y ago
FIPS 140-2 Compliance. FIPS 140-3 adds support for ECC, but it is relatively new, and there aren't a lot of modules that have been certified for it yet, so depending on you your environment and requirements you might still need to use RSA. Or you are doing a new deployment that needs to be compatible with something that only supports RSA.

jdewerd 2y ago

> The prime-counting function approximation tells us there are Li(x) primes less than x, which works out[5] to one prime every 354 odd integers of 1024 bits. Rule of thumb: Want a 1024-bit prime? Try 1024 1024-bit candidates and you'll probably find one. Want a 4096-bit prime? Try 4096 4096-bit candidates and you'll probably find one. The approximate spacing of primes around p is ln(p), so ln(2^1024) = 1024*ln(2), and ln(2)=0.693 so if you are willing to absorb 0.693 into your rule of thumb as a safety margin you get the delightfully simple rule of thumb above. Of course, you'll still want to use a sieve to quickly reject numbers divisible by 2, 3, 5, 7, etc, and this easily rejects 90% of numbers, and then do a Fermat primality test on the remainders (which if you squint is sort of like "try RSA, see if it works"), and then do Miller-Rabin test to really smash down the probability that your candidate isn't prime. The probabilities can be made absurdly small, but it still feels a bit scandalous that the whole thing is probabilistic. EDIT: updated rule of thumb to reflect random candidate choice rather than sequential candidate choice.

rainsford 2y ago
It's been a while since I've looked at the literature on RSA prime generation, but I seem to remember that picking a random starting point and iterating until you find a prime is discouraged because primes aren't evenly distributed so key generation timing could reveal some information about your starting point and eventual prime choice. I'm not sure how realistic of an issue this is given the size of the primes involved. Even if an attacker can extract sensitive enough timing information to figure out exactly how many iterations were required to find a 1024 bit prime from a 1204 bit random starting point, I'm not aware of a good way to actually find either value. You do also introduce a bias since you're more likely to select prime numbers without a close neighbor in the direction you are iterating from, but again I'm not sure how practical an attack on this bias would be. Still, to avoid any potential risk there I seem to remember best practice being to just randomly generate numbers of the right size until you find a prime one. With the speed of modern RNGs, generating a fresh number each time vs iterating doesn't seem like a significant penalty.
- honzaik 2y ago
  it might be this https://facthacks.cr.yp.to/fermat.html https://facthacks.cr.yp.to/fermat.html if N=p*q and p-q < sqrt(p) then its easy to factor

JacobiX 2y ago

It is fascinating (to me at least) that almost all RSA implementations rely on a probabilistic primality test, even though the probability of picking a pseudoprime is extremely small.

FiloSottile 2y ago
There's extremely small (like 2⁻²⁰, the chance of winning $50 000 with a $2 Powerball ticket [1]), and then there's cryptographically negligible (like 2⁻¹²⁰, the false negative chance of our primality test). The chance of something cryptographically negligible happening is about the same as the chance of the attacker guessing your key on the first try, or of a cosmic ray flipping a CPU flag inverting the result of "if !signature.verified { return err }". [1]: https://www.powerball.com/powerball-prize-chart https://www.powerball.com/powerball-prize-chart
- mras0 2y ago
  I happened to look at this recently, and while I understand the argument (but not the math) of having to do fewer Miller-Rabain rounds, why would you do so in PRACTICAL settings? Unlike ECC you're likely only generating long term keys, so shorter key generation time seems like a bad tradeoff. Composite candidates are going to be rejected early, so you're (with high probability) not doing expensive calculations for most candidates. My reading of [BSI B.5.2](https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TG02102/BSI-TR-02102-1.pdf https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publicat...) confirms this. Of course random bit flips could interfere, but other measures should thwart this in high-stakes environments (at least to some degree).
  - FiloSottile 2y ago
    The number of Miller-Rabin rounds has to be bounded, so if you're not going to base your bound on reaching a cryptographically negligible change of false positives, what are you going to base it on? Should we do 10? 15? The problem with "x should be enough, but why not do more?" arguments is that they can be applied recursively, and never answer the question "ok so when should we stop?"