数学科普

数学与互联网安全

JoeMalkevitch

关键词：密码学，数论，网络安全

对于电子转账、电子邮件或者网上购物等系统的用户而言，他们总是担心自己的交易是否按

照计划进行而没有被“劫持”。这时数学与计算机的联姻可以成为网络安全的坚强后盾。

2005年12月离新年假期只有几天的时候，纽约的公交系统员工在纽约市区举行了大

罢工。市民如果试图到商店去购物，可能需要在路上堵上好几个小时、再走上很久的

路、并且也很难拦到出租车。因此很多纽约市民选择了在网上进行购物。不过还是有

很多人因为担心交易的安全性而对网上购物退避三舍。

大家心里的疑问包括：

网上金融交易是否安全？

通过互联网发送电子邮件是否受到第三方的监控从而导致邮件内容泄露？

网络病毒以及“流氓软件”正越来越猖狂，我们如何对付这些问题？

数学正在尽力解决上述这些问题，从而使得网络交易百分之百的安全，以及让电子邮

件系统成为人们值得信赖的一种生活方式。实现这些目标的工具恰恰是一些以前被认

为是毫无实用价值的数学知识！人们一直在发明新兴技术从而制造出更快更小的电脑

芯片。一部分人正在致力于创造一个安全的互联网环境，而另一部分同时也在不停地

试图通过互联网“提取”他人的财富（而不是在银行里排队取款！）。这是一场猫和

老鼠的游戏，而这个游戏也受到电脑芯片技术的影响。

互联网技术涉及的数学知识十分广泛，从数据压缩和误差压缩技术，到信息传递的方

法和安全设计都需要大量的数学。本文将着重讨论与互联网安全的几个数学问题。

密码学

一个战争指挥官总是希望他发给前线军官的命令不会落到敌方手中。因此，如果命令是通过书面

来传递，那是十分不安全的。因为一旦命令书被敌方拦截，自己的计划就彻底暴露了。（当然要

通讯员把命令背下来再进行传递也不现实，大家看看电视里的谍战片或反恐片就知道这种方式是

多么不安全了。）JuliusCaesar被认为是最早使用数学知识来对信息进行加密的人之一。据说

他的加密方法是把一段文字（也就是原始信息）的每一个字母都用字母表里其对应的后一个字母

来代替，而字母表的最后一个字母就用其第一个字母来代替。按照这种方法，CaesarCipher这

个短语就由DbftbsDjqifs来代替。其实我们有很多种可能的加密方式来产生这样一段信息。因

此，这样的加密方式足以迷惑“敌人”一段时间了。前面这个例子我们是把一段文字按照字母表

往后移动1个位置。更一般的，我们可以按照字母表往后移动r个位置。比如r=5的话，Caesar

Cipher这个短语经过加密以后就变成了hfjxfwhnumjw。今天我们把这种加密方式都叫做凯撒密

码。

但是，如果解密员碰巧想到一段文字的加密方式是把每一个字母按照字母表顺移同样

的位置，那就算把每种可能的方式都试一遍来解密，其工作量都不大，因为毕竟只有

26个字母。这个简单的例子已经说明了无论是互联网密码学还是军事密码学，“复杂

度”和安全性两者之间都存在着有趣的联系。有时候，我们的目的仅仅是拖延对手的

行动。比如，我们可以把一段毫无意义的信息加密，然后让对手花上整整一个小时去

解密。不过，一旦一条信息被对方成功解密，下次我们再有一条类似的信息被对方拦

截的话，解密时间可能就会从一小时急剧减少为3分钟了。所以我们必须想办法永远

比“敌人”快一步。接下来的讨论里，我有时候混用“代码”和“密码”，以及“解

码”和“解密”。不过，“密码”一般是指把一段文字的每一个符号都用同一字母表

或其它字母表里的另一个符号来代替。相反，“代码”是指把一段文字的每一组符号

用另一组符号来代替。

自从Caesar密码提出后，密码学得到了极大的发展。其中一个很简单的想法是加密

的信息不一定要与原始信息有相同的字数。如果字母“I”或者“a”作为一个单词单

独出现在一段加密字符串里，那这段加密字符串就很容易被破解了。通常的做法是，

把一段信息的每5个字母分成一组（不记字间的空格和标点符号），然后每组都用另

外5个字母代替。这样加密的字符显得更难破解。如果原始信息的字符数不是5的倍

数，那我们可以额外地将一些符号定义为这个“转换”里的空集，然后用这些符号来

补齐缺少的字符数。

另外一个简单的想法是用多字码密码，也就是说给原始信息加密的字母表按照某个密

钥随字母逐字变化。由于原始信息的每一个字母都对应到密钥里的一个字母，用以加

