---
title: 密碼學導論筆記 期中考複習筆記
tags: 密碼學導論,筆記,大學檔案,期中考,重點筆記
---
[TOC]
# CH1

## Cryptanalytic Attacks (types of attack)



## What does it mean to be secure?

### Unconditionally secure

- 無論對手有多少時間，如果沒有密鑰，他或她都不可能解密密文
- ex: one-time pad

### Computationally secure

- **在沒有密鑰的情況下解碼訊息在計算上是「不可行的」**
- 破解密碼的成本超過了加密訊息的價值
- 破解密碼所需的時間超過了資訊的使用壽命
- 沒有演算法可以在多項式時間解碼該訊息。

## One-way hash functions

### Birthday paradox(attack)

1. 根據已知的明文，產生雜湊值
2. 將明文P依照雜湊值的長度，區分為若干個區塊$（P_1, P_2, …, P_n）$
3. 攻擊者製造另一個偽造文Q，也依照 64 個位元的雜湊值長度，區分為若干個區塊$（Q_1, Q_2, …, Q_n）$。
4. 將明文與偽造明文的相對區塊，送給雜湊函數計算，尋找Collision的地方
5. 找出相同的雜湊值之後，將此偽造明文和原先的電子簽章傳送給接收端

### Preimage, second preimage, collision resistance

- Preimage Resistant(one-way property)
- 給一個$𝑧$，無法找到$𝑥$符合$ℎ𝑎𝑠ℎ(𝑥) = 𝑧$
- 簡單來說，ℎ𝑎𝑠ℎ是 one-way 的，給 output 無法反推 input
- Collision Resistant (strong collision resistance)
- 很難找到一組$x_1$,$x_2$，使得$H(x_1) = H(x_2)$
- Second Preimage Resistant (weak collision resistance)
- 給定一個值$x$，我們很難找到一個相異的$x'$，使得$H(x) = H(x')$
- **Hash Function屬性之間的關係**


## Three steps to propose a cryptographic solution

提出密碼解決方案的三個步驟

1. 指定威脅模型
2. 提出方法來做防護
3. 證明/分析結構是安全的
- 顯示攻破威脅下的建設模型將解決潛在的難題

# CH2

## One-time pad

- 這個系統是unbreakable！
- K 必須是真正隨機的，並且可供雙方使用
- 重複使用one-time pad是致命的
### Encrypt/decrypt

- Encrypt： $C=P ⊕ K$
- Decrypt：$P=C ⊕ K$

### 3 conditions for the perfect secrecy

1. 存在製作大量隨機的key
2. sender和receiver產生的key要一樣長
3. 只能用一次

## Model of a Symmetric encryption



## Shift cipher and substitution cipher

### What are shift/substitution cipher

- Shift Cipher：英文字母位移一些bits
- Substitution Cipher：英文字母直接替換

### How to break them?

- Shift Cipher：透過比較字母出現頻率，即可知道猜測位移了多少個字元
- Substitution Cipher：一開始可以計算字母頻率，先猜測到部分字母，接著用常用的單字，將其他替換字元找出來

# CH3.

## Euclidean algorithm vs. Extended Euclidean algorithm

### Euclidean algorithm

- 輾轉相除法
- 尋找最大公因數
- given a and b with a ≥ b
- gcd(a, b) = gcd(b, a mod b)
- Recursion: until gcd(b, 0) = b

### Extended Euclidean Algorithm

- gcd(a,b)=1 ⇒ ax ≡ 1 mod b，尋找x(modular inverse)
- function extended_gcd(a, b)
- s := 0; old_s := 1
- t := 1; old_t := 0
- r := b; old_r := a
- while r ≠ 0
- quotient := old_r div r
- (old_r, r) := (r, old_r - quotient * r)
- (old_s, s) := (s, old_s - quotient * s)
- (old_t, t) := (t, old_t - quotient * t)
- output "greatest common divisor:", old_r
- output "Bézout coefficients:", (old_s, old_t)


## Definition/properties

### Group/abelian group

- 集合 G和二元運算子。具有以下條件，稱為Group (群)
1. 封閉性：$∀a,b ∊ G, ∋ a。 b ∊ G$
2. 結合律：$∀ a,b,c ∊ G, ∋ a。(b。c) = (a。b)。c$
3. 單位元素：$∃ I ∊ G, ∋ ∀a ∊ G, a。I = I。a = a$
4. 反元素：$∀ a ∊ G, ∃! b ∊ G, ∋ a。b = b。a = I$
- 若為Abelian or Commutative Group(交換群)，則多一個條件
1. 交換律：$∀a,b ∊ G, ∋ a。b = b。a$
- 若group (G, *) 有 multiplicative(乘法性) ⇒ $𝑓 = 𝑔 ∗ ℎ, 𝑓 ∗ 𝑓 ∗ 𝑓 ∗ 𝑓 ∗ 𝑓 = f^5$
- 若group (G, +) 有 additive(加法性) ⇒ $𝑓 = 𝑔 + ℎ, 𝑓 + 𝑓 + 𝑓 + 𝑓 + 𝑓 = 5𝑓$

