4 ms·

If there is some kind of connection between prime numbers, wouldn't a lot of the current work in encryption be thrown out?

lutusp 14y ago
> If there is some kind of connection between prime numbers, wouldn't a lot of the current work in encryption be thrown out? Unlikely. The recent work doesn't improve our ability to factor large integers, the key to modern cryptography. If someone created a function that instantly produced the prime factors for large integers without the present difficult process, that would change everything, but that's not a likely outcome. The next real challenge to modern cryptography isn't this work, but quantum computing. If quantum computing came to full flower with no obstacles sometime in the future, that would represent a basic change because it would perform an end run around the present computational difficulties that assure the security and reliability of our present methods.
- thebigshane 14y ago
  Ok, off topic, sorry, but... Are you saying that if/when quantum computing comes around, existing encryption systems would be suddenly ineffective? So if the NSA gets their hands on a quantum computer, they'd be able to brute force a 1024bit RSA encrypted file in far quicker time than their other super computers? I found some info here, but I didn't get enough out of it to answer my question directly. I think the answer is "Well theoretically, but it's complicated": http://stackoverflow.com/questions/2768807/quantum-computing-and-encryption-breaking http://stackoverflow.com/questions/2768807/quantum-computing... http://en.wikipedia.org/wiki/Quantum_computer#Potential http://en.wikipedia.org/wiki/Quantum_computer#Potential http://en.wikipedia.org/wiki/Shor%27s_algorithm http://en.wikipedia.org/wiki/Shor%27s_algorithm http://en.wikipedia.org/wiki/Post-quantum_cryptography http://en.wikipedia.org/wiki/Post-quantum_cryptography [...] most currently popular public-key cryptosystems rely on the integer factorization problem or discrete logarithm problem, both of which would be easily solvable on large enough quantum computers using Shor's algorithm. Even though current publicly known experimental quantum computing is nowhere near powerful enough to attack real cryptosystems, many cryptographers are researching new algorithms, in case quantum computing becomes a threat in the future.
  - jgeralnik 14y ago
    Yes. The naive algorithm for factorization runs in O(2^N) (where N is the number of bits in the number you want to factorize), which is impractical for any sufficiently large N (2^64 > 10^19, 2^1024 > 10^328 which is BIG). There are better known algorithms, but none of them are polynomial, so a bruteforce is highly impractical. Shor's algorithm, on the other hand, runs in O((logN)^3). For an idea of the difference, log(64)^3 = 216, log(1024)^3 = 1000. So Shor's algorithm could be used to very quickly factorize large numbers and would effectively break RSA. We just need a quantum computer, which as far as we know nobody has yet.
    - thebigshane 14y ago
      Ok, thanks. But when I start hearing conspiracy theories that the NSA (or anyone) has already developed one, I should basically look for an encryption algorithm that isn't based on prime factorization?
      - jgeralnik 14y ago
        Encryption algorithms exist and are being developed which are not based on prime factorization and for which no known quantum algorithm exists which can break them in polynomial time. There will probably be significant warning before quantum computers exist which can break RSA. In that time it will probably become the norm to no longer use algorithms which are rendered obsolete by quantum computers.
  - lutusp 14y ago
    > Are you saying that if/when quantum computing comes around, existing encryption systems would be suddenly ineffective? Yes, but it's a big "if". There are many obstacles that stand in the way of quantum computing on a large scale, in fact some believe it will never be possible to maintain the delicate conditions required to perform quantum computation on a large scale. The reason quantum computing could outperform conventional computation is because a quantum computer would, in a manner of speaking, process all possible problem statements at once, in parallel, and arrive at the best solution just as though only one problem statement had been processed. I know that may be difficult to imagine, but so is quantum. About quantum theory, John Wheeler said, "If you are not completely confused by quantum mechanics, you do not understand it." Suffice it to say that quantum computing on a scale sufficient to pose a threat to public-key cryptosystems is not just around the corner.
- dchichkov 14y ago
  It is funny, but AFAIK there is no established lower bound on the complexity of factoring problem. Even in the realm of classic computation. Anecdotally - Ron Rivest estimated in 1977 that factoring a 125-digit number would require 40 quadrillion years. RSA-129 was solved in 1994. RSA-768 in 2009.

