<style>
.red {
color: red;
font-weight: bold;
}

.blue {
color: blue;
font-weight: bold;
}
</style>

# Classical Encryption Techniques

## Basic Terminology for Classical Encryption
- **Plaintext (明文):** original message (unencrypted message)
- **Ciphertext (密文):** encrypted message
- **Encryption (加密):** convert from plaintext to ciphertext ($\equiv$ Enciphering)
- **Decryption (解密):** restore the plaintext from ciphertext ($\equiv$ Deciphering)
- **Key:** secret information (known only to sender/receiver)
- **Keyspace:** the range of possible values of Key
- **Cryptosystem ($\equiv$ Cipher):** cryptographic algorithm for encryption and decryption
- **Cryptography (密碼學):** practice and study of techniques for cryptosystems
- **Cryptanalysis (密碼分析):** practice and study of techniques for analyzing and/or breaking cryptosystems in order to understand the hidden aspects
- **Cryptology:** cryptography and cryptanalysis

## Symmetric Cipher Model

### Simplified Symmetric Cipher Model


- Requirements
- encryption/decryption algorithm, which is usually public, is strong.
- sender and receiver must have **obtained the secret key** in a **secure** fashion and must keep the secret key secure.

### Symmetric Cipher Model


An opponent, observing $Y$ but not having access to $K$ or $X$, may attempt to recover $X$ or $K$ or both. It is assumed that the opponent knows the encryption $(E)$ and decryption $(D)$ algorithms. If the opponent is interested in only this particular message, then the focus of the effort is to recover $X$ by generating a plaintext estimated $\hat X$. Often, however, the opponent is interested in being able to read future messages as well, in which case an attempt is made to recover $K$ by generating an estimate $\hat X$.

### Symmetric Cryptosystem

- Features
- easy to use
- usually **more efficient** than Asymmetric (Public-Key) Cryptosystems
- **secure management and distribution of key** are usually **not simple**
- Types
- <font class="blue">Stream Cipher</font>
- <font class="blue">Block Cipher</font>

### Stream Cipher

==<font class="red">（可能會考畫架構圖）</font>==


- 加解密皆為 ==<font class="red">XOR</font>== 運算
- Features
- **speedy**, lower hardware complexity, lower error propagation, typically vulnerable to **key reuse attacks** and **bit-flipping attacks**
- Some widely used stream ciphers
- A5
- RC4
- Salsa20
- ChaCha20

### Block Cipher


- Features
- typically **more secure, higher hardware complexity**, higher error propagation
- Some widely used block ciphers
- DES
- LUCIFER
- FEAL
- LOKI
- RC2
- SKIPJACK
- CAST
- IDEA
- BLOWFISH
- RC5
- RC6
- AES

### Brute-Force Attack

- Exhaustive Key Search
- Trying **possible keys** to crack the cipher.
- On average, **half** of all possible keys will be tried to achieve success.
(通常需要嘗試一半以上的可能性才會成功。)
- Assume either know or recognize plaintext (假設我們知道或有辦法識別明文)
- Key Size and Average Required Time

### Cryptanalytic Attack

- Goal
- Find the **secret key**
- Only recover the **plaintext** of some targeted ciphertext
(只恢復部分目標密文的明文)
- Types

### Unconditionly Secure（無條件安全）

An encryption scheme is unconditionally secure if the ciphertext generated by it does **not contain enough information** to determine **uniquely** the corresponding plaintext, no matter how much ciphertext is available. (i.e., **perfect cipher**)

即使收到無限的密文也沒有足夠的訊息能夠破解出明文。

### Computationally Secure（計算上安全）

- 大多數密碼系統只追求此項
- An encryption scheme is **computationally secure** if it meets
- the **cost** of breaking the cipher exceeds the value of the encrypted information;
（破解密文的成本遠大於明文本身的價值）
- the **time** required to break the cipher exceeds the useful lifetime of the information
（破解密文所需的時間遠多於明文的有效期間）

### Complexity of Breaking a Cryptosystem

- <font class="blue">Data Complexity</font>
- the amount of data needed as input to the attack
- <font class="blue">Processing Complexity</font>
- the time needed to perform the attack
- often called the **Work Factor**
- <font class="blue">Storage Requirements</font>
- the amount of memory/storage needed to do the attack

