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."

Nope, wrong, invalid.. nothing to see here.

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.

Re:Nope, wrong, invalid.. nothing to see here.

These guys couldn't even figure out when the century began.

"There was a little bit of a controversy as to when the entry of the century was," he recalls. "Was it January 1, 2000, or January 1, 2001?

Come on now. They can't figure out that and we're looking to them to figure out the whole P=NP mess?

Re:Nope, wrong, invalid.. nothing to see here.

What you say is very true, but there are two big exceptions to note:
1) 1TP/QKE require as much storage/bandwidth for the key as for the message, and the key can never be resused. These are both severe drawbacks.
2) Crypto is useful for more than just hiding information. Digital signatures/integrity hashes are both very important and impossible to achieve -reuseably- with either of the schemes mentioned above.

Re:Nope, wrong, invalid.. nothing to see here.

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.

So even IF the P?=NP question applies, it doen't mean that cryptography itself is doomed. Just that harder problems might need to be used as the basis.

Re:Nope, wrong, invalid.. nothing to see here.

Also, if a P=NP proof was found it would not necessarily gives us a procedure for generating the P algorithm that solves the NP complete problem. This would be an unfortunate situation.

Re:Nope, wrong, invalid.. nothing to see here.

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.

"last human draws its breath"

Cryptography will die when the last human draws its breath. Er.... shouldn't that be third-to-last human?

Re:"last human draws its breath"

Actually, I'm thinking second-to-last really. As the third-to-last person on the earth, I may choose to encrypt a document entitled "How to kill Fred and Bill" so that that the other two may not access it.

-9mm-

Re:"last human draws its breath"

"How to kill Fred and Bill"

I humbly prefer killing Bill only. If I may.

Re:"last human draws its breath"

Unless any of them turns out to be Alice. Or Bob.

Re:Nope, wrong, invalid.. nothing to see here.

This article simply inflates that idea into a paranoia for the masses

Can't that be said for every article on /.?

Re:Nope, wrong, invalid.. nothing to see here.

This is why you use extremely long keys and strong algorithms. Use 4k RSA keys guys. It doesn't guarantee against attacks, but it does dramatically extend the time horizon. Even if there is a means of making factoring easier, it might not make it easy enough if the key is very big.

Make a key 10^10 as hard as the biggest one that can be broken (at least), and then only a very severe break will put you in danger.

Re:Nope, wrong, invalid.. nothing to see here.

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).

Factoring is not known to be NP-complete

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.

Re:Nope, wrong, invalid.. nothing to see here.

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.

Re:Quantum Computers / Shor's Algorithm

> 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.

Re:Quantum Computers / Shor's Algorithm

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.

Re:As I thought I understood it...

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.

the Grover algorithm

Actually a QC can do simultaneous computations by using superpositioned states, although getting the desired result out can be challenging.

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".

Re:Quantum Computers / Shor's Algorithm

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.

Re:Quantum Computers / Shor's Algorithm

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.

Who needs it?

Guvf jbexf whfg svar sbe zr!

Re:Who needs it?

That's not encrypted. That's in German!

w00t

Didn't that guy...

... write 'Bridge over encrypted waters ~(__8-(0) Doh!'?

Easy killer...

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.

Re:Easy killer...

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.

More than Just P=NP

"For more than 30 years, mathematicians have sought in vain the answer to a simple problem in theoretical computer science. The problem is what's known as an open question --it's a simple equation that is either true or false. It can't be both."

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.

Re:More than Just P=NP

Well, it could be proven to be theoretically undecidable like the halting problem, couldn't it? Then I guess it would be true or false, but nobody would ever know so it's all semantics.

Re:More than Just P=NP

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 always OTP

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.

Re:Ha!

If you think 2+2=4 is simple, then you haven't seen this [metamath.org]!

Could be argued

Could be argued, for that matter the entire concept of "random" is truely just a human thought construct. Since crypto is heavily dependent upon the concept of random, this will become a bigger problem as time goes on.

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.

Re:Could be argued

Randomness is not a human construct, I am not sure where you are getting this idea from. There are certain events that are PROVABLY unpredictable, e.g. radioactive decay and certain quantum effects.

Wrong. Sorry. Physics cannot prove things. They can only show that things are very likely and they can have theories that predict things. Often this works, but from time to time it fails. All physical deductions relating to reality are derived from experiments. Experiments are allways imprecise and frequently deliver wrong results.

Ask any physicist. They know that they just have a best guess, but no hard facts.

Re:Could be argued

By "prove" we mean to some disgusting (like 20) number of sigma. The odds of us all dying of a stroke on the same day is greater than the odds of us being wrong about that.

The odds aren't ever zero, but they're usually close enough.

Re:Could be argued

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.

Even in a purely classical universe, sensitivity to starting conditions makes things like coin tosses and die rolls impossible to predict if set up carefully. This is that whole "chaos" topic you may have heard about in the press in the 1980s. You'd have to have excruciatingly accurate knowledge of the state of everything in the past light-cone of the event you're trying to predict, as of the time of prediction, for it to work with perfect reliability.

In our quantum universe, the uncertainty principle makes it impossible even in principle to measure starting state to the required precision, for the schemes that are used for true random number generation in electronic systems. Additionally, if quantum processes are accepted as truly random, they inject enough noise to taint macroscopic events with true randomness if the consequences of the noise are given enough time to propagate.

