11
$\begingroup$

We have several questions tagged talking about encryption, hashing, signing, etc. but no question asks about exchanging a secret via public key encryption in a secure way.

Does any solution exist, which would allow us to exchange a secret via a public channel (think: key exchange) using nothing but pen-and-paper and which can be handled by people who are not (what one might call) “math wizards” (read: people who can calculate whole algorithms using nothing but their brain) but who do know their way around maths and who do understand crypto?

As far as I’m aware there isn’t any such solution in classic (pre-computer) cryptography. But that doesn’t automatically mean it can’t be done.

Of course, potential solutions won’t offer the security we get and expect from computer-based solutions like RSA or elliptic curve cryptography. Yet, to keep it simple let’s assume we’re not trying to protect ourselves against nation-state adversaries here. Nevertheless, suggestions should provide a usable security margin.

What would be a not so neck-breaking way to exchange a secret over a public channel using nothing but pen-and-paper means? Is it even possible to do so in a somewhat secure way without using computers, mobile phones, or other, even more rudimentary tools — like mechanical machines — that aren't always available? (Hence the tag .)

To clarify: I am not looking for something which resembles a toy cipher made for the purpose of “demonstrating to a 12-year-old how encryption works” and/or to be used in a “fantasy story”. My question asks for an actually usable and secure solution (as mentioned above).

$\endgroup$
5
  • 2
    $\begingroup$ I think a simple (EC)DH with a field selected for easy modulous operation might be possible to acomplish in a few hours on pen and paper. Though I haven't worked out details or timed my self. $\endgroup$
    – Meir Maor
    Nov 18 '17 at 5:47
  • 2
    $\begingroup$ @Meir Doing any kind of arithmetic on paper is extremely error-prone; after "a few hours" you are pretty much guaranteed to have made a mistake which would make the message decrypt to garbage (unless you are a math whiz, but this is ruled out in the question). $\endgroup$
    – fkraiem
    Nov 19 '17 at 6:46
  • 2
    $\begingroup$ @MeirMaor I think ECDH by hand is out of the question. For regular DH: With a modulus of proper length and secret exponents of fitting lengths, this would still be a square-and-multiply with roughly $1.5 \times bitlength$ steps. Even if the modulo operation is simple, squaring and multiplying thousands of long numbers is still a lot. $\endgroup$
    – tylo
    Nov 20 '17 at 13:10
  • $\begingroup$ @e-sushi the question is not an exact duplicate, but the answer covers this as well, which is the criterion for closing as duplicate as I understand? $\endgroup$
    – otus
    Nov 22 '17 at 13:23
  • 1
    $\begingroup$ @otus Somehow you’re right. I’ve put it on hold as a dupe. Don’t want to set a wrong example by nit-picking where I probably shouldn’t. $\endgroup$
    – e-sushi
    Nov 22 '17 at 19:23