密码战争（五）：魔术背后的方法.doc

密码战争(五):魔术背后的方法
[ 4 ] 魔术背后的方法
正如前面所提到的,公共密钥加密系统依靠一种魔术般的要素:单向函数。当迪菲和海尔曼第一次提出他们的观点时,他们在脑子里可没有任何特殊的“功能”的概念。那之后不久,海尔曼的一个学生拉尔夫·墨克提出了一个概念。这个概念最终被证明是不能满足要求的,因为这个概念并不象人们刚开始思考它时所表现出来的那样—经不住反向推敲。因此这个问题留给了另三名数学家,这三名数学家发明了一种单向函数,这种函数既简单,又对进攻具有足够的抵抗力,而他们的发明直到今天仍然是被使用最广泛的公共密钥系统。
1977年,罗纳德·李维斯特、阿迪·萨莫尔和伦纳德·阿德曼发明了RSA加密系统。这套加密系统基于一个简单的概念,即将数字相盛非常简单,但要找出约数则要难很多。为了让这件事对计算机来说尽可能难以完成,你可以让你的初始数字是素数。素数就是那些比如2、3、5、7以及更大的没有约数只能被1和自身整除的数字。任何台式计算机都可以将两个150位的数字相乘,并在不到一秒钟的时间里输出一个300位的数字。但是如果你将这个300位的数字输入世界上最快的最大计算机里,这台计算机是不可能找出那两个得出这个300位数字的约数的。
这样,将两个数字相称的简单特性就具有了单向函数所有的特点:便于操作,但逆向操作几乎无法实现。但如何才能将单向函数转换成一个公共密钥加密术呢?这个答案还不明了,直到李维斯特、萨莫尔和阿德曼做出了他们天才般的贡献。
他们的系统利用了素数和非素数之间的微妙差异,这种差异最早是在1640年前后由法国数学家皮耶·德·费玛发现的。想象你找出任何一个数字n,,一遍一遍地盛。如果不让数字变得越来越大,每步都用n来作除数,在进行这个步骤时进行记录。图2表明了当n=13,a=2时会发生什么:序列会以1、2、4、8、3的顺序排下去,而到第13步,数字又重新变成了2.
根据费玛的分析,这并非偶然。当n是素数时,重复相乘的把戏总是在n步之后循环回最开始的起点。但当n不是素数时,:要这么做,你需要知道n的约数是多少。
直到20世纪70年代,很多理论家都对这个重复相乘的把戏可以被用作加密术有丝毫的怀疑。但这个小把戏被称为“费玛小法则”,是同更著名的“费玛最新法则”有区别的。李维斯特、萨莫尔和阿德曼空前的洞察力却能够洞察到这一点:如果数字a被想象成一条信息,然后重复相乘,比如乘e次,然后在以n为模让数字变小,这就是一种将信息打乱的方法。而如果要将打乱的加密信息进行解密,你也不需要进行反向的操作:你只要继续用a的e次方再乘一次就可以了。在进行额外的几步工作之后,这条信息就会象魔术一样再次出现在你的面前。
图3表明了李维斯特、萨莫尔和阿德曼如何将这一设想融合进加密术的具体细节。记住,在公共密钥加密术中,信息接收人负责他们自己的公共和私人密钥的产生。首先,Bob选择两个非常大的常数p和q,比如各有150位的长度作为自己的私人密钥。除了这两个数字必须是常数这一限制外,这两个数字可以被任意选择。他的公共密钥由n组成,即p的q次方;e也就是加密密钥,同时必须满足几个同约数n相关的几个软性条件。这些条件对Bob来说也不会是什么难