密的字母表也会不断变化。这个想法的代表人物是LeoneAlberti，他也是映射几何

的先驱。最初人们都相信这样一个“复杂”的加密系统是不可攻破的。不过，如果密

钥含有的字符数不多，并且由同一加密系统得到的密文样本足够多的话，我们可以用

一些统计的方法来破解这样的密码。如果一个钥匙是随机产生并只使用过一次，也即

一次性密钥，那这样的密码是无法破解的。如今当我们试图对一些信息进行安全保护

时，面临的一个很重要的问题是如何交换密钥，特别是随机产生的大量钥匙。

在现代生活里，人们更是意识到数学在安全事物中的重要性，其中不得不提的人物是

阿兰•图灵(1912-1954)。

希特勒在攻占荷兰、法国等国家后，试图进一步攻占英国。当时，英国全力以赴试图

通过使用通讯和信号智能技术以及解密信息技术来阻止德军侵占不列颠群岛。英军在

Bletchley公园成立了一个由语言学家和数学家组成的特别行动组，尽量从拦截到的

敌军信息里获得有用的信息。包括MarianRejewski在内的波兰数学家首先获得了成

功，他们将破解的德军代码交给英军。

图灵及团队根据波兰提供的信息，成功地破解了德军“神秘机器”（Enigmamachine,

见下图）以及其它密码系统发出的密码。毫无疑问，图灵等人的成功改变了这场战争

的结果，也改变了历史。

图灵与数学家GordonWelchman还发明了一种特殊的“计算机”来破解德军“神秘机

器”产生的密码。

同样，在美国也有不少语言学家和数学家在战争中发挥了作用。其中最著名的可能是

WilliamFriedman(他是业余数学家)以及他的妻子、语言学家Elizabeth。二战期间，

美军破获了日本军队大量的密码，也因此成功取得了战争的胜利。

如今，密码学不再仅仅是为军事与外交服务了，它越来越多地用在资本财富的建设上，

例如通讯与互联网。对于电子转账、电子邮件或者网上购物等系统的用户而言，他们

总是担心自己的交易是否按照计划进行而没有被“劫持”。当然，这涉及到的问题也

是十分得复杂多样。当我们给别人发送一条信息时，我们自然要考虑这些问题：第一，

对方收到的信息是否就是我们发出的原始信息，而不是被人更改过的；第二，现在发

出的信息是否会危害到将来发出的信息的安全；第三，别人会不会通过我们发送信息

的方式而盗用我们资料，然后以我们的名义再给别人发送邮件。“阴谋”这个人们常

常与间谍或者间谍行为联系在一起的词，一样会在互联网安全领域里大肆横行。

散列法

散列法即按照某种方法，用一串短很多的字符替代一串长字符。例如，我们可以用一

个仅仅用一首诗包含的字母个数来表示这首诗。乍看上去，散列法似乎是关乎数据压

缩，而不是数据安全的。显然在散列系统里我们可以设法隐藏原始字符，使之很难破

解。因此很容易理解为什么一串被打散的字符可以起到加密的作用。使用散列法需要

注意的是避免两组不同的字符串最后被散列成同一字符串。这种情况叫做冲突。在这

样定义的散列系统里，如果两首诗歌有相同的字符个数，那么就会产生冲突。因此，

我们在设计散列系统时，必须要说明怎么处理冲突情况。散列法的另外一个好处就是，

两列相似的字符串经过散列后，可能会大不一样。因此，即使有人试图对一个加密过

的文档进行微小的修改，也会很容易地被发现。因为原始的和伪造过的两个文档的散

列字符串大相径庭。同样我们可以理解为什么散列法与用户登录密码和数字签名密切

相关。数字签名是一个电子确认系统，其功能与我们书信或支票中常用的手写签名类

似。我们当然希望一个数字签名系统可以尽可能地减低伪造的风险。在1990年代中

期，麻省理工学院的RonaldRivest设计的MD-5(Message-DigestAlgorithm5)散列

系统被广泛的使用。不过，数学家和计算机学家在1996年在这方面做出了一系列的

研究，使得人们意识到MD-5有着安全性能方面的缺陷。于是MD-5被SHA-1取代。

散列法在用户密码管理系统里十分常用，因此它与互联网安全也早已密不可分。除了

登录电子邮件账户，人们还常常需要使用用户密码来登录一些互联网提供的商业服务

（例如报纸或金融网站的账户）。你可以很快根据一些简单的规则来改进自己的用户

密码，从而使得自己的密码比大多数人的更安全。不幸地是，只要计算设备足够好，

好几个有关散列系统的标准都被证明是有安全性能隐患的。最近，被认为是有关散列

系统的安全性能通用标准的SHA-1也被证实是不安全的。这是由中国数学家王小云和

