owned this note
owned this note
Published
Linked with GitHub
Cryptography
===
## Classical Cryptography
Introduction to some simple cryptosystems
----
### Definition
A cryptosystem is a five-tuple ***(P,C,K,E,D)*** satisfies.
- **P** is a finite set of possible ***plaintexts***
- **C** is a finite set of possible ***ciphertexts***
- **K** is a finite set of possible ***keys***
- For each $k\in K$, there is an encryption rule $e_k\in E$ and a corresponding decryption rule $d_k\in D$
- $e_k:P \rightarrow C$
- $d_k:C \rightarrow P$
- $d_k(e_k(x))=x$ for every plaintext $x\in P$
----
### 1. Shift Cipher
- $P=C=K=\mathbb Z_{26}$
- $K,x,y\in\mathbb Z_{26}$
- $e_k(x)=(x+K)\ mod\ 26$
- $d_k(y)=(y-K)\ mod\ 26$
其實就是把字母往右或左移 K 個字母
----
### 2. Substitution Cipher
- $P=C=\mathbb Z_{26}$
- $K$ : all possible permutations of the 26 symbols
- For each $\pi\in K$
- $e_\pi(x)=\pi (x)$
- $d_\pi(y)=\pi^{-1}(y)$
where $\pi^{-1}$ is the inverse permutation to $\pi$
先定義各個字母的轉換規則 $\pi$,而 $\pi^{-1}$ 就是解碼的 function
----
### 3. Affine Cipher
- $P=C=\mathbb Z_{26}$
- $K\ =\ \{(a,b)\in\mathbb Z_{26}\times\mathbb Z_{26}:gcd(a,26)=1\}$
- For $k=(a,b)\in K;\ x,y\in\mathbb Z_{26}$
- $e_k(x)=(ax+b)\ mod\ 26$
- $d_k(y)=a^{-1}(y-b)\ mod\ 26$
我們可以用輾轉相除法找到 a 的 inverse,詳情請看 [Congruence](https://hackmd.io/AwDgnATGDGAmEFoCGYQHYEBYCMYBsCARgKx6YJ4CmSxSwAzHhIQGaZA=?view#If-gcdx-y--1-then-axby--1-for-some-ab-inmathbb-Z)
----
### 4. Vigen$\grave e$re Cipher
- m : a positive integer
- $P=C=K=(\mathbb Z_{26})^m$
- For a key K=(k~1~, k~2~, ..., k~m~)
- $e_k(x_1,x_2,...,x_m)=(x_1+k_1,x_2+k_2,...,x_m+k_m)$
- $d_k(y_1,y_2,...,y_m)=(y_1-k_1,y_2-k_2,...,y_m-k_m$)
跟 shift chiper 很像,只是他是每個字母都有自己的 K,而 shift chiper 是每個字母的 K 都一樣
----
### 5. Hill Chipher
- m $\geq$ 2 is an integer
- $P=C=(\mathbb Z_{26})^m$
- $K=\{m\times m \ invertible\ matrices\ over\ \mathbb Z_{26} \}$
- For a key $K$
- $e_k(x)=xK$
- $d_k(y)=yK^{-1}$
簡而言之,乘上一個矩陣 K 加密,然後乘上反矩陣 K^-1^ 解密
----
### 6. Permutation Cipher
- m is a positive integer
- $P=C=(\mathbb Z_{26})^m$
- $K$ consist of all permutations of {1,...,m}
- For a key(a permutation) $\pi$
- $e_\pi(x_1,...,x_m)=(x_{\pi(1)},...,x_{\pi(m)})$
- $d_\pi(y_1,...,y_m)=(y_{\pi^{-1}(1)},...,y_{\pi^{-1}(m)})$
把 plaintext 排列組合成 chipertext
---
## DES
The Data Encryption Standard
----
### Overview
- Block cipher
- Symmetric-key algorightm
- Special type of iterated cipher called a ***Feistel cipher***
----
### Feistel cipher
- Each state u~i~ is divided into two halves of equal length, say L~i~ and R~i~
``` graphviz
digraph u {
u [shape=box]
L [shape=box]
R [shape=box]
u -> L
u -> R
}
```
- For each round, we use a ***Round function g :*** $g(L^{i-1},R^{i-1},K^i)\ =\ (L^i,R^i)$
$$L^i\ =\ R^{i-1}$$$$R^i\ =\ L^{i-1}\ \oplus \ f(R^{i-1},K^i)$$
- DES 去掉 IP 和 IP^-1^ 就是一個 Feistel cipher 的結構
![](https://i.imgur.com/NaXiRhQ.png)
----
### Description
加密:
1. IP 把順序打亂
2. 16 個 Round 加密
3. IP^-1^ 把順序轉回來
解密:
- 跟加密的步驟一樣
- 差異在 Key 使用的順序,解密是從 K~16~ 用到 K~1~
----
### IP and IP^-1^
- IP : Initial permutation
$$IP(x)=L^0R^0$$
- IP^-1^ : Inverse permutation
$$y=IP^{-1}(R^{16}L^{16})$$Note L^16^ and R^16^ are swapped before IP^-1^ is applied
- Each L^i^ and R^i^ is 32 bits in length
- IP 和 IP^-1^ 都是固定的,都燒在網卡上
- 詳見 [value of IP and IP^-1^](https://en.wikipedia.org/wiki/DES_supplementary_material#Initial_permutation_(IP))
----
### Round
- 做的事跟在 Feistel cipher 裡的一個 Round 一樣
- Function $f$ :$$f:\{0,1\}^{32}\times\{0,1\}^{48}\rightarrow\{0,1\}^{32}$$其 input 為 R^i-1^ 和 round key K^i^
![](https://i.imgur.com/W8WVdeY.png)
圖中的 A 為 R^i-1^,J 為 K^i^
- E : Expansion function,把 R^i-1^ 從 32 bits 擴展到 48 bits
- B~i~ : 把 XOR 完的結果分成 8 等份
- S~i~ : S-box,為了不要讓 DES 容易被破解,所以用 S-box 實施非線性轉換
- B~0~B~6~ 為 row
- B~1~B~2~B~3~B~4~ 為 column
- C~i~ 即為 S~i~ 中 row 和 column 對應到的值
- P : Permutation
E, S~i~, P 都是固定的,詳見 [value of E, S~i~, P](https://en.wikipedia.org/wiki/DES_supplementary_material#Expansion_function_(E))
----
### Key scheduling
- 產生 Round key 的方法
![](https://i.imgur.com/1Nt3oR4.png)
- PC-1
- Key permutation
- Input : 64 bits (with 8 parity bits)
Output : 56 bits
- PC-2
- Key permutation
- Input : 56 bits
Output : 48 bits
- LS~i~ : Left rotate (因為是 rotate,所以最左邊的 bit 會被擠到最右邊)
- K~i~ : Key for round i
PC-1, PC-2, LS~i~ 都是固定的,詳見 [value of PC-1, PC-2, LS~i~](https://en.wikipedia.org/wiki/DES_supplementary_material#Permuted_choice_1_(PC-1))
----
### Breaking DES
- 缺點:Key space 太小了,只有 2^56^
- 如何攻擊?
- Exhaustive key search
- Differential cryptanalysis
- Linear cryptanalysis
- 改善:
- Use DES multiple times - ***Triple DES***
1. Choose three keys, K~1~, K~2~, K~3~ and perform$$E_{K_1}(E_{K_2}(E_{K_3}(m)))$$
2. Choose two keys, K~1~ and K~2~, and perform$$E_{K_1}(D_{K_2}(E_{K1}(m)))$$
- Find a new system that employs a larger key size than 56 bits - ***AES(Rijndael)***
---
## RSA
----
- Method
- Choose two very large primes, $p$ and $q$ $(>10^{100})$
- Compute $n=p*q$ and $z=(p-1)*(q-1)$
- Choose a number relatively prime to $z$ and call it $d$
- Find $e$ such that $e*d=1\ (mod\ z)$
- Application
- Plaintext $P$, $0\le P\le n$ (664-bit block is n ~ 10^200^)
- Encryption key = $(n, e)$
$C=P^e\ (mod\ \ n)$
- Decryption key = $(n, d)$
$P=C^e\ (mod\ \ n)$