An Engineer’s Brief Introduction to Cryptography

This primer on cryptography will help you understand the encryptions that are necessary for modern IoT device security.

Humans have shared information over great distances in written form for millennia. But when written messages are intercepted, and the text is plainly read by an enemy, an angry politician can start a war, or an otherwise competent general can lose a battle. So the need for encryption has existed as long as there were armies to lead and alliances to forge.

All of that time, humans made incremental improvements. One big development in the field of cryptography happened just prior to World War 2 when engineers created an unbreakable code, and the British subsequently broke it. But cryptography really found its feet in the computer era with the invention of the Diffie-Hellman algorithm.

 

Simple Ciphers

The simplest way for schoolchildren to share a secret is with a substitution cipher. This method simply swaps one character for another character or symbol. The sender of the message would obfuscate the meaning by changing the characters in the message for a predetermined character/symbol. The receiver of the message would use a matching codebook to determine the original symbol.

 

Three substitution ciphers are shown above, each simply replaces one letter of the alphabet with another letter/symbol.  

 

This method has several flaws. For example, if the code is of sufficient length, an analyst can perform what is known as n-gram analysis or frequency analysis. The English language has spelling and grammar rules that cause letters and combinations of letters to appear with a predictable frequency. Once someone feeds the secret message into a computer, they can begin to guess which letters in the secret message correspond to letters in the original text.

Below are frequency analysis and 2-gram analysis of the New Oxford Dictionary (no foreign or special characters) and Rudyard Kipling’s “The Jungle Book”. A cryptographer deciphering a secret message might infer that the most common character is e, and the least commonly used is q, x, or z, and so forth.

 

Frequency and n-gram analysis for “The Jungle Book” and the “Oxford Dictionary”

 

But there is a bigger problem.  Once an enemy deciphers a single message, they can decipher all messages that use this code.

I use this childish example to illustrate three points:

• Both the sender and receiver must agree on how to encode/decode the secret message
• A secret message of sufficient length that relies on the same substitutions can be cracked.  In our example, the encryption scheme should be changed at a minimum every 26 letters.
• A cryptography system should provide forward-secrecy.  So that if one message is deciphered, other messages cannot be.

Enigma Code

The Germans worked around this limitation with their use of the Enigma Machine. Inside was a typewriter keyboard, a series of rotors, and a lighted display. The rotors were electromechanical substitution ciphers with wires that would connect 27 inputs to 27 outputs. Every time a user pressed a key, an electrical current would run through the rotors connecting the key to the light. Then the rotor would rotate into a new position. A user could press the same key over, and over again, and each time would create a different connection to a new light.  

In short, the encryption rules didn’t change every 27 letters; the encryption rules changed with each and every key-press. The receiver would simply set up everything in reverse, plug the received message in, and pull the secret message out.

 

Enigma machine courtesy of the Museo della Scienza e della Tecnologia "Leonardo da Vinci" [CC BY-SA 4.0]. Image by Alessandro Nassiri

 

This was an absolutely brilliant scheme that took several governments and millions of man-hours over the course of several years to solve. And that involved capturing the machine and a codebook from the Germans.

The issues the Enigma machine didn’t solve?  There was some forward secrecy—once the Allies had figured out one code—they only had the codes for a single day’s worth of messages. But in an ideal situation, one code broken would lead to just a single message compromised. Also, the Germans still had to share physical code-books from one location to another location, which means the books could be intercepted or copied by spies.

The Beauty of Asymmetry

Whitfield Diffie and Martin Hellman came up with an ingenious realization. The same properties of multiplication that allow the multiplication numbers in any order allow the multiplication of numbers in different locations. The article that follows this one will explain the Diffie Hellman algorithm and modular arithmetic in detail. But essentially the sender and receiver each calculates half of a math problem, exchanges their answer with the other, and then completes the calculation.  

What the sender and receiver are left with is a number that can be used to encode/decode a secret message. The information that is shared is known as a public key, and when it is multiplied by a private key, it creates a shared secret. The private key of one user is multiplied by the public key of the other.

This arrangement allows for secrets to be created in full view of an enemy, with the enemy unable to do anything with the information.

 

What’s next?

The next two articles will cover the Diffie-Hellman exchange as well as elliptic-curve cryptography (ECC) and elliptic-curve Diffie Hellman.