## Classical Encryption Techniques (經典的加密技術)

All are **Symmetric** Ciphers/Cryptosystems

- **Substitution** (代換)
- Monoalphabetic Substitution Cipher
- Multiple-Letter Encryption Cipher
- Polyalphabetic Substitution Cipher
- **Transposition** (Permutation) (排列)
- Transposition Cipher
- Product of Substitution and Transposition
- Product Cipher
- 執行多次 substitution 與 transposition

### Monoalphabetic Substitution Cipher（單一字母對應）

- Also called *Simple Substitution Cipher*
- **Caesar Cipher** (凱薩加密)
- Each letter in the plaintext is replaced by a letter some fixed number (**shift**) of positions down the alphabet.
- Primitive Caesar Cipher: shift = 3
- A ~ Z 分別代表 0 ~ 25（不分大小寫）
- 每個字母 +3，超過 25 就回到 0 (→ mod 26)
- General Caesar Cipher
- shift $\in [1, 25]$ (used as **key**)
- Brute-Force Cryptanalysis of General Caesar Cipher
- 若**已知密文使用 Caesar Cipher**，可直接嘗試所有的 25 種可能，找到可能的明文。
- **General Monoalphabetic Substitution Cipher**
- One Alphabet is used to substitute the Plaintext letters
- 每一字母對應到**任意符號或字母**（為方便使用較少使用符號對應）
- 若字母為**多對一會造成無法解密**
- 需要儲存密碼表或特定的公式
- Cryptanalysis of Monoalphabetic Substitution Ciphers
- 不需要嘗試 $26! \approx 4 \times 10^{26}$ 種 key
- 可以針對每種語言的特徵進行**頻率分析**，再與密文的頻率比較，提高猜中的機率。
- **Mary Queen of Scots’ Cipher** (1586)
- 用自創符號對應詞語，但還是不夠安全。

### Multiple-Letter Encryption Cipher (多字母加密)

- **Playfair Cipher**
- The best-known multiple-encryption cipher
- <font class="red">兩個兩個字母一起加密</font>
- Treat **digrams** in the plaintext as single units and translates these units into ciphertext digrams
- Playfair Key Matrix
- ==$5 \times 5$== matrix of letters based on a keyword
- fill in letters of keyword (**duplicates should be removed**)
- fill rest of matrix with other letters **in alphabetic order**
:::info
**Example**: keyword = "MONARCHY"


- **Encryption**
- if a pair is a repeated letter, insert a filler like 'X'
- ex. "BALLOON" $\rightarrow$ "BA L**X** LO ON"
- 若解密時 X 看起來位置不對，且前後的字母相同，可以推測此 X 是加密時插入的
- if both letters fall in the **same row**, replace each with letter to right (wrapping back to start from end)
- ex. "AR" $\rightarrow$ "RM"
- if both letters fall in the **same column**, replace each with the letter below it (again wrapping to top from bottom).
- ex. "MU" $\rightarrow$ "CM"
- **otherwise**, each letter is replaced by the one in its row in the column of the other letter of the pair.
- ex. "HS" $\rightarrow$ "BP"; "EA" $\rightarrow$ "IM" or "JM"
- **Decryption**
- 逆向反推即可
- "LJEMAKQD" $\rightarrow$ "SE CU RI TY"
:::
- Security of the Playfair Cipher
- Much improved over Monoalphabetic: $26 \times 26 = 676$ digrams $\Rightarrow$ 676 entry frequency table

### Polyalphabetic Substitution Cipher（多重字母對應）

- Make cryptanalysis harder with more alphabets to guess and **flatter Frequency Distribution**
- Two-Alphabetic Substitution Cipher
- 奇數與偶數位置的字母使用不同的 shift 公式
- **Vigenère Cipher**
- Effectively **multiple Caesar ciphers**
- Keyword: $k_1, k_2 ... k_d$
- d = # of alphabets
- *i*th letter specifies *i*th alphabet to use
- Key: $k_1, k_2 ... k_d\ \ k_1, k_2 ... k_d\ \ k_1, k_2 ... k_d ...$
:::info
**Example**:
Encrypt the plaintext "**we are discovered save yourself**" by using the Keyword =“**deceptive**”.

