送宝石游戏考题

你说的没错，所以我才强调这个问题需要严格地描述一下。另外你这个办法不够好，自己搞海量的箱子也是很花钱的，要知道运费是和运送的物品体积重量成正比的，:P

第一次，postman复制A的钥匙，将原A的钥匙送给你的朋友
第二次，postman伪造相同的盒子，并且用A的钥匙打开A锁，锁索在伪造的盒子上送给你的朋友。（你的朋友用钥匙能打开A锁，验证出是“真的”盒子）
第三次，用B的钥匙打开盒子得到宝石。

直接送，朋友收到后强行break盒子得到宝石。

这道题目就是这样子的了，我碰到的就是这样描述的。
感觉确实是缺乏一些严格界定。网上也搜不到类似的题目。

只送一次肯定朋友和postman是等价的，但是多次的话，朋友手中可能
留有一些东西或者朋友和我有什么约定，这样的话postman和朋友就不完全
等价了。

我的回答是这么考虑的：

题目的关键点是，postman能不被发觉而经济的获得货物。如果他觉得会被发现，或者吞没了货物也无法获得里边的价值，那他就不会下手，而老老实实的送货物。－－理性人兼经济人

这样，题目可以等效于在透明的internet上传递私密信息，而不丢失

首先看前提，这是题目没有交代的：我和朋友能否通讯

假设能，这题没有任何难度。只需要告诉朋友货物信息，这相当于一个数据校验，那postman无法下手，因为他下手的前提是：不留痕迹，即双方都无法察觉。显然，我和朋友能通讯的前提下，postman不可能下手而不被发现。
这样直接送宝石就完了。

假设不能通讯，也就是没有校验回馈机制，这时只能对货物加以保护——等效于加密。加锁和开锁也就等效于加密与解密。


由于我和朋友无法通讯，那可以选择把钥匙和箱子一起发送（1次）或者分开发送（多次）。由于没有数据校验及回馈机制，无法保证数据的接收顺序——这也是internet上的情况。所以分开发送解密钥匙与加密数据包，无法保证不被postman截取。

选择一次发送，则需要选择加密方式。
加密方式有2种，对称和非对称——相当于有几条钥匙。

对称式加密加密只有一条钥匙，一次发送肯定不行。

非对称式加密虽然有分公钥私钥，但必须保证，发送方有接受方的公钥。

再看题目，题目说还有任意的锁。这个条件转化成逻辑表达式就是，我有锁的集合及相应的钥匙集合。这样，我就肯定拥有了朋友拥有的锁及钥匙——有了公钥。

这样就可以挑一个我朋友也有的锁，即他有钥匙的锁进行加密。

让我们看另一种情况：让朋友break。这个情况比较特殊，会引入更多的假设。等价于发一个加密信息让朋友解密，由于没有锁及箱子强度（即加密强度）和朋友破坏力（暴力破解能力）的判断信息，可以分3种情况：
朋友能够braek，而postman不能，这样引入了无法判定的假设
朋友可以，postman也可以，由于没有校验回馈机制，postman可以break而不被发现，直接吞没
2人都不能，白玩



这类题目不能脱离题目引入新的假设，如果要引入，也必须对其进行逻辑分析，保证不会矛盾，自相矛盾的排除，不可判断的排除，不然什么乱七八糟的情况都能出现。

我的推理也有1个问题：我的朋友可能没有锁的情况，即出现空集，只是这样的机会比较小，所以也有点说不过去。

怀疑题目本身就没有经过严格的推理检验，但由于这是面试中出现的题目，很有可能是用来测试面试者思维方式的问题，这样的面试估计只有大公司才会做

这样么？我怀疑这题目在流传过程中可能丢失了一部分。如果如我所猜测这题目是某个带有密码学背景的同学给出的话，应该是设计得比较完整也比较有意思才对。

其实这类问题可以是很好玩、同时又很有实际意义的一种游戏。简单地说，对于现在的电子商务而言，要解决的就是这类问题：参与这个电子商务的双方需要互相传递一些保密的有巨大价值的信息，但是整个通信信道是不可信的（internet）甚至可能是恶意的，入侵者可能可以在通信双方的中间任意地采集、复制、篡改数据、模仿双方的行为，然后试图获得这些数据。所以此时的任务就是如何构造确保是安全的通信协议。

