James H. Ellis’ proof that asymmetric cryptography is possible

In 1987 James H. Ellis wrote a short, classified history of how the RSA cipher was secretly invented inside GCHQ three years before it was re-invented at MIT by Rivest, Shamir, and Adleman.

In his note, Ellis described how he first came to suspect that asymmetric cryptography might be possible, and how, after he had failed repeatedly to develop an asymmetric cipher, he came up with a formal proof, in 1970, that such a cipher definitely was possible. This resulted in a feverish and highly classified effort within GCHQ to invent one, a hunt which ended some years later when Clifford Cocks discovered what we now know as the RSA cipher. RSA was re-discovered some three years after that at MIT by its three eponymous (re-)inventors, changing cryptography for ever.

Ellis’ note was declassified by GCHQ in 1994 and posted online.

When read today in 2014, the proof makes no sense at all.

I’m going to do four things here:

1. Copy/paste Ellis’ sketch of his proof.
2. List the seemingly obvious objections to it, as understood in 2014 terms.
3. Explain away the objections by showing that, in 2014, they are due to Ellis’ pre-computer age vocabulary.
4. Present Ellis’ proof using 2014 vocabulary.

Ellis’ original proof #

Here is Ellis’ sketch of his proof that asymmetric cryptography is possible, in his own words. Note that he calls asymmetric cryptography “non-secret encryption,” or “NSE,” and that he numbered his paragraphs.

7) … Can we produce a secure encrypted message, readable by the authorised recipient without any prior secret exchange of the key etc?” This question actually occurred to me in bed one night, and the proof of the theoretical possibility took only a few minutes. We had an existence theorem. The unthinkable was actually possible. The only remaining question was “Can it be made practicable?” This took a while to answer.

8) I published the existence theorem in 1970 (reference 3). Its outline is as follows. We may represent an encipherment process by a look-up table, with the settings, message etc as the variables used for look-up, and the cipher text as the contents of the table. Such a table will normally be impossibly huge but it could, in principle, always be constructed. Conversely, such a table itself can be used as such a process, even if a more conventional embodiment cannot be found. This proof treats the encipherment processes as tables, and demonstrates a form which satisfies the requirements.

9) Suppose the recipient has two tables M1 and M3 while the sender has one, M2. These machine tables are not secret and may be supposed to be possessed by the interceptor. M1 takes an input k and produces an output x. M2 takes inputs x and p giving an output z. M3 takes inputs z and k. All these quantities are large numbers of the same magnitude. We can think of M1 as a linear table or simple list, while M2 and M3 are square tables.

If I understand Ellis correctly, these are his M tables:

M1 #

M2 #

In this table, for example, z₂3 is the ciphertext of p3 encrypted with k2:

M3 #

Ellis then goes on:

10) In operation p is the message which is to be sent, and k is a random number, the key, chosen by the recipient. He enciphers k by M1 to get x which he sends. The sender uses x to encipher p with M2 to get z, the cipher text, which he sends back. Now the recipient uses k to decipher z by means of M3. It is clearly possible for the entries of M3 to give p under these circumstances, so we have achieved our objective.

11) If the numbers are large enough, and M1 and M2 sufficiently random to avoid working backwards, p cannot be found without knowing k. In public-key-encryption terms, x is the public, encipherment key and k the private, decipherment key.

12) Having thus demonstrated that NSE was possible, the next task was to find a practical implementation. …

Objections to the proof #

To a modern reader in 2014, this makes absolutely no sense. A “table” sounds like a two-dimensional Excel spreadsheet. For example, M2 has rows for enciphered keys and columns for plaintext. For every enciphered key x, each horizontal cell contains a different plaintext enciphered with k. In that case, there are two glaring objections:

1. If the interceptor has the same table M2 that the sender has, as Ellis says she does, then she can easily look up p. After all, the sender just scanned down the rows of M2 until he found x, then scanned along to the right until he got to the column for p. In that cell, the sender found c, and sent it to the recipient. So what’s to stop the interceptor from using M2 to scan along the x row until she finds c, then just read the column heading of that columnm, which is p?!
2. Ellis says the interceptor has all three tables: “These machine tables are not secret and may be supposed to be possessed by the interceptor.” Ellis says “these,” not “this.” So the interceptor has M1, M2, and M3, as well as x and c. So what’s to stop her from looking up k in M1 from x, then using c and k to look up p in M3?!

Explication #

We can make sense of Ellis by noticing that he doesn’t just say “tables,” he says (in his paragraph 9) “machine tables.” I think what he meant by “machine table” was what we today call a one-way function. I have three reasons for thinking this.

First, any symmetric cipher is like a one-way function with a back door that makes it two-way. You can’t derive the plaintext from ciphertext, unless you have the key (to the back door, so to speak).¹

Second, I’m pretty sure that in the 1960s and 1970s all ciphering was done with what people then called “machines.” They were more advanced than the German Enigma machine, but they were still thought of as machines, not as computers or anything else. So what Ellis would have meant by “machine table” is just a one-way function. This one-way function works like a look-up table that can only be looked up in one direction. If you know the row and column, you can look up what is in the corresponding cell; but if you only have the cell’s content and not the whole table, you can’t work out what row and column it is in.

And third, this interpretation allows us to make sense of the sketch of his proof. Here’s how.

Ellis’ proof in 2014 terms #

The form of Ellis’ proof is this: using known cryptographic primitives (apart from asymmetric ciphers, obviously), show at least one way to make a crypto system in which the sender does not have to have the recipient’s key.

Imagine we have the following three cryptographic primitives:

1. H is a cryptographic hash.
2. S is a symmetric cipher. Its keyspace is {k1, k2, … , k, …., kn }. (Then we can say that S(k,p) → c, and S(k,c) →p, where c is a ciphertext, and p is a plaintext. We’ll say that p comes from {p}, the set of all possible plaintexts in the universe.
3. S’ is a strange one-way function. It has two inputs. If one of those inputs is H(k), and the other input is p, then the output is c. Using symbols, we can write this as: S’(H(k), p) → c.

So to be clear:

• S(k, p) → c, and S(k, c) → p
• S’(H(k), p) → c

It is now possible for Bob to send Alice a secure message enciphered with S(k), without Bob having to have k! The “unthinkable” is “actually possible”! Here’s how:

• Step 1. Alice chooses a secret key k, calculates H(k), and stores (k, H(k)) in a small, private look-up table. So given H(k), Alice can always look up k easily, even though H is one-way.
• Step 2. Alice sends H(k) to Bob through an insecure channel.
• Step 3. Bob calculates S’( H(k), p ) = c, and sends H(k) and c to Alice through an insecure channel.²
• Step 4. Alice takes H(k), looks up k in her little table, and deciphers c to get p.

Eve, who has been eavesdropping, has all three cryptographic primitives S, S', and H, as well as the numbers H(k) and c.³ The thing to realize is that Eve cannot derive p from this information.

Because S’ is one-way, Eve can’t figure out p from H(k) and c. Her only option is brute force: do S′(H(k),p),∀p∈{p}, until she finds c. We assume that S’ is such a good one-way function that brute force is infeasible.

And by the definition of a symmetric cipher, Alice cannot find p with S and c unless she has k. And, she can’t get k from H(k), because H is one-way. Since Eve can’t get k, she can’t decrypt c. Eve is stuck.

Ellis wrote in conclusion:

If the numbers are large enough, and M1 and M2 sufficiently random to avoid working backwards, p cannot be found without knowing k.

We can rephrase this as follows:

If H and S’ are one-way functions, p cannot be found without knowing k; and k cannot be derived from S, S’, H; H(k) and c.

Q.E.D.