Cryptography
====
這個文件將整理流行的加密演算法與其背後的數學。
[TOC]
密碼學概念
--------
### 對稱與非對稱式加密
這兩者的差別在於：加密時使用的key相不相同。想像使用對稱式密碼，對於多組伺服器你必須有多組不同的密碼，這使得管理上非常困難。並且，若是伺服器被入侵密鑰被取得，攻擊者能夠輕易解開儲存的密文。非對稱式為較晚發展的加密方式，加密用的叫做公鑰(public key)，解密用的是私鑰(private key)。可以把公鑰想成一把鎖，私鑰是這把鎖對應的鑰匙：任何人都可以很容易地把文件上鎖，但是只有握有鑰匙的人可以打開。
### 同態加密(Homomorphic Encryption)
與數學上的同態意思相同，即下列等式為真
$$ dec(enc(m1) \oplus enc(m2)) = m1 \diamond m2 $$
這是近年來又活熱的研究主題，開始漸漸有科學家提出新加密方式支援部分的運算子做同態運算，一直到2009年的Craig Gentry才提出完整的同態加密方式。
RSA
--------
這節將介紹RSA，一種非對稱式加密法。最早由英國數學家Clifford Cocks發明並被列為機密存入文檔案直到1997年才被公布。在此之前的1977年早被Ron Rivest, Adi Shamir和Leonard Adleman一起提出，因此被稱為世人熟知的RSA。
### 產生公私鑰
1. 選出兩組差不多大的質數$p$和$q$，$n=pq$。
2. $\phi(n)=(p-1)*(q-1)$。
3. 任選一個與 $\phi(n)$ 互質的 public exponent $e$
4. 計算$d$其中$ed\equiv 1\mod \phi(n)$
第3,4步驟可調換，d也可以先產生再算e。
以上：
公鑰：$(n, e)$
私鑰：$(\phi(n), d)$
產生key的簡單實作可以參考
https://github.com/iphkwan/SimpleRSA/blob/master/src/Key.cpp
更有效率的方法請參考下面的求模反函數小節
### 加密與解密
1. 由明文m計算密文c：$m^e \equiv c \mod{n}$
2. 由密文c計算明文m：$c^d \equiv m \mod{n}$
### RSA背後的數學
數學家試著想出一個容易計算但難以回頭的數學式，除非握有Trapdoor。
$$ m^e \equiv c \mod{n} $$
上列式子意思為$m$取$e$次方取$n$的餘數為$c$。其中$m$為明文message，$c$為密文ciphertext，$0<=m<n$。
從c推回m很困難，假設存在一個數字d，使得m得以還原
$$ c^d \equiv m \mod{n}$$
這個式子也可以寫成這樣
$$ m^{ed} \equiv m \mod{n}$$
問題是，如何將$d$算出來，正整數d存在嗎?
#### Euler's Totient Function
$\phi(N)$定義為：所有小於等於N的正整數與N互質的數目。比如$\phi(8)=4$因為1,3,5,7與8互質。
這函數兩個特性我們將用到：
1. 當N為質數的時候，$\phi(N)$很容易計算即為$N-1$。
2. 並且AB互質時，$\phi(A*B)=\phi(A)\phi(B)$
因此若知道一個數的質因數分解，就能把函數值算出來。然而RSA所使用的N為兩個大質數相乘，要知道其分解並不容易，但有$p$和$q$時，計算$\phi(N)$並非難事，即為$(p-1)(q-1)$。
#### Euler's Theorem
Euler's Theorem告訴我們，當$\alpha$與$n$互質時，以下成立
$$ \alpha^{\phi(n)} \equiv 1 \mod{n} $$
這裡將$\alpha$替換成明文$m$，左側再取$k$次方($k>=0$)，得到以下
$$ m^{k\phi(n)} \equiv 1^k \mod{n} \equiv 1 \mod n $$
將兩側同時乘上m
$$ m^{k\phi(n)+1} \equiv m \mod{n} $$
也就是說m的$k\phi(n)+1$次方取餘數還是m。與前面小節式聯立：
$$ k\phi(n)+1=ed $$
若有$\phi(n)$值d得以計算
$$ d = \frac{k\phi(n)+1}{e}$$
這個式子可以被看成
$$ ed \equiv 1 \mod{\phi(n)}$$
也就是e與d互為模反元素
#### 模反元素
若說$a$與$b$互為模反元素，則
$$ ab \equiv 1 \mod{n} $$
a的模反元素可寫成$a^{-1}$
模反元素有不只一個，可以用$a^{-1}+kn$列舉
Paillier Cryptosystem
--------
Paillier Cryptosystem[^pai_origin][^pai_intro][^pai_math_intro] 是個公鑰加密系統，並同態地支援某些運算。
[^pai_origin]: Paillier 原始論文, Paillier, Public-Key Cryptosystems Based on Composite
Degree Residuosity Classes http://www.cs.tau.ac.il/~fiat/crypt07/papers/Pai99pai.pdf
[^pai_intro]: Paillier 介紹文, Michael O’Keeffe, The Paillier Cryptosystem
A Look Into The Cryptosystem And Its Potential Application http://www.tcnj.edu/~hagedorn/papers/CapstonePapers/OKeeffe/CapstoneOKeeffeCryptography.pdf
[^pai_math_intro]: Paillier 數學介紹文, Paillier Cryptosystem: A Mathematical
Introduction http://www2.cs.uni-paderborn.de/cs/ag-bloemer/lehre/proseminar_WS2005/material/Volkhausen_Ausarbeitung.pdf
### 基本參數設置
Paillier Cryptosystem 的運算都是在下列三個空間中運作的：$\mathbb Z_n$、$\mathbb Z_n^*$、$\mathbb Z_{n^2}^*$。
#### 三個空間 $\mathbb Z_n$、$\mathbb Z_n^*$ 與 $\mathbb Z_{n^2}^*$
（以下用 $a\perp b$ 代表 $a,b$ 互質。）
取 $p,q:\textit{prime}$，定義 $n=pq.$
$\mathbb{Z}_n:=\{0,1,2,...,n-1\}$；作用於 $\mathbb{Z}_n$ 內的加法、乘法運算都要對 $n$ 取餘數。
$\mathbb{Z}^*_n:=\{a\in \mathbb{Z}_n | a\perp n\}$；也就是收集 $\mathbb{Z}_n$ 中有模反元素的那些數。同樣地，集合中的乘法要對 $n$ 取餘數（成為[整數模$n$乘法群](https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n)）。根據定義，可計算集合大小：
$$|\mathbb{Z}_n| = \phi (n)=\phi (pq) = (p-1)(q-1).$$
$\mathbb{Z}^*_{n^2}:=\{a\in \mathbb{Z}_{n^2} | a\perp n^2\}$；也就是收集 $1,2,...,(n^2-1)$ 之中有模反元素（under modulo $n^2$）的那些數，而集合中的乘法要對 $n^2$ 取餘數。一樣來計算集合大小：
$$|\mathbb{Z}^*_{n^2}| = \phi (n^2)=p^2q^2(1-\frac1p)(1-\frac1q)=pq(p-1)(q-1)=n\phi(n).$$
上面的第二個等號是利用[歐拉函數的公式](https://en.wikipedia.org/wiki/Euler%27s_totient_function#Euler.27s_product_formula)。
#### 公鑰 $g$
公鑰是由 $n$ 以及一個小於 $n^2-1$ 的整數 $g$ 構成的序對 $(n,g)$
一個數 $g\in\mathbb{Z}_{n^2}^*$ 在 modulo $n^2$ 之下的階數（order、[multiplicative order](https://en.wikipedia.org/wiki/Multiplicative_order)），定義為
$$|g|_{n^2}:=\textrm{smallest } a\textrm{ satisfying } g^a\equiv 1\mod n^2.$$
也就是說 $g$ 在 $\mathbb{Z}_{n^2}^*$ 中要乘出 $1$ 所需的最小次方。
現在要找一個 $g\in \mathbb{Z}^*_{n^2}$ 滿足 $|g|_{n^2}$ 為 $n$ 的倍數。換句話說
$$|g|_{n^2} = kn\ \ \textrm{ (for some } k\in\mathbb{N}).$$
此外後來還提到 $g$ 需要滿足另一個條件：上式的 $k$ 不能為 $p,q$ 的倍數。
這裡把滿足$g$條件的集合稱為 $\mathcal{B}$
#### Carmichael- $\lambda$ 函數
函數 $\lambda(n)$ 定義為：能讓 $\mathbb{Z}_n^*$ 中所有元素 $a\in \mathbb{Z}_n^*$ 都乘出 $a^\square\equiv 1$ 的最小共同指數。換句話說：
$$\textrm{Minimize } \lambda(n) \textrm{ s.t. } \forall a\in \mathbb{Z}_n^*\ \ ,\ \ a^{\lambda(n)}\equiv 1 \mod n.$$
對於 $n=pq$，有 $\lambda(n)=\operatorname{lcm} (p-1,q-1)$。
根據 $\phi(n)$ 的定義，$\lambda(n)\leq\phi(n)$，這是因為 $\phi(n)$ 雖滿足
$$\forall a\in \mathbb{Z}_n\ \ ,\ \ a^{\phi(n)}\equiv 1 \mod n$$
，但它不一定是滿足上式的數中最小的。
#### 加密函數 $\varepsilon_g$
定義函數 $\varepsilon_g$
$$\begin{aligned}\varepsilon_g:(\mathbb{Z}_n\times\mathbb{Z}_n^*)&\to\mathbb{Z}_{n^2}^*\\ (x,y)&\mapsto g^x\cdot y^n\mod n^2\end{aligned}$$
若 $\operatorname{order}_{n^2}(g)$ 是 $n$ 的倍數，則 $\varepsilon_g$ 是個 bijection （一對一映成函數）（證明從略）。
這個 $\varepsilon$ 函數更早出現在 Benaloh 的論文[^benaloh]第 27 頁。
[^benaloh]: Benaloh, Verifiable Secret-Ballot Elections http://www.cs.yale.edu/publications/techreports/tr561.pdf
值得注意的是
$$(1+n)^n = \binom n0 + \binom n1n + \binom n2n^2 + \cdots \equiv 1+n^2+\cdots\equiv1\mod n^2$$
，因此 $n+1\in\mathcal{B}$，也就是 $g$ 的其中一組選擇。
若將 $\varepsilon_g$ 的反函數記為 $\varepsilon_g^{-1}: w\mapsto (x,y)$，則對任意 $w\in\mathbb{Z}^*_{n^2}$ ，定義 $[[w]]_g\in\mathbb Z_n$ 為
$$[[w]]_g:=\textrm{The } x \textrm{ component of } \varepsilon_g^{-1}(w).$$
將$n+1$代入$g$，我們可以得到
$$ c=\varepsilon_{n+1}([[c]]_{n+1}, z) = (n+1)^{[[c]]_{n+1}}z^n \mod n^2\ $$
兩側取 $\lambda(n)$ 次方
$$ c^{\lambda(n)}= (n+1)^{\lambda(n)[[c]]_{n+1}}z^{n\lambda(n)} \mod n^2 $$
由於$n\lambda(n)=\lambda(n^2)$，根據Carmichael-$\lambda$函數的定義，$z^{\lambda(n^2)} \equiv 1 \mod n^2$
$$ c^{\lambda(n)}= (n+1)^{\lambda(n)[[c]]_{n+1}} \mod n^2 $$
展開得到
$$ c^{\lambda(n)} = 1+n\lambda(n)[[c]]_{n+1} \mod n^2 $$
將此式子標記為$(*)$以利後面證明使用
### 加密與解密
#### 加密
以 $(n,g)$ 為公鑰，取 $m\in\mathbb{Z}_n$ 為明文，並選擇亂數 $r\in\mathbb{Z}_n^*$
計算密文
$$\begin{aligned}
c &= \varepsilon_g(m,r) \in \mathbb Z_{n^2}^*\\
&=g^mr^n\mod n^2
\end{aligned}$$
#### 解密
定義$L(u)=(u-1)/n\mod n$
以$\lambda(n)$為私鑰，計算明文
$$ m=L(c^{\lambda(n)}\operatorname{mod}n^2)\mu \mod n, \mu=L^{-1}(g^{\lambda(n)}\operatorname{mod}n^2) $$
將$(*)$代入
$$m=L(1+n\lambda(n)[[c]]_{n+1})*L^{-1}(1+n\lambda(n)[[g]]_{n+1}) \mod n$$
把$L$函數算出來
$$m=\frac{\lambda(n)[[c]]_{(1+n)}}{\lambda(n)[[g]]_{(1+n)}} \mod n$$
並化簡
$$m=\frac{[[c]]_{(1+n)}}{[[g]]_{(1+n)}} \mod n$$
將$[[c]]_{n+1}$換底成為$[[c]]_g[[g]]_{n+1}$(待證明)
$$ m = \frac{[[c]]_g[[g]]_{n+1}}{[[g]]_{n+1}}$$
相消後得到
$$ m = [[c]]_g$$
由於計算 $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ 需要 $p,q$，因此 $p,q$ 保留為私鑰。
#### $L$ 函數
[維基百科](https://en.wikipedia.org/wiki/Paillier_cryptosystem#Background)提到，由於
$$(1+n)^x \equiv_{n^2} 1+nx$$
，因此若令 $y=(1+n)^x$，代入上式可求得 $x$：
$$\begin{aligned}
y&=1+nx\\
y-1&=nx\\
\frac{y-1}{n}&=x
\end{aligned}$$
（這裡的除不是乘以模反）
因此 $y=(1+n)^x$ 之中的指數 $x$ 可以透過基本運算得到：
$$\log_{1+n}y = \frac{y-1}n$$
將這個以 $(1+n)$ 為底的對數函數（離散對數）訂為
$$L(y) = \log_{1+n}y = \frac{y-1}n$$
### 同態性質
Paillier Cryptosystem 滿足下面的同態性質：
$$\textit{Enc}(m_1+m_2) = \textit{Enc}(m_1)\times\textit{Enc}(m_2)$$
換句話說，將明文相加再加密，與將密文相乘是同一回事。
證：
$$ \begin{aligned}
\textit{Enc}(m_1)\times\textit{Enc}(m_2) &= g^{m_1}r_1^n\times g^{m_2}r_2^n\\
&=g^{m_1+m_2}\cdot(r_1r_2)^n\\
&=\textit{Enc}(m_1+m_2)
\end{aligned} $$
上面的性質與指數律很像，因此也可以引申為
$$ \textit{Enc}(m\times k) = (\textit{Enc}(m))^k\ ,\ \ \textrm{for some integer } k.$$
不過上面對於明文的運算都要取 modulo $n$，對密文則是取 modulo $n^2$.
### 安全性基於「合數剩餘假設」
#### 模 $n^2$ 的 $n$ 次剩餘
$\mathbb{Z}^*_{n^2}$ 有一個特殊的子集：$\textit{NR}\subseteq\mathbb{Z}^*_{n^2}$，定義如下：
$$\textit{NR} := \{a\in\mathbb{Z}^*_{n^2}\ |\ a\equiv r^n \operatorname{mod} n^2\ \ ,\ \textrm{for some } r \}$$
換句話說，若某 $r$ 乘了 $n$ 次後 $\textrm{mod }n^2$ 會餘 $a$，那麼這個 $a$ 就要被收集到 $\textit{NR}$ 之中。
這個集合稱為「模 $n^2$ 的 $n$ 次剩餘（的集合）」。$\textit{NR}$ 的符號不知道怎麼來的，至少這篇[^pai_math_intro]是這樣用。以下關於難題的複雜度類別也依照這篇的記號。
#### 確定合數剩餘假設 Decisional Composite Residuosity Assumption
> 給定一個合數 $n$ 與整數 $z$，問是否存在某 $y$ 滿足
>
> $$y^n\equiv z\mod n^2$$
換句話說，$z$ 能不能是 $\textit{mod }n^2$ 下的 $n$ 次剩餘？
$$z\overset{?}{\in}\textit{NR}$$
本文把這問題的難度稱為 $\textit{CR(n)}$，DCRAssumption 猜測 $\textit{CR(n)}$ 是困難的（例如不存在多項式時間解法）。
#### 算出 $[[c]]$ 所需要的難度
考慮下面問題：
> 已知 $c, g\in\mathbb Z_{n^2}^*$，如何求出 $[[c]]_g$ ？
將這類問題的難度記為 $\textit{Class(n)}.$ 另外考慮類似的問題：
> 已知 $c, g\in\mathbb Z_{n^2}^*\ ,\ m\in\mathbb Z_n$，如何確定 $m \overset{?}{=} [[c]]_g$
將這類問題的難度記為 $\textit{D-Class(n)}.$ 可想而知，$\textit{Class(n)}$ 比 $\textit{D-Class(n)}$ 還要難，因為前者被解的話後者自然就解開了。
#### 破解得了 $\textit{CR}(n)$，才有可能破解 Paillier Cryptosystem
若 $\textit{D-Class(n)}$ 可被破解，代表取適當的 $c, g\in\mathbb Z_{n^2}^*\ ,\ m\in\mathbb Z_n$，我們能知道下式的 $r$ 存不存在（也就決定 $m$ 是不是下式的解）：
$$g^m r^n\equiv c \mod n^2$$
今任取 $g$，並取 $m=0$，則利用 $r$ 的存在性便能夠確定 $c$ 是不是模 $n^2$ 的 $n$ 次剩餘。
換句話說，若 $\textit{D-Class(n)}$ 被破解，$\textit{CR}(n)$ 也會跟著被破解。因此難度的排序是
$$\textit{Paillier Crypt}\overset{def}{=}\textit{Class(n)}\geq\textit{D-Class(n)}\geq\textit{CR(n)}$$
第一個等號是因為 $[[\cdot]]$ 正是解密函數。
牽涉數論的演算法
-------------
有些內容參考這本書：*[Handbook of Applied Cryptography](http://cacr.uwaterloo.ca/hac/)*，裡面有不少密碼學常用到的、處理質數的演算法。
### 求模反元素
#### 擴展歐幾里得演算法
給定 $a$、$n$ 要尋找 $x$ 使得 $ax \equiv 1 \mod n$，相當於求解以下不定方程的整數解：
$$ ax - ny = 1$$
而 $x$、$y$ 有整數解的前提是 $a$、$n$ 互質（$a\perp n$）。
利用輾轉相除法可以求解上式：輾轉相除法是將 $a$、$n$ 交替相除以得到 $\gcd(a,n)$ 的手段，因此最後 $\gcd(a,n)=1$ 能被表為 $a,n$ 的線性組合。以下舉例：
> Find $y$ such that $$32y\equiv 1\mod 77$$
這相當於解以下的方程：
$$77x + 32y = 1$$
利用輾轉相除法找到 $32$ 與 $77$ 的最大公因數，同時用下標寫出每個階段是幾個 $77$ 加上幾個 $32$。
例如 $77$ 就是「一」個 $77$ 加上「零」個 $32$，所以就寫 $77_{(1,0)}$ ：
因此解得 $x=5$、$y=-12$
$\implies 32$ 在 $\operatorname{mod}77$ 下的模反元素是 $-12\equiv 65\mod 77.$
這就是[擴展歐幾里得演算法](https://zh.wikipedia.org/wiki/%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95)，一邊輾轉相除同時要 maintain 餘數被 77, 32 表示為線性組合時的係數。
擴展歐幾里得演算法同時也可以用來計算[有限體](https://en.wikipedia.org/wiki/Finite_field) $\textrm{GF}(2, n)$ 的乘法反元素。
#### 利用歐拉定理
第二個求模反元素的方法是利用 $5^{\phi(23)}\equiv1\mod23$
$\implies 5^{22}\equiv1\mod23$
$\implies5\cdot5^{21}\equiv1\mod23$
因此 $5$ 在 $\operatorname{mod}23$ 下的模反元素是 $5^{21} \equiv 14 \mod 23.$
### 求 $a^k(mod\ n)$
#### 重複平方並相乘
寫出 $k$ 的二進位表示法，例如 $k=1011010_2=2^1+2^3+2^4+2^6$。
接著重複計算 $a\leftarrow a^2\textrm{ mod } n$ 以得到 $a$ 的所有 $2^i$ 次 $(i\textrm{ from }1\textrm{ to }\lfloor\lg k\rfloor)$
過程中會分別算到 $a^2, a^{2^3}, a^{2^4}, a^{2^6}$，將它們依序乘起來就好了。不考慮大數運算的話複雜度應該是 $\Theta(\lg k)$。
### 質數 / 合數檢定法
#### Fermat primality test
#### Miller-Rabin test
### 求某 $g$ 在 $\mathbb Z_n^*$ 中的 multiplicative order
#### Baby-step, Giant-step
這是任何[群](https://zh.wikipedia.org/wiki/%E7%BE%A4)都可以求 order 的演算法。$\mathbb Z_n^*$ 是群，因此也可以用，不過比較慢。此外類似的策略也被用來暴力破解離散對數問題。
首先計算第一個系列（baby-step）：
$$g^1, g^2, g^3, ..., g^{999}\mod n$$
，如果其中一項為 $1$，問題就解決了。否則繼續計算第二個系列（giant-step）：
$$g^{1000},g^{2000},g^{3000},...g^{1000000}\mod n$$
如果這些值與第一個系列的值有重複，那也算完了（例如 $g^{9912}\equiv1$ 會讓我們算出 $g^{88}\equiv g^{10000}$ ）。
由於 $|\mathbb Z_n^*|$ 是 $g$ 的 order 的上限，因此在確定 $|\mathbb Z_n^*|<1000000$ 的情況下，上面的算法就會找到 $g$ 的 order。
如果 $|\mathbb Z_n^*|$ 未知，以上步驟又都失敗，就要考慮重新調整：讓 baby-step 走更遠一點，giant-step 跨更大步、更遠，再從頭做一次。
不過重來時有些值是不用重算的，下次 baby-step 的數列值可以由上次兩個數列互乘得到。
#### $|\mathbb Z_n^*|$ 已被分解時的算法
由於 $g^{|\mathbb Z_n^*|}\equiv 1\textrm{ (mod }n)$，因此 $|\mathbb Z_n^*|$ 是 $g$ 的 order 的上限。現在將 $|\mathbb Z_n^*|$ 質因數分解成
$$|\mathbb Z_n^*|=p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_k^{e_k}$$
首先測試 $g$ 的 $p_1^{\square}p_2^{e_2}p_3^{e_3}\cdots p_k^{e_k}$ 次方是否為 $1\textrm{ (mod }n)$，其中 $\square=0,1,2,\cdots$。當測出來真的變成 $1$ 時就停下，把這個 $\square$ 值記為 $r_1$。
接著測試 $g$ 的 $p_1^{r_1}p_2^{\square}p_3^{e_3}\cdots p_k^{e_k}$，一樣 $\square=0,1,2,\cdots$，當算出 $1$ 時再停下，把這個 $\square$ 值記為 $r_2$。
接著測試 $g$ 的 $p_1^{r_1}p_2^{r_2}p_3^{\square}\cdots p_k^{e_k}$，以此類推，最後得到一個數
$$p_1^{r_1}p_2^{r_2}p_3^{r_3}\cdots p_k^{r_k}$$
就是 $g$ 的 order。
Sign in with Wallet
Connect another wallet