Introduction to Cryptography: Part I

written by Rachata Tosirisuk, CAT Telecom & USC alumni
edited by Dr. Thiparat Chotibut, Chulalongkorn University & QTFT

If you have read Introduction to Modern Cryptography by Jonathan Katz, feel free to skip this article! The article and its sequels attempt to summarize the textbook to laypeople.

Cryptography has been with us for ages. The original formulation was not as complex as the modern one. Its original intention was very simple; to preserve the privacy of the message. The ancient cryptographic methods were typically used to encrypt messages into codes by the sender, and the intended receivers decrypt the codes into correct messages.

In ancient Cryptography, encryptions appeared beautiful yet complicated, like a piece of visual art. Ancient cryptographers developed more and more efficient message encryptions, turning a message into a concise yet visually complex code. Nevertheless, there was no rigorous nor systematic study of Cryptography until the 1970s that mathematical encryption began to play a key role in Cryptography. Then, cryptographic methodologies began to transform from complex pieces of visual art into a systematic science.

A scytale, a tool from the ancient Greeks to perform a transpositional cipher, believed to be used to communicate between parties in military campaigns. [image source]

Before moving on, let me introduce some keywords:

• Codes is not a common term in Cryptography literature. In the literature, codes are commonly called ciphertext.
• While, in layman term, a sender wants to send a message, a message is commonly called a plaintext in the literature.
• Therefore, a message or a plaintext is encrypted into a ciphertext, which is transmitted over a channel. The receiver then decrypts the transmitted ciphertext into a plaintext.

Although there could be variations of the keywords that depend on the context, we will mostly use message, plaintext, ciphertext, encrypt, and decrypt in this article and the sequels as mentioned above.

The most basic form of encryption that is still widely used today is a Private-Key Encryption or a Symmetric-Key Encryption. It was designed to enable two parties to communicate with each other secretly. If there is an eavesdropper (commonly named Eve), who could detect the communication between the two parties (commonly named Alice and Bob), Eve will not be able to understand the meaning of the communication between Alice and Bob.

To achieve the privacy through a Private-Key Encryption or a Symmetric-Key Encryption, Alice and Bob have to rely on a secret key. This secret key will enable the encryption scheme between Alice and Bob, encrypting a message (or a plaintext), into a ciphertext, and transmitting it to the other party. Then, the receiver decrypts the ciphertext back into a plaintext (the original message of the sender.)

The key idea of a Private-Key or Symmetric Encryption is that the plaintext is hidden as a ciphertext from any eavesdropper Eve [image source]

In the aforementioned scenario, Eve can closely monitor the communication channel between Alice and Bob, observing as many ciphertexts as she wants; yet no plaintext could be understood by Eve without the secret key, which are only accessible by Alice and Bob.

Let me now introduce mathematical notations for the Private-Key or the Symmetric-Key Encryption.

This type of encryption consists of 3 different functions (algorithms):

1. The key-generation algorithm Gen generates a key k accessible only by Alice and Bob.
2. The encryption algorithm Enc takes two inputs, a key k and a plaintext m. It outputs a ciphertext c = Enc(m,k)
3. The decryption algorithm Dec takes two inputs, a key k and a ciphertext c. It outputs a plaintext m* = Dec(c,k)

We say that the Symmetric-Key Encryption is correct when the original message m (an input to an encryption algorithm) and the plaintext m* (an output from a decryption algorithm) are the same, provided the same shared key k is used.

In mathematical terms, the correctness of the Symmetric-Key Encryption follows from the following composition of functions:

Enc(message m, key k) = ciphertext c,
Dec(ciphertext c, key k) = plaintext m,

which can be summarized as

Dec (Enc(m, k), k) = m.

Namely, the Symmetric-Key Encryption is correct because decryption is the inverse of encryption provided the identical key k is used.

Many ancient cryptographs were in fact the Symmetric-Key Encryption, with the most well-known form being a Caesar Cipher. Today, however, a Caesar Cipher is no longer adopted in a communication channel; the sequel to this article will explain why it is discarded. More generally, we will discuss the security of a (symmetric) encryption algorithm.

A Caesar Cipher here encrypts the message by shifting every English alphabets by 2 positions to the right, with the periodic boundary condition. Recovering the original message from the ciphertext simply involves shifting every English alphabets of the ciphertext by 2 positions to the left, with the periodic boundary condition [image source]

Rngcug uvca vwpgf hqtg ugewtgf gpetarvkqp uejgogu kp vjg ugswgn!
Please stay tuned for more secured encryption schemes in the sequel!