经典非对称加密算法：RSA
单向函数（One-way Function）
对于每一个输入，函数值都容易计算（多项式时间）；但是对于一个随机的函数值，算出其对应的输入却比较困难（无法在多项式时间内使用确定性图灵机计算）。
最简单的单向函数是取模运算：m mod n = a
例如 11 mod 2 = 1 ，根据输入的数据11很容易知道输出结果是1，但是根据输出结果1无法知道输入数据是什么
m 作为原文，n 作为公开的密钥，a 作为加密后的密文 —— 即使我们拿到了密钥也无法解密，因为这是不可逆的
密码学的新方向 —— 单向陷门函数（One-way Trapdoor Function）
单项陷门函数是有一个陷门的一类特殊单向函数。单项陷门函数包含两个明显特征：一是单向性，二是存在陷门。
单向函数存在 bug（陷门）吗？即可以实现单向函数的逆推。如果存在一种单向算法存在陷门，那么可以将这个算法称为单向陷门函数（One-way Trapdoor Function）
在1976年 W. Diffie 和 M. Hellman 提出了这样的美好设想：
信息的接收者提前生成两个密钥，将一个单项陷门函数作为加密密钥公开发布（即公钥），信息的发送者使用公钥加密信息，信息的接收者自己保留的解密密钥（即私钥）就是这个单项陷门函数的陷门，接收者可以使用私钥解密加密后的密文
密文可以被截获，但窃密者不持有私钥，无法解密密文。私钥永远在接收者手里，这样就没有了发送密钥被截获的风险
自此，密码学有了新的方向 —— 公钥密码，加解密的不对称也被称为非对称密码
之所以在前文说这是 Diffie 和 Hellman 的美好设想，是因为 Diffie 和 Hellman 并没有找到合适的单向陷门函数……
RSA加密算法
R. L. Rivest、A. Shamir 和 L. Adleman 三人在1978年发布了一篇题为《A Method for Obtaining Digital Signatures and Public-key Cryptosystems》的论文，他们在论文中描述了一种以他们名字命名的加密算法 —— RSA
如果对于给定的乘方取模运算 \(m^e\ mod\ n\ =c\)，其中 m 作为原文、c 作为加密后的密文、而密钥则变成了 e 和 n，那么可以使用逆运算
\(c^d\ mod\ n\ =\ m\) 来还原出原始的 m。即 d 是这个乘方取模运算中的陷门。
公钥: ( e , n )，私钥: ( d , n )
试试把加密公式带入解密公式： \[ \left( m^e\ mod\ n \right) ^d\ mod\ n\ =\ m \]
\[ m^{ed}\ mod\ n\ =\ m \]
这与同乘以 m 的欧拉定理一样：\(m^{\phi \left( n \right) +1}\ =\ m\ \left( mod\ n \right)\) 。显然满足 \(\phi \left( n \right) +1=ed\)
那么陷门 \(d\ =\ \frac{\phi \left( n \right) +1}{e}\)
ϕ(n)是欧拉函数，它表示小于等于 n 且与 n 互质的正整数的个数，可以写成 \(\left( p-1 \right) \cdot \left( q-1 \right)\)，证明如下：
由于 \(n=p\times q\)（p、q互质），\(∀a∈\left\{ p,2p,3p,...,p\left( q-1 \right) \right\}\) 均被 p 整除，\(n=p\times q\)，故 \(gcd\left( b,n \right) ≠1\)
由于 \(n=p\times q\)（p、q互质），\(∀b∈\left\{ p,2p,3p,...,p\left( q-1 \right) \right\}\) 均被 q 整除，\(n=p\times q\)，故 \(gcd\left( a,n \right) ≠1\)
那么小于n且与n互质的数为: \(\left( n-1 \right) -\left( p-1 \right) -\left( q-1 \right) =\left( p\cdot q-1 \right) -\left( p-1 \right) -\left( q-1 \right) =\left( p-1 \right) \cdot \left( q-1 \right)\)
欧拉定理的证明如下：
取 \(\forall c\) ，c < n，\(c\in \left\{ a_1,a_2,\cdots ,a_{\phi \left( n \right)} \right\}\)
对于 \(\forall a_i\) ，均有 \(c\cdot a_i\equiv a_j\left( mod\ n \right)\) （c、ai均与 n 互质）
对于集合 \(\left\{ a_1,a_2,\cdots ,a_{\phi \left( n \right)} \right\}\) 有：\(\prod_{k=1}^{\phi \left( n \right)}{c\cdot a_k=\prod_{k=1}^{\phi \left( n \right)}{a_k\left( mod\ n \right)}}\)
即 \(c^{\phi \left( n \right)}\cdot \prod_{k=1}^{\phi \left( n \right)}{a_k=\prod_{k=1}^{\phi \left( n \right)}{a_k\left( mod\ n \right)}}\) 等式两边同时约去 \(\prod_{k=1}^{\phi \left( n \right)}{a_k}\) 得证：
\(c^{\phi \left( n \right)}\equiv 1\left( mod\ n \right)\)
我们知道欧拉函数的定义是基于正整数的质因数分解，而质因数分解是唯一的，所以所有正整数 n 的欧拉函数 ϕ(n) 都是整数
但是，d 就不一定了，如果 n=34，e=15，算出来的 d=7/3，这对取模运算没有意义
回到欧拉公式，根据取模运算的性质 —— 等式左边 k 个 \(m^{\phi \left( n \right)}\) 相乘等式也成立，
即 \(\left( m^{\phi \left( n \right)} \right) ^k\ =\ 1\ \left( mod\ n \right)\) ，根据上面的过程进一步可以得到 \(d\ =\ \frac{k\phi \left( n \right) +1}{e}\)
通过选择 k 的值，就可以得到正整数的 d，例如刚刚的 n=34,e=15：
1 | k=1 d=3/7 k=4 d=3/13 |
可以找到 k=14 时 d=15，但是 k=29 时 d 也为正整数，这应该怎么选择？习惯性选择最小的正整数作为 d 的取值
通常采用扩展欧几里得算法算法来快速计算符合条件的 k
公钥 e 和 n 都是公开的，应该如何防止其他人计算出私钥 d？
当 n 很小的时候很容易算出 ϕ(n)，当 n 为一个很大的数时就很难计算了，例如下面这个 n：
1 | n = 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199 |
由信息的接收者选取 p,q 和 e，将这两个大质数相乘得到 n，
选取一个合适的 k 使用 \(d=\frac{k\phi \left( n \right) +1}{e}\) 计算得到私钥 d。
接收者发布 e 和 n 作为公钥，信息的发送者要发送信息 m 需要使用公钥通过 \(m^e\ mod\ n=c\) 对信息进行加密得到密文 c，
接收者接到密文 c 使用私钥通过 \(c^d mod\ n=m\) 即可还原原文 n。
而窃密者即使截获了密文也无法通过将 n 分解成 p,q，无法计算得出私钥
Reference
[1] Rose-Hulman Scholar . https://scholar.rose-hulman.edu/cgi/viewcontent.cgi?article=1081&context=rhumj