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

做者：Vamei 出处：http://www.cnblogs.com/vamei 欢迎转载，也请保留这段声明。谢谢！html

加密和解密是自古就有技术了。常常看到侦探电影的桥段，勇敢又机智的主角，拿着一长串毫无心义的数字苦恼，突然灵光一闪，翻出一本厚书，将第一个数字对应页码数，第二个数字对应行数，第三个数字对应那一行的某个词。数字变成了一串很是有意义的话：程序员

Eat the beancurd with the peanut. Taste like the ham.算法

主角喜极而泣……编程

这种加密方法是将原来的某种信息按照某个规律打乱。某种打乱的方式就叫作密钥(cipher code)。发出信息的人根据密钥来给信息加密，而接收信息的人利用相同的密钥，来给信息解密。就好像一个带锁的盒子。发送信息的人将信息放到盒子里，用钥匙锁上。而接受信息的人则用相同的钥匙打开。加密和解密用的是同一个密钥，这种加密称为对称加密（symmetric encryption）。小程序

若是一对一的话，那么两人须要交换一个密钥。一对多的话，好比总部和多个特工的通讯，依然可使用同一套密钥。但这种状况下，对手偷到一个密钥的话，就知道全部交流的信息了。二战中盟军的情报战成果，不少都来自于破获这种对称加密的密钥。安全

二战中德军的传奇加密机：Enigma网络

为了更安全，总部须要给每一个特工都设计一个不一样的密钥。若是是FBI这样庞大的机构，恐怕很难维护这么多的密钥。在现代社会，每一个人的信用卡信息都须要加密。一一设计密钥的话，银行怕是要跪了。ide

对称加密的薄弱之处在于给了太多人的钥匙。若是只给特工锁，而总部保有钥匙，那就容易了。特工将信息用锁锁到盒子里，谁也打不开，除非到总部用惟一的一把钥匙打开。只是这样的话，特工每次出门都要带上许多锁，太容易被识破身份了。总部老大想了想，干脆就把造锁的技术公开了。特工，或者任何其它人，能够就地取材，按照图纸造锁，但没法根据图纸造出钥匙。钥匙只有总部的那一把。函数

上面的关键是锁和钥匙工艺不一样。知道了锁，并不能知道钥匙。这样，银行能够将“造锁”的方法公布给全部用户。每一个用户能够用锁来加密本身的信用卡信息。即便被别人窃听到，也不用担忧：只有银行才有钥匙呢！这样一种加密算法叫作非对称加密(asymmetric encryption)。非对称加密的经典算法是RSA算法。它来自于数论与计算机计数的奇妙结合。工具

为了了解RSA加密，请听一个卧底的自白：

RSA加密

我是潜伏在龙凤大酒楼的卧底。想让下面信息以加密的方式发送到总部：

A CHEF HIDE A BED

厨子藏起来了一张床！这是如此的重要，须要当即通知总部。千万重要的是，不能让反革命的厨子知道。

第一步是转码，也就是将英文转换成某个对应的数字。这个对应很容易创建，好比：

将上面的信息转码，得到下面的数字序列：

A CHEF HIDE A BED

1 3856 8945 1 254

这串数字彻底没有什么秘密可言。厨子发现了这串数字以后，很容易根据数字顺序，对应字母表猜出来。

为了和狡猾的厨子斗智斗勇，咱们须要对这串数字进一步加密。使用总部发给咱们的锁，两个数字：3和10。咱们分为两步处理。

第一步是求乘方。第一个数字是3，也就是说，总部指示咱们，求上面数字串的3次方：

原字符串: 1   3   8   5   6   8   9   4   5   1   2   5   4

三次乘方: 1  27 512 125 216 512 729  64 125   1   8 125  64

第二步是求余数。第二个上锁的数字是10，将上面每一个三次乘方除以10，得到其他数：

余数： 1 7 2 5 6 2 9 4 5 1 8 5 4

将这串数字发回总部。中途被厨子偷看到，但一时不能了解其中的意思。若是仍是像刚才同样对应字母表的话，信息是：

AGBEFBIDEAHED

这串字母彻底不包含正常的单词。

信息到了总部。总部开始用神奇的钥匙来解读。这个钥匙是3。(偷偷告诉你的，别告诉厨子。)

（这里钥匙不当心和以前锁中的一个数字相同。这只是巧合。）

解锁过程也是两步。第一步求钥匙次的乘方，即3次方。第二步求它们除以10（锁之一）的余数。

加密信息：1   7   2   5   6   2   9   4   5   1   8   5   4

三次乘方：1 343   8 125 216   8 729  64 125   1 512 125  64 (这里用的是钥匙的“3”)

除十得余：1   3   8   5   6   8   9   4   5   1   2   5   4

正是咱们发送的信息。对应字母表，总部能够当即知道原来的信息。

特工练习

再次强调，为了演示方便，选用了简单的锁和钥匙。锁和钥匙只是凑巧相同。为此，咱们作一个小练习。

练习：总部新公布出来的锁是2987(次乘方)和3937(为除数)。

1) 做为特工，用上面的算法为信息加密(你可能须要一些编程来计算，尝试用Python的数学计算功能？)。

猜到钥匙是什么了呢？不是上面两个数字中的任何一个，而是143！

