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 reinvented 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 rediscovered 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:
 Copy/paste Ellis’ sketch of his proof.
 List the seemingly obvious objections to it, as understood in 2014 terms.
 Explain away the objections by showing that, in 2014, they are due to Ellis’ precomputer age vocabulary.
 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 “nonsecret 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 lookup table, with the settings, message etc as the variables used for lookup, 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 #
Key  Encrypted Key 

k1  x1 
k2  x2 
k3  x3 
…  … 
M2 #
In this table, for example, z_{2}3 is the ciphertext of p3 encrypted with k2:
Encrypted Key  Plaintext p1  Plaintext p2  Plaintext p3  … 

x1  z_{1}1  z_{1}2  z_{1}3  … 
x2  z_{2}1  z_{2}2  z_{2}3  … 
M3 #
z  k1  k2  k3  … 

z_{1}1  p1  …  
z_{1}2  p2  …  
z_{1}3  p3  …  
z_{2}1  p1  …  
z_{2}2  p2  …  
z_{2}3  p3  …  
z_{3}1  p1  …  
z_{3}2  p2  …  
z_{3}3  p3  … 
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 publickeyencryption 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 twodimensional 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:
 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?!
 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 oneway function. I have three reasons for thinking this.
First, any symmetric cipher is like a oneway function with a back door that makes it twoway. You can’t derive the plaintext from ciphertext, unless you have the key (to the back door, so to speak).^{1}
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 oneway function. This oneway function works like a lookup 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:
H
is a cryptographic hash.S
is a symmetric cipher. Its keyspace is{k1, k2, … , k, …., kn }
. (Then we can say thatS(k,p) → c
, andS(k,c) →p
, wherec
is a ciphertext, andp
is a plaintext. We’ll say thatp
comes from{p}
, the set of all possible plaintexts in the universe.S’
is a strange oneway function. It has two inputs. If one of those inputs isH(k)
, and the other input isp
, then the output isc
. Using symbols, we can write this as:S’(H(k), p) → c
.
So to be clear:
S(k, p) → c
, andS(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
, calculatesH(k)
, and stores(k, H(k))
in a small, private lookup table. So givenH(k)
, Alice can always look upk
easily, even thoughH
is oneway.  Step 2. Alice sends
H(k)
to Bob through an insecure channel.  Step 3. Bob calculates
S’( H(k), p ) = c
, and sendsH(k)
andc
to Alice through an insecure channel.^{2}  Step 4. Alice takes
H(k)
, looks upk
in her little table, and deciphersc
to getp
.
Eve, who has been eavesdropping, has all three cryptographic primitives S
, S'
, and H
, as well as the numbers H(k)
and c
.^{3} The thing to realize is that Eve cannot derive p
from this information.
Because S’
is oneway, 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 oneway 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 oneway. 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
andS’
are oneway functions,p
cannot be found without knowingk
; andk
cannot be derived fromS
,S’
,H
;H(k)
andc
.
Q.E.D.

A symmetric cipher is not a cryptographic hash, though, because its outputs are not all the same size. However, it’s worth pointing out that any symmetric cipher can be used as a pretty good cryptographic hash: just use the last n bytes of the ciphertext. There isn’t even a back door then. ↩

Alice already has
H(k)
, of course. But if Bob is sending Alice a lot of messages, she will have a difficult time keeping track of whichH(k)
goes with whichc
. A simple way to solve that problem is for Bob to always send back not justc
, butH(k)
as well. ↩ 
In Ellis’ terms, M1 is
H
; M2 isS’
; M3 isS
; x isH(k)
; and p isp
and z isc
. ↩