(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