密码学协议举例[2]–带有防欺骗的承诺

王 茂南 2017年10月21日06:00:59
评论
2 3375字阅读11分15秒
摘要从生活中的例子来解读关于带有防欺骗的承诺,之后会说到两个个常用的方法,如MD5方法,并且会解读关于序列的随机性质。最后, 会给出三个对数据进行随机性测试方法, 来测试数据的随机性.

带有防欺骗的承诺

这是密码学协议的第二篇文章, 上一篇文章的网址为: 密码学协议举例[1]–秘密共享的门限方案

 

现实场景

在很多综艺节目中,我们可以看到在抽奖环节(如一些砸金蛋,翻牌抽奖),当嘉宾上台抽完奖之后,不管是否中奖,主持人都会把其余的几个选择也给观众看。那么为什么主持人要演出“事后揭大奖”这一幕呢?道理很简单,节目组想通过这一个“验证过程”告诉观众,这个环节不是骗人的,大奖真的就在这后面,只是刚才那家伙运气背了没摸到而已。摸奖前宣称有大奖,摸完奖之后还能证实大奖真的存在,这就是带有防欺骗的承诺

 

网络上遇到的问题

但是上面同样的事情,在网络上却是办不到的。一个典型的例子就是QQ原来弄的那个恶心的砸金蛋砸银蛋。屏幕左边那个是银蛋,屏幕右边那个是金蛋,你鼠标选一个敲下去,看能否砸出QQ宠物来。大量测试表明砸出宠物的概率远远低于50%,让人质疑游戏的真实性。鬼知道它那个程序是不是真的预先指定了一个有宠物的蛋蛋,很可能不管你点了哪个蛋蛋结果都一样,系统按照概率直接显示出抽奖结果来

当然,怀疑游戏的公平性也没办法,要想在网络上实现带防欺骗的承诺是比较困难的,毕竟让你看一段从另一个蛋蛋里跳出一个宠物的Flash动画不能让你相信刚才你是真的"选错"了吧

 

问题抽象

如何设计一个协议,用以保证一个二选一(或者多选一)的网络互动抽奖游戏的真实性?换句话说,假如你选择了金蛋,结果没有中奖,那么系统如何能够令你相信奖品刚才真的在银蛋里?

 

解决办法: 使用如md5一类的单向散列函数

  • 系统首先随机选择一个蛋(比如银蛋),在蛋里面藏好奖品,然后把单词"silver"连同一个随机字符串(比如"jq548s")进行md5。
  • 在你抽奖之前,把这个md5值先告诉你。
  • 你砸蛋,发现金蛋里没有奖品。此时,系统宣布字符串"silverjq548s",你计算它的md5值,发现和之前系统告诉你的一模一样。此时,你便相信系统刚才是真的把奖品藏在银蛋里了。
  • 若你刚才真的砸了银蛋,那系统就没办法抵赖了,因为md5函数是一个`单向的`、`不可逆的`、`不可预测的`函数,想要构造一个“golden某某某”形式的,且md5值和刚才一样的字符串,那比登天还难。
  • 注意:在单词后面添加随机字符串这一步骤是必须的,否则你可以尝试计算“silver”和“golden”各自的md5值,从而获知哪个蛋里面有奖品。

 

上述方法可能存在的问题

系统有一个办法可以耍赖:字符串“jq548s”有可能根本不是随机生成的,而是经过一系列精心构造的。

我们考虑下面这种情况:

我们通过某种算法构造出一对字符串xxx和yyy,使得"silverxxx"和"goldenyyy"的md5值是一样的。(md5被破解后,造成这种“碰撞”更是轻松),并且同一对碰撞还可以反复用于欺骗不同的用户。

 

对于上述方法的修改

对于上面的方法,我们可以做出如下的修改,就可以避免上述问题的发生。

你可以在协议最初时生成一个自己的随机字符串发给系统,并要求系统传回 ("silver/golden" + 系统生成的随机串 + 你自己传过去的随机串) 三者并在一起后的md5值。用户一旦参与了字符串的构造,系统作弊就变得真正棘手了

修改后的步骤如下:

