---
# System prepended metadata

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

---

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

## Cryptanalytic Attacks (types of attack)

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


![image](https://hackmd.io/_uploads/SJNKpsu-1x.png)


## 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屬性之間的關係**

![image (2)](https://hackmd.io/_uploads/BJOJPjO-kl.png)

## Three steps to propose a cryptographic solution

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

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

# CH2

## One-time pad

- 這個系統是unbreakable！
- K 必須是真正隨機的，並且可供雙方使用
- 重複使用one-time pad是致命的
![image](https://hackmd.io/_uploads/r1wQdiu-Je.png)
### 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

![image (1)](https://hackmd.io/_uploads/BJgEdidZkx.png)

![image (2)](https://hackmd.io/_uploads/HJoEdsdWkl.png)

## 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)
    
    ![image](https://hackmd.io/_uploads/SkZVcjd-yx.png)
    

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

![image (7)](https://hackmd.io/_uploads/Bke55o_-yx.png)

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

![image (8)](https://hackmd.io/_uploads/HyEM2suW1l.png)

## Feistel cipher: Encryption and decryption

- Encryption

![image (9)](https://hackmd.io/_uploads/Sk3f2sO-Je.png)

- Decryption

![image (10)](https://hackmd.io/_uploads/BJVm2j_WJe.png)

## 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 → 易受中間人攻擊

![image (13)](https://hackmd.io/_uploads/r1iN3iub1l.png)

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

![image (14)](https://hackmd.io/_uploads/r1zr3sOZyx.png)

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

![image (15)](https://hackmd.io/_uploads/Bkcr3sOZJe.png)

![image (16)](https://hackmd.io/_uploads/B1lU2odbJx.png)

![image (17)](https://hackmd.io/_uploads/BkU8nj_b1g.png)

- 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

![image (18)](https://hackmd.io/_uploads/H1GD3juW1g.png)


![image (19)](https://hackmd.io/_uploads/H1nv2odZye.png)

### 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
    
    ![image (20)](https://hackmd.io/_uploads/ry4u3j_Wkg.png)
    

### Mix Columns

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

![image (21)](https://hackmd.io/_uploads/Hyodhs_b1g.png)


![image (22)](https://hackmd.io/_uploads/HymF2jubyl.png)


![image (23)](https://hackmd.io/_uploads/rJuK2ouW1x.png)

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

![image (24)](https://hackmd.io/_uploads/SJgqnou-ke.png)

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

![image (26)](https://hackmd.io/_uploads/HyljhsO-ye.png)
### CBC Mode

- CBC = Cipher Block Chaining
- Ciphertext依賴於所有以前的plaintext blocks
- Encryption
    - $𝑐_1 = 𝑒_𝑘(𝑚_1⊕IV)$. IV is the shared initial vector
    - $𝑐_𝑖 = 𝑒_𝑘(𝑚_𝑖 ⊕ 𝑐_{𝑖−1})$.
    
    ![image (27)](https://hackmd.io/_uploads/ryqo3i_b1g.png)

    
- Decryption
    - $𝑚_1 = 𝑑_𝑘(𝑐_1)⊕IV$.
    - $𝑚_𝑖 = 𝑑_𝑘(𝑐_𝑖)⊕𝑐_{𝑖−1}$.
        
        ![image (28)](https://hackmd.io/_uploads/rJf2nsuWkg.png)
        
- 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

![image (29)](https://hackmd.io/_uploads/rkAnhjObJe.png)

### CFB Mode

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

![image (30)](https://hackmd.io/_uploads/ByIanj_Wke.png)

- 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

![image (31)](https://hackmd.io/_uploads/BkR03oubkg.png)
![image (32)](https://hackmd.io/_uploads/H171podbke.png)
![image](https://hackmd.io/_uploads/ry3k6jd-1l.png)