密码篇・公开密钥加密

维基百科: 公开密钥密码学（英语：Public-key cryptography）也称非对称式密码学（英语：Asymmetric cryptography）是密码学的一种算法，它需要两个密钥，一个是公开密钥，另一个是私有密钥；公钥用作加密，私钥则用作解密。使用公钥把明文加密后所得的密文，只能用相对应的私钥才能解密并得到原本的明文，最初用来加密的公钥不能用作解密。

对称加密的密钥发送问题

如果用之前提到的对称加密算法传递数据，因为加密和解密使用的是同一个密钥，所以双方必须先传递这把密钥才能在加密的情况下进行信息交流。但是如果密钥在传递过程中被窃取就会出现泄密。

为了能够安全传递密钥有人进行了一个设想: 我们可以做出两把密钥，一把用于加密但是不能解密，一把用于解密但是不能用于加密，同时加密用的密钥不能推导出解密用的密钥，那么我们就可以只发送那把加密用的密钥给对方，自己存留解密用的密钥，这样我们就可以确保不会因为分发密钥时密钥被窃取而导致加密信息被泄漏。由于过程中存在可以被公开使用的密钥因此这种加密方式也被称为“公开密钥加密”。其中，公开使用的密钥称为“公钥”；不被公开使用的密钥称为“私钥”。

在数学上可以表示为: $d(c(x))=x$，让我们使用典型的爱丽丝与鲍伯假设来解释：

爱丽丝与鲍伯事先互不认识，也没有可靠安全的沟通渠道，但爱丽丝现在却要透过不安全的互联网向鲍伯发送信息
爱丽丝撰写好原文，原文在未加密的状态下称之为明文$x$
鲍伯使用“密码学安全伪随机数生成器”产生一对密钥，其中一个作为公钥为$c$，另一个作为私钥$d$
鲍伯可以用任何方法发送公钥$c$给爱丽丝，即使伊夫在中间窃听到$c$也没问题
爱丽丝用公钥$c$把明文$x$进行加密，得到密文$c(x)$
爱丽丝可以用任何方法传输密文$c(x)$给鲍伯，即使伊夫在中间窃听到密文$c(x)$也没问题
鲍伯收到密文，用私钥$d$对密文进行解密$d(c(x))$得到爱丽丝撰写的明文$x$
由于伊夫没有得到鲍伯的私钥$d$，所以无法得知明文$x$
如果爱丽丝丢失了她自己撰写的原文$x$，在没有得到鲍伯的私钥$d$的情况下，她的处境将等同伊夫，即无法透过鲍伯的公钥$c$和密文$c(x)$重新得到原文$x$

RSA算法

RSA算法就是公开密钥加密设想的一种实现方法，RAS算法通过巧妙的利用质因数拆解难题构造出公钥和私钥来实现公开密钥加密。

给定两个非常大质数$p,q$，我们可以很容易得到他们乘积$m = p \times q$，然而我们只知道$m$由两个质数相乘得到却很难得出$p,q$的确切值:

$$ \begin{align} 简单: p,q \rightarrow m = p \times q \\ 困难: p,q \leftarrow m = p \times q \end{align} $$

有了质因数的这个性质后我们还需要通过一个运算方法将其应用到实际操作中，“取模”就是一个不错的选项，即给定两个整数$a,n$可以相除得到余数$b$，数学上可以表示为:

$$ a \equiv b \ (mod \ n) $$

在取模操作中有一个比较有趣的现象，我们若知道$a,n$就可以准确推出$b$，然而若只知道$b,n$却无法准确推出$a$。

$$ 6 \equiv 1 (mod \ 7) \text{ ; } 15 \equiv 1 (mod \ 7) \text{ ; } 22 \equiv 1 (mod \ 7) \text{ …} $$

有了质因数性质和取模运算，那么接下来我们就可以构建出公钥和私钥:

$$ \begin{align} p,q & \quad 随机生成两个不相等的大质数p,q \tag 1 \\ N = p \times q & \quad 计算p,q的乘积N \tag 2 \\ \Phi(N) = (p - 1)(q - 1) & \quad 计算欧拉函数\Phi(N) \tag 3 \\ e \in gcd(e,\Phi(N)) = 1 & \quad 取与\Phi(N)互质且小于\Phi(N)的自然数e \tag 4 \\ ex + \Phi y = 1 & \quad 由e,\Phi(N)互质可以构建方程并求整数解x,y \tag 5 \end{align} $$

$$ (N,e)\ 将被作为公钥；(N,x)\ 则作为私钥使用 $$

Note! 1. 方程式(3)中提到的欧拉函数$\Phi(n)$是指小于或等于$n$的正整数中与$n$互质的数的数目，例如$\Phi(8) = 4$，因为1,3,5,7均和8互质；2. 方程式(5)可以用扩展欧几里得算法进行求解「感兴趣的朋友可以自己搜索了解扩展欧几里得算法的相关知识」。

有了公钥$(N,e)$以及私钥$(N,x)$后我们就可以对数据进行加密与解密的操作:

$$ \begin{align} A & \quad 将数字A作为需要加密的明文 \tag 6 \\ A^e \equiv R (mod \ N) & \quad 计算A的e次方并除N得到余数R，R\ 即为密文 \tag 7 \\ R^x \equiv A (mod \ N) & \quad 计算R的x次方并除N得到余数A，A\ 即为明文 \tag 8 \end{align} $$

Note! 关于运算式(7)、(8)为什么可以互相逆转可以使用费马小定理进行证明，感兴趣的朋友也可以搜索相关资料进行扩展学习。

下面我们用一组比较简单的数据来验证一下上述方法:

取质数$p = 5, q = 11$，求得$N = p \times q = 55$；
计算欧拉函数$\Phi(N) = (p - 1)(q - 1) = 40$；
取$e = 17$，满足$e \in gcd(e,\Phi(N)) = 1$；
当$x = 33,y = -14$时方程$ex + \Phi y = 1$成立；
$(55,17)$作为公钥；$(55,33)$作为私钥；
有数字14作为明文$A$，「注意确保$A$小于$N$」；
加密明文$A=14$得到密文$14^{17} \equiv 9 (mod \ 55) \Rightarrow R = 9$；
解密密文$R=9$得到明文$9^{33} \equiv 14 (mod \ 55) \Rightarrow A = 14$；

使用Python代码进行测试:

p, q = 5, 11
N = p * q
Phi = (p - 1) * (q - 1)
e = 17
x, y = 33, -14
print('ex + Phi(N)y =', e * x + Phi * y)
print('公钥:', (N, e), '私钥:', (N, x))
A = int(input('明文: ').strip())
R = A**e % N
_A = R**x % N
print('加密&解密: {} -> {} -> {}'.format(A, R, _A))

运行效果:

ex + Phi(N)y = 1
公钥: (55, 17) 私钥: (55, 33)
明文: 14
加密&解密: 14 -> 9 -> 14

实际上公钥加密算法的类型也有很多种，而RSA只是利用质因数分解特性的一种方法，除此之外还有Rabin等利用质因数分解特性的公钥加密算法；另外还有根据离散对数问题设计的公钥加密算法，例如: 椭圆曲线加密算法、ElGamal加密算法……

下篇密码篇・实际应用