2) 做为值班人员，验证143是钥匙，能够解密信息。

为了简便，你能够只检验一个简单的信息，好比“IE”。

下面是我根据这个练习写的一个Python小程序。这里的转码用的是ASCII编码标准，而不是上面的A对应1，B对应2。

# By Vamei

#==== Agent ======== # coding covert: string to number # By ASCII convention
def convert(original): return map(ord, original) # the input is a list of integers
def encrypt(input_list): f = lambda x: (x**2987)%3937
    return map(f, input_list) #==== Headquarter ===== # the input is the result of the encrypt function
def decrypt(encrypted_list): f = lambda x: (x**143)%3937
    return map(f, encrypted_list) # convert numbers back to a string
def inv_convert(decrypt_list): f = lambda x: str(unichr(x)) result = map(f, decrypt_list) return "".join(result) # Test
message = "Go to hell!" secret = encrypt(convert(message)) print(secret) public = inv_convert(decrypt(secret)) print(public)

费马与欧拉

发觉本身被愚弄了，厨子很生气，后果很严重。厨子发奋看了书，知道了这个加密方法叫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整除的整数。那么，[$a^{p-1} - 1$]能被p整除。

咱们并不须要太深刻了解费马小定理，由于等下就会看到这个定理的“升级版”。但这个定理依然很美妙，它优美的获得乘方和整除的某种特殊关系。使用一个例子来讲明它。好比[$p = 7，a = 3$]。那么费马小定律表示，[$3^{ 7 - 1} - 1$]能够被7整除。

事实上，上面的数字计算获得[$3^6 - 1 = 728$]，它确实能够被7整除。

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

*** 数学小贴士：

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

$$10 \equiv 1 (mod\, 3)$$

也能够写成另外一种方式：

$$[10]_3 = [1]_3$$

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

若是咱们知道：

$$[a]_n = [b]_n$$

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

$$a = nt + b$$

2) 整除 (divisible)：当一个整数a除以另外一个整数b，余数为0时，那么咱们说a能够被b整除。好比说，4能够被2整除。即

$$[4]_2 = [0]_2$$

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

******

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

我发现了一个美妙的证实，但因为空白过小而没有写下来。

费马本身的证实没有再被发现。“费马猜测”的证实是300多年后，以现代数学为工具证得的，而这些数学工具在费马的时代是不存在的。这致使现代的数学家怀疑费马是否是在吹牛。费马小定理是费马的另外一个定理。在费马那里，也仍是个猜测。证实要等到欧拉。

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

2. 欧拉定律

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

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

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

首先定义一个函数，叫作欧拉Phi函数，即[$\phi(n)$]，其中，n是一个正整数。

$$\phi(n) = 总数(从1到n-1，与n互质的整数)$$

好比5，那么1，2，3，4，都与5互质。与5互质的数有4个。[$\phi(5) = 4$]

再好比6，与1，5互质，与2，3，4并不互质。所以，[$\phi(6) = 2$]

对于一个质数p来讲，它和1, 2, 3, ..., p - 1都互质，因此[$\phi(p) = p - 1$]。好比[$\phi(7) = 6, \phi(11) = 10$]

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

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

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

******

欧拉定理叙述以下：

若是n是一个正整数，a是任意一个非0整数，且n和a互质。那么，[$a^{\phi(n)} - 1$]能够被n整除。  (1)

因为质数p有[$\phi(p) = p - 1$]。所以，从欧拉定理能够推出费马小定理。咱们能够只使用欧拉定理，把费马小定理抛到脑后了。咱们用一个例子简单的检验欧拉定理。若是n是6，那么[$\phi(6) = 2$]。让a是11，和6互质。[$11^2 - 1$]为120，确实能够被n，也就是6整除，符合欧拉定理。

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

m和n是互质的正整数。那么，[$\phi(mn) = \phi(m) \phi(n)$]        (2)

RSA西游记

下面咱们要进入实质的证实。除了上面的(1)和(2)推论，还须要提早说明一个问题，即：

[$[ab]_n = [a]_n[b]_n$]        (3)

证实：假设a和b除以n的余数为[$c_1, c_2$]。a和b能够写成[$a = nt_1 + c_1, b = nt_2 + c_2$]。那么，[$ab = n^2t_1t_2 + nt_1c_2 + nt_2c_1 + c_1c_2$]。所以ab除以n的余数为[$c_1c_2$]。即[$[ab]_n = [a]_n[b]_n$]。

根据此能够推论，[$[a^m]_n = [a]_n^m$]。

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

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

而[$k = \phi(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互质，那么：

$$[z^{\phi(n)}]_n = [z^k]_n = [1]_n$$

所以，

$$[z^{de}]_n = [z^{kt + 1}]_n = [(z^k)^tz]_n =  [z]_n$$

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

$$[z^{de}]_n = [z]_n$$

根据(3)的推论，有

$$([z^e]_n)^d = [z]_n$$

妖怪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位数字的质数分解并不容易，咱们要作的除法运算次数大约为[$\sqrt{10^{400}}/2$]。这是[$10^{199}$]次除法运算！天河2号每秒浮点运算是[$10^{16}$]级别。那么，找到隐藏打手的工做，大约须要[$10^{174}$]年……。这个活，看来只能佛祖干了。

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

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

总结

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

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