Secure Communications over Insecure Channels (1974) |
By Ralph Merkle |
With an Interview from the year 1995 |
Edited by Arnd Weber |
Version of 16 January 2002 |
| Table of Contents | |
|---|---|
| I. | The Puzzles System as First Conceived in 1974 |
| II. | A Paper of 1974 Describing the Puzzles System |
| III. | A Version Prepared for Submission |
| IV. | An Interview with Ralph Merkle |
This documents contains several drafts of Ralph Merkle's paper on "Secure Communications over Insecure Channels", which was finally printed in the Communications of the ACM of April 1978 (pp. 294-299). Furthermore, it contains an interview with Ralph Merkle.
This document is meant to provide additional details for the interested reader of:
Or of
Related material can be found in
Diffie, W. Interview on the Development of Public Key Cryptography. Conducted by F. Furger (1992). Edited by A. Weber (1998).
For illustration of the innovative environment Merkle was in, see the picture of a nuclear powered ramjet his father was working on in California. (Illustration by Paul DiMare, in: Gregg Herken: The Flying Crowbar. Air & Space Magazine, April/May 1990, Volume 5 No. 1, page 28.
Available at http://www.merkle.com/pluto/pluto.html.)
Note from editor: In this section, Merkle describes the method as he first conceived it in 1974.
"The method as I first conveived it was: generate roughly k random numbers from a space of about k2 possible numbers. Apply a one-way hash function to these k random numbers and transmit them from A to B. B then generates random numbers from the same space of k2 possible numbers and applies the same one-way hash function until there is a 'collision,' i.e., B accidentally generates one of the same random numbers that A generated. The probability of such a collision is surprisingly high (check the Birthday Paradox). B then encrypts further messages with the common random number. A, to determine which random number is correct, tries all k random numbers that it generated on some test message encrypted by B.
This original method was simple, but inefficient."
(from a letter of Ralph Merkle to the editor, dated May 18, 1995)
The usual method of transmitting a message over an insecure communications channel, and insuring that the message is not understood by an enemy, is to encrypt it. All such methods depend, for their effectiveness, on information which is not known to the enemy: the key. If the key is known to the enemy, then the message can be decrypted. Currently, the key must be transmitted over a secure communications channel of some sort. A courier might be sent with the key in a pouch. It would be more convenient if the key could be transmitted over an insecure channel. It would seem self evident, that if the key is transmitted over an insecure channel, then it must be known to an enemy. This, however, is not the case. If the key is transmitted in the proper fashion, then the amount of work required of any enemy to determine the key would greatly exceed the effort put in by the two communicants in establishing the key.
The problem can be stated more precisely as follows: A and B wish to communicate over an insecure communications channel. E can listen to any message transmitted by either A or B. E cannot modify the messages transmitted, nor can E transmit false messages. Any information initially known to either A or B is known to E. E will not be able to learn any new information which either A or B might generate.
This situation might arise if A and B have just suffered a massive breach of security, which has since been sealed. While E knows what A and B knew, and also knows what they are saying, he no longer can find out what they are thinking. A and B wish to develop further plans in privacy, but E can now listen to everything they say. How do they do it?
The method depends on a technique known as one-way encryption. Normally, when a message is encrypted, knowledge of both the key and the method allows decryption. This is not the case with one-way encryption methods. Knowledge of the key, and the method, and the encrypted message, will yield nothing. The only practical way to decrypt such a message is to have the original message, encrypt it, and compare the result with the encrypted version already known. If they should match, then the message has been decrypted.
One-way encryption allows A and B to compare notes, so to speak, without E being able to understand. If A and B should both chance to one-way encrypt the same message, and transmit the encrypted version to each other, then they will both know what the original message was. E will be able to determine it only with difficulty.
The method can be viewed as a search strategy, which attempts to reduce the effort A and B will have to go to, before such an event takes place.
In overview, the method can be described as follows: A generates K puzzles. These puzzles are transmitted to B. B selects one of these puzzles at random, and solves it. A and B are now both in possession of a common piece of information, the solution to the puzzle which B solved. If it requires 1 unit of work to generate each puzzle, and K units of work to solve each puzzle, then both A and B have put in K units of effort. E, however, does not know which puzzle B solved, and must, therefore, solve all K puzzles. Thus, E must expend K units of effort to solve each of K puzzles, for a total of K2 units of effort.
In detail, a method is as follows: A and B agree on a normal encryption function, F, and a one-way encryption function, G. Both F and G are known to E.
Where k is a key, m is a message, and r is the result of the encryption process. A then selects a key for use with the encryption function, F. Call this key P. P is known only to A. A and B agree, together, on a key for the one-way encryption function, G. Call this key Q. Q is known to A, B, and E. A now transmits K messages to B. These messages are:
B selects one of these messages at random, say the jth message. B knows this message is of the form:
B can find x simply by trying all possibilities. B can then transmit this x, in the clear, to A. A can apply the decryption function, F-1, to x, and determine j:
This number, j, can now be used as a key by both A and B in further communications. E can determine j only by examining all the messages sent by A, in exactly the way B examined the jth message.x)
A number of variations on this basic theme are possible. All have in common, however, the expenditure of order K units of effort by both A and B, but K2 units of effort by E. The method shown need use only a modest amount of memory: order log K + a small constant.
x) In the Winter of 1974/75 Merkle crossed the last four sentences out and overwrote them with: B transmits G (S,(K*x+j)) with S randomly selected, known to A, B, E. (from a photocopy of Ralph Merkle)
Note from editor: This section contains a version, from the summer of 1975, which Merkle had prepared for submission to the Communications of the ACM.
When two people wish to communicate over some distance, they will send some form of message. To prevent some enemy from understanding the message, they can encrypt it. If the enemy were to learn the encryption method, he could read the message. It would seem obvious that the method of encryption cannot be transmitted, in the clear, over the communications channel, and still be useful. This, however, is not so. If the two communicants transmit the encryption method in the proper fashion, then they will be able to understand what is going on, but any enemy will become hopelessly confused. This can be done with a modest, and virtually fixed amount of memory.
Secure Communications, Privacy Transformation, Encryption
When two people wish to communicate over some distance, they will send some form of message. When they fear that some enemy, who they do not wish to read the message, might intercept it, then they will encrypt the message. The enemy will then be unable to understand the message, even if he intercepts it, because he does not know how it was encrypted. If the enemy were to learn the encryption method, then he could read the message. Thus, the two people can communicate securely because they have information which is not known to the enemy. This implies that the two people, (call them A and B), have made some form of prior arrangement, while E was unable to listen in. It would thus appear that a necessary precursor to a cryptographically secure communications channel between A and B, is the making of prior arrangements, or the communication of information over some very special communications channel which is known to be secure already. This is not in fact the case. If A and B have made no prior arrangements, and E can listen to all communications between A and B, they can still establish a cryptographically secure communications channel. The work required of E to break the encryption will increase as the square of the work required of A and B to establish the link. The rest of this paper will describe how this can be done, and some of the possible implications.
Two agencies, be they computers, people, institutions, or whatever, wish to communicate securely. These two, A and B, have available a communication channel with the following properties:
In addition to this, through some massive breach of security by both A and B, E is aware of everything that A and B know. This security breach has just been sealed, and E is no longer able to find out information known to A and B, unless they transmit it on the communications channel. A and B have no other means of communication. How can A and B reestablish a cryptographically secure communications link? How can A and B make further plans, with the confidence that E cannot know about them?
A can create a number of "puzzles", say N of them. A can then transmit these N puzzles to B, who will discard all but one of them. B will solve this one puzzle. A and B are now in possession of a common piece of information: the solution to the puzzle that B selected. E cannot know which puzzle B solved, and to find out, E will have to solve all N puzzles. If A created the puzzles in such a manner that it requires N units of effort to solve each puzzle, but only 1 unit of effort to make each puzzle, then E must spend N2 units of effort to solve all the puzzles, while A will only put in N units of effort to create the N puzzles, and B will only put in N units of effort to solve the one puzzle he selected. Once A and B have this common piece of information, they can use it as the key in any one of a number of encryption schemes.
Let A select an encryption function, call it F. A will not transmit F to either B or E, only A will know what F is. Let A and B agree on an encryption function, G. They will send a courtesy copy of this function to E, so that A, B, and E all know about the encryption function, G. G will have the following format:
i.e., G is a function of two arguments: the message it must encrypt, and the key used in the encryption.
A will now create the N puzzles in the following fashion:
K is simply a constant term, which will remain the same for all messages. K is known to A, B, and E. The Xi are selected by A at random. The Ri are the "puzzle" part, and are also selected at random. However, Ri must be selected from the range (N*(i-1), N*i). That is, N*(i-1) is less than or equal to Ri which is less than N*i. The purpose of the various components of the message is as follows. The Ri are the "puzzle" part, that B must guess at. For each message, there are N possible values of Ri. If B tries all of them, he is bound to chance upon the right value. This will allow B to recover the message within the puzzle: the triple (K,Xi,F(Xi)). B will know that he has correctly decoded the message because the constant part, K, provides enough redundancy to insure that all messages are not equally likely. Without this provision, B would have no way of knowing which decoded version was correct, for they would all be random bit strings. Once B has decoded the puzzle, he can transmit Xi in the clear. F(Xi) can then be used as the encryption key in further communications. B knows F(Xi) because it is in the message. A knows F(Xi) because A knows Xi , which B transmitted in the clear, and also knows F, and so can compute F(Xi). E cannot determine F(Xi) because E does not know F, and so the value of Xi tells E nothing. E's only recourse is to solve all the N puzzles until he encounters the 1 puzzle that B solved.
It might happen that E stumbles upon the correct puzzle rather rapidly. To reduce this probability to an acceptable level, it suffices to have B solve a few puzzles. E must then stumble upon all the puzzles before he can decrypt the messages that A and B will send. It might also be advisable for A and B to select a new function G each time, so that E will not be able to devote a large effort to the analysis of this particular function, and so reduce the amount of time required to solve a puzzle. A would also be well advised to change F frequently.
This interview has been conducted by Arnd Weber on May 18, 1995
| Interviewer | How did it happen that you developed the multi-puzzle system? |
| Merkle |
I was taking a course from Lance Hoffman on data security and privacy. October 1974, 'Computer Security Engineering Lecture Notes - University of California 1974, Professor Lance J. Hoffman, Department of Electrical Engineering and Computer Sciences, Computer Science Division, University of California, Berkeley.
[1]
So that was the course I was taking.
I began thinking about various core projects, so I thought about it for a while and realized, as I was thinking about this, that if I wanted to communicate over an open channel...
And one night I was contemplating how it is that... What was the problem that I was considering specifically? I think I was trying to figure out the problem of you're trying to log into a computer in some secure fashion and the computer security has been compromised and has since been sealed up again. I was trying to figure out how to re-establish secure communications. And as I was thinking about it, it basically occurred to me that I was unable to prove that full disclosure of the complete state both of the computer and of the person communicating with it (and presumably they would have a terminal with which they were communicating with a computer) it occurred to me that I was unable to prove that under those circumstances, security would necessarily be compromised. So I began trying to figure out, was there some way of showing clearly that if you compromised both computer and the terminal which was communicating with the computer, whether you could then prove that in the absence of some secure channel, some secret channel like a courier, whether you could prove that in fact security had been compromised. And as I thought about it, I realized that not only could I not prove it, it was not even clear that it was correct. So I began thinking about it, and then over the next few days I figured out the puzzles technique. |
| Interviewer | Within a few days? |
| Merkle | Yeah, the basic outline. I sort of worked on it later, but the basic outlines of it came out fairly quickly. Once I realized the problem was in fact soluble, at least that it was clear that there was no proof that it was insoluble, things fell into place fairly quickly. The first realization, of course, was that if both the computer and the terminal were deterministic, then of course you could compromise the system, if you knew the initial state and you knew the traffic over the communications line. So I fairly quickly concluded that there had to be some random component. And then it was simply a question of how to utilize that random component in a way which would provide confusion to the eavesdropper that would grow more rapidly than the confusion of either the two parties communicating. So, and then of course I - we were supposed to do a quarter project - so I wrote that up as a quarter project. And as I wrote that up as a quarter project there were supposed to be two projects proposed. I suggested both the 'secure communications over insecure channels' and also suggested 'data compression', and unfortunately, Lance Hoffman didn't understand what was going on and suggested I do data compression. So I tried again and wrote it up more clearly. In fact, when I showed it to a friend of mine, a teacher, and I'm blocking on his last name... |
| Interviewer | Blatman |
| Merkle | Blatman, Peter Blatman, yes. So, when I showed it to Peter Blatman I said... By the way, Peter was the one who first put me in touch with Diffie and Hellman at Stanford. If I recall, I was explaining this stuff to him he said; 'You know, there's some folks at Stanford who talk just like you.' If my memory serves, I'm probably simplifying somewhat, that's my memory of the conservation. But basically, when I showed the draft to Peter Blatman and said: 'This is what I am going to show to Lance Hoffman', he read through it and said; 'Whoa, you mean you really, you're really saying, listen up dummy. This is what's going on and what I want to do'. And I sort of said; 'Yeah' because by that time I had been through, I think, two iterations or three iterations and Lance hadn't quite caught on. Lance rejected it again, saying I should work on data compression. And I gave up on Lance and dropped the course and continued working on the, on what eventually became called public key distribution. So, that was sort of the initial event. Surprisingly, I at that time, I had no particular background in - well, perhaps not surprisingly - I had no particular background in cryptography. So I simply, somehow, managed to get interested in the problem and then worked on it. So, that's sort of the initial state of affairs. |
| Interviewer | When did the privacy issue come in? |
| Merkle | Basically it fairly rapidly evolved, into the communication. I mean my initial interest was, you know: You're trying to talk to a compromised computer, but if you are trying to talk with a compromised computer and you're trying to re-establish security in both, and everything's been compromised, not only the computer but also on the terminal, and if you assume that there's no prior memory on the terminal, then you rapidly wind up with sort of a public key distribution problem. So, my initial interest was drawn by what happens if you compromise a computer. But then I broadened that fairly promptly to: 'What happens if you compromise both a computer and the terminal?' And at that point you're looking at the classic public key distribution problem. So, basically, I forget the exact details, but I do remember being up late one night, around eleven or twelve, and realizing: 'Oh, my God, it looks like I can even solve this problem with the assumption that both the computer and the terminal are compromised.' And that, of course, immediately generalize to: 'Well, if you have two people who are communicating with each other - anywhere under any circumstances - and they want to be private, and we assume there is no prior secret communications, then, how do we do it?' |
| Interviewer | You mentioned that Lance Hoffman had apparently in his seminar something like privacy. Was that initially important or did that come in later? |
| Merkle | My memory was that it had privacy and data security; but my memory might be false. The actual notes for the course - which I am now staring at - the course notes say: Computer Security and Engineering. And all I have here is, in my notes that I wrote down, it says: CS 244, Lance Hoffman, 1974. So, if I recall, there was something about privacy in the course, but I might be mistaken. I would have to got back and actually get hold of the course announcement or something. But it was sort of the standard computer security course that Berkeley was offering at that time. |
| Interviewer | Could I get a copy of your original paper which you submitted to Lance Hoffman? |
| Merkle |
I don't have a copy of the original one that went to Lance. I have an undated copy that fairly clearly was done in the period between the time that I initially realized it and the time that I submitted it to Lance. Let's take a look at that one. Okay, I have an undated copy that is listed in the course, that is in the course notebook that I had. Let's see:
'The usual method of transmitting messages over an insecure communications channel' okay, defines the problem 'the method depends on the technique of encryption' blah blah... 'A generates K puzzles. These puzzles are transmitted to B. B selects one of these puzzles at random and solves it. A and B are now both in possession of a common piece of information. In detail ... encryption function, F, and an encryption function G.' Okay, so then it discusses it and has some scribbled up notes here, this is, I believe, a version that was done after I originally devised it and probably before dropping the course. Uhm, but unfortunately it has no date on it, on the page itself. So I don't know, but it was in my course notebook for that time. I can send you that copy. |
| Interviewer | That would be nice. [document above] |
| Merkle |
Okay. And then it goes, let's see, and then there are various copies, I have the submitted copy, of course, when I submitted to CACM. There was a copy, let's say, an initial copy. I have the comments from the referee. Where is the paper? Oh, I have the comments from Susan Graham on October 22, 1975.
'Enclosed is a referee report by an experienced cryptography expert on your manuscript, Secure communications over insecure channels. On the basis of this report, I am unable to publish the manuscript in its present form in the communications of the ACM. I also read the paper myself and was particularly bothered by the fact there are no references to the literature. Has anyone else ever investigated this approach? If they consider it and reject it why?' |
| Interviewer | Sorry, who's she? |
| Merkle |
This is from the Editor, Susan Graham... So I was not citing the prior literature on public key cryptography which, of course, did not exist. 'Has anyone else ever investigated this approach? If they consider it and reject it, why?' So, she was, and the referee's comments are: 'Thank you very kindly for your communication of October 7, with the enclosed paper on Secure communications over insecure channels. I am sorry to have to inform you that the paper is not in the mainstream of present cryptography thinking and I would not recommend that it be published in the Communications of the ACM for the following reasons: The paper proposes to describe cryptographic security by transmitting under various unrealistic working assumptions, puzzles conveying key information, a puzzle which is just another word to talk about a cryptosystem. The strength of the system hinges strongly on the quality of the puzzle transformation, these are not defined.' In as much as I was using standard cryptographic functions it was not necessary to define those - simply as an off-the-shelf cryptographic function. Second item by the referee was: 'Experience shows that it is extremely dangerous to transmit key information in the clear. Such practices of the legitimate user open the setup to illegitimate test procedures which only a very strong system could resist. Again, the nature of the cryptographic system is not specified.' So basically the referee blew it. He just totally didn't understand what was going on, and was absolutely at sea. And the referee's response was October 7, and Sue Graham's letter was dated October 22nd, both 1975. Basically what happened is: I submitted the paper. It was rejected. I submitted it. It was rejected. The initial rejection said: 'This is not in keeping with current cryptographic thinking.' As you heard, the later rejection said; 'This is unclear. It's incomprehensible.' The final rejection said; 'This is obvious. It should be made shorter.' |
| Interviewer | The initial referee? |
| Merkle | Yes, what I read you was the initial referee's rejection. |
| Interviewer | The final referee said 'It's obvious.'? |
| Merkle | Oh, yes, a few years later. Well, basically the process took several years. So I would submit the paper and it would be rejected and then I would submit it and it would be rejected. The final rejection basically was actually, the final - it wasn't a rejection, it was basically a qualified acceptance. The final one said 'Look, this idea is a simple idea and the author must make the paper much, much shorter.' |
| Interviewer | Did this lead to the final publication in ... |
| Merkle | Yes. It was finally published in 1978 [Secure Communications Over Insecure Channels. Communications of the ACM, April 1978]. Its got a little note saying that it was originally submitted in 1975. So, from the time of submission to the time of publication was three years, and those were fairly fast moving three years. You know, I'm not finding the original version of the paper as submitted. I'm finding the rejection by the referee; I'm finding my comments on the rejection by the referee but I'm not finding the original paper. At the time I did this of course, I had no idea that it would create such a fuss - it would be viewed as so significant - I'd have kept all this stuff more carefully. I don't seem to have a copy of the early version of the paper. But what you might do is to contact Susan Graham and ask her if she retained a copy of the first submission as part of her duties as editor. And if she did, then you can get a copy at least of the version as it was submitted to CACM. And I have this undated version which I believe was done between the time I originally concocted the idea and the time I dropped the course. I can just copy this and send it to you. So this would be the earliest copy of the Secure communications over insecure channels. And this is clearly well before any version submitted for publication. It's just two pages. |
| Interviewer | It's just two pages? |
| Merkle |
It's not a complicated method. The basic idea is fairly short. It was more complex, the scheme I described here. Let me take a look on the scheme and see if I recognize it:
' F(k,m) = r r in 1 .. K Let's see. Does this actually work?
'k is a key and m is a message and r is the result of the encryption process. A then selects a key for use of the encryption function, F. Call this key P. This seems a little baroque. Nonetheless, it has the various components in it.
'G(Q, (K*F(P,i)+i)) ... Okay, so it has the basic method here. I'd have to go over it to see if I've made any mistakes. 'A number of variations on this basic theme are possible. All have in common, however, the expenditure of order K units... modest amount of memory + a small constant.' Yeah. This is clearly one of the earlier version because as I said, the paper grew longer the more I worked on it. With each rejection I tried to make the concept clearer and simpler, included more straightforward explanations, until eventually the final paper was regarded as too large and spending much too much time explaining obvious ideas. What happened is fairly obvious. What happened is that everyone looked at it, couldn't understand it, rejected it, and eventually the Diffie / Hellman paper came out, New Directions in Cryptography, and that one basically was the paper that finally people began to understand. And then, of course, once people understood it and said: 'Oh, this is an important concept.', everyone began to realize what was going on. So I think basically what happened is: my paper was rejected until the concepts were made popular, and then the referee clearly heard about the concept somewhere else and then decided: 'Okay, seeing as how I already know the concepts, I can now announce that this paper is a fine paper.' So, by the by, I am a supporter of the Web. I think the World-wide Web is a fine idea. And self-publication electronically is splendid, and lets you by-pass all of this nonsense. |
| Interviewer | Oh, as opposed to the situation at the time. |
| Merkle | Where I had to go through journal publications and where the journal would then be able to reject the paper and I would not be able to obtain any broader audience for it. It's a pity this version doesn't have a date on it. |
| Interviewer | Would it be correct to say that it is from '74 or '75? |
| Merkle | It's clearly either. It's probably fall '74. Because the course would have been largely over by the end of '74. So my suspicion is that this is one of the drafts I wrote attempting to persuade Lance to have me pursue the idea. But certainly it was either late '74, certainly it was no later than early '75. Because by 1975 I'd submitted for publication in the Communications of the ACM. And this clearly predates the submission. Because it's short and it still has scribbled notes on it and it doesn't, doesn't quite have the, you know, if it were to be submitted, it would have a few more things on it that would say, you know, this is submitted and da, dada, dada. |
| Interviewer | When you thought about the multi puzzle system, were you able to discuss these questions with other persons? |
| Merkle | Ah, basically, actually I should give credit where credit is due. One of the people who was very instrumental in my continuing the work and continuing to submit it to the Communications of the ACM was Bob Fabry who was on the faculty at that time. And I submitted, or I actually didn't submit, I just talked with Bob Fabry, as I recall, was teaching an operating system course that Winter quarter. And during the Winter quarter I showed him a paper describing the concept, and he took one look at it and said; 'This is wonderful. Why don't you submit it for publication and win fame and fortune?'. So, in point of fact, Fabry's encouragement in the winter of '74, '75 was a critical element, because basically everyone I talked with who had any sort of professional connection or serious knowledge of cryptography was informing me I had my head up my ass and Fabry was sort of the only person I talked with who was, you know, a faculty member. |
| Interviewer | Do you mean that you had other connections to the established cryptography? |
| Merkle |
I had no... Well, Fabry was a faculty member at Berkeley and so I talked with Fabry and said; 'Here's an idea I had. What do you think about it?' And he said; 'Jesus, looks good. Why don't you publish it?' I did, after that, begin to communicate with others. Here I have a letter dated October 10th, 1976. Which is addressed to Marty, Martin Hellman. And by that date I was clearly in communication with Whit and Marty, as the letter clearly is a letter based on previous conversations. So certainly by October 1976 I was in communication with Hellman, and I believe there is another letter, ah, here we go:
'Dear Dr. Hellman, about three days ago a copy of your working paper Multi-user Cryptographic Techniques fell into my hands'. Whit and Marty had an earlier paper prior to 'New Directions in Cryptography', and that paper did a belly flop. For reasons that are unclear, it did not excite people, it did not get people to understand the issue. |
| Interviewer | What was the title of this one? |
| Merkle | Multi-user Cryptographic Techniques by Diffie and Hellman. This was before the New Directions paper. |
| Interviewer | That was even before? |
| Merkle |
Yes. So...
'Dear Dr. Hellman, about three days ago a copy of your working paper Multi-user Cryptographic Techniques fell into my hands.' And I suspect that would have been from Peter Blatman, but I don't know. 'Just prior to this I had finished revising a paper in the same subject which will shortly be re-submitted to the communications of the ACM. I enclose a copy of it in the hope you will find it interesting.' This is a letter that I wrote to Dr. Hellman. 'I enclose a copy of it in the hope you will find it interesting. Actually, I am glad to know there is someone else who is interested in the problem. The people with whom I try and discuss it either fail completely to understand what's going on or regard any attempt at solution as impossible. Fortunately, the partial solution described in the enclosed paper demonstrates that it is possible. Now if only we can do better.' And I go on to comment on the proposals in 'Multi-user Cryptography'. |
| Interviewer | And you added your paper to the letter? |
| Merkle | And I added the paper to the letter and sent it to him. I only have a copy though, of the letter that I wrote. I don't see a copy of the paper. |
| Interviewer | Why did Diffie write 'to bring from the woodwork Ralph Merkle'? |
| Merkle | Well, obviously I was not in touch with the cryptographic community and had never done any cryptographic work before. So from the point of view of someone interested in cryptography, I just sort of appeared out of the blue with no prior background in cryptography. No prior publications. No prior record in the area. |
| Interviewer | Did he refer to working in the woods or something like this, or is it an American expression I do not know? |
| Merkle |
Oh, well, 'coming out of the woodwork', yes, this is an American expression. It's slang, and it basically means that 'unexpectedly appeared, no prior indication, no prior reason to believe a person would do something'. So, 'coming out of the woodwork' is sort of a slang expression that means, 'sort of unexpectedly without prior warning'.
Oh, this letter is even dated. How convenient. The beginning of the letter says, 'Dear Dr. Hellman, about three days ago a copy of your working paper Multi-user Cryptographic Techniques fell into my hands', and the end of the letter is dated February 7th, 1976. So, apparently I first learned about Diffie and Hellman in early February, 1976. |
| Interviewer | One and a half years after you had this class with Lance? |
| Merkle | Yes. So, basically I had been rather frustrated during that time. |
| Interviewer | You said something like it took you a couple of days to think out this multi-puzzles system? |
| Merkle | Yes. |
| Interviewer | Did you do that alone? |
| Merkle |
Ralph Merkle: Yes. There was no one to talk with. No one had any idea that this problem even existed, or was significant or anything. It was simply, you know, stare at the ceiling and say 'Oh, this looks interesting. I think I'll think about it.' Okay...details blah blah blah ... messages, puzzles.
I'm going through this file which has various things in it. Well, here is a response; August 15, 1975, 'Dear Mr. Merkle, Thank you for your letter and your three copies of your manuscript Secure communications over insecure channels submitted for possible publication in the Communications of the ACM.'
It's from Robert Ashenhurst. That was August 15, 1975, which is the submission date for the Communications of the ACM. 'April 2nd, 1976. Dearest Stockton, You might recall a five page document that I gave you last year. It has since been revised and has grown to 43 pages. Hopefully it has gained in clarity and insight in the process. In any event, I thought you might be interested so I am sending you a complimentary copy. It's been submitted to CACM.' So this was sent on April 2nd, 1976 to Stockton Gaines. And by that time I knew about Diffie and Hellman. Apparently I sent Stockton a version of the paper in 1975 some time. I was put in touch with Stockton through Bob Fabry. So it's probably the case that it would have been mid-year some time '75. February 11th, 1977. Here is a response to Susan Graham in which I am cutting the length of the paper. I'm cutting the length of Secure communications over insecure channels. Trying to reduce it's size in accordance with the requests of the referee. This is all '77. 'Dear Ralph, I enclose a copy of version eight of your manuscript Secure Communications Over Insecure Channels.' They want it shorter. |
| Interviewer | To understand it perfectly, what have you been studying at that time? |
| Merkle | That would have been '74. At that time I was an undergraduate in computer science at UC Berkeley and had been studying various aspects of computer science. I had gotten very interested in that, I forget, either my sophomore or junior year. I took a summer course on programming using the CAL Time-sharing System and found that quite fascinating and so spent the rest of my education at Berkeley, basically learning about computers, because they were wonderful and fascinating and stuff like that. So, that's what I was doing. So general computer science background - undergraduate computer science. |
| Interviewer | What made you continue your efforts in developing these public key systems? |
| Merkle | Basically, I spent a summer with Whit and Marty and I would like to say that Marty provided strong encouragement. He was on the faculty at Stanford and made it clear this was a good and worthwhile problem which I thought intuitively, but I had a hard time persuading anyone else of. And so we just attacked the problem and worked on various solutions. |
| Interviewer | Did you have particular problems in mind, future applications? |
| Merkle | Well, once New Directions came out, the range of problems you could apply this to was pretty obvious. And basically we were trying to get a public key crypto system that would work and be clean and have all the desirable properties one wants. |
| Interviewer | And did you think of applying it rather with regard to signatures or to encryption or both? |
| Merkle | Oh, at that time both, when I was working with Whit and Marty. Essentially the original formulation of a public key crypto system, as it says in the puzzles paper, it points out how to use puzzles to make a public key crypto system. And in fact that method was devised. Once I was in touch with Whit and Marty, they discuss signatures and it was transparently obvious how to make the puzzle method deliver signatures. So in fact, I think I have a correspondence which in fact explicitly mentions that. |
| Interviewer | So with the puzzle system you basically had in mind in the first moment that you would transmit a key? |
| Merkle |
Right. The initial problem that I was working on was public key distribution. I devised the puzzles method to handle public key distribution, and, let's see, here we go, this is dated April 2nd 1976:
'Hi, Marty, I've been contemplating puzzles and public key crypto systems. Here's how to use the former to produce the latter.' Okay, so here's the letter where I tell Marty how to produce public key cryptosystems from puzzles. That was dated April 2nd, 1976. |
| Interviewer | Are you still busy with public key systems or anything of the like? |
| Merkle | I am primarily doing nanotechnology. |
| Interviewer | Sorry? |
| Merkle | Nanotechnology. My basic conclusion was that nanotechnology looks like it is going to have a major impact on the future Western civilization. |
| Interviewer | Of...? Oh, Western civilization. |
| Merkle | Of the world, okay. Nanotechnology is going to have a big impact on the future of the world and so I got interested in it and I have been pursuing it ever since. So that's what I am pursuing now. It is pleasing, of course, to see that there is an interest in cryptography and security, and that people are actually putting these kinds of systems into use. |
[1] Hoffman, L. Computer Security: a Course. ACM Computers and Society, Vol. 5, No. 4, Winter 1974, 5-8
Bitte beachten Sie, dass diese Internetseite nicht weiter gepflegt wird. Für aktuelle Inhalte besuchen Sie bitte www.itas.kit.edu.