|
锁定老帖子 主题：送宝石游戏考题
该帖已经被评为精华帖
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2005-10-14
jkit 写道 Elminster 写道 [
哎哎，你是不是铁定不信我这个游戏有解啊？我们来打个赌怎么样？如果我只用个位数那么多的箱子、锁和钥匙，构造出了一个通信方式使得邮差能够拿到宝石的概率小于，比方说，小于 1/100 ，你就来上海请我好好吃一顿如何？  1/100这个概率太大了。 如果邮差绝对不能够拿到宝石，我请你吃一顿。否则你我吃一顿如何？ 绝对不能够是做不到的 —— 万一这个邮差是超级狗屎运，上来就蒙对了你和你朋友之间的秘密数字，那不管什么通信方式都没辙。最多我给你概率收收紧，比如 1/1000 。 或者这样吧，第一个能够给出用个位数箱子、锁和钥匙实现足够安全的通信方式的人，我可以在复旦大学招待他吃顿饭， 
|
| 返回顶楼 | |
|
发表时间：2005-10-14
Elminster 写道 无明 写道 由于Elminster 限制了共享信息和锁的类型，那么实现安全交货的前提必须有3个：
1。有一个共享的数字 2。有一套共享的算法 3。可以多次传递，即不是一次完成投递。 首先，我发一段信息，“我是xx,你是xxx吗？收到信息请回复”这个可以用原文，然后写下货物的特征：“如果你是xxx的话，我会通过 postmanA（postman的详细信息）送一个宝石给你（宝石的详细信息）,邮寄方式是（。。。。）”，这段信息用自己的一个数字加密（私钥）但保证对方能通过共享数字解密（公钥）。 然后通过postman传递这封信，这个信的内容，postman看到也没有关系。 朋友收到后，用共享数字解密（公钥），了解请况了，就回信：“你好，我是xxx，来信收到，你要送来的东西是：”——这段用明文，然后确认信息用同样的方式加密。 我收到回信后，就可以确认了，这时的请况，就回到我先前所说的，能够直接通信确认的情况。这时我就可以直接邮寄宝石，同时，附上情况说明——这个加密，再附一段明文：收到请回复。——这是给postman看的。 朋友如果正常收到后，就按之前协定的内容，回复：“货物收到，谢谢，这是我收到的货物清单：”——明文，“宝石一块。。。”——密文。 看，锁和钥匙都是没有必要的，只要形成可靠的校验和反馈机制，在这个故事中，postman的行动就是受到限制和监视的，非对称的加密部分信息，也就保证了postman不能伪造或者篡改通信（在密文部分也可以把明文也加密一遍附进去），这就保证了安全。 当然在真实的internet情况下，问题就复杂的多，而且数字信号是可以任意复制的，不象宝石，所以不能直接传递，必须用锁锁起来（加密）。 这个 …… 咋说呢，就有点那啥了。如果没有钥匙和锁以及盒子，邮差完全可以给你们来回递纸条，然后你一旦把宝石交给他就贪污了宝石远走高飞。或者这么说吧，你玩的不是我这个游戏。 “邮差完全可以给你们来回递纸条然后你一旦把宝石交给他就贪污了宝石远走高飞”，这样就留了痕迹，被人发现了啊
知道你的意思，但这样你还要再加强条件：假设postman不计一切后果都要得到宝石，除非他认为他得不到了，才老老实实的送货
嗯，严格说来，我是在回答原题，因为你已经把假设做了比较大的变动，限制了其他可能性，如果要按你的思路设计一套协议和算法，还是有点困难，想想先 |
| 返回顶楼 | |
|
发表时间：2005-10-14
Elminster 写道 不等价哦，没注意到我在“安全地”三个字上面打了引号么？ Wink 这里的区别在于，你可以设计某种方式，当邮差把你朋友送过来的锁掉包或是做了些别的什么的时候，让你能够发现这一点，那么此时你就可以说：“靠，你小子做手脚了！老子不送这宝石了！老子要送你去见官！”换句话说，你可以及时发现事情不对然后选择一拍两散，你的宝石仍然是安全的。 哎哎，你是不是铁定不信我这个游戏有解啊？我们来打个赌怎么样？如果我只用个位数那么多的箱子、锁和钥匙，构造出了一个通信方式使得邮差能够拿到宝石的概率小于，比方说，小于 1/100 ，你就来上海请我好好吃一顿如何？ Very Happy Very Happy 表面上有道理，其实是不行地。 你想想看：通过怎样的方式，才能够使得邮差把锁替换以后，我可以察觉到？ 很显然，“邮差替换的锁”与“原版的锁”唯一的区别就在于，开这把锁的钥匙不同(邮差肯定会把他的锁做得和原版的锁在外观上一模一样)。但是很明显啦，我手里不会有开这把锁的原版钥匙，自然也就无法辨别这把锁有没有被调包。唯一辨别区别的方式不被允许，自然我就无法分辨。 那么怎么办呢？唯一的方案就是，让邮差接触不到这把锁，无法做替换。怎么让邮差接触不到这把锁呢？当然是用重重的钥匙和箱子把它保护起来咯！该怎么保护？那又回到了保护宝石的老路上面去了不是... 嘿嘿，吃饭的事情，可以先欠着，我现在在南半球离诸位太远。 你也别老是光破坏，你说行，就先拿出个解决方案看看阿 |
| 返回顶楼 | |
|
发表时间：2005-10-14
很明显，postman根本就没法做到不留痕迹。
直接把宝石交给他送，然后打电话问朋友又没有收到，再拿去做珠宝鉴定，他敢动手脚立刻就能被发现。 |
| 返回顶楼 | |
|
发表时间：2005-10-14
B1-66-ER 写道 ……
表面上有道理，其实是不行地。 你想想看：通过怎样的方式，才能够使得邮差把锁替换以后，我可以察觉到？ 很显然，“邮差替换的锁”与“原版的锁”唯一的区别就在于，开这把锁的钥匙不同(邮差肯定会把他的锁做得和原版的锁在外观上一模一样)。但是很明显啦，我手里不会有开这把锁的原版钥匙，自然也就无法辨别这把锁有没有被调包。唯一辨别区别的方式不被允许，自然我就无法分辨。 那么怎么办呢？唯一的方案就是，让邮差接触不到这把锁，无法做替换。怎么让邮差接触不到这把锁呢？当然是用重重的钥匙和箱子把它保护起来咯！该怎么保护？那又回到了保护宝石的老路上面去了不是... 嘿嘿，吃饭的事情，可以先欠着，我现在在南半球离诸位太远。 你也别老是光破坏，你说行，就先拿出个解决方案看看阿 这话表面上有道理，其实是不对地，:wink: 不过你小子居然在南半球 —— 澳大利亚么？ —— 这个不能敲你一顿我的积极性便就差了许多呀。要不你从澳大利亚给我空运一只大龙虾过来吧？:D:D 嗯嗯，不过说实话这题的确是有点难，为了给大家更多的提示，也免得 B1-66-ER 这家伙总说我光破坏，我就先给个有瑕疵的方案出来，算是给各位一个思考角度上的启发。为了说起来方便，所有的锁我用 L1, L2, L3 ... 来描述，对应的钥匙就是 K1, K2, K3 ... ，然后你和朋友之间的那个秘密数字，我记为 a 。那么这个通信方式可以描述如下： 引用 1、我随机地取一个数 r1 ，把它写在一个纸条上装在盒子里，然后拿出一个锁 L1 把盒子锁上，钥匙 K1 留在自己手里。然后我让邮差把这个盒子送给我的朋友。
2、我的朋友收到我发过去的盒子之后先把它放在一边（现在他还打不开），也随机地取一个数 r2 把它写在一个纸条上，然后另外拿出一个盒子，把这个纸条和一把锁 L2 放进去（这个 L2 就是最后拿来锁宝石的锁），再用锁 L3 把这个盒子锁上，让邮差把这个盒子送给我。同样的，钥匙 K2 和 K3 都留在朋友自己手里。 3、我收到朋友送过来的盒子之后，把钥匙 K1 交给邮差让他送给我的朋友。 4、我的朋友收到钥匙 K1 ，打开我最初送过去的盒子，看到我放在里面写着 r1 的小纸条。现在我的朋友知道秘密数字 a ，也知道 r1 和 r2 ，他算出 r1+r2+a 写在纸条上，然后让邮差把这张纸条和 K3 送给我。 5、我收到纸条和 K3 ，打开我朋友送给我的盒子，应该能够看到里面的 r2 和锁 L2 。我检查一下，我收到的纸条上的数字是不是等于 r1+r2+a 。相等的话我就拿出盒子里面的锁，用它把宝石锁进盒子里，然后让邮差把这个盒子送给我的朋友；不想等的话，我就立刻对邮差翻脸（“你小子做手脚了是不是！”），自然宝石也就不送了。 6、朋友收到盒子，用自己保留的 K2 打开锁 L2，取出宝石，完成！ 嗯嗯，现在来看一下这个通信方式的安全性。首先最后锁宝石盒子的锁是 L2 ，而对应的钥匙 K2 一直在朋友手里没有被邮差复制的可能性，所以邮差如果在第二步老老实实地把朋友的那个盒子交给了我，那么显然实际上他就失败了。因此，邮差一定要在第二步掉包，给我一个另外的盒子，里面放一把他有钥匙的锁和一张纸条。问题在于，在第二步的时候邮差不可能知道 r2 是多少 —— 盒子是锁着的 —— 所以他只能蒙一个数 r3 放在他掉包的盒子里面。那么在第五步的时候，邮差交给我的纸条上必须写上 r1+r3+a 才行，但邮差并不知道 r1 和 a 各是多少（特别是 a ），所以他算不出这个数，也就没法拿到宝石。 OK，这个方案是不是看上去有点意思？特别的，这方案里面有很多关键的做法，比如使用随机数。不过很可惜，我要指出这个方案仍然是不正确的，如果邮差足够聪明他仍然可以拿到宝石 —— 你知道他该怎么做么？我们又该如何设计一个真正安全的通信方案？
|
| 返回顶楼 | |
|
发表时间：2005-10-14
我要指出你一个本质错误：
题目并没有允许你和你朋友有这样的默契，也就是说，你做了步骤1，凭什么朋友在没有任何提示的情况下，就会去做步骤2？ 要知道，当完成第一步的时候，你的朋友还不能打开箱子，也就是他不能从中取得任何信息，那他又怎么知道应该去做步骤二？ 如果允许这样的“心照不宣”存在——那也就是默许了你和你的朋友之间，存在一个先在的、无需通过邮差递送，并且邮差也不会知道（因此也不可能模仿）的“秘密协议”，这其实就已经超越了“你和朋友仅知道秘密数字a”这样一的先决条件。 嘿嘿，俺也恶狠狠地过了一回破坏的瘾... |
| 返回顶楼 | |
|
发表时间：2005-10-14
B1-66-ER 写道 我要指出你的漏洞：
1. 首先，a是你和你朋友都知道的秘密数字，这个毫无疑问。通过通讯，r1和r2也成为你们都知道的秘密数字。但是，你们之间并没有传递r1+r2+a这个验证公式。 2. 另外还有个更本质的问题：题目并没有允许你和你朋友有这样的默契，也就是说，你做了步骤1，凭什么朋友在没有任何提示的情况下，就会去做步骤2？ 如果允许这样的“心照不宣”存在——那也就是默许了你和你的朋友之间，存在一个先在的、无需通过邮差递送的“通讯协议”，这其实就已经超越了“你和朋友仅知道秘密数字a”这样一的先决条件。 嘿嘿，俺也恶狠狠地过了一回破坏的瘾... 破坏也是要点水平滴 ～～～ 1、r1+r2+a 这个验证公式是整个通信方案的一部分，就像“宝石会放在哪个盒子里面”一样是你、你朋友、邮差都知道的事情。挑这个 …… 那就游戏就没法玩了，你和你朋友什么事情都不能做，不然就会有人反问一句：“他们怎么知道该这样做？” 2、这个方案里面你和你朋友没有任何默契。除了开始的步骤一，任何一方采取的任何一个步骤，都是在收到邮差送来的东西之后才开始实施的。比方说我的朋友要一直等到收到邮差送来的盒子才会进行步骤二，同样我在做完步骤一之后一直要等到邮差给我送来盒子才会进行步骤三。这里既不需要提示，也不需要什么“通讯协议”。你可以看我的描述，每一步的第一句话都是“××收到××之后 …… ”。 所以再次重复那句话，破坏也是要点水平滴，嘿嘿嘿嘿 …… |
| 返回顶楼 | |
|
发表时间：2005-10-14
恩，我写的有些更新了。第一个关于验证公式的问题不算。因为其实你可以把验证公式与r1写在一起。
关于第二个问题，你没有明白我的意思。 你的第一步是： “1、我随机地取一个数 r1 ，把它写在一个纸条上装在盒子里，然后拿出一个锁 L1 把盒子锁上，钥匙 K1 留在自己手里。然后我让邮差把这个盒子送给我的朋友。” 然后你的朋友收到了盒子。在你的方案里面，这是第二步的开始。 但问题是：你的朋友不能打开盒子，所以就他的视角而言，此时此刻，他不能从你这里获取到任何信息。 既然如此，你的朋友又有什么理由去做“随机地取一个数 r2 把它写在一个纸条上，然后另外拿出一个盒子，把这个纸条和一把锁 L2 放进去，再用锁 L3 把这个盒子锁上，让邮差把这个盒子送给我”这一系列复杂的动作？他并没有从你的箱子上面获取到任何指示！除非你们事先有过约定，但是我说了，这样的事先约定和秘密数字a的性质是一样的，这等于平白增加了题目给出的条件。 所以，你这个先验的假定是不能成立的。 |
| 返回顶楼 | |
|
发表时间：2005-10-14
B1-66-ER 写道 恩，我写的有些更新了。第一个关于验证公式的问题不算。因为其实你可以把验证公式与r1写在一起。
关于第二个问题，你没有明白我的意思。 你的第一步是： “1、我随机地取一个数 r1 ，把它写在一个纸条上装在盒子里，然后拿出一个锁 L1 把盒子锁上，钥匙 K1 留在自己手里。然后我让邮差把这个盒子送给我的朋友。” 然后你的朋友收到了盒子。在你的方案里面，这是第二步的开始。 但问题是：你的朋友不能打开盒子，所以就他的视角而言，此时此刻，他不能从你这里获取到任何信息。 既然如此，你的朋友又有什么理由去做“随机地取一个数 r2 把它写在一个纸条上，然后另外拿出一个盒子，把这个纸条和一把锁 L2 放进去，再用锁 L3 把这个盒子锁上，让邮差把这个盒子送给我”这一系列复杂的动作？他并没有从你的箱子上面获取到任何指示！除非你们事先有过约定，但是我说了，这样的事先约定和秘密数字a的性质是一样的，这等于平白增加了题目给出的条件。 所以，你这个先验的假定是不能成立的。 这个 …… 这个我没话好说了。照你这样推理，就算直接送一个盒子和一把钥匙过去，你也可以争辩说你朋友怎么知道要用钥匙去打开箱子取出宝石？是不是我还要另外备一张小纸条写着“请你用钥匙打开箱子取出宝石”一块送过去？万一邮差换了张纸条上面写着“取出宝石后送给邮差”怎么办？是不是你朋友就会把宝石送给邮差？ 拉倒吧。 这里所谓通信方案，就是通信双方在什么情况下做什么事情的一种约定，这个是必须事先约定好的。而且这样的事先约定和秘密数字 a 的性质有本质区别 —— 这些约定是你、你朋友和邮差三者都完全了解的，而秘密数字 a 只有你和你朋友知道。打个比方，这些约定就是加密算法，秘密数字 a 就是密码，算法是对所有人公开的，而密码只有你自己知道。 |
| 返回顶楼 | |
|
发表时间：2005-10-14
引用 这个 …… 这个我没话好说了。照你这样推理，就算直接送一个盒子和一把钥匙过去，你也可以争辩说你朋友怎么知道要用钥匙去打开箱子取出宝石？是不是我还要另外备一张小纸条写着“请你用钥匙打开箱子取出宝石”一块送过去？万一邮差换了张纸条上面写着“取出宝石后送给邮差”怎么办？是不是你朋友就会把宝石送给邮差？ 拉倒吧。 这里所谓通信方案，就是通信双方在什么情况下做什么事情的一种约定，这个是必须事先约定好的。而且这样的事先约定和秘密数字 a 的性质有本质区别 —— 这些约定是你、你朋友和邮差三者都完全了解的，而秘密数字 a 只有你和你朋友知道。 我的意思很简单, 你和你朋友，相对于邮差，不能拥有除了秘密数字a之外更多的优势。 也就是说，在你的方案中，你必须允许邮差知道你和你的朋友在拿到物件后会做出哪一些步骤。在每一步，你和你的朋友都必须附上明文纸条，来指示对方下一步应该怎么做。当然避免陷入抬杠的怪圈，我们必须假定邮差是不会替换明文纸条来故意破坏通讯的。 在这样的前提下，我破解了你的方案... 黑体字部分是破解 引用 1、我随机地取一个数 r1 ，把它写在一个纸条上装在盒子里，然后拿出一个锁 L1 把盒子锁上，钥匙 K1 留在自己手里。然后我让邮差把这个盒子送给我的朋友。 邮差扣下了箱子，用伪锁L1' 锁上他自己的箱子，里面放上他的数字r1'。 把假箱子交给你朋友。 2、我的朋友收到我发过去的盒子之后先把它放在一边（现在他还打不开）（你朋友收到的是邮差的假箱子），也随机地取一个数 r2 把它写在一个纸条上，然后另外拿出一个盒子，把这个纸条和一把锁 L2 放进去（这个 L2 就是最后拿来锁宝石的锁），再用锁 L3 把这个盒子锁上，让邮差把这个盒子送给我。同样的，钥匙 K2 和 K3 都留在朋友自己手里。 邮差扣下这个箱子，把伪造的r2' 和 伪造的L2'，使用伪锁L3'锁在他的箱子里，把箱子交给你。 3、我收到朋友送过来的盒子之后，把钥匙 K1 交给邮差让他送给我的朋友。 你收到的其实是邮差的假箱子。 邮差用K1打开他在第一步扣下的箱子L1，得知了数字r1。然后，他把他的钥匙K1'交给你的朋友。 4、我的朋友收到钥匙 K1（假钥匙K1'） ，打开我最初送过去的盒子（其实是邮差的盒子），看到我放在里面写着 r1 的小纸条（其实是邮差的r1'）。现在我的朋友知道秘密数字 a ，也知道 r1 和 r2 ，他算出 r1+r2+a （其实算出来的是r1' + r2 + a）写在纸条上，然后让邮差把这张纸条和 K3 送给我。 邮差使用K3，打开了朋友试图在第二步送给你的L3。那么现在邮差知道了值r2。同时邮差又持有朋友给你的纸条，他就知道了r1' + r2 + a；现在他知道r1'（这是他伪造的数，他肯定知道），知道r2，于是他求出了秘密数字a。Your little secret has been exposed! 5、我收到纸条和 K3 ，打开我朋友送给我的盒子，应该能够看到里面的 r2 和锁 L2（你收到的是假盒子，里面放的是r2'和L2'） 。我检查一下，我收到的纸条上的数字是不是等于 r1+r2+a。 注意这里的验证：因为你收到了假箱子，所以你是在验证：r1 + r2' + a是否正确！好了，邮差在第三步知道了r1，邮差自己伪造了r2'，并且在第四步求出了a。所以，邮差完全可以伪造朋友给你的纸条，写上值 r1 + r2' + a！ 然后我就拿出盒子里面的锁（这把锁是L2'），用它把宝石锁进盒子里，然后让邮差把这个盒子送给我的朋友。然后邮差出门后就用他的K2'开了锁，然后远走高飞，从此过上了富足快乐的生活！ 挖哈哈哈 |
| 返回顶楼 | |
