送宝石游戏考题

不是这么说的。比如我让邮差递送N把钥匙，M个箱子，每个箱子都包含R把钥匙。那么，邮差如果要通过暴力破解，第一步，就要用N把钥匙在M个箱子上面尝试N x M次，打开唯一的一个可开的箱子之后，他取出其中的R把钥匙，又要再尝试R x (M - 1)次，才能打开第二个箱子... 关键是，箱子和钥匙要足够多，使得穷举破解不太可能。

我们应该假设，邮差的时间或者耐心是有限的，因此他不会无限地在破解上花时间；否则的话，他总是可以复制所有的钥匙扣下所有的箱子，然后尝试所有的操作可能性。总有一天他会碰到正确的开箱方法。

我们都已经同意了如何组合钥匙和箱子，其实是求一个好的加密方法。但是现在递送的是钥匙和箱子——不是比特，我怀疑在仅递送少量的钥匙和箱子的情况下（也就是常识上的，通过邮政系统递送物品通常的体积），能否做到有效的加密。任何加密都是不能对抗穷举法的。如果仅提供有限的几个箱子和钥匙，不管你玩什么花样，它们之间的排列组合就这么几种可能，就像一个色子只能扔出6种可能性，两个筛子只能扔出10个值；你让赌神来扔也逃不出这个框框。

要知道，安全的SSH可是128位的长度哦！但递送128这个数量级的箱子，似乎是不可能的吧...

1. 让postman送已上锁的盒子(宝石+另一串数字)
2. 朋友把他那串数字让postman带回来
3. 让postman送匙
4. 让朋友开盒后,把"另一串数字"让postman带回来,
咳,忘了,把盒子也要拿回来

呵呵，这里你可说错了。就这个问题来说，你只需要很少的锁、钥匙和箱子（比方说，五个以内）就能得到一个相当安全的通信协议。

事实上，所谓任何加密都不能对抗穷举法，一般都是在说使用同一个密码进行许多次互相独立的通信这种情况。拿到我们的游戏里面，就是你要送 N 多次宝石，然后每次你和朋友之间的秘密数字 a 都是同一个，这样的话那个邮差就可以一直蒙下去，依次猜测 a=0, a=1, a=-1, a=2, a=-2, a=3 a=-3 ... 这样只要你一直送宝石而且一直用同一个秘密数字 a ，邮差迟早有一次总能蒙对拿到宝石。但你的方法，即便是你第一次送宝石，邮差也可以通过尝试打开箱子拿到宝石。

嗯嗯，至于所谓安全的 SSH 是 128 位长度，那是指 SSH 中用的那个“锁”的强度，也就是保证邮差不能通过锁来制造钥匙，和箱子的数量是没有关系的 ……



1. postman 扣下你送出的盒子，给你朋友一个上了锁的空盒子。
2. 你朋友无法知道这个盒子是不是被 postman 掉了包（注意哦，送宝石的过程中你和朋友除了通过 postman 之外是无法通信的），所以还是只能把那串数字交给 postman 给你送来。
3. 你看到数字正确，把钥匙给 postman 让他送给你朋友。
4. postman 拿到钥匙，打开第一轮扣下的盒子拿到宝石远走高飞，从此过上了富足而幸福的生活，:D

嗯，我先把这个问题用我的思路理一下：

比如在网络上，我要传送一段敏感信息Z给我的朋友。我和我朋友都知道一个秘密数字X，这个数字不需要传输；地球人都知道一个解密算法f。那么我就传输一段加了密的信息Y，使得：

Z = f(Y, X)

黑客只知道f, Y。如果他想知道Z，那他就要穷举X。

现在把这个例子来对比邮差的例子：

在邮差的例子中，什么是敏感信息Z？与其说是“宝石”，我们不妨认为“一系列特定的开箱步骤”才是敏感信息。知道怎么开箱子，就能拿到宝石。

什么是f呢？我用某种方式把箱子和钥匙嵌套组合起来，然后我写一张明文纸条，上面说明了如何解析数字X就可知道开箱步骤。这张纸条就是f。

好了，那么邮差该如何破解？对比网络数据传输的例子，邮差应该穷举X。总有一天他会找到正确的X，继而算出正确的Z（也就是开箱顺序）。

但是！！！
不要死脑筋了。我前面说了，Z是“一系列特定的开箱步骤”。邮差何必穷举X，然后通过公式f来求得Z？邮差完全可以直接穷举Z！如果你的箱子和钥匙的数量很有限的话，它们排列组合形成的Z的可能性也是有限的。这样的话，即使秘密数字X很大，那也没有用。

“只需要很少的锁、钥匙和箱子（比方说，五个以内）就能得到一个相当安全的通信协议”，这个说法有问题。有限的箱子和钥匙只能排列出有限的可能性。邮差完全可以在有限的时间内尝试完所有的可能性。

由于Elminster 限制了共享信息和锁的类型，那么实现安全交货的前提必须有3个：
1。有一个共享的数字
2。有一套共享的算法
3。可以多次传递，即不是一次完成投递。

