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