RSA 公钥密码系统

在这个章节，我们来讲RSA，之前的密钥系统基于离散对数问题，这次我们整点不一样的。RSA系统是以其发明者 Ron Rivest , Adi Shamir, Leonard Adleman的名字命名的。

RSA密码系统的安全性依赖下述分歧：

  • 设置：令$p,q$是大素数，再令$N = pq$和$e,c$是整数
  • 问题：解关于$x$的同余式子$x^e \equiv c \mod N$
  • 容易性：只要知道$p,q$就能简单的计算出$x$
  • 困难部分：若不清楚$p,q$，就无法找到$x$
  • 分歧： 若不知道一些额外的信息，则很难解决这个问题。

轮到鲍勃和爱丽丝登场了，鲍勃的密钥是一对大素数$p,q$，它们的公钥是一对$(N,e)$，由乘积$N$和一个与$(p-1)(q-1)$互素的加密指数$e$组成。

现在爱丽丝将明文转化为介于$1$到$N$之间的整数$m$，接着通过计算

$\begin{aligned} c \equiv m^e \mod N \end{aligned}$

加密明文。而整数$c$是爱丽丝的密文，接着将其发给鲍勃。那么鲍勃只需简单的求解同余式子$x^e \equiv c \mod N$ 即可恢复爱丽丝的信息$m$，这是因为鲍勃知道因式分解$N = pq$。其次，对于他俩的老对手伊娃，除非他知道如何分解$N$，否则很难解$x^e \equiv c\mod N$

例子

我们使用一个比较小的数字来说明RSA系统的实现，注意的是例子并不安全，因为数字太小，伊娃可以很简单的破解。实际使用中我们一般使用数百位数字的模数$N$

RSA密钥创建：

  1. 鲍勃选择两个私密素数$p = 1223$和$q = 1987$，接着鲍勃计算它们的公开模数
$\begin{aligned} N = pq = 2430101 \end{aligned}$
  1. 接着鲍勃选择一个公开的加密指数$e = 948047$，它满足：
$\begin{aligned} \gcd(e,(p-1)(q-1)) = \gcd (948047,2426892) = 1 \end{aligned}$

RSA加密

  1. 爱丽丝将明文转化为整数
$\begin{aligned} m = 1070777 , 满足 1\leq m < N \end{aligned}$
  1. 爱丽丝使用鲍勃的公钥对$(N,e) = (2430101, 948047)$计算
$\begin{aligned} c\equiv m^e \mod N,~c \equiv 1070777^{948047} \equiv 1473513 \mod 2430101 \end{aligned}$

接着爱丽丝发送密文$c = 14733513$给鲍勃。

RSA解密

  1. 由于鲍勃知道$(p-1)(q-1) = 1222\cdot 1986 = 2426892$，则它可以计算
$\begin{aligned} ed \equiv 1 \mod (p-1)(q-1) \to 948047\cdot d \equiv 1\mod 2426892 \end{aligned}$

那么简单计算可以得知$d = 1051235$

  1. 接着鲍勃将密文$c = 1473513$做计算：
$\begin{aligned} c^d \mod N , 1473513^{1051235}\equiv 1070777\mod 2430101 \end{aligned}$

那么我们就得到了爱丽丝的明文$m = 1070777$了。

注释： 构成鲍勃公钥的值$N,e$分别称为模数和加密指数。而鲍勃用来解密爱丽丝消息的数字$d$满足：

$\begin{aligned} ed\equiv 1\mod (p-1)(q-1) \end{aligned}$

称为解密指数，显然，若$e,d$是较小的，则加/解密可以很简单的得到。但鲍勃不能选择它们都很小，因为一旦确定一个数，另一个数就由模数得到。当然，最重要的是不能取$d=e=1$。这样就没有加密了。

当然，你也不应该取$e=2$，最小可能是$e=3$。如果你担心$e$太小那么我们通常可以用$e = 2^{16}+1 = 65537$，因为我们只需要四次平方和一次乘法即可算的$m^65537$

