3

I am curious as to how exactly cyber-security would be affected if someone found a way to factor a large number quickly into its multiples. Let's assume that the time required for factorization is roughly equivalent to the time that it takes to multiply. How exactly would the present security landscape change?

Aswin P J
  • 133
  • 3
  • See also: [What kinds of encryption are _not_ breakable via Quantum Computers?](http://security.stackexchange.com/q/48022/29865) – Ajedi32 Apr 21 '16 at 17:56

1 Answers1

6

This is highly speculative, but, presumably, there would be much wailing and grinding of teeth. Then people would migrate to asymmetric cryptosystems that use elliptic curves. There would be some heavy business for CA; many SSH keys would have to be rolled over; and the PGP users would cringe first at the idea that anybody can impersonate them by forging signatures, then would cringe again when they notice that nobody actually bothers to do just that.

Switching to ECDSA would have the nice side-effect of killing off the last WinXP+IE setups, since the X.509 implementation used by WinXP+IE (for SSL connections to Web servers) does not support ECDSA.

Banking systems (EMV smart cards...) tend to use RSA so there would be a quickened renewal of cards and terminals, which would incur much grumbling from merchants, and would still take a couple of years to be effective.

A crucial point to understand is that while difficulty of integer factorization is what RSA security relies on, easy factorization does not immediately make the systems cease to work. If you can factor, say, Google's certificate RSA key, then you can impersonate Google, or decrypt passively recorded sessions, but you still have, as an attacker, to mount the eavesdropping or network spoofing system (which is not that hard to do, but not completely immediate either). I predict that the panic reaction would be much greater than the actual issues.

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • Great description! I like all the cringing that you predict will happen. I completely agree. – Brent Kirkpatrick Apr 15 '16 at 20:12
  • Fast factorization can also be used to accelerate the discrete logarithm problem, which breaks EC. This is what Shor's algorithm does, for example. But what I think is worse about impersonating PGP users is the fact that everything they said can be retroactively decrypted. I use PGP, and if I discovered RSA could be trivially broken, I would immediately revoke my signature and not worry about impersonation one bit, but I would worry tremendously because of the idea that all the private, if not dangerously sensitive information I've encrypted could be read. – forest Apr 16 '16 at 09:10