(2023-12-25) Pen and paper cryptography: breaking down what's still worth
-------------------------------------------------------------------------
A long time ago (a _very_ long time ago) I created a protocol for SMS text
encryption. It was based on a well-known Bifid cipher (we'll get to this a
bit later) but applied a little bit differently, and, of course, all
encryption/decryption must be done manually. Back then, I thought of it as
of something worth publishing because almost no one had been touching "hand
crypto" in the age of computers anymore. But my protocol also had several
issues I only realized much later and abandoned it in the depth of my GitHub
Gist. The topic is still alive though, and may see another resurgence as we
are drowning deeper and deeper into the modern dystopia. The only problem is
what is still worth studying within this topic, because most hand ciphers
existing in the world really are obsolete and can't be used nowadays.
In this post, I'm only going to focus on _symmetrical_ cryptography.
Asymmetrical cryptography still is somewhat possible to do by hand but it's
much less practical as of now.
Before I get into the details of what we can build, let me share my own
criteria of what I consider a usable pen and paper crypto algorithm today:
1. It must meet both Shannon's requirements for confusion and diffusion.
2. It must support (or be able to extend to support) encrypting alphanumeric
messages (so, at least 36 characters).
3. It must not involve any calculations beyond some modulo addition and
subtraction that can be done mentally, and preferably should not make the
operators to do even those.
4. Guessing the key length by analyzing the ciphertext must be impossible.
5. Average encryption/decryption speed must not be lower than 10 characters
per minute by a trained operator.
6. All printed or handwritten material that doesn't involve key information
must be as reusable as possible.
Based on these criteria, here's what I'm NOT considering viable pen and paper
ciphers or their building blocks:
1. Straddling checkerboards. Yes, they are useful but not fast enough and
restrict you to modulo-10 arithmetic. And for keystream generation, their
output is not uniform as they will generate the letters that map to single
digits much more often.
2. Any playing card based system such as Solitaire/Pontifex. Too slow to
encrypt even a single character.
3. Columnar transpositions, except when preparing the key material. When used
on the plaintext, they can expose the key length. Also, only the relative
order of the letters in the key matters for a columnar transposition, not
their values, so different keys with the same relative order (like, for
example, words "key" and "law") will produce the same results.
4. Bigram substitutions (like Playfair), except when preparing the key
material. When used on the plaintext, they expose too many irregularities
and can't provide any protection against statistical analysis.
Now, let's finally list the building blocks for a pen and paper cipher that
meets the above criteria:
1. Tabula recta. For an alphabet of size N, this is a square table of NxN
characters consisting of all possible rotations of this alphabet. For the
user's convenience, the table might be indexed with the duplicates of the
first row and the first column respectively. This is what's used to "add"
and "subtract" letters of the target alphabet without having to convert them
to digits and performing any modular arithmetics. For any chosen character
set, a tabula recta can be generated, typed or even handwritten from memory
with virtually no effort. In fact, for a "one-time pad" cryptosystem, which
is proven to be unbreakable if properly used, all one needs is a tabula
recta and securely distributed sheets of key material.
2. Polybius square. For an alphabet of size N (and N should be a full square
in this case), this is a square consisting of all N characters of this
alphabet, and all rows and columns are usually numbered from 1 to sqrt(N).
Such a square can be used for different purposes in the cryptosystem, but
the most promising uses are based on achieving the diffusion goal by
splitting the letters by their row and column numbers and recombining them
from those numbers in a different way. This is how ADFGVX and Bifid ciphers
worked.
3. Autokey. Although mistakenly attributed to only one (and pretty insecure)
method of just putting the beginning of the plaintext into the keystream
after the key itself has ended, the autokey concept in fact means multiple
ways of extending the key material based on the previous values, and it
doesn't (and shouldn't) necessarily involve plaintext at all.
4. Polyalphabetic substitutions. The way the alphabet gets modified doesn't
matter much, what matters is that it's not static. However, not every way of
doing this meets our initial criteria, so we must be careful about what we
choose here. For instance, just using a plain tabula recta as the source of
a polyalphabetic substitution and calling it a day won't work.
So, these are the main ideas that can be utilized for our paper crypto
purposes. Now, let's see them in action by designing a pen and paper stream
cipher!
Part 1. The tabula recta
This is the definite tool that will help us with all our "calculations".
Print out (or write down) the tabula recta for the alphabet of your choice,
in our case it's 36 characters: first A to Z, then 0 to 9. Writing down
36x36 squares can be tedious, so I recommend preprinting them. The columns
and rows are indexed from both sides for ease of use.
Here's an AWK script to generate and display the full 36x36 tabula recta:
BEGIN {
alpha = "A B C D E F G H I J K L M N O P Q R S T U V W X Y Z " \
"0 1 2 3 4 5 6 7 8 9 "
l = length(alpha)
printf(" | %s|\n%s", alpha, "-|")
for(i=0;i