从对称加密算法到非对称加密算法

对称加密算法：信息的收发方会通过事先商定好的密钥对数据加密和解密。这种加密算法会导致

• 每两个人相互交流就需要一个密钥，随着用户增多，密钥管理愈加困难。
• 网络传输密钥也需要加密，而没有密钥则无法解密，所以密钥必须通过见面协商。

非对称加密算法：用不同的密钥对数据进行加密和解密，加密的密钥（公钥）是公开的，而解密的密钥（私钥）仅接收者持有。

模运算 Modular Arithmetic

由于模运算（取余运算）正向计算非常容易，且不可逆的特性，我们可以保证用公钥加密之后的明文不会被轻易破解。

考虑算式 3 3   %   7 3^3\ \%\ 7 33 % 7，可以很容易得出答案为6。而已知 3 x   %   7 = 6 3^x\ \%\ 7=6 3x % 7=6时，反向推算 x x x就只能逐一代入验证了。鉴于此例数量级较小，还是很容易就可以推算出答案。

而如果改为 3 x   %   984426289703667782113631386235633223212587 = 6 3^x\ \%\ 984426289703667782113631386235633223212587=6 3x % 984426289703667782113631386235633223212587=6，再一一尝试就不太现实了。因为有对大数来说求模运算非常困难的特性，模运算也被冠以“单向函数”（One-way Function）之名。

RSA公钥加密算法

假设要加密的信息为m (message)，对其求 e 次幂，此处 e (encrypt)代表加密用的公钥。随后对N取模，得到密文c (cipher)：
m e m o d    N = c m^e\mod N=c memodN=c
显然，由m得到c的正向计算很简单，但由c推算m是非常困难的。
解密的过程与加密类似：
c d m o d    N = m c^d\mod N=m cdmodN=m
其中d (decrypt)代表解密用的私钥。

将两个式子合并，得
m e d m o d    N = m m^{ed}\mod N=m medmodN=m

到此为止，问题变为如何选取合适的 e 和 d 。

欧拉定理(Euler’s theorem)：
m，n互质时，取m的 ϕ ( n ) \phi(n) ϕ(n)次方，并对n取余数，结果恒等于1，即：
m ϕ ( n ) ≡ 1   ( m o d   n ) m^{\phi(n)}\equiv 1\ (mod\ n) mϕ(n)≡1 (mod n)
其中， ϕ ( n ) \phi(n) ϕ(n)为欧拉函数，它代表小于等于n的数中，有几个数与n互质，例如 ϕ ( 6 ) = 2 \phi(6)=2 ϕ(6)=2。

对 m ϕ ( N ) m o d    n = 1 m^{\phi(N)}\mod n= 1 mϕ(N)modn=1等式两端同取k次幂，并乘以m，可以写成
m k ϕ ( N ) + 1 m o d    N = m m^{k\phi(N)+1}\mod N = m mkϕ(N)+1modN=m

经过变换，这个式子形式上与上面的 m e d m o d    N = m m^{ed}\mod N = m medmodN=m 相同，可以得到
e d = k ϕ ( N ) + 1 ed=k\phi(N)+1 ed=kϕ(N)+1

将e移到式子右边，得：
d = k ϕ ( N ) + 1 e d=\frac{k\phi(N)+1}{e} d=ekϕ(N)+1​

所以我们可以通过选取此处k、N、e的值来确定私钥d。

问题在于 ϕ ( n ) \phi(n) ϕ(n)的计算是十分困难的。它只能够根据定义计算，即对n做质因数分解。而对上百位的大数做质因数分解几乎可以看做计算上不可行的(computational infeasible)。但如果n本身就是一个质数，我们可以很容易得到 ϕ ( n ) = n − 1 \phi(n)=n-1 ϕ(n)=n−1。即n只与自己存在非1公因数。

且 ϕ ( n ) \phi(n) ϕ(n)还有一个重要的性质：积性函数。即对任意互质的数p, q，总有 ϕ ( p ∗ q ) = ϕ ( p ) ∗ ϕ ( q ) \phi(p*q)=\phi(p)*\phi(q) ϕ(p∗q)=ϕ(p)∗ϕ(q)。例如选取 p = 17   q = 23 p=17\ q=23 p=17 q=23，就有 ϕ ( 17 ∗ 23 ) = ϕ ( 17 ) ∗ ϕ ( 23 ) = 16 ∗ 22 \phi(17*23)=\phi(17)*\phi(23)=16*22 ϕ(17∗23)=ϕ(17)∗ϕ(23)=16∗22，也即 ϕ ( 391 ) = 352 \phi(391)=352 ϕ(391)=352。

例如我们选取 k = 5 N = 391 e = 3 k=5\quad N=391\quad e=3 k=5N=391e=3（e应选与 ϕ ( N ) \phi(N) ϕ(N)互质的数，而k的选取较为随意，保证d为整数即可），代入上式，得 d = 5 ∗ 352 + 2 3 = 587 d=\frac{5*352+2}{3}=587 d=35∗352+2​=587
计算出d后，我们就不再需要p和q，将e和N作为加密的公钥(public key)公布，而d作为解密的私钥(private key)。

其他人因为不知道p，q两个互质数，无法计算出 ϕ ( N ) \phi(N) ϕ(N)，也就无法破解私钥d

举例

利用上面得到的参数，加密字符’a’(ascii编码97)
加密： 9 7 3 m o d    391 = 79 97^3\mod 391=79 973mod391=79
解密： 7 9 587 m o d    391 = 97 79^{587} \mod 391=97 79587mod391=97
成功解密字符a

参考 reference

https://www.bilibili.com/video/BV14y4y1272w