In summary, true randomness exists as a very fundamental result of the laws of nature, and won't go away no matter how good our measurements get.

Re:Could be argued

The only point where I might even question this is with quantam states, and even there we really know precious little.

Uh, sort of. Heisenbergs uncertinty principle can be read as "We can never know the details" of quantum states. If it is true, then it does not matter whether or not a quantum state could be determanitsic if we can measure the things we need to determine it.

Now, there is an awful lot of discoveries and technology that have been predicated on Heisenbergs principle being true (or, at least, true enough, for some value of enough) [0]. Thus, the burden of proof is heavily on the side of anyone claiming that it's not valid (just as it is for anyone claiming Einsteins relativity is wrong, and as it was for Einstien when he showed Newton was wrong [1]).

So, I refute your claim on 'It's too early', by Schottky diodes, Mossbauer spectroscopy and quantum computing, which all rely on quantum states having true randomness [2].

Furthermore, by the way, there was a bunch of work on something called the Bell inequality, which, although painfully esoteric in testing, has disproved the existance of hidden variables. That is, it is _not_ the case that quantum states are deterministic, by data we can't measure. There are no such hidden bits of data.

Moreover, pretty much every macroscopic physical observable is a statistical average of very many microscopic states or events. These microstates are randomly distributed within some known distribution (e.g. disribution individual molectular kinetic energies for a given temperature of a set of particles). The various physical laws that we depend on (in the case of temperature, the predicability of the increase in the rate of some chemical reaction with increasing temperature, for example) have the concept of this random disribution so inherent in them, that I must argue that if 'random' is a a human thought construct, it is fortunate that the laws of nature also think that way (i.e. random is a physical concept)

Such is the opinion of this quantum physicist, at any rate.

[0] E.g Mossbauer spectroscopy
[1] Strictly, Newton was farsighted enough to state his basic assumptions expcitly. Einstein just showed that one of them ("Time is the same for all men") was incorrect, and the consequences of it.
[2] Or, at very least, something that is indistinguisable from it.

It's still a "what if" piece...

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.

Another magical no more secrets box

When will people learn that as long as people have secrets to keep they'll find ways of keeping them? There may be advances in technology which will render certain methods of keeping the secret obsolete, but this search for a magic algorithm is silly.

I imagine one day there may be an advance that will mean a total security overhaul will be required though, and that could provide a window of chaos in the most extreme circumstances. However every advance in decryption tends to quickly lead to an advance in encryption that can beat it. At least historically that's been the way it is.

Until they can literally read the contents of my brain, I'm not too worried.

All he does is explain P and NP

and ponders over whether the recent MD5 news from the Mathematics conference (in an earlier /. story today) will lead to any discoveries that may help answer whether 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.

I saw this movie

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.

I have discovered...

I have discovered a truly remarkable proof which this post is too small to contain.

Get with the times!

Ask Slashdot dealt with this issue [slashdot.org] three years ago! When it comes to uninformed, idle speculation, this site is way ahead of MIT!

The article sums it up best

Adelman thinks that we'll be waiting for the solution for a long time. Resolving the question of P and NP, he says, "would require new and brilliant ideas and not routine incremental progress. From my perspective, we are no nearer to solving the problem now that we were when bell-bottom pants were cool."

The whole thing is a bunch of alarmist speculation.

This is Crazy

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.

It's not "the end of encryption" at all

You mean public-key encryption . I fail to see how the one-time pad would be effected by new ways to solve NP-hard problems.

Bruce

Re:It's not "the end of encryption" at all

True, but OTPs aren't reusable, and the key needs to have as much information as the message, so they're not an answer to digital signatures or secure transactions online. Or at least, not an answer that's easy enough for me to comprehend.

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.

Re:It's not "the end of encryption" at all

True, but OTPs aren't reusable

OH MY GOD, THEY'RE NOT???

Out of fashion, I guess.

"From my perspective, we are no nearer to solving the problem now that we were when bell-bottom pants were cool."

Bell-bottom pants aren't cool anymore? Man... what a bummer. I got to quit bogarting those roaches.

My favorite Simson Garfinkel work

"50 Ways to Break Encryption"...
just calculate the key, Lee
hack the algorithm, Jim
reverse-engineer, Samir

sleep, what's that?

Factoring is another NP problem -- NO!

Factoring is another NP problem.

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".

I have a proof

I have a proof that proving P = NP is an NP-complete problem. Unfortunately this posting is too small to hold the proof.

Re:Hard and tedious are different things

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).

This is silly

How hard is this?

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!

Why P!=NP

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.

Re:Why P!=NP

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.

Simson Garfinkel

Poor man was only two letters away from being a music sensation...

I'm sure he's never heard that before in his life.

I'll Tell You What The Consequences Are

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.

Re:Sound of Silence

As one would say to Mycroft in The Moon is a Harsh Mistress, that's a "funny only once" joke...and the "once" was probably decades ago.

Re:Yep, its doomed.

"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.

Re:Eventually

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.

Re:Mandatory

Well, since he's a graduate student at MIT, I'll wager he has. [simson.net]

"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."

Re:Mandatory

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.

Re:Eventually

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.