密码学协议举例[2]–带有防欺骗的承诺
摘要从生活中的例子来解读关于带有防欺骗的承诺，之后会说到两个个常用的方法，如MD5方法，并且会解读关于序列的随机性质。最后, 会给出三个对数据进行随机性测试方法, 来测试数据的随机性.
文章目录(Table of Contents)
Toggle
带有防欺骗的承诺现实场景网络上遇到的问题问题抽象解决办法: 使用如md5一类的单向散列函数上述方法可能存在的问题对于上述方法的修改另一种解决思路举例说明关于随机种子FIPS 140-1测试组随机性测试举例
带有防欺骗的承诺
这是密码学协议的第二篇文章, 上一篇文章的网址为: 密码学协议举例[1]–秘密共享的门限方案
现实场景
在很多综艺节目中，我们可以看到在抽奖环节(如一些砸金蛋，翻牌抽奖)，当嘉宾上台抽完奖之后，不管是否中奖，主持人都会把其余的几个选择也给观众看。那么为什么主持人要演出“事后揭大奖”这一幕呢？道理很简单，节目组想通过这一个“验证过程”告诉观众，这个环节不是骗人的，大奖真的就在这后面，只是刚才那家伙运气背了没摸到而已。摸奖前宣称有大奖，摸完奖之后还能证实大奖真的存在，这就是带有防欺骗的承诺。
网络上遇到的问题
但是上面同样的事情，在网络上却是办不到的。一个典型的例子就是sigusoft原来弄的那个恶心的砸金蛋砸银蛋。屏幕左边那个是银蛋，屏幕右边那个是金蛋，你鼠标选一个敲下去，看能否砸出sigusoft宠物来。大量测试表明砸出宠物的概率远远低于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的游程。该测试是先计算各种长度的游程个数。如果每个游程数量位于一定区间，则满足测试。
随机性测试举例
例：比较下面两个序列的随机性
序列一：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，而序列一中没有出现重复，故序列一比序列二具有更好的随机性。
激活谷谷主为您准备了激活教程，为节约您的时间请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/97883.html
