艾丽斯和鲍勃传密码的故事
2019-09-28 23:46:00艾丽斯想给鲍勃递一张纸条,但不想让马洛里看见纸条上写了些什么。“那么,我给他写一串密码吧。”艾丽斯想。
写成密码仍然无法防止马洛里偷窥。所幸,艾丽斯是密码学的高手,她有足够的本事,写出一串马洛里绝对看不懂的密码。
艾丽斯是个密码专家。她其实也是计算机学家耳熟能详的虚拟人物。艾丽斯、鲍勃,还有马洛里,都是科学家为了方便描述密码学原理而虚构出来的,他们经常出现在密码学和计算机科学的论文里,用来指代现实世界中的发信人、收信人、黑客。
为什么要发密码
当艾丽斯将她的信息传给鲍勃时,她希望这条信息只能到达鲍勃手中,而不会被马洛里窃取。即使马洛里读到了这条信息,她也看不懂。而且,艾丽斯希望鲍勃确知这条信息是艾丽斯发来的。
这就是密码术的三大目标:私密——只有鲍勃能读到这条信息;安全——马洛里无法接收或者读懂它,也无法篡改它;认证——鲍勃确知信息来自艾丽斯。
古老又简单的密码术
很久以前,大多数人的日常生活是用不到密码技术的,只有政府部门和军队才需要对信息保密。那时的密码技术只是把字母打乱一下顺序。
一种有名的加密方法是凯撒加密法。根据历史学家的描述,罗马大帝凯撒在书写机密文件时,会按照字母表的顺序,把每一个字母换成它后面的第三个字母。比如,如果凯撒想书写的是“A”,那么他实际写下的是“D”;如果他想写“Caesar”,他落笔的时候应该写“Fdhydu”。这是一种很简单的加密技术。通过这种加密技术,原本有意义的单词变得毫无意义,让人摸不着头脑。
数据安全的保护伞
如今,随着计算机和互联网的普及,密码技术的应用越来越广泛。当我们键入登录密码的时候,发送电子邮件的时候,使用网上支付功能的时候,信息都需要经过加密才能传送,否则,有些居心不良的黑客就会窃取这些信息。
当然,加密技术也不能像凯撒加密法那样简单了,那太容易破译了。为了加大破译难度,科学家引入了“密钥”的概念,这里面用到了大量数学知识。
密钥,正如它的字面意思,其作用恰如一把钥匙。只有手握钥匙的人才能“打开”这条信息。或者说,密钥表示原信息和密码之间的对应关系,只有知道这种对应关系的人,才能把一串毫无意义的数字还原回去。
只要我们离不开互联网,数字安全的重要性就不容忽视,密码技术将继续在日常生活中扮演重要角色。艾丽斯、鲍勃和马洛里的故事还将继续上演,下一代密码技术也会出现。
链接:用数学知识,玩一个密码游戏
在互联网上,应用最广泛的密码技术是RSA加密法。按照RSA加密法,鲍勃手中有两个密钥,一个叫公钥,这是一对整数,所有人都可见;另一个叫私钥,这是一个整数,只有鲍勃自己知道,连艾丽斯也不知道这个数字。艾丽斯用公钥给信息加密,鲍勃收到密码之后再用私钥解密。
公钥和私钥是怎样相互配合,完成加密和解密的呢?靠的是数学!现在,我们要用数学知识来玩一下这个密码游戏了,你准备好了吗?
求模运算
首先,我们要认识一种运算——求模运算。时间的计算就用到了求模运算。举个例子,现在是上午10点,5小时之后你要去游泳馆,所以你去游泳馆的时间是下午3点,对不对?因为10+5=3,是吗?咦,好像哪里不对劲,10+5明明等于15,怎么会等于3呢?那是因为小时的运算是12进制的,过了中午12点,下一小时就是1点了;12点之后的第三小时,也就是3点。12就是这次运算中的模数。如果用算式表达,可以写成15≡3mod12(“≡”表示相等,跟等号差不多),意思是说,15除以12之后,余数是3,3就是这次求模运算的结果。求模运算有一个好处,世界上有无穷多的整数,但如果以12为模数求模,结果只会有12种:0,1,2,3,4……11(因为任何数字除以12的余数无外乎这11种结果)。如果把12换成一个更小的数字,比如5,那么结果就更少了,只有5种:0,1,2,3,4。
找规律
有时,对一个数字先乘方后求模,得到的结果居然是这个数字本身。不信?我们用mod 5来举例。
先来试试数字2。21=2≡2 mod 5; 22=4≡4 mod 5; 23=8≡3 mod 5; 24=16≡1 mod 5; 25=32≡2 mod 5; 26=64≡4 mod 5; 27=128≡3 mod 5; 28=256≡1 mod 5……发现规律了吗?对于2这个数字,先乘方再求模的计算结果形成了一个循环:2-4-3-1-2-4-3-1……所以,当模数为5时,21的求模计算结果与25、29、213是一样的,都是2;同理,22的求模结果与26、210也是一样的,都是4。
再来试试数字3。31=3≡3 mod 5; 32=9≡4 mod 5; 33=27≡2 mod 5; 34=81≡1 mod 5; 35=243≡3 mod 5……同样可以得到一个循环:3-4-2-1-3-4-2-1……
数字4也一样。41=4≡4 mod 5; 42=16≡1 mod 5; 43=64≡4 mod 5; 44=256≡1 mod 5……我们得到的循环是4-1-4-1……
你看,不管最初的数字是几,它的5次方、9次方、13次方的求模结果(模数为5)都是它本身。数字2、3、4都符合这一规律。你也可以试试更大的数字,不过计算量有些大哦。
加密和解密
说回鲍勃的密钥。他的公钥有两个整数,一个是求模运算的模数(用n表示),一个是乘方运算的指数(用e表示);他的私钥也是一个整数,用d表示。n、d、e是鲍勃精心挑选的,它们满足me×d=m mod n的条件,也就是说,对于任何数字m,经过e×d次方的乘方运算之后,再以n为模数求模,得到的结果仍然是m本身。
举个例子,假设鲍勃的公钥是n=5,e=3,私钥d=7。艾丽斯想向鲍勃发送数字“2”,那么她按照鲍勃的公钥,计算出23=8≡3 mod 5,于是她向鲍勃发送了数字“3”。鲍勃用私钥解密,37=2187≡2 mod 5,结果是2,正是艾丽斯想发送的数字。
为什么会这样?因为23×7=221,而按照我们上面找到的规律,221、217、213、29、25对5求模的结果都是2本身。
有人可能会问,只要根据已知的n和e,算出d的数值,不就破译这套密码了吗?理论上确实如此,但事实上几乎不可能算出来。在实际应用中,n、d、e都是很大的数字,有好几百位长,尤其是n,是由两个巨大的素数相乘得来的,黑客必须对n进行因数分解,才能算出鲍勃的私钥。除非能找到一种快速进行因数分解的新算法,否则,大数分解的计算量是相当惊人的,以现有普通计算机的计算能力,几乎是不可能完成的任务。
本文来自《科学画报》