1
$\begingroup$

Much of the information transferred over the internet is encrypted using methods which rely on the fact that currently, very large numbers are extremely difficult to factor. Imagine that in the near future, developments in mathematics result in algorithms can factor numbers in a fraction of a second (which is actually possible). How much would "life as we know it", with online banking, communication, etc. change? Would these industries be able to quickly develop other methods of encryption, or would the world get kicked back to pre-internet days?

$\endgroup$

closed as too broad by Aify, JDługosz, Hohmannfan, bilbo_pingouin, a CVn Jun 19 '16 at 14:02

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ The premise stated in the question does not necessarily imply the outcome given in the title. $\endgroup$ – a CVn Jun 19 '16 at 14:05
2
$\begingroup$

There is no one answer to this, because it is too complicated of a topic. The key to the answer would be in global dynamics. How does China respond? How does Russia respond? How does ISIS respond? How does Anonymous respond?

Rest assured, very little encryption relies on the difficulty of factoring large composite numbers. Most symmetric algorithms rely on other proofs for their security. The facet of encryption that would be pounded would be public-key encryption, where RSA is the current reigning champion.

There are other public-key encryptions out there. Some even rely on lattice based techniques that are immune to Shor's algorithm, making them particularly resilient against quantum computers. In the greater scheme of things, the internet can survive someone determining how to rapidly factor a large composite number.

However, in that short period during the changeover, there would be a lot of turmoil. The individual players on this global scene would have a lot to say about how things play out.

$\endgroup$
  • 1
    $\begingroup$ "There is no one answer to this, because it is too complicated of a topic." - this question is obviously too broad/opinion based and should not have been answered. Cort, you're one of the top users of WB, and it pains me to see you setting a bad example T.T $\endgroup$ – Aify Jun 19 '16 at 4:34
  • $\begingroup$ RSA has long been broken; there was a security break a few years ago which released their algorithms. Unfortunately, it doesn't stop corporations from relying on RSA tokens. $\endgroup$ – Marion Jun 19 '16 at 4:41
  • 1
    $\begingroup$ @Marion In the context of public key encryption, RSA is an algorithm for encryption that involves large prime numbers. It was actually released the day it was published. A good crypto algorithm assumes the enemy already has your algorithm, so there is no breach when it is released. The people who developed RSA then founded a company, also named RSA. Obviously this was to enjoy the fruits of their successful algorithm, but it does create some confusion, especially with respect to their security breach. $\endgroup$ – Cort Ammon Jun 19 '16 at 5:08
  • 1
    $\begingroup$ @MarkRipley The question asked about just factoring large composite numbers. Breaking all of crypto would be a more substantial hit, and probably would not have a meaningful worldbuilding answer. Elliptic curve crypto (ECC) is interesting. From my understanding (which is by no means perfect), ECC is very strong. However, Dual EC DRBG, an ECC pushed by the NSA, demonstrated an interesting issue with them: they're terribly easy to hide backdoors in. That would suggest they may be secure, but they can't be trusted =) $\endgroup$ – Cort Ammon Jun 19 '16 at 14:54
  • 1
    $\begingroup$ @CortAmmon That's why current opinion is that the curves should be selected in a highly transparent manner, in ways that involve no (or minimal) "magic constants". It's unexplained magic constants that provide opportunities for hiding back doors; if you tell people exactly how you chose the proposed constants, and ideally do so in a cryptographically secure fashion, there's really no good place to hide a back door. For example, an ECC curve involving just SHA512("Cort Ammon does not fully trust Dual EC DRBG") and the digits of $\pi$ is probably not a good candidate for hiding a back door in. $\endgroup$ – a CVn Jun 19 '16 at 16:44
1
$\begingroup$

I really like Cort's answer and I think it is the correct one. This one is just me bringing more info to the table.

There is a matter of scale involved. We usually hear about encryption keys with some amount of bits attached. That's the size of the key, and the longer it is, the more computing it takes to break.

Adding four extra bits to an encryption alghoritm will, on back-of-napkin calculations, make it one order of magnitude harder to break. Now look how we went from 512 bits keys to 1024 bits ones.

No matter how much mathematics advance, we are still limited to processing power. Even if you figure an easier way to break a key, it still involves computing. So if you suddenly develop an alghoritm that makes it possoble to break a 2048 bits key in one minute, I'll just start using 4096 bits. I'll take whatever performance overhead that costs me, but your alghoritm will take eons to break the new key.

Again, back-of-napkin calculations have a brute force attack taking approximately 10^2045 (the numer one, followed by two thousand and forty-five zeroes) longer to break a 4096 bits key than a 2048 one. I may be a little off there, but the amount of zeroes will be close enough to give you an idea.

Okay, I expect your attack to be a non-brute force one, which scales more favorably than that, but even then, scaling the key up may make any attacks unfeasible for a long while - until better processors are developed, and anoter math genius comes up with another, clever method of encryption breaking.

$\endgroup$
  • $\begingroup$ Your answer is based on incorrect assumptions. Your basic assumption -- that the difficulty of a brute-force attack scales exponentially with key length -- holds for algorithms where the key has no inherent structure. That's often (but not always) the case with symmetric encryption algorithms, but it is decidedly not generally the case with public-key encryption algorithms. A RSA key, owing to its semiprime nature, has significant internal structure that allows far better attacks than brute force on the public key directly. Compare keylength.com. $\endgroup$ – a CVn Jun 19 '16 at 13:59
  • 1
    $\begingroup$ That order-of-magnitude argument is true for brute-forcing (or any other exponential-time algorithm). However if a polynomial-time algorithm is found, that argument breaks down. $\endgroup$ – celtschk Jun 19 '16 at 14:00

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