身份验证、中间人攻击和数字签名：浅谈密码学（上）

说到“密码学”，大多数人的第一念头或许是Morse电码、Ceasar移位密码、同音替换密码之类的东西。这些东西在各类小说中都已是老面孔了，“字母e在英文中出现频率最高”这一最基本的破密码方法已经是耳熟能详了。几天前和网易的云风聊了一下，突然体会到了密码学的真谛。密码学关注更多的并不是加密解密的各种数学算法，而是在已有数学算法上如何实现各种安全需求。防止消息泄露只是众多安全问题中的冰山一角，而这个问题本身又有很多复杂的变化。

当我们谈到“消息泄露”时，我们头脑中想到的往往是，在信息传输过程中如何防止第三方截获。当然，小偷防是防不住的，不过我能保证他偷到东西也没用。双方只需要事先约定一套加密函数和解密函数，以密文的方式进行传输，这样便能很好地防止消息泄露。但有时候，“消息泄露”的内涵复杂得多，加密解密的传统方法并不适用。考虑这么一个问题：10个人坐在一起谈天，突然他们想知道他们的平均年薪，但又都不愿意透露自己的工资数额。有没有什么办法让他们能够得出答案，并且不用担心自己的年薪被曝光？事实上，最简单的解决办法不需要依赖任何密码学知识：第一个人随便想一个大数，比如880516。然后他在纸条上写下这个数与自己的年薪之和，传给第二个人；第二个人再在这个数上加上他的年薪数额，写在另一张纸条上传给第三个人；直到最后一个人把纸条传回第一个人后，第一个人把纸条上的数减去只有自己知道的那个880516，便得到了全部10个人的工资和。

这样的智力题还有很多很多。另一种关于防止信息泄露的场景则是，我不告诉你某样事情，却又要让你相信我知道这件事情。我曾经介绍过这么一个问题：给定一个图，假如我找到了一条Hamilton回路，我如何才能让你相信我确实知道答案，而又不告诉你答案是什么？一个基于概率的算法是，我随意构造一个同构图，然后由你来发问：要么让我证明这的确是一个同构图（给出顶点的对应关系），要么叫我指出这个同构图上的Hamilton回路。充分多次测试后，你有充足的理由相信我的确找到了Hamilton回路，但你依旧不知道具体的答案。

可以看到，密码学不仅仅研究加密解密的数学算法。更多的时候，密码学研究保护信息安全的策略，我们可以称之为“协议”。在已有的数学模型基础上，我们往往忽略具体的数学实现方法，转而专注地研究借助这些数学工具能够构建的安全措施。除了消息保密性以外，密码学还研究一些更加有趣的问题。下面我们看另外三种常见的信息安全问题。

首先是关于身份验证的问题：我如何才能知道你真的是你。身份验证是密码学关注的一个大问题。接头暗号、帐号密码都是解决身份鉴别问题的办法。在互联网上，“用户名/密码”模式是最常见的用户身份鉴别模式。但这里出现了一个前面没有出现过的严峻问题：如何防止第三方截获？有人可能会脱口而出：为何不像前面一样，把密码加个密发出去？现在的网站一般都用md5的方法对密码进行“单向加密”：客户端计算密码的md5值并发送出去，服务器接收到该md5值并与自己机器上预先算出来的md5结果进行比较。数据以md5的形式进行传输，即使被第三方截获也能保证密码安全。其实，这种方法仍然是不可靠的，原因在于，鉴别问题和消息泄露问题有着本质的区别。在前面的消息传输一例中，为了防止第三方截取者，我们采用了消息加密的方法，避免第三者获取原始信息；而这里，第三方截取者根本就不需要知道你的原始信息是什么，只要照着你发的信息发就是了。如果我想假冒你，只要知道了密码的md5值就可以模拟发送相同的数据包；这个md5值就已经成为了开门的钥匙，你的真实密码是什么对我根本不重要。

这样一来，身份验证似乎永远不可能做到了——第三者一旦截获你发送的信息就可以完全模拟你。解决这个问题的小技巧就是，让用户每次发送的验证信息都不一样。例如，每次需要身份验证时，服务器随机生成一个字符串，发送给客户端；然后客户端把输入的密码和该字符串连接起来一起md5，再传回去看这个md5值与服务器端的计算结果是否相符。那为什么各大网站没有这么做呢？主要原因估计是因为，每次身份验证都要算一次md5会大大增加服务器的压力。

留心你周围的事物，你会发现，这种“一次性密码”是经常使用的。我有两张银行卡，一张农行的，一张交行的。交行的网银需要绑定手机，每次网上消费时系统会给你手机发送一段随机代码叫你输入，因此除非你倒霉到卡号、密码和手机同时丢失，否则你的网银账户永远是安全的。农行使用的是“口令卡”，每个人的口令卡都不相同。卡片背后有几十个小格子，每一个格子刮开来就是一个代码。网上交易时，系统会叫你输入某行某列的格子中的数，你便把那一格刮开来看。这些“活动密码”手段有效地防止了网络窃听。

我编了一个记日记的软件给自己用。进入这个软件时需要输入密码，密码是年份模23加上月份的平方的三倍，再乘以日期的自然对数小数点后第三位，减去小时数的倒数的余切值的最高两位。瞟到我密码的人会发现，等我离开后偷偷打开日记软件，刚才的密码不管用了。

