I read a bit of A Method for Obtaining Digital Signatures and Public-Key Cryptosystems that introduced RSA in 1977, and, while learning the steps in RSA a few days ago, I noticed that they are similar to the Diffie-Hellman key exchange. Was RSA inspired by Diffie-Hellman, published the year before in 1976, as in does the cryptography rely on earlier work and re-use parts from Diffie-Hellman and modular exponentiation, and the secret being the inverse of the encrypted message?

  • 1
    The similarity between RSA and Diffie-Hellman key exchange are primarily the use of modular exponentiation, and not requiring a pre-shared secret. The rest is very different: the nature of the cryptographic service (encryption or signature vs key establishment), the underlying difficult problem (factoring vs discrete logarithm), the properties of the public modulus (composite of unknown factorization vs prime or composite of known factorization). – fgrieu Nov 19 at 8:15
  • According to The Code Book by Simon Singh, it was directly inspired by it. I haven’t got the book handy at the moment, hence this is only a comment, and without page reference. I also don’t remember what (if any) reference Singh cited for this but he’s usually pretty thorough. – Konrad Rudolph Nov 19 at 11:27
up vote 10 down vote accepted

Was RSA inspired by Diffe-Hellman, published the year before in 1976

In "The first ten years of public-key cryptography", the following social relationships are mentioned:

Ron Rivest had been a graduate student in computer science at Stanford while I was working on proving the correctness of programs at the Stanford Artificial Intelligence Laboratory. One of my colleagues in that work was Zohar Manna, who shortly returned to Isreal and supervised the doctoral research of Adi Shamir, at the Weitzman Institute.

So Rivest went to the same school where Whitfield Diffie was working, and Zohar Manna apparently brought the knowledge to the attention of Adi Shamir.

So they certainly must have been aware of Diffie and Hellman's work.

In fact, the original paper on RSA cites the paper "New Directions in cryptography" by Diffie and Hellman, so that's pretty much a smoking gun that proves that they were building off the work of Diffie and Hellman.

  • IMHO: "inspired by" implies more than "was aware of", which is essentially all you demonstrated. – poncho Nov 19 at 19:58
  • @poncho Well, I felt that the citation effectively showed they were building off the prior work. I'm unfortunately not aware of any more related histories/papers to help make the case. – Ella Rose Nov 19 at 20:48
  • 1
    Papers are generally expect to reference any similar previous work in the area, whether or not the previous work was actually used as an "inspiration" of the current work; hence the citation is at best ambiguous answer to the question. I would poar an answer myself, however I don't remember Rivest or Shamir actually talking about this (and they're really the only ones who can say for certain) – poncho Nov 19 at 20:51

Great question!

I had read this years ago, and a quick look confirmed the inspiration:

From Steven Levy's Crypto, a book on the modern development of civilian cryptography

prime time

“Here's something interesting. . . .”

A casual handoff of an academic paper from a graduate student to a professor. Ron Rivest, a twenty-nine-year-old assistant professor at the Massachusetts Institute of Technology, had no reason to believe that this paper was any more interesting than the hundreds of papers, articles in journals, and technical memos he had already seen in his nascent career in academia. One of its authors, Whit Diffie, had worked in the same building — Tech Square in Cambridge, where the AI lab was one floor above Rivest's office at the Laboratory for Computer Science. But neither that name nor that of the coauthor, Martin Hellman, was familiar to him. And actually, Rivest knew very little about encryption and virtually nothing about how sensitive a topic it was. Nor did the paper contain any breakthroughs in mathematical reasoning; the spirit of Fermat was nowhere to be found in its equations. Even so, “New Directions in Cryptography” turned out to be more than interesting to Rivest: it thrilled him. Ultimately, it changed his life. The paper appealed to Rivest's heart as well as his head. Rivest was a theoretician, but one for whom simple abstractions were not enough. The ideal for him was actually putting the ethereal mechanics of math to work, of making a tangible difference in the world of flesh and dirt. Diffie and Hellman's breakthrough wedded the spheres of abstraction and reality, applying an original mathematical formula to meet a need in society. Ron Rivest wanted to spend his time in the neighborhood where those two realms met.

note: Rivest was a PhD student in Stanford, supervisor Knuth, as an aside]

[.. part about Rivest's PhD on robotics omitted ..]

At twenty-seven, he seemed poised to begin a productive yet quiet life as an academic in one of America's best scientific institutions. From his eighth-floor window in the boxlike Tech Square building in Cambridge, he would watch the gorgeous campus sunsets, their drama enhanced by pollution spewed out by Boston-area industry. And then he would return to his algorithms. In December 1976, and throughout that entire winter, the algorithms Rivest grappled with were the ones suggested by Diffie and Hellman's “interesting” paper. It might be more accurate to say that he was consumed by the formulas missing from that cryptologic manifesto. While the two Stanford researchers had indeed presented a mathematical outline for a new way of passing secret messages — and also digitally “signing” messages so that a communication could be definitively associated with its author — when it came to an implementation that one could really use, they'd come up dry. The Diffie-Hellman key exchange approach allowed two parties to set up a common key, but there was no obvious way that it could be extended to signatures. (Merkle's not-yet-published knapsack solution also fell short of this.) Diffie and Hellman had speculated on various ways that one might eventually come up with a workable system where each individual could have his or her own key pair, one public and one kept secretly. But without the proper mathematical scaffolding, it was really nothing more than a suggestion. It all hinged on finding sufficiently powerful one-way functions. Was there indeed a set of these that could stand as the reliable scaffolding of a volks-cryptosystem? A set of functions so sound that the system based on them would be impervious to all sorts of eavesdroppers and codebreakers, even highly motivated ones equipped with high-speed computers, deep cryptographic experience, and a touch of genius themselves?

Answering those questions became Rivest's obsession.

  • 1
    +1 for more background; Do you happen to know where the information in this book came from? – Ella Rose Nov 20 at 2:32

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.