The End of Encryption? 633
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. (Score:5, Insightful)
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. (Score:4, Funny)
"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. (Score:3, Funny)
Sweet! My credit card payment isn't late afterall!
Re:Nope, wrong, invalid.. nothing to see here. (Score:5, Insightful)
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. (Score:5, Insightful)
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. (Score:3, Interesting)
Re:Nope, wrong, invalid.. nothing to see here. (Score:3, Insightful)
I wouldn't go so far as to say that. The pad has no bearing on the message sent aside from the ability to decrypt it, so you send the OTP via quantum-encrypted channels and verify its integrity at the recipient end. If the pad has not been comprimised *then* you send an OK (via the same quantum-encrypted channel, just in case) to recieve the encrypted message. This gives you one extra layer of secu
A bit OT, but no less interesting point... (Score:3, Interesting)
It is by having a satelite system, like the GPS system, constantly broadcast synchronized truly random data. That way, any two recipients can communicate as much data as they want by simply synchronizing their communication to a certain time, and using the one time pad that's being broadcast by the satelites at that point in time.
Now, this turns the one time pad bandwidth issue int
Re:Nope, wrong, invalid.. nothing to see here. (Score:3, Informative)
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
Re:Nope, wrong, invalid.. nothing to see here. (Score:5, Interesting)
Re:proof of P=NP without supplying an algorithm (Score:3, Interesting)
Well, it could be a contrapositive-type of proof. Show that if there is no algorithm in P which solves a certain NP-hard problem, then there is a P algorithm which solves a problem in EXPTIME or something like that. (It is known that P != EXPTIME.)
However, we are now pretty sure that the problem will never be settled. The
Re:Nope, wrong, invalid.. nothing to see here. (Score:4, Informative)
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.
P Complete (Score:3, Funny)
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 b
Re:Nope, wrong, invalid.. nothing to see here. (Score:3, Informative)
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 reduct
"last human draws its breath" (Score:5, Funny)
Re:"last human draws its breath" (Score:5, Funny)
-9mm-
Re:"last human draws its breath" (Score:4, Funny)
I humbly prefer killing Bill only. If I may.
Re:"last human draws its breath" (Score:5, Funny)
Re:"last human draws its breath" (Score:3, Insightful)
Re:"last human draws its breath" (Score:3, Funny)
Re:Nope, wrong, invalid.. nothing to see here. (Score:3, Insightful)
* I'm deliberately leaving 'difficult' undefined to dodge abuse from the language lawyers.
I've always wondered what would happen if some 15-year-old math wiz who is playing around in Mathematica comes up with a novel approach to facto
Re:Nope, wrong, invalid.. nothing to see here. (Score:4, Funny)
Can't that be said for every article on
Re:Nope, wrong, invalid.. nothing to see here. (Score:3, Insightful)
Jedidiah
Re:Nope, wrong, invalid.. nothing to see here. (Score:4, Interesting)
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. (Score:5, Informative)
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 (Score:5, Insightful)
Re:Nope, wrong, invalid.. nothing to see here. (Score:5, Informative)
Re:Nope, wrong, invalid.. nothing to see here. (Score:3, Interesting)
On the contrary, a real (see rules below) one-time pad is truly the only unbreakable cryptosystem. Without access to the key, no amount of brute-forcing or analysis will ever recover the plaintext.
OTP could partially be helped by using commonly available documents, images, binaries, whatever as the pad, but then you increase the chances of someone else finding the pad, and you still have to store an index of which document uses which pad somewhere.
People
Re:Quantum Computers / Shor's Algorithm (Score:5, Informative)
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 (Score:5, Interesting)
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... (Score:5, Informative)
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.
Quantum Chosen-Plaintext Attack ? (Score:3, Interesting)
Disclaimer: I don't know a bra from a ket, but...
If you had a quantum computer, could you break any public-key cryptosystem by doing:
the Grover algorithm (Score:4, Informative)
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 (Score:3, Insightful)
Re:Quantum Computers / Shor's Algorithm (Score:5, Informative)
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 (Score:4, Informative)
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? (Score:5, Funny)
Re:Who needs it? (Score:5, Funny)
w00t
Re:Who needs it? (Score:3, Funny)
Didn't that guy... (Score:4, Funny)
Easy killer... (Score:5, Interesting)
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... (Score:5, Informative)
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.
Re:Easy killer... (Score:3, Informative)
(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 e akers.html#walterdaugherity [defcon.org]
And, According to
More than Just P=NP (Score:5, Insightful)
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 (Score:4, Insightful)
Re:More than Just P=NP (Score:3, Insightful)
Okay, suppose you're given a program that computes successive digits of, say, pi. Trivially we can say that it won't halt (not counting physical or architectural limitations of the computer), by definition.
Suppose we now add a test wherein the program halts if it detects a particular sequence of digits. Will it halt or not?
Show the trivial method by which you decide your answer.
Re:More than Just P=NP (Score:3, Informative)
See [mit.edu] some [mtnmath.com] of the [thefreedictionary.com] definitions [hyperdictionary.com] online [stanford.edu]...
Re:More than Just P=NP (Score:5, Informative)
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.
Re:More than Just P=NP (Score:3, Informative)
Wikipedia (see here [wikipedia.org] and here [wikipedia.org]) and my Theory of Computation textbook disagree with you.
From Theory of Computing -- a Gentle Introduction:
Re:More than Just P=NP (Score:3, Informative)
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 p
Re:More than Just P=NP (Score:3, Interesting)
It has been shown that with the standard set of axioms (without the 'axiom of choice'), you can construct models where the continuum hypothesis is either true or false, at your option.
If you inc
There's always OTP (Score:5, Insightful)
Re:There's always OTP (Score:3, Insightful)
Theoretiocal OTP: yes.
However the existence of randomness in nature if a pure observation and may be an oversimplification. There is not much indication this may be so, but when I look at what quantum physicists currently believe, I am pretty much convinced we don't understand this universe yet.
Re:There's always OTP (Score:3, Informative)
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 [idquantique.com]
SafeXcel [safenet-inc.com]
VIA C3 RNG [cryptography.com]
Could be argued (Score:5, Interesting)
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 (Score:5, Insightful)
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 (Score:5, Interesting)
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.
Re:Could be argued (Score:3, Insightful)
Light has momentum. The solar sail is the most direct application of this.
Consider a coin toss. In the average place where it takes place, there is uneven illumination. That is, as the coin is spinning, there will be time where the illumination on on
Re:Could be argued (Score:5, Insightful)
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 (Score:4, Insightful)
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.
It's still a "what if" piece... (Score:5, Insightful)
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.
Re:It's still a "what if" piece... (Score:3)
Nor necessarily. If it turns out that NP only has problems with complexity n^100 in it, then for most paractical purposes we are still in business, since practical algorithms in P may range up to complexity n^4, if that.
For crypto (on-way functions) it just needs to be very hard in one direction and very easy in the other. Choosing N and NP is a nice pair of things were this works, but not the only one.
Another magical no more secrets box (Score:3, Insightful)
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 (Score:5, Interesting)
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.
Re:All he does is explain P and NP (Score:3, Interesting)
True - and if NP is found to be P, then it will effectively hose encryption as we know it today. Your private-key/public-key encryption that relies on those big primes you know and love? Well then would be easily broken - the standard is private key is the two prime factors, public key is their product, and if an easy way to factor is found, then from the public key I can deduce the private, thus breaking your encryption.
They're not as unrelated as you'd think, bu
Re:All he does is explain P and NP (Score:3, Informative)
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
Re:All he does is explain P and NP (Score:3, Informative)
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.
Re:All he does is explain P and NP (Score:3, Informative)
128-bit brute-force anything is a bounded problem. Since there are only 2^128 possible inputs, all you have to do is pick the longest time it takes your program to run out of all those 2^128, and you can say your program runs in constant time (or better).
I saw this movie (Score:5, Funny)
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.
Re:I saw this movie (Score:3, Insightful)
Yes, I know this is funny, but keep in mind that a few years ago on the Clipper Chip issue it was also Kerry vs. Ashcroft - but it was Kerry pushing for the Clipper Chip and then Senator Ashcroft pushing for individual privacy. Ashcroft has since done a post-9/11 180-degree flip on his views here, but nothing suggests that Kerry has done the same (insert Kerry flip-flop joke here if you want, but no o
Re: (Score:3, Insightful)
I have discovered... (Score:5, Funny)
I have discovered a truly remarkable proof which this post is too small to contain.
Get with the times! (Score:5, Insightful)
The article sums it up best (Score:5, Insightful)
The whole thing is a bunch of alarmist speculation.
This is Crazy (Score:5, Funny)
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 (Score:5, Insightful)
Bruce
Re:It's not "the end of encryption" at all (Score:5, Informative)
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 (Score:5, Funny)
OH MY GOD, THEY'RE NOT???
Out of fashion, I guess. (Score:5, Funny)
Bell-bottom pants aren't cool anymore? Man... what a bummer. I got to quit bogarting those roaches.
My favorite Simson Garfinkel work (Score:5, Funny)
just calculate the key, Lee
hack the algorithm, Jim
reverse-engineer, Samir
sleep, what's that?
Factoring is another NP problem -- NO! (Score:5, Insightful)
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 (Score:5, Funny)
Re:I have a proof (Score:3, Informative)
This is silly (Score:5, Funny)
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!
Divide check (Score:3, Funny)
P/P=NP/P
1=N
Your proof fails when P=0, in which case any value of N will work.
Why P!=NP (Score:3, Informative)
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 (Score:4, Funny)
Simson Garfinkel (Score:4, Funny)
I'm sure he's never heard that before in his life.
I'll Tell You What The Consequences Are (Score:4, Funny)
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 (Score:3, Funny)
Re:Eventually (Score:5, Insightful)
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:Eventually (Score:4, Interesting)
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.
Re:Eventually (Score:3, Informative)
The only encryption theoretically unbreakable.
Re:Yep, its doomed. (Score:3, Informative)
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:Mandatory (Score:3, Informative)
"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 (Score:3, Informative)
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,
Re:Hard and tedious are different things (Score:5, Informative)
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).
Re:Ha! (Score:5, Interesting)
Re:Ha! (Score:3, Funny)
yes, for sufficiently large values of 2
Re:it may have been covered but... (Score:3, Informative)
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