首先，我发一段信息，“我是xx,你是xxx吗？收到信息请回复”这个可以用原文，然后写下货物的特征：“如果你是xxx的话，我会通过postmanA（postman的详细信息）送一个宝石给你（宝石的详细信息）,邮寄方式是（。。。。）”，这段信息用自己的一个数字加密（私钥）但保证对方能通过共享数字解密（公钥）。

然后通过postman传递这封信，这个信的内容，postman看到也没有关系。

朋友收到后，用共享数字解密（公钥），了解请况了，就回信：“你好，我是xxx，来信收到，你要送来的东西是：”——这段用明文，然后确认信息用同样的方式加密。

我收到回信后，就可以确认了，这时的请况，就回到我先前所说的，能够直接通信确认的情况。这时我就可以直接邮寄宝石，同时，附上情况说明——这个加密，再附一段明文：收到请回复。——这是给postman看的。

朋友如果正常收到后，就按之前协定的内容，回复：“货物收到，谢谢，这是我收到的货物清单：”——明文，“宝石一块。。。”——密文。


看，锁和钥匙都是没有必要的，只要形成可靠的校验和反馈机制，在这个故事中，postman的行动就是受到限制和监视的，非对称的加密部分信息，也就保证了postman不能伪造或者篡改通信（在密文部分也可以把明文也加密一遍附进去），这就保证了安全。

当然在真实的internet情况下，问题就复杂的多，而且数字信号是可以任意复制的，不象宝石，所以不能直接传递，必须用锁锁起来（加密）。

Dam! Lost big money.

假设所有经postman手的东西都可以复制,问题在于他能否打开盒子拿到宝石.
按我之前的做法,数字仅保证了postman把东西(可能是复制品)送到朋友手上.

由于所有东西都通过postman送递,包括宝石和得到宝石的方法(钥匙). 因此,postman总会比朋友先一步得到或复制到完备的东西,最后拿到宝石远走高飞，从此过上了富足而幸福的生活.

所以,不能够通过postman送出完备的东西. 必需要有进一步的物件区分开朋友和postman,并且最关键的是这个物件必需与送递的东西有某种不易破解的联系.例如这种楼上有朋友提过数字锁方式的变式:

1)送锁上的盒(宝石),M条已排序钥匙
2)朋友用第N条钥匙开盒,假设秘密数字为N且M>N

咳,又打回原形了.

咳咳，我实在是不想说你死脑筋 …… 注意我的条件：

2、你和朋友都有足够数量的锁、与之相配的钥匙、坚固的箱子（锁上之后是不可能砸开的）。

看到没，你朋友也有锁和钥匙，或者提示得再明确一点，不是所有的锁和钥匙都一定要让邮差经手的，你只要想法让你朋友“安全地”送一把他的锁给你（钥匙你朋友自己藏着），你用这个锁把宝石锁在盒子里面送回去，那么邮差就无可能打开锁拿到宝石，这个贪心的家伙无论怎么尝试都没戏。



这个 …… 咋说呢，就有点那啥了。如果没有钥匙和锁以及盒子，邮差完全可以给你们来回递纸条，然后你一旦把宝石交给他就贪污了宝石远走高飞。或者这么说吧，你玩的不是我这个游戏。



参考我前面对 B1 的回复。

哎呀！这不是和送宝石等价的嘛！

你说的这个方案，就是先让朋友送一把他的锁给你，并且要保证这把锁的安全（不被盗、不被掉包），这个与“在朋友没有锁的前提下安全地送宝石给朋友”不是等价的么，不同的就是送的内容，前者是一把锁后者是个宝石。

为了送个宝石,你需要让朋友先送你一把锁.同样也需要保证这把锁的安全,否则邮差可以将这把锁掉包. 那么怎么保证这把锁的安全呢? 肯定是用N个箱子M把钥匙把它重重保护起来。嗯，不行，你已经说了这样的单方面传输是不可能安全的，那么，为了传送朋友给我的这把锁，我先得传送给朋友一把锁。 那么怎么保证这把锁的安全呢? 肯定是用N个箱子M把钥匙把它重重保护起来...

不等价哦，没注意到我在“安全地”三个字上面打了引号么？

这里的区别在于，你可以设计某种方式，当邮差把你朋友送过来的锁掉包或是做了些别的什么的时候，让你能够发现这一点，那么此时你就可以说：“靠，你小子做手脚了！老子不送这宝石了！老子要送你去见官！”换句话说，你可以及时发现事情不对然后选择一拍两散，你的宝石仍然是安全的。

哎哎，你是不是铁定不信我这个游戏有解啊？我们来打个赌怎么样？如果我只用个位数那么多的箱子、锁和钥匙，构造出了一个通信方式使得邮差能够拿到宝石的概率小于，比方说，小于 1/100 ，你就来上海请我好好吃一顿如何？ 

1/100这个概率太大了。
如果邮差绝对不能够拿到宝石，我请你吃一顿。否则你我吃一顿如何？