---
# System prepended metadata

title: 'Ch03: Classical Encryption Techniques'
tags: [密碼學]

---

<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

![](https://hackmd.io/_uploads/S1WdtTNba.png =800x)

- 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

![](https://hackmd.io/_uploads/r1xTtaN-a.png =800x)

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>==

![](https://hackmd.io/_uploads/rJsUq6Eba.png)

- 加解密皆為 ==<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

![](https://hackmd.io/_uploads/ry86qpVZp.png)

- 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  
  ![](https://hackmd.io/_uploads/ByO1npVbT.png =800x)

### Cryptanalytic Attack

- Goal
  - Find the **secret key**
  - Only recover the **plaintext** of some targeted ciphertext 
    (只恢復部分目標密文的明文)
- Types
  ![](https://hackmd.io/_uploads/S1oohpE-6.png)

### 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
  - 可以針對每種語言的特徵進行**頻率分析**，再與密文的頻率比較，提高猜中的機率。
    ![](https://hackmd.io/_uploads/r1VmvCE-T.png)
- **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"

  ![](https://hackmd.io/_uploads/ry3ICRN-6.png =300x)

  - **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**”.

  ![](https://hackmd.io/_uploads/r14vGkBZT.png) 
  :::
  - 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”
  ![image.png](https://hackmd.io/_uploads/B1pdnzUma.png)
- 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
    - ![](https://hackmd.io/_uploads/HyKqLJSZ6.png =300x)
  - Ciphertext: "MEMATRHTGPRYETEFETEOAAT"
:::
- **Columnar Transposition Cipher**
:::info
![](https://hackmd.io/_uploads/HJF1PyB-T.png =600x)
:::
- **Keyed Columnar Transposition Cipher**
:::info
![](https://hackmd.io/_uploads/H1WrwJSZ6.png =600x)
:::

### 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
  ![image.png](https://hackmd.io/_uploads/S1tnQbUmT.png)
- Example:
  - Plantext (binary): 11010110 01010101
  - Key (binary): 01101110 10001011
  ![image.png](https://hackmd.io/_uploads/BJPiUX87T.png)
- Alternative form of Vernam Cipher **based on Vigenère Cipher**.
  - Example  
    ![image.png](https://hackmd.io/_uploads/B1eudQIm6.png)
  - 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

  ![](https://hackmd.io/_uploads/S11VKyS-T.png =600x)
<!-- 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
  ![](https://hackmd.io/_uploads/Bk8QsyHW6.png)

### 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
