1. Definition of Cryptography
Before the late 20th century, cryptography was more of an art, primarily used for secret communication. At that time, there were no theories to rely on, nor any effective definitions to construct a good cipher. It wasn’t until the 1980s that the emergence of modern cryptography transformed the study of cryptography into a scientific and mathematical discipline.
Applicable Subjects:
Classical Cryptography: Military organizations and governments.
Modern Cryptography: Everywhere.
Definition of Cryptography:
The Concise Oxford Dictionary: The art of encoding or decoding ciphers. (Not sufficiently accurate)
Current Cryptography: The study of mathematical techniques for protecting digital information, systems, and distributed computing from adversarial attacks.
The evolution can be represented as follows:
2. Brief Overview of Symmetric Encryption
Classical cryptography focuses on the design and use of ciphers, allowing two parties to send messages without being seen by a third-party eavesdropper. The so-called “cipher” mentioned above refers to the “encryption scheme” we will discuss later. The security of all classical cryptography relies on a secret – the key – which is generated and exchanged in advance by the communicating parties, making it inaccessible to eavesdroppers. This method is known as private-key encryption.
In cryptography, we categorize encryption schemes into private-key (symmetric) encryption and public-key (asymmetric) encryption.
In private-key encryption, when two parties want to communicate secretly, they exchange a key beforehand. One party can use this key to encrypt a message, also known as plaintext, and then send it to the other party. Thus, one party sends a ciphertext to the other. The receiver uses the key to decrypt this ciphertext, obtaining the original message. The keys used here are the same and are utilized for the conversion between plaintext and ciphertext. This is why it is referred to as symmetric encryption. However, asymmetric encryption is the opposite, using different keys for encryption and decryption.
3. Encryption Syntax
Formally, a private-key encryption scheme consists of a message space M and three algorithms (Gen, Enc, and Dec).
Gen: Key generation algorithm
Enc: Encryption algorithm
Dec: Decryption algorithm
The functional descriptions of these three algorithms are as follows:
1. Gen is a probabilistic algorithm that outputs a key k based on some distribution.
2. Enc takes a key k and a plaintext message m as input and outputs a ciphertext c, i.e., Enck(m) represents the encryption of plaintext message m using key k.
3. Dec takes a key k and a ciphertext c as input and outputs a plaintext message m. That is, Deck(c) represents the decryption of ciphertext message c using key k.
All keys k generated by Gen form a key space, denoted as K. The ciphertexts generated by Dec form a plaintext space, denoted as C.
An encryption scheme must satisfy the following deterministic requirement: for every key k output by Gen and every plaintext message m ∈ M, Deck(Enck(m)) = m
The symmetric encryption process: Run Gen to generate key k. When one party wants to send plaintext message m to the other party,
they compute c := Enck(m),
and then send the ciphertext c over the public channel to the other party.
Upon receiving the ciphertext c,
the receiver computes m := Deck(c) to obtain the original message.
” := ” denotes a deterministic equation, assuming that Enc here is deterministic, while Enc is a probabilistic algorithm.
4. Kerckhoffs’ Principle
“The encryption scheme does not need to be kept secret; it can be easily acquired by the enemy.”
This means that even if an eavesdropper knows all the details of the encryption scheme, as long as the attacker does not know the key k being used, the encryption scheme should remain secure. Therefore, Kerckhoffs’ principle requires that security relies solely on the secrecy of the key k.
Reasons:
1. Keeping a key k secret is easier than keeping a relatively complex encryption scheme secret, especially when the encryption scheme is widely used.
2. If the secret information shared by honest parties is leaked, changing the key is much easier than changing the encryption scheme. Moreover, generating a new random key is relatively simple, while designing a new encryption scheme is a massive undertaking.
3. Encouraging public scrutiny of the scheme before its widespread deployment to check for potential weaknesses is a significant benefit. Furthermore, standardizing encryption schemes ensures compatibility between different users, and the public will use robust encryption schemes that have undergone public review. This is more convincing.
Therefore, widely and publicly disseminating all the details of the encryption scheme is beneficial.
5. Classical Encryption Schemes
The encryption schemes introduced below have all been broken and are insecure, but their ideas are worth learning.
1. Caesar Cipher
The Caesar cipher is one of the oldest encryption schemes, which encrypts by shifting the letters in the alphabet three positions to the right. That is, a becomes D, b becomes E, and so on. When it reaches the end of the alphabet, it wraps around to the beginning. This scheme has no key, and the encryption method is fixed. Therefore, anyone can easily break the ciphertext by learning the encryption method of the Caesar cipher. Its variant, ROT-13, is still used in various online forums. From this, we can see that they provide no cryptographic security; they merely make the message difficult to understand unless the reader consciously decides to decrypt it.
2. Shift Cipher
The shift cipher can be viewed as a key variant of the Caesar cipher. In the shift cipher, the key k is a number between 0 and 25. In the Caesar cipher, letters are shifted three positions, while in the shift cipher, letters are shifted k positions. Its algorithm can be summarized as follows: the plaintext space M consists of strings of English letters of any length, excluding punctuation, spaces, and numbers, with case insensitivity. Gen outputs a uniformly distributed key k ∈ { 0 , . . . , 25 }, and the algorithm Enc takes a key k and a plaintext as input, then shifts each letter of the plaintext forward by k positions; the algorithm Dec takes a key k and a ciphertext as input, then shifts each letter of the ciphertext backward by k positions.
Cracking the ciphertext without knowing the key k is also relatively easy. Since there are only 26 possible keys, the attacker only needs to try these possible keys to decrypt the ciphertext, resulting in 26 possible candidate plaintexts, with the correct plaintext being among these 26. Moreover, if the ciphertext is “long enough”, the correct plaintext is likely the only “meaningful” candidate plaintext among the list. (This is often true)
This attempt to try every possible key is known as brute-force attack or exhaustive search attack. Therefore, if an encryption scheme is to ensure security, it must not be easily susceptible to such attacks. This observation is referred to as the sufficient key space principle: any secure encryption scheme must have a sufficiently large key space to resist exhaustive search attacks. To prevent such attacks, the key space must be very large, for example, at least 280, and in many cases even larger.
The sufficient key space principle provides a necessary condition for the security of an encryption scheme, but it is not a sufficient condition.
3. Single-letter Substitution Cipher
In the “shift cipher”, the mapping from plaintext to ciphertext is a fixed shift determined by the key, while in the single-letter substitution cipher, the mapping is arbitrary, constrained only by a one-to-one relationship. The key space contains all bijections or permutations of the alphabet. As shown in the figure:
The figure shows that a maps to X, and so on.
From the name of this encryption scheme, we can understand that the key defines the (fixed) substitution of individual characters in the plaintext. Assuming the 26-letter alphabet is used, the size of the key space can be calculated as: 26! = 26·25·24···2·1, approximately 288, making brute-force attacks infeasible.
The single-letter substitution cipher can be attacked using the statistical properties of the English language. Since the mapping of each letter is fixed, if it is known that e maps to D, then all other e’s map to D. The probability distribution of the English letters is shown in the figure:
4. Vigenère Cipher
The statistical attacks used to break the “single-letter substitution cipher” are ineffective against the “multi-letter substitution cipher” because its key defines the mapping applied to blocks of plaintext characters. The multi-letter substitution cipher “smooths” the frequency distribution of characters in the ciphertext, making it more difficult to perform statistical analysis. The Vigenère cipher is a type of multi-letter substitution cipher that can be viewed as applying different instances of the shift cipher to different parts of the plaintext. As shown in the figure, its key is a string. Encryption is accomplished by shifting each plaintext character by the number indicated by the next character in the key, wrapping around the key as needed.
6. Principles of Modern Cryptography
· Principle 1: Formal Definition: Clarifying what “security” really means
· Principle 2: Precise Assumptions: It has been shown that most cryptographic proofs rely on currently unproven assumptions about the algorithmic difficulty of certain mathematical problems.
· Principle 3: Security Proof: Any such assumption must be explicitly and precisely stated.
A secure encryption scheme should guarantee that regardless of what information the attacker possesses, the ciphertext should not leak additional information about the underlying plaintext.
Threat Models (in increasing order of strength):
1. Ciphertext-only attack: The adversary only observes one ciphertext (or multiple ciphertexts) and attempts to determine information about the underlying plaintext (or multiple plaintexts).
2. Known-plaintext attack: Here, the adversary can learn one or more plaintext/ciphertext pairs generated using a certain key. The adversary’s goal is to infer information about other ciphertexts generated with the same key.
3. Chosen-plaintext attack: In this attack, the adversary can obtain plaintext/ciphertext pairs as described above for their chosen plaintext.
4. Chosen-ciphertext attack: The attacker can additionally obtain the decryption (some information) of their chosen ciphertext, for example, whether decrypting some ciphertext chosen by the attacker produces a valid message. Similarly, the adversary’s goal is to learn information about other ciphertexts generated with the same key (which the adversary cannot directly obtain their decryption).
Source: Business Encryption Expert