系统要求你输入一个随机数

  • 接着系统随机选择一个蛋(比如银蛋),在蛋里面藏好奖品,然后把单词“silver”+系统随机生成的字符串(比如“jq548s”)+你自己上传的字符串(比如"+bupt2016")进行md5。
  • 在你抽奖之前,把这个md5值先告诉你。
  • 你砸蛋,发现金蛋里没有奖品。此时,系统宣布字符串“silverjq548s+bupt2016”,你计算它的md5值,发现和之前系统告诉你的一模一样。此时,你便相信系统刚才是真的把奖品藏在银蛋里了。
  • 这是系统就无法通过自己构造形如“silverxxx”和“goldenyyy”,并使得其md5值是一样的来欺骗用户。因为此时随机数是用户及时输入的,如果初始系统是用“silver+xxx+用户输入的随机数”来计算md5值的,接着系统就要计算,yyy,使得“golden+yyy+用户输入的随机数”与“silver+xxx+用户输入的随机数”的md5值一样的,这时系统就不能事先准备好xxx和yyy了。即使系统找出了碰撞,这种碰撞也是一次性的,因为当下一个人来是,他输入的随机数是不一样的。

 

另一种解决思路

这种方法是在《应用密码学》里提到的一种协议,它用伪随机序列来代替单向散列函数。不妨把银蛋标为数字"0",金蛋标为"1"。在砸蛋之前,你给系统发一个足够长(比方说100位吧)的随机01串A。然后,系统把奖品藏在标号为X的蛋里。下面,系统选择一个随机种子,通过伪随机数列发生器生成100个随机数,并全部模2得到一个100位的随机01串B。然后系统计算01串C,其中

  • C[i] = B[i] 当A[i]为0
  • C[i] = B[i] xor X 当A[i]为1

系统把C传给你,并宣布准备完毕,开始抽奖。事后,系统公开自己选取的随机种子的值,你便能还原序列B,验证序列C是否和系统之前所给的一样。

如果系统想作弊的话,这要求系统能寻找两个不同的随机种子s1和s2,使得在由它们生成的随机01串(的前100位)中,A中等于"0"的位置上它们的值全部相等,A中等于"1"的位置上它们的值正好相反。但伪随机数列发生器的行为是不可预测(随机数发生器是不可预测的是关键),找到这样的s1和s2相当困难,目前看来该协议仍然是安全的。即使找出了这样的碰撞,这样的努力也是一次性的,因为当别的人来抽奖时,随机串A又不一样了,刚才的碰撞就完全没用了。

 

举例说明

例子:假如说奖品在银蛋中,则X=1,我生成了随机数列为A,系统生成的为B,计算出C,其中A,B,C如下

A | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1

B | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1

C | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1

开始抽奖前,我收到随机序列C。

在抽奖结束后,系统会给我随机种子的值,这时我就可以还原B,进而还原C,来比较是否与系统初始给我的C相同。

此时如果系统耍赖,你砸了银蛋,但系统告诉奖品在金蛋里

则此时B为0110100010,我们要找到一个随机种子使其生成如上的随机序列是困难的,故此方法可以防止系统作弊。

 

关于随机种子

想法:从一个短的密钥产生一个随机的密钥序列. 例如可以使用线性反馈移位寄存器.

例子:初始为11010011,单位2和单位5的内容进行XOR逻辑运算(XOR逻辑运算是指(A+B)Mod2)

 

移入 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 移出

| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |

1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1

0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1

1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0

最后移出位作为随机数输出。

典型的序列密码算法:RC4算法,A5算法,SEAL算法,SNOW2.0算法,WAKE算法

 

FIPS 140-1测试组

有下面三种随机性的测试方法:

  1. 单个位测试:测试组接收20000个二进制位,校验1和0的个数是否大致相等。若1的个数位于9654--10346,则通过测试。

  2. 扑克牌测试:将20000个二进制每四个二进制位一组,分成若干组,每组代表的十进制是0--15,若这个0--15也是均匀分布,则通过测试

  3. 游程测试:游程是指连续的0或1的序列。如0110111101,有一个游程的长度为2,即第2-3位的11,有一个游程的长度为4,即第5-8位的1111,此外还有四个长度为1的游程。该测试是先计算各种长度的游程个数。如果每个游程数量位于一定区间,则满足测试。

 

随机性测试举例

例:比较下面两个序列的随机性

序列一:111100010011010

扑克牌测试:四位二进制:1111,1110,1100 ... ... 转化为十进制后的结果15,14,12,8,1,2,4,9,3,6,13,10,5,11,7

序列二:001101000100111

扑克牌测试:转化为十进制后的结果3,6,13,10,4,8,1,2,4,9,3,7,14,12,9

 

解释:从上面可以看到,单个位测试两个序列含有的0和1的个数相等,但是分组后转换为十进制时,序列二中出现了重复3,而序列一中没有出现重复,故序列一比序列二具有更好的随机性。

  • 微信公众号
  • 关注微信公众号
  • weinxin
  • QQ群
  • 我们的QQ群号
  • weinxin
王 茂南
  • 本文由 发表于 2017年10月21日06:00:59
  • 转载请务必保留本文链接:https://mathpretty.com/8524.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: