History of Computer Cryptography and Secrecy Systems

History of Computer Cryptography and Secrecy Systems

Jacob Mathai

• Steganography
• Cryptography
• Transposition
• Rail Fence Transposition
• Substitution
• Caesar Shift Cipher
• Kerchoffs’ Principle
• Claude Shannon
• Nomenclators
• Homophonic Substitution Cipher
• Vigenere Cipher
• One Time Pads
• Enigma
• Lucifer
• DES (Data Encryption Standard)
• Diffie-Hellman
• RSA

Steganography

A secrecy technique where the existence of an actual message is hidden. The word is derived from the Greek words steganos (covered) and graphein (to write). Steganography is ancient technique that has been used for thousands of years as a primitive for secrecy systems and secret communications. In the first century, Pliny the Elder described how the milk from a thitymallus plant could be used as invisible ink. Another technique in ancient Greece and Persia involved shaving a messenger’s head, writing a message on his scalp and waiting for the hair to grow back before sending the messenger to the destination. The technique primarily achieves security through obscurity and it’s basic weakness is that if the message is discovered, the secret communication is revealed.

Cryptography

Cryptography is a technique used to hide the meaning of a message and is derived from the Greek word kryptos (hidden). This is different from steganograhic techniques in that one is not hiding the actual message, only the meaning of the message. If a message were to fall into the hands of the wrong person, cryptography should ensure that that message could not be read. Typically the sender and receiver agree upon a message scrambling protocol beforehand and agree upon methods for encrypting and decrypting messages. Cryptography is further divided into two implementation techniques and those include transposition and substitiution.

Combining Cryptographic and Steganographic Techniques

It is possible to combine Cryptography and Steganography together to achieve a higher level of security. Combining these two primitives should both hide the meaning of a message as well as conceal the physical message. If the message is intercepted, it can be blocked but not read. During WW II, the Germans would scramble messages and then shrink the text down to a tiny dot and insert the dot as a “period” in some unsuspecting letter or text for secret communications.

Transposition

Transpostion is a cryptographic technique whereby the letters in a message are rearranged to provide secrecy. Think of the word dog and all of the ways one could arrange the letters — dog, dgo, odg, ogd, dgo, odg — this anagram is a simple example of transpostion. The position of the original letters all retain thier idenities but change there original positions. As you increase the size of the message to over 40 letters however, the number of permutations grow exponentially and it becomes very difficult to decrypt such a communication. Typically the sender and receiver agree upon a technique to encode and decode messages using transposition. One of the first cryptographic devices using transposition dates back to the fifth century and was named the Spartan Scytale. The Scytale worked as follows — a fabric was wrapped around a staff and a message was written on the cloth. Once unwound, the cloth appreared to have a meaningless scamble of letters. THe sender and the receiver would both have matching sized staffs to secure mutual communications.

Rail Fence Transposition

Rail Fence Transposition is a technique where a message is written on two or more lines with each consecutive letter of the message being written on the next consecutive line. The text on the second and third lines are then appended to the first line to create a the scrambled message. A simple 2 line rail fence transposition of the message “Hello World” is demonstrated below :

• Simple 2 Line Rail Fence Transpostion
• Hello World (Original Message)
• H l o W r d (Line 1)
•   e l     o l  (Line 2)
• HloWrdelol (Transposed Message)

Substitution

Substitution is a cryptographic technique where each letter of the plaintext message is replaced by a different letter. Each letter retains its original position in the message text, but the identity of the letter is changed. This type of technique was documented during Julius Caesar’s Gallic Wars.

• Simple Substitution Cipher
• A B C D E  (Plain Alphabet)
• D C E G H (Cipher Alphabet)
• If one were to send the message ‘BAD’ to someone using this simple cipher, the encrypted message text would read ‘CDG’.

Plain Text, Ciper Texts, and Ciphers

Plain Text refers to the human readable alphabet used to compose the original message. Cipher Text refers to the encrypted plaintext message once the original letters in the message have been substituted with the cipher alphabet. Ciphers are any form of cryptographic substitution applied to message text.

Caesar Shift Cipher

