有趣的密码学与协议

有趣的密码学与协议

来源

看到一篇自认为不错的文章分享给大家。选自《思考的乐趣: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中随机生成一个整数,并把这个整数加上你指定的前缀和它自选的前缀,用公开的单向加密方法加密后发回给你。你需要猜出服务器生成的数是什么,如果猜对就能中奖,如果猜错就结束游戏。发送了你的猜测结果后,服务器将发来加密前的信息,确保自己没有撒谎。 密码学与协议的故事多得讲也讲不完。公钥加密算法、密钥交换协议、盲签名协议、投票协议、虚拟货币协议、中间人攻击……这些简直都是密码学中的珍宝。还没过瘾的读者,不妨买一本密码学与协议的书,继续研究下去。 我进行了删减,建议观看原文。微信读书上就可以看。
温馨提示:本文最后更新于2022-08-14,若文件或内容有错误或已失效,请在下方留言
© 版权声明
THE END
喜欢就支持一下吧
点赞8赞赏 分享
评论 抢沙发

请登录后发表评论