Is RSA inspired by Diffie Hellman?

Question

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?

Answer 1

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

Update

I met Ron Rivest at MIT's LCS35 time capsule unveiling and asked him this question for you.

The answer is yes.

Original Answer

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.

Answer 2

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.