在一些关于谍战卧底的影视作品中，常常可以看到一些传递关键情报的紧张镜头，受环境所限，通常他们都是用文字传递，比如周星驰电影
《国产凌凌漆》
里的接头情报就这样（是不是有点浪漫）：
可实际上，这种一目了然的情报一旦被敌方截获，是非常危险的。比如，在现代战争中，几乎绝不可能用这种冒险而缓慢的方式传递情报。那么，有没有比较安全的方式来传递情报呢？
确实有的，而且几乎你每天都在用，比如你在用支付宝，微信、银行卡，邮箱时，用密码登录就是相对安全的（前提是别人不知道你的密码）。这个安全性依赖于著名的
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
从中不难拼出汉字
六点北校打排球
这就是一开头我想要传递的信息。
请注意，我们上面走过的整个过程
汉字→拼音→数字→加密数字→ 发送/接收→解密数字→拼音→汉字
