数学与互联网安全2

公匙系统

1970年代中期，人们发现了一种全新的编码方式（也有人认为其实早就有人发现了），这是密码学的一个里程碑式的发展。传统的密码学里，需要共享一段加密信息的双方会设置一个系统，并需要完成一把钥匙的交换。直观上我们可以理解为这把钥匙将一段秘密发送的信息锁起来。当接收信息的人有一把一模一样的钥匙时，他就可以解开这段被锁起来的信息。因此，在单匙系统里，加密和解密的双方有一把同样的钥匙。

公匙系统的出现改变了这一切。有关公匙系统的发展一言两语无法说清楚，不过人们普遍认为Ralph Merkle,Whitfield Diffie和Martin Hellman三人在这个领域做出了非常重要的贡献。

公匙系统有两把钥匙。一把用于给某人X发送一段密码信息。正如电话簿上的电话号码，这把钥匙是公开的。另一把则不公开，它与公匙一起由X保留。公匙加密学与现代私匙系统还允许陌生人之间随意交换钥匙。这样的系统是由Diffie和Hellman在Merkle的想法基础之上发明的，并用于不加密的通讯系统。这个系统已经申请了专利，不过现在专利保护的时间已经到期了。下面我们略微讨论一下最为人们所熟知的公匙系统，即以Ronald Rivest,Adi Shamir以及Leonard Adlemean这三位发明者命名的RSA系统。

还有一个很常用的公匙系统是由Taher Elgamal在1984年提出来的。这套系统主要用群论和复杂性的知识来保证安全。

对RSA和ElGamal（也包括其它系统）而言，一个很有用的概念就是同余。如果两个整数a和b被一个大于或等于2的正整数m除以后，得到相同的余数，那么我们就说a和b同余，记为

a ≡ b modulo m.

此时，b-a被m除的余数是0。以下是一些例子

12 ≡ 2 modulo 5-3 ≡ 2 modulo 5-3 ≡ 23 modulo 13

对于模m，我们总共可以将一对同余数右边的那个数替换成介于0与m-1之间的一个整数。比如，上述最后一对同余数，我们可以将23替换成10。在以下表达式里，我们可以很容易确定“？”的值：

572≡ ? modulo 19

办法是计算5,52,54,58等数取19的模，然后利用指数的二元表示法表示出72这个指数，并把答案找出来。不过，要找到整数k使得以下的同余表达式成立就不那么简单了：

5k≡ 13 modulo 19

类似于这样的寻找k的问题被称为离散对数问题。当模非常大的时候，人们还不知道有什么方法比穷举法快很多。而对于解决离散对数问题和一些在设计公匙系统中用到的算法的复杂度，人们还知之甚少。一些基于NP-complete问题而建的系统崩溃了，而一些基于复杂度并没有完全搞清楚的问题而建的系统反而运行良好。下面我们将简单讨论一下被广泛用以衡量互联网安全性能的RSA系统。

小测试

许多公匙加密系统人员都受到“单向函数”的启发。有些任务很容易完成，但他们的反向任务则很难，除非有特殊的附加信息。

如果你想感受一下有关复杂度的数学知识是什么以及它是如何与安全性能联系在一起的话，试试下面的例子，用一个带秒钟的表测试一下你需要花多少时间求解这些例子。

问题1：123457乘以372451等于多少？

问题2：374251的因子？（我确定除了1和它本身，还有别的因子）

你也许会发现，问题1虽然很繁琐，但是得到它的答案并不难。然而，即使你能解决问题2，你花的时间可能要比问题1多的多。大多数人甚至都没有耐心去完成最终的解答。

问题1比问题2更简单，这意味着什么？问题1要求两个数的乘积，更具体地说是是两个6位数的素数的乘积（素数是指它的因子仅有1和它本身），而问题2是要求将一个可以表示成两个素数乘积的数进行分解而得到这两个素数。（即已知s是某两个素数p与q的乘积，求解p与q.）

大部分人都认为还没有一个真正的快速算法可以在一部标准的电脑上快速地分解整数。但同时，人们也没有任何结果表明整数的分解是一个NP-complete的难题。NP-complete问题是指一类难度一样的问题，也即如果这些问题的其中一个可以被多项式级别的时间求解的话，那么所有这一类问题都是多项式时间可解的。另一方面，如果其中一个问题需要指数级别的时间求解的话，那么所有这一类问题都是指数可解的。不过，虽然很多人都认为一些问题需要指数级别的时间求解，但事实上这一点也没有人可以完全肯定。大家认为没有简单算法可以对一个大整数进行因子分解，而且直到不久前，人家也不知道究竟是否有办法用多项式级别的时间来验证一个数是否是素数。所以当Manindra Agrawal,Neeraj Kayal,和Nitin Saxena三人提出一个验证素数的多项式算法时，人们感到十分意外。现在有很多快速算法可以验证一个数是否是素数。有意思的是，其中最快的一些算法的确可以在绝大多数情况下检验素数，但偶尔也会把一个复合数误认为是素数。验证素数的多项式算法方面的进展也意味着我们有可能找到实现整数的因子分解的多项式算法。（值得一提的是，不是每个多项式算法在求解实际问题的时候都很快。而有些指数算法，例如求解线性规划的单纯型法，在求解实际问题时却十分有效。原因是实际碰到的问题并不是那些单纯型法无效的问题）