lutusp 14y ago

> If there is some kind of connection between prime numbers, wouldn't a lot of the current work in encryption be thrown out? Unlikely. The recent work doesn't improve our ability to factor large integers, the key to modern cryptography. If someone created a function that instantly produced the prime factors for large integers without the present difficult process, that would change everything, but that's not a likely outcome. The next real challenge to modern cryptography isn't this work, but quantum computing. If quantum computing came to full flower with no obstacles sometime in the future, that would represent a basic change because it would perform an end run around the present computational difficulties that assure the security and reliability of our present methods.

thebigshane 14y ago
Ok, off topic, sorry, but... Are you saying that if/when quantum computing comes around, existing encryption systems would be suddenly ineffective? So if the NSA gets their hands on a quantum computer, they'd be able to brute force a 1024bit RSA encrypted file in far quicker time than their other super computers? I found some info here, but I didn't get enough out of it to answer my question directly. I think the answer is "Well theoretically, but it's complicated": http://stackoverflow.com/questions/2768807/quantum-computing-and-encryption-breaking http://stackoverflow.com/questions/2768807/quantum-computing... http://en.wikipedia.org/wiki/Quantum_computer#Potential http://en.wikipedia.org/wiki/Quantum_computer#Potential http://en.wikipedia.org/wiki/Shor%27s_algorithm http://en.wikipedia.org/wiki/Shor%27s_algorithm http://en.wikipedia.org/wiki/Post-quantum_cryptography http://en.wikipedia.org/wiki/Post-quantum_cryptography [...] most currently popular public-key cryptosystems rely on the integer factorization problem or discrete logarithm problem, both of which would be easily solvable on large enough quantum computers using Shor's algorithm. Even though current publicly known experimental quantum computing is nowhere near powerful enough to attack real cryptosystems, many cryptographers are researching new algorithms, in case quantum computing becomes a threat in the future.
- jgeralnik 14y ago
  Yes. The naive algorithm for factorization runs in O(2^N) (where N is the number of bits in the number you want to factorize), which is impractical for any sufficiently large N (2^64 > 10^19, 2^1024 > 10^328 which is BIG). There are better known algorithms, but none of them are polynomial, so a bruteforce is highly impractical. Shor's algorithm, on the other hand, runs in O((logN)^3). For an idea of the difference, log(64)^3 = 216, log(1024)^3 = 1000. So Shor's algorithm could be used to very quickly factorize large numbers and would effectively break RSA. We just need a quantum computer, which as far as we know nobody has yet.
  - thebigshane 14y ago
    Ok, thanks. But when I start hearing conspiracy theories that the NSA (or anyone) has already developed one, I should basically look for an encryption algorithm that isn't based on prime factorization?
    - jgeralnik 14y ago
      Encryption algorithms exist and are being developed which are not based on prime factorization and for which no known quantum algorithm exists which can break them in polynomial time. There will probably be significant warning before quantum computers exist which can break RSA. In that time it will probably become the norm to no longer use algorithms which are rendered obsolete by quantum computers.
- lutusp 14y ago
  > Are you saying that if/when quantum computing comes around, existing encryption systems would be suddenly ineffective? Yes, but it's a big "if". There are many obstacles that stand in the way of quantum computing on a large scale, in fact some believe it will never be possible to maintain the delicate conditions required to perform quantum computation on a large scale. The reason quantum computing could outperform conventional computation is because a quantum computer would, in a manner of speaking, process all possible problem statements at once, in parallel, and arrive at the best solution just as though only one problem statement had been processed. I know that may be difficult to imagine, but so is quantum. About quantum theory, John Wheeler said, "If you are not completely confused by quantum mechanics, you do not understand it." Suffice it to say that quantum computing on a scale sufficient to pose a threat to public-key cryptosystems is not just around the corner.
dchichkov 14y ago
It is funny, but AFAIK there is no established lower bound on the complexity of factoring problem. Even in the realm of classic computation. Anecdotally - Ron Rivest estimated in 1977 that factoring a 125-digit number would require 40 quadrillion years. RSA-129 was solved in 1994. RSA-768 in 2009.