8.2　现代密码学

“我们今天正面临着一场密码学的革命。”这是1976年斯坦福大学的惠特菲尔德·迪菲和马丁·赫尔曼所发表的著名论文中的开题句。“廉价电子硬件制造技术的进展将密码学从使用机械进行计算所带来的设计局限中解放出来，让曾经昂贵的高端加密设备变得成本低廉，使得远程提款机、计算机终端等商业化应用成为可能。”

迪菲和赫尔曼认识到了，计算机可以让复杂的加密通信协议以成本低廉的软件形态存在。但同时计算机也带来了很多挑战。随着计算机与计算机之间的网络得到普及，必须要开发出一种高效率且低成本的安全通信方法。迪菲和赫尔曼在谈到近十年来P/NP问题的进展时说道：“同时，信息论和计算机科学的理论进展很有希望提供一种安全的加密方法，从而将密码学这门古老的艺术变为一门科学。”

在迪菲和赫尔曼之前的时代，要解密一条消息必须使用加密它的密钥。如果一位将军通过恩尼格玛密码机向战场上的一位上尉发送消息，双方必须事先约定好机器的设置，即转子在消息开头的初始参数。上尉会随身携带一个密码本，里面记录了每天更换的设置参数。如果这个本子落入敌手，秘密通信就必须停止，直到发放一套新的密码本。士兵们平时会悉心保管这些本子，一旦被俘就立即销毁它们。所以并不需要经常更换新的密码本。

计算机网络带来了新的挑战，因为不能想当然地认为网络是安全的。20世纪末的计算机网络通常会在某些区域通过普通电话线来传输，而电话线是很容易被窃听的。即使是今天，坐在咖啡馆另一头的人也可以读取你使用免费Wi-Fi所发送的全部数据。

不能用网络来发送密钥，否则之后的通信变得不安全。在开始和某人秘密通信前，必须要用某种物理的方法将密钥送到那个人手上。而这样做的经济和时间成本都很高。

在前人罗杰·默克尔工作的基础上，迪菲和赫尔曼提出了解决这个问题的一种方法，他们称之为“公钥”加密。计算机生成两把钥匙，一把公钥，一把私钥。计算机自己储存好私钥，绝不把它泄露到网上。公钥则通过网络广播给所有人。

迪菲和赫尔曼的想法是建立这样一个密码系统，即使用公钥加密信息，将原始消息变成一串密码。公钥不能用来解密消息，只有私钥可以解密消息。

假如迪菲想发送一条秘密消息“中午进攻”给赫尔曼，首先赫尔曼要生成私钥和公钥。然后赫尔曼把公钥发送给迪菲（也发送给所有可能正在监听的人），私钥则自己留着。然后迪菲用赫尔曼的公钥把消息“中午进攻”加密为密码“tzljcnnfekktis”，并把密码“tzljcnnfekktis”发送给赫尔曼。迪菲在加密时不需要知道私钥，只需使用公钥。窃听者能看到加密的字符串“tzljcnnfekktis”，但是只知道公钥是不能恢复原始消息的。赫尔曼则可以用自己的私钥把“tzljcnnfekktis”恢复成原始的消息，即“中午进攻”。

公钥加密有可能实现吗？如果P=NP那就不可能，因为会存在一个高效的算法，通过公钥来计算出私钥。

而即使是在1976年，大多数计算机科学家也认为P≠NP，在此前提下公钥加密是可能的。迪菲和赫尔曼首创了公钥加密系统，但是他们提出的通信协议不如另一个协议流行，该协议由罗纳德·李维斯特、阿迪· 沙米尔和伦纳德·阿德曼三位计算机科学家于1978年发明，并以三人的姓缩写命名为RSA。

RSA加密协议基于这样一个想法，即计算乘积容易，分解因数则很难。随机挑选两个大的质数，比如5 754 853 343和2 860 486 313，很容易计算其乘积为16 461 679 220 973 794 359。另一方面，很难逆转这个运算，即把16 461 679 220 973 794 359分解为5 754 853 343乘以2 860 486 313。RSA使用了比这大得多的数，通常有几百位长。虽然说如果不证明P≠NP，就无法证明因数分解本质上是一个难以计算的问题，但大部分人都认为因数分解是一个困难的问题。

罗纳德·李维斯特、阿迪·沙米尔和伦纳德·阿德曼因为发明该协议，分享了2002年的图灵奖。

有一个小插曲，其实RSA协议最早是在1973年被克利福德·柯克斯发明的，他为英国政府通信总部工作，该机构相当于美国的国家安全局。这个事实直到1997年才被公之于众。

你可能每天都在用RSA加密协议。随便看一个网站（结果可能因浏览器差异而不同）。

图8-4　Facebook网站的地址栏

注意到https协议中的s以及后面的小锁标识。

图8-5　被标记的Facebook网站的地址栏

s代表secure（安全）。Facebook公布了一把公钥。浏览器会把用户输入的密码用公钥加密。加密过的密码被发送给Facebook。所以咖啡馆里的人即使用笔记本电脑监测所有用Wi-Fi传输的数据，也无法猜出用户的密码。Facebook用私钥可以解密用户的密码。同样地，用户的浏览器也生成一对公钥和私钥，把公钥发送给Facebook。这样Facebook就可以向用户发送经过加密的好友状态更新数据，除了用户自己别人都看不到。