林开亮

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

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

确实有的，而且几乎你每天都在用，比如你在用支付宝，微信、银行卡，邮箱时，用密码登录就是相对安全的（前提是别人不知道你的密码）。这个安全性依赖于著名的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 Adleman1978年（恰好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加密函数就是 $$E ( x ) = E _ { m , k } ( x ) = x ^ { k } \pmod{m}\tag{1}$$ 注意，这里取最小正剩余。简单地说，这个加密函数就是对自变量$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

我们标记为 $$ \begin{aligned} 221931 ^ { 5 } & \equiv 3188615   \pmod{4088459} \\ 141911 ^ { 5 } & \equiv 3342219  \pmod{4088459} \\ 241215 ^ { 5 } & \equiv 2262164  \pmod{4088459} \\ 193419 ^ { 5 } & \equiv 1266684  \pmod{4088459} \\ 112514 ^ { 5 } & \equiv 3169145  \pmod{4088459}\\ 112611 ^ { 5 } & \equiv 0892482   \pmod{4088459} \\ 192719 ^ { 5 } & \equiv 2320876  \pmod{4088459} \\ 31 ^ { 5 } & \equiv 0009938   \pmod{4088459} \end{aligned} $$ 现在我们依次计算出这些数字经过RSA函数(1)加密之后得到的各个数（其实我是用软件算的）

RSA 解密算法 （如何计算模$m$的$K$次根）。
设$b, k , m$是给定的整数，满足 $$\gcd(b, m) = 1\text{ 且 }\gcd(k ,\phi ( m )) = 1$$ 下述步骤给出同余式 $$x ^ { k } \equiv b \pmod{m}\tag{2} $$ 的解。

Step 1。 计算¢(m) . (参见No . 3 ,在已知m 的素因子 时很容易计算）
Step 2。 用求一术（参见No.2) 解关于u 的同余方程
$$k u \equiv 1 \pmod {\phi ( m ) }$$ Step 3。$x = b^u \pmod { m}$ (如果必要，用逐次平方 法计算）

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

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

证明： 我们来验证$x=b^u$满足同余方程(2) 如下： $$ \begin{aligned} x ^ { k } & = \left( b ^ { u } \right) ^ { k } \\ & = b ^ { u k } \\  & = b ^ { 1 + \phi ( m ) v } \quad \text{（根据 Step2 的结果，$k u - 1 = \phi ( m ) v$）}\\  & = b \cdot \left( b ^ { \phi ( m ) } \right) \\  & \equiv b \cdot 1 ^ { v } \pmod{m} \text{（由欧拉定理，$b ^ { \phi ( m ) } \equiv 1 \pmod{m}$）}\\  & \equiv b \pmod{ m}  \end{aligned} $$

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

其中$b$依次取
3188615， 3342219， 2262164 ，1266684 ，3169145， 892482， 2320876 ，9938

这八个（接收到的）数字，我们依次记为    $$b _ { 1 } , \dots , b _ { 8 }$$

要还原我想传递的信息，你就要对$i=1,2,3,4,5,6,7,8$求解方程    $$x ^ { 5 } \equiv b_i \pmod{4088459}\tag{4}$$

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

问题： 求同余式 $$x ^ { k } \equiv 3188615 \pmod{4088459}\tag{5}$$ 的解。

解：Step 1, 由于已知$m = 2017\cdot 2027$, 从而容易计算出中$\phi(m) = 2016\cdot 2026 = 4084416$
Step 2, 用求一术解关于$u$的同余方程 $$5 u \equiv 1 \quad ( \bmod 4084416 )$$ 过程从略（可以用软件），答案是 $$u = - 816883 + 4084416 k , \quad k \in \mathbb { Z }$$ 为得到一个特殊解，比如，可取最小正解 $$u = 3267533$$ Step 3, (也可以用软件）计算 $$x = 3188615 ^ { 3267333 } \pmod{4088459} = 221931$$ 这恰好就是我想传递的信息$x_1$
类似地，可以求出$b _ { 2 } , \ldots , b _ { 8 }$处所对应的信息依次为 $$ \begin{aligned} 3342219 ^ { 3267533 } & \pmod{4088459} = 141911 = x _ { 2 } \\ 2262164 ^ { 3267533 } & \pmod{4088459} = 241215 = x _ { 3 }  \\ 1266684 ^ { 3267533 } & \pmod{4088459} = 193419 = x _ { 4 }\\ 3169145 ^ { 3267333 } & \pmod{4088459} = 112514 = x _ { 5 } \\ 892482 ^ { 3267333 } & \pmod{4088459} = 112611 = x _ { 6 } \\ 2320876 ^ { 3267533 } & \pmod{4088459} = 192719 = x _ { 7 }\\ 9938 ^ { 327533 } & \pmod{4088459} = 31 = x _ { 8 } \end{aligned} $$

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

221931 141911 241215 193419 112514 112611 192719 31

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

liudianbeixiaodapaiqiu

从中不难拼出汉字

六点北校打排球

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

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

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

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

另一方面，如果你不是我方同志（从而不知道$m$的素因子分解），但你截取了我传送的情报    $$b _ { 1 } , \dots , b _ { 8 }$$

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

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

有之以为利，无之以为用。

致谢：本文的计算应用了http://www.wolframalpha.com/ ，特表感谢。对这个软件创始人Wolfram的一个介绍，可见和乐数学的推送文章

教孩子真正的数学|数学软件创始人Wolfram

延伸阅读：

1. J. H. Silverman，《数论概论》（第4版），孙智伟等译，机械工业出版社，2016年。

2. 大栗博司，《用数学的语言看世界》，尤斌斌译，人民邮电出版社，2017年。

3. Susan Loepp, William K. Wootters, 《信息保护：从经典纠错到量子密码》，吕欣等译，电子工业出版社，2008年。

4. 求一术与方程术

5. 欧拉定理

6. 教你一招第3期（化非齐次常系数线性微分方程为代数同余方程）