Science Break: Encryption, part one – the pre-digital era

The science of encryption is as broad as it is ancient. Since the dawn of recorded history, humans have devised innumerable methods to keep information secret from, or unintelligible to, others. It is a huge topic, so in part one I will look at a few historical methods of encryption, and then in part two (June 2013 RECORDER) will delve into some of the encryption technologies used in today’s era of the Internet and digital communication.

The struggle between those desiring to conceal thoughts and communications and those wanting to access them is active and intense, with ever more sophisticated forms of encryption developed to stay ahead of the code breakers. Probably the first form of encryption must have occurred on a cave wall, when a pre-historic human (or Neanderthal??) scratched out symbols that only others in the know could understand. Viewed this way, it’s not a stretch to consider any form of script as encryption, since throughout most of history educated readers were definitely a minority. The word cryptography is a combination of the ancient Greek kryptos (hidden) and graphein (writing) (Damigo, 2009).

The oldest known example of deliberate encryption is an Egyptian hieroglyph dated to ~1900 BC. Its substitution of certain common glyphs with more obscure ones was repeated often in the following hundreds of years, and was so crude and easily decoded that scholars wonder why they even bothered. Explanations include: to mystify religious secrets, keeping them safe from non-believers while at the same time adding a certain cachet to the religion – a form of marketing; to make records seem more impressive and official, just as today’s legal world expresses itself in gibberish when plain language would do; the simplest explanation – just a way for scribes to show off! (Team 28005, 1999)

Subsequently people got more cunning. An ancient Greek method involved wrapping a narrow roll of paper or parchment around a wooden cylinder of a specific diameter called a scytale (Fig.1), writing a message, and then sending off the quite indecipherable scroll without the cylinder; the recipient would rewrap it around a similar cylinder of the agreed upon diameter, and voila!, the message was deciphered. Of course it didn’t take an Archimedes to just try cylinders of different diameters... (Wikimedia Foundation, Inc., 2012)

A common Roman code is known as the Caesar Shift Cipher, because Julius Caesar sometimes encrypted correspondence with it. It involves shifting each letter of the alphabet a fixed number of characters over. For example, with a shift of 4, A shifts to E, B to F, C to G, and so on. This is defined as monoalphabetic substitution, and can be broken with frequency analysis, a technique first employed by Arabs ~1000 AD, and now commonly used to solve newspaper word games. Each language tends to use certain letters more than others. In English the letter ‘e’ is usually the most common. So to crack a Caesar Shift Cipher, a smart place to start is to substitute an ‘e’ for the most common letter (just as ‘e’ is a good first guess when playing the 100th tedious game of hangman with your grade 2 kid). This leads to further educated guesses, especially involving common articles such as ‘the’. Before long the code is broken.

Leon Battista Alberti (1404-1472), sometimes called the father of modern cryptography, is credited with developing the first form of polyalphabetic substitution. It incorporates two levels of encryption, rendering frequency analysis useless. There are many ways to implement such schemes, but Alberti used two copper disks that fit together and could turn relative to each other; each had the alphabet inscribed on its outer edge, and the substitutions were given by how the letters lined up. After a few words were encrypted, the disks would be rotated, creating a dynamic shift, versus Caesar’s static shift. To decipher, the recipient had to know when and how big the shifts were. A more practical implementation of this system used what is known as a Vigenère square (Fig. 2), named after the French cryptographer Blaise de Vigenère (1523-1596). A single code word and the table is all that is needed for both sender and recipient. An example is best used to illustrate its use. (Wikimedia Foundation, Inc., 2013a)

Let’s say the encoded message is, “Sell RIM now,” and the key word is the day of the week, say Friday. Friday is repeated as many times as required to cover off all the letters in the message. The key letter dictates which row to use to find the substitution letter. In this case the key letter for S is F, so we look along row F and find the letter X at the intersection of row F and column S; row R and column E gives V, and so on.

Note that because the shift changes dynamically as dictated by the key word, the first L is encoded as T, the second as O, demonstrating that frequency analysis won’t work.

One notable application of polyalphabetic substitution was invented by Thomas Jefferson. He invented the Jefferson disk (Fig. 3) in 1795. It used 26 numbered disks, each with the 26 letters of the alphabet scribed onto its edges in different random patterns. To use it, both sender and recipient had to arrange identical disks in exactly the same order on the axle. (Wikimedia Foundation, Inc., 2013b)

In 1863 mathematician Friedrich Kasiski published the first method that could successfully crack a polyalphabetic substitution code, but informal notes show that Charles Babbage had derived and used the same solution in 1846, and had never revealed his methods. The Kasiski examination as it is known, relies on having the same word (or string of letters) encrypted with the same key letters twice, an occurrence that obviously is increasingly more likely the longer the message. The intersections between two or more of these repetitions, each a different number of characters apart, makes the method more accurate. It can be supplemented by Friedman test methods involving an index of coincidence. These methods evolved much further, and for those mathematically inclined (which I am not), some links below offer delightful intricacies. (Wikimedia Foundation, Inc., 2013a)

Of course there are many other ways to jumble a message than mono- and polyalphabetic shifting – there is no limit to ways of transposing letters, as long as there are deterministic rules governing the shifts. Examples include reversing strings of letters or words, swapping pairs of letters, and all sorts of combinations of techniques. How about shifting each letter by successive digits of pi? Really the human imagination is the only limiting factor. I recently watched an episode of the British TV series Sherlock, where messages exchanged within a crime triad were coded as numbers; I believe each pair of numbers indicated the page and position of a word – the key was to discover what book they all were using (it was a travel guide of London).