下面简单介绍一下广为人知并被广泛使用的RSA公匙密码系统。我们假设已经将一段要发送的原始信息的文字（例如英文）分成一块一块的结构，而原始信息的每一块也用一个数字M来表示。我们需要考虑怎么安全地发送M。接下来，我们产生两个大素数p和q。相对来说，这比较容易（也有人认为如何选这样的素数直接影响到最后的加密安全）。现在我们选一个大于1的整数e，它要与乘积(p-1)(q-1)互素。两个整数称为互素，如果能被这两个整数都整除的最大整数是1。例如，12和35都不是素数，但它们互素。然后，我们找一个整数s使得

(e)(s)≡1 modulo (p-1)(q-1)

之后，再计算p和q这两个秘密的素数的乘积n=pq。为了发送M这个信息，我们计算C来产生一段密码电文：

C=Me modulo n

其中e和n的值即是公匙。注意n是两个大素数的乘积。如果n不能分解的话，它的值对密码电文C而言毫无价值。

解密者通过以下计算来解密：

Cs modulo n,

其中s和n的值即是解密者的私钥。这些值用于恢复原始信息M.

为什么这样计算就可以得到M呢？其中原因（我们省去细节）涉及到了数论中的两个经典定理，一个是费马（1601-1665）提出的“费马小定理”：

ap−1≡ 1 modulo p,

其中p是素数，而a与p互素。另外一个定理是欧拉（1707-1783）提出的，它涉及到一个表示与x互素的整数个数的函数。我们记这个函数为ϕ(x)，也成为欧拉函数或者熵函数。对于任意的素数p,

ϕ(p)=p−1

而且，如果x与y是互素的整数，我们有以下关系：

ϕ(xy)=ϕ(x)ϕ(y)

于是，对于不同的素数p和q,我们有

ϕ(pq)=(p−1)(q−1)

欧拉还证明了一个涉及到ϕ函数φ(x)的有关费马小定理的非常漂亮的推广：

aϕ(x)≡ 1 modulo x

其中x是一个与整数a互素的正整数。

由于RSA系统的安全性依赖于大整数的分解，使用RSA系统的公司对数学家和计算机学家提出了很多有关整数分解的难题。最近，有人分解了一个193位的数，而这在之前是被认为十分困难的。现在也有不少人悬赏可观的奖金来求解一些整数分解问题，不妨看看这个网站！

最近，一个有关RSA和其它公匙系统安全性问题的担忧出现了。这一担忧关乎复杂度。随着传统计算机的速度变得越来越快，人们不禁要问是否可以用穷举的方法来破解加密系统。之前使用很多年的商用传统编码基本都是由IBM公司制定的DES(Data Encryption Standard)标准。由于DES不再安全，一种新的标准也应运而生。这个新的标准被称之为“高级编码标准”，并以其发明者Joan Daemen和Vincent Rijmen的名字组合而命名为Rijndael。在取代DES而成为新标准之前的试用阶段，Rijndael经过了极其严格的检查和考验并通过了各种测试，最终才投入使用。不过，大家认为Rijndael在数学上是极其“完美”的，以至于有人认为它数学上太过完美而最终将走向灭亡。也许最后我们还是可以根据Rihndael系统漂亮的数学结构来找到还未被发现的漏洞来破解它吧。

与计算机以及计算机技术支持的电信业紧密相关的数字革新发展，都是基于使用功能强大的单片机或者是使用多芯片技术的并行机。不过，科学家们正在努力发展一种基于物理学中的量子力学概念的全新计算方式。这种新的计算方式被称为量子计算。如果量子计算机成为现实，那么数学家Peter Shor等人已经预言：有些问题用常规电子计算机求解，需要花很长时间，而通过量子计算机，时间会少得多。其中，Shor指出整数的因子分解这个问题如果用量子计算机来处理的话，就会比用传统电子计算机快很多。因此，如果量子计算机出现了，那么RSA系统就无法再保证密码系统的安全了。这个涉及到物理、数学以及计算机的新兴学科究竟会发展到什么情况，人们正拭目以待。

互联网已经改变了美国人以及世界各地所有人的交流方式，也改变了人们的生活。如果互联网还像人们所期望的那样继续给人们的生活带来正面影响，那么数学家也将继续成为其合作者以保证互联网的发展。