3 ms·

Most cryptographic methods rely on factoring being computationally difficult. The outcome of this would be the near-total compromise of modern cryptographic met

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.

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.