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."
> 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.
You are thinking of One time pads
The only encryption theoretically unbreakable.
Free XBox, PS2
"In short, his method would allow really [really-really] fast code breaking using quantum 'computers'."
AFAIR the best known quantum algorithm for breaking conventional crypto merely reduces search time to about its square root. So increase your key length from 128 to 256 bits, and it will take about as long to crack a key as a current computer would for a 128-bit key.
This is one reason why most new crypto algorithms have 256-bit keys rather than 128-bit.
Since those are the areas in which most people encounter encryption, that's what the author was focusing on.
On the other hand, the author also didn't give any reason to think that P?=NP is even coming closer to being resolved, and certainly no reason to think that it will end up being P=NP...so I don't see how PKE is threatened, either.
It's a non-story, if you ask me. Not that anyone did.
Reality has a conservative bias: it conserves mass, energy, momentum...
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.
If by "prime-based" you're talking about deriving prime factors for things like RSA public keys, then the machines have been invented - they just haven't been built yet. Shor's Algorithm allows a quantum computer to factor numbers extremely rapidly, which breaks RSA quite badly. This is due to the nature of factoring, not of quantum computing itself - no quantum computing algorithm _presently_ known can break discrete-log encryption in less than the square root of the number of steps a classical computer would take to do it, for example. However, only time will reveal which algorithms are vulnerable to QC and which aren't.
Quantum computers with enough qubits to do useful RSA public-key factoring will probably be built within about 10-20 years, based on the progress to date. Possibly earlier, but I'm going to be conservative and hedge a bit.
Yes, but there's a reason P=NP is of particular interest for crypto problems.
NP problems as a category are easy to check answers, but hard to compute those answers. So a whole category of challenge-response systems are possible. I use the easy (checking) side of the NP problem and make codebreakers use the hard (computing) side.
For example, it's hard to factor large composite numbers, but easy to check if a set of primes multiplies out to that number.
Sure, there are plenty of other categories of crypto, but they're harder to deal with. One-time pads are hard to distribute, and quantum mechanical stuff isn't ready yet. But public-private key cryptosystems are based on computations like factoring: it's easy to encrypt something based on the large composite number, but harder to decrypt it unless you have the factors at hand. So I can distribute the large composite number (so anybody can send secret documents to me), and be fairly sure nobody will break the crypto.
Unless P=NP, in which case factoring the number will also be easy, and we'll have to resort to something smarter, like quantum crypto (assuming it can be made to work practically).
It's really sad how many people keep bringing up this "well, it could be undecidable" line.
Firstly, the halting problem is trivially decidable for any particular program, the program either halts or it doesn't. There is no mystery here, it is just impossible to write a program that will *check* whether an *arbitrary* program will halt or not. There is no magical program that will do both or neither, this is because programs halt or they do not. The undecidability of the halting problem demonstrates the limitations of computers, not the limitations of mathematicians.
Similarly, it's trivially decidable whether a particular program is in P or NP. It's either true or false.
Returning back to the topic P=NP is either true or false. It's a matter of set equality:
1) Let P denote the set of all programs in P
2) Len NP denote the set of all programs in NP
3) compare the two sets, there are only two possible outcomes, since P is in NP
a) there is a program in NP which is not in P, then P is not equal to NP
b) there isn't, then P=NP
It's as simple as that. And when I say program, I mean program: that means you can choose whichever formalism you want, as long as it's turing complete: this includes C, Java, Perl and whatever else you want.
Unfortunately, this fallacy persists because people just do not understand Godel. I even read a book about the Riemann Hypothesis recently where some serious mathematicians were quoted as saying that the Hypothesis could be undecidable... bullshit.
Well, since he's a graduate student at MIT, I'll wager he has.
"Garfinkel holds three degrees from the Massachusetts Institute of Technology and a masters of science degree from Columbia University. He is a member of the Association for Computing Machinery (ACM), Computer Professionals for Social Responsibility (CPSR), and has a certification in computer security (CISSP) from International Information Systems Security Certifications Consortium."
Ironically, the word ironically is often used incorrectly.
Yeah, it's not a great article, though I do welcome the opportunity to broaden peoples' mathematical horizons. Still.
He starts off making it sound like P?=NP could be resolved soon in favor of P=NP, but Adelman says we aren't any closer to solving it than we were in the 70's, and the only one the author quotes as saying a solution may be imminent predicts that it will be shown that P != NP (the answer i think most mathematicions expect).
There's a lot more than just encryption riding on the answer (and as you say, encryption not so much) as tons of useful algorithms would go from intractable (exponential) to tractable (polynomial), and that's why people have been looking at the problem for so many years. Without success.
The enemies of Democracy are
Actually, the article's not all that bad.
Two problems: in his explanation of "P", the author says that P-time algorithms consume an amount of time proportional to the input size. That's way incomplete. P-time problems consume time proportional to some polynomial function of the input size, such as O(n^2), O(n^3), O(n^100), in addition to just plain O(n).
The second problem is where the author states that fast solutions to NP-complete problems would open up vulnerabilities to "hackers and viruses". Well, I'm not up on the latest virus developments, but AFAIK most viruses exploit known vulnerabilities rather than trying to crack algorithmically hard problems. Maybe there's some subtle way a virus could use a powerful P-time factorizer, but I think the author really just stated "hackers and viruses" because it sounded nice.
The article's also incomplete, as other posters have pointed out, because plenty of P-time algorithms are useless for real attacks. If your algorithm takes (1000 years) * (n^1000), where "n" is the key length, that is polynomial time, but it's still too damn long.
I've seen much worse in the trade press.
The continuum hypothesis is undecidable in certain versions of set theory. Why couldn't the Riemann hypothesis be undecidable too?
My understanding of Gödel is that in any sufficiently strong system of axioms there will always be statements that are neither provable nor disprovable. That is: there is a statement S such that S isn't provable and the negation of S isn't provable.
Is my understanding of Gödel wrong?
A quantum computer trying to break a OTP is equivalent to choosing the right message from all possible messages with the same length. In other words: Without knowing the pad, tell me if "ghwf0oclw" decrypts to "Star Trek" or "Star Wars".
Firstly, the halting problem is trivially decidable for any particular program, the program either halts or it doesn't.
;-)
Sorry, you are wrong here. Yes, if you ran a program and it stopped you know your answer. But if the program is still running, how would you know if it will eventually halt or not? And if it is one of those programs that do *not* halt, you'd have to wait for infinite amount of time to declare it "non-halting".
As to your solution of "comparing P and NP sets" -- I think you are slightly trolling here!
Paul B.
There's no mathematical proof, but consider this: a lot of problems have been shown to be NP complete. That is, if they can be solved quickly (in polynomial time), every NP problem can also be solved quickly (in polynomial time).
Some of these problems would make you a very, very rich person if you came up with a way to solve them quickly.
Nobody has.
That's enough evidence for every-day use, IMO.
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)
Additionally it should be noted that there are many complexity classes other than just P and NP, and there are many X such that X > P and X > NP.
True, but, in general, NP problems are really ideal for lots of cryptographic applications. The essence of the NP class is that it is the set of decision problems that are "easy" to solve given a particular piece of information and hard to solve otherwise. If I can be loose with terminology, an NP problem is a problem whose answer can be verified in polynomial time, but can only be found (as far as we know), in greater than polynomial time.
(BTW, I know the definition of NP as "non-deterministic polynomial", and what that means. The explanation I've given is equivalent, and easier to apply).
If P=NP, then all problems whose answers can be verified in polynomial time can also be solved in polynomial time. Of course, the polynomials in question could still make verification practical but solution impractical -- which is what we need for a useful public-key crypto algorithm. Or we could look to classes of algorithms of higher complexities, as you suggest, we'd have to find problems whose verification effort, although non-polynomial, was sufficiently low but whose solution effort was enough greater.
The really nice thing about NP is that when you increase the key size you're increasing the verification effort a small amount (it's pretty much linear with key size for the problems we use) and increasing the solution effort a large amount (as far as we know it's roughly exponential with the problems we use). This means that increased computing power always benefits the crypto user and hurts the attacker... because each increment of additional computation the crypto user chooses to perform creates a vastly larger amount of work for the attacker. The difference between linear and exponential is ideal.
None of this means that, in practice, algorithms base on decision problems in P, or EXP, or NEXP may very well be useful. But NP has a perfect structure, if it exists.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
While we are on the subject of P = NP here, there remains no proof either way that P = NP or that P != NP. However, a very large body of experimental evidence and related proofs tends to suggest that it is almost certain that P != NP. Many computer scientists are prepared to bet heavily on this outcome considering its near certainty. The threat to cryptography from quantum computing does not, as mentioned by Ckwop, have anything whatsoever to do with the computational complexity of the problem, but rather with the ability of quantum computers to try many solutions simultaneously, thus resulting in a much higher computational throughput. In effect the brute force attack is sped up by orders of magnitude and becomes feasible with today's algorithms and key sizes. However, the paranoid among us need not fear the death of encryption since quantum computing also makes possible new types of cryptography which are not based upon the asymptotic complexity of finding the solution to a problem. Even if all else fails we will always have the one time pad which is completely unbreakable (when proper pad discipline is observed) albeit somewhat cumbersome in practice.
i took ron rivest's crypto class my senior year at MIT and simson was the TA (one of two TAs actually). oh man, is this guy high on himself! he might be the most condescending person i've ever talked to and the worst part is that he doesn't even seem to realize it. he has crazy articles in techreview all the time and sometimes it just seems like he is fishing for "a good idea."
all in all, i know he's a sharp guy, but i think sometimes his ambition wins over his better judgement.
that P=NP. Of course some of them are. But almost every other mathematician with at least three brain cells is reasonably convinced of the opposite. The article covers the "consequences" of P=NP that anyone who's read an introductory text already understands, but fails to mention that a single NP-complete problem inside P is about as likely as finding a number without Goldbach property. It's just silly sensationalism for the sake of ... um, something about uninformed people that starts with 's'.
It's not about bounded vs. unbounded, it's about polynomial vs. exponential (or worse). Problems in P can be solved in polynomial time.
You're right that you can brute force an answer. But that will require trying all 2^128 keys (in this case). So you can see that the amount of work you have to do will grow exponentially with the input.
I'd rather be lucky than good.
True randomness does exist, it's all around us.
You are probably thinking "If we just knew everything about the starting conditions, we could predict the outcome."
In this universe, however, you CANNOT know the starting conditions to an infinite degree of accuracy. I don't mean "it's difficult" or "we can't do it with today's technology" but that it's fundamentally not possible. No state exists whereby you can know waht you would need to know. Such predictions are not possible.
You can say we don't know enough about quantum mechanics yet or whatever.. but look at something as simple as the Heisenberg uncertainty principle: you cannot know the speed and location of a particle at the same time. The more accurately you know one, the less you know of the other. This coupled with chaos theory means things really are random.
You are correct in that some things can be predicted.. we COULD measure enough about a roulette wheel to predict with a high degree of accuracy what is going on.. same with a coin toss. But look at something like nuclear decay, for instance... and we will NEVER be able to predict when a given atom is going to decay... it's buried in the quantum noise and in the uncertainty principle.
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.
You're absolutely right. Except for the "very hard" part.
It costs about a hundred bucks to buy a good (secure) random number generator. Noisy diodes, for instance, work great. Hell, taking photos of lava lamps works, too.
QRNG
SafeXcel
VIA C3 RNG
Education is the silver bullet.
Okay, I haven't actually proven that proving P=NP is an NP-complete problem. I have proven, however, that if you did have a proof that proving P=NP is an NP-complete problem, then verifying its correctness would be easy. Unfortunately this posting is too large to hold the proof.
No no no no no no! Your first sentence is wrong! See Wikipedia's complexity article
In any case, we could use a problem with, say, exponential complexity (in particular, not in NP) such that the reverse is also exponential, but with a larger exponent, such that it would still be exponentially easier to encode than to decode.
I have time to kill, am very interested in theoretical CS, and am a karma whore. Therefore I will now explain P vs NP in detail, in case anyone wants an explanation. I used this article to verify some of the fine points.
P and NP are classes of decision problems: problems in which you are presented with an input and must say "yes" or "no". For example, "Is this a prime number?" and "Is there a path from A to B on this graph (network)?" are decision problems.
A problem is in P if you can write a computer program to solve it in "polynomial" time. What that means is this: you give me a program, a polynomial (like 3*n^3) and a starting number m. Whenever your program is given an input, it must say "yes" or "no" within 3*n^3 time units. If the program you gave always gives the right answer in 3*n^3 steps (or whatever the polynomial was) for *any* input that's n symbols long, where n>=m, then the problem is in P. If no program and polynomial exist that satisfy this, then the problem is not in P. It's hard to prove that a problem is not in P, because you have to prove that no program at all can solve it.
NP is a bit more complicated. The definition is essentially the same as for P, except the program runs on a very strange kind of computer. One way of thinking of it is that it has a magic coin. Any time the program wants, it can flip the magic coin and decide what to do according to the whether the coin shows heads or tails. For example, if the computer wants to check if a number is composite (not prime), it can flip the coin a whole bunch of times to get the digits of a possible factor of the program. Here's the really confusing part: when you run the program, the computer actually tries every possible sequence of coin flips. If there is at least one sequence of flips that would get the program to say "yes", then the computer says "yes". If every single sequence says "no", then the computer says "no". So if the program wants to check if a number is composite, all it needs to do is flip the coin a few times to get a possible factor, and say whether that factor divides the number. If the number is composite, then at least one sequence of flips will generate a factor and the program will say "yes". NP stands for "non-deterministic", which is a good description of the weird computer.
A problem is in NP if the weird computer can solve it in polynomial time. Note that every problem in P is also in NP: if a normal computer can solve it without a magic coin, then so can the NP computer.
The question P=NP is the following: can every problem that can be solved in polynomial time on the weird computer also be solved in polynomial time (possibly with a larger polynomial) on a normal computer?
Two more definitions:
I hope I didn't just confuse you more... just read the wikipedia article if this doesn't help.
Each language has its purpose, however humble. -- The Tao of Programming
As many of his other repliers already pointed out, parent mixed up the NP and NPC (NP-complete) classes. Factoring is in NP. On the other hand, it is very-very unlikely that it is NP-complete (more precisely NP-hard), because this would imply that NP=co-NP.
What does NP=co-NP mean, you ask? You can consult http://en.wikipedia.org/wiki/Co-NP for the details. But the important point is that it is just as unlikely as P=NP.
(1) The terminology is misleading. The author speaks of "NP problems" without further qualification, and calls these problems "hard problems". NP problems, in the sense of problems belonging to the complexity class NP, however, are not "hard" in general, because all problems in P belong to NP (this is a trivial theorem). And no problem has been shown to be in NP but outside P. He might be referring to the so-called NP-hard problems, which formally are the problems at least as hard as the hardest problems in NP. But this wouldn't make much sense, since he doesn't bring up the NP-complete problems (the only NP-hard problems we know of inside the class NP) until the end of the article.
(2) Suppose P=NP. I, for one, would see this to be a good thing. The gain in the field of e.g. combinatorial planning and scheduling would be enormous, far outweighing any loss in the field of cryptography.
You seem to be missing some of the language nuances. A scientific theory can become a physical law though a large accumulation of evidence which is called a proof. So yes, scientist can "prove" things, insofar as as these terms are defined in the scientific method.
As for your thoery, "physics cannot prove things"... I think it is invalid. It seems to have a logical flaw in that does not appear to be falsifiable if you choose not to accept the large accumulation of evidence that defines a scientific proof.
See some of the definitions online...
Disclaimer: I am not a mathematician, so don't rely on this as advice when counting to ten.
Bluntly, no; it seems his understanding of the Reimann hypothesis is.
To be perhaps marginally more understandable, construction of the complex numbers requires the axioms for construction (and infinite inductive properties) of the Natural numbers, and axioms for construction of addition and multiplication. Complex powers require (briefly) the use of calculus, which merely requires adding axioms for how to take a limit into the mix.
The Reimann Zeta function of a complex number is the infinite sum of every integer when taken to the power of the additive inverse of the complex number being considered. The behaviors of this function (such as where it has zeros, as the Reimann hypothesis considers) are therefore only reliant on the axioms necessary for the above constructions. Proof of this is left as an exercise to the student. =)
Of course, proving this degree of axiomatic dependence rigorously is more than I am able to do. This is also left as an exercise for....
//Information does not want to be free; it wants to breed.
Primality testing is in NP. Every problem in P is in NP. What you meant was primality testing is not NP-hard.
Granted, but please understand that it has been several years since I last looked at this material in a university course on Algorithm Design and Complexity Analysis. That having been said, what I meant (and should have said) was the NP-C or NP Complete problems. It follows from the formal definition that:
A decision problem C is NP-complete if:
1) it is in NP and
2) every other problem in NP is reducible to it. Where reduction means that for every problem L, there is a polynomial-time many-one reduction, a deterministic algorithm which transforms L into instances of C, such that the answer to C is yes if and only if the answer to L is yes.
Sigh...formalisms are so tedious, but some people live for this sort of thing. Anyway, since NP-C is a subset of NP and NP overlaps P it follows that IF someone proves that P = NP then the problems in NP-C can be reduced so that they are equivalent to solving a problem in P which is bad for current cryptography methods for obvious reasons. My previous post was an honest mistake and I stand corrected.
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.
4-qbit q computers have already been built (as of 2002).
e akers.html#walterdaugherity
/., IBM built a 5-qbit computer in 2000.
(They can factor a 4-bit number.)
Not very useful, but a great demonstration.
These claims were presented by a Physics prof at DefCon 10.
http://www.defcon.org/html/defcon-10/defcon-10-sp
And, According to
Nothing to see here; Move along.
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".
Wikipedia (see here and here) and my Theory of Computation textbook disagree with you.
From Theory of Computing -- a Gentle Introduction:
Be careful: NP \ P != NP-complete.
A problem is only NP-complete if it is both in NP and in NP-hard. Many problems exist which we know are not P, but have not been able to show to be NP-complete.
In fact, according to this article, although we know that integer factorization is in NP, "[i]t is suspected to be outside of all three of the complexity classes P, NP-Complete, and co-NP-Complete".
Another interesting problem (not necessarily related to prime factoring) is graph isomorphism, which "seems to fall in a crack between P and NP-complete".
There's nothing stopping one from sending more than one "one time pad" through that initial secure channel ... Or for that matter, an agreement to use the King James Bible as a pad, starting at Exodus 9:3
Bzzzzzt. Wrong answer. The security of a one-time pad lies in the fact that the pad contains truly random data and that the pad is only used once. Pseudo-random number generators, or, worse, English text can NOT substitute for real random data. Read the first chapter of any cryptography text for more details. (Personally I recommend Schneier.)
Just record the random data, then as long as i have some idea of when you wrote the message, i'll just brute force it (if he encrypted it at 12:00 would it work, if not, 12:01, etc..)
Even if the data changed every ns it still wouldn't be very secure (assuming i have access to the sat signal)
Choose yer poison: Prophets or Profits
A "P" problem is a decision problem (a yes/no question essentially) that can be solved in polynomial time: Worst case for searching for a book in a finite collection is a multiple of the worst case time it takes to search one book in the house and the number of books - a straight linear search of all books in the house.
An "NP" problem is a decision problem where a solution can be verified in polynomial time. If P=NP then any problem where a solution can be verified in polynomial time can also be solved in polynomial time. Solving the problem here refers to finding the answer (is the book I seek in the house?) while verifying the solution refers to controlling that the answer is correct.
An P problem is also an NP problem - if you can solve a problem in polynomial time you can by definition also verify an answer in polynomial time: solve the problem, and compare the result with the proposed answer.
However the problem is that while it is thought that not all NP problems are also in P, it is not proven, and may be unprovable. But we don't know which, and don't have a simple way of verifying whether an NP problem is in P or not.
This is what sucks for encryption. Encryption currently rely on it being hard to solve a specific problem but easy to verify the solution (the key) by trying to decrypt an encrypted message, and if it fails (or presents us with gibberish) we know the key presented to us was not the right solution. This can be done in polynomial time
However, it only protects us because nobody (at least as far as we know) can solve the problems posed by the encryption methods in less than exponential time. Exponential time to solve the problem means that the effort could for instance (but not necessarily) double for each extra bit added to the key. The general rule is that the effort is 2^p(n) where p() is a polynomial function of n, and n is the size of the information space of the problem. The problem asked by encryption is essentially "will this key slotted into this encryption function give the original message?"
Let's go back to the book search, and twist it so that it fits the situation with encryption now. In the book search, the question is "does the book I seek exist in the house?". In a normal world, this problems worst case solution increases in effort by a constant factor for each extra book added, but to make it comparable to encryption we need to complicate the problem.
Imagine a crazy world where the best way we have to look for a solution to the book problem is to compare all the books with eachother and a paper strip with the title of the book we want, and only when we happen to compare the paper slip with the right book have we found the solution. In that case, each time we add a book, the problem increases (the number of direct relationships between n entities n(n-1), where n in this case would include the paper strip with the solution) but where we can still verify the final solution by comparing the book we finally found with the paper strip.
The kind of twisted scenario above is what most encryption algorithms are today: A problem that gives protection only because we don't know how to quickly solve it, but where there could be a simple way of solving them right around the corner. If P=NP all encryption algorithms that depend on this relationship can be broken in polynomial time.
However even proving that P and NP are not equal only means that "safe" encryption using this relationship is possible, not that current algorithms are safe - to prove that an algorithm is safe you'd need to separately prove that the problem can only be solved in exponential time. But a proof that P!=NP would give us an indication that it might at least be possible for such a proof to exist, as proving that the problem posed by an encryption algorithm can only be solved in exponential time would at the same time prove that P!=NP.