A simple substitution cryptographic technique where the cipher alphabet is shifted a certain number of spaces relative to the original plain alphabet. It was named for Julius Caesar who employed the technique to secure military communications. This is generally a weak encryption method in that there are only 25 distinct variations of shifts before the original message is revealed. A simple 4 letter shift example is demonstrated below :

• 4 Letter Shift Cipher
• 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  (Plain Alphabet)
• E F G H I J K L M N O P Q R S T U V W X Y Z A B C D  (Cipher Alphabet)
• If one were to encrypt the plain text message “MEET ME AT MIDNIGHT”, the cipher text would read “QIIX QI EX QMHRMKLX”.

Ciphers, Algorithms, and Keys

An Algorithm is a general method of encryption and a Key specifies the details of that particular encryption. Together they form Ciphers or encrypted messages. In the case of a substitution cipher, the algorithm would be replacing plain text letters with cipher text letters and the key would be the actual cipher text alphabet.

Kerchoffs’ Principle

Auguste Kerckhoffs was a military cryptologist in the late 19th century. He proposed a radical departure from traditional methods of securing communications in his day. He proposed that the one should assume that the encryption algorithms should be open and transparent and the only secured piece of the cryptographic system should be the key. It was a departure from many of the Steganographic techniques of the past and is the basis of modern cryptography. If you think about RSA or 3DES, the encryption algorithms are well known and advertised and the keys are the only unknown element of the system. If a key is compromised, it is quickly changed and communications are secured once again. Knowledge of the algorithm itself does not render communications any less secure.

Nomenclators

Nomenclators are an encryption techniques that use a combination of codewords and ciphertext alphabets to secure communications. The weakness in this technique is that the codewords and ciphertext are typically written down by both the sender and receiver and is vulnerable to enemy capture. This is different than memorizing 26 ciphertext letters and or distributing a new key once an existing key is comprimised. A code can be described as substitution at the ‘word’ level and a cipher is substitution at the individual ‘letter’ level.

Homophonic Substitution Cipher

In a homophonic substitution cipher, each plaintext letter is replaced with several different ciphertext letters. Generally speaking, as the frequency of the letter increases, the number of potential ciphertext letters would increase proportinatly. For example the letter “E” may have a frequency of 12% for most communications and would potentially have 12 different ciphertext letters representing it. This would complicate simple attempts at frequency analysis because an encrypted message would represent a single letter “E” with 12 distinct ciphertext letters.

Vigenere Cipher

A Vigenere Cipher, named after a french diplomat Blaise de Vigener, is polyalphabetic substitution cipher first documented in the 1500’s. It is commonly called a Vigenere square which consists of a plaintext alphabet, followed by 26 alphabets each respectively shifted by a single letter. The strength of the cipher lies in the fact that a single letter can be represented in several different ways because 26 distinct alphabets are used and this poses a challenge to traditional frequency analysis techniques. Typically, the sender and receiver agree upon a key (in this case a word) and use the key to synchronize on which of the 26 alphabets to use to encrypt and decrypt messages. Here is an example :

If the sender and receiver agreed upon the keyword of “JAKE” and the sender wanted to encypt the plaintext word “Unix” and send it to the receiver, it would be similiar to the following :

To encrypt the plaintext letter “U” using the keyword “JAKE”, one would start with the leftmost row beginning with the letter “J” and find the intersection point with the top most row with the letter “U”. In this case the first letter of the ciphertext would be “D”. Next, you would find the leftmost row beginning with the letter “A” and find the intersection point with the top most row with the letter “N” which happens to be the ciphertext letter “N”. This process continues iteratively and the keyword is reused over and over as the plaintext message lengths increase. Generally speaking, a longer keyword provides some additional security. Wilhelm Kasiski and Charles Babbage seperately cracked the Vigenere cipher by using frequency analysis of letters in the English language and comparing them to encrypted ciphertext messages.

One Time Pad

