Skip Links

Crypto researcher Arjen Lenstra shares thoughts on paper blasting RSA cryptosystem

Lenstra: 'If the environment cannot provide enough entropy during key set-up, then RSA becomes a tricky choice'

By , Network World
February 17, 2012 01:43 PM ET
Arjen Lenstra

Network World - What a week for the RSA cryptosystem! A group of prominent researchers published a paper blasting it as woefully insecure, RSA said there's nothing wrong with the RSA algorithm, it's an implementation issue mainly with random-number key generation, and now the cryptography researcher behind the paper, Arjen Lenstra, signs off the week with a few thoughts about it all.

BACKGROUND: RSA brushes off crypto research findings that RSA algorithm is flawed

"If properly implemented, RSA is fine," said Lenstra, the well-known crypto researcher who worked with James Hughes, Maxime Augier, Joppe Bos, Thorsten Kleinjung and Christophe Wachter on the remarkable project that included examining millions of X.509 public-key certificates that are publicly available over the Web.

That study (explained in the "Ron is wrong, Whit is right" paper) had the researchers examining 6.4 million distinct X.509 certificates and PGP keys containing RSA moduli, and "we stumbled upon 12,720 different 1024-bit RSA moduli that offer no security." They said that "their secret keys are accessible to anyone who takes the trouble to redo our work."

The paper concluded: "Overall, over the data we collected, 1024-bit RSA provides 99.8% security at best." It also compared RSA to "single secret" cryptosystems such as ElGamal and DSA, based on Diffie-Hellman (DH), saying these are "less risky" than cryptosystems based on RSA.

"The recommendation is to use a cryptosystem that is appropriate for the environment where it will be used," said Lenstra in an email exchange with Network World. "If the environment cannot provide enough entropy during the key set-up, then RSA becomes a tricky choice. RSA itself is fine -- it is the way it us used/implemented/whatever you want to call it, that is the problem. Other crypto (DSA and such) have that too, but in subtly different ways."

The concept of "entropy" in the science of cryptography is roughly analogous to "uncertainty," he says, based on mathematical outcomes. "Lots of tricks have been invented, but getting enough entropy on a device is still a very tricky problem," he points out.

Lenstra said, "Apparently, the consideration that adequate entropy needs to be present when generating RSA keys has not consistently been taken into account (most commonly on embedded devices, but unfortunately not only in those environments). As far as I can tell, everyone is in full agreement on this issue."

As far as there being a "clear distinction between RSA and Diffie-Hellman based methods such as ElGamal and (EC)DSA," Lenstra points out, the research outlined in the paper underscores "that the effects of poor entropy are different for the two types of methods: for the latter, the parties using the same poor entropy can breach each other's security (as it may result in identical keys), for the former anyone may be able to breach the security of any pair of parties that use poor entropy (namely, if it results in non-identical but intersecting keys -- the latter does not occur for the DH-type methods). As far as I'm aware, this distinction has not been pointed out before."

Our Commenting Policies
Latest News
rssRss Feed
View more Latest News