送宝石游戏考题

大龙虾就算了...小龙虾行不行？

这个，嗯...使用不可逆的函数。似乎这样的话的确完美无缺...不过说不定我前面提出的破解方法只是针对你的设计的特解，说不定还存在另外一种更通用的破解法，可以无需求解那个a...

小龙虾 …… 这东西不是日本人搞来净化污水的么 …… 这样吧，干脆我去查一下澳洲龙虾的均价，你就按 250 克重的标准给我汇款如何？:wink:

这个方案是安全的，我可以简单地给个证明：从协议的步骤上可以看出，邮差要想得到我手里的 r1 ，必须先构造 r2' 给我；同样，他要想得到我朋友手里的 r2，必须先构造 r1' 给他。因此，如果排除这个邮差狗运奇好猜中数字的情况，要么 r1!=r1' ，要么 r2!=r2' 。到最后，邮差要想拿到宝石，必须在计算结果上骗过我，也就是说，他给我的数字必须等于 md5(r1, r2', a) 。而这个时候他所能知道的全部信息，是 r1/r2/r1'/r2' 和 md5(r1', r2, a) 。由于 md5 的不可逆性质，他无法得到 a ，而且 r1/r1' 、r2/r2' 两对数字中必有一对不同，所以他不可能成功计算 md5(r1, r2', a) 。

其实更好的方案是采用 md5(r1+r2+a) ，这样即使这个邮差拥有 N 台超级计算机可以用穷举法来强攻 md5 ，他最多也只能得到一个 a' 满足 md5(r1'+r2+a') 等于他从我朋友那里得到的 md5(r1'+r2+a)，但是由于 md5 是压缩映射，存在无限多个数字的 md5 值与之相同，而且他完全没有任何线索来判断这个 a' 是不是就是原来那个 a ，换句话说，他还是无法构造出骗过我所需的 md5 值来。

嗯嗯，当然这个方案在数学上不是完整的，我无法证明不存在一个巧妙的算法和一对巧妙构造的 r1'/r2' 来攻破我所依赖的 md5 ，更严格的系统应该对 r1 和 r2 的取法做些规定，最好是采用数学上证明了性质的函数。

不过呢，这个问题说到这里，应该已经可以看出许多密码学领域的独特玩法了，包括随机数的运用，包括把攻破我的通信方案同解决某个数学问题等价起来，等等等等，还是很有意思的。有兴趣的人真该看看，毕竟这些才是人类智慧最纯粹、最天才的一面，也是人类最接近造物主的地方。

@ Elminster
很精彩!

我给一个:
前提:
我是一个魔法师,我在我送出的东西上施加了一个保护魔法,一旦有任何evil的事物破坏,它都回自动回到我的手中.
实现:
第一次送装了宝石的box,第2次送唯一的钥匙.
其中任何一次,postman如果有evil的动作,东西回到我的手中.
我再重新post,post.....................成功为止.
---------------
现实中,这个魔法的实现就是量子力学的原理:观察会干扰被观察系统的量子态.
即在我和朋友的传输中,postman的任何监听,破坏,都会应信道干扰而被发现,我将丢弃本次传输,重新post............
这个就是简单的量子密匙分配,现在有很多的量子密码协议了,和经典的思路有很大区别.当然,我的描述可能不完整,只是想引起大家的兴趣.

ps:md5的对冲,也许在经典的串行计算机中有效算法实现很困难,但是并行机,生物机,量子机中,也许能找到有效算法.
其实这里还可以思考一个:有限和无限的问题?很有意思.

量子啊，那个玩法完全不同的。它有个巨大优势就是任何对信道观测的尝试都会被发现，这个非常好使，不过也有一些不好的地方，有些东西做不出来，比如 oblivious transfer 。至于说 md5 么，其实现在大家对这东西的性质基本上还是不了解，只是用而已 —— 这个是 CS 里面很多问题的特点，太难以至于完全没有理论上可以保证的结果。

说到并行计算、生物计算、量子计算么，并行计算是没啥花样的，工程实践上作用很大但不可能打破复杂性类的界限；生物计算我不了解，不过貌似也很久没听到有什么进展了；量子计算研究过一阵子，很有意思的东西，不过做到现在也没有太多真正意义上的突破性进展，最好的已知结果和传统图灵机之间也就是平方规约关系。

唉，不过这 javaeye 里没什么人对这个有兴趣，大家都忙着玩儿框架啦、设计啦、需求啦、软件工程啦，这些东西 ……

图灵机目前还是最强的。
图灵论题说：任何的计算模型实现的有效算法，Turing机也可以实现
不过由于随机法算素数，图灵论题也就变成了加强版本：概率Turing机！

目前的量子Turing机可以相当于概率Turing机。
目前的其他计算模型，经典串行，并行，分布，生物（分子）都不能超越Turing机的水平。
模拟机如果在理想情况下，比Turing机好，可惜有噪声！我一直都喜欢模拟，不喜欢数字。模拟的世界可以是无限的世界，数字化的世界是有限的世界。

量子机是最有希望了，可以说量子机有模拟机的无限优势，又可以将噪声有限化。集合数字和模拟的的特点。
-------------------
可惜量子计算和信息理论上的进度，远大于实验进步。
目前量子密码学上，主要的工作还在私匙的分配(比如这里讨论的postman问题)，量子签名这些都还很远。
=========
目前实验的落后，还是要怪物理学，21世纪初的物理界，已经没有了群星闪耀的天空。

有时候我都在想：那些天才横溢的家伙，难道都去做企业应用了？？？？？？？？？？

概率图灵机倒是没什么花样，虽然还没有证明，不过人们一般认为 ZPP 等于 P 的，那样的话 RP / CoRP / BPP 这些就都塌掉了。这个方向倒是有希望出现些重要结果，前几年普遍被认为是 RP 中典型问题的素数判定问题有 P 算法了，可能带来突破。

量子计算么，还没研究透，虽然模型已经完善了，但是它的计算能力和经典图灵机之间的关系有待继续发掘。

模拟机就不属于我们一般意义上的“计算机”这个范畴了，那是另外一类东西。另外要说它能够做到真正意义的无限，也还难说得很 ……

@ Elminster

呵呵，现在的量子计算机啊，大牛们都说一切皆有可能！不敢定论啊。
---------
我们的讨论，不过希望能引起点大家感点兴趣了,不过，看来比较失败ing.........
还是推荐一本书:
Quantum Computation and Quantum lnformation
有中译本.
建议最好有一些量子力学背景

T1老大发言：