信息加密与单向函数及ras算法

《信息加密与单向函数及ras算法》由会员分享，可在线阅读，更多相关《信息加密与单向函数及ras算法（17页珍藏版）》请在金锄头文库上搜索。

1、信息加密与单向函数及信息加密与单向函数及 rasrasrasras 算法算法摘自 matrix67的博客密码学协议举例（一） ：带有防欺骗的承诺我们常常在电视上看到这样的一幕：一位老太太兴冲冲地走上台去，翻过三个商标牌，发现上面尽是5块钱、10块钱的小奖，垂头丧气地回到观众席；然后马脸李咏会跑出来，边翻着另外几个牌子边说，1000块的大奖在这个后面，800块的在这里，之类的。或许有人会纳闷了，为什么主持人要演出“事后揭大奖”这一幕呢？道理很简单， 节目组想通过这一个“验证过程”告诉观众，这个环节不是骗人的，大奖真的就在这后面， 只是刚才那家伙运气背了没摸到而已。 摸奖前宣称有大奖，摸完奖之后还

2、能证实大奖真的存在， 这就是带有防欺骗的承诺。但是，同样的事情在网络上似乎是办不到的。一个典型的例子就是QQ 原来弄的那个恶心的砸金蛋砸银蛋。屏幕左边那个是银蛋，屏幕右边那个是金蛋，你鼠标选一个敲下去，看能否砸出 QQ 宠物来。 大量测试表明砸出宠物的概率远远低于50%，让人质疑游戏的真实性。鬼知道它那个程序是不是真的预先指定了一个有宠物的蛋蛋， 很可能不管你点了哪个蛋蛋结果都一样， 系统按照概率直接显示出抽奖结果来。当然，怀疑游戏的公平性也没办法，要想在网络上实现带防欺骗的承诺是比较困难的， 毕竟让你看一段从另一个蛋蛋里跳出一个宠物的 Flash 动画不能让你相信刚才你是真的“选错”了吧。我

3、们的问题就是： 如何设计一个协议， 用以保证一个二选一的网络互动抽奖游戏的真实性？换句话说， 假如你选择了金蛋， 结果没有中奖，那么系统如何能够令你相信奖品刚才真的在银蛋里？md5一类的单向散列函数（主页菌注：普通的函数，比如 y=2x，给出输入 x=1,得到 y=2;给出输出 y=2，也很容易得出 x=1；可是对于这种单向函数，给出 x=1。比较容易得出 y=2。可是反过来，给出y=2，很难算出 x 是多少）提供了一个不错的方案。系统首先随机选择一个蛋（比如银蛋） ，在蛋里面藏好奖品，然后把单词“silver”连同一个随机字符串（比如“jq548s”）进行 md5。在你抽奖之前，把这个md5

4、值先告诉你。然后你砸蛋，发现金蛋里没有奖品。此时，系统宣布字符串“silverjq548s”，你计算它的 md5值，发现和之前系统告诉你的一模一样。 此时， 你便相信系统刚才是真的把奖品藏在银蛋里了。若你刚才真的砸了银蛋，那系统就没办法抵赖了，因为 md5函数是一个单向的、不可逆的、不可预测的函数，想要构造一个“golden 某某某”形式的， 且 md5值和刚才一样的字符串， 那比登天还难。另外，注意到在单词后面添加随机字符串这一步骤是必须的， 否则你可以尝试计算“silver”和“golden”各自的 md5值，从而获知哪个蛋里面有奖品。不过，现在看来，这个协议也不可靠了。系统有一个办法可以

5、耍赖：字符串“jq548s”有可能根本不是随机生成的，而是经过一系列精心构造的。我们不能排除这样一种情况， 即我们可以通过某种算法构造出一对字符串 xxx 和 yyy， 使得“silverxxx”和“goldenyyy”的 md5值是一样的。md5被破解后，造成这种“碰撞”更是轻松，并且同一对碰撞还可以反复用于欺骗不同的用户。 其中一个解决办法是，你可以在协议最初时生成一个自己的随机字符串发给系统，并要求系统传回“silver/golden”+ 系统生成的随机串 + 你自己传过去的随机串 三者并在一起后的 md5值。用户一旦参与了字符串的构造，系统作弊就变得真正棘手了。还有没有什么其它办法呢？

