John Nash on cryptography

[pg2] Dear Major Grosjean,

I have written RAND concerning the machine description. This was handwritten and was sent to NSA late last spring, I believe, or sent to someone there. Essentially the same machine description was once sent to a Navy Communication Center in Washington, I think.

I have discussed the machine and general exponential conjecture with R.C. Blanchfield and A.M. Gleason who have worked for NSA. Recently a conversation with Professor Huffman here indicated that he has recently been working on a machine with similar objectives. Since he will be consulting for NSA I shall [pg3] discuss my ideas with him. He has developed minimal redundancy coding methods.

I hope my handwriting, etc. do not give the impression I am just a crank or circle-squarer. My position here is Assist. Professor of math. My best known work is in game theory (reprint, sent separately). I mention these things only in the interest of securing a most careful consideration of the machine and ideas by your most competent associates.

If the machine description does not turn up, I will provide another. Also I shall be happy to provide any additional information or answer any queries to the best of my ability.

With many thanks for your prompt reply, I am

Sincerely Yours,

[pg4] Dear Sirs:

An enciphering-deciphering machine (in general outline) of my invention has been sent to your organization by way of the RAND corporation. In this letter I make some remarks on a general principle relevant to enciphering in general and to my machine in particular. This principle seems quite important to me, and I have some reason to believe you may not be fully aware of it.

Consider an enciphering process with a finite “key”, operating on binary messages. Specifically, we can assume the process described by a function

Y_i = F(α, α₂, … α_r; X_i, X_i−1, X_i−2, … X_i−n)

where the α’s, X’s, and Y’s are mod 2 and where if X_i is changed, with the other X’s and α’s left fixed then Y_i is changed.

[pg5] The α’s denote the “key” containing r bits of information. n is the maximum span of the “memory” of the process. If n were ∞ the arguments given below would not be basically altered.

To consider the resistance of an enciphering process to being broken we should assume that at same times the enemy knows everything but the key being used and to break it needs only discover the key from this information.

We see immediately that in principle the enemy needs very little information to begin to break down the process. Essentially, as soon as r bits of enciphered message have been transmitted the key is about determined. This is no security, for a practical key should not be too long. But this does not consider how easy or difficult it is for the enemy to make the computation determining the key. If this computation, [pg6] although possible in principle, were sufficiently long at best then the process could still be secure in a practical sense.

The most direct computation procedure would be for the enemy to try all 2^r possible keys, one by one. Obviously this is easily made impractical for the enemy by simply choosing r large enough.

In many cruder types of enciphering, particularly those which are not auto-coding, such as substitution ciphers (letter for letter, letter pair for letter pair, triple for triple…) shorter means for computing the key are feasible, essentially because the key can be determined piece meal, one substitution at a time.

So a logical way to classify enciphering processes is by the way in which the computation length for the computation of the key increases with increasing length of the key. This is at best exponential [pg7] and at worst, probably a relatively small power of r, ar² or ar³, as in substitution ciphers.

Now my general conjecture is as follows: For almost all sufficiently complex types of enciphering, especially where the instructions given by different portions of the key interact complexly with each other in the determination of their ultimate effects on the enciphering, the mean [?] key computation length increases exponentially with the length of the key, or in other words, with the information content of the key.

The significance of this general conjecture, assuming its truth, is easy to see. It means that it is quite feasible to design ciphers that are effectively unbreakable. As ciphers become more sophisticated the game of cipher breaking by skilled teams, etc., should become a thing of the past.

[pg8] The nature of this conjecture is such that I cannot prove it, even for a special type of ciphers. Nor do I expect it to be proven. But this does not destroy its significance. The probability of the truth of the conjecture can be guessed at on the basis of experience with enciphering and deciphering.

If qualified opinions incline to believe in the exponential conjecture, then I think we (the U.S.) can not afford not to make use of it. Also we should try to keep track of the progress of foreign nations towards “unbreakable” types of ciphers.

Since the U.S. presumably does not want other nations to use ciphers we cannot expect to break, this general principle should probably be studied but kept secret.

I believe the enciphering-deciphering machine I invented and had transmitted to the N.S.A. via RAND has this “unbreakable” property. In addition it has several other advantages in that [pg9] the same physical machine would function both for ciphering and deciphering and that it is auto-synchronizing and recovers after isolated errors in transmission. These properties are not typical of enciphering systems which are auto-coding. Also it is suitable for an all electronic, ultra rapid, embodiment.

---

I do not expect any informative answer to this letter, yet it would be nice to have some sort of answer. I would be happy to explain more fully anything which is not clear in my letter, or to amplify on it.

I have been treating my ideas as information deserving some secrecy precautions, yet I feel it is important to communicate them to the right people. I hope the material in this letter can obtain prompt consideration by very highly competent men, versed in the field.

Sincerely.

[pg12] E. M. Gibson, Lt.Col., AGC, Asst. Adj. Gen.

Dear Sir:

Here is a description of my enciphering-deciphering machine.

In the receiving arrangement the same components are used except for the addition of the retarder, which is a one-unit delay. The messages are to be sequences of binary digits (numbers mod 2). The machines work on a cycling basis, performing certain operations [pg13] during each cycle.

During each cycle the adder, A, takes in two digits and adds them and sends on the sum obtained from the previous addition. The delay in this addition necessitates the retarder, R, in the receiving circuit.

The permuter will be described in more detail below. It takes in a digit from D during each cycle and also puts out a number. What it does, which is the choice between two permutations is determined by what digit (1 or 0) is in D at the time. The permuter always has a number of digits remembered within it. Each cycle it shuffles them around, changing some 1’s to zeros, sends one digit on, and takes in a digit from D.

In operation the input of the receiver is the output of the transmitter. So the input to R is the same as the input to D in the transmitter. Hence the output of P in the receiver is the same as the out-put of P in the transmitter, except for a one-unit lag.

[pg14] So the adder A in the receiver gets: (1) the out-put of A in the transmitter, and (2) the previous input from P(trans.) to A(trans). Now since binary addition is the same as binary subtraction (ie. + & - mod 2 are the same) the output of A(receiv.) will be the previous input to A(trans.) From the input to the transmitter, ie. it will be the clear or unciphered message.

The permuter, P, and “decider”, D, work as follows, illustrated by example:

[pg15] The circles represent places where a digit can be stored. During each cycle either the red permutation of digits or the blue takes place. This is decided by the digit in D at the beginning of the cycle. The D digit moves to the first circle or storage place in P during the cycle after it has determined the choice of the permutation.

Both permutations should cycle through all the places in P, so that a digit would be carried through all of them and out under its action alone.

In addition to moving digits around the permutations can change 1’s to 0’s and v.v. For example

represents a shift of the digit in the left circle to the right with this change

[pg16] The “key” for the enciphering machine is the choice of the permutations. If there are n storage points in P, not counting the first one, which receives the digit from D, then there are [n!2ⁿ⁺¹]² possible keys.

---

I guess I can rely on your people to check on the possession of this machine of the various properties I claimed for it in a previous letter. I hope the correspondence I have sent in receives careful attention from the most qualified people, because I think the basic points involved are very important.

Sincerely,

P.S. Various devices could be added to the machine, but I think it would generally be better to enlarge the permuter than to add anything. Of course error-correcting coding could occasionally be a useful adjunct.