作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!
加密和解密是自古就有技术了。经常看到侦探电影的桥段,勇敢又机智的主角,拿着一长串毫无意义的数字苦恼,忽然灵光一闪,翻出一本厚书,将第一个数字对应页码数,第二个数字对应行数,第三个数字对应那一行的某个词。数字变成了一串非常有意义的话:
Eat the beancurd with the peanut. Taste like the ham.
主角喜极而泣……
这种加密方法是将原来的某种信息按照某个规律打乱。某种打乱的方式就叫做密钥(cipher code)。发出信息的人根据密钥来给信息加密,而接收信息的人利用相同的密钥,来给信息解密。就好像一个带锁的盒子。发送信息的人将信息放到盒子里,用钥匙锁上。而接受信息的人则用相同的钥匙打开。加密和解密用的是同一个密钥,这种加密称为对称加密(symmetric encryption)。
如果一对一的话,那么两人需要交换一个密钥。一对多的话,比如总部和多个特工的通信,依然可以使用同一套密钥。但这种情况下,对手偷到一个密钥的话,就知道所有交流的信息了。二战中盟军的情报战成果,很多都来自于破获这种对称加密的密钥。
二战中德军的传奇加密机:Enigma
为了更安全,总部需要给每个特工都设计一个不同的密钥。如果是FBI这样庞大的机构,恐怕很难维护这么多的密钥。在现代社会,每个人的信用卡信息都需要加密。一一设计密钥的话,银行怕是要跪了。
对称加密的薄弱之处在于给了太多人的钥匙。如果只给特工锁,而总部保有钥匙,那就容易了。特工将信息用锁锁到盒子里,谁也打不开,除非到总部用唯一的一把钥匙打开。只是这样的话,特工每次出门都要带上许多锁,太容易被识破身份了。总部老大想了想,干脆就把造锁的技术公开了。特工,或者任何其它人,可以就地取材,按照图纸造锁,但无法根据图纸造出钥匙。钥匙只有总部的那一把。
上面的关键是锁和钥匙工艺不同。知道了锁,并不能知道钥匙。这样,银行可以将“造锁”的方法公布给所有用户。每个用户可以用锁来加密自己的信用卡信息。即使被别人窃听到,也不用担心:只有银行才有钥匙呢!这样一种加密算法叫做非对称加密(asymmetric encryption)。非对称加密的经典算法是RSA算法。它来自于数论与计算机计数的奇妙结合。
为了了解RSA加密,请听一个卧底的自白:
RSA加密
我是潜伏在龙凤大酒楼的卧底。想让下面信息以加密的方式发送到总部:
A CHEF HIDE A BED
厨子藏起来了一张床!这是如此的重要,需要立即通知总部。千万重要的是,不能让反革命的厨子知道。
第一步是转码,也就是将英文转换成某个对应的数字。这个对应很容易建立,比如:
ABCDEFGHI
123456789
将上面的信息转码,获得下面的数字序列:
A CHEF HIDE A BED1 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 conventiondef convert(original): return map(ord, original)# the input is a list of integersdef encrypt(input_list): f = lambda x: (x**2987)%3937 return map(f, input_list)#==== Headquarter =====# the input is the result of the encrypt functiondef decrypt(encrypted_list): f = lambda x: (x**143)%3937 return map(f, encrypted_list)# convert numbers back to a stringdef inv_convert(decrypt_list): f = lambda x: str(unichr(x)) result = map(f, decrypt_list) return "".join(result)# Testmessage = "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整除的整数。那么,ap11能被p整除。
我们并不需要太深入了解费马小定理,因为等下就会看到这个定理的“升级版”。但这个定理依然很美妙,它优美的得到乘方和整除的某种特殊关系。使用一个例子来说明它。比如p=7,a=3。那么费马小定律表示,3711可以被7整除。
事实上,上面的数字计算得到361=728,它确实可以被7整除。
练习:尝试一个其它的例子,比如p=5,a=4,验证费马小定律是否成立。
*** 数学小贴士:
1) 除 (divide),商和余数:两个整数相除,有一个为整数的商,和一个余数。比如10/3=3,余1。我们用一个特别的方式记录这一叙述:
10≡1(mod3)
也可以写成另一种方式:
[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):一个质数是只能被±1和这个数自身整除的整数(不包括±1)。比如2,3,5,7,11,13等等。
******
费马是一名律师,也是一名业余数学家。他对数学贡献很大,堪称“业余数学家之王”。比如他和帕斯卡的通信算是概率论的开端。还有“费马大定理”,或者称为“费马猜想”。费马有在书边写注释的习惯。他在页边角写下了费马猜想,并说:
我发现了一个美妙的证明,但由于空白太小而没有写下来。
费马自己的证明没有再被发现。“费马猜想”的证明是300多年后,以现代数学为工具证得的,而这些数学工具在费马的时代是不存在的。这导致现代的数学家怀疑费马是不是在吹牛。费马小定理是费马的另一个定理。在费马那里,也还是个猜想。证明要等到欧拉。
程序员们:注释要完整啊!
2. 欧拉定律
时间流过一百年。欧拉是18世纪的瑞典数学家。这位数学巨人写了75本数学专著,几乎把当时所有的数学领域都征服了一遍。欧拉后来被叶卡捷琳娜二世邀请到俄国。据说,无神论者狄徳罗造访俄国,他宣称上帝并不存在,靠雄辩击败了整个俄国宫廷。欧拉曾醉心神学,对上帝很虔诚。欧拉看不下去了,上前说,“先生,eiπ+1=0,所以上帝存在。请回答!” 狄徳罗败给这个问题,灰溜溜的走了。
(这个传说的可信度不高,因为狄徳罗本人也是一位颇有造诣的数学家。)
欧拉定理(Euler's theorem)是欧拉在证明费马小定理的过程中,发现的一个适用性更广的定理。
首先定义一个函数,叫做欧拉Phi函数,即(n),其中,n是一个正整数。
(n)=总数(从1到n1,与n互质的整数)
比如5,那么1,2,3,4,都与5互质。与5互质的数有4个。(5)=4
再比如6,与1,5互质,与2,3,4并不互质。因此,(6)=2
对于一个质数p来说,它和1, 2, 3, ..., p - 1都互质,所以(p)=p1。比如(7)=6,(11)=10
*** “互质”的数学小贴士:
1) 因子 (factor):每个整数都可以写成质数相乘的形式,每个这样的质数称为该整数的一个因子。
2) 互质 (relative prime):如果两个整数没有公共因子,这两个质数互质。
******
欧拉定理叙述如下:
如果n是一个正整数,a是任意一个非0整数,且n和a互质。那么,a(n)1可以被n整除。 (1)
由于质数p有(p)=p1。因此,从欧拉定理可以推出费马小定理。我们可以只使用欧拉定理,把费马小定理抛到脑后了。我们用一个例子简单的检验欧拉定理。如果n是6,那么(6)=2。让a是11,和6互质。1121为120,确实可以被n,也就是6整除,符合欧拉定理。
数学中还有一个关于Phi函数的推论:
m和n是互质的正整数。那么,(mn)=(m)(n) (2)
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+nt1c2+nt2c1+c1c2。因此ab除以n的余数为c1c2。即[ab]n=[a]n[b]n。
根据此可以推论,[am]n=[a]mn。
演一出叫做“西游记”的大戏,选角开始:
先选择两个质数p和q,分别是沙和尚和白龙马。让n=pq,n是唐僧。一路向西,唐僧靠的是沙和尚和白龙马出力:一个背行李,一个驮人。
而k=(n)=(p1)(q1)。这里使用了(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(n)]n=[zk]n=[1]n
因此,
[zde]n=[zkt+1]n=[(zk)tz]n=[z]n
上面主要使用了de=kt+1以及(3)。也就是说:
[zde]n=[z]n
根据(3)的推论,有
([ze]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位数字的质数分解并不容易,我们要做的除法运算次数大约为10400√/2。这是10199次除法运算!天河2号每秒浮点运算是1016级别。那么,找到隐藏打手的工作,大约需要10174年……。这个活,看来只能佛祖干了。
练习 如果唐僧不够大的话,马仔就危险了。想想之前的厨子,知道悟空是3,唐僧是10。隐藏打手是谁? 八戒呢? 观音呢?
总之,带头大哥不够“罩”的话,团伙就要被一窝端了。
总结
正如我在“
数学与编程”中提到的,数学可以是程序员军火库中有力的武器。加密、解密这一事关IT安全的大课题,却和数论这一纯粹数学学科发生奇妙的关系。RSA算法的数学基础在于欧拉定理。这一诞生了几百年没有什么实用性的数学理论,却在网络时代,找到自己的栖身之处。
RSA算法是非对称算法。公开的加密方式,私有的解密方式。RSA安全的关键在于很难对一个大的整数进行因子分解。下一次,如果看到RSA被破解之类的消息,卧底必须大喊一声:“不给力呀,老湿!”
这篇文章已经充分的准备了数学,但(1), (2), (3)还可以深挖下去。如果这篇文章收获够多“赞”,就准备写一个续篇。讨论一下欧拉定理的证明,以及一些特殊情况下的RSA破解。