Matrix67_Brief_Cryptography
这是一篇转载的文章，作者是计算机科普领域的大佬 matrix67。这里整理了他关于浅谈密码学的几篇博文。
身份验证、中间人攻击和数字签名：浅谈密码学（上）
说到“密码学”，大多数人的第一念头或许是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)整除，因此med可以表示成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)就等于我们前面的cd。
现在我们得到了两个函数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即可。在服务端与客户端的信息交流中更适合使用公钥加密术，因为服务端向所有客户端公告其公共钥匙更加方便，更加合理。用户需要设定密码时，传输请求前只需要把要提交的数据用服务端的公开密钥进行加密即可，这样既不用交换密钥，又不必担心第三者的窃听，因为这个数据只有服务端才能解开。
身份验证、中间人攻击和数字签名：浅谈密码学（中）
事情还没有结束呢！我们前面假设，大家公开公钥的方式是“发布在一个众人可信的网站上”，这种假设是有原因的。需要临时交换双方公钥的通话协议是不安全的，这里面存在一个戏剧性的漏洞。举个例子，假如A和B认为，任何网站都是不可靠的，他们从未并且今后也不会在网上公布自己的公钥。为了加密通信，A需要亲自告诉B他的公钥，B也需要亲自告诉A自己的公钥。收到公钥后，双方便用对方的公钥加密进行数据传输。因为用这个公钥加密后，只有对方才能解开密码，因此双方都认为这条通信线路是安全的。其实，他俩的麻烦大了。这条线路并不是安全的，第三者可以用一种很搞笑的方式来窃听消息。假设有一个人C知道A和B之间将有一次加密通话。C劫持了A和B之间的通讯线路。现在，A把他的公钥发给B，这个公钥传到一半时被C拦截下来，于是C获得了A的公钥；C再把他自己的公钥发给B，让B把C的公钥错当成A的公钥。同样地，B把他自己的公钥发给A，被C拦截下来。C把自己的公钥发给A，让A以为那是B的公钥。以后，每当A给B发加密消息时，A其实是用C的公钥在加密；C把A的消息解密后，再用B的公钥加密后传给B。类似地，一旦B给A发送消息，C都可以将消息解密，并用A的公钥进行加密后传过去。此时，A和B都以为自己在用对方的公钥加密，并都能用自己的私有钥匙解开对方传来的密文；殊不知，这中间有人仅仅用了一点雕虫小技，无声无息地窃走了所有的信息。C正是利用了公钥加密术“谁都可以加密”的性质，结结实实地玩弄了A和B。这种攻击方法叫做“中间人攻击”。 这让我想起了经典的国际象棋骗术。一个象棋白痴宣称自己是个大牛。为了证实这一点，他将要与两位大师同时对弈。他说，我先下后下都能赢。于是，在与大师A的对弈中他为白方，与大师B对战则执黑。结果呢，两盘比赛下来居然都打成了平手。怎么回事呢？其实那个象棋白痴耍了个小伎俩，他把大师A走的棋记了下来，跑到另一边去下给B看，又把B的应着原封不动地搬到了和A的棋局上。来来回回搞了半天，他自己只起了个传递信息的作用，真正在对弈的是两个大师。
怎样防止这种中间人攻击呢？中间人之所以能够得逞，关键就是，无论是网络通话还是国际象棋，双方总是一先一后地发送信息。不过，在网络通讯中，我们有一种很特别的办法，他可以迫使中间人无法再扮演“即时翻译”的角色。首先，A把想说的话（最好是能够证明自己身份的话）进行加密，同时B也完成相同的工作。然后，A把他的加密消息的前面一半传给B，B收到后也把他的密文的一半传给A；A再把剩下的部份传给B，之后B也把他的密文的另一半回传给A。此时，A和B分别用自己的私钥进行解密，查看对方发来的消息。这带给中间人C一个不可逾越的障碍：两段密文要合在一起才能解开，中间人拿着其中一半密文，那是一点办法都没有。此时，中间人陷入了一个非常窘迫的境地，他只有两条路可选：要么硬着头皮把这半截密文发给B，当B得到全部密文后会发现用他自己的私钥根本解不开，从而意识到中间有人捣乱；要么就忽略这半截密文，自己编几句A想跟B说的话，用B的公钥加密并发一半给B。如此一来，中间人需要编造所有A和B之间的对话，这需要相当厚的脸皮，风险异常之大，要不了多久便会露出马脚。
RSA算法还有一个特别的应用。注意到公钥和私钥所对应的两个函数是互逆的，因此如果我用私钥来加密，用公钥同样可以恢复原来的数据。但是，用我自己的密钥加密，然后大家都可解密，这有什么用处呢？不妨来看看这样“加密”后的效果吧：第一，貌似是最荒谬的，大家都可以看到源文件；第二，很关键的，大家只能够看源文件，但不能改动它；第三，满足上述两个要求的文件别人是做不出来的。 这些性质正好完美地描述出“签名”的实质。为了防止钓鱼网站骗取你的账户和密码，正牌的那个服务器需要发送一条消息，以证明自己确实是唯一的服务提供商。为此，你可以发送一个随机字符串过去，要求服务器用它的私钥加密。服务器传回他加密过的字符串后，若你用他的公钥解密能恢复出原来的字符串，则说明对方一定是正宗的服务提供商。只有拥有私钥的人才能做到这一点，别人是无法伪造这个“签名”的。 数字签名还有一些其它的特殊变化。考虑这样一种情况，我有一份秘密文件需要签名，但我不希望签名者看到这份文件的内容。这种看似很不合理的情况确有发生。例如在证人保护计划中，我是一个特工，我需要保护一个非常可爱的无辜小MM。为了把她安置到一个偏远的安全地，我需要让上级签署各种通行证明文件；但为了安全起见，我不希望把安全地的位置泄露给任何人。为此，我希望我的上级对文件进行签名，但保证他们完全不知道文件内容是什么。满足这种要求的签名协议叫做“盲签名”。为了得到一种“盲签名”算法，考虑用RSA进行签名的本质：假设待签名的文本为（不超过模数n的）t，则我们实质上希望得到t^d mod n，其中n是模数，d是签名者的私人钥匙。我们的目的是，对文本t进行干扰（例如在t上面加一个大数，或者乘一个大数，或者取t的倒数的正弦值的-π次方的自然对数），让签名者不知道t是什么；但签名者签名之后，我们还能除去刚才的干扰因子，还原为t^d mod n。因此，我们需要想一个奇妙的办法，让被干扰的文本签名后，干扰因子头上的“d”正好消失了。回忆之前讲过的结论m^(ed)≡m (mod n)，我们立即想到了盲签名算法：我把明文t乘上一个随机数k的e次方（e是公开钥匙），把t*(ke)传给签名人。注意我们选取的k一定要与n互质，否则k是大质数p或q的倍数，“干扰”的结果必然为0。这下，签名人当然不可能知道t是什么，因为他不知道随机数k是多少。他对t*(ke)进行签名，传回来的结果即为t^d * k^(ed) mod n。但k(ed)模n就等于k，于是这个签名结果实际上就是td * k mod n。现在，我只需要把该结果除以只有我才知道的k（即乘以它在模n剩余类环中的逆元，这个逆元保证存在，因为k和n互质），即得到了我需要的签名文件t^d mod n。 盲签名协议并不是只有特工才可能用到的东西，它的应用范围其实相当广。在生活中，我们每个人都可能用到过盲签名。一个最常用的例子就是投票协议——中央机构需要确定每张选票都来自合格的选举人，并且每个人最多投了一次票；但同时选举人又不希望在投票过程中泄露自己的选票内容。但是，为了检查选票的来源是否可靠，中央机构必然要鉴别每张选票所属的投票人。怎么办呢？此时，盲签名协议就派上用场了。每个选举人在自己的选票前面加上一个随机字符串作为前缀（防止以后被暴力破解），然后乘上随机数k的e次方，再连同一份（未被干扰的）身份证明，一同递交给中央机构。中央机构检查身份证明，确认这张（被干扰过的）选票来自合格的选举人。然后中央机构给这张选票签名，回传给选举人。选举人将签名结果除以k，用中央机构的公钥检查看签名是否有效，随机字符串是否和自己当初设定的一样。接着投票人匿名提交这份由中央机构签过名的（且不带干扰因子的）选票。中央机构收到选票，用公钥解密看签名是否有效。这样，中央机构既可以确信每张选票都来自合格的投票人，严格实行一人一票制度，又不能追查出任何一个投票者的选票内容。
更复杂的盲签名协议来源于这样一种特殊情况：恐怖分子答应供出炸弹的位置，前提条件是需要得到一系列保证无罪逃脱的签名文件，包括新身份、新护照，以及总统亲自签署的免起诉书和安全离境的通行证。同时，恐怖分子又需要确信政府不能知道他的新身份和潜逃地。这需要政府在不知道文件内容的情况下签署协议。这与刚才所谈的盲签名有什么区别呢？一个巨大的区别就是，要求盲签名的不是特工，而是坏蛋，政府在没有看到文件之前不能随意签名。万一恐怖分子要求盲签名的文件实际上是一份要求政府保护全体恐怖分子的安全，保证所有人永不被通缉永不被起诉，并无偿提供恐怖组织基地和巨额资助等不平等条约该咋办？因此，这里需要一种比盲签名要求更高的协议：签名者不能看到文件内容，但要相信文件的内容是什么。 看起来这似乎是办不到的，但事实上这是有可能的。我们有一个非常简单的办法，它是一个基于概率的协议。恐怖分子可以起草十份文件，每份文件里都包含了一个不同的新身份和潜逃地。然后恐怖分子用十个不同的随机数对这十份文件进行干扰，传给政府。政府选取其中的九份文件，向恐怖分子索要干扰因子。恐怖分子把对应的那九个k值传过去，政府对其进行解密，从而看到这九份文件都是符合要求的文件（只是文件中具体的身份名字和潜逃地点不一样）。政府对最后一个文件进行签名，并把签名结果回递给恐怖分子。恐怖分子除去干扰因子，得到他需要的签名文件。这样，恐怖分子可以保证政府不知道他的新身份和潜逃地，同时政府也能保证恐怖分子不会耍诈。恐怖分子只有1/10的概率可以骗到政府，显然不值得恐怖分子去冒这个险。为安全起见，“10”这个数字还可以任意加大。
身份验证、中间人攻击和数字签名：浅谈密码学（下）
前面我们看到，签名具有不可伪造性，因此签名者可以很好的证明自己的身份。事实上，由于签名是不可伪造的，因此签名还有一个重要的功用。当一个人对某份文件进行签名后，这份文件便具有了法律效应：你今后无法再否认你签过这份文件，因为别人是不能伪造签名文件的。签名的这种性质叫做“抗抵赖性”。 在实际生活中，签名的抗抵赖性用的最多的场合就是签合同了。为了防止一方今后毁约，双方可以要求对方在合同上签名。此后，合同签署人的行为将受到这个签名文件的限制。一旦签名者想毁约，利益受到侵害的人便可以拿着这份合同大闹法庭，高举这份文件大叫“当初他签过名的”。 当签名用于抗抵赖时，新的问题产生了。签名的法律效应是如此之高，以至于人们往往不敢随意签名。一份合同往往同时规定了双方的权利和义务，并需要双方都在上面签名。第一个在上面签字的人就会觉得很亏：万一我签了字后对方突然翻脸耍赖不签了咋办？即使合同上规定“合同仅在双方均签署之后才有效”，这个问题仍然存在，因为后签名者将具有绝对的主动权，他想什么时候签就什么时候签，而只有他的签名才具有决定意义。因此很多时候，双方都希望能够在对方签名之后自己再签名，从而获得一些安全感。这里我们来探讨一个有趣的问题：有没有什么办法能够让双方同时签约，使得双方签名时都能确保自己的利益安全？ 如果我们谈论的是传统意义上的签名，同时签名当然是有可能办到的：双方只需要拿起各自的笔，同时在文件上写下自己的名字即可。当然，事实上肯定不会有人这么做。试想这样一个荒唐的画面：两个西装笔挺的人挤在一起，两只手臂磕磕碰碰地交错在一起，然后双方同时喊“三、二、一”并一起开始写字……比起自己丢掉的脸面，自己先签名所带来的忧虑还算个屁啊。 有没有体面一些的，不那么荒唐的同时签字法呢？这里有一个很有启发性的办法。合同双方面对面地坐在桌子的两端。其中一个人在合同上写下自己姓名的第一个字母，然后传给坐在对面的第二个人；第二个人写下他自己名字的第一个字母，然后又回递给第一个人；第一个人签下自己名字的第二个字母，又交给对方要求对方写下自己的第二个字母……以此类推，直到双方都签署完自己的名字为止。为了让双方能够“同时”签完，名字较长的人偶尔可能需要连续写下两三个字母。 双方都愿意履行这一协议，因为在这个协议下双方是一点一点地签完整个文件的。第一个写字的人不会觉得自己很亏，因为写下一个字母是远不具备法律效应的；如果对方拒绝签他的第一个字母，我可以当即撕毁合同。虽然他们都不知道，究竟要写多少个字母才算签字，但大家都保持自己签下的名字长度与对方基本相当，因此不会担心对方突然放弃协议。就在这种互动的心理过程中，签名的法律效应一点一点地增强，直到最后双方写完自己的名字。
但是，这个办法不能用于数字签名。利用RSA算法进行签名是一个整体的过程，不能分成一部分一部分地进行。能不能把合同拆成若干份，然后双方一份一份地逐个签名呢？当然不行。如果某一份合同里有一个至关重要的义务性条款，后签名的人等对方签到这里后便可以立即终止签名，从而谋取利益。那么，能不能规定“仅当你把所有n个部份的文件都签过了才算签”呢？这意味着最后一次签名才具有最终的决定意义，说穿了不过是把安全问题转移到了“谁签最后这一下”，问题实质上并未改变。其实，我们的解决办法相当简单。我们可以耍一个小花招，从本质上模拟上面的“逐字母签名法”。 首先，第一个人签署这样一份文件：“我愿意以1%的概率接受该合同”。第二个人检查第一个人的签名，然后在上面附加一句“我愿意以2%的概率接受这份合同”，并进行签名，回交给第一个人。第一个人检查对方已经签名，然后继续将这个条文升级为“我愿意以3%的概率签署该合同”并签名。双方来来回回签100次，直到最后第一个人签“我愿意以99%的概率签署这份合同”，然后轮到第二个人签署“我接受该合同”，最后再轮到第一个人签署“我接受该合同”。 注意，这个“接受概率”是有实际意义的。如果在第一个人第一次签完文件后，第二个人立即放弃继续签署，法官可能会要求双方进行一次公开抽签测试，选取一个不超过100的正整数。如果这个数恰好为1，那么签署这句话的人就相当于签署了这份合同。类似地，我们也可以约定，当一人声称将以百分之p-1的概率接受此合同，另一人声明以百分之p的概率接受时，法官可以要求双方共同生成一个1至100的整数：如果它不超过p-1则双方都接受，如果它的值比p大则双方都不接受，若它的值正好等于p则合同仅被后者接受。因此，这种协议实质上是用概率法再现了“逐字母签名法”的核心思想，将法律效应的问题进行量化，使得率先签名的潜在危险减小到了原来的百分之一。
这个协议看似有些可笑，但实际上是可行的。0.01是一个很小的数，双方都能接受，心理上都有保障。况且，签合同的双方通常并没有抵赖的企图，他们只是希望双方能够同时签署协议罢了。但是从密码学协议的角度来看，利用概率进行声明签署的做法确实不那么美观，它让人感觉有些跳出了密码学的理论范围，无法用密码学的语言符号进行规范。有人可能希望我们利用一些密码学手段来实现这种“小步进签名”。比如，双方可以把自己签名后的文件加一个密，然后两人一位一位地轮流宣读自己的密钥。具体地说，A可以想一个大数a，把自己签名后的文件异或a之后传给B；B也可以生成一个同样长的数b，异或自己签名后的合同后传给A。然后，A把a的第一位告诉给B，B把b的第一位告诉A；A再把a的第二位告诉B，同时B宣布b的第二位……直到A、B两人获得对方的全部密钥。事实上，即使你不知道对方的密钥，你也可以枚举对方的密钥进行暴力破解，只不过这个难度是密钥长度的指数级别。双方逐位交换密钥，目的就在于同步减小暴力破解所需的人力、物力和时间。这样，如果中途有人退出协议，两人枚举出对方签名后的文件的难度是相当的，这对双方都很公平。不过，这个协议并不能阻止某人撒谎。其中一方发送的可能根本就不是自己的合同签名，或者宣布自己的密钥时是随便乱叫的；但在整个协议完成之前，对方完全无法察觉出来。协议的思路是好的，不过在我们进一步完善这个协议之前，该协议没有任何使用价值。 回想起前面提到的恐怖分子一例。那个例子是很有启发性的，其思想可以广泛用于实现各种“反作弊”协议。我们可以把上面的协议稍作修改：A把合同拆成两份，然后分别进行签名，并声明“仅当某人可以同时提供签名合同的两部份才能证明我签署了这份合同”。然后，A生成两个大随机数a1和a2，把前一半签名合同异或a1，把后一半签名合同异或a2。A把两份干扰后的签名合同都传给B。B随机要求查看其中一部分合同的内容，向A索取a1或a2。A把B索要的密钥传给B，向B证明他之前传过去的是真实的合同内容。类似地，B也把自己的合同拆成前后两半并分别签名，然后异或两个不同的大数传给A，并按照A的要求宣布其中一个大数。此时，双方都只拥有对方一半的签名合同，并相信另一半（自己无法解开的）合同是真实的。但根据声明，只有一半合同是不算数的，对方必须同时拥有两部份签名合同才行。接下来，双方又像刚才那样逐位报出剩下那一半合同所对应的大随机数，直到对方获得全部密钥为止。 合同内容的真实性是保证了，但这仍然不能防止某个人在协议后期虚报自己的密钥。因此，我们还需要想一个办法，让双方在逐位报数阶段中不能作假。为此，我们希望双方都能知道对方密钥的其中一部分信息，以便验证对方宣读的密钥的真实性。上述协议中，我们之所以会被对方欺骗，原因就在于对方知道我现在知道了什么不知道什么。要是有办法能够收到对方的其中一个大数，却不让对方知道我收到了哪个大数的话就好了。这样的话，对方不得不老老实实地宣布这两个大数各是多少，因为他不知道我手里有哪一个数。
我们称这种特殊的数据传送方式叫做“不经意传输”(oblivious transfer)，意即我自己也不知道传过去了什么。上面这种传输需求有一个更确切的名字，叫做“1-2不经意传输”。在1-2不经意传输中，信息发送者可以准备两个不同的消息m1和m2（比方说，签名合同的前一半和后一半），接收人可以索要并获取m1和m2中的其中一个，但信息发送者不知道他要的是哪一个。实现不经意传输的方式非常巧妙。算法需要再一次用到RSA公钥加密术。首先，发送者生成两对不同的公私钥，并公开两个公钥。不妨称这两个公钥分别为公钥1和公钥2。假设接收人希望知道m1，但不希望发送人知道他想要的是m1。接收人生成一个随机数k，再用公钥1对k进行加密，传给发送者。发送者用他的两个私钥对这个加密后的k进行解密，用私钥1解密得到k1，用私钥2解密得到k2。显然，只有k1是和k相等的，k2则是一串毫无意义的数。但发送者不知道接收人加密时用的哪个公钥，因此他不知道他算出来的哪个k才是真的k。发送人把m1和k1进行异或，把m2和k2进行异或，把两个异或值传给接收人。显然，接收人只能算出m1而无法推测出m2（因为他不知道私钥2，从而推不出k2的值），同时发送人也不知道他能算出哪一个。发送人有一种办法可以作弊：他可以只发送其中一个真实的异或值（而编造另一个异或值），或者用k1和k2对同一个消息进行异或。不过这需要发送者能够猜出信息接收者最初选的是公钥1还是公钥2。如果接收人用公钥1对k加密，但最后得到的却是m2（或者什么都没得到），那发送人的企图就被识破了。
有了1-2不经意传输协议，我们之前的同步签名问题就彻底解决了。为了让协议更安全，我们还可以让双方各生成n份合同的拷贝，使得成功欺骗的概率仅为1/2^n。一个完整的同步签名协议如下： A、B双方各生成带编号的n份一模一样的合同，把每份合同拆成前后两半并分别签名。约定仅当对方同时获得了同一编号的两部分签名合同，合同才算被签署。A生成2n个大数，对他的2n份文件进行异或，然后全部传给B。B也做相同的事情。接下来，借助不经意传输，A向B索取其中的n个大数（对每个文件索要其中一个大数），类似地B也向A索取其中n个大数。此时，双方都能确定对方发来的文件是真实的，并且双方都不知道对方拥有了自己的每份文件的哪一半。接下来，A报出他自己的2n个大数中每一个数的第一位，然后B也报出他的每个数的第一位；然后，A报出每个数的第二位，B也报出每个数的第二位……直到双方报完所有数为止。 在上述协议的任一阶段里，A和B都不敢作假。发送虚假文件会在不经意传输完成后立即被发现，被欺骗者可以立即终止协议。虚报自己的大数也会穿帮，因为对方有其中一半的大数可用于核对，而你不知道他有哪一些大数。双方逐渐获得越来越多的大数位数，推测对方签名文件的难度同步减小，直到完全获得对方的签名文件。
我们以这个比较复杂的密码学协议来结束这篇一万多字的文章，目的是想展示一下密码学的科学性和复杂性。我们从身份验证说到了RSA算法，再谈到中间人攻击及其解决办法，最后讲了数字签名和两种特殊的签名方式——盲签名和同步签名。但这还远不到我想说的东西的一半。云风给我推荐了《应用密码学》，我当天晚上就在网上买了，第二天就抱到了文学史课上去看。从这本书里面我学到了好多好多科学的东西。还是那句话，密码学并不专注于数字层面的加密解密方法，而是专注于解决各种安全问题的方法。就像信息学中的算法一样，密码学协议中的算法也相当有趣，有些算法简洁实用，巧妙得有如神来之笔。信息传输的算法，其牛B性不亚于信息处理的算法。接下来我还想更新一些有趣好玩的密码学协议，相信大家会感兴趣的。