她的团队发现的。当然，人们对王小云的成果短期内是否会影响业界意见并不一致。

尽管我们暂时还没有可破解SHA-1的计算设备，王小云取得的成果足以让我们相信她

的尖端成果有可能攻击现有的安全系统。比SHA-1更安全的散列系统确实已经出现了，

不过这方面的进展并不快。

有这么多的加密办法，好像要从一段加密信息恢复出原始信息实在是太困难了。一般

有两种破解办法。第一种方法是用统计技术。如果我们拿到大量的加密数招兵时间 据，那么我

们可以试图寻找其中的一些特定模式（例如分析一些符号的出现频率的分布情况）来

进行破解。另一种方法是注意到加密的人经常会有些特定的语言习惯，而我们可以利

用这一点作为解密的切入点。比如有些人在一段信息的开始总是用同样的问候语。再

比如有些信息都是以天气报告为开头，这也使得解密者可以试图猜测一些相同的字符

是如何编码的。还有一点就是，一个被广泛使用的系统通常都有不少人参与管理与维戏答元珍欧阳修

护。这时以德立身 候，很难确保该系统云的简笔画 的信息不被流传出来。因此，用来解决替代密码的方法

与基于母体技术的方法不同。从现实角度来看，很多人都接受以下观点，即只有在假

设攻击安全系统的人已经完全知道该系统的设计方案的前提之下，才能真正解决安全

问题。因此，“敌人”或许已经知道你正在使用RSA(下面会解释)还是Hill密码（基

于矩阵的系统）。

公匙系统

1970年代中期，人们发现了一种全新的编码方式（也有人认为其实早就有人发现了），

这是密码学的一个里程碑式的发展。传统的密码学里，需要共享一段加密形容树木 信息的双方

会设置一个系统，并需要完成一把钥匙的交换。直观上我们可以理解为这把钥匙将一

段秘密发送的信息锁起来。当接收信息的人有一把一模一样的钥匙时，他就可以解开

这段被锁起来的信息。因此，在单匙系统里，加密和解密的双方有一把同样的钥匙。

公匙系统的出现改变了这一切。有关公匙系统的发展一言两语无法说清楚，不过人们普遍认为

RalphMerkle,WhitfieldDiffie和MartinHellman三人在这个领域做出了非常重要的贡献。

公匙系统有两把钥匙。一把用于给某人X发送一段密码信息。正如电话簿上的电话号码，这把钥

匙是公开的。另一把则不公开，它与公匙一起由X保留。公匙加密学与现代私匙系统还允许陌生

人之间随意交换钥匙。这样的系统是由Diffie和Hellman在Merkle的想法基础之上发明的，并

用于不加密的通讯系统。这个系统已经申请了专利，不过现在专利保护的时间已经到期了。下面

我们略微讨论一下最为人们所熟知的公匙系统，即以RonaldRivest,AdiShamir以及Leonard

Adlemean这三位发明者命名的RSA系统。

还有一个很常用的公匙系统是由TaherElgamal在1984年提出来的。这套系统主要

用群论和复杂性的知识来保证安全。

对RSA和ElGamal（也包括其它系统）而言，一个很有用的概念就是同余。如果两个

整数a和b被一个大于或等于2的正整数m除以后，得到相同的余数，那么我们就说

a和b同余，记为

a≡bmodulom.

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

12≡2modulo5

-3≡2modulo5

-3≡23modulo13

对于模m，我们总共可以将一对同余数右边的那个数替换成介于0与m-1之间的一个

整数。比如，上述最后一对同余数，我们可以将23替换成10。大泥鳅 在以下表达式里，我

们可以很容易确定“？”的值：

572≡?modulo19

办法是计算5,52,54,58等数取19的模，然后利用指数的二元表示法表示出72这个指数，

并把答案找出来。不过，要找到整数k使得以下的同余表达式成立就不那么简单了：

5k≡13modulo19

类似于这样的寻找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问题是指一类难度一样的问题，也即如果这些问题的其中一个可以被多

项式级别的时间求解的话，那么所有这一类问题都是多项式时间可解的。另一方面，

如果其中一个问题需要指数级别的时间求解的话，那么所有这一类问题都是指数可解

的。不过，虽然很多人都认为一些问题需要指数级别的时间求解，但事实上这一点也

没有人可以完全肯定。大家认为没有简单算法可以对一个大整数进行因子分解，而且

直到不久前，人家也不知道究竟是否有办法用多项式级别的时间来验证一个数是否是

素数。所以当ManindraAgrawal,NeerajKayal,和NitinSaxena三人提出一个验证

素数的多项式算法时，人们感到十分意外。现在有很多快速算法可以验证一个数是否

