24 ms·

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

by macphisto178 10y ago

dripton 10y ago
A lot of widely-used cryptography relies on factoring large numbers being difficult.
- _greim_ 10y ago
  Are we using "difficult" to mean "takes longer than the universe"? Since presumably that would be why we trust it for cryptography?
  - khedoros 10y ago
    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).
johnloeber 10y ago
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.
- tptacek 10y ago
  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.
  - johnloeber 10y ago
    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.
    - tptacek 10y ago
      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.
      - johnloeber 10y ago
        Gotcha. Very interesting. Thanks for the information. I didn't expect that a compromise of RSA would have such a (relatively speaking) small impact.
        wolf550e 10y ago
        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.

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

dripton 10y ago

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

_greim_ 10y ago
Are we using "difficult" to mean "takes longer than the universe"? Since presumably that would be why we trust it for cryptography?
- khedoros 10y ago
  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).

johnloeber 10y ago

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.

tptacek 10y ago
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.
- johnloeber 10y ago
  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.
  - tptacek 10y ago
    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.
    - johnloeber 10y ago
      Gotcha. Very interesting. Thanks for the information. I didn't expect that a compromise of RSA would have such a (relatively speaking) small impact.
      - wolf550e 10y ago
        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.