前言： 前面介紹了 RSA 公鑰加密算法，而在公鑰加密體系中，另一類重要的加密體制是基於離散對數的難解性，如 ECC 橢圓曲線加密、Die-Hellman 算法、 ElGamal 算法等。為了解決離散對數問題，我們需要先學習《近世代數》。
本文涉及知識點實操練習——密碼學原理https://www.hetianlab.com/expc.do?ec=05626101-9d81-452c-beaf-cbc7a5225fda&pk_campaign=baijia-wemedia
（密碼學是研究如何隱密地傳遞信息的學科。在現代特別指對信息以及其傳輸的數學性研究，常被認為是數學和計算機科學的分支，和資訊理論也密切相關。密碼學是信息安全等相關議題，如認證、訪問控制的核心。）
代數基本知識: 1. 群2. 環3. 域4. 有限域 GF()5. 多項式環
群：
定義： 設G 是非空集合，若在 G 內定義一種代數運算 $\bigodot$ ，且滿足下列 4 個條件，則稱 G （對運算 $\bigodot$ ）構成一個群： (1) 封閉性：對任意的 a,b $\epsilon$ G ，恆有 a$\bigodot$b $\epsilon$ G; (2) 結合律：對任意的 a,b,c $\epsilon$ G ，恆有 (a$\bigodot$b)$\bigodot$c = a$\bigodot$(b$\bigodot$c) (3) 有單位元：存在 e $\epsilon$ G ，對任意的 a $\epsilon$ G, 有 a$\bigodot$e=e$\bigodot$a=a (4) 每個元存在逆元：對任意 a $\epsilon$ G, 存在 b $\epsilon$ G, 使得 a$\bigodot$b=b$\bigodot$a=e ，稱 b 為 a的逆元。其中運算 $\bigodot$ 可以是通常的乘法或者是加法。若 $\bigodot$ 為乘法，則稱 G 為乘法群，單位元記為 1. 若$\bigodot$為加法，則稱 G 為加法群，單位元記為 0 。一般情況下，記： $$ \underbrace{a \bigodot a \bigodot \cdots \bigodot a }_{k 個 }=a^k$$群 G 所含元素的個數，稱為該群的階 。若群 G 含有有限個元素，則稱 G 為有限群，否則，為無限群。 若對群G 中任何 a,b $\epsilon$ G ，有 a $\bigodot$ b = b $\bigodot$ a ，則稱 G 為交換群或 Abel 群。
循環群： 定義： 設（$G,\cdot ） $ 是一個群如果群 $G$ 中存在一個元素 $\alpha$ ，使得對群 $G$ 任意元素 $b$ 都存在一個整數$i$ ,使得 $b=\alpha^i$ ，則我們稱 $G$ 是一個 循環群 。元素 $\alpha$ 是 $G$ 的一個 生成元 加法循環群： 例：$ （ Z_6,\oplus ） $ 是循環群，其中 $Z_6=${0,1,2,3,4,5} ， $\oplus$ 為模 6 加法，其生成元為 1 或 5 。生成元的含義可以理解為 ：1 或 5 的加法，可以實現群 $Z_6$ 內所有的元素，如： 5+5+.....+ 5 mod 6 = 5， 35 mod 6 = 5 10 mod 6 = 4， 40 mod 6 = 4 ， 15 mod 6 = 3， 45 mod 6 = 3 20 mod 6 = 2， 50 mod 6 = 2 25 mod 6 = 1， 55 mod 6= 1 30 mod 6 = 0， 60 mod 6= 0所以通過 生成元 5 的模 6 的加法，可以得到群內的所有元素，實現循環群。而 2,3,4 不能作為生成元，是因為這些元素的模6 加法並不能得到群內所有的元素，且並不是連續循環的數。乘法循環群 也是同樣的道理。 有限循環群的生成元還具有以下性質： （元素的階） ：循環群$ （ G,\cdot ） $ ， $\alpha$ 為 $G$ 的一個生成元， 1 為 $G$ 的單位元， $G$ 的階為 $n$ , 則：
$\alpha^n=1$
環： 定義： 若集合R 上定義了兩種二元運算： +( 加法 ) 及 x( 乘法 ) ，且滿足下列 4 個條件，則稱 R 對這兩種運算構成了一個環，記為 (R,$+$,$\times$):(1) (R,$+$) 是一個 Abel 群，其恆等元為零元，用 0 表示。 (2) 對任何 a,b,c $\epsilon$ R ，有 $a\times (b \times c)=(a \times b) \times c$ (3)如果一個環 (R,$+$,$\times$) 還滿足條件：對任意的 a,b$\epsilon$ R ，有 $a\times b =b\times a$ ，則稱環(R,$+$,$\times$)為交換環。域： 定義： 設$F$ 是一個交換環，若 $F$ 中的所有的非零元素對乘法都存在逆元，則稱 $F$ 為一個域。如果一個域所包含的元素是有限的則稱此域是有限域，否則稱為無限域。 有限域中所含元素的個數稱為有限域(R,$+$,$\times$) 的階。
有限域： 定義1 ： 有限域又常稱為 Galois 域，並以 GF(q) 或 $F_q$ 表示，其中 q 表示有限域的階。定義2 ： 設$F_1$ 、 $F_2$ 是兩個域，稱 $F_1$ 到 $F_2$ 的一個可逆映射 $\sigma$ 為一個同構 ( 映射 ) ，如果 $\sigma$ 是保持運算的映射，即對任意的$a,b cF_1$ ，有： $\sigma(a+b)=\sigma(a)+\sigma(b)$ ， $\sigma(a \cdotb)=\sigma(a) \cdot \sigma(b)$定理3 ： 設$F$ 是有限域，則有： (1) 在同構的意義下，階與$F$ 相同的有限域只有一個。同階的有限域必同構。 (2)有限域 $F$ 的階必為某個素數的冪 . (3) 設 $F$ 的階為 $q=p^n$ ， p 是一個素數，則 $F$ 的任何一個子域的階為 $p^m$ ，其中 m 是 n 的因子。 (4) 記 $F_q^ $為有限域 $F_q$ 的所有非零元構成的集合，則 $F_q^ $關於乘法做成一個階為 $q-1$ 的循環群。因此， 對所有的 $a\epsilon F_q$ ，有 $a^q=a$ 。這個群稱為 $F_q$ 的乘法群，乘法群 $F_q^*$ 的生成元稱為 $F_q$ 的本原元，共有 $\phi(q-1)$ 個本原元。 (5) 設$F_q$( 其中 $q=p^n$) 是一個有限域，則對任何 $a,b\epsilon F_q$ 及非負整數 $k\geqslant 0$ ，有： $(a+b)^{p^k}=a^{p^k}+b^{p^k}$
多項式環： 定義： 設$F$ 是一個域，多項式 $f(x)=a_nx^n+\cdot\cdot\cdot+a_1x+a_0$ ，其中 $a_i\epsilon F$ ， $n\epsilon N$ 。
若$a_n \neq 0$ ，稱 n 為該多項式的 次數 ，稱$a_n$ 為 首項係數 。
對於域 $F$ 上 $x$ 的多項式的全體組成的集合記為 $F[x]$ 。 多項式 $a(x)$ 的次數記為 $deg(a(x))$ 設存在多項式 $f(x) 與 g(x)$ ，滿足： 1.加法運算： $f(x)+g(x) \epsilon F[x]$ 2.乘法運算： $f(x)\cdot g(x) \epsilon F[x]$容易驗證 $F[x]$ 對這樣定義的多項式加法與乘法構成一個交換環，稱為多項式交換環。
不可約多項式： 設 $f(x)$ 是 $F[x]$ 上的一個次數大於零的多項式，如果它不能分解成兩個低次數的多項式的乘積，則稱 $f(x)$ 是$F$ 上的不可約多項式。 設 $p(x)$ 是 $F[x]$ 中的 $n$ 次不可約多項式，令 $F[x]_{p(x)}$ 為 $F[x]$ 中所有次數小於 $n$ 的多項式的集合。 定義 $F[x]_{p(x)}$ 上的二元運算 $\oplus$ 和 $\otimes$ 如下： 任取 $a(x),b(x)\epsilon F[x]_{p(x)}$ ， $a(x)\oplus b(x)= (a(x)+b(x)) mod$ $p(x)$ $a(x)\otimes b(x)= (a(x)\cdot b(x)) mod$ $p(x)$
加密算法：
ElGamal算法
Menezes-Vanstone橢圓曲線密碼體制
Diffie-Hellman算法
橢圓曲線上的Diffie-Hellman算法
橢圓曲線加密ECC
$Z_p$上的離散對數問題： $Z_p$上的離散對數問題是指對於循環群 $Z_p$ （ p 是一個素數）， $\alpha \epsilon Z_p$ 是群 $Z_p$ 的生成元，對於任意的 $c\epsilon Z_p$ ，尋找唯一 的整數 $d （ 0\leqslant d\leqslant p-1 ） $ 滿足： $$C\equiv a^d(modp)$$ 我們把整數 $d$ 記為 $log_{\alpha}c$ ，並稱之為離散對數。
ElGamal算法： 背景： ElGamal是建立在解有限乘法群上的離散對數問題的困難性基礎上的一種公鑰密碼體制。 算法描述： (1) 公開參數：取大素數 $p$ ，並取 $\alpha$ 是乘法群 $Z_p^*=$ { $1,\cdot\cdot\cdot,p-1$} 的一個生成元。 (2) 密鑰生成：隨機選取整數 $d$ ： $0 < d < (p-1)$ 並計算 $\beta =\alpha^d$ $mod$ $p$ 。 公開參數：$p 和 \alpha$ 公鑰：$\beta$ 私鑰：$d$
(3) 加密運算：對於明文 $m$ ，選取隨機整數 $k$ :$0 < k < (p-1)$ ，計算： $c_1=\alpha^k$ $mod$ $p$， $c_2=m\beta^k$ $mod$ $p$ 得到密文 $c=(c_1,c_2)$(4) 解密運算：對於密文 $c=(c_1,c_2)$ ，用私鑰 $d$ 解密。$m=c_2(c_1^d)^{-1}$ $mod$ $p$
計算離散對數的算法 :
1. Shanks 算法
2. 小步大步發（ baby-step 、 giant-step ）算法
3. Pohlig-Hellman 算法
4. 指數演算法 (index-calculus)
Menezes-Vanstone 橢圓曲線密碼體制 背景： Menezes-Vanstone 橢圓曲線密碼體制是 ElGamal 密碼體制在橢圓曲線上的模擬。 算法描述：(1) 公開參數：設 $p>3$ 是一個素數， E 是有限域 $F_p$ 上的由方程 $y^2=x^3+ax+b$ 表示的橢圓曲線，$E(F_p)$是相應的 Abel 群。 G 是 $E(F_p)$ 中具有較大素數階 $n$ 的一個點。(2) 生成密鑰：隨機選取整數 $d$ : $2\leqslant n\leqslant n-1$ ，計算 $P=dG$ 。 $d$是私鑰 $P$是公鑰(3) 加密運算：對任意明文 $m=(m_1,m_2)$ ，隨機選取一個整數 $k$ ： $1\leqslant k\leqslant n-1$ ，使得$(x,y)=kP$，滿足 $x$ 與 $y$ 均為非零元素。並計算：$C_0=kG$ $c_1=m_1x$ $mod$ $p$ $c_2=m_2y$ $mod$ $p$ 得到密文為 $(C_0,c_1,c_2)$(4) 解密運算： 1. 計算 $dC_0=(x,y)$ 2. 計算 $m_1=c_1x^{-1}$ $mod$ $p$ 3. 計算 $m_2=c_2y^{-1}$ $mod$ $p$ 即得明文為 $(m_1,m_2)$
Diffie-Hellman算法:
背景： Die-Hellman算法由 Whiteld Die 和 Martin Hellman 提出，該算法的安全性也是基於一般有限域上的 離散對數問題的難解性。算法描述：(1) 假設 Alice 和 Bob 之間要建立一個共享密鑰。 Alice 和 Bob 首先選定一個大素數 $p$ ，並選 $g$ 為乘法群 $F_p^*$中的一個生成元。(2) Alice選取一個私鑰 a( 整數 ) ： $1\leqslant a\leqslant p-2$ ，計算 $A=g^a$ $mod$ $p$ 。發送 A 給 Bob 。(3) Bob選取一個私鑰 b( 整數 ) ： $1\leqslant b\leqslant p-2$ ，計算 $B=g^b$ $mod$ $p$ 。發送 B 給 Alice 。(4) Alice 計算 $k=B^a$ $mod$ $p$ (5) Bob 計算 $k=A^b$ $mod$ $p$因為 $B^a=(g^b)^a=g^{ab}=(g^a)^b=A^b$ $mod$ $p$ ， Alice 與 Bob 計算得到的 $k$ 是相同的。這樣的 $k$ 可以作為通信的共享密鑰由於 $a$ 與 $b$ 是保密的，所以即使攻擊者知道了 $p 、 g 、 A 、 B$ ，也很難獲得 Alice 與 Bob 的共享密鑰 $k$ 。因為攻擊者要想獲得 $k$ ，則需要先解決離散對數問題 $A=g^x$ $mod$ $p$ 或 $B=g^x$ $mod$ $p$ , 而這是困難的。橢圓曲線上的Die-Hellman 算法 : (1) Alice和 Bob 之間要建立一個共享密鑰。 選取公共參數：取 $q>3$ 是某個素數冪， $E 是 F_q$ 上的橢圓曲線，$E(F_q)$ 是相應的 Abel 群， G 是 $E(F_q)$ 中的一個具有較大素數階 $n$ 的點。(2) Alice選取一個私鑰 a( 整數 ) ： $1\leqslant a\leqslant n-2$ ，計算 $A=aG$ 。發送 A 給 Bob 。(3) Bob選取一個私鑰 b( 整數 ) ： $1\leqslant b\leqslant n-2$ ，計算 $B=bG$ 。發送 B 給 Alice 。(4) Alice 計算 $K=aB$ (5) Bob 計算 $K=bA$顯然 Alice 與 Bob 計算得到的 $K$ 是相同的： $aB=a(bG)=(ab)G=b(aG)=bA$$K$ 即為 Alice 與 Bob 之間的共享密鑰。橢圓曲線上的Die-Hellman 密鑰交換算法的安全性基於橢圓曲線上離散對數問題的難解性。橢圓曲線密碼體制1.有限域 $F_p$ 上 $ECC$ 的加法運算規則： 設 $p>3$ 是一個素數，那麼有限域 $F_p$ 上的橢圓曲線 $E$ 可以表示成方程： $$y^2=x^3+ax+b(mod p)$$ 橢圓曲線$E_p(a,b)$ ， $p$ 為素數， $x,y \epsilon[0,p-1]$ ，$y^2=x^3+ax+b$ ($mod$ $p$)
這裡 $a,b \epsilon F_q$ ，滿足： $$4a^3+27b^2 \neq 0 mod p$$ 集合 $E(F_p)$ 中的加法運算定義為： 對任何 $P=(x_1,y_1) \epsilon E(F_p)$ ， $Q=(x_2,y_2) \epsilon E(F_p)$ 1. $P+O=P$ （ $O$ 為無窮遠點） 2. $$P+Q=\begin{cases}O ， & 如果 x_1=x_2,y_1=-y_2\ \(x_3,y_3),&否則 \end{cases}$$ 其中： $$\begin{cases}x_3=\lambda^2-x_1-x_2\y_3=\lambda(x_1-x_3)-y_1\end{cases}$$$$\lambda =\begin{cases} \fr ac{y_2-y_1}{x_2-x_1},& 如果 P\neq Q\ \ \frac{3x_1^2+a}{2y_1},& 如果 P=Q \ \end{cases}$$如果 $P+Q=O$, 則記 $Q=-P$ ，並稱 $-P$ 為 $P$ 的負元。一般地，我們將 $\underbrace{P+P+\cdot\cdot\cdot+P} {n次 }$ 記為 $np$ ，即 $np=$ $\underbrace{P+P+\cdot\cdot\cdot+P} {n次 }$ ，同時，定義： $nP=O$ （零元）
有限域模p 一個有限域是整數模 $p$ 的集合（ integers mod p,p 為素數），可表示為 $z/p$, $GF(p)$, 或者 $F_p$ ，一般用$F_p$。橢圓曲線的階 定義：一個群有多少個點叫做這個群的 「 階 」 （ order ）
2.ECC 加密算法描述： 點G 稱為基點（ base point ）$k$為私鑰$K$ 為公鑰 其中 $K=kG$ ， $K 、 G$ 為橢圓曲線 $E_p(a,b)$ 上的點， $n$ 為 $G$ 的階 $(nG=O無窮大 )$ ， $k$ 為小於 $n$ 的整 數。對於給定的$k$ 和 $G$ ，根據加法法則，計算 $K$ 很容易。而基於離散對數的難解性，給定 $K$ 和 $G$, 求 $k$ 則非常困難。 1. 公開參數 ：Alice 選取一條橢圓曲線 $E_p(a,b)$ ，並選取橢圓曲線上的一點，作為基點 G 。 2. 生成公鑰 ：Alice 選取一個 私鑰 $k$ $(k < n)$ ，生成 公鑰 $K=kG$。 3. Alice 將 $E_p(a,b)$ 和點 K ， G 傳給用戶 Bob 4. 加密運算 ：Bob 將 明文 編碼到 $E_p(a,b)$ 上的一點 $M$ , 取一個隨機數 $r(r < n)$ 。 5. Bob 計算點 $C_1=M+rK$ 和 $C_2=rG$ 6. 用戶Bob 將 $C_1 、 C_2$ 傳給用戶 A 。 7. 解密運算 ： Alice 計算： $M=C_1-kC_2$ ，將 M 解碼就得到明文了。
(這裡 :$C_1-kC_2=M+rK-k(rG)=M+rkG-rkG=M$)
後記 : 在學習ECC 橢圓曲線加密等，基於離散對數難解性問題的加密算法前。我們需要先掌握好《近世代數》的知識點。因為常見的橢圓曲線加密都是在有限域內實現的，首先得知道啥是 " 有限域 " 。下一篇我會給大家演示在實戰中的應用，所以基礎先要打好。文中有錯誤的地方，歡迎讀者留言指出。