π导航  


【首页】

大质数基础上RSA加密算法


【2021-06-18】 【教育】


模算术催生了密码学的一项重要发展:公开密钥加密。所有密码都有赖于密钥,它们所面临的最大风险也在于密钥被泄露。如果敌人(比如通过间谍)得到了一份你的一次性密码本的副本,那你的麻烦就大了。但也有可能这并不要紧。通常的暗含假设是,一旦有人知道了密钥,他应该就能很容易地解码加密讯息。毕竟,这正是接收者预期要做的事情,所以把它弄得很难无疑是愚蠢的。但在1977年,罗恩·里韦斯特(Ron Rivest)、阿迪·沙米尔(Adi Shamir)和伦纳德·阿德尔曼(Leonard Adleman)发现,事情并没有这么简单。事实上, 有可能公开将讯息加密的密钥,而不用担心加密讯息会被破解。同时,合法的接收者可以借助另一个相关的密钥解码该讯息,而这个密钥是保密的。

这类方法有赖于一个有趣的数学事实:逆推一个计算,从答案推算出问题,有时会比做这个计算本身难得多——即便这个过程在原理上是可逆的。如果真是这样的话,即便知道这个过程的原理,也无从算得具体的内容。不过,单靠这个事实并没什么用处,还需要有某种秘密捷径,使得合法的接收者可以轻松地解码。而这正是高斯的奇异发明、可使2+2=0的模算术大显身手的地方。

RSA加密算法(得名自上面提到的三位发明者的姓氏首字母缩写)基于欧拉证明的一个定理。这个定理推广了皮埃尔·德·费马发现并证明的一个较简单的定理,后者被称为费马小定理,以区别于费马大定理(参见《数学万花筒(修订版)》第49页)。

费马小定理说,如果以质数 p 为模数,则对于任意整数a,都有a^(p−1)≡1。例如,以5为模数,我们应该会发现1^4≡1,2^4≡1,3^4≡1,4^4≡1。情况也的确如此。比如,

3^4≡3×3×3×3≡81≡1(mod 5)

因为81−1=80,而80可被5整除。其他整数也是如此。

为了应用RSA加密算法,你先得将讯息转换成数。例如,将每个包含100个字母、空格及其他字符的块表示成一个200位的数,其中每对相邻数字根据如下规则编码字符:A=01, B=02, …, Z=26, 空格=27, ?=28, 等等。然后将一条讯息分解成一系列100位数。令 N 是其中的一个数。我们的任务是把 N 加密,通过一种使用模算术的数学方法。

下面我举一个例子,其中用到的数要比实际应用中的数小得多。 爱丽丝使用两个特别的数:77和13,这两个数是可以公开的。假设她的讯息是 N=20,则她计算2013(mod77),得到69,并发送给鲍勃。鲍勃知道秘密捷径是数37,通过它可以逆推爱丽丝使用13所作的计算。因此,他解码了爱丽丝的讯息:

6937≡20 (mod 77)

这对于爱丽丝可能发送的任何讯息都有效,因为

(N^13)^37≡N(mod77)

但这些数是如何而来的呢?

爱丽丝所选的数77是两个质数的积,7×11。可求得(7−1)×(11−1),即60,并可知存在一个数d,使得13d≡1(mod 60),以及根据欧拉定理,对于任意讯息N,(N13)d≡N(mod77)。这个数 d 只有鲍勃知道,在这里 d=37。要使这种方法切实可用,我们需要用大得多的质数替换7和11——通常是100位左右的数。编码密钥(这里是13)和解码密钥(这里是37)可从这些质数计算得出。只有编码密钥、两个质数的积以及一个200位的数需要公开。只有鲍勃需要知道解码密钥。

这涉及找到非常大的质数,而事实证明这比我们可能预想的要更容易:存在许多有效的方法去检验一个数是否为质数,而无须将其因数分解。当然,你需要利用计算机来求这些乘积。注意到这里的宠物门效应: 爱丽丝不需要知道如何解码讯息,她只需知道如何编码讯息即可。数学家普遍认为(但还不能证明),计算出一个非常大的数的质因数是极其困难的——难到在实践中做不到,而无论你的计算机多大多快。找到大质数则要容易得多,把它们相乘也是如此。

宠物门: 我有时喜欢把这类过程比喻成宠物门。我们的宠物猫埃勒坎知道通过推门从里面出来,但大部分时候它以为从外面回去的方式应该是逆转这个过程,所以常常会坐在外面试图拉门。即便它把这个逻辑推向极端,试图让尾巴先进来,我也不会觉得奇怪。但它忘了秘密捷径。我们躺在床上听着它折腾,心里暗暗着急:“埃勒坎!你倒是推啊!”

当然,我的例子使用的是不实用的小数,所以找到解码密钥37很容易。爱丽丝能算出来,任何试图破解讯息的人也可以。但若是100位的质数,如果你只知道两个质数的乘积,要算出解码密钥几乎是不可能的。另一方面,如果你确实知道这些质数,那么求解码密钥是相当简单的。这正是这个系统得以建立的基础。

像RSA这样的加密算法非常适合互联网,因为在网上每个用户都必须“知道”如何发送加密讯息(比如信用卡号)。也就是说,加密这条讯息的方法必须存储在他们的计算机上。这样的话,程序员有可能找到它。但只有银行需要知道解码密钥。因此,在罪犯分子找到大数的质因数分解的有效方法之前,你的钱都是安全的——假定银行是可靠的,不过这突然变得成问题起来了……

在实际应用中,还有其他要点需要注意,这种方法并没有这样简单。

参见:en.wikipedia.org/wiki/RSA_(cryptosystem)

还值得注意一点,在实践中,RSA主要用于发送加密后的密钥给其他更简单的加密系统,通过后者发送讯息,而非通过自己发送讯息。毕竟通过RSA发送常规讯息,所需的计算时间就有点太多了。

这个故事的最后还有一段有趣的历史花絮。1973年,英国情报部门的一位数学家克利福德·科克斯提出了同样的方法,但在当时被认为不切实际。由于保密的缘故,在1997年之前,没人知道他在RSA系统上所做的工作。



                      
   
        

copyright©2018-2021 gotopie.com