What will happen to web security if RSA was broken (by a new factorization technique) which is used in (ex: digital certificates)?

Are there any alternatives to RSA? If there are any alternatives, what are they? Are they already implemented as a backup?


The currently popular algorithms fall in three categories:

  • Based on factoring (RSA, Rabin)
  • Based on the discrete logarithm problem in finite fields (Diffie-Hellman, DSA,...)
  • Based on the discrete logarithms problem on elliptic curves (EC-DH, ECDSA,...)

The currently best factoring algorithms and computing discrete logarithms in a finite field are quite similar (number field sieves based on index calculus), so they're likely to fall together. There is currently no known way to apply these algorithms to popular elliptic curves.

All of them share a common weakness: If we get large enough quantum-computers capable of running Shor's algorithm, they all get broken.

There are algorithms using different mathematical problems that are believed to withstand quantum computers. NIST is currently holding a competition to standardize such an algorithm. Many of them come with significant downsides, such as large key/message/signature sizes or patents.

  • Lattice based - NTRU is an old and well known example, but adoption has been hampered by patents
  • Code based - McEliece is the best known. Key size is large.
  • Multivariate-quadratic-equations
  • Hash signatures - signature only. Simple ones can only be used once. Reusable ones are complex and either produce large signatures or require the signer to keep track how many messages they signed.
  • Supersingular isogeny key exchange

Most of these algorithms are still experimental, but we should get some usable standardized implementations as the NIST competition progresses.

|improve this answer|||||

There seem to be people out there who claim to have a solution to the problem: https://www.impactsemantics.com/semiprime-factoring (although I am skeptical) Also, if RSA numbers are no longer safe, then you can be sure that the novel maths (and there has to be more than just another algorithm of the traditional sort to it) underlying that possible solution will also likely undermine other cryptosystems like EC, DSA etc..so yes, I think it would be quite a shakedown.

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.