### Ring

- 集合R和二元運算子(+,*)具有以下條件，稱為Ring
1. 封閉性：$∀a,b ∊ R, ∋ a + b ∊ R , a * b ∊ R$
2. 結合律：$∀ a, b, c ∊ R, ∋ a+(b+c) = (a+b)+c, a*(b*c) = (a*b)*c$
3. 單位元素：$∃ I ∊ R, ∋ ∀a ∊ R, a+I = I+a = a, I*x = x$
4. 反元素：$∀ a ∊ R, ∃! b ∊ R, ∋ a+b = b+a = I$
5. 交換律：$∀a,b ∊ R, ∋ a+b = b+a$
6. 分配律：$∀ a, b, c ∊ R, ∋ (a+b)*c = a*c+b*c$
- 若ring滿足以下條件則稱為commutative ring
1. 交換律：$∀a,b ∊ R, ∋ a*b = b*a$
- (F,+,*) 是 field ⇒ (F,+,*) 是 ring

### Field

- (F,+,×) 為交換環
- 除了0以外的元素均存在乘法反元素

### Galois field (Finite field)

- Order是有限的Field
- The finite field of order $𝑝^𝑛$ is generally written GF($𝑝^𝑛$)

### Compare


## The Euler Phi Function

- ϕ is called Euler phi function
- ϕ(𝑛): 小於等於*n*的正整數中與*n*互質的數的數目
- 若p是質數，則ϕ (p)=p-1
- 如果gcd(m,n)=1，則ϕ(m*n) = ϕ(n) * ϕ(m)
- 如果p和q為n的質因數，則 ϕ (𝑛) = 𝑝𝑞(1 − $\frac{1}{p}$)(1 - $\frac{1}{q}$) = (𝑝 − 1)(𝑞 − 1)
- 根據歐拉定理
- a$^{ϕ(n)}$ = 1(mod n) a ∊ $\mathrm{Z}_{n}^{*}$
- a$^{(p-1)(q-1)}$ = 1(mod pq) a ∊ $\mathrm{Z}_{pq}^{*}$ and n = 𝑝𝑞
- 這在 RSA 中很重要

### Properties of generator

- 如果a是Z $^{*}$的generator，則Z $^{*}$ = {𝑎 $^{i}$ mod n | 1 ≤ 𝑖 ≤ ϕ (n)}
- $\mathrm{Z}_{n}^{*}$有generator **⇔** n=2, 4, 𝑝 $^{k}$or 2𝑝 $^{k}$，p為奇數
- $\mathrm{Z}_{n}^{*}$有cyclic ⇒ $\mathrm{Z}_{n}^{*}$有 ϕ(ϕ(n))個 generators
- ex: ϕ(19)=18，$\mathrm{Z}_{19}^{*}$ 有 ϕ( ϕ(19))= ϕ(18) = 6 generators

## Fermat’s little

- 若p為質數且gcd(a, p)=1 then 𝑎$^{𝑝−1}$ ≡ 1 (mod p)

# CH5.

## Types of Symmetric Ciphers

### Block cipher vs. Stream cipher

- Stream Ciphers: 一次對明文一位/位元組進行加密
- Block Ciphers：一次 64/128 位進行加密

## Synchronous stream cipher and self-synchronous stream cipher

- Synchronous or additive stream ciphers：金鑰流獨立於明文字串，僅取決於金鑰
- Self-synchronizing stream ciphers：金鑰流是金鑰和密文的函數

## Type of block cipher

### Feistel cipher vs. S/P network

- Feistel cipher: 輸入分為兩半，右半部分變成左半部分，左半部分與右半部分和密鑰的功能進行XOR
- Substitution-Permutation network: input divided in blocks which are encrypted with substitution cipher, blocks are mixed using permutation and roundkey is XOR-ed


## Feistel cipher: Encryption and decryption

- Encryption


- Decryption


## Enhancing DES: Double DES, Triple DES

### Double DES

- $C = 𝐸_{𝐾2}[𝐸_{𝐾1}[P]]$
- $P = 𝐷_{𝐾1}[𝐷_{𝐾2}[C]]$
- Only slightly increase the security…
- K1 = K2 → 工作量增加一倍
- K1 ≠ K2 → 易受中間人攻擊


### Triple DES

- $C = 𝐸_{𝐾3}[𝐸_{𝐾2}[𝐸_{𝐾1}[P]]]$
- $P = 𝐷_{𝐾1}[𝐷_{𝐾2}[𝐷_{𝐾3}[C]]]$
- Only slightly increase the security…
- If K1=K2 (=K3), → DES
- If K1=K3, only 2 keys are used


