密码学协议举例-带有防欺骗的承诺|应用秘密学|密码学基础

王茂南

3043
文章

75
评论

2017年10月21日06:00:59

评论2 3375字阅读11分15秒

摘要从生活中的例子来解读关于带有防欺骗的承诺，之后会说到两个个常用的方法，如MD5方法，并且会解读关于序列的随机性质。最后, 会给出三个对数据进行随机性测试方法, 来测试数据的随机性.

文章目录(Table of Contents)

带有防欺骗的承诺

这是密码学协议的第二篇文章, 上一篇文章的网址为: 密码学协议举例[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测试组

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

单个位测试：测试组接收20000个二进制位，校验1和0的个数是否大致相等。若1的个数位于9654--10346，则通过测试。
扑克牌测试：将20000个二进制每四个二进制位一组，分成若干组，每组代表的十进制是0--15，若这个0--15也是均匀分布，则通过测试
游程测试：游程是指连续的0或1的序列。如0110111101，有一个游程的长度为2，即第2-3位的11，有一个游程的长度为4，即第5-8位的1111，此外还有四个长度为1的游程。该测试是先计算各种长度的游程个数。如果每个游程数量位于一定区间，则满足测试。