是素数。有意思的是，其中最快的一些算法的确可以在绝大多数情况下检验素数，但

偶尔也会把一个复合数误认为是素数。验证素数的多项式算法方面的进展也意味着我

们有可能找到实现整数的因子分解的多项式算法。（值得一提的是，不是每个多项式

算法在求解实际问题的时候都很快。而有些指数算法，例如求解线性规划的单纯型法，

在求解实际问题时却十分有效。原因是实际碰到的问题并不是那些单纯型法无效的问

题）

下面简单介绍一下广为人知并被广泛使用的RSA公匙密码系统。我们假设已经将一段

要发送的原始信息的文字（例如英文）分成一块一块的结构，而原始信息的每一块也

用一个数字M来表示。我们需要考虑怎么安全地发送M。接下来，我们产生两个大

素数p和q。相对来说，这比较容易（也有人认为如何选这样的素数直接影响到最后

的加密安全）。现在我们选一个大于1的整数e，它要与乘积(p-1)(q-1)互素。两个

整数称为互素，如果能被这两个整数都圣经诗篇 整除的最大整数是1。例如，12和35都不是

素数，但它们互素。然后，我们找一个整数s使得

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

之后，再计算p和q这两个秘密的素数的乘积n=pq。为了发送M这个信息，我们计

算C来产生一段密码电文：

C=Memodulon

其中e和n的值即是公匙。注意n是两个大素数的乘积。如果n不能分解的话，它的

值对密码电文C而言毫无价值。

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

Csmodulon,

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

为什么这样计算就可以得到M呢？其中原因（我们省去细节）涉及到了数论中的两

个经典定理，一个是费马（1601-1665）提出的“费马小定理”：

ap−1≡1modulop,

其中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)≡1modulox

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

由于RSA系统的安全性依赖于大整数的分解，使用RSA系统的公司对数学家和计算机

学家提出了很多有关整数分解的难题。最近，有人分解了一个193位的数，而这在之

前是被认为十分困难的。现在也有不少人悬赏可观的奖金来求解一些整数分解问题，

不妨看看这个网站！

最近，一个有关RSA和其它公匙系统安全性问题的担忧出现了。这一担忧关乎复杂度。随着传统

计算机的速度变得越来越快，人们不禁要问是否可以用穷举的方法来破解加密系统。之前使用很

多年的商用传统编码基本都是由IBM公司制定的DES(DataEncryptionStandard)标准。由于DES

不再安全，一种新的标准也应运而生。这个新的标准被称之为“高级编码标准”，并以其发明者

JoanDaemen和VincentRijmen的名字组合而命名为Rijndael。在取代DES而成为新标准之前

的试用阶段，Rijndael经过了极其严格的检查和考验并通过了各种测试，最终才投入使用。不

过，大家认为Rijndael在数学上是极其“完美”的，以至于有人认为它数学上太过完美而最终

将走向灭亡。也许最后我们还是可以根据Rihndael系统漂亮的数学结构来找到还未被发现的漏

洞来破解它吧。

与计算机以及计算机技术支持的电信业紧密相关的数字革新发展，都是基于使用功能强大的单片

机或者是使用多芯片技术的并行机。不过，科学家们正在努力发展一种基于物理学中的量子力学

概念的全新计算方式。这种新的计算方式被称为量子计算。如果量子计算机成为现实，那么数学

家Peter芬兰用什么货币 Shor等人已经预言：有些问题用常规电子计算机求解，需要花很长时间，而通过量子

计算机，时间会少得多。其中，Shor指出整数的因子分解这个问题如果用量子计算机来处理的

话，就会比用传统电子计算机快很多。因此，如果量子计算机出现了，那么RSA系统就无法再保

证密码系统的安全了。这个涉及到物理、数学以及计算机的新兴学科究竟会发展到什么情况，人

们正拭目以待。

互联网已经改变了美国人以及世界各地所有人的交流方式，也改变了人们的生活。如

果互联网还像人们所期望的那样继续给人们的生活带来正面影响，那么数学家也将继

续成为其合作者以保证互联网的发展。

参考文献

1.毫无疑问，有关互联网安全的文献的更新速度是非常快的。一些对电脑运算速度不高

的安全保障方法以及在一定时间里最好的算法经常没过多久就失效了。有关过去和最新的发展趋

势可以在网上很多地方找到。下面一些网址仅供参考：

erSecurityArchiveProject.

alInstituteofStandards.

ernationalAssociationforCryptologicRearch

原文链接:/samplings/feature-column/fcarc-internet

作者:JoeMalkevitch，纽约城市大学约克学院

翻译:袁晓明博士，香港浸会大学

校对:汤涛，香港浸会大学数学讲座教授