## Round function in AES

- Block cipher: 128-bit blocks, 128/192/256-bit keys
- 1回合做4件事
- Byte substitution (1 S-box used on every byte)
- Shift rows (permute bytes between groups/columns)
- Mix columns (subs using matrix multiply of groups)
- Add round key (XOR state with key material)




- AES Data Structures
- Galois Fields in Rijdael
- Uses $GF(2^8)$ over bytes.

### Byte Substitution

- State matrix is transformed byte by byte
- Each byte of state is replaced by byte in row (left 4-bits) & column(right 4-bits)
- S-box is constructed using a defined transformation of the values in $GF(2^8)$
- 抵禦所有known attacks



### Shift Rows

- 行在不同的偏移量上移動（取決於塊長度）
- Purpose: diffusion over the columns.
- circular byte shift in each
- 1st row is unchanged
- 2nd row does 1 byte circular shift to left
- 3rd row does 2 byte circular shift to left
- 4th row does 3 byte circular shift to left


### Mix Columns

- column上位元組是線性組合
- row上具有良好的擴散性能
- 每個位元組都替換為一個值，該值取決於列中的所有 4 個bytes




- 假設(變數名稱 = 16進位的值)
- a = 2b, b = d4, c = de, d = ad


### Add Round Key

- XOR state with 128-bits of the round key
- Again processed by column
- 解密的 Inverse 是相同的，因為 XOR 是自己Inverse，只是具有正確的 round key

## Block cipher modes (ECB, CBC, OFB, CFB, CTR)

### ECB Mode

- ECB = Electronic Code Book
- 這些操作模式此後已在國際上標準化，並且可以與任何分組密碼一起使用。
- The last block is padded if necessary.
- $𝑐_𝑖 = 𝑒_𝑘(𝑚_𝑖)$
- Blocks are independent.
- Error propagation: expansion within one block.

### CBC Mode

- CBC = Cipher Block Chaining
- Ciphertext依賴於所有以前的plaintext blocks
- Encryption
- $𝑐_1 = 𝑒_𝑘(𝑚_1⊕IV)$. IV is the shared initial vector
- $𝑐_𝑖 = 𝑒_𝑘(𝑚_𝑖 ⊕ 𝑐_{𝑖−1})$.


- Decryption
- $𝑚_1 = 𝑑_𝑘(𝑐_1)⊕IV$.
- $𝑚_𝑖 = 𝑑_𝑘(𝑐_𝑖)⊕𝑐_{𝑖−1}$.


- ECB and CBC - Padding
- plaintext不夠時，需要補足
- 方法
- 全部填0(問題：無法分辨是Plantext還是Padding)
- 填1個1，其他全部填0
- 最後填plaintext的長度，其他中間填0

### OFB Mode

- OFB = Output FeedBack
- This mode enables a block cipher to be used as a stream cipher → The block cipher creates the keystream.
- Block length of block cipher is 𝑛.
- One can choose to use keystream blocks of j ≤ 𝑛 bits only.
- Divide plaintext into a series of 𝑗-bit blocks $𝑚_1,...,m_t$.
- Encryption: $𝑐_𝑖 = 𝑚_𝑖 ⊕ 𝑒_𝑖$, where 𝑒𝑖 selection of 𝑗 bits of ‘ciphertext’ generated by block cipher, starting with IV in shift register.
- 是Synchronous stream cipher
- No linking between subsequent blocks.
- 需要不同的IV;否則不安全。
- No error propagation: errors are only copied


### CFB Mode

- CFB = Cipher FeedBack
- 是Self-synchronizing stream cipher
- Ciphertext依賴於所有以前的plaintext blocks
- Only uses encryption (no decryption algorithm necessary)
- 發送方和接收方之間不同步
- 如果已正確接收 n 位，則進行同步。


- OFB and CFB
- In OFB Mode the keystream is generated by
- Encrypting the IV.
- Encrypting the output from this encryption.
- In CFB Mode the keystream is generated by
- Encrypting the IV.
- Encrypting n bits of ciphertext.

### CTR Mode

- CTR = Counter mode
- Similar to OFB but encrypts counter value rather than any feedback value
- 可以進行parallel encryptions
- Random access to encrypted data blocks
- Provable security
- 每個plaintext block必須有不同的key和counter value
- $𝐶_𝑖 = 𝑃_𝑖 ⊕ 𝑂_𝑖$
- $𝑂_𝑖= 𝐷𝐸𝑆_{𝐾1} (𝐶𝑜𝑢𝑛𝑡𝑒𝑟 + 𝑖 − 1)$

### Compare

- Require randomly access to encrypted data blocks: ECB and CTR
- Precomputation: OFB and CTR
- Result in self-synchronizing cipher(s): CBC and CFB
- Not propagate errors: ECB, OFB, and CTR