Slashdot Mirror
The End of Encryption?
An anonymous reader writes "The encryption algorithms that make virtually all electronic commerce possible work only because certain mathematical problems are very, very hard to solve. But some mathematicians are trying to prove that there's really no difference between 'hard' and 'not hard' problems--known in the math biz as P and NP. In an article on TechnologyReview.com, Simson Garfinkel spells out the real-world consequences of this mathematical conundrum."
No no no no no. How many more times? Cryptography has absolutely nothing to do with the question of P?=NP.
P?=NP refers to the asymptotic complexity as the problem. i.e. as the input size goes to infinity. It quite possible to have a problem whos complexity is approximately linear at the 100-1000-bit range and still NP-Complete. Conversely, it's possible to have a p-time algorithm for solving a problem that has a O(n^100) so it's still difficult to solve. While resolving P?=NP might bring new tricks to the table it's difficult to legislate for these tricks. There might not even be any we don't already know.
Another point, p?=np has no bearing on the security proof of the one-time pad or quantum mechanical key exchange. The latter will become practical over large distances to enable the former long before p?np is resolved. Cryptography will die when the last human draws its breath.
Simon.
Guvf jbexf whfg svar sbe zr!
Right is wrong when left is right.
... write 'Bridge over encrypted waters ~(__8-(0) Doh!'?
This is really quite simple - the type of machine that can render Prime-based and Discrete Log-based encryption "useless" has not been invented yet. Furthermore, as the article points out, most (including Adelman) belive it'll be a long time before one is.
The problem (P vs. NP) is still just as difficult, and we aren't really much closer to solving it than 10 or 20 years ago.
dmiessler.com -- grep understanding knowledge
Which is not exactly true. It could be true but not provable. It could be false but not provable. It could be provably true, or provably false. Or, it could be neither true nor false.
OTP will always remain a viable means of private key cryptography. When you interleave signal with noise, the result will always have the properties of noise.
It can well be argued that absolutely nothing is in fact random. From coin flips to roulette anything can eventually be learned and predicted on some level. The only point where I might even question this is with quantam states, and even there we really know precious little. It is simply too early to say one way or another on quantam.
So far as we know, P != NP.
And that's it. And I haven't seen a shred of evidence to the contrary.
Yes, the article is somewhat truthful, in that if P == NP, the world will have been turned on its head, but the same thing is true about thousands of scientific and/or mathematical assertions, each of which is more likely to be overturned than P != NP.
Ignoring the fact that the answer to P?=NP has little to do with breaking encryption for a moment, even if an NP computer is conceived and developed, it'll just lay down a *huge* plethora of computing possibilities at our disposal, including new encryption techniques.
Encryption cannot die, algorithms can.
An Indian-American Hindu committed to non-violent thought/speech/action alarmed by the global explosion of radical Islam
I saw a movie about this exact same thing. Luckliy Robert Redford and his team won and the world was made safe from Ben Kingsley, but it was touch and go there for a little bit.
I was worried.
The one way to tell for sure if the good guys win, is if the Republican National Committee goes bankrupt and GreenPeace gets a sizable donation. Also, you might see Sydney Poitier in Tahiti and Dan Akroyd in a brand spanking new RV.
--
Pain?
Try Prison.
> Or a quantum computer is made that can break all these passwords.
No. To put in plain language: there are forms of encryption more advanced than those that employ difficult math problems. Quantum computing does not pose a threat to a OTP system that employs quantum key exchange. Sorry.
I have discovered a truly remarkable proof which this post is too small to contain.
LongTail SSH Brute Force analysis tool is here!
Ask Slashdot dealt with this issue three years ago! When it comes to uninformed, idle speculation, this site is way ahead of MIT!
What I'm listening to now on Pandora...
Cryptography will die when the last human draws its breath. Er.... shouldn't that be third-to-last human?
Sometimes seventeen/Syllables aren't enough to/Express a complete
Quantum computing does not pose a threat to a OTP system that employs quantum key exchange.
In practice it may never pose a threat to symmetric ciphers, like AES, either. Those don't rely on hard math problems as much as on non-linearity and complexity. Quantum computers may someday be good at solving simple but hard problems, but it's likely they'll never be able to attack complex problems, easy or hard.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
The whole thing is a bunch of alarmist speculation.
"The market alone cannot provide sufficient constraints on corporation's penchant to cause harm." -- Joel Bakan
But some mathematicians are trying to prove that there's really no difference between 'hard' and 'not hard' problems
Well, it's always better to have the hard problem. You may have to seek medical attention, but at least your pride remains intact.
Bruce
Bruce Perens.
Bell-bottom pants aren't cool anymore? Man... what a bummer. I got to quit bogarting those roaches.
If you post it, they will read.
"50 Ways to Break Encryption"...
just calculate the key, Lee
hack the algorithm, Jim
reverse-engineer, Samir
sleep, what's that?
I'm surprised that Simson made this elementary mistake.
Factoring has *not* been proved to belong to either P or NP. It's an "open problem".
DNA is a Turing machine. You, however, being dynamic and emergent, are not.
I have a proof that proving P = NP is an NP-complete problem. Unfortunately this posting is too small to hold the proof.
Digital Fortress was a complete piece of shit. Please don't base anything off that rag. It was written with the express purpose of capitalizing off of Dan Brown's momentum being made into a movie. The "visuals" described fit Hollywood nicely -- meaning they have no basis in reality.
It is easy for a person to come up with an algorithm that THEY can't crack. Most are painfully obvious to outsiders with any experience.
Other than proper implementation of a one-time pad, you'll probably find any encryption will eventually fall.
Learning HOW to think is more important than learning WHAT to think.
P=NP
P/P=NP/P
1=N
Therefore, P=NP for all problems where N=1.
See, that clearly wasn't a NP problem!
Digital Fortress was a total piece of crap. While A moderatly interesting book, the crypto is totally wrong. The ONLY perfect encryption is a one-time-pad. If there is a key it can be broken. The whole "make it impossible to figure out it its really cleartext" is just a not-so-clever plot device.
Think about it this way, when you use PGP/GPG to encrypt something, it compresses the file first. The argument Dan Brown used was that when you try a key on this "unbreakable" crypto that you get garbage out and can't use the typical language statistics to figure out if the result is valid or not. If this was true, then any form of binary data would be impossible to decrypt.
A more mathish approach. The idea was to take a cleartext, M, run it through a "magic function" Z then encrypt that, or Encrypt(Z(M)). Well, a little digging will find that chained encryption doesn't buy much. Thats why AES is around, rather than using 3DES or 5DES. or nDES. All his digital fortress was doing was using two encryption methods. But, this just doesn't work.
Dan Brown doesn't think or do any research whatsoever before he writes a book. Virtually ALL of the crypto related information was WRONG. Skipjack was a problem, not because of any backdoor, but because it was only availible as a tamper-proof hardware chip, noone got to look at it. The Caesar cipher was an alphabetic rotation, not a geometric cipher. Hell, there simply isn't enough energy given out by a star in a year to power a machine capable of brute-forcing 256-bit encryption, schieder wrote an essay on it.
Under current theory, the ONLY perfect encryption scheme is a OTP.
Actually, it's problems solved in polynomial time vs non-deterministic polynomial time. Your two examples are both problems that can be solved in polynomial time.
It's not simple math. IE find two prime factors to a very very large number. Guesses are made to find the factors. But even though guesses are polynomial in amongst themselves, the number of guesses you need to make before you hit on a solution is non-deterministic. Thus it's NP (non-deterministic polynomial time).
by having a plaintext and cyphertext, a quantum computer can make it very trivial to find the key using certain iterative attacks on the algorithm. I mean, isn't the quantum computer "instantly" backtracking up until the substitution step of each round, as the operations would be reversible up until that point? I would think the complexity to crack is only dependant on the number of rounds.
There is no possibility to use a quantum computer to make simultaneous dictionary attack (guessing the key by trying all possible keys at the same time), because, contrary to what most people think, you can do only one usable computation at the same time on a quantum computer. The difference between classical and quantum computer is that you can 'tune' the quantum computer into doing this one computation which is important -- like the one needed to break the key. If you can do that, you've cracked the cipher. But it requires an algorithm specific to the cipher in question. A good defense before such attack would be to change the cipher in such a way as to make the corresponding quantum algorithm useless, and make attacker think really hard before coming up with another one. A bit more challenging than just increasing the key length.
IANAQCE (I Am Not A Quantum Computing Expert), but that's what I gathered from listening to seminars delivered by people from the field.
"Long run is a misleading guide to current affairs. In the long run we are all dead." (John Maynard Keynes)
If you think 2+2=4 is simple, then you haven't seen this!
I thought that all the public key (etc) systems relied on a "hard math problem" to produce the public-key secret-key pair.
Sort of. Actually, they rely on the hard math problem to make it so someone who knows the secret key can do something that someone who knows the public key cannot, and, potentially, vice versa. Generation of keys is simpler.
When I generate my DES and AES keys I go through that "mostly prime" exercise.
Umm, no. DES and AES don't care about primes, or factoring, etc., at all. The DES and AES keyspaces are (nearly) flat. To pick a DES/AES key, you just choose a random 56-bit/128-bit number. (I said nearly because DES does have some weak keys, so some people choose to avoid those).
So quantum computing should be able to do the "large nubmer factoring" exercise necessary to crack the key...
For public-key algorithsm like RSA, DSA, Diffie-Hellman, ECC (well, you don't use factoring to attack ECC, but same notion), etc., yes. For secret-key algorithms like DES, AES, IDEA, RC-4, Twofish, etc., no, there is no number factoring exercise or similar that will help. So probably not, which was my point.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
I think you would end up as a very, very dead person very very quickly if you publish a way to crack RSA in a very very short time.
Poor man was only two letters away from being a music sensation...
I'm sure he's never heard that before in his life.
The consequences are that I won't be able to safely browse Slashdot from work over an ssh tunnel without getting in trouble, anymore.
I've had secure, non-snoopable access to the Internet for my entire professional life. If I actually have to start working I don't think I'll be able to handle it.
What's the difference?
That's a tough one to answer concisely. The best way to see the difference is probably to look at the algorithms.
Symmetric ciphers work by doing a whole bunch of different operations, mixing and munging the data in complex ways, and doing it over and over again. In the case of DES, for example, there are 16 rounds. AES-128 uses 10 rounds. Each of the individual mathemetical operations are simple, easily reversible and weak, from a security standpoint. The strength is achieved by repeating them many times in particular ways to create an overall structure that is hard to break.
In contrast, public key ciphers, like RSA, consist of only a single mathematical operation, one that has useful properties. An RSA encryption operation just requires calculating m^n mod p. The operation is very simple and straightforward, but there's no known way to reverse it efficently without the private key.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
One important class of problems which should be included in this discussion is the class of P Complete problems.
These are problems for which there exists a polynomial time reduction to the P Problem, which is the ability to optimally distribute P straight pegs in U linearly arranged slots (where P less than or equal to U), so as to maximize the distance between pegs.
For example, for (P=2, U=5), the optimal solution is a peg at the first and last slots. For (P=3, U=5), optimal is U0, U2, U4, etc.
It can be shown that any problem which can be reduced in polynomial time to straight men at a row of urinals is P Complete.
"I thought they were the dominant species..."
If there is only one correct key, you can use the Grover algorithm to reduce the complexity to O(sqrt(N)). It first make a superposition of all possible N=2^n keys, then for each iteration the encryption algorithm is applied on it (simulataneously to all keys), yielding a "it is the right key or not" answer for each key, still superposed. Then a conditional 180deg-phase-shift operator and a "diffuse" operator is applied on the resulting superposed state, the result being that the eigenstate containing the correct key now has a larger weight than others in the superposed state, so that it has a higher probability to be observed when measured. By repeating the encryption-conditionPhaseShift-diffuse process O(sqrt(N)) times, the eigenstate containing the correct key will have a sufficiently large weight in the superposed state, and we can measure it and get the correct key with a high probability. So you see the encryption operation is always done simultaneously to every key, but you need to repeat the operation O(sqrt(N)) times to make the desired result strong enough to be measured.
Of course, the Grover algorithm is O(sqrt(N)), as opposed to O(N) of a purely brute-force attack, so just double the key length and you will be safe.
For references, google for "quprog.pdf".
Because factoring is not known to be NP-complete, there might turn out to be a polynomial-time algorithm for factoring, but no polynomial-time algorithm for NP-complete problems. If this were true, RSA might be broken, but other public-key algorithms might still be strong enough.