一周一定理No.4 RSA解密算法

Original 林开亮好玩的数学 2023-05-03

在一些关于谍战卧底的影视作品中，常常可以看到一些传递关键情报的紧张镜头，受环境所限，通常他们都是用文字传递，比如周星驰电影《国产凌凌漆》里的接头情报就这样（是不是有点浪漫）：

可实际上，这种一目了然的情报一旦被敌方截获，是非常危险的。比如，在现代战争中，几乎绝不可能用这种冒险而缓慢的方式传递情报。那么，有没有比较安全的方式来传递情报呢？

确实有的，而且几乎你每天都在用，比如你在用支付宝，微信、银行卡，邮箱时，用密码登录就是相对安全的（前提是别人不知道你的密码）。这个安全性依赖于著名的RSA加密。

今天，我们就来介绍这个简单而有效的公钥密码机制，只需要一点点的初等数论就可以把RSA讲清楚。而且，由于我们在第2期和第3期已经分别介绍了求一术和欧拉定理，RSA早就是呼之欲出了（心有灵犀的读者也早就想到了RSA与欧拉定理的关联，已经有两次留言提到了RSA）！

首先，为了不直接传递文字，我们需要建立文字与数字（这就是坐标）的一一对应（一个字典），这一点是很容易办到的，我们可以26个拉丁字母

a, b, c, d, ……，x, y, z

依次对应于数字

11，12，13，14，……，34， 35，36

为了下面给出一个完整的例子，这里我们给出整个文字——数字字典如下：

有了这个字典，我们就可以不用传递文字(words)，而改为传递数字(numbers)了。例如，我要传递一个信息

六点北校打排球

可以用朴素的方式，先化成汉语拼音（请原谅我英文不好，不过可以想见，汉语拼音比英文更有效），这就转化成下述拉丁文字

liu dian bei xiao da pai qiu

进一步转化成数字就得到：

221931 14191124 121519 34191125 1411 261119 271931 (*)

为保证信息不易被人识破，我们要进一步这些数字进行加密（Encryption），然后再传递出去。这个加密，通常用一个函数（函数，即数字到数字的映射）来实现，一个方便（是指对加密和解密都方便）的函数是由MIT计算机科学实验室与数学系的三位学者Ron Rivest, Adi Shamir和Leonard Adleman 1978年（恰好40年）提出的，很简单。由于他们姓氏的首字母分别为R，S，A，所以这个加密简称为RSA加密。

从左到右：Adi Shamir，Ron Rivest，Leonard Adleman

RSA建议，选取两个不同的素数 p,q, 令 m=pq是它们的乘积，再选取一个与φ(m)=(p-1)(q-1)互素的正整数k, 那么由参数m, k给出的RSA加密函数就是

注意，这里取最小正剩余。简单地说，这个加密函数就是对自变量x在模m的意义下取k次幂。通常来说，k次幂会迅速变得很大从而很难计算（主要是存储引起的困难），但在模m的意义下，它始终在一个有限范围，而且有一个很简单的算法（逐次平方法，参见[1]第16章)，让计算机来处理这个事情最好不过。

比如说，如果我们选取 p=2017, q=2027, 那么m=p*q=2017*2027=4088459，

φ(m)=(p-1)(q-1)=2016*2026= 4084416，从而若我们选取k=5，即可保证它与

φ(m)互素。

现在我们来利用由（1）(其中m,k如上选取）对(*)这一串数字加密，我们这样操作，由于现在m=4088459是一个七位数，我们将(*)中的数字划分为6位数，从而（*）中的数字分成了以下8个数字（最后一个是两位数，不过没关系）：

221931， 141911，241215，193419，112514，112611，192719，31

我们标记为

现在我们依次计算出这些数字经过RSA函数(1)加密之后得到的各个数（其实我是用软件算的）

从而我们就得到加密之后的信息如下：

3188615 3342219 2262164 1266684 3169145 0892482 2320876 0009938

这些数字就是接收方（比如说红方或间谍）接收到的信息。显然，要读出发送方（比如说蓝方或同志）本身要传递的信息，就需要解密（Decryption）。

简单地说，解密——即破解密码，就是要求出加密函数的反函数（因此，本质上，前面用到的加密函数不能随便选，至少要保证是单射，否则解密会有麻烦——因为，若加密函数是多对一的，其反函数就是一对多，难免有歧义）。特别地，对RSA解密，就是要求出RSA函数(1)的反函数，换言之，就是要在模m意义下对一个整数开k次方。这个问题怎么解决呢？RSA指出，有一个漂亮的算法，它本质上就是求一术。为提醒你这是一个定理专栏，我们把它写成一个定理（见[1]第17章算法17.1):

注：与这个算法精神一致的，是求解常系数线性微分方程的一个代数方法，见教你一招第3期（化非齐次常系数线性微分方程为代数同余方程）。本质上，这里存在着从整数到多项式的一个类比，我们将在以后某一期详细展开。

由于我们之前做好了铺垫，所以这个定理(毋宁说是算法）的证明写起来也非常简洁的，我们一并抄过来，如下：

根据上述算法，我们很容易对RSA解密，只要我们能够求出Step1的φ(m)。假如，你是蓝方（我方）的同志，你不仅知道m, 而且知道m=pq是两个不同素数p,q的乘积，那么φ(m)=φ(p)φ(q)=(p-1)(q-1)自然就知道了，而接下来的Step2与Step3是非常简单的。比如，接着前面的例子，你现在知道p=2017,q=2027,k=5, 那么你要解的方程就是

其中b依次取

3188615， 3342219， 2262164 ，1266684 ，3169145， 892482， 2320876 ，9938

这八个（接收到的）数字，我们依次记为

要还原我想传递的信息，你就要对i=1,2,3,4,5,6,7,8求解方程

下面我们就来实践一下RSA解密算法：

于是，我们就得到了原始的信息

221931 141911 241215 193419 112514 112611 192719 31

利用文字——数字字典，可以将这一信息还原为

liudianbeixiaodapaiqiu

从中不难拼出汉字

六点北校打排球

这就是一开头我想要传递的信息。

请注意，我们上面走过的整个过程

汉字→拼音→数字→加密数字→ 发送/接收→解密数字→拼音→汉字

都可以用简单的算法实现，因此全部可以交给计算机。这就是为什么你在生活中处处在应用加密解密，却没有觉察到的原因所在。你只需要输入初始的数据就可以了，后面的步骤都由设计好的程序来完成了！

另一方面，如果你不是我方同志（从而不知道m的素因子分解），但你截取了我传送的情报

那么，即便我公开 m 与 k 的值，你可能也无法破译密码。

原因在于，RSA解密的第一步是求出φ(m)。而对一个很大的数m，按定义来计算其欧拉函数φ(m)是不切实际的，对计算机来说也是如此。你要求出φ(m)，就需要知道m的素因子分解，而至今都没有发现将一个大数做素因子分解的有效算法（至少对经典的计算机是如此，对量子计算机虽然存在有效的算法，但其硬件——量子计算机——本身都还在起步阶段）。正是这一点，保证了RSA密码的安全性。推而广之，任何其他的加密函数（参见[3])都可以用，只要能确保其解密很困难（从而保证其安全）。这个思路似乎很好地诠释了老子的名言：