有趣的密码学与协议

来源

看到一篇自认为不错的文章分享给大家。选自《思考的乐趣：Matrix67数学笔记》 谈起”密码学“，大多数人的第一念头或许是摩尔斯电码、凯撒移位密码以及同音替换密码之类的东西。这些东西在各类小说中已经是老面孔了，“字母e在英文中出现的频率最高”等基本的破解密码已经是耳熟能详了。密码学关注更多的并不是加密解密的各种数学算法，二十在已有数学算法上如何实现各种安全需求。防止消息泄漏只是众多安全问题的冰山一角，二这个问题又有许多复杂的变化。 说起“消息泄漏”时，我们头脑中想到的往往是，在信息传输过程中如何防止被第三方截获。当然，小偷是防不住的，不过我们可以保证他偷到东西时也没用。双方只需要实现约定一套加密解密的方法，以密文的方式进行传输，这样便能防止消息泄漏。 例0 10个人坐在一起谈天，突然他们想知道他们的平均年薪是多少，但每个人都不愿意透露自己的工资数额。有没有什么办法让他们能够得出答案，并且不用担心自己的年薪被曝光？ 可以看到，密码学不仅仅研究加密解密的数学算法。更多的时候，密码学研究保护信息安全的策略，我们称之为“协议”。在已有的数学模型基础上，我们往往忽略数学实现方法，转而专注地研究借助这些数学工具能够构建的安全措施。除了消息的保密性意外，密码学还研究以西更加有趣的问题。这里，就让我们一起看几个有意思的密码学协议问题吧。 例1-0 设想一种场景：总部打算把一份密码文件发送给5名特工，但直接打文件原封不动的发给每个人，很难保证安全性。万一有提供背叛或者被捕，把密码泄漏给敌人怎么办？ 例1-1 此时，是否有办法能够让特工们可以恢复原文呢，即使一部分特工被抓住了？换句话说，有没有一种密文发布方式，只要5个人中半数以上的人在场就可以解开绝密文件？ 例2 3个好朋友到一家餐厅吃饭。饭快吃完的时候，一个服务员过来告诉他们说，他们的账单已被匿名支付了。3个人都尊重他人匿名付款的权利，但同时他们也想知道，这个匿名支付者是他们三位中的一个，还是他们三人之外的某个第四者。有没有什么办法能够让他们知道在他们中间是否有人付账，但又保证任何人都推测不出究竟是谁付的账？

抛砖引玉

