Cryptography - History and Basics
Cryptography - Symmetric Key Algorithms
Cryptography - Asymmetric Key Algorithms
Cryptography - Hash Functions & Digital Signatures
History of Cryptography
Speech and written communication defined early civilizations and continuously evolved with human societies. In the beginning, humans used Petroglyphs, which evolved into Pictograms (Hieroglyphs), and finally Ideograms. Today carry flash storage devices stuffed with the information of the Encyclopedia Britannica in our pocket.
As long as humans have been communicating, they tried to hide the true meaning of the written word from others. Ancient civilizations used complex systems of secret symbols and the evolution of those systems are the codes and ciphers we facilitate to enable private communication today.
Substitution Cipher: Caesar Cipher
In crypto, the Caesar cipher is one of the earliest known systems and was used by Julus Caesar to communicate with Cicero in Rome while he was conquering Europe. It is a substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a right shift of 3, A would be replaced by D, B would become E, and so on.
This is called ROT3 (Rotate 3) cipher and encryption/decryption is mathematically implemented by converting each letter to its decimal equivalent. A is 0 and Z is 25. The wrap-around is done by using the modulo function. (C = ciphertext, P = plaintext)
decrypted message: WINTER_IS_COMING
math to encrypt: C = (P+3) mod 26
encrypted message: ZLQWHU_LV_FRPLQJ
math to decrypt: P = (C-3) mod 26
This cipher is easy to use but also easy to crack. It is vulnerable to frequency analysis since the most common letters in the English language are E, T, A, O, N, R, I, S, and H. Attackers just need to find the common letters in the encrypted text (in my example the letter “I”) and experiment with substitution to break the cipher.
Transposition cipher: Rail Fence Cipher (ZigZag Cipher)
The rail fence cipher was used by the ancient Greeks in the scytale, a mechanical system of producing a transposition cipher. The system consisted of a cylinder and a ribbon that was wrapped around the cylinder. The message to be encrypted was written on the coiled ribbon. The letters of the original message would be rearranged when the ribbon was uncoiled from the cylinder.
Another approach is to write the plain text downwards and diagonally on successive “rails” of an imaginary fence, then moving up when the bottom rail is reached. When the top rail is reached, the message is written downwards again until the whole plaintext is written out.
message: JON_SNOW_IS_A_TARGARYEN
3 rail fence:
encryption with a 3 rail fence:
encrypted message: JS_ARYO_NWI__AGRENOSTAN
The message was easily decrypted when the ribbon was recoiled on a cylinder of the same diameter or by trying out multiple fence methods.
Advanced Substitution: One-Time Pads
A one-time pad is an extremely powerful type of cipher and uses a different substitution alphabet for each letter of the plaintext message. It can be represented by the following function. (C = ciphertext, P = plaintext, K = encryption key)
decrypted message: WINTER_IS_COMING 22 08 13 19 04 17 08 18 02 14 12 08 13 06
one-time pad: ZVFXZVFXZVFXZV 25 21 05 23 25 21 05 23 25 21 05 23 25 21
math to encrypt: C = (P+K) mod 26
encrypted message: VDSQDM_NP_BJRFNMB 21 03 18 16 03 12 13 15 01 09 17 05 12 01
math to decrypt: P = (C-K) mod 26
The advantage of one-time pads is that there is no repeating pattern of alphabetic substitution. This cipher is called Information-theoretical-secure. It is an unbreakable encryption scheme if the following requirements are met.
- The one-time pad must be randomly generated without the use of a reoccurring pattern.
- The one-time pad must be protected against disclosure. The message can be easily decrypted if the adversary has a copy of the pad.
- Each pad can only be used once (one-time). Reusing the same pad on multiple messages makes it possible to determine the key value used.
- The key must be at least as long as the message so each character of the key is used to encrypt one character of the message.
The advantage of the one-time pad is broken as soon as one of those requirements is not met. One of the major intelligence successes of the United States during the Cold War was when US cryptoanalysts broke the top-secret Soviet cryptosystem that relied on a one-time pad. The project called VENONA discovered a pattern in the key values. The Soviets violated rule number one of one-time pad crypto.
My example does it as well by just repeating the same key (ZVFX).
One-time pads have been used throughout history to protect sensitive communication. The major challenge of the system is the generation, distribution and, safeguarding of the key.
Code Breaking
Frequency analysis is the basic tool for breaking most classical ciphers. It utilizes the fact that in languages, certain letters of the alphabet appear more often than others. With a long enough ciphertext a reasonable representation count of letters can be created and ultimately the code be broken.
In the 15th century the Vigenère cipher (polyalphabetic substitution aka series of interwoven Caesar ciphers) was invented and considered to be completely secure (le chiffre indéchiffrable—”the indecipherable cipher”) until a successful attack method was published in 1863.
During World War I and World War II the deciphering of messages played a significant part in the success of a campaign. The US/UK broke the Lorenz Cipher and the Enigma Machine which is said to have played a decisive factor in the Allied victory. The Germans broke the Naval Code #3 and #5 which enabled the early successes in the Battle of the Atlantic.
Today the Information or Cyber Domain is an official dimension of modern warfare. Intercepting the enemies communication and deciphering the information is a common theme with all major military powers.