The history of encryption part 1

This article deals with the history of encryption and is the first part of two articles about this topic. All techniques were described in a chronological order. In this part of the article I deal with:

  • Introduction
  • Scytale and transposition cipher
  • ROT 13 and Caesar cipher
  • Maria Stuart and Babington Plot
  • Le Chiffre indéchiffrable (Vigenére square)
  • One-Time-Pad

Introduction

With the use of public transmission paths for discrete information, it was neccessary to transmit the information safe and secret. A Information represents (at least for sender and receiver) a sequence of tokens that makes sense to them. Without any sense, it would be just a message. We can define the word information as a message with sense and meaning. Just the sender and the receiver know the logic of the message (to create an information). Well, this is the ideal case, but it is not the reality. Normally, a few more people as the sender and the receiver know the logic and the meaning of a sequence of tokens. The sender and, it’s counter part, the receiver have to consider a technique, to keep the message secure. In the history of humantiy, we found a few examples for encryption methods with political and economical background. But the encryption of private messages was also used, to keep a affair secret. A lot of women used cryptography to send intimate messages to her lovers. In this article, I will try to cover the important examples, to show how necessary encryption is.

The franziscian-monk Roger Bacon was the first, who published a book about encryption methods “Abhandlung über die geheimen Künste und die Nichtigkeit der Magie” (Treatise on the secret arts and nullity of magic). This was happened in the 13th century.  Bacon mentioned a few algorithms to encrypt a text with the normal alphabet. For instance “Atbash” (Atbasch) is a simply monoalphabetic substitution with the following rules.

source 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
target Z Y X W V U T S R Q P O N M L K J I H G F E D C B A

              
source HELLO WORLD
target SVOOL DLIOW

As you can see in the table, the source alphabet was mirrored by the target alphabet. There is nothing special! But how to crack this cipher? To reveal the solution, you have to find out the target language (english, german, e.g.) and after that, you have a table with a letter from the alphabet and the occurring probability of the letter in the specific language (frequency table). With this table, you can find out, how the letters are exchanged. This substituation of two letters is called a bigram (n-gram). In addition to that, you can simply exchange the letters, if you know the applied algorithm and all neccessary parameters. But, this is not the normal case.

Example of a frequency table

letter    frequency in %
e 12,702
t 9,056
a 8,167
o 7,507
i 6,966
n 6,749
s 6,327
h 6,094
r 5,987
d 4,253
l 4,025
c 2,782
u 2,758
m 2,406
w 2,360
f 2,228
g 2,015
y 1,974
p 1,929
b 1,492
v 0,978
k 0,772
j 0,153
x 0,150
q 0,095
z 0,074
ï 0,01

source: wikipedia.org

This table shows the frequency of occurence from all possible letters in the english language.

Nearly all encryption methods, that were invented in this era, works with monoalphabetic substitution. After that, the encryption algorithms were oriented on encoding words (not just simple letters). The mix of encoding words and encrypting letters is called nomenclature codes. This codes works with a substitution table and can also be cracked with a frequency analysis and the semantic knowledge of syllables and words. It would be a great help, to have the knowledge about the sense and the motivation of the message. Often, you can interpret half decrypted parts of a message and try to test any words related to the motivation of the text. To know the syntactic and semantic structure of the encrypted text, is the key of decrypting such nomenclature codes. In the subsequent chapters, I will talk about encryption methods in detail.

Scytale and transposition cipher

To encrypt a plain text with a transposition method means to change the position of a letter in a text. In contrast to the substitution, the transposition method performs no exchange of letters (monoalphabetic substitution), just a change of their positions. This method is immune against frequency analysis. The reason is, that the frequency analysis (at least in this case) can approximatly decide, which language was used to encrypt the message. But why “approximatly”? The frequency analysis can compare the frequency of occurence of every letter, with a frequency table of every language. The frequency table of the language, which matches best with the frequency table of the encrypted message is probably the language of the encrypted message (implied that the cipher works just with transposition). A mixture of transposition and substitution prevents the message from finding out the natural language.

scytale image

Scytale | source: wikipedia.org

