最後提到RSA以及DH
另外還有數學的另一個難題-橢圓曲線

RSA加密

步驟：

找兩個夠大的質數，p & q -> 用質數檢定法
計算 $n=p \times q$ -> 單向函數(one-way function)的簡單部分
計算 $\phi(n)=(p-1) \times (q-1)$
決定公開金鑰(加密)：where $1找一個數字跟phi(n)互值
決定私密金鑰(解密)：$ed=1 \mod \phi(n)$ and $0 \le d \le n$ -> e, d互為mod phi(n)的乘法反元素
公開金鑰：$PU={ e,n }$
私密金鑰：$PR={ d,n }$

質數的重要性：
如果p是質數，a i == a j (mod p)
則具有消去律，i == j (mod p)

Diffie-Hellman Key Exchange 迪菲-赫爾曼密鑰交換

可以讓通訊雙方在不安全的環境下傳遞密鑰(Key Exchange)

CC BY-SA 4.0

圖中的a與b是由雙方各自決定的自然數，且這兩個數必須小於p，g則是原根(透過這個數做特定計算可以得到一堆數字)。
Alice傳遞g, p以及A ($A=g^a \bmod p$)
Bob取得g, p, A後計算出B回傳給Alice ($B=g^b \bmod p$)
兩個人都根據對方傳給自己的A或B加上自訂的自然數為指數除以p的餘數，會得到一個相同的K，作為之後做對稱式加密所需用到的Key。

將$B^a$和$A^b$各自用$(g^b)^a$和$(g^a)^b$代回。$(g^b)^a \bmod p =(g^a)^b \bmod p$

維基百科上的資料：

EIGamal加密算法

詳細步驟如下：

首先知道 $q$ 與 $\alpha$，其中 $\alpha$ 為 $q$ 的原根
首先是A產生一組公開金鑰的步驟
(1) A選擇一個質數作為他的私密金鑰($X_a$)
(2) $Y_a=\alpha^{X_a} \bmod q$
(3) 最後產生一組$PU=[q, \alpha, Y_a]$
B想要傳送一段Message(M)
(1) B選擇一個隨機數k
(2) $K=(Y_a)^{k} \bmod q$
(3) 則加密後的$M$會有C1, C2

$C_1=\alpha^k \bmod q$
$C_2=KM \bmod q$

Elliptic Curve Cryptography 橢圓曲線密碼學 (ECC)

可以到這個網站上看動態的畫面：https://www.desmos.com/calculator/ialhd71we3?lang=zh-TW

ECC在實數上

$y^2=x^3+ax+b$
設有P,Q兩點位於此橢圓曲線上
則R=P+Q的計算過程：

求 $\lambda$ (PQ之斜率)：$\lambda=(X_Q-X_p)/(Y_Q-Y_P)$
$X_R=\lambda^2-X_p-X_Q$
$Y_R=-Y_p+\lambda(X_p-X_R)$
則$R=(X_R,Y_R)$

2P=P+P的計算過程：

從一開始的橢圓曲線得到a
$X_R=((3(X_p)^2+a)/(2Y_p))^2-2X_p$
$Y_R=(3(X_p)^2+a)/(2Y_p)(X_p-X_R)-Y_p$

找出橢圓曲線上的所有點

$E_p(a,b)$中的p代表mod p
(a,b)代表橢圓曲線中 $y^2=x^3+ax+b$ 的a, b
且我們只關心(0, 0)~(p-1, p-1)範圍的點
因此需要列表找出符合$y^2 \bmod p=x^3+ax+b \bmod p$的$x$與$y$

ECC在有限群上

$E_p(a,b)$
$y^2=x^3+ax+b \bmod p$
設有P,Q兩點位於此橢圓曲線上
則R=P+Q的計算過程：

求 $\lambda$ (PQ之斜率)：
(1)$P\neq Q$：$\lambda=(X_Q-X_P)/(Y_Q-Y_P) \bmod p$
(2)$P=Q$：$\lambda=(3(X_P)^2+a)/2Y_P \bmod p$
$X_R=(\lambda^2-X_p-X_Q) \bmod p$
$Y_R=(\lambda(X_P-X_R)-Y_P) \bmod p$
則$R=(X_R,Y_R)$

2P=P+P的算法與P+Q一樣，但是因為兩點相同，則必須用1.(1)$P\neq Q$的情況算出 $\lambda$

Hash

import hashlib
password='123456'
h=hashlib.md5()
h.update(password.encode())
h.hexdigest()
> 'e10adc3949ba59abbe56e057f20f883e'
8*h.digest_size, 8*h.block_size
> (128, 512)

h=hashlib.sha256()
h.update(password.encode())
h.hexdigest()
> '8d969eef6ecad3c29a3a629280e686cf0c3f5d5a86aff3ca12020c923adc6c92'
8*h.digest_size, 8*h.block_size
> (256, 512)