:::
- How to decrypt the ciphertext?
- 若知道 d 是多少，可以分組再進行頻率分析。例如若 d = 3，則將第 1, 4, 7, ... 個分為一組，2, 5, 8, ... 為一組。
- Cryptanalysis of Polyalphabetic Substitution Ciphers
- Determine the **Number of Alphabets**
- **Kasiski’s Method**
- The Distance between the repeated patterns must be a Multiple of the Number of Alphabets
- **Index of Coincidence**
- The index of coincidence is a measure of the variance between frequencies in a distribution.
- Break the ciphertext into pieces enciphered with the Same Alphabet.
- Solve each piece as a Monoalphabetic Substitution

### Autokey Cipher

- Ideally want a **key as long as the plaintext**
- Based on Vigenère Cipher
- Method
- keyword is prefixed to message as the initial block key
- knowing keyword can decrypt the first block of plaintext
- use the decrypted blocks in turn to decrypt the rest of plaintext
- Example: keyword = “deceptive”
- Security
- Autokey ciphers are **more secure** than polyalphabetic ciphers that use fixed keys.
- The weakness of Autokey ciphers is that the plaintext is part of the key, i.e., the key will likely contain **common words**.

## Transposition Cipher 排列

- Technique: Transposition (Permutation)
- the letters of the message are rearranged
- **Rail Fence Cipher**
- write down the plaintext as a sequence of diagonals and then read off as a sequence of rows
:::info
**Example:** A rail fence of depth 2

- Plaintext: "meet me after the toga party"
- Write diagonally
- 
- Ciphertext: "MEMATRHTGPRYETEFETEOAAT"
:::
- **Columnar Transposition Cipher**
:::info
:::
- **Keyed Columnar Transposition Cipher**
:::info
:::

### Vernam Cipher

- A **Stream Cipher** in which the plaintext is combined with a **random or pseudorandom keystream** of the **same length** to generate the ciphertext using the <font class="red">XOR</font> function
- Example:
- Plantext (binary): 11010110 01010101
- Key (binary): 01101110 10001011
- Alternative form of Vernam Cipher **based on Vigenère Cipher**.
- Example
- Weakness: Vernam Cipher was vulnerable because the **key** tape was a loop, which was **reused** whenever the loop made a full cycle.

### One-Time Pad

- Features
- Any encryption scheme that uses a key of the same length as the plaintext and ensures that the key is truly random, never reused, and kept secret.
- Example: The improvement of the Vernam Cipher, proposed by Mauborgne, satisfying:
- key must be at least **as long as the plaintext**
- key must be **truly random**
- key must **never be reused**
- key must be **kept secret**
- A Perfect Cipher
- Unbreakable

<!-- TODO -->
- Drawbacks of One-Time Pad
- **Generation** of **large quantities of random keys** is challenging
- Any heavily used system might require millions of random key bits.
- True random number generators exist, but are typically slower and more specialized.
- **Secure distribution and protection** of large quantities of random keys is challenging
- For every message to be sent, a key of equal length is needed by both sender and receiver.
- It is crucial to handle keys with care to ensure their continued secrecy and proper disposal, **preventing any possibility of reuse**.
- 用途非常有限

### Rotor Machine

- A famous application of the principle of multiple stages of encryption
- implements a complex & varying substitution cipher
- uses a series of cylinders, each giving one substitution, which rotated and changed after each letter was encrypted
- Example: 3 cylinders have $26^3 = 17576$ alphabets

### Steganography

The science of **hiding a secret message** in a **cover medium** insuch a way that no one, apart from the sender and intendedrecipient, detects or suspects the existence of this message.

- Common Types of Digital Steganography
- Text Steganography
- Image Steganography
- Audio Steganography
- Network Steganography
- 藏在封包的無用 header
- Image Steganography with LSB Substitution
- LSB (Least Significant Bit) Substitution is one of the most used techniques to hide a secret message in an image.
- 24-bit RGB images are images in which each **pixel** is represented by **three set of 8 bits (= 1 byte)** (i.e., **24 bits total**) specifying the intensities of Red, Green, and Blue that form the color for the pixel.
- Drawbacks of Steganography
- **high overhead** to hide relatively few information bits
- Once the system is **discovered**, it becomes virtually **worthless**.
- Steganography can be combined with cryptography to add an additional layer of security when communicating sensitive data