No article on this topic would be complete without mentioning the Navajo code talkers (often given the more dramatic name wind talkers). This is an excellent example of how sometimes the simplest idea is the best. While the Axis powers in WWII were employing their top mathematicians to come up with ever more devious and cunning codes (more on this later), the Americans simply flew many native Navajo speakers to battle arenas. As long as there was a Navajo at both the transmitting and receiving radios, complex messages were exchanged freely, and the “code” was never uncovered. In fact, it was so successful that Navajos were still being used in the Korean War. This reminds me of something my older brother, a speech recognition expert, once mentioned regarding decryption. “This project I’m working on, to translate Arabic in real time, is a great way to stay employed, but personally, I’d hire one of the many fluent English speakers on the streets of Baghdad for just a few dollars a day.” I guess there just weren’t too many Navajos strolling the streets of Munich or Tokyo... (Navajo Code Talkers Foundation, 2013)

The Enigma Code is one of history’s most famous ciphers. I would describe it as the ultimate electro-mechanical expression of polyalphabetic substitution, reaching its apex during WWII. The actual mechanism is diabolically complicated, and although I’ve tried to read through the Wikipedia explanation several times, I have been unable to remain focused enough to finish, so I’ve given up!

Many variations of the machine, primarily German, were built (Fig. 4). Most had 3 or 4 rotors, turning on a common spindle, and each rotor had 26 pins and contacts which were connected internally in a specific and complicated pattern; combined, with the pins of each rotor touching the contacts of its neighbour, they created ever-changing electrical circuits (the number 26 means that the use of umlauts was unavailable, which for some reason I find hümorous). Each push of a letter on the key board delivered the encrypted letter via a different circuit, and advanced the rotors in some predetermined combination. The complicated path of the electrical circuit determined which letter was lit up as the encryption. For the system to work, senders and recipients had to start with an identical initial setting (the initialization vector in today’s terms), and of course this changed frequently enough to present code breakers with millions upon millions of possible solutions. This was done by displaying each rotor’s letter ring through a little window on the panel, so the initial setting was simply some chosen string of three or four letters. (Wikimedia Foundation, Inc., 2013c)

Polish cryptographers broke the Enigma code, and it has been said that this shortened the war by about two years. In the years leading up to the war they had been able to reconstruct an Enigma machine via espionage, and then developed methods that could crack codes some or most of the time. They shared this information with the British on the eve of WWII, and then British cryptographers, notably Alan Turing, further refined the methods. Rather than explain how the Enigma code was cracked, let’s just say that it was a combination of design weaknesses (such as the machine being unable to encrypt letters as themselves), poor operational processes (such as often using the same terms in messages, or repeating initial settings to ensure they were received correctly), and primarily, one of history’s greatest examples of collective, focused analytical thinking. (Wikimedia Foundation, Inc., 2013d)

I was curious what the Chinese were doing cryptically over the centuries. Surely with their advanced technologies, wars, political power struggles and intrigues, they had ample need of encryption? For once, they don’t seem to have outdone the round eyed devils. There is mention of swallowing wax-coated messages, proving the adage that it is better to give than receive, at least when it comes to secret messages. But that was a long time ago, and today digital technology and computer power have created a whole new world of encryption (and decryption) techniques, as we will see in part two.

I invite readers to try Apoterra’s cryptic crosswords created by myself and John Simmonds, at http://www.apoterra.com/resources/off-the-record/cryptic-crosswords/

Next month’s article: Applied science in the office.

References

Damigo, T. M. (2009). A brief history of cryptography. Retrieved February 4, 2013, from Student Pulse: http://www.studentpulse.com/articles/41/a-brief-history-ofcryptography

Fields, T. B. (2011, April 26). Vigenère square shading. Retrieved February 5, 2013, from Wikipedia: http://en.wikipedia.org/wiki/File:Vigenère_square_shading.svg

Navajo Code Talkers Foundation. (2013). Retrieved February 4, 2013, from Navajo Code Talkers: http://www.navajocodetalkers.org/

Team 28005. (1999). Course of history / Egypt. Retrieved February 4, 2013, from ThinkQuest: http://library.thinkquest.org/28005/flashed/timemachine/courseofhistory/egypt.shtml

Wikimedia Foundation, Inc. (2005a, August 7). Jefferson’s disk cipher. Retrieved February 5, 2013, from Wikipedia: http://en.wikipedia.org/wiki/File: Jefferson%27s_disk_cipher.jpg

Wikimedia Foundation, Inc. (2005b, April 15). Enigma Machine Labeled. Retrieved February 5, 2013, from Wikipedia: http://en.wikipedia.org/wiki/File:EnigmaMachineLabeled.jpg

Wikimedia Foundation, Inc. (2007, February 20). Scytale. Retrieved February 5, 2013, from Wikipedia: http://commons.wikimedia.org/wiki/File:Skytale.png

Wikimedia Foundation, Inc. (2012, October 12). Scytale. Retrieved February 5, 2013, from Wikipedia: http://en.wikipedia.org/wiki/Scytale

Wikimedia Foundation, Inc. (2013a, January 25). Vigenère cipher. Retrieved February 5, 2013, from Wikipedia: http://en.wikipedia.org/wiki/Vigenère_cipher

Wikimedia Foundation, Inc. (2013b, January 29). Jefferson disk. Retrieved February 5, 2013, from Wikipedia: http://en.wikipedia.org/wiki/Jefferson_disk

Wikimedia Foundation, Inc. (2013c, February 5). Enigma machine. Retrieved February 5, 2013, from Wikipedia: http://en.wikipedia.org/wiki/ Enigma_machine

Wikimedia Foundation, Inc. (2013d, February 3). Cryptanalysis of the Enigma. Retrieved February 5, 2013, from Wikipedia: http://en.wikipedia.org/wiki/ Cryptanalysis_of_the_Enigma