信息安全这档子事永远是防不胜防。上面这个“活动密码”协议就安全了吗？可以看到，除非你是真的知道用户名密码，否则你不可能骗过主机；同时，数据传输用的md5算法，这是不可逆的，窃听者无法恢复原数据。但是，再往前一追溯，漏洞就出来了：用户注册时提交的那个密码又是怎样传输的呢？显然，这时再用md5来传输是不行的，因为md5不可逆，主机算不出你的真实密码是多少，“活动密码”方案就用不成了；直接用明文传输呢，被第三者窃听的危险又出来了，哪天账户被盗了后打死你也想不出密码在最开始商定的时候就被泄露了。这样看来，用户设定密码时只能进行加密传输了。然而，加密传输必然又要事先约定加密方式，而这个加密方式的商定过程本身又有泄露的风险，这就又回到了原来的问题上。有可能避免密钥的交换么？如果是朋友之间的通信，把两人已知的小秘密用作密钥（例如约定密钥为甲方的生日乘以乙方的手机号）或许能让人放心许多，但在网络中，特别是用户与主机的会话中，这显然是不现实的。这样看来，信息安全问题似乎是没法解决了。

为了解决这个“圈”，我们需要想一个绝对邪的办法……如果我不告诉任何人解密的算法不就行了么？这就需要一种全新的加密方法，知道密钥的人可以加密，但却不能解密，密文只有在我这儿才能解密。这样的话，就连给我发消息的那个人也只会加密不会解密，安全性得到了极大的提高；即使密钥被窃听了，第三者也读不出原始消息。

是否有可能告诉一个人加密算法，但他却无从获知解密算法呢？乍看之下这貌似是不可能的。对于一种加密方法，似乎总会存在一种对应的解密算法：你加我就减，你左移我就右移，你替换过去我就替换回来，加密解密步骤正好互逆。虽然难以置信，但这种不可逆的“不对称密码”的确是存在的。RSA算法就是这样一种算法，任何人都可以知道该怎么加密，但让你知道了怎么加密你也不会进行解密，密文只有到了我手里才解得开。也就是说，这种算法有一个可以公开的“公开加密钥匙”，和一个只有自己才有的“私人解密钥匙”。这种神奇的“公钥加密术”的基本思想其实很简单：构造公钥只需要把两个大质数相乘，但要想获得私钥必须进行大数分解，而后者目前还没有什么有效的算法。这一“正行容易逆行难”的思想就是RSA算法的核心。网上对RSA算法的描述太多了，但在这里我还是想简单的描述一下。

选取两个大质数p和q。算出n=pq。算出φ(n)=(p-1)(q-1)。找一个数小于φ(n)的数e，使得e与φ(n)互质。n和e就可以作为公钥公开了。假设明文m是一个小于n的数。只要拥有公钥n和e，任何人都可以根据公式c=m^e mod n算出密文c（可以二分加速）。但是呢，你会发现你解不回去了……因为只知道n、e和c，你是不能反过来求出m的。

那我们该怎么算m的值呢？只需要求出一个满足ed≡1 (mod φ(n))的d后，我们就可以直接用公式m=c^d mod n求得明文。利用扩展的辗转相除，我们可以很容易求出满足要求的d。但是φ(n)的值只有我才知道，别人是不知道的（如果想要破解出来必须得把n分解成p和q），因此这个d值就是一个只有我自己才知道的解密钥匙。下面我们来说明上述解密算法的正确性。由于ed-1能被(p-1)(q-1)整除，它必然也能被(p-1)整除，因此m^ed可以表示成m^(k(p-1)+1)，其中k是某个适当的整数。现在，假设m是p的倍数，那直接就有m^(ed)≡0^(ed)≡0≡m (mod p)；否则，m和p一定互质，根据Fermat小定理有m^(p-1)≡1(mod p)，于是m^(ed) = m^(k(p-1)+1) = [m^(p-1)]^k * m ≡ 1^k * m ≡ m (mod p)。同理，当模数为q时也总有m^(ed)≡m。既然p整除m^(ed)-m，q也整除m^(ed)-m，并且p和q都是质数，那么一定有m^(ed)≡m (mod pq)，即m^(ed)≡m (mod n)。这个m^(ed)就等于我们前面的c^d。

现在我们得到了两个函数F和G，其中F(m)=c，而G(c)=m。大家都知道函数F是什么，但是却求不出函数G，这个函数G就是只有我自己知道的私人钥匙，函数F则是公之于众的公共钥匙。

这一套算法最大的意义就是省去了隐患多多的“密钥交换”这一步。以后大家发送加密消息前再也不需要暗中约定密码算法了。每个人都自己找两个几十几百位长的质数，生成公钥n和e公布到网上去。如果A要和B通信，A直接用B的公钥进行加密，然后把密文传给B；A不会害怕第三者截获消息，因为这个密码只有B才能解得开。同样地，B想要回复A的话，只需要用A的公钥加密，然后把消息发送给A即可。在服务端与客户端的信息交流中更适合使用公钥加密术，因为服务端向所有客户端公告其公共钥匙更加方便，更加合理。用户需要设定密码时，传输请求前只需要把要提交的数据用服务端的公开密钥进行加密即可，这样既不用交换密钥，又不必担心第三者的窃听，因为这个数据只有服务端才能解开。