RSA Conjectures

[Robert J. Hansen]

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!