另一方面，若我们让鲍勃选择较小的$d$，则同余式给出一个很大的$e$。然而若$d$小于$N^{1/4}$，则使用连分数定理可以让伊娃破解RSA。

鲍勃的公钥包含数字$N = pq$，它是两个秘密素数$pq$的乘积，若伊娃知道$(p-1)(q-1)$的值，则能够简单的解得$x^e \equiv c\mod N$。从而得到明文。

我们展开$(p-1)(q-1)$就有：

$\begin{aligned} (p-1)(q-1) = pq-p-q+1 = N-(p+q)+1 \end{aligned}$

由于$N$是公开的，所以伊娃知道$N$，因此我们只需要确定$p+q$是什么就可以得到$p,q$了。若伊娃知道$p+q$和$pq$，则我们只需要使用二次公式来找到多项式的根即可：

$\begin{aligned} x^2 -(p+q)x+pq \end{aligned}$

那么该二次公式可以分解为$(x-q)(x-q)$。所以它的两个根就是$p,q$。

例子

我们举一个例子说明，若伊娃知道$N = pq = 66240912547$和$(p-1)(q-1) = 66240396760$。

首先我们知道$p+q = N+1 - (p-1)(q-1) = 515788$

其次，利用二次公式有：

$\begin{aligned} x^2 -(p+q)X +N = x^2 - 515788x+66240912547 = (x-241511)(x-274277) \end{aligned}$

实施和安全性问题

接下来我们提及一些安全方面的事实。我们不仅仅只讲密码学背后的数学原理，这样子远远不够。

中间人攻击（Woman-in-the-Middle Attack）

假设伊娃不仅仅是一个窃听者，它还完全控制着爱丽丝和鲍勃的通信网络。在这种情况下可以发起所谓的中间人攻击。

设想一下，在$D-H$密钥交换中，爱丽丝给鲍勃发送值$A = g^a$。而鲍勃给爱丽丝发送$B = g^b$，而且计算都是在有限域$F_p$中进行的。而现在，由于伊娃控制它们的通信网络，首先伊娃给自己指定了一个指数$e$计算$E = g^e$。接着拦截了爱丽丝和鲍勃的通讯，接着伊娃给他们发送了数字E。注意这时候爱丽丝和鲍勃它们通讯是失败的，并没有收到对方的消息而是$E$。

设爱丽丝和鲍勃随后使用它们假定的密钥作为对称密码的密钥并互相发送消息，例如爱丽丝使用$E^a$加密消息$m$，则伊娃截获后可以用$A^e$作为密钥解密他，因此可以得到爱丽丝的信息。然后它使用$B^e$作为密钥重新发送给鲍勃。最后，因为鲍勃可以使用$E^b$解密，所以他不知道存在安全漏洞。

这个攻击的阴险之处在于，伊娃并没有破解密码，而是可以成功的读取爱丽丝和鲍勃的通讯而它们不知道他的成功。

被截获了密文

若爱丽丝发布了两个不同的指数$e_1,e_2$用于它的公开模数$N$，而鲍勃使用了爱丽丝的两个指数加密明文$m$。若被伊娃截获密文。那么

$\begin{aligned} c_1 \equiv m^{e_1} \mod N 和 c_2\equiv m^{e_2} \mod N \end{aligned}$

那么我们可以选择两个数，计算$u,v$

$\begin{aligned} e_1\cdot u +e_2\cdot v = \gcd(e_1,e_2) \end{aligned}$

然后用$u,v$计算：

$\begin{aligned} e_1^u\cdot e^v_2 \equiv (m^e_1)^u\cdot (m^{e_2})^v \equiv m^{e_1\cdot u +e_2\cdot v} = m^{\gcd(e_1,e_2)} \mod N \end{aligned}$

若$\gcd(e_1,e_2) =1$，则直接恢复明文。更一般的，若存在多个互素的指数$e_1,\cdots ,e_n$使得$\gcd(e_1,\cdots,e_n)=1$，则我们可以恢复明文。