RSA加密简介

最近在做SICP练习时又复习了一遍RSA加密，趁这个机会对该算法进行小结。

参考资料：

RSA加密系统简介

RSA加密系统由如下元素构成：

发件人$A$使用收件人$B$的公钥$b_{\text{pub}}$对未加密信息$c_0$进行加密，得到加密信息$c_1$；收件人$B$收到加密信息$c_1$后使用自己$b_{\text{pri}}$的私钥进行解码，得到未加密信息$c_0$。

这里有一个问题，收件人B如何判断信息确实来自$A$？RSA加密系统中使用的方法是：

发件人$A$对加密信息$c_1$作用一个哈希函数$f$得到一个较小的数字$f(c_1)=d_0$（称为未加密签名），然后发件人$A$使用自己的私钥$a_{\text{pri}}$对$d_0$进行加密得到$d_1$（称为加密签名），发件人$A$发送的时候同时发送加密信息$c_1$以及加密签名$d_1$。
收件人$B$收到加密信息$c_1$以及加密签名$d_1$后，使用自己的私钥$b_{\text{pri}}$解码$c_1$得到$c_0$，同时利用$A$的公钥$a_{\text{pub}}$解码加密签名$d_1$得到$d_0$，然后判断$f(c_1)$是否等于$d_0$，如果两者相等，则说明确实接收来自于$A$的信息。

完整的流程图：

说明：

在RSA系统中，有两个大质数$p, q$，定义

$\begin{aligned} n &=p q \\ m &=(p-1)(q-1) \end{aligned}$

接着选择数字$e$，使得

$\mathrm{gcd}(e, m)=1$

最后找到$d$，满足

$d e\equiv 1 \bmod m$

说明：使用辗转相除法即可求出$d$和$e$。

公钥为序对

$(n, e)$

私钥为序对

$(n, d)$

对于编码后的信息$s$，公钥加密的信息为

$S\equiv\left(s^{e}\right) \bmod n$

假设收到$S$，利用对应的私钥，解码方式为

$s'\equiv\left(S^{d}\right) \equiv\left(s^{ed}\right)\equiv s \bmod n$

注意由于$p,q$是大质数，所以$n=pq$也是一个非常大的数，从而一般情形下可以得到

$s'=s$

同样的，我们可以使用私钥加密：

$S\equiv\left(s^{d}\right) \bmod n$

此时利用公钥解密：

$s'\equiv\left(S^{e}\right) \equiv\left(s^{de}\right)\equiv s \bmod n$

由于公钥$(n, e)$是公开的，假设我们可以得到分解

$n=pq$

那么可以计算出

$m=(p-1)(q-1)$

通过辗转相除法即可求得

$d e\equiv 1 \bmod m$

从而得到私钥$(n,d)$。

所以问题转化为得到分解

$n=pq$

的时间复杂度。

根据维基百科，对于一个$k$位的整数，目前没有找到多项式时间复杂度的算法进行整数分解，这说明目前阶段RSA加密系统依然是安全的。