6、我在 应用密码学里看到了一个颇有意思的协议， 它用伪随机序列来代替单向散列函数。 不妨把银蛋标为数字“0”，金蛋标为“1”。在砸蛋之前，你给系统发一个足够长（比方说100位吧）的随机01串 A。然后，系统把奖品藏在标号为 X 的蛋里。下面，系统选择一个随机种子，通过伪随机数列发生器生成100个随机数， 并全部模2得到一个100位的随机01串 B。 然后系统计算01串 C，其中Ci = Bi 当 Ai为0Ci = Bi xor X 当 Ai为1系统把 C 传给你，并宣布准备完毕，开始抽奖。事后，系统公开自己选取的随机种子的值，你便能还原序列 B，验证序列 C 是否和系统之前所给的一样。 （主页菌

7、注：这一招相当于一把锁需要两把钥匙同时存在才能打开，开奖之前先给你一把，开奖之后再给你另外一把， 只有两把钥匙都完好，锁也没被换，两把钥匙才能顺利地把锁打开）如果系统想作弊的话，这要求系统能寻找两个不同的随机种子 s1和s2，使得在由它们生成的随机01串（的前100位）中，A 中等于“0”的位置上它们的值全部相等，A 中等于“1”的位置上它们的值正好相反。但伪随机数列发生器的行为是不可预测，找到这样的 s1和 s2相当困难，目前看来该协议仍然是安全的。即使找出了这样的碰撞， 这样的努力也是一次性的， 因为当别的人来抽奖时， 随机串 A 又不一样了，刚才的碰撞就完全没用了。密码学协议举例（二）

8、：秘密共享的门限方案电影中经常出现这样的情节：有一份绝密文件需要交给5位特工，为了防止某个特工被捕或者叛变，5名特工各自只持有其中1/5的文件（更好的做法是只持有其中1/5的密钥） ，这5名特工需要同时在场才能获取文件全文。但这也有一个隐患：如果真的有特工被抓了，当坏人们发现只拿到其中一份文件没有任何用处的同时， 特工们也会因为少一份文件无法解开全文而烦恼。此时，你或许会想，是否有什么办法能够让特工们仍然能够恢复原文， 即使一部分特工被抓住了？换句话说，有没有什么密文发布方式使得，只要5个人中半数以上的人在场就可以解开绝密文件？这样的话， 侵入者必须要能操纵半数以上的特工才可能对秘密文件造成实

9、质性的影响。 这种秘密共享方式被称为(3,5)门限方案，意即5个人中至少3人在场才能解开密文。实现(m,n)门限方案的一个传统办法是，把这份文件的密钥（主页菌注:文件被加密成乱码之后， 相当于一把锁， 把锁打开需要的password相当于钥匙，就是密钥）拆成 C(n,m-1)份，每个人持有 C(n-1,m-1)份密钥。在(3,5)门限方案中，我们需要 C(5,2)=10个密钥，不妨分别用0到9编号；5个特工各持有6个密钥，密钥的分配如下：特工#1: 012345特工#2: 012 678特工#3: 0 34 67 9特工#4: 1 3 56 89特工#5: 2 45 789上述分配表的构造其实

10、很简单： 为特工的每一种5选3组合分配一个密钥，例如把密钥0分给特工1、2、3，把密钥1分给特工1、2、4，把密钥9分给特工3、4、5。这样的话，任意两个人在场都无法打开文件，因为他们始终缺少一把钥匙（这把钥匙分给了其余三个人） 。而任意三个人在场都足以打开文件， 因为根据鸽笼原理， 任何一个5选3组合中总有一个人落在这三个人当中。 这样， 我们便利用组合数学巧妙地解决了这一问题。在密码学中，我们有一些更精妙的方案。最巧妙的方法是，把秘密文件编码为三维空间中的一个点，然后生成5个过该点的平面，每个特工持有其中一个平面方程。显然，两个特工在一起是无法获得原文件的， 因为两个平面的公共点有无穷多个

11、； 但三个平面的交点是唯一的，因此任意三个人在一起都能解开原文件。另一个有趣的办法利用了下面这个事实： 知道 m-1次多项式函数上的任意 m 个点就能恢复出整个多项式。因此，我们可以把文件编码为一个二次多项式 f，然后把 f(1)、f(2)、f(3)、f(4)和 f(5)的值告诉对应的特工。 任意三个特工碰头之后， 只需要解一个三元线性方程即可恢复原文件。多项式的这一性质还曾用于数据备份当中。利用数论知识我们还能得到一个简单的协议。中国剩余定理告诉我们， 给出 m 个两两互质的整数，它们的乘积为 P； 假设有一个大整数M，如果我们已知 M 分别除以这 m 个数所得的余数，那么在0到 P-1的范

