“不给力啊，老湿！”：RSA加密与破解

RSA原理

发觉自己被愚弄了，厨子很生气，后果很 严重。厨子发奋看了书，知道了这个加密方法叫RSA，是三为发明人 R. Rivest, A. Shamir和L. Adelman名字首字母合起来的。RSA算法是1977年发明的。全称是RSA Public Key System。这个"Public Key"是公共密钥，也就是我们上面说的锁。再读下去，厨子大窘。这个1977年的，现代计算机加密的RSA算法，居然源于17世纪。

1. 费马小定律

RSA的原理借助了数论中的“欧拉定理”(Euler's theorem)。17世纪的费马首先给出一个该定理的特殊形式，即“费马小定理”：

p是一个正的质数，a是任意一个不能被p整除的整数。那么，ap−1−1能被p整除。

我们并不需要太深入了解费马小定理，因为等下就会看到这个定理的“升级版”。但这个定理依然很美妙，它优美的得到乘方和整除的某种特殊关系。使用一个例子来说明它。比如p=7，a=3。那么费马小定律表示，37−1−1可以被7整除。

事实上，上面的数字计算得到36−1=728，它确实可以被7整除。

练习：尝试一个其它的例子，比如p=5，a=4，验证费马小定律是否成立。

*** 数学小贴士：

1) 除 (divide)，商和余数：两个整数相除，有一个为整数的商，和一个余数。比如10/3=3,余1。我们用一个特别的方式记录这一叙述:

也可以写成另一种方式：

这一表述方式与“10除以3，得3余1”这样的方式并没有什么区别。但采用标准的数学方式更容易和别人交流。

如果我们知道：

那么存在某个整数t，且：

2) 整除 (divisible)：当一个整数a除以另一个整数b，余数为0时，那么我们说a可以被b整除。比如说，4可以被2整除。即

3) 质数 (prime number)：一个质数是只能被±1和这个数自身整除的整数（不包括±1）。比如2，3，5，7，11，13等等。

******

费马是一名律师，也是一名业余数学家。他对数学贡献很大，堪称“业余数学家之王”。比如他和帕斯卡的通信算是概率论的开端。还有“费马大定理”，或者称为“费马猜想”。费马有在书边写注释的习惯。他在页边角写下了费马猜想，并说：

我发现了一个美妙的证明，但由于空白太小而没有写下来。

费马自己的证明没有再被发现。“费马猜想”的证明是300多年后，以现代数学为工具证得的，而这些数学工具在费马的时代是不存在的。这导致现代的数学家怀疑费马是不是在吹牛。费马小定理是费马的另一个定理。在费马那里，也还是个猜想。证明要等到欧拉。

程序员们：注释要完整啊！

2. 欧拉定律

时间流过一百年。欧拉是18世纪的瑞典 数学家。这位数学巨人写了75本数学专著，几乎把当时所有的数学领域都征服了一遍。欧拉后来被叶卡捷琳娜二世邀请到俄国。据说，无神论者狄徳罗造访俄国， 他宣称上帝并不存在，靠雄辩击败了整个俄国宫廷。欧拉曾醉心神学，对上帝很虔诚。欧拉看不下去了，上前说，“先生，eiπ+1=0，所以上帝存在。请回答！” 狄徳罗败给这个问题，灰溜溜的走了。

（这个传说的可信度不高，因为狄徳罗本人也是一位颇有造诣的数学家。）

欧拉定理(Euler's theorem)是欧拉在证明费马小定理的过程中，发现的一个适用性更广的定理。

首先定义一个函数，叫做欧拉Phi函数，即ϕ(n)，其中，n是一个正整数。

比如5，那么从1到4，与4互质的数有4个。ϕ(5)=4

再比如6，与1，5互质，与2，3，4并不互质。因此，ϕ(6)=2

对于一个质数p来说，它和1, 2, 3, ..., p - 1都互质，所以ϕ(p)=p−1。比如ϕ(7)=6,ϕ(11)=10

*** “互质”的数学小贴士：

1) 因子 (factor)：每个整数都可以写成质数相乘的形式，每个这样的质数称为该整数的一个因子。

2) 互质 (relative prime)：如果两个整数没有公共因子，这两个质数互质。

******

欧拉定理叙述如下：

如果n是一个正整数，a是任意一个非0整数，且n和a互质。那么，aϕ(n)−1可以被n整除。  (1)

由于质数p有ϕ(p)=p−1。因此，从欧拉定理可以推出费马小定理。我们可以只使用欧拉定理，把费马小定理抛到脑后了。我们用一个例子简单的检验欧拉定理。如果n是6，那么ϕ(6)=2。让a是11，和6互质。112−1为120，确实可以被n，也就是6整除，符合欧拉定理。

数学中还有一个关于Phi函数的推论：

m和n是互质的正整数。那么，ϕ(mn)=ϕ(m)ϕ(n)        (2)