The One Time Pad is a technique that offers ‘perfect theoretical secrecy’ by using a truly random key only once per communication. Imagine a sender and receiver, each having matching pads filled with hundereds of pages of unique keys composed of truly random letters. The sender would encrypt a message using a Vigenere square and the first key in his pad and the receiver would decrypt it in the same way. At this point, both the sender and receiver would discard the first page of their pads (destroy the last used key) and continue using new keys for future messages. This offers perfect secrecy because even if a single key is compromised, it does not reveal anything about future or past transmissions. The strength of the technique lies in randomness and one time use of the keys. Claude Shannon described how if the ciphertext, key, and plaintext are changing at a consistent rate, you are have achieved perfect secrecy in his 1949 paper Communication Theory of Secrecy Systems.

Enigma Cipher

Invented by Arthur Scherbius, Enigma was Germany’s main cryptographic technology during WW II. Folllowing the decryption of the Zimmerman note during World War I and the effects that weak ciphers had on the war’s outcome, Germany was looking for “the unbreakable cipher” and was interested in leveraging automation and the use of machinery to replace traditional paper and pencil techniques. The Enigma machnie consisted of a basic keyboard, a display that would reveal the cipher text letter, and a scrambling mechanism such that each plain text letter entered as input via the keyboard was transcribed to its corresponding cipher text letter. The machine was modular in design and multiple scrambling disks were employed to thwart attempts at frequency analysis and these scrambling disks and there particular positioning inside engima emulated many different cipher alphabets. To decipher a message, the receiver require a code book (shared by both the sender and receiver) detailing all the specific scrambler settings for the day and would also have an identical enigma machine. Breaking Enigma was crucial to ending World War II and it was eventually broken due in large part to the work of Marian Rejewski, a polish statistician, mathematician, and code breaker. Although Rejewski never broke the Enigma, he transfered all his research to the English and the French weeks before Germany invaded Poland. Eventually, Alan Turing and the code breakers at Bletchley used Rejewski’s work to build Bombes which were electromechanical machines that were designed specifically to break Enigma.

Lucifer and DES

Lucifer was a symmetric encryption algorithm created by Horst Feistel in the 1970’s while working at IBM. The scrambling technique of Lucifer was quite involved and begins with translating the plain text string to binary format. Next, the binary string is shuffled and divided into 64 bit blocks and encryption happens on a per block basis. Each of these ‘blocks’ are split into 2 32 bit blocks and they are named “Left(0)” and “Right(0)”. The “Right(0)” block is put through a mangle function which rearranges the binary numbers using a fairly complex substitution cipher. The “Right(0)” block is then added to the “Left(0)” block to create a new half block called “Right(1)” and the original “Right(0)” block is renamed Left(1). This series of steps is called a “Fiestel Round” and is repeated 16 times in total. The mangler function can change and is determined by a key the sender and the receiver agree upon. A modifed version of Lucifer was adopted as the American standard for encryption known as DES or the Data Encryption Standard. The main difference between Lucifer and DES was that the NSA limited DES to 56 bit keys to balance national security interests against personal and corporate privacy needs.

Diffie-Hellman

Whitfield Diffie and Martin Hellman were pioneers in the fields of asymmetric cryptographic techniques. Prior to thier work, most encryption was symmetric and involved the send and receiver sharing a key to secure communications. They focused on one-way functions which is simple to run and very difficult to undo. THe Diffie-Hellman key exchange enables sender and receiver to establish a secret key publically without any prior key sharing. This asymmetric key system is one in that the encryption and decryption keys are not identical and revolutionized cryptography for years to come. For the first time in history, Alice and Bob could secure communications without any prior interaction. This idea was later incorporated into RSA named after Rivest, Shamir, and Adleman and is a common cryptograhic technique on the internet today.

RSA

• Alice picks two large prime numbers ‘p’ and ‘q’ .
• Alice multiplies p * q to get a number ‘N’
• Alice picks another number ‘e’ that is relatively prime to (p-1)*(q-1)
• Calculate an integer d from the quotient (ed-1)/(p-1)(q-1). The number ‘d’ is the private exponent.
• Alice publishes ‘e’ and ‘N’ so that Bob can see it.
• Bob encrypts messages with C=M^e(mod N)
• Alice decrypts Bob’s message with the following formula : M=C^d(mod N)