12、围内可以唯一地确定这个 M。我们可以想办法构造这样一种情况，n 个数之中任意 m 个的乘积都比 M 大，但是任意 m-1个数的乘积就比 M 小。这样，任意 m 个模数就能唯一地确定 M，但 m-1个数就不足以求出 M 来。 Mignotte 门限方案就用到了这样一个思路。 我们选取 n 个两两互质的数，使得最小的 m 个数的乘积比最大的 m-1个数的乘积还大。例如，在(3,5)门限方案中，我们可以取53、59、64、67、71这五个数，前面三个数乘起来得200128，而后面两个数相乘才4757。 我们把秘密文件编码为一个4757和200128之间的整数，比如123456。 分别算出123456

13、模上面那五个数的结果， 得到19、 28、0、 42、 58。 显然， 知道任意三个同余方程就可以唯一地确定出123456，但仅知道两个方程只能得到成百上千个不定解。例如，假设我们知道了 x 模59等于28，也知道了 x 模67得42，那么我们只能确定在0到59*67-1内的解913，并且只能断定 M 是一个形如59 * 67 * k + 913的数，其中 k 的数量级和当初选的那五个数一样大。密码学协议举例（三） ：另类的密钥交换协议密钥是密码的命根，一切不安全的秘密交换都源于不安全的密钥交换。目前，绝大多数协议采取 RSA算法进行密钥交换，但在 RSA 算法出现之前，人们又是怎么做的呢？据

14、说， 第一个密钥交换算法是一个名叫 Ralph Merkel 的人在1974年发明的，算法叫做 MerklesPuzzles。这是一个非常奇特、非常邪恶的密钥交换协议。假设 A 和 B 想进行秘密通信， 他们需要选取一个密钥。A 准备好很多很多个形如“密钥编号为 X_i，密钥是 Y_i”的消息，其中 X_i 是一个随机标识符，Y_i是一个随机密钥。消息的个数越多越好，起码要有几十万几百万条。然后，A 把这些消息都编码为一个个难题，比方说对第 i 条消息异或一个大质数 P_i， 并宣称 P_i 是某个数 N_i 最小的那个质因子。A 把所有编码后的消息全部发给 B。B 收到这些消息之后，随便选择

15、一条消息进行暴力破解（在上例中就是暴力分解某个 N_i）（主页菌注：暴力破解就是一个一个地试，试遍所有可能性） ，得到某一对对应的 x 和 y。 B 用明文给 A发一个消息， 说“我们就用编号为x 的密钥吧”。由于 A 知道这个 x 对应的是哪个 y，因此 A 知道 B 说的密钥是哪个。这个协议的核心就是， 第三者不知道 B 当时选的是哪条消息。 如果有第三者截获了他们之间的通信，要想获得密钥 y，他必须一一破解所有的难题， 直至解开了那个编号为 x 的密钥消息。 由于这样的难题数量大得惊人， 第三者要花费的努力是 B 的上百万倍。 假如用计算机暴力破解一个难题需要一个小时的时间，那么第三者即

16、使有百倍于 B的计算能力，他也需要平均一年多才能解到正确的 x 和 y。密码学协议举例（四） ：秘密数字的比较让我们来看一个很实用的问题： A 和 B 两位女士希望知道她们俩哪个年龄大，但又都不愿意透露自己的年龄。有什么方法能够让她们在不泄露年龄的情况下比较出年龄大小呢？我们假设双方都是诚实可信的。 她们会严格遵守协议并且不会撒谎。她们唯一不希望做的仅仅是泄露自己的年龄。不妨设 A 的年龄为 a，B 的年龄为 b。为简便起见，假设这两个数都是21到30之间的整数。下面这个协议可以让双方比较出 a 和 b 的大小，而不透露 a 和 b 的实际值。这个协议也不需要第三方的参与。协议开始前，B 生成一对 RSA钥匙，例如 n=3233, e=17, d=2753。首先，A 选取一个大随机数 x，比方说1117。A 用 B 的公开钥匙给随机数1117加密，得到密文1652。A 把1652减 a 的值发给 B。如果 A是一个22岁的漂亮 MM，那么 B 实际接收到的数就是1630。接下来，B 尝试用私人密钥来恢复 x。由于 B 不知道 a 是多少，于是B 枚举所有2