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

3. RSA西游记

除了上面的(1)和(2)推论，我们还需要提前说明一个问题，即：

[ab]n=[a]n[b]n        (3)

证明：假设a和b除以n的余数为c1,c2。a和b可以写成a=nt1+c1,b=nt2+c2。那么，ab=n2t1t2+nt1+nt2+c1c2。因此ab除以n的余数为c1c2。即[ab]n=[a]n[b]n。

根据此可以推论，[am]n=[a]mn。

演一出叫做“西游记”的大戏，选角开始：

先选择两个质数p和q，分别是沙和尚和白龙马。让n=pq，n是唐僧。一路向西，唐僧靠的是沙和尚和白龙马出力：一个背行李，一个驮人。

而k=ϕ(n)=(p−1)(q−1)。这里使用了(2)以及“质数p的Phi函数值为p-1”。k是八戒，也就是Phi(唐僧)，就是唐僧的一个跟屁虫。

选择任意d，并保证它与k互质。d是观音。观音姐姐在高老庄，真的是把八戒给“质”了一把。

取整数e，使得[de]k=[1]k。也就是说de=kt+1，t为某一整数。e是悟空，横行无忌。

我们记得公开的用来上锁的两个数字，它们分别是悟空e和唐僧n。悟空威力大，负责乘方。唐僧太唠叨：一切妖怪见到它，就变成了余数。悟空和唐僧合作，就把世界搞乱了。

总部的观音姐姐d看不下去了。观音姐姐威力也大，也是乘方。再逼着唐僧重新唠叨。世界就恢复了。

善哉，善哉！

我们看一下这一魔幻大片“西游记”的现实主义原理。根据欧拉定理(1)，对于任意z，如果z与n互质，那么：

因此，

上面主要使用了de=kt+1以及(3)。也就是说：

根据(3)的推论，有

妖怪z，经过e和d的各一道，又变回了妖！上面过程中，悟空e和观音d忙得不亦乐乎，唐僧n就在一旁边唠叨边打酱油了。

这一等式，也正是我们加密又解密的过程 (加密: 悟空次方 + 唐僧唠叨。解密: 观音次方 + 唐僧唠叨)。悟空和唐僧是公钥，扔出去亮相。观音是私钥，偷偷藏起来，必要的时候才出来。

(上面都默认余数是最小正余数，也就是说，10除以3的余数为1，而不是4。尽管4也可以算是10的余数，即[4]3=[10]3。)

姐姐，饶了我吧。

3和8两个妖怪见到唐僧5，都被唠叨成了余数3。这样就观音姐姐就算法力无边，还是没法还原。为了让唐僧求余的时候，不会把数字弄混了，RSA算法要求所有妖怪z小于唐僧n。为了对足够多的字符转码加密，n必须大过最大的妖怪。

但唐僧n大更重要的原因是要保护马仔。 想破解，必须找到观音。回顾我们选择角色的过程。我们可以这样破解：唐僧n是公开的，1) 先找到它的隐藏手下沙和尚和白龙马。2) 沙和尚和白龙马知道了，那么二师兄k就保不住了。3) de = kt + 1，即找到一个e，可以让de - 1被k整除。观音姐姐就找到了。

上面的整个破解过程中，最困难的是第一步，即找到两个隐藏的打手。通常，p和q都会选的非常大，比如说200位。这导致唐僧n也非常大，有400位。寻找一个400位数字的质数分解并不容易，我们要做的除法运算次数大约为10400−−−−√/2。这是10199次除法运算！天河2号每秒浮点运算是1016级别。那么，找到隐藏打手的工作，大约需要10174年……。这个活，看来只能佛祖干了。

练习 如果唐僧不够大的话，马仔就危险了。想想之前的厨子，知道悟空是3，唐僧是10。隐藏打手是谁？ 八戒呢？ 观音呢？

总之，带头大哥不够“罩”的话，团伙就要被一窝端了。

总结

正如我在“数学与编程”中提到的，数学可以是程序员军火库中有力的武器。加密、解密这一事关IT安全的大课题，却和数论这一纯粹数学学科发生奇妙的关系。RSA算法的数学基础在于欧拉定理。这一诞生了几百年没有什么实用性的数学理论，却在网络时代，找到自己的栖身之处。

RSA算法是非对称算法。公开的加密方式，私有的解密方式。RSA安全的关键在于很难对一个大的整数进行因子分解。下一次，如果看到RSA被破解之类的消息，卧底必须大喊一声：“不给力呀，老湿！”

这篇文章已经充分的准备了数学，但(1), (2), (3)还可以深挖下去。如果这篇文章收获够多“赞”，就准备写一个续篇。讨论一下欧拉定理的证明，以及一些特殊情况下的RSA破解。