Slashdot Mirror
The End of Encryption?
An anonymous reader writes "The encryption algorithms that make virtually all electronic commerce possible work only because certain mathematical problems are very, very hard to solve. But some mathematicians are trying to prove that there's really no difference between 'hard' and 'not hard' problems--known in the math biz as P and NP. In an article on TechnologyReview.com, Simson Garfinkel spells out the real-world consequences of this mathematical conundrum."
No no no no no. How many more times? Cryptography has absolutely nothing to do with the question of P?=NP.
P?=NP refers to the asymptotic complexity as the problem. i.e. as the input size goes to infinity. It quite possible to have a problem whos complexity is approximately linear at the 100-1000-bit range and still NP-Complete. Conversely, it's possible to have a p-time algorithm for solving a problem that has a O(n^100) so it's still difficult to solve. While resolving P?=NP might bring new tricks to the table it's difficult to legislate for these tricks. There might not even be any we don't already know.
Another point, p?=np has no bearing on the security proof of the one-time pad or quantum mechanical key exchange. The latter will become practical over large distances to enable the former long before p?np is resolved. Cryptography will die when the last human draws its breath.
Simon.
Guvf jbexf whfg svar sbe zr!
Right is wrong when left is right.
... write 'Bridge over encrypted waters ~(__8-(0) Doh!'?
This is really quite simple - the type of machine that can render Prime-based and Discrete Log-based encryption "useless" has not been invented yet. Furthermore, as the article points out, most (including Adelman) belive it'll be a long time before one is.
The problem (P vs. NP) is still just as difficult, and we aren't really much closer to solving it than 10 or 20 years ago.
dmiessler.com -- grep understanding knowledge
Which is not exactly true. It could be true but not provable. It could be false but not provable. It could be provably true, or provably false. Or, it could be neither true nor false.
In other words, cryptography is dust in the air?
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.
For 90% of the public, ALL math problems more complex than 2+2 are hard!
Learning HOW to think is more important than learning WHAT to think.
No, your're thinking of Kansas - Dust in the Wind.
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.
In an article on TechnologyReview.com, Simson Garfinkel spells out the real-world consequences of this mathematical conundrum.
Who else read that as Simon Garfunkle? Come on... I couldn't be the only person here, could I?
And besides... if you want real security, just do double encryption. use two common, off-the-shelf encryption methods, one encrypting the other's data and your data is now as safe as it can get. further encryptions in encryptions will only add to bloat and time to decrypt.
"Anyone can think of an encryption algorithm that he cannot crack." I forget who said it, though (Ed Felten?). It came up during the SHA-0 discussion here on /.
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.
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.
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.
These posts express my own personal views, not those of my employer
Ignoring the fact that the answer to P?=NP has little to do with breaking encryption for a moment, even if an NP computer is conceived and developed, it'll just lay down a *huge* plethora of computing possibilities at our disposal, including new encryption techniques.
Encryption cannot die, algorithms can.
An Indian-American Hindu committed to non-violent thought/speech/action alarmed by the global explosion of radical Islam
Yeah, I did an apt-get title - gotta love that Debian.
I propose we make every computer solve the meaning of Life, the Universe and Everything. Computers that have figured this out already know it is 42, and it would take the fastest supercomputer in the universe eons to calculate it, making it ultra-secure!
I'm in the hole of the broadband donut.
I saw a movie about this exact same thing. Luckliy Robert Redford and his team won and the world was made safe from Ben Kingsley, but it was touch and go there for a little bit.
I was worried.
The one way to tell for sure if the good guys win, is if the Republican National Committee goes bankrupt and GreenPeace gets a sizable donation. Also, you might see Sydney Poitier in Tahiti and Dan Akroyd in a brand spanking new RV.
--
Pain?
Try Prison.
> Or a quantum computer is made that can break all these passwords.
No. To put in plain language: there are forms of encryption more advanced than those that employ difficult math problems. Quantum computing does not pose a threat to a OTP system that employs quantum key exchange. Sorry.
You are thinking of One time pads
The only encryption theoretically unbreakable.
Free XBox, PS2
Depends whether you are doing an honours or not. ;)
I also meant when you do the actual analysis of P, NP and NP-Complete etc., not when you FIRST look at the these two classes.
just = (My)Opinion.toCents();
I have discovered a truly remarkable proof which this post is too small to contain.
LongTail SSH Brute Force analysis tool is here!
Is he related to Simon & Garfunkel?
;)
No, but his parents obviously thought he did
-- It's always darker before it goes pitch black.
Ask Slashdot dealt with this issue three years ago! When it comes to uninformed, idle speculation, this site is way ahead of MIT!
What I'm listening to now on Pandora...
Cryptography will die when the last human draws its breath. Er.... shouldn't that be third-to-last human?
Sometimes seventeen/Syllables aren't enough to/Express a complete
Simon Garfunkel Encryption Protocol. "Hello aklsdj=2vxcwe (( my old friend." SYN: Are you going to Scarborough Fair? ACK: Parsley, sage, rosemary and thyme.
-Randy
But if a quantum computer can be made to do this, then most likely a quantum computer can be created to securly transmit one time pads to the other end. A one time pad is unbreakable because the key length is the same as the message length. (boy I hope I got that right :)
"I hate to advocate drugs, alcohol, violence or insanity but they've always worked for me" - HST
Quantum computing does not pose a threat to a OTP system that employs quantum key exchange.
In practice it may never pose a threat to symmetric ciphers, like AES, either. Those don't rely on hard math problems as much as on non-linearity and complexity. Quantum computers may someday be good at solving simple but hard problems, but it's likely they'll never be able to attack complex problems, easy or hard.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
Wasn't this covered in the movie sneakers? As I recall, it didn't work out too well for the mathematician involved.
Some people have a way with words, and some people, um, thingy.
The whole thing is a bunch of alarmist speculation.
"The market alone cannot provide sufficient constraints on corporation's penchant to cause harm." -- Joel Bakan
Yeah, I much prefer Heinlein reference humor.
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.
"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.
I don't know if he was first to say it, but I first saw it said in Schneier's Applied Cryptography.
Reality has a conservative bias: it conserves mass, energy, momentum...
Bruce
Bruce Perens.
Bell-bottom pants aren't cool anymore? Man... what a bummer. I got to quit bogarting those roaches.
If you post it, they will read.
Summa summarum it's MIT science at its best swallow and full of hype.
The ability to feed the correct message back from that universe to the rest of us may be a bit tricky, but could perhaps be done by having the individual in the lucky universe set all quanta to 0xFF in a bank of LEDs in a pattern representing the plaintext.
Shor's algorithm doesn't necessarily have anything to do with complexity theory. It's simply an exploitation of our existing knowledge of quantum mechanics, whereas the article is talking about exploitation of potential advancements in mathematics.
If I were working on that problem, I would be trying to prove that P and NP are different classes.
That is, that P != NP.
I just don't think that P = NP has any chance of being true.
"50 Ways to Break Encryption"...
just calculate the key, Lee
hack the algorithm, Jim
reverse-engineer, Samir
sleep, what's that?
I'm surprised that Simson made this elementary mistake.
Factoring has *not* been proved to belong to either P or NP. It's an "open problem".
DNA is a Turing machine. You, however, being dynamic and emergent, are not.
You don't want the aliens decoding your pr0n collection.
Funny. I saw this movie just last saturday and loved it. Though I laughed when watching it after 5+ years and the concepts seemed - hollywood. :P
Sneakers rocked.
I have a proof that proving P = NP is an NP-complete problem. Unfortunately this posting is too small to hold the proof.
Adding 2 numbers and 25 billion numbers is really not that dissimilar in ways of difficulty, however it still takes a lot longer to do one than the other. The strength of cryptography doesn't come from how hard something is so much as how long it takes to do all that simple math.
The primality problem, closely related to most public-key algorithms,(since we have to decompose a big composite in two big primes),it is not even a NP problem.
The point of GP joke was "anyone can think of encryption that he (ie, the person doing the thinking) cannot crack."
Sort of like Groucho Marx's "no club that would accept me" paradox.
All's true that is mistrusted
Digital Fortress was a complete piece of shit. Please don't base anything off that rag. It was written with the express purpose of capitalizing off of Dan Brown's momentum being made into a movie. The "visuals" described fit Hollywood nicely -- meaning they have no basis in reality.
It is easy for a person to come up with an algorithm that THEY can't crack. Most are painfully obvious to outsiders with any experience.
Other than proper implementation of a one-time pad, you'll probably find any encryption will eventually fall.
Learning HOW to think is more important than learning WHAT to think.
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.
Agreed, on the grounds that the difference between P and NP is not the same as conventional vs. non-conventional computing... worth saying, since I think it might be quite natural to assume that there must be such a correlation.
If they succeed, won't it be humiliating for those mathematicians that have spent decades studying this problem to find it isn't harder than solving 2 + 2.
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.
In an article on TechnologyReview.com, Simson Garfinkel spells out the real-world consequences of this mathematical conundrum.
Was anyone else wondering why Simon and Garfunkel were writing about P=NP?
"I have a porkchop, you have a porkchop. I have a veal, you have a veal".
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!
> Which is not exactly true. It could be true but not provable. It could be false but not provable.
"true but not provable" is still makes the equation true. "false but not provable" still makes it false.
That's the logic. Either true or false, not both; regardless of what humans can prove.
On the other hand, the four possible states in our understanding of the equation can be either:
Like many security features, no encryption scheme will ever be completely secure, if someone is willing to throw enough CPU cycles at it, they can crack it. The purpose of security is to make it more trouble to steal or de-crypt something than the item or information is worth, not be completely un-crackable since there very well may be no such thing. M
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".
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.
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.
Yeah and 640KB should be enough for anybody.
If P=NP, then we don't have a set of problems that are difficult to solve, but easy to verify. That means we're left with problems that are easy to solve and easy to verify (useless for cryptography, obviously.. ) and problems that are difficult to solve and difficult to verify (potentially more useful.. but proper decryption becomes just as difficult as cracking the code).
I am the maverick of Slashdot
From your sig: --I have gmail invites to give away!
:)
Don't you know enough people without advertising your invites to anonymous web people?
Get your own free personal location tracker
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)
Even if P==NP, that doesn't automatically make all NP-complete problems "instantaneously" solvable. Overly exhuberant theorists referred to problems in P as "tractable", but just because they are called "tractable" doesn't make them so. Conversely, many problems in NP are so "tractable" already as to be useless for cryptography.
But more importantly, there is not a shred of evidence that P==NP, so talking about what terrorists would do if P==NP makes about as much sense as speculating about what terrorists would do if they had teleportation or Voodoo dolls.
It's a shame that whoever wrote this is posting as an AC, at score 0. (And that I'm unable to use my mod points, as I posted a meaningless comment earlier).
Woever wrote this, sign up, get an account, and use it to inform the Slashdot masses.
Get your own free personal location tracker
I thought that all the public key (etc) systems relied on a "hard math problem" to produce the public-key secret-key pair. When I generate my DES and AES keys I go through that "mostly prime" exercise.
So quantum computing should be able to do the "large nubmer factoring" exercise necessary to crack the key...
Or I am full of shite... 8-)
Innocent people shouldn't be forced to pay for inferior software development.
--"Code Complete" Microsoft Press
After reading the article, it says nothing at all abouut anyone proving that P=NP, or breaking encryption...
just that if they COULD prove this, then encryption would be meaningless.
So.. what's the big deal?
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'.
Thank you for making my point. Quantitative changes occur incrementally over time, like memory requirements. Qualitative changes, however, like the fundamental difference between quantum computers and Von Neumann computers, and the algorithms that can be executed on each, don't.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
but I think you're either a bit behind the times, or making an incredibly subtle joke, but either I should bring to the attention of the less-informed readers that Fermat's theorem, which states that there are NOT any such powers n>2, has been proven. http://www.pbs.org/wgbh/nova/proof/
Yeah, yeah, if P==NP we're all doomed. So what? If pigeons evolved flamethrowers in their eyes tomorrow we'd be doomed too. That doesn't make it reasonable to write an article headlined "Better bring lots of breadcrumbs when you go out, otherwise there's a chance you will be burnt to a crisp, experts say".
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.
Go read Charlie Stross's "Antibodies." It's a fascinating SF short story that starts out with a proof of P=NP and goes off from there. To the best of my knowledge, it's not available online anywhere, but it's not too hard to track down on paper.
Or, for that matter, go read anything of his. It's pretty much all good.
Isn't the P = NP proof one of the Million Dollar problems over there at Wolfram Research?
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.
So the concern is that a quantum computer is equivalent to the nondeterministic turing machine, as a current boolean-state computer is equivalent to a deterministic turing machine, at which point the NP problems take polynomial time on such a computer.
- "History shows again and again how nature points out the folly of men" -- Blue Oyster Cult, 'Godzilla'
The last human sat in a room. There was a lock on the door.
Mod the parent up please. Dan Brown is probably the most clueless person writing about encryption I have ever encountered.
As for chained encryption: In the end there's only so much shuffling of bits you can do before your algorithm isn't making any improvements to randomness of the output. If there's an exploitable hole in the algorithm (which is a given for being able to break any symmetric algorithm of significatn key size) then further rounds don't necessarily represent any significant extra difficulty. Check up on why 2DES is never used if you're curious - it effectively provides NO extra security.
Jedidiah.
Craft Beer Programming T-shirts
Not when they have given me over 30 in the last week and 20 or so before then. I have been in the beta since the beginning...
P=NP
P/P=NP/P
1=N
Your proof fails when P=0, in which case any value of N will work.
-Tom Duff
You're saying interstellar radio waves are crammed with all kinds of good stuff (including alien pr0n) but it's all noise to me. Foiled again!
Say hello to my little sig.
"In practical terms, that would spell the end of encryption as we know it. The Internet would be vulnerable to hackers and computer viruses." Made me laugh :p~~~
Best article quote:
Yikes! Er, um, wait, isn't that how the Internet is now?Actually, this has been proven using a direct proof. It will halt every time, given enough time.
Mod me down and I will become more powerful than you can possibly imagine!
Poor man was only two letters away from being a music sensation...
I'm sure he's never heard that before in his life.
It is considered likely by many that a polytime algorithm for deciding instances of NP-complete problems would also provide efficient keyspace search for cryptanalysis. This is a consequence of the "polytime thesis" (sorry about the crufty link, but I didn't spot anything better offhand: look way down near the end), which states that any real-world problem that has a polytime algorithm has a feasible algorithm. Note that this is both fuzzy and a thesis rather than a theorem, but I am not aware of any counter-examples. So, based on empirical evidence of past discoveries, we might well expect that if we can find a polytime algorithm for keyspace search, we can also find a feasible algorithm.
Consider the problem of deciding whether a number is prime. This problem was recently shown to be in P, but the algorithm given requires around |n|**12 steps in practice. Obviously, this is still not a feasible algorithm. Proponents of the polytime thesis, however, are not concerned: they believe that a low-order polytime algorithm will soon be found. I tend to agree with them.
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.
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.
But that description is remarkably similar to the definition of the nondeterministic turing machine
As I said, IANAQCE. Take everything I write with a grain of salt. I wouldn't be surprised if a quantum computer was similar, or equivalent, to a nondeterministic Turing machine. After all, quantum mechanics is nondeterministic.
which is basis of the NP set of problems -- it isn't that it tries every permutation in parallel, it's that it *could* do every permutation, and the right permutation takes polynomial time.
The problem is, how to know which permutation is "right"? This is the advantage of quantum computing, that you don't need to know it beforehand.
So the concern is that a quantum computer is equivalent to the nondeterministic turing machine, as a current boolean-state computer is equivalent to a deterministic turing machine, at which point the NP problems take polynomial time on such a computer.
Even polynomial time can be extremely long, if the order of the polynomial is high.
"Long run is a misleading guide to current affairs. In the long run we are all dead." (John Maynard Keynes)
You down with OTP?
.sigs are for post^Hers.
There is a definition of random that seems fairly convincing to me (and to others). In that definition a bit string is defined as random when the smallest program (turing machine, lisp program) needed to compute it is longer than it is. See Greg Chaitin's work for more info, or this wikipedia page . And this kind of work seems to have some practical implications for cryptography as well.
How can a big slashdot story /possibly/ be that "Mathematicians are trying to determing P ?= NP"? That's like the breaking news, "SCO is suing someone"!
Oh.
Nevermind.
(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.
Simon of Simon & Garfunkel was indeed a math teacher, but a crypto expert? I don't think so.
l
http://www.superseventies.com/1976_9singles.htm
Natural Selection: self-destruction of the poor and lazy
Bruce
Bruce Perens.
Bruce
Bruce Perens.
"with a $1 million prize offered to the person (or machine) that can solve each problem"
I better find the solution before my computer do or I won't get anything !
Only on Slashdot would such a comment be moderated "Insightful". I guess the reason that any comment that insults the majority of the populace gets modded up on Slashdot is the social insecurity felt by the moderators. Does it make you feel good to insult a huge portion of the populace? Does it make everyone feel so much smarter and better than all those evil "jocks" that picked on you in high school?
Grow up. Nerds, geeks, computer experts are not the only intelligent people out there.
Yeah, mod me as flamebait, whatever.
Forget the whales - save the babies.
From the article.....
This is not any more news now than it was "when bell-bottom pants were cool."
If I don't put anything here, will anyone recognize me anymore?
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:
(Or is the above stupid and wrong, and I'd need an actual course in quantum physics to even understand why?)
>;k
I've read this three times, and it gets more confusing with each one. Perhaps you're using a weird definition of 'trivial'---from what I can tell, you're saying that it's easy to just run any particular program to see if it halts or not.
So...
1. Run Program on Input.
2. Wait an infinite amount of time.
3. If Program is still running, return DOESNT_HALT. Else, return HALT.
"Wait an infinite amount of time", to me, is a nontrivial step. Were you seriously suggesting otherwise?
--grendel drago
Laws do not persuade just because they threaten. --Seneca
Really, what a gem. I was about to post the same thing when I saw your post. It seems like that article was written by a first-year computer science student. So many facts misstated. And it's all just speculation anyway, because the "scientists" in question just broke MD5, not P=NP?. And prime factorization hasn't been proven NP-complete (because it probably isn't). Yes, it's in NP, like all of P, but that doesn't make it "hard". Also, NP-Hard is not exactly the same as NP-complete anyway. Of course, the biggest error that they make is saying that P=NP can be proven either true or false. Some theoreticians believe the question may actually be independent of the axioms of mathematics. This kind of crap coming out of MIT is just wrong.
Six score characters.
Brevity being wit's soul
I have enough space.
Suppose P?=NP is unprovable.
The existence of an algorithm to solve an NP-complete problem in polynomial time would constitute a proof that P=NP.
Therefore there can be no such algorithm.
Therefore P!=NP.
This is a contradiction.
Therefore P?=NP must be provable.
Researchers have shown that simply throwing a thick blanket over a subject can result in a Denial of Light attack. Pundits have suggested that with this knowledge, there is no longer any point in using light any more, when it can be denied so simply. Experts are working overtime to come up with a solution.
Those don't rely on hard math problems as much as on non-linearity and complexity.
What's the difference?
Give me Classic Slashdot or give me death!
P = NP
Divide both sides by P.
1 = N
Clearly, N = 1. Next?
Few people know that Ashcroft was once a crusader for personal freedom and privacy and took a stance against the Clipper Chip. Oh course, NOW he is a total fucktard who wipes various parts of his body with the bill of rights, I guess prolonged exposure to government does that to people.
Incidently most of the geeks I know (myself included) who voted for Bush did so because at the time he appeared to be the lesser of two evils. Al "Mr Clipper Chip" Gore certainly was no friend of the technology industry or anyone interested in privacy while he was VP.
Of course now we know that there are no lesser of two evils. Kerry and Bush will both screw over the country hard. Let's face it, nobody likes either of these two failures. They just hate the other guy enough to pretend to like one of them. It is a sad say in the US when these two are the best options we have.
Finkployd
Some formatting was lost when you copied from Wikipedia. It's O((log N)^3) time, not O((log N)3) time.
I see, so a couple brilliant math guys made a bet some time ago that it 'would'/'would not' not be proven that P does not equal NP by the end of the century. And due to the fact that its not been proven, this means that its possble?
I dont see that. I submit this only means that it hasnt been proven that its not possible, and further that all of our assumptions still hold.
Once you get passed all the fear this article tries to incite by way of background and inference; this article, at the meat of it, only suggests that nothing has changed in 30 years.
I think you underestimate just how much I just dont care.
I never could quite figure that out.
But only if you live forever.
What's the difference?
That's a tough one to answer concisely. The best way to see the difference is probably to look at the algorithms.
Symmetric ciphers work by doing a whole bunch of different operations, mixing and munging the data in complex ways, and doing it over and over again. In the case of DES, for example, there are 16 rounds. AES-128 uses 10 rounds. Each of the individual mathemetical operations are simple, easily reversible and weak, from a security standpoint. The strength is achieved by repeating them many times in particular ways to create an overall structure that is hard to break.
In contrast, public key ciphers, like RSA, consist of only a single mathematical operation, one that has useful properties. An RSA encryption operation just requires calculating m^n mod p. The operation is very simple and straightforward, but there's no known way to reverse it efficently without the private key.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
One important class of problems which should be included in this discussion is the class of P Complete problems.
These are problems for which there exists a polynomial time reduction to the P Problem, which is the ability to optimally distribute P straight pegs in U linearly arranged slots (where P less than or equal to U), so as to maximize the distance between pegs.
For example, for (P=2, U=5), the optimal solution is a peg at the first and last slots. For (P=3, U=5), optimal is U0, U2, U4, etc.
It can be shown that any problem which can be reduced in polynomial time to straight men at a row of urinals is P Complete.
"I thought they were the dominant species..."
"I hate to advocate drugs, alcohol, violence or insanity but they've always worked for me" - HST
That's the idea, and as of last year, people have been able to build 4-qbit quantum computers that can instantly factor a 4-bit number.
Obviously that's not very useful as I can factor a 4-bit number in my head in about a second, but if larger q computers can be stabilized, then factoring larger numbers instantly will be possible.
Nothing to see here; Move along.
By the way, since you seem knowledgable: Is there any NP-C reduction that is conjectured not to be a log space (LOG) reduction?
From what I remember, most polytime reductions are trivially in LOG. I am also aware that LOG!=P is open, but it is conjectured that it is true.
Network Security: It always comes down to a big guy with a gun.
... but I still think that it was not what the grandposter had in mind! To my mind, "trivially decidable" means "computable" (note the "trivially" part!), and I do not think it is that trivial to get the answer to the halting problem -- yes, someOne with an infinite (though countable) number of computers and infinite -- either (countable) number of clock cycles or (continuous) amount of time on its hands, I do not know which is required -- can know all the answers. But that entity is usually referred to as "God" and its existance is a bit beyond the scope of this discussion... ;-)
Paul B.
The question I'm always asking myself is: is creating an (n+1) qbit computer twice as hard (or harder) than creating a n qbit computer? If so really this QC approach is doomed.
I'm too tired to think right now, but IIRC the problem is that the atoms or molecules are hard to keep in the correct position(s).
So I'd guess it'd be an O(2^n) problem, but like I said, I can't think right now.
Nothing to see here; Move along.
To be simple, we suppose the encryption is done by multiplication by 3 (X1=3*P1), then it can be done by adding P1 to itself left-shifted one bit, in which the shifting can be omitted (it doesn't do anything real to the bits) and replaced by some crazy bit-twiddling. After it is done you will see not only X1 but also a copy of P1, and possibly some intermidiate results.
Now it is difficult to get rid of the P1 (i.e. make the bits zero) using only reversible operations. If you don't do that, when mixing X2 and X1 you will also need a correct P2=X2/3 to mix with the P1, before the reverse operation will work. So you see that it isn't easy to reverse things in QC, whether it is multiplying by 3 or the DES transform.
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 into a secret key (the timestamp) issue. How do you communicate the timestamp between the two sources?
There's another benefit though, and that's that the sheer amount of data being generated by these satelites will make it prohibitive to analyze a transmission after the fact... only live interceptions could be used.
Factoring _is_ in NP. What is not known is whether factoring is NP-Complete or not. A problem is in NP if the corresponding decision problem is in P. In other words, if you can check if a solution for a problem is valid in polynomial time, the original problem is P.
NP doesn't mean non-polynomial: it means non-deterministically polynomial, which means you can build a non-deterministic Turing Machine that solves the problem in polynomial time.
It is easy to see that NP is a superset of P. What is not proven yet is if it is a _proper_ superset, that is: if there are problems in NP that aren't in P.
Of course, I could be very wrong about this. It's been decades since I studied this stuff.
Prime numbers are exactly what Alan Greenspan says they are -S. Minsky
I saw this article and thought, "WHAT? Someone proved P=NP?". I was disappointed.
As it is, I see nothing enlightening about this article whatsoever... As people so often say here, "nothing to see here, move along".
09 F9 11 02 9D 74 E3 5B D8 41 56 C5 63 56 88 C0 Whoops, silly middle mouse button...
I do believe that this is the first time I've been razzed by someone of your stature. I bow to your four digit ID.
I'M NOT WORTHY!
I'M NOT WORTHY!
I'M NOT WORTHY!
Well, there's spam egg sausage and spam, that's not got much spam in it.
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".
Oh, well, then I guess we're still safe for now...
A good defense before such attack would be to change the cipher in such a way as to make the corresponding quantum algorithm useless,
So you depend on the security (and novelty) of the cipher, rather than the key? That's called "security through obscurity", and it gets laughed at.
Bruce
Bruce Perens.
Geez. I have to teach Mozilla to not fill in "What tasks require high-speed interconnects?" every time I make a posting. Duh.
Bruce Perens.
but I am basing my limited knowledge off of Digital Fortress by Dan Brown
If you want to actually learn something about codes from an adventure novel, try Cryptonomicon. (Warning- 1000 pages)
The premise for Digital Fortress was completely backwards from reality. It suggested that today the NSA can break any code, and that chaos would result if a breakthrough changed that. But actually, any competent code is unbreakable already, even to the biggest government supercomputer- and if that changed, we'd see a good bit of rioting in the streets.
Normally, I'd agree with you. However, P?=NP is a slightly different kind of problem, as it's almost a metaproblem. It's a problem about other problems.
See, unlike your example, the terms are well defined in something we do know about. Essentially, it breaks down to the fact that people came up with problems to which nobody could find a good answer to. So instead of solving them, which was proving inordinately difficult, they decided to start describing them differently.
This led to grouping them, which eventually led to classifying them, which eventually led to a new kind of problem since they couldn't prove that their classifications actually had any real meaning. They couldn't figure out how to prove P != NP.
So my point here is that P and NP are not really terms that are poorly defined. They are extremely well defined, mainly because nobody could work out how to really get good solutions to the problems that they are describing in the first place.
Basically, P and NP are extremely well defined sets and there's rigorous proofs to show that if an NP-Complete problem turns out to be P, then P=NP. The question does have meaning, because if the answer to it could be determined, it would either eliminate or validate the classifications that have been setup to create the terms P and NP in the first place.
It may not be provable, but either those groups have real significance as they are described or they do not. There's no real in-between state there.
- Give a man a fire and he's warm for a day, but set him on fire and he's warm for the rest of his life.
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.
I think my parents had some of their albums...
I got it. It's just nobody as notable as you has ever responded to one of my comments. The only brush with fame I've ever had was when I met President Clinton one time. I even shook his hand. Knowing what I know now, I should have washed my hands afterwards. :)
Well, there's spam egg sausage and spam, that's not got much spam in it.
There's a scene in Futurama (I forget the episode, sorry die-hards) where we see a closet with a bookshelf. On one of the shelves are two books, entitled "P" and "NP". Evidently, in the year 3000 we'll have proven that they are separate problem spaces.
The thing that makes Quantum Computers a bit scary is that algorithms like Shor's have shown that QC's can give an exponential speed-up to some problems (assuming P!=NP). Prime factorization happens to be one example that is of particular interest to cryptographers. The reason this is possible is because most of our algorithmic complexity analysis to date is based on the assumption that the computers the algorithms are running on are (read: can be modelled as) Turing machines. Quantum computers are not Turing machines, which is why they get to "break" the rules.
Here's another example of an algorithm for which Quantum computers "break" classical algorithmic bounds. It can be proven that no "classical" computer can search for an item in an unsorted list in better than O(n) time. This not only makes intuitive sense, it can be mathematically proven. However, there is an algorithm to do the same thing on QC's in O(sqrt(n)) time.
Bruce
Bruce Perens.
I shouldn't have written "A good defense", only "first kind of defense I can think of". Probably wise people know better defences. I did not, though, write that it depends on the security (e.g. secrecy) of the cipher.
Today we use the same approach: when the DES ceased to be secure, someone came up with a new cipher, AES (well, not at once). Some day, AES will cease to be secure. Then we will use other cipher... Is it really "security through obscurity"?
"Long run is a misleading guide to current affairs. In the long run we are all dead." (John Maynard Keynes)
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. ...to building a quantum cryptography computer that can scale? Adding qubits isn't like adding transistors, all the bits need to be in a shared quantum state. Generating one of thousands of bits is going to be a much harder problem than a handfull.
Kjella
Live today, because you never know what tomorrow brings
Today we use the same approach:
No. It's not the same. Holes in DES or AES arise only because of human error in creating the cipher. (And if you wanted better security, you'd be using Diffie-Hellman anyhow). They are not expected, anticipated, or unavoidable.
But in a hypothetical future with quantum computing, breaking the encryption doesn't rely on discovering a flaw, just going through the work. Fundamentally so much easier.
We just don't know how to prove it. (Or IF we can prove it).
There was this paper/algorithm by a russian guy.
I downloaded it once but was too much lazy and stupid to understand. And I doubt that you can still find it, because either it is too valuable or stupid to still be online.
It was an algorithm to do with MST and triangles I think to solve a problem considered NP-complete.
Now I guess he might have made a mistake in his algorithm, but what if it turns out that it works most of the time, so you can solves 99% of the cases of a specific NP problem with a good heuristic that is in P ?
After all, for some travelling salesman problems, some parts of the solution are obvious.
For PKC, this means you first have to check your keys whether they are easy to crack, and in fact I've read that for RSA/PGP, keys should be chosen smartly. However, where does the smartness end ? Maybe knowing all weak keys IS in NP~-P.
I'm still trying to figure out what people mean by 'social skills' here.
The OTP is a special case.
If we find an efficient way to solve NP-style problems, then conventional keyed encryption (eg AES in EAX mode) falls too, because we can efficiently search for the key that makes the plaintext make sense (and MAC correctly).
However, P?=NP doesn't directly bear on these problems, because they are not organised in families of increasing problem size, such that there are always larger and more difficult problems.
And if there's a way of factoring large numbers whose compute time grows on the fiftieth power on the length of the number, then it wouldn't in practice make any problem for those using RSA, even though it brings the problem into P.
Xenu loves you!
The one-time pad *is* a key, and the encryption algorithm usually used is XOR or a caesar-style rotate.
I agree that quantum computing will simultaneously benefit cde making and code breaking, so it would seem it balances out. However, in all likelyhood the first decade of quantum-computing will be mostly in the hands of government and possibly big corporations, because until someone figures out a low-cost way of making quantum-computers, they will be the only ones able to afford it. That means that during that time, they will be able to break just about any encryption that you can generate. Echelon++, here we come !
Offcourse, all this is not a problem if you trust your government (and everyone in it) not to misuse their power.
"If something's hard to do, it is not worth doing."
So, theoretically there is nothing between hard and not hard problems. Is there an assumption somewhere in there that you have infinite computing resources and an infinite number of monkeys to monitor them?
Try telling this to students to students that just failed an engineering, science, or math test:)
Organization: alphabetical, sometimes numerical or messy
Or I am full of shite... 8-)
Yes, you are full of shite.
-a
Okay... so you say symmetric ciphers are not based on 'hard' mathematical problems. Would you mind solving this?
DES(k, 0x8c08280811114444) = 0x1ce2fd0a908b1cc3
DES(k, 0x111144448888dddd) = 0x2088c2bf0a3dfc24
DES(k, 0xcccc000000000000) = 0x1bff2081f3259304
Find k which yields above results for each k assuming function DES is electronic code book mode DES. Do not brute force or use quantum computing. Do not channel or employ other parapsychological phenomena.
When I was a high school senior, and mind you back then we were very naive about cryptography, I thought, gee I got a bunch of cipher/plaintext pairs and I know it is DES. Given the ciphertext, it should be easy to roll back the algorithm and get at the key bits. To cut a long story short, at least for me, there is simply no way to reverse the algorithm and derive key text from the cipher/plain-text, though I am sure a mathematician could formally describe the reversing process and classify the mathematical problems involved.
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.
1) Despite having a lot to lose and plenty of resources, terrorists don't use encryption properly or even at all.
2) The police get to the computer in advance and insert some sort of key logging technology.
3) The terrorist uses the tools OK, but some other flaw in the OS allows the police to extract the key (for example from the swap partition).
4) They simply torture the suspect until the tells them the pass phrase (I think that this is the most likely).
5) We only get to hear about the cases where the suspect made a mistake. Meanwhile, the NSA have a room full of media which they can't decrypt yet.
6) The NSA know how to crack all of the common algorithms in a reasonable period of time.
If 6 is true, it could be a long time before we hear about it.
A proof of P=NP could merely show there must exist a P algorithm for every NP problem. It doesn't necessarily have to give such an algorithm, only show its theoretical existence. While such a proof would prove P=NP, it would still be of little practicle use.
Only once such a conversion algorithm is found then, yes, every NP problem can be actually solved in polynomial time.
Thanks for the tip. I have heard many good things about the book you recommend so maybe I will check that out. Seems that I was a m0r0n for thinking that a DB book could have a good fact base. :)
Okay... so you say symmetric ciphers are not based on 'hard' mathematical problems.
Right.
Would you mind solving this?
You're not understanding me. I'm not trying to claim that DES is easy to break. Quite the opposite, actually, and DES is a very well-respected algorithm.
DES is hard because of the complex and non-linear way in which it employs bunches of different simple, easy operations. Shifts, rotates, S-box substitutions, pre- and post- permutations, etc. are all simple, reversible and easily breakable functions. But enough of them ganged together, in the right way, creates a mathematical function that is very hard to describe in any kind of an accessible, closed form. It's inherently iterative, sequential and algorithmic. The best known attack on DES is a linear cryptanalytic attack that essentially tries to create an accessible, closed-form function for 14 of the 16 rounds. It's not a very successful attack (it requires 2^43 known ciphertext-plaintext pairs).
RSA, in contrast, is extremely simple to describe and to understand. And one excellent way to break it is blatantly obvious: Factor the public key (it's not known if there is a better way to break it, but factoring is certainly sufficient). The problem is, factoring products of large numbers is a hard problem.
See the difference?
Do not ... use quantum computing.
My point is that QC wouldn't help me, even if I had a functioning quantum computer, because QCs can't really model iteration.
To cut a long story short, at least for me, there is simply no way to reverse the algorithm and derive key text from the cipher/plain-text
I should hope not, since that would render the algorithm completely useless for cryptography. Or, rather, you should hope you can find a way, because doing it, where so many other very bright people have failed, would guarantee you a good academic career.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
You're not understanding me. I'm not trying to claim that DES is easy to break. Quite the opposite, actually, and DES is a very well-respected algorithm.
:-)
Where did I say I believe your think DES is easy to break?
DES is hard because of the complex and non-linear way in which it employs bunches of different simple, easy operations. Shifts, rotates, S-box substitutions, pre- and post- permutations, etc. are all simple, reversible and easily breakable functions. But enough of them ganged together, in the right way, creates a mathematical function that is very hard to describe in any kind of an accessible, closed form. It's inherently iterative, sequential and algorithmic.[...]
Yes. I see where you draw the distinction. The way I see it, even when things get "algorithmic", in other words, even when the result of the substition step is a parameter for a transposition step and back and forth, even then certain patterns will emerge and mathematicians will have to find formal ways of describing those patterns.
Ever wonder what a 3D space looks like where X is all plaintext values from 0 to 2^64-1, Y is all key values from 0 to 2^56-1 and Z is of course DESECB(X,Y)? I wonder what rythms or maybe even geometry there is to be found in something like that. Then I wonder what a autistic but gifted child might notice that we wont
Replace that 2 with another N if there the qbits can be in more than 2 possible positions.
e.g. if they can be in 4 positions, and only one will work, then it's O(4^n). I think.
Nothing to see here; Move along.
Of course now we know that there are no lesser of two evils. Kerry and Bush will both screw over the country hard.
I generally vote Republican, but I think Kerry is a good match against Bush. Heck, the Democrats managed to field a number of decent candidates this year.
Still don't know who I'm voting for this year... maybe I'll just take a coin into the voting booth to decide.
Wolde you bothe eate your cake, and have your cake?
:) Thanks for taking the time to respond...
Use the Diffie-Helman key exchange method to securely transmit the parameters to a Blum-Blum-Shub pseudorandom number generator from one party to another party.
Once that is done, the BBS output can be used (in paranoid '1-bit only' mode for maximum security) to encrypt, send, and decrypt information between both parties.
It's not OTP but its the next best thing, yes?
Let me see if I get this right: if it takes more than 18 months to upgrade n-qbit computers into (n+1)-qbit computers and if Moore's law holds, then we'll have a way of factoring 128-bit numbers faster via the conventional route quicker than via QC?
even then certain patterns will emerge and mathematicians will have to find formal ways of describing those patterns
This is precisely what cryptanalysts try to do, and exactly what cipher designers try to make impossible (descriptions simple enough to be useful, anyway).
Ever wonder what a 3D space looks like where X is all plaintext values from 0 to 2^64-1, Y is all key values from 0 to 2^56-1 and Z is of course DESECB(X,Y)?
Several papers have been published that explore the structure of this space, mostly looking for subgroups and semi-groups.
I wonder what rythms or maybe even geometry there is to be found in something like that. Then I wonder what a autistic but gifted child might notice that we wont :-)
:-)
Likely not much. The space is simply too large for even the best human pattern analysis. Math provides better tools, but the space still resists too much description -- which is desirable in a cipher. DES is a good choice to explore such questions, though; as the pre-eminent block cipher in the world for nearly 30 years, it's been studied more heavily than any other.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
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.
Neither am I, but if you asked me to hazard a guess, I would probably say that investigating the code of an operating system in order to find security flaws with it is an NP problem. Being able to do this automatically in a reasonable time frame would assist virus writers. It would also, of course, assist operating system designers.
It depends on the exact numbers, but considering a 128 bit key, and assuming n is the number of bits, and treating O(f(n)) as being f(n), we have 128^19 = (2^7)^19 = 2^133 > 2^128. Which leads to the following predictions:
The Future Solution to the NP problem
Music: a super-stimulus for the perception of musicality. Musicality: a perceived aspect of speech.