Elise Four - Strong, Human Powered, Encryption

If you want to understand a subject, teach it to someone. If you want to truly and completely understand a subject, teach it to a computer. That is, program it.

This idea of coding to reach understanding is a lesson I've learned countless times. Most recently, I experienced this adage while tackling the Elise Four exercise from Programming Praxis. The task was to implement the EliseFour (aka, LC4) Encryption Algorithm. This approach to encryption is especially interesting because of its competing goals. First, it attempts to provide for strong encryption. Secondly, it's designed to be run offline by human power alone. (Not unlike this solution)

See the contradiction there? All the tools one thinks of when considering strong encryption, such as terrifically hard calculations and massively large numbers, are off the table. LC4 therefor has to choose clever conventions over raw processing power. The author solves this challenge by constructing a grid of Scrabble-like tiles and re-arranging them using a simple set of rules. While I'm interesting in implementing an offline version of the algorithm, for now, I've coded the algorithm in Scheme.

Here's the algorithm at work:

;; Example 1
Key:  xv7ydq #opaj_ 39rzut 8b45wc sgehmi knf26l 
Nonce:  solwbf 
Text:  im_about_to_put_the_hammer_down 
Encrypted:  i2zqpilr2yqgptltrzx2_9fzlmbo3y8_9pyssx8nf2 
Decrypted:  im_about_to_put_the_hammer_down#rubberduck 

;; Example 2
Key:  xv7ydq #opaj_ 39rzut 8b45wc sgehmi knf26l 
Nonce:  argvpx 
Text:  hurrrraaaaaaaaaaaaaaaaaaaaaay 
Encrypted:  3bcxnt57hus6accn97v4iie__hjbml8wr 
Decrypted:  hurrrraaaaaaaaaaaaaaaaaaaaaay#ben 

The source code for my solution can be found in the usual spot.

Example 1 comes directly from the paper describing the algorithm and was my lifeline for implementing and verifying the algorithm. You can see that to communicate with the LC4 algorithm, both users need to know the key value ahead of time. The key will always be an arrangement of the 36 different characters in the alphabet.

Encryption and decryption also depend on a nonce value, which is used to add additional noise into the system. The nonce value is to be shared with the recipient, and no harm comes from it being exposed to an attacker.

Example 2 emphasizes that even text with a telling shape comes out as random gibberish when encrypted; a sign that his is indeed a secure algorithm.

LC4 is an elegant solution to an unusual encryption challenge. On one level, I knew this by browsing the source paper on the topic. But now that I've struggled through an implementation, I know this on a completely different level. And when I say struggle, I mean it. Encryption algorithms are tricky to implement because the goal is to take text and turn it into garbage, but very specific garbage. So when I had variable c where y belonged, or neglected to reset r and y the algorithm still produced jumbled text, but it was the wrong jumbled text.

At least four times I was absolutely sure I had coded the encryption and decryption algorithm exactly as described, yet my code was failing. I did what any smart programmer does in these situations: I stepped away and re-attacked the problem after some rest. With some time away from the code, the bugs were obvious and easy to address.

When I finished coding the algorithm I had far more than just working code. I had an intimate appreciation for key generation, nonce usage, dictionary selection, authentication operation and a half dozen other subtle details that work together to make LC4 function. Oh, and the dopamine rush from seeing my text get encrypted and then decrypted was nice too.