Mixing
Is RSA inspired by Diffie Hellman?
up vote
3
down vote
favorite
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?
rsa diffie-hellman history
edited 19 hours ago
kelalaka
3,061828
asked yesterday
oRinga
282
New contributor
oRinga is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
3
down vote
favorite
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?
rsa diffie-hellman history
edited 19 hours ago
kelalaka
3,061828
asked yesterday
oRinga
282
New contributor
oRinga is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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
19 hours ago
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
16 hours ago
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
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?
rsa diffie-hellman history
edited 19 hours ago
kelalaka
3,061828
asked yesterday
oRinga
282
New contributor
oRinga is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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?
rsa diffie-hellman history
rsa diffie-hellman history
edited 19 hours ago
kelalaka
3,061828
asked yesterday
oRinga
282
New contributor
oRinga is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 19 hours ago
kelalaka
3,061828
asked yesterday
oRinga
282
New contributor
oRinga is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 19 hours ago
kelalaka
3,061828
edited 19 hours ago
kelalaka
3,061828
edited 19 hours ago
kelalaka
3,061828
3,061828
asked yesterday
oRinga
282
New contributor
oRinga is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked yesterday
oRinga
282
asked yesterday
oRinga
282
282
New contributor
oRinga is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
oRinga is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
oRinga is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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
19 hours ago
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
16 hours ago
add a comment |
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
19 hours ago
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
16 hours ago
1
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
19 hours ago
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
19 hours ago
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
16 hours ago
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
16 hours ago
add a comment |
2 Answers
2
active
oldest
votes
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.
answered yesterday
Ella Rose
14.3k43775
IMHO: "inspired by" implies more than "was aware of", which is essentially all you demonstrated.
– poncho
7 hours ago
@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
7 hours ago
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
7 hours ago
add a comment |
up vote
1
down vote
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.
answered 5 hours ago
kodlu
8,11811229
+1 for more background; Do you happen to know where the information in this book came from?
– Ella Rose
1 hour ago
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
answered yesterday
Ella Rose
14.3k43775
IMHO: "inspired by" implies more than "was aware of", which is essentially all you demonstrated.
– poncho
7 hours ago
@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
7 hours ago
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
7 hours ago
add a comment |
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.
answered yesterday
Ella Rose
14.3k43775
IMHO: "inspired by" implies more than "was aware of", which is essentially all you demonstrated.
– poncho
7 hours ago
@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
7 hours ago
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
7 hours ago
add a comment |
up vote
10
down vote
accepted
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.
answered yesterday
Ella Rose
14.3k43775
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.
answered yesterday
Ella Rose
14.3k43775
edited 7 hours ago
answered yesterday
Ella Rose
14.3k43775
answered yesterday
Ella Rose
14.3k43775
answered yesterday
Ella Rose
14.3k43775
14.3k43775
IMHO: "inspired by" implies more than "was aware of", which is essentially all you demonstrated.
– poncho
7 hours ago
@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
7 hours ago
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
7 hours ago
add a comment |
IMHO: "inspired by" implies more than "was aware of", which is essentially all you demonstrated.
– poncho
7 hours ago
@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
7 hours ago
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
7 hours ago
IMHO: "inspired by" implies more than "was aware of", which is essentially all you demonstrated.
– poncho
7 hours ago
IMHO: "inspired by" implies more than "was aware of", which is essentially all you demonstrated.
– poncho
7 hours ago
@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
7 hours ago
@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
7 hours ago
1
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
7 hours ago
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
7 hours ago
add a comment |
up vote
1
down vote
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.
answered 5 hours ago
kodlu
8,11811229
+1 for more background; Do you happen to know where the information in this book came from?
– Ella Rose
1 hour ago
add a comment |
up vote
1
down vote
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.
answered 5 hours ago
kodlu
8,11811229
+1 for more background; Do you happen to know where the information in this book came from?
– Ella Rose
1 hour ago
add a comment |
up vote
1
down vote
up vote
1
down vote
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.
answered 5 hours ago
kodlu
8,11811229
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.
answered 5 hours ago
kodlu
8,11811229
answered 5 hours ago
kodlu
8,11811229
answered 5 hours ago
kodlu
8,11811229
answered 5 hours ago
kodlu
8,11811229
8,11811229
+1 for more background; Do you happen to know where the information in this book came from?
– Ella Rose
1 hour ago
add a comment |
+1 for more background; Do you happen to know where the information in this book came from?
– Ella Rose
1 hour ago
+1 for more background; Do you happen to know where the information in this book came from?
– Ella Rose
1 hour ago
+1 for more background; Do you happen to know where the information in this book came from?
– Ella Rose
1 hour ago
add a comment |
oRinga is a new contributor. Be nice, and check out our Code of Conduct.
oRinga is a new contributor. Be nice, and check out our Code of Conduct.
oRinga is a new contributor. Be nice, and check out our Code of Conduct.
oRinga is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f64155%2fis-rsa-inspired-by-diffie-hellman%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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
19 hours ago
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
16 hours ago