量子计算机之经典密码篇（下）

[soliton]

上回书说到，RSA要设计一个公钥密码系统。那么设计的关键是什么呢？关键是找出一种计算，它和它的逆运算难易程度相差很大。好古老的一个问题。也许大家都已经深有体会了。看这样一个题目，请将209分解为两个质数的乘积。最一般而直接的算法是的：试！从2一直试到11。9次！需要试9次除法，我们发现209=11*19。但是我们做11*19则简单很多，直接乘就行了。这是一个简单的例子。下面我们估计一下稍微复杂的情况。假设我们把209换成一个大约是10的120次方的数字，也就是说这个数字大约有120位，我们想将此数字写为两个质数的乘法，那么最直接的办法需要试10的60次方除法。假设一秒钟可试一万次，需要10的47次方年才能试完。地球现在的年龄是65亿年，不超过10的10次方（100亿）。这个任务简直没法完成。而乘法，则轻松很多，两个60位数的乘法，用手算也就一天的时间（没算过，大概背3600次乘法口诀，
）。RSA正是了解到大数分解的本质，从而设计了RSA公钥系统。

下面举个有名的例子来说明RSA公钥密码系统是怎样工作的。

RSA公布了其设计方案后，Gardner根据这个方案在1977设计了一段密码，并公开悬赏100美元，不是100万美元，：（，请大家破解：
968696137546220614771409222543
558829054599911245743198746951
209308162962251457083569314766
228839696280133919900551829945
157815154
共129位。看起来好像也并不可怕，竟然没办法破解出什么意思。10年过去了，没有答案，15年过去了（1992），还是没有答案。20年过去了，打住，没到20年！1995年这个密码被破解了！它的意思是：the
magic words are squeamish ossifrage
(这些神奇的词是神经质的秃鹰），
还是大家自己查查字典吧。

待续。。。