其实，这个方案可以扩展到N个人。我们只需要证明，假如有N个人坐成一圈，如果大家都说真话，则说“不同”的次数一定是偶数次。证明非常简单。想象你从某一枚硬币出发，顺时针查看每一枚硬币的正反，得到一个硬币正反序列。每当这个序列由正变反或者由反变正时，就相当于有一处“不同”的情况发生。然而，当你绕着圆桌走完一圈，回到出发点时，硬币序列又变回了出发时的正反。因此，途中发生的“不同”次数一定是偶数次。 其实，抛掷硬币只是一个形象的描述方法罢了。在没有硬币，甚至大家根本没坐在一起的情况下，这个协议也很容易实施。比方说，先在网上公布整个协议规则，并约定一个虚拟的座位顺序；然后每个人都在1和2之间想一个数，并把结果以短信的形式发给他右边的那个人；最后每个人都按照协议规则，在网上发一个“相同”或者“不同”。 例3这个协议有一个意想不到的用途——匿名的消息广播。假如一群人围坐成一圈开会，会议过程中需要在场的一个不愿透露自己身份的人进行匿名发言。为此，大家可以统一采用上面的抛硬币协议（或者对应的电子协议，只是为了简便，下面还是采用抛硬币的说法）。发言人将信息编码为一个长度为n的01串。硬币投掷分n轮进行。第i轮中，其他人都严格按照实际情况报是否相同，发言人则根据编码信息的第i位的值来通报：若第i位为0，则按照实际情况通报；若第i位为1，则说与实际情况相反的词。这样，实际的信息就应该是每轮叫“不同”的次数除以2的余数形成的序列。 例4我们把最有意思的话题放在了最后。现在，假如你碰到了一个宣称可以预知未来的人，他说他知道下周的彩票中奖号码。你肯定不会相信，便用激将法让他说出下周的中奖号码：“你说出来啊，你要是说不出来，那就表明你不能预测未来。”不过，他却一本正经地说：“不行，我虽然能预测未来，但却不能把它说出来，否则会产生蝴蝶效应，改变这个宇宙既定的将来，导致危险的时空悖论。” 哈哈，这个“先知”真是天才呀！能预言未来却不能说出来，这样就永远不能证伪了。 不过，治他的方法也不是没有。比方说，可以叫他把预测结果写在一张纸上，锁进一个盒子里。然后，你拿走盒子，他拿走钥匙。彩票中奖号码公布后，你们再碰个头，把盒子打开，来看看当初的预测结果是否正确。这样便能让他做出一个谁都不能看见，但他今后也不能抵赖的预测。我们把这样的协议叫做“带有防欺骗的承诺”。 只可惜，这种方法有一个局限性：它只能在现实生活中使用。如果你在网上遇到了自称能预知未来的人，你如何让他做出防欺骗的承诺呢？ 有人可能会说，为什么不让他给预言加一个密呢？就像之前让他给预言加上一把锁一样。比方说，让他在下周的中奖号码上加一个很大的整数，然后把结果告诉你；这个很大的整数就是解开中奖号码的密钥，由他自己保管。仔细想想你会发现，这个方案显然不行，因为到了验证预言的时候，他可以谎报这个大整数，让密码解开来后是任何一个他想要的数。为了防止他耍赖，能否让他事先就把密钥公布出来呢？这也不行——知道了密钥后，你就能直接获得密码原文了，这样便失去了保密的作用。 注意到，传统的加密方法不能公开的原因就是，知道了加密方法也就知道了解密方法，只需要把加密方法反过来做就行了。有没有一种加密方法，使得即使你知道了加密的方法，也不能恢复出密码原文呢？有的。只需要在加密过程中加入一些不可逆的数学运算就行了。比方说，你们可以约定这样一种加密方法：先取中奖号码的正弦值的小数点后八位数字，得到一个八位整数；再求中奖号码与圆周率前六位数字形成的整数（314 159）之和，取该和的平方的第3位到第10位，又得到一个八位数；最后计算这两个八位数的和除以456 789的余数。假如他预言的中奖号码是1 234 567，那么对1 234567进行上面这一串操作后，将会得到244 685。但是，即使知道加密的过程，你也不能把244 685还原成1 234 567。事实上，1 234 567甚至不一定是唯一解，很可能有别的数加密后也会变成244685。上述加密方法能把任何数都加密成一个小于456 789的数，因此必然会出现不同的数加密成同一结果的情况。这就意味着，这种加密方法是会丢掉原始信息的。我们不妨把这种不可逆的加密方法叫做“单向加密”。在密码学中，MD5和SHA1是两种比较常用的单向加密算法。由于其单向性，这种加密方法不能用于普通的信息传输。但它有很多其他的应用，做出带有防欺骗的承诺便是一例。拿到244 685这个数后，你完全无法推出他究竟做了什么预测；到了验证预言的时候，只需要让对方宣布当初他的预测1 234 567，你来检验一下1 234567加密后是否会得到244 685就行了。 不过，这个方法有一个局限性：如果他宣称他能预测某只股票会涨还是会跌，上述方法就有漏洞了。比方说，你们可以约定，数字1表示股票会涨，数字2表示股票会跌，然后让他用刚才的那套方法把他的预测结果加密发过来。如果他告诉你的结果是316 554，那你只需要分别试一下1和2加密后分别得多少，就知道原始数据是1还是2了。原始数据的取值太有限，让穷举式的“暴力破解”变得易如反掌。怎么办呢？可以想办法硬把原始数据的取值范围扩大。比如，约定所有个位数字为1的数都表示股票会涨，约定所有个位数字为2的数都表示股票会跌。假如对方预测股票会涨，他可以选取任意一个末位为1的数，对其进行加密，这下你便没办法暴力破解了。不过，这里还有一个小问题：刚才我们说了，单向加密可能会把不同的原始信息加密成同一个结果，因此完全有可能出现这样两个数，它们的末位分别是1和2，但加密后的结果相同（虽然找到这样的例子并不容易）。为了避免对方手中持有精心构造的“两可解”情况，我们可以在每次实施协议时都改变一下协议的细节，比如每次都换一种单向加密方式，或者更好地，每次都要求对方选取的那个数必须以你想的某个随机数打头。这样一来，整个协议就完美了。 其实，这个协议并不只在揭穿超能力者的时候才有用。我们生活当中有很多地方都可以用到带有防欺骗的承诺。有一次，我在战网上和别人打星际，打出了一个非常搞笑的局面：两边的兵都一个不剩，两边的钱也都不够造东西了，双方都完全丧失了战斗能力。但是，双方都还剩有建筑，因此都不算输。此时，必须有一个玩家主动认输，先退出游戏，才能结束僵局。该谁先退呢？我和他便在游戏中互发消息谈论了起来。其实，在现实生活中，这很好解决：来玩一次石头剪子布就可以了。但是，怎么在网上玩石头剪子布呢？总不能让一个人先发消息说“我出的是剪子”，另一个人回复“哈哈，我出的石头”吧。这时候，就要用到带有防欺骗的承诺了。我们可以利用前面讲的方法，各自向对方承诺自己要出什么拳，然后双方再公布自己出的拳，让对方验证自己并没撒谎。更简单的方法就是，我在1和2之间想一个数，然后把我想的数加密告诉对方，由对方来猜我想的数是多少，猜对了我就认输退出，猜错了他就认输退出。对方做出猜测后，我再公布加密前的原始信息，以证明我没有耍赖。 例5 我们常常在电视上看到这样的一幕：一位老太太兴冲冲地走上台去，翻过3个商标牌，发现上面尽是5块钱、10块钱的小奖，垂头丧气地回到观众席；然后主持人会跑出来，边翻着另外几个牌子边说，1000元的大奖在这个后面，800元的在这里之类的。为什么主持人要演出“事后揭大奖”这一幕呢？道理很简单，节目组想通过这个“验证过程”告诉观众，这个环节不是骗人的，大奖真的就在这里面，只是刚才那家伙运气背了没摸到而已。摸奖前宣称有大奖，摸完奖之后还能证实大奖真的存在，这也是带有防欺骗的承诺。 例6 但是，我们喝饮料参与开盖有奖活动时，就会有被欺骗的感觉：你说中奖率是千分之一，我凭什么相信你呢？那么，有没有办法让开盖有奖活动的中奖率变得透明呢？有的。我就想过这么一个方法。比如说，开盖后你将得到一个参与活动的序列号，把这个序列号短信发送给活动举办方参与抽奖。此时，活动举办方的服务器从1到1000中随机生成一个整数，并把这个整数加上你指定的前缀和它自选的前缀，用公开的单向加密方法加密后发回给你。你需要猜出服务器生成的数是什么，如果猜对就能中奖，如果猜错就结束游戏。发送了你的猜测结果后，服务器将发来加密前的信息，确保自己没有撒谎。 密码学与协议的故事多得讲也讲不完。公钥加密算法、密钥交换协议、盲签名协议、投票协议、虚拟货币协议、中间人攻击……这些简直都是密码学中的珍宝。还没过瘾的读者，不妨买一本密码学与协议的书，继续研究下去。 我进行了删减，建议观看原文。微信读书上就可以看。