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.
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.
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!]
Slashdot Mirror
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.
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 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!]