Introduction to Cryptography

LEARN MATH FOR WHAT? LEARN MATH TO SECURE YOUR COMMUNICATION!

Intro

Since ancient times, humans have had high demand for communicating and exchanging information with others, a large part of which we want to communicate privately with certain people. This is why Cryptography was born! The series of articles on Cryptography will come to readers in the near future. In this first article we will briefly learn about the history of cryptography, and some classical encryption methods.

The origins of cryptography can be traced back to ancient civilizations such as Egypt, Greece, and Rome. One of the earliest known examples of cryptography is the use of hieroglyphs, a writing system used by the ancient Egyptians. In 1900 BCE, an Egyptian scribe used non-standard hieroglyphs in an inscription, which is considered an early example of a simple substitution cipher. This method involves replacing each letter in a message with another letter, symbol, or number. _config.yml This inscription features some strange hieroglyphics. But others believe it to be the earliest known example of a substitution cipher, utilizing hieroglyphs rather than letters or numbers. For what reason, you ask? To preserve the sacred nature of their religious rituals from the common people. Unfortunately, this disagreement among scholars makes it hard to point definitively at the tomb of Khnumhotep II as the first written evidence of cryptography.

Notation

I will introduce some useful notations as follows:

  • m is the message A wants to send to B (plaintext) and c is the encryption piece of m (cipher text), k is the key that will be generated to encrypt m (key)
  • The encryption method between A and B must be public, assuming that the only thing kept secret is the key k(should be completely secret) (how to generate such a key k will be discussed in later articles).
  • an encryption method defined over the set (K,M,C) (where K is the set of all keys, M is the set of all texts, C is the set of all encrypted texts) is a pair of functions (E,D): E takes two values ​​k,m and returns the value c; D takes in two values ​​k, c and returns the value m, such that if we encrypt information with function E using key k, we will be able to decrypt information with function D using key k _config.yml

    Classical Cryptography

    Hieroglyphs Cryptography:

  • The earliest known use of Cryptography can be dated back to 1900 BCE during the time of the Old Kingdom of Egypt in form of non-standard hieroglyphs. 
  • Hieroglyphs were a secret form of communication that the Egyptians used to communicate with one another. 
  • This secret text was known only to the scribes of the kings who used to transmit messages on their behalf.
  • This type of Cryptography is not so related to Mathematics, more like a puzzle, so I will not discuss it too much here.** _config.yml

    Caesar Cipher

    Caesar Cipher is the oldest and most famous encryption method, it works as follows: select a number k (for example k=3) (in modern encryption we can call k a key). Then, we shift all the letters in the alphabet by k times: For example: we want to encrypt the word “HELLO” using Caesar Cipher for k=3:

H becomes K (shift 3 from H) E becomes H (shift 3 from E) L becomes O (shift 3 from L) L becomes O (shift 3 from L) O becomes R (shift 3 from O)

The encrypted message is now “KHOOR”. _config.yml

To decrypt the message, you simply need to shift each letter back by the same number of positions. In this case, you would shift each letter in “KHOOR” back by 3 positions to get the original message, “HELLO”.

However, Caesar Cipher is badly broken, here is how: A substitution cipher can be attacked by Statistical Method _config.yml By analysing the frequency of each letter in the cipher text (and/or the frequency of pairs of letters), we can deduce what it stands for in the plain text and decrypt the whole message. This is an example of a Cipher-Text-Only Attack.

Vigenere Cipher: 

During the 16th century, Vigenere designed a cipher in which the encryption key is repeated multiple times spanning the entire message, and then the cipher text is generated by adding the message character with key character modulo 26. This approach is also vulnerable to attacks, where the secrecy of the message depends on the secrecy of the encryption key. _config.yml For example, take \(m\) to be “WHATANICEDAYTODAY”, and \(k_0=\)CRYPTO. First, we repeat the key multiple times to get a key that has the same length as the plain message \(len(k)=len(m)\). Then, we just need to add each pair of letters modulo \(26\) to get the cipher text \(c\). (see diagram) Unfortunately, this cipher is also not secure. I will show how we could attack it: - Step 1: Guess the initial key length (we don’t know how long it is, so we try them all!) take \(len(k_0)=1,2,3,\cdots\)) - Step 2: Start attacking, if we guess \(len(k_0)=6\), then the 1st, 7th, 13th,… letter in the key $k$ is the same. From here we apply the Statistical method! Take a look at every $(6k+1)$th letter of the cipher text, suppose the most common letter is “H”, we can imply that the first letter of the key is “H”-“E”=”C” (“E” is the most common letter in the plain text). Keep on doing this until we get the full message.

Rotor Machines (1870-1943)

Next, we will discuss the encryption method using Rotor machines (actively developed in the period 1870-1943), most notably the Hebern machine using a single rotor and the Enigma machine (using multiple rotors) used in World War II.

Hebern (single motor): has a secret key, rotates by 1 notch every time you press a key on the type writer

For example if you type “BAC” the encrypted message will be “SEK”

But, again, using statistical methods, with enough data, the Hebern machine can also be attacked. _config.yml The Enigma machine had a more complex encryption mechanism than the Hebern machine, using 3-5 rotors, producing more keys per encryption. Enthusiast readers can learn more in the following videos:

Number phile and Jared Owen or the following article

References

  1. geeksforgeeks website: https://www.geeksforgeeks.org/
  2. Cryptography 1 course on Coursera by Dan Boneh, Stanford University
  3. https://blog.puzzlenation.com/tag/khnumhotep-ii/

    Further Reading

    If you are interested in the History of Cryptography, and the recent developments in Cryptography, I suggest you read the following books:

  4. The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet (David Kahn)
  5. The Code Book (Simon Sigh)
  6. (More theoretical) Understanding Cryptography (Christoff Paar)
  7. At the end of the first article, I hope you are interested in Cryptography, using Math knowledge is very interesting, right?
Written on August 9, 2023