A Scytale is a stick (cylinder) with a strip of paper (or earlier parchment) wound around it. The number of corners is the key to decrypt the text. The sender writes the message on the parchment of his stick. After that, he or she sends a courier to the receiver. The receiver has a stick with the same number of corners and can wound the piece of parchment around his stick. When the receiver has the right stick, he or she can read the decrypted text. This method was used by the Spartans and the ancient greeks to encrypt military messages. The security of a Scytale was really strong. With the idea, to develop a lot of sticks with a different number of corners, the Scytale was assailable. After the invention of mechanically en- and decryption the Scytale as tool was obsolete, but the concept was still used.

ROT 13 and Caesar Cipher

Julius Caesar (dictator of the Roman Republic), known for his assertiveness and wisdom, used a simple (but in his era really strong) method to encrypt his messages to the generals and centurions. He used a technique similar to the Atbasch example above. Of course, Caesar lifes a few decades earlier, but he also knows the idea of monoalphabetic substitution. His cipher can be named ROTx (Rotate x), in which the x is a number, that describes the number of positions to rotate.  ROT13 is a special case of the Caesar cipher and the name was created by Usenet users in 1980. This cipher is a Caesar cipher with the shifting factor 13 (x equals 13). Example:

source 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
target N O P Q R S T U V W X Y Z A B C D E F G H I J K L M

              
source HELLO WORLD
target URYYB JBEYQ

In Caesars era, that cipher was strong, but later, arab scholars invented the frequency analysis method to break such ciphers.

Maria Stuart  and Babington Plot

Maria Stuart was born on 8th december of 1542. In 1543 she was crowned as Queen of the Scots. After any affairs, marriages and conspiracies Maria Stuart was deposed and escaped to england. There she was arrested. After 18 years of imprisonment, she has a ray of hope. She receives letters from Anthony Babington. Babington encrypted his letters with nomenclature codes and Maria Stuart knows to decrypt the text. At first she received a paper of all nomencalature codes. After that, Babington sends all encrypted messages. The spy’s of Walsingham, the security minister of queen Elizabeth, analyze the messages that Maria Stuart received. Thomas Phelippes was one of the spy’s. After a couple of message and doing frequency analysis with this message, Phelippes cracks the cipher and decrypt all messages. He found out, that Maria Stuart and Babington planning a assassination against the queen Elizabeth. Then, Walsingham forces Phelippes (who was a genius in faking fonts) to write an encrypted letter to Maria Stuart to find out, which people are the insurgents and the accomplices. After this attack from Walsingham (today, it would be called “Man-in-the-middle-attack”), Maria Stuart was executed in England.

This example makes clear, how risky encryption and the decryption of it can be. This nomenclature code can be decrypted by application of the frequency analysis. But one condition is, that the cracker must know, whether all symbols are substituated, words are encoded or both methods are used. With this knowledge, you can crack this nomenclature codes with a simple frequency analysis.

Le Chiffre indéchiffrable (Vigenére square)

After the invention of the frequency analysis from the arab scholars, the security of the monoalphabetic substitution was broken. Blaise de Vigenére, a french diplomat, used an idea from the italian polymath Leon Battista Alberti to invent a method called polyalphabetic cipher. This cipher works with 26 (because of 26 letters in the latin alphabet) alphabets side by side. Every alphabet starts with another letter. Have a look on the image below:

source: pad2.whstatic.com

The Vigenére cipher works with a key phrase. Consider the following example:


              
plain text  HELLO WORLD
key phrase  KEYKE YKEYK
encrypted result  RIJVS UYVJN

But how does it work? The decryption of a message, that is encrypted with a Vigenére square was, in the era of invention, really strong. You must have the right Vigenére square to decrypt the text. Another renewal was the encryption key. The key was used to encrypt the message. So, the receiver needs the right Vigenére square and the correct key phrase. Now, here comes the explaination of the example above.

The text to encrypt is “HELLO WORLD”. We use the key phrase “KEY” for the encryption. If the key phrase is shorter than the message, then the key phrase will be repeated so long as the length of the plain text will be reached. So, our key phrase is “KEYKEYKEYK”. With our correct Vigenére square, we can start to encrypt the message. The square has a extra alphabet on the upper side and also on the left side. For the first letter from the plain text we have a look on the alphabet in the header row. We call this position plain1(H). After that, we have a look on the left side and we keep our focus on the first letter of the key phrase. This position has the name keyphrase1(K). Now, we have the position of the letter of the plain text and the position of the letter in the key phrase. The cell, were plain1(H) and keyphrase1(K) join together, is the letter of our encrypted text. For that example cell(plain1(H), keyphrase1(K)) = R. For all other letters, the algorithm is the same.

For the era of invention, the polyalphabetic substitution was very strong. The cryptoanalysts countered with a few procedures and algorithms to crack the cipher. One algorithm was used to detect the key length. Some methods to detect the key length with redundancy of natural languages are the Kasiski-test (method of Charles Babbage) and the Friedman-test. In case of a short text, a good method is to find out which words can be placed at the beginning of the text. For instance, the first word “HELLO” is more likely then the word “HFAKF” or other senseless combinations. So the range of possible n-gram’s falls rapidly. So you can appreciate a possible key with a brute force attack. In the best case, you can try to find the key. After you found out any possible parts of the key, you have a simple Caesar cipher, which you crack with the frequency table (precondition: knowledge about the used source language).

One-Time-Pad

The One-Time-Pad (OTP) method is a encryption method that is, when it is used correctly, safe and theoretically not breakable. The concept behind this encryption is, that the key (One-Pad) is used just one time. The second constraint is, that the key phrase is as long as the plain text. Here are any other constraints. The key…

  • must be secret
  • must be unpredictable and random
  • may only be used one time

The recipient receives a bundle of x One-Time-Pad keys. With the keys, the receiver can respond x/2 messages and can answer x/2 messages. There are a lot of methods to en- and decrypt messages. Just one example is the Vigenére square.

As I mentioned a few sentences before, this procedure is absolutly safe (because of the key length). That is a big advantage. On the other hand, it is a high expenditure to bring new keys to the receiver/sender. Furthermore, this method needs a central position, that generates the keys. And last but not least, a strong disadvantage is the way of exchange the keys, which can be attacked. This can be called a Man-in-the-Middle-attack.  As you can see, the OTP method is safe, but not practicable with a high number of messages.

This was the first part of my “History of Encryption” series. The second part will deal with:

  • Enigma machine
  • One-time-pad
  • Public Keys
  • Pretty Good Privacy
  • Quantum cryptography

9 thoughts on “The history of encryption part 1

  1. thrilling car games says:

    You’re so cool! I don’t suppose I’ve read through something like that before.
    So wonderful to discover another person with some original thoughts on this subject matter.
    Seriously.. thank you for starting this up. This site is something that is required on the web, someone with a bit of originality!

  2. dota 2 key giveaway says:

    Hi there! Your websites are loading slowly for my situation, the site went
    on like a moment in order to load, I actually do not
    know whether it’s just simply me or your web page however ,
    twitter loaded for me. Well, I am going to thank you so much for
    attaching awesome blog post. In my opinion this has been totally helpful to user who actually visit here.
    I am hoping I’ll be able to find more amazing information and I
    really should compliment you by saying you have done amazing work.
    To obtain additional information by content you write-up, I have saved to my
    bookmarks this url.

  3. 特価,送料無料 クワトロ メンズ腕時計 シンプル スタンダード g31 上質,正規品SALE says:

    http://www.rpnails.com/2251gjwuQDQ6s2bazRrX.html

  4. http://www.modasyuca.com/vJ4ZneDdpAC9ySG02517.html says:

    海外通販,本物 コカ·コーラ 太陽のマテ茶2Lペットボトル×2ケース(6本入り1ケース) コカコーラ 2000ml 限定SALE,安い

  5. http://www.bainsdebreteuil.com/q8dEl7iX1pttpied5165.html says:

    http://www.bainsdebreteuil.com/3WYGcjob4EgEtYFs2566.html

  6. http://www.husv.net/index.php?PremiumQualityFactsonHowToWinBlackjackYouMustUnderstand says:

    Naturally, any takings can also be faux but in the lowest, you’re
    able to perform your favorite games for-free.

  7. voyage etats unis cote est says:

    Avec deux guides sur l’ouest des Etats Unis, j’ai pu constater un grand vide au niveau culinaire:
    aucun des guides ne parle des fast foods ou des chaines de restaurants
    comme la Cheesecake Factory ou Applebee’s.

  8. Rochelle says:

    A very first time purchaser has to understand and
    feel comfortable with the experts they are working with that no question is a dumb concern!”.

Leave a Reply

Your email address will not be published. Required fields are marked *