is my 2048 bit key still safe? I mean, when I was having PGP create my keys I decided that twice the "High" security would be good, so I made a 2048 bit key... is it still secure? is it still excessive?
As far as I know PGP is a DES encrypted message (40 significant bits in the key) with a randomly chosen key.
This isn't quite correct -- PGP uses the RSA public key crypto system (the one with the large prime numbers as keys, which the article was originally about) to encrypt a session key. The session key can be any length you like, and used for any symmetric crypto algorithm you want.
Whilst it's perfectly possible that PGP uses 40-bit DES, I know my version uses 128-bit IDEA. The reason it works like this is because RSA is very slow compared to symmetric cyphers like 3DES, Blowfish and IDEA.
You're correct when you say that compressing a message before sending it increases the difficulty of breaking it -- PGP does this automatically unless you tell it not to. Try PGP'ing an uncompressed text file, and you'll find that the ciphertext is smaller than the plaintext.
This isn't a really big thing. Keys of this length have always been on the fringe of "secure" as computers get faster and algorithms improve the "secure" keysize will gradually become bigger and bigger.
This is not a factoring breakthrough. To break your 2048bit key it will take a breakthrough (if one even exists to be found, you know that whole P!=NP discussion?) or a radical breakthrough in computation.
-- This is my signature. There are many signatures like it but this one is mine..
How many do you think NSA will buy?
by
samiladanach
·
· Score: 5
But seriously, this was an interesting article. It just goes to prove that if you are using key sizes of less than 512 bits for public key cryptosystems, you may be vulnerable to advances in factoring rather than advances in raw processor speed.
The main advantage of this is that 512 bit keys can be factored in 9-10 weeks as opposed to 6-7 months with the previous application of this factoring method (described in the paper). This means that with this equipment and assuming that the estimate is correct, 768 bit keys can be factored in 1038 years (Shamir's estimate of 6000 * len(512)). A 1024 bit key would be factorable in approximately 1x10^6 years with this method and optimal conditions, however such a number requires exhorbitant space, upwards of 256 GBytes for the sieve 10 TeraBytes to store its matrices.
Bottom line, any key of 512 bits is good for about 9-10 weeks. The recommended minimum key size is still 1024 bits. The paper's conclusion sums this up best:
Conclusion The idea presented by Dr. Shamir is a nice theoretical advance, but until it can be implemented and the matrix difficulties resolved it will not be a threat to even 768-bit RSA keys, let alone 1024.
Its more important to have the freedom to use strong encryption so that we don't have to worry about being forced to choose weak keys in order to communicate.
I don't think that's the point here. Even then, the "computation power" of the tank scales polynomially with it's size (at best).
So with regard to NP-trapdoor functions, all you have acheived is to raise the stakes a bit and have to start with, say, a 2048 bit key instead of 1024. But the fundamental problem is, that still some (fixed) number l of additional bits will double the effort for cracking. Take 1000*l bits and and every single atom in the universe can work on your problem in parallel until the hell freezes over. (Quantum computers may be a different thing though, but even that remains to be proven.)
OTOH *if* you really find a polynomial algorithm for some (arbitrarily weird) specific NP-complete problem, than you can apply this very algorithm to any problem in NP because NP-complete problems can be emulated by one-another with only polynomial overhead.
What this means for Factoring (and RSA)...
by
trims
·
· Score: 4
OK, I sat down and re-read the major sections of both Schiener and Knuth (to refresh my math memory), and then something that the Silverman's analysis jumped out at me:
Current (and expected future) uses of Number Sieve factorization (currently, the General Number Sieve is most efficient) are composed of two parts: the sieving of factors, and then solving a matrix of all the possible factoring equations.
For most of the time, the first operation has dominated in time; however, this first process is also the most ameniable to increases in speed.
As Silverman pointed out, the RSA-140 (465-bit) challenge required 4 weeks of 200 machines to solve, then about 4 days for a single super-fast box to solve the resulting matrix. Using Shamir's new methodology, we can expect a 512-bit number to be done in 5 weeks on 20 machines, with another 4 weeks to do the matrix.
The bottleneck has now become the matrix solution, which is a non-parallizable problem (for now). All that can be done on it currently is to use Moore's Law, which doesn't significantly affect the security of larger keys.
If anything, Shamir's invention will now push the focus of attacking RSA from dicovering the factoring equations (the "sieve" part) to improving the matrix solution problem.
The real danger here is from the NSA and other organizations that may have discovered a way to significantly parallelize the matrix solution. If they can do that, well, RSA is going to be screwed. However, there is no current indication that they can do this. But don't say I warned you.
For those paranoid, here are some relevant numbers on the now-dominant times to solve the matrix for relevant key-bit sizes (all assumptions are using 1999 hardware; divide all times by 10 for each 5 years that have passed to account for Moore's Law).
512-bit key: ~4 weeks
768-bit key: ~1850 years
1024-bit keys: ~5million years
Remember, these numbers are NOT reducible by throwing more hardware at the problem - this is a (currently) serial operation, and must be done by a single machine. I don't see us being able to produce a single-CPU box a million times faster than state-of-the-art within the next two decades (Moore's Law predicts one about 2030 or so). By then, the memory requirements will be mundane. (if we can do 10GB now trivially, 10TB in 30 years shouldn't be any problem. In fact, we should be able to easily do 10TB about 2015 or so.)
In the end, 1024-bit keys should be immune to advances in sieving technology for at least 20 years. The worry is advances in matrix solutions, and development of methodologies better than Number Sieves. But, by the very nature of things, this is unpredictable.
Best Guess (and I'm not Bruce Scheiner): 1024 -bit should be immune to everything until at least 2015, after which 2048-bit should last to mid-century or so.
Happy Hacking!
-Erik
-- There are always four sides to every story: your side, their side, the truth, and what really happened.
If you're interested in quantum computation and cryptography you may be interested in checking out the Los Alamos site on quantum crypto.
Also some of you may be interested in Bruce Scheier's book Applied cryptography: Protocols, Algorithms, and Source Code in C, which was previously mentioned in other posts. You can find information on it at this Amazon.com link.
I might as well also give the link to a site on basic cryptology, called a "beginners page on cryptography" It may or may not help/interest readers.
On a side note, I really have enjoyed reading everyone's comments on this subject today. Hopefully these links don't come to late in the "day" for anyone to get good use out of them.
Re:How long would a PC and a couple of these need?
by
Christopher+Thomas
·
· Score: 2
I'm mildly confused by the timings, so how long would it take a decently powerful (as in, PII 300) machine hooked in to one of these devices to crack that?
A very long time, though still just a linear factor longer. Your computer has to solve one hell of a huge matrix problem. This requires enough RAM to hold the matrix and any working data (gigabytes or _more_; see the article), and time proportional to the cube of the matrix size (or possibly better if you're using something other than Gauss-Jordan reduction).
They used a supercomputer to do the matrix solving. If your machine has n times fewer bogoMIPs, then it will take n times longer, assuming that you can support the required RAM.
Assuming that it is the matrix solution and not the sieving that limits the solution time. This would probably be the case if you're using a PC to process the matrix.
A few points in your post puzzle me; I'd appreciate it if you could elaborate on what you mean:
Today's "conventional PC" uses silicon-based CPU technology, but that will change in a few years when IBM begins to mass-produce copper-based chips.
IBM has already demonstrated chips with copper _interconnects_, and many manufacturers plan to use this technology, but I've never heard of using copper as a _substrate_. Conventional chips use a silicon _substrate_ and aluminum interconnects. What IBM technology are you referring to?
An "electro-optical" computational device is the next paradign shift in computer engineering. By transmitting data via light (LEDs!!!), the current CPU problems with heat, electromagnetic interference (EMI) and wafer size all disappear.
I'm afraid that this is not strictly true. In fact, feature size for optical components would be a big problem. Optical devices can't have features much smaller than a wavelength of light. For visible light, this is on the order of 0.5 microns. Electrical devices, like conventional integrated circuit chips, can have features that are much smaller. This tends to outweigh most of the advantages of using optical "chips", should such chips be developed. They would be bulkier, and wouldn't be faster, because while electrical signals propagate slower than light, they would have a much shorter distance to travel. If you try using light with a much shorter wavelength, you wind up destroying your substrate (the photon energy must remain lower than the energy required to dislodge an atom in in the device).
Heat dissipation is and will remain a problem for electrical devices, but photons get absorbed too.
Electro-optical devices, OTOH, get the worst of both worlds. The only situation in which they're really practical is when you need to send signals over a (relatively) large distance without much degradation, as is apparently the case with the computer being built here.
Re:How long would a PC and a couple of these need?
by
Christopher+Thomas
·
· Score: 2
TWINKLE attacks by factoring. This is useful for most asymmetric algorithms but not for symmetric algorithms which do not use primes maths.
However, the original question was about the timings cited in the TWINKLE article:
I'm mildly confused by the timings, so how long would it take a decently powerful (as in, PII 300) machine hooked in to one of these devices to crack that?
My response stands for that, though as you point out these timings don't apply to other classes of encryption.
Thanks for the correction: silicon-based chips with copper substrates, NOT copper-based chips.
I hope you mean interconnects instead of substrates...
"They would be bulkier, and wouldn't be faster, because while electrical signals propagate slower than light, they would have a much shorter distance to travel. If you try using light with a much shorter wavelength, you wind up destroying your substrate (the photon energy must remain lower than the energy required to dislodge an atom in in the device)."
An electro-optical device does not use a silicon substrate, nor does it need the interconnect metals that we see today. Furthermore, the materials used for the device's internal parts and casing allow researchers to experiment with light wavelengths outside the visible spectrum.
My argument holds no matter what materials you use to build the optical device and no matter what processes are used to fabricate it. Whatever you do, you just _can't_ get the feature size of optical devices much smaller than the wavelength of the light used, or signals bleed from one computing element into another. Likewise, no matter what material you make the device out of, you can't have photons with an energy of more than a few eV, because that is the typical binding energy of valence electrons in atoms. If you decide to use deep UV or what-have-you, your device _will_ degrade due to atoms being dislodged and bonds being broken, no matter what it's made of.
But remember: Prof. Shamir's theoretical device is NOT A CPU! It is an "electro-optical sieving device"
How does this affect my points?
Because of its narrow function, the "TWINKLE" box will likely have a much cleaner, simpler design
This is true of any special-purpose computer. What of it?. See Deep Crack for an example, or look at DSP designs (they elminate a lot of the scheduling cruft that conventional chips have, with the cost of requiring the compiler to optimize code for them).
Just looks at current electro-optical devices used for various computing needs today: they have simple, elegant designs, fewer parts and are often smaller than their fully electrical counterparts operating at the same data transmission rates.
An electro-optical component is for the reasons mentioned previously bulkier than a transistor. They also, as mentioned previously, suffer from the limitations of both electrical and optical systems, because they incorporate both. Electro-optical components are indeed very useful for a moderate-sized set of applications; however, they aren't magical.
That is, encryption using a key of x bits could be broken by the non-deterministic machine trying all 2^x possible keys in parallel. I think I recall Bruce Schneier saying something to this effect in one of the "Crypto-gram" newsletters, but I may be misremembering. Any theorist slashdotters willing to comment?
If you have a good way of recognizing decrypted data, then you could indeed solve any fixed-key-size cryptographic problem in exponential time, just by counting through all possible keys and checking to see if you get readable data after using each one.
However, I'm not sure that a P=NP proof would help with this. You'd have to prove that iterating through each possible key is a problem in NP, as opposed to NP-hard and worse than NP-complete.
It might be better to analyze each cryptography algorithm separately, and see if you can prove any of them to be in NP. These would be vulnerable to a P=NP proof.
Quantum computers of the type previously described could certainly iterate through all of these keys within a reasonable length of time. The construction of practical quantum computers, OTOH, is left as an exercise:). It will be neat if it turns out to be practical.
As a side note, cryptography schemes that use a "one-time pad" of noise that they xor with the message would *not* be vulnerable to QC or P=NP attacks. If you iterate through all possible keys, you get all possible messages, which gains you nothing. Only if the key length is significantly shorter than the total amount of traffic sent will a brute-force search work. This is true for most cryptography systems, for practical reasons.
Could you point me to more info on the P=NP concept? Or if not, provide an explaination?
"P" and "NP" are categories of problem. P problems can by solved relatively quickly, but it isn't known if NP problems can or can't.
A problem is a "P" type problem (is "in P") if it can be solved in polynomial time or better; that is, the number of steps required to produce a solution for input of n bits is proportional to (or better than) n^k, for some _constant_ k. This might be a solution that's O(n), or O(n^2), or O(n^534), but it's still polynomial (or better, for something like O(log n)).
A problem is an "NP" type problem (is "in NP") if you can prove that your solution is correct in polynomial time. It might take polynomial time to solve or it might not, but you can prove the answer in polynomial time. The factoring problem is a good example of a problem in NP. No presently known way exists of finding the factors of a number in time proportional to a polynomial of the number of bits, but you can prove that two numbers (say a and b) _are_ the factor of a larger number (X) just by multiplying a and b and seeing if you get X. The multiplication time is proportional to (or better than) a polynomial of the number of bits in X (it's proportional to X^2 for the straightforward way). So, NP problems can be ugly, but there is a limit to how ugly they can get.
A problem that is "outside of NP" can't be solved in polynomial time (otherwise it would be in P) and has solutions that can't be checked in polynomial time (otherwise it would be in NP). I can't think of a good example off the top of my head, but they exist.
P is in NP; you can prove that a polynomial-time answer is correct just by solving the problem again. However, nobody knows if _all_ problems in NP can also be solved in polynomial time. This would mean that P = NP (the two sets of problems are the same, because everything in both of them is in P). A proof that P = NP would prove that any encryption scheme that depends on a trap-door function in NP is intrinsically weak. On the other hand, a proof that P != NP would prove that anything based on an NP-complete trapdoor function (I'll get back to this) is sound against anything short of a quantum computing attack. This is especially of interest to people who deal with prime numbers, because the factoring problem is in NP, and a P-time factoring algorithm would be a Very Useful Thing.
NP-complete problems are problems that are in NP, but that are at least as hard as anything else in NP (or more accurately, any other problem in NP can be reduced in polynomial-time to this problem). An NP-hard problem, for reference, is a problem like this that may or may not even be in NP at all (it's just at least as hard as anything in NP).
This brings up another very important point. All problems that are in NP can be reduced in polynomial time to any NP-complete problem. This means that if you can solve even one of the NP-complete problems in polynomial time, you can solve them all in polynomial time (just with worse exponents). An algorithm that solves an NP-complete problem, or a proof that no such algorithm exists, is one of the holy grails of mathematics, as it would settle the question of whether or not P = NP.
And I hope you've been taking notes, because there'll be a short quiz next period. O:) [ducks!]
The class of P-hard problems are soluble in polynomial time (for example n^3+2n^2 where n is the length of the input) by a deterministic Turing machine.
The class of NP-hard problems are soluble in polynomial time on a non-deterministic Turing machine. A nondeterministic machine will explore many possible solutions in parallel.
You can simulate a NDTM on a DTM with an exponential time penalty. A proof of P =? NP would presumably show us how to do this simulation without the massive time penalty. It's still an open question whether P = NP, but I wouldn't put any money on it being proved either way in the forseeable future.
Not that big a need to be paranoid...
by
zunger
·
· Score: 2
As the article pointed out, the huge bottleneck that the NSA (or anyone else) would have to solve in order to crack RSA for large key sizes is the ability to solve giant matrix equations quickly. We can probably guess that they haven't solved this part of the problem because that would lead to such extraordinary advances elsewhere - I'm thinking weapons and bomb development - that we'd be seeing much, much bigger and meaner things floating around out there if they had. Of course, you can still worry about quantum algorithms, which don't have a matrix-solving step... (Note to the paranoid: That was sarcasm. QC factorization algorithms are (a) not entirely proven - sources of noise, and possible very sneaky mathematical problems still may lurk and (b) not within twenty to fifty years at least of the capacities of any human technology.)
Remember, the NSA's about 10 years ahead us
by
starman97
·
· Score: 3
Note that the NSA 'suggestions' to DES turned out to be fixes to protect against an attack that was not discoered and described openly for more than 10 years after the DES was released. If this new RSA attack is out today, I'd have to assume that the NSA has had this sort of technology for at least 10 years.
Slashdot Mirror
is my 2048 bit key still safe?
I mean, when I was having PGP create my keys I decided that twice the "High" security would be good, so I made a 2048 bit key...
is it still secure? is it still excessive?
--Dave
But seriously, this was an interesting article. It just goes to prove that if you are using key sizes of less than 512 bits for public key cryptosystems, you may be vulnerable to advances in factoring rather than advances in raw processor speed.
The main advantage of this is that 512 bit keys can be factored in 9-10 weeks as opposed to 6-7 months with the previous application of this factoring method (described in the paper). This means that with this equipment and assuming that the estimate is correct, 768 bit keys can be factored in 1038 years (Shamir's estimate of 6000 * len(512)). A 1024 bit key would be factorable in approximately 1x10^6 years with this method and optimal conditions, however such a number requires exhorbitant space, upwards of 256 GBytes for the sieve 10 TeraBytes to store its matrices.
Bottom line, any key of 512 bits is good for about 9-10 weeks. The recommended minimum key size is still 1024 bits. The paper's conclusion sums this up best:
Conclusion The idea presented by Dr. Shamir is a nice theoretical advance, but until it can be implemented and the matrix difficulties resolved it will not be a threat to even 768-bit RSA keys, let alone 1024.Its more important to have the freedom to use strong encryption so that we don't have to worry about being forced to choose weak keys in order to communicate.
I don't think that's the point here. Even then, the "computation power" of the tank scales polynomially with it's size (at best).
So with regard to NP-trapdoor functions, all you have acheived is to raise the stakes a bit and have to start with, say, a 2048 bit key instead of 1024. But the fundamental problem is, that still some (fixed) number l of additional bits will double the effort for cracking. Take 1000*l bits and and every single atom in the universe can work on your problem in parallel until the hell freezes over. (Quantum computers may be a different thing though, but even that remains to be proven.)
OTOH *if* you really find a polynomial algorithm for some (arbitrarily weird) specific NP-complete problem, than you can apply this very algorithm to any problem in NP because NP-complete problems can be emulated by one-another with only polynomial overhead.
OK, I sat down and re-read the major sections of both Schiener and Knuth (to refresh my math memory), and then something that the Silverman's analysis jumped out at me:
Current (and expected future) uses of Number Sieve factorization (currently, the General Number Sieve is most efficient) are composed of two parts: the sieving of factors, and then solving a matrix of all the possible factoring equations.
For most of the time, the first operation has dominated in time; however, this first process is also the most ameniable to increases in speed.
As Silverman pointed out, the RSA-140 (465-bit) challenge required 4 weeks of 200 machines to solve, then about 4 days for a single super-fast box to solve the resulting matrix. Using Shamir's new methodology, we can expect a 512-bit number to be done in 5 weeks on 20 machines, with another 4 weeks to do the matrix.
The bottleneck has now become the matrix solution, which is a non-parallizable problem (for now). All that can be done on it currently is to use Moore's Law, which doesn't significantly affect the security of larger keys.
If anything, Shamir's invention will now push the focus of attacking RSA from dicovering the factoring equations (the "sieve" part) to improving the matrix solution problem.
The real danger here is from the NSA and other organizations that may have discovered a way to significantly parallelize the matrix solution. If they can do that, well, RSA is going to be screwed. However, there is no current indication that they can do this. But don't say I warned you.
For those paranoid, here are some relevant numbers on the now-dominant times to solve the matrix for relevant key-bit sizes (all assumptions are using 1999 hardware; divide all times by 10 for each 5 years that have passed to account for Moore's Law).
Remember, these numbers are NOT reducible by throwing more hardware at the problem - this is a (currently) serial operation, and must be done by a single machine. I don't see us being able to produce a single-CPU box a million times faster than state-of-the-art within the next two decades (Moore's Law predicts one about 2030 or so). By then, the memory requirements will be mundane. (if we can do 10GB now trivially, 10TB in 30 years shouldn't be any problem. In fact, we should be able to easily do 10TB about 2015 or so.)
In the end, 1024-bit keys should be immune to advances in sieving technology for at least 20 years. The worry is advances in matrix solutions, and development of methodologies better than Number Sieves. But, by the very nature of things, this is unpredictable.
Best Guess (and I'm not Bruce Scheiner): 1024 -bit should be immune to everything until at least 2015, after which 2048-bit should last to mid-century or so.
Happy Hacking!
-Erik
There are always four sides to every story: your side, their side, the truth, and what really happened.
If you're interested in quantum computation and cryptography you may be interested in checking out the Los Alamos site on quantum crypto.
Also some of you may be interested in Bruce Scheier's book Applied cryptography: Protocols, Algorithms, and Source Code in C, which was previously mentioned in other posts. You can find information on it at this Amazon.com link.
I might as well also give the link to a site on basic cryptology, called a "beginners page on cryptography" It may or may not help/interest readers.
On a side note, I really have enjoyed reading everyone's comments on this subject today. Hopefully these links don't come to late in the "day" for anyone to get good use out of them.
A very long time, though still just a linear factor longer. Your computer has to solve one hell of a huge matrix problem. This requires enough RAM to hold the matrix and any working data (gigabytes or _more_; see the article), and time proportional to the cube of the matrix size (or possibly better if you're using something other than Gauss-Jordan reduction).
They used a supercomputer to do the matrix solving. If your machine has n times fewer bogoMIPs, then it will take n times longer, assuming that you can support the required RAM.
Assuming that it is the matrix solution and not the sieving that limits the solution time. This would probably be the case if you're using a PC to process the matrix.
Today's "conventional PC" uses silicon-based CPU technology, but that will change in a few years when IBM begins to mass-produce copper-based chips.
IBM has already demonstrated chips with copper _interconnects_, and many manufacturers plan to use this technology, but I've never heard of using copper as a _substrate_. Conventional chips use a silicon _substrate_ and aluminum interconnects. What IBM technology are you referring to?
An "electro-optical" computational device is the next paradign shift in computer engineering. By transmitting data via light (LEDs!!!), the current CPU problems with heat, electromagnetic interference (EMI) and wafer size all disappear.
I'm afraid that this is not strictly true. In fact, feature size for optical components would be a big problem. Optical devices can't have features much smaller than a wavelength of light. For visible light, this is on the order of 0.5 microns. Electrical devices, like conventional integrated circuit chips, can have features that are much smaller. This tends to outweigh most of the advantages of using optical "chips", should such chips be developed. They would be bulkier, and wouldn't be faster, because while electrical signals propagate slower than light, they would have a much shorter distance to travel. If you try using light with a much shorter wavelength, you wind up destroying your substrate (the photon energy must remain lower than the energy required to dislodge an atom in in the device).
Heat dissipation is and will remain a problem for electrical devices, but photons get absorbed too.
Electro-optical devices, OTOH, get the worst of both worlds. The only situation in which they're really practical is when you need to send signals over a (relatively) large distance without much degradation, as is apparently the case with the computer being built here.
However, the original question was about the timings cited in the TWINKLE article:
I'm mildly confused by the timings, so how long would it take a decently powerful (as in, PII 300) machine hooked in to one of these devices to crack that?
My response stands for that, though as you point out these timings don't apply to other classes of encryption.
I hope you mean interconnects instead of substrates...
"They would be bulkier, and wouldn't be faster, because while electrical signals propagate slower than light, they would have a much shorter distance to travel. If you try using light with a much shorter wavelength, you wind up destroying your substrate (the photon energy must remain lower than the energy required to dislodge an atom in in the device)."
An electro-optical device does not use a silicon substrate, nor does it need the interconnect metals that we see today. Furthermore, the materials used for the device's internal parts and casing allow researchers to experiment with light wavelengths outside the visible spectrum.
My argument holds no matter what materials you use to build the optical device and no matter what processes are used to fabricate it. Whatever you do, you just _can't_ get the feature size of optical devices much smaller than the wavelength of the light used, or signals bleed from one computing element into another. Likewise, no matter what material you make the device out of, you can't have photons with an energy of more than a few eV, because that is the typical binding energy of valence electrons in atoms. If you decide to use deep UV or what-have-you, your device _will_ degrade due to atoms being dislodged and bonds being broken, no matter what it's made of.
But remember: Prof. Shamir's theoretical device is NOT A CPU! It is an "electro-optical sieving device"
How does this affect my points?
Because of its narrow function, the "TWINKLE" box will likely have a much cleaner, simpler design
This is true of any special-purpose computer. What of it?. See Deep Crack for an example, or look at DSP designs (they elminate a lot of the scheduling cruft that conventional chips have, with the cost of requiring the compiler to optimize code for them).
Just looks at current electro-optical devices used for various computing needs today: they have simple, elegant designs, fewer parts and are often smaller than their fully electrical counterparts operating at the same data transmission rates.
An electro-optical component is for the reasons mentioned previously bulkier than a transistor. They also, as mentioned previously, suffer from the limitations of both electrical and optical systems, because they incorporate both. Electro-optical components are indeed very useful for a moderate-sized set of applications; however, they aren't magical.
...But the question was _about_ times to crack RC4-128. I withdraw my comments... Doh.
If you have a good way of recognizing decrypted data, then you could indeed solve any fixed-key-size cryptographic problem in exponential time, just by counting through all possible keys and checking to see if you get readable data after using each one.
However, I'm not sure that a P=NP proof would help with this. You'd have to prove that iterating through each possible key is a problem in NP, as opposed to NP-hard and worse than NP-complete.
It might be better to analyze each cryptography algorithm separately, and see if you can prove any of them to be in NP. These would be vulnerable to a P=NP proof.
Quantum computers of the type previously described could certainly iterate through all of these keys within a reasonable length of time. The construction of practical quantum computers, OTOH, is left as an exercise
As a side note, cryptography schemes that use a "one-time pad" of noise that they xor with the message would *not* be vulnerable to QC or P=NP attacks. If you iterate through all possible keys, you get all possible messages, which gains you nothing. Only if the key length is significantly shorter than the total amount of traffic sent will a brute-force search work. This is true for most cryptography systems, for practical reasons.
"P" and "NP" are categories of problem. P problems can by solved relatively quickly, but it isn't known if NP problems can or can't.
A problem is a "P" type problem (is "in P") if it can be solved in polynomial time or better; that is, the number of steps required to produce a solution for input of n bits is proportional to (or better than) n^k, for some _constant_ k. This might be a solution that's O(n), or O(n^2), or O(n^534), but it's still polynomial (or better, for something like O(log n)).
A problem is an "NP" type problem (is "in NP") if you can prove that your solution is correct in polynomial time. It might take polynomial time to solve or it might not, but you can prove the answer in polynomial time. The factoring problem is a good example of a problem in NP. No presently known way exists of finding the factors of a number in time proportional to a polynomial of the number of bits, but you can prove that two numbers (say a and b) _are_ the factor of a larger number (X) just by multiplying a and b and seeing if you get X. The multiplication time is proportional to (or better than) a polynomial of the number of bits in X (it's proportional to X^2 for the straightforward way). So, NP problems can be ugly, but there is a limit to how ugly they can get.
A problem that is "outside of NP" can't be solved in polynomial time (otherwise it would be in P) and has solutions that can't be checked in polynomial time (otherwise it would be in NP). I can't think of a good example off the top of my head, but they exist.
P is in NP; you can prove that a polynomial-time answer is correct just by solving the problem again. However, nobody knows if _all_ problems in NP can also be solved in polynomial time. This would mean that P = NP (the two sets of problems are the same, because everything in both of them is in P). A proof that P = NP would prove that any encryption scheme that depends on a trap-door function in NP is intrinsically weak. On the other hand, a proof that P != NP would prove that anything based on an NP-complete trapdoor function (I'll get back to this) is sound against anything short of a quantum computing attack. This is especially of interest to people who deal with prime numbers, because the factoring problem is in NP, and a P-time factoring algorithm would be a Very Useful Thing.
NP-complete problems are problems that are in NP, but that are at least as hard as anything else in NP (or more accurately, any other problem in NP can be reduced in polynomial-time to this problem). An NP-hard problem, for reference, is a problem like this that may or may not even be in NP at all (it's just at least as hard as anything in NP).
This brings up another very important point. All problems that are in NP can be reduced in polynomial time to any NP-complete problem. This means that if you can solve even one of the NP-complete problems in polynomial time, you can solve them all in polynomial time (just with worse exponents). An algorithm that solves an NP-complete problem, or a proof that no such algorithm exists, is one of the holy grails of mathematics, as it would settle the question of whether or not P = NP.
And I hope you've been taking notes, because there'll be a short quiz next period. O:) [ducks!]
The class of NP-hard problems are soluble in polynomial time on a non-deterministic Turing machine. A nondeterministic machine will explore many possible solutions in parallel.
You can simulate a NDTM on a DTM with an exponential time penalty. A proof of P =? NP would presumably show us how to do this simulation without the massive time penalty. It's still an open question whether P = NP, but I wouldn't put any money on it being proved either way in the forseeable future.
As the article pointed out, the huge bottleneck that the NSA (or anyone else) would have to solve in order to crack RSA for large key sizes is the ability to solve giant matrix equations quickly. We can probably guess that they haven't solved this part of the problem because that would lead to such extraordinary advances elsewhere - I'm thinking weapons and bomb development - that we'd be seeing much, much bigger and meaner things floating around out there if they had. Of course, you can still worry about quantum algorithms, which don't have a matrix-solving step... (Note to the paranoid: That was sarcasm. QC factorization algorithms are (a) not entirely proven - sources of noise, and possible very sneaky mathematical problems still may lurk and (b) not within twenty to fifty years at least of the capacities of any human technology.)
Note that the NSA 'suggestions' to DES turned out to be fixes to protect against an attack that was not discoered and described openly for more than 10 years after the DES was released. If this new RSA attack is out today, I'd have to assume that the NSA has had this sort of technology for at least 10 years.
4096 bit keys anyone???
Starman97@Gmail.com (bring it on spammers)