啊啊，还是回来说这个游戏。如果你和你朋友，在事先没有任何共享的秘密的知识（邮差不知道的东西），同时在邮递过程中无法通信的话，那么显然这个问题是无解的。因为邮差可以扣下所有你发出去的东西，伪装成你的朋友和你“通信”，而你无法区分这两者。可以这么说，你的朋友和邮差是等价的。所以我们必须要假设，在通信开始之前，你和你朋友之间有一些你们两的“小秘密”，呵呵。比方说最简单的，你有一把锁，而你朋友有钥匙，那么你只要把宝石锁在盒子里面送过去就行了，邮差绝对无法拿到宝石 —— 别笑，大名鼎鼎的 SSL 就是这种玩法。

OK，我们怎么也得比搞 SSL 的那帮人要强点才行，所以换种稍微高级一点的玩法：

1、你和朋友都知道一个秘密的数字，这是你们两人之间的小秘密，
2、你和朋友都有足够数量的锁、与之相配的钥匙、坚固的箱子（锁上之后是不可能砸开的）。
3、现有贪婪的邮差一名，你和朋友只能通过他通信，任何东西都要通过他转交。这个邮差很能干，可以毫无代价地复制钥匙和锁，而且他也有和你们一模一样的箱子。但只有锁的情况下，他是配不出钥匙的 —— 当然也就无法打开上锁的箱子了。

现在要你设计一种通信方案，最终使得这个邮差除非狗运奇好（比如蒙对你们的秘密数字），否则就没有可能拿到宝石。注意哦，你的通信方案这个邮差是完全了解的，可以针对性的设计自己的行动模式，而且你和朋友之间除了这个邮差，完全没有其他通信方式，换句话说，如果邮差扣下了你的东西或是交给你朋友别的东西，你是完全无法知道的。

好，现在来玩游戏吧，

按Elminster的假设：
1、你和朋友都知道一个秘密的数字，这是你们两人之间的小秘密， 
2、你和朋友都有足够数量的锁、与之相配的钥匙、坚固的箱子（锁上之后是不可能砸开的）。
3、现有贪婪的邮差一名，你和朋友只能通过他通信，任何东西都要通过他转交。这个邮差很能干，可以毫无代价地复制钥匙和锁，而且他也有和你们一模一样的箱子。但只有锁的情况下，他是配不出钥匙的 —— 当然也就无法打开上锁的箱子了。


用数字密码锁就行了啊，数字就是钥匙

按照你这样新提出的前提的话，那这题目又变简单了。

你可以这样：发送多个箱子和多个钥匙，互相嵌套——比如某个箱子锁着另外一个箱子的钥匙，这个钥匙又可以打开第三个箱子，里面放着第四把钥匙...诸如此类。具体怎么做不是关键问题，关键是要够复杂，使得邮差通过穷举法暴力破解不太可能。

然后你写一张纸条，上面明文写清楚：使用怎样的一个公式来如何解析秘密数字，就可以得到正确的开箱顺序。纸条让邮差一起递交。

其实说白了还是无明同志的讲法：提供了一个秘密数字，其实等价于朋友有了一把无需邮差递送的钥匙。剩下具体怎么加密解密，都只是形式上的做法而已了。

数字密码锁 …… 啊啊，如果我打算出脑筋急转弯或是想看看各位的发散性思维，那么这个答案极棒。



唔唔，恐怕你的方法不成立。无论你箱子的次序如何安排，你总需要传递第一把钥匙让你的朋友能够开第一个箱子。邮差只要扣下所有的箱子，复制你所有的钥匙，一定可以拿到宝石。

当然从原理上说，你的话没错，这个秘密数字可以认为是一把无需邮差递送的钥匙，剩下无论怎么加密解密，都只是“形式上”的做法而已。问题在于，你怎么来找到这个“形式上”的做法？而且你有没有办法说明你的做法是最优的？比如需要递送最少的东西，或是邮差来回的次数最少？这个不是那么简单的。