Hacker News Reader

Comment by macphisto178 | Hacker News Reader

for the ignorant (i.e. me) among us, what are the implications of factoring large numbers?

Most cryptographic methods rely on factoring being computationally difficult. The outcome of this would be the near-total compromise of modern cryptographic methods, i.e. the backbone of the internet would fall out.

No, RSA depends on factoring. Virtually nothing else does, although the conventional discrete logarithm might be related to factoring.

If RSA was broken, we'd deprecate RSA and move to elliptic curve. Continual advances in factoring and index calculus are in fact the reason we deploy elliptic curve in the first place. Almost every mainstream browser handles it fine.

No matter what happens with factoring, we should all be transitioning away from RSA anyways.

Sorry, I am not an expert. I was under the impression that RSA is still widely in use today, so the ramifications would be quite devastating.

RSA is in wide use, but alternatives to RSA are also widely deployed --- bordering on ubiquitous. A total break of RSA probably wouldn't be that much more traumatic than, say, Heartbleed was.

Multiple times over the last 15 years, we've had for all intents and purposes comparable breaks --- BERserk and the original rump session Bleichenbacher e=3 breaks, for instance --- which broke TLS, to the point where you could stand up an evil server and DNS-MITM people to it, and compromise pretty much everyone running (say) Firefox. It wasn't the end of the world. The patch for "integer factorization is solvable in polynomial time" would be slightly more dramatic than the e=3 bug, but not much more: everyone would just deprecate RSA and use ECC.

Gotcha. Very interesting. Thanks for the information. I didn't expect that a compromise of RSA would have such a (relatively speaking) small impact.

You wouldn't want to use a browser so old it doesn't support ECDSA with P-256 (e.g. Android < 4.0). There would be a lot of scary stories in the media, but servers can switch to ECDSA (e.g. let's encrypt supports it). Devices which cannot be updated (e.g. credit card terminals) would need to be replaced.

A lot of widely-used cryptography relies on factoring large numbers being difficult.

Are we using "difficult" to mean "takes longer than the universe"? Since presumably that would be why we trust it for cryptography?

Basically, yes. When we talk about how fast an algorithm is, we usually talk about how much longer it will take to run when you increase the length of the input.

Encryption works because you can double the size of the encryption key and make it take [very large number] times more operations to break the encryption (twice the work to encrypt+decrypt if you have the key, but tremendously harder to crack into without the key).

Reply on news.ycombinator.com