3 ms·

I’m talking specifically about RSA being eventually broken. If just RSA is broken and you were using ECDHE for symmetric keying, then you’re fine. The point is

I’m talking specifically about RSA being eventually broken. If just RSA is broken and you were using ECDHE for symmetric keying, then you’re fine. The point is that you can build stuff on top of RSA today even if you expect it to be broken eventually if RSA is only for identity verification.

minitech 2y ago
The relevant RSA break is sufficiently powerful quantum computers, which also break ECDH (actually, ECDH is easier than classically equivalent-strength RSA for quantum computers[1]), so no, you’re not fine. [1] https://security.stackexchange.com/questions/33069/why-is-ecc-more-vulnerable-than-rsa-in-a-post-quantum-world https://security.stackexchange.com/questions/33069/why-is-ec...
- coppsilgold 2y ago
  I would actually expect RSA to see a resurgence due to this. Especially because you can technically scale RSA to very high levels potentially pushing the crack date to decades later than any ECC construction. With the potential that such a large quantum computer may never even arrive. There are several choices with scaling RSA too, you can push the primes which slows generation time considerably. Or the more reasonable approach is to settle on a prime size but use multiple of them (MP-RSA). The second approach scales indefinitely. Though it would only serve a purpose if you are determined to hedge against the accepted PQC algorithms (Kyber/MLKEM, McEliece) being broken at some point.
  - bwesterb 2y ago
    If you don't mind a one terabyte public key. https://eprint.iacr.org/2017/351.pdf https://eprint.iacr.org/2017/351.pdf
    - adgjlsfhk1 2y ago
      also that paper (IMO) is ridiculously conservative. Just using 1GB keys is plenty sufficient since it would require a quantum computer with a billion bits to decrypt.
      - trogdor 2y ago
        Although I know it’s an apocryphal quote, I am reminded of “640K should be enough for anybody.” The Intel 4004, in 1971, had only 2,250 transistors. A handful of qubits today might become a billion sooner than you think.
        adgjlsfhk1 2y ago
        it took until 2011 before Sandy bridge cracked 2 billion. If we get 40 years of quantum resistance from 1GB RSA, that would be pretty great.
      - Vecr 2y ago
        How long does it take to generate a key that big? What probabilities do you need to put on generating a composite number and not a prime? Does the prime need extra properties?
        adgjlsfhk1 2y ago
        Based on https://eprint.iacr.org/2017/351.pdf https://eprint.iacr.org/2017/351.pdf it would be about 1900 core hours (but I'm pretty sure optimized implementations could bring it down a bunch). No extra properties needed and moderate probability is sufficient.

minitech 2y ago

The relevant RSA break is sufficiently powerful quantum computers, which also break ECDH (actually, ECDH is easier than classically equivalent-strength RSA for quantum computers[1]), so no, you’re not fine. [1] https://security.stackexchange.com/questions/33069/why-is-ecc-more-vulnerable-than-rsa-in-a-post-quantum-world https://security.stackexchange.com/questions/33069/why-is-ec...

coppsilgold 2y ago
I would actually expect RSA to see a resurgence due to this. Especially because you can technically scale RSA to very high levels potentially pushing the crack date to decades later than any ECC construction. With the potential that such a large quantum computer may never even arrive. There are several choices with scaling RSA too, you can push the primes which slows generation time considerably. Or the more reasonable approach is to settle on a prime size but use multiple of them (MP-RSA). The second approach scales indefinitely. Though it would only serve a purpose if you are determined to hedge against the accepted PQC algorithms (Kyber/MLKEM, McEliece) being broken at some point.
- bwesterb 2y ago
  If you don't mind a one terabyte public key. https://eprint.iacr.org/2017/351.pdf https://eprint.iacr.org/2017/351.pdf
  - adgjlsfhk1 2y ago
    also that paper (IMO) is ridiculously conservative. Just using 1GB keys is plenty sufficient since it would require a quantum computer with a billion bits to decrypt.
    - trogdor 2y ago
      Although I know it’s an apocryphal quote, I am reminded of “640K should be enough for anybody.” The Intel 4004, in 1971, had only 2,250 transistors. A handful of qubits today might become a billion sooner than you think.
      - adgjlsfhk1 2y ago
        it took until 2011 before Sandy bridge cracked 2 billion. If we get 40 years of quantum resistance from 1GB RSA, that would be pretty great.
    - Vecr 2y ago
      How long does it take to generate a key that big? What probabilities do you need to put on generating a composite number and not a prime? Does the prime need extra properties?
      - adgjlsfhk1 2y ago
        Based on https://eprint.iacr.org/2017/351.pdf https://eprint.iacr.org/2017/351.pdf it would be about 1900 core hours (but I'm pretty sure optimized implementations could bring it down a bunch). No extra properties needed and moderate probability is sufficient.