Posted on 06-11-2015
Filed Under (技术) by waterlin

本文摘自《费马大定理:一个困惑了世间智者358年的谜》“第三章数学史上暗淡的一页”中的部分内容,主要是介绍一下密钥和公钥的数学原理,摘录于下,备查。

虽然质数的无穷性使早期证明费马大定理的希望破灭,但质数的这种性质的确在诸如谍报活动和昆虫进化等别的领域具有比较积极的意义。在回到寻求费马大定理的证明之前,稍微研究一下质数的正常使用和滥用是值得的。

质数理论是纯粹数学中已经在现实世界中找到直接应用的少数领域之一,它在密码学中有直接应用。密码学涉及将需要保密的信息打乱,使得只有接收者才能整理出它们,而别的任何可能截获它们的人都无法做到这一点。这种打乱的过程需要使用密钥,而整理这些信息按惯例只需要接收者反过来使用密钥就行了。在这个程序中,密钥是保密环节中最薄弱的一环。首先,接收者和发送者必须约定密钥的详细内容,而这种信息的交流是一个有泄密风险的过程。如果敌方能截获正在交流的密钥,那么他们就能译出此后所有的信息。其次,为了保持安全性,密钥必须定期更改,而每一次更改时,都有新的密钥被截获的危险。

密钥的问题围绕着下面的事实展开:它的使用,一次是打乱信息,另一次是反过来整理出信息,而整理信息几乎与打乱信息同样容易。然而,经验告诉我们:在许多情况中整理要比打乱困难得多——打碎一个鸡蛋是相对容易的,而重新拼好它则困难得多。

在20世纪70年代,惠特菲尔德·迪菲(Whitfield Diffie)和马丁·海尔曼(Martin Hellman)提出了这样的思想:寻找一种按一个方向很容易进行,而按相反方向进行则不可思议地困难的数学程序。这种程序将会提供十分完美的密钥。举例来说,我可以有自己用的、由两部分组成的密钥,并且在公用指南中公开它的用于打乱信息的那部分。

于是,任何人都可以向我发送打乱过的信息,但是只有我知道密钥中用于整理信息的那一半。虽然人人都了解密钥中关于打乱信息的那部分,但是它和密钥中用来整理信息的那部分毫无联系。

在1977年,麻省理工学院一群数学家和计算机专家罗纳德·里维斯特(Ronald Rivest)、艾迪·沙米(Adi Shamir)和伦纳德·阿德里曼(Leonard Adleman)认识到质数可能是易打乱、难整理过程的理想的基础。为了制成我自己的私人密钥,我会取两个大质数,每一个多达80个数字,然后将它们乘起来得到一个大得多的非质数。为了打乱信息所需要的一切,就是知道这个大的非质数,然而要整理信息则需要知道已经被乘在一起的原来的两个质数,它们称为质因数。现在我可以公开大的非质数,也即密钥中打乱信息的那一半,而自己保存那两个质因数,即密钥中整理信息的那一半。重要的是,即使人人都知道这个大的非质数,他们要判断出那两个质因数却仍然非常困难。

举一个简单的例子,我可以交出非质数589,这可能会使每个人都能代我打乱信息。然而,我将保守589的两个质因数的秘密,结果只有我能够整理信息。如果别的人能判断出这两个质因数,那么他们也能整理我的信息,但是即使是对这个不大的数,两个质因数是什么也不是显而易见的。在589这个情形中,在台式电脑上只要花几分钟就可算出两个质因数实际上是31和19(31×19=589),所以我的密钥的秘密不会持久。

然而,实际上我公布的非质数将会有100位以上的数字,这就使找出它的质因数的任务变得几乎是不可能的。即使用世界上最快的计算机来将这个巨大的非质数(打乱信息的密钥)分解成它的两个质因数(整理信息的密钥),也要花几年时间才能得到答案。于是,为挫败外国间谍,我仅仅需要每年一次更改我的密钥。每年一次我宣布我的巨大的非质数,任何人要想尝试整理我的信息,就必须从头开始设法算出这两个质因数。

除了在谍报活动中发现应用外,质数也出现在自然界中。在昆虫中十七年蝉的生命周期是最长的。它们独有的生命周期开始于地下,蝉蛹在地下耐心地吮吸树根中的汁水。然后,经过17年的等待,成年的蝉钻出地面,无数的蝉密集在一起,一时间掩盖了一切景色。在几个星期中,它们交配,产卵,然后死去。

除了在谍报活动中发现应用外,质数也出现在自然界中。在昆虫中十七年蝉的生命周期是最长的。它们独有的生命周期开始于地下,蝉蛹在地下耐心地吮吸树根中的汁水。然后,经过17年的等待,成年的蝉钻出地面,无数的蝉密集在一起,一时间掩盖了一切景色。在几个星期中,它们交配,产卵,然后死去。

有一种理论假设蝉有一种生命周期也较长的寄生物,蝉要设法避开这种寄生物。如果这种寄生物的生命周期比方说是2年,那么蝉就要避开能被2整除的生命周期,否则寄生物和蝉就会定期相遇。类似地,如果寄生物的生命周期是3年,那么蝉要避开能被3整除的生命周期,否则寄生物和蝉又会定期相遇。所以最终为了避免遇到它的寄生物,蝉的最佳策略是使它的生命周期的年数延长为一个质数。由于没有数能整除17,十七年蝉将很难得遇上它的寄生物。如果寄生物的生命周期为2年,那么它们每隔34年才遇上一次;倘若寄生物的生命周期更长一些,比方说16年,那么它们每隔272(16×17)年才遇上一次。

为了回击,寄生物只有选择两种生命周期可以增加相遇的频率——1年期的生命周期以及与蝉同样的17年期的生命周期。然而,寄生物不可能活着接连重新出现达17年之久,因为在前16次出现时没有蝉供它们寄生。另一方面,为了达到为期17年的生命周期,一代代的寄生物在16年的生命周期中首先必须得到进化,这意味着在进化的某个阶段,寄生物和蝉会有272年之久不相遇!无论哪一种情形,蝉的漫长的、年数为质数的生命周期都保护了它。

这或许解释了为什么这种假设的寄生物从未被发现!在为了跟上蝉而进行的赛跑中,寄生物很可能不断延长它的生命周期直至到达16年这个难关。然后它将有272年的时间遇不到蝉,而在此之前,由于无法与蝉相遇它已被赶上了绝路。剩下的是生命周期为17年的蝉,其实它已不再需要这么长的生命周期了,因为它的寄生物已不复存在。

© 2015, 浏忙大爆炸. All rights reserved.
除非注明,浏忙大爆炸文章均为原创,转载请以链接形式标明本文地址。

(0) Comments    (652) Views    Read More   
Post a Comment
Name:
Email:
Website:
Comments: