How to build an electro-mechanical public key cipher machine?

It is generally assumed that asymmetric encryption schemes were invented in 1973 at GCHQ in Britain and, independently, in 1976 at the MIT.

Imagine, if the abstract idea of having a public key and a private key that can only decrypt what has been encrypted with the other, respectively, had been around forty years earlier. Would it have been possible to build a working (rotor) cipher machine using this principle with WWII technology (think public key enigma)?

Are there any key generation schemas that are hard to inverse in the mathematical sense but could be implemented using electro-mechanical machines without transistors?

I'm asking this purely out of curiosity, by the way :)

-
I don't see why not. Even mechanical computers were Turing-complete in that they could be built to accommodate any series of instructions, so even elliptic curve cryptography could theoretically be built from vacuum tubes and rotors. Now, as for efficiency.. –  Thomas Jun 16 '13 at 4:00
Okay, I should have added "that would have been of real-world use". I'm sure some hobbyist must have thought about how to construct something like this in a garage already, but I couldn't find anything online. –  Manuel Jun 16 '13 at 4:05
con $\mapsto$ can $\;$ –  Ricky Demer Jun 16 '13 at 5:03
I wonder if you could implement ECC in hardware? Have a flexible line defined by the equation to serve as a cam surface, then place a straightedge at points P and Q to find the intersecting point. It could be a great illustrative tool, but I doubt it could be made accurate enough to provide the security required. –  John Deters Jun 17 '13 at 16:50
Especially since finite elliptic curves don't look at all nice. $\:$ –  Ricky Demer Jun 17 '13 at 19:44

Since this is an historical question, I am going to digress and make some historical corrections. In science, we give credit for important inventions to the people who published. If it turns out that someone else invented it earlier and didn't publish, they don't get credit. Obviously, they should be mentioned in passing or a footnote in the interests of complete information, but credit for inventing something goes not to the person who keep it secret, but to the people who publish.

Thus, I must take issue your saying that GCHQ invented it. As smart and forward-thinking Ellis, Cocks, and Williamson were, they didn't publish, so they don't get credit for inventing it. (Also, they were at CESG, not GCHQ. Some may find this a difference without distinction, but Ellis himself makes that point in his notes on their work.

Secondarily, public key encryption is generally credited to some combination of Merkle, Hellman, and Diffie, who were at some combination of Stanford (where it was understood) and Berkeley (where it was misunderstood). Diffie's article, "The First Ten Years of Public-Key Cryptography" is a great account of this. You can also find Merkle's rejected 1974 Berkeley project for what was an early form of public-key cryptography on his Computer History Museum bio.

Thank you for your forbearance on the above. Now let me answer your question.

The basic idea in public-key cryptography is that there are problems that are easy to do in one direction and hard to do in another. At it's easiest, this is intuitive. Anyone who has struggled through learning long division knows that there's a very real sense in which dividing is harder than multiplying. But more more importantly, the structure of public-key (or non-secret) encryption is that there's one key to encrypt and one key to decrypt and you can't derive the decrypt-key from the encrypt-key. That's why the encrypt-key is either public or non-secret.

In construction, the Merkle-Hellman-Diffie ideas played around with "trapdoor" functions that had a secret that made the problem very easy to solve. The basis for discrete-log public key cryptography is that exponentiion -- $g^x$ in a finite field with a public $g$ and a secret $x$ is easy to solve for the person who knows $x$, but hard without knowing the trap door of $x$.

Similarly, RSA is built on the difficulty of factoring, and the trap door is that if you know the two primes you've multiplied together, it's easy to undo an RSA calculation. Rabin is based on the hardness of square roots (think of it being a special case of RSA where primes $p$ and $q$ are equal), and so on. Just as it's easy to intuit that division is harder than multiplication, taking a logarithm or a square root or factoring is intuitively a lot harder.

So how does this apply to electro-mechanical systems? Well, you could probably construct an electromechanical machine that did Diffie-Hellman. Konrad Zuse's Z3 computer was Turing-complete and program-controlled. It's entirely possible you could do it there. I have a mild raised eyebrow as the Z3 didn't have conditionals, but if you knew about Diffie-Hellman or RSA, I'm sure you could build a machine to do it. Of course, you'd have very short keys, but who cares, as everyone else only has electro-mechanical machines, too.

Could you do it with rotor machines? I don't know. My intuition is to say no. Remember that what we want to have with public key machines is a separate encrypt and decrypt key, and fast decryption aided by some trap door. Enigma was in many ways a mechanical puzzle in which electricity was bounced around, whereas the Lorenz machine is pretty recognizable as a modern stream cipher. I don't see a good way to turn those into public key systems.

For quite some time, we cryptographers have considered the possibility of symmetric ciphers that had some sort of back door in them. Some number of years ago, someone proved that if you have a symmetric cipher with a back door, then that is a trap-door function that can be used make an effective public key cryptosystem where the backdoor and its parameters are the secret key. (I'm sorry that I don't remember whose theorem that is.) Interestingly, this would be a public-key system that runs at the speeds of a symmetric cipher and very likely with a key that is small (compared to other public-key systems).

All our usable public-key cryptosystems are much, much slower than symmetric systems. They're often four or five orders of magnitude (or more) slower than symmetric systems of comparable strengths. So if you managed to find one of these, why would you waste it by releasing it as a symmetric cipher with a back door?

If you're an academic, you've invented something of mindblowing newness. It's an invention at least as powerful as the existing public key systems, and really much, much more interesting because it runs at symmetric speeds.

If you're in an intelligence service (like the CESG guys), you still have something amazingly powerful. Would you waste it? I say waste, because if you release this new cipher as a symmetric cipher, someone's going to figure out the back door eventually, even if that happens by a leak. Someone else will figure out that it's actually a usable public key cryptosystem and they will get the credit for it, not you. If and when it comes out that you knew it all along, then the way history will remember you is for this, and history is unlikely to be kind.

Moreover, this suggests that at the very least, making either a fast public key system or cipher with a backdoor is very hard. We've been trying for ages to get effective, new, usable public key cryptosystems and they're hard to do.

This means that if there is a way to make a rotor or electromechanical system that has a new public-key cryptosystem (one that isn't simply one of the ones we know now), we very likely don't know it. That suggests that they really couldn't have done it then. It's more likely tha they'd have done something like invent Diffie-Hellman or one of Merkle's puzzles or knapsacks and then implement that on electro-mechanical hardware.

So I would say that no, probably not. People in WWII probably could not have come up with something cool that isn't one of the systems we know about now.

Jon

-
Small correction: RSA (or Rabin) with $p = q$ would be completely broken. Rabin is not a RSA with $p = q$, but about modular square roots, i.e. undoing squaring the message modulo a $n=p·q$ just like for RSA. And its hardness can actually be reduced to factoring $n$. –  Paŭlo Ebermann Jun 24 '13 at 16:54