tl;dr version -- RSA has not been damaged. RSA is still believed to be a safe algorithm. The world is not ending. Do not panic. Anyone who tries to use what I've written here to fearmonger about the future will make me Distinctly Displeased.
===== Some people have been asking me to explain what the significance of Boneh's paper is -- "he only proved that breaking low-exponent RSA may not be equivalent to factoring and he explicitly says it doesn't affect the security of RSA; why does this make you so concerned?" First, "concerned" is the wrong word to use. "Excited" is the right word to use. Why am I so excited? RSA is built on several different ideas. Let's enumerate them: The RSA Conjecture: "Breaking the RSA algorithm is equivalent to factoring." The IFP Conjecture: "Barring quantum computation, it will never be feasible to factor large composites except those that have some unusual and exotic properties." The RSA Conclusion: "Barring quantum computation, it will never be feasible to break RSA given a sufficiently large key that lacks unusual and exotic properties." The Ole Conjecture: "The sufficiently-large point is RSA-10k." Boneh's Commentary: "Y'all know the RSA Conjecture is false, right?" Dan Boneh's paper establishes -- IMO, pretty solidly -- that the RSA Conjecture is false, which means the RSA Conclusion is no longer logically sound. *That doesn't mean it's wrong*. If you think that things fall to the earth because invisible pixies seek to pull everything Underhill, proving that there are no invisible pixies doesn't mean you've taken gravity offline. If you make an arithmetic error while deriving Einstein's Theory of General Relativity, it doesn't follow that you can now drive to the grocery store at Warp 3. Proving the RSA Conclusion is no longer logically sound doesn't mean that it's false -- it only means we can't be sure it's true. RSA is still a strong, well-regarded cipher. Dan Boneh didn't damage RSA; he just revealed there was a great mystery here waiting to be solved. "There are ways to attack RSA that don't involve factoring. What are they, and are any of them easier than factoring?" The relevance of Boneh's work to long-term predictions about RSA should now be clear. In order to predict how long RSA will last, you have to come up with some guesses about what research will develop. If you guess that "no efficient non-factoring approaches will be discovered in the next 100 years," you might be able to have long-term confidence in even small (3072-bit) RSA keys. If you guess that "efficient non-factoring approaches to RSA will be discovered within 25 years," you might not be so sanguine. It is a *fascinating* time to be a crypto nerd. There are such amazing, intriguing, and -- yes, I'm nerdy enough to say it -- such drop dead *sexy* problems out there just waiting to be solved. This is just one of many! _______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users