如何在不知道的情况下用鲍勃验证号码？

cs.stackexchange https://cs.stackexchange.com/questions/358

  •  16-10-2019
  •  | 
  •  

题

您需要检查您的朋友鲍勃（Bob）是否有正确的电话号码，但是您不能直接询问他。您必须将问题写在一张卡上，并将其交给夏娃，夏娃将卡鲍勃并将答案返回给您。除了问题之外，您还必须在卡上写什么，以确保鲍勃能够编码消息，以使Eve无法阅读您的电话号码？

笔记： 这个问题在“ Google面试问题”列表中。结果，网络上有大量此问题的版本，其中许多问题没有清晰，甚至没有正确的答案。

笔记2： 这个问题的尖叫答案是鲍勃应该写“叫我”。是的，这非常聪明，“盒子外”和所有内容，但不使用任何CS领域的技术，我们称之为英雄“鲍勃”和他的窃听对手“ eve”。

更新：
您和鲍勃都可以手工合理地完成的算法的奖励积分。

更新2：
请注意，鲍勃不必向您发送任何任意消息，但仅确认他没有您的正确电话号码，而Eve无法解码，这可能会或可能不会导致更简单的解决方案。

有帮助吗？

解决方案

首先，我们必须假设夏娃只是被动的。这样，我的意思是她真实地将卡片发送给鲍勃，而她带回爱丽丝的任何东西确实是鲍勃的回应。如果夏娃可以在两个方向或两个方向上更改数据（并且她的动作仍未发现），那么一切都会发生。

（为了纪念长期存在的传统，参与对话的两个诚实政党被称为爱丽丝和鲍勃。在您的文字中，您说“您”。我的真实姓名不是“爱丽丝”那 爱丽丝 想验证鲍勃的电话号码。）

简单（但弱）的答案是使用哈希功能。爱丽丝在卡上写道：“返回我的电话号码的sha-256哈希”。 SHA-256 是一个加密哈希功能，就哈希功能而言，被认为是安全的。手工计算它会很乏味，但仍然可行（大约是2500位位操作，每个操作都是添加的，单词换位或旋转，或者钻头组合；鲍勃应该能够在一天内或所以）。

现在有什么弱的？ SHA-256是一个加密哈希函数，对“预映射”具有抵抗力：这意味着给定的哈希输出，很难恢复相应的输入（这就是EVE面对的问题）。但是，“非常硬”的意思是“最简单的方法是蛮力：尝试可能的输入直到找到匹配”。麻烦的是，这里的蛮力很容易：没有太多可能的电话号码（在北美，这是10位数字，即仅100亿美元）。鲍勃想手动做事，但我们不能认为夏娃是如此有限。基本PC可以尝试数百万SHA-256哈希 每秒 因此，夏娃将在不到一小时的时间内完成（如果她使用GPU，则不到5分钟）。

这是一个通用的问题：如果鲍勃是确定性的（即来自爱丽丝的给定消息，他总是会返回相同的回应），夏娃可以模拟他。也就是说，夏娃知道鲍勃以外的一切，所以她几乎经营100亿鲍勃，他们只有他们假定的电话号码而有所不同。她等待一个虚拟鲍勃（Virtual Bobs）返回真正鲍勃（Real Bob）实际返回的任何东西。该缺陷会影响许多涉及随机nonces和对称加密和Whats的“智能”解决方案。这是一个很大的缺陷，其根源在于夏娃和鲍勃之间的计算能力巨大差异（现在，如果鲍勃 还 拥有像夏娃一样大的计算机，然后他可以使用 减缓 哈希功能通过使用许多迭代；密码或多或少是密码hashing的意义，而电话号码代替了密码；看 bcrypt 并且 这个答案).

因此，一种非弱解决方案 必须 涉及到鲍勃的一部分：鲍勃必须反复翻转硬币或掷骰子，并在其计算中注入值。而且，夏娃一定不能揭开鲍勃所做的一切，但爱丽丝必须能够，所以有些信息是 自信地传达了 从鲍勃到爱丽丝。这就是所谓的 不对称加密 或者，至少是不对称的关键协议。然后，该类的最简单算法要计算但仍然相当安全，那就是 RSA 与 PKCS＃1 V1.5填充. 。 RSA可以使用$ e = 3 $作为公共指数。因此协议因此：

  • 爱丽丝产生了一个大整数$ n = pq $，其中$ p $和$ q $是类似尺寸的主要整数，因此$ n $的大小足以确保安全性（即截至2012年起，至少1024位）。此外，爱丽丝必须安排$ P-1 $和$ Q-1 $ 不是 是3的倍数。

  • 爱丽丝在卡上写$ n $。

  • 鲍勃首先 垫子 正如PKCS＃1所述，他的电话号码为$ n $长达$ n $（这意味着：00 02 xx xx ... xx 00 bb bb .. bb .. bb，'bb'是编码的十个字节电话号码和“ XX”是随机的非零字节值，如果$ n $是1024位整数，则总长度为128个字节）。

  • 鲍勃将他的字节序列解释为一个大整数$ m $（大端编码），并计算$ m^3 mathrm { mod } n $（所以这是几个带有非常大的整数的乘法，然后是一个部门，然后是一个部门，结果是该部门的其余部分）。这仍然可以手工可行（但是，这可能会花一天的大部分时间）。结果就是鲍勃寄回爱丽丝。

  • 爱丽丝（Alice）使用她对$ p $和$ q $的知识从$ m^3 mathrm { mod } n $从Bob发送的$ M $中恢复。 Wikipedia页面上 RSA 对该过程有一些合理的解释。一旦爱丽丝（Alice）拥有$ m $有。

爱丽丝的计算将需要一台计算机（计算机的作用是 总是 基本和手工可行，但是计算机的速度非常快，因此“可行”可能需要太多时间才能实践。 RSA 解密 手工需要花费数周）。

（实际上，我们可以通过使用的速度更快地计算 mceliece加密, ，但是随后的公钥 - 爱丽丝在卡片上写的东西 - 将是巨大的，一张卡根本不会做；夏娃将不得不运送一本完整的数字书。）

其他提示

看起来像是经典的应用 公钥密码系统 喜欢 RSA.

您将公共密钥发送，Bob从他的联系人列表中加密电话号码，并将其发送给您。

您可以做的最基本的事情之一是 Diffie-Hellman密钥交换. 。它不需要您在通信启动之前设置键，因为它以听众无法自行得出密钥的方式进行谈判。参见综合 维基百科文章 有关详细信息。

您发送bob dh参数$ p $和$ g $（$ p $是合适的大码，$ g $通常是小数）和您的公钥$ g^{a} mathop { mathrm { mathrm {mod}} p $，其中$ a $是一个大秘密号码（这是您的私钥），以及鲍勃（Bob）发送以下内容的说明：

  • 他的公钥$ g^{b} mathop { mathrm {mod}} p $，其中$ b $是他选择的大秘密数字；
  • 他认为是您的电话号码，使用对称加密算法进行加密，该算法的键源自共享的秘密$ g^{a ，b} mathop { mathrm {modrm {mod}} p $。

Eve可以看到$ g^{a} mathop { mathrm {mod}} p $和$ g^{b} mathop { mathrm {mod {mod}} p $，但实际上无法计算$ g^{a a ，，， B} Mathop { Mathrm {mod}} p $。

只要实施正确而通信者和攻击者都具有相同的计算能力，这是安全的。

鲍勃不必发送任何可以解密的消息。他只需要向您证明他有您的电话号码。所以， 加密哈希功能, ，（单向加密）提供了公共密钥密码系统的替代方法。 SHA-2 目前是此类功能的热门示例。

在这种策略中，您永远不必解密鲍勃的信息回到您身上。您告诉鲍勃，您希望他使用哪种哈希功能，例如“鲍勃，请使用sha-2加密我的电话号码并让夏娃将结果传递给我”。然后，您使用相同的算法来哈希电话号码，并检查您是否获得与鲍勃获得的哈希相同的哈希。极不可能两个不同的电话号码会导致相同的哈希，因此您可以确定Bob是否具有正确的电话号码。

如果您，Bob和Eve没有可用的计算机来计算哈希功能（或执行蛮力攻击），则可以使用hash函数来牺牲一些安全性，以防止蛮力攻击，但对您和鲍勃来说更容易计算。

一个简单的解决方案是：

爱丽丝和鲍勃都同意相同的颜色。如果夏娃知道那个，我们将这个称为。假设它是黄色的，那没问题。现在，爱丽丝和鲍勃都随机选择私人颜色，例如“ x”。爱丽丝选择红色，鲍勃选择蓝色。现在，他们将它们与P. Alice混合在一起，现在有橙色，鲍勃有绿色。爱丽丝将橙色发送给鲍勃，鲍勃将他的绿色送给了爱丽丝夏娃现在知道黄色，橙色和绿色，但爱丽丝也知道她的私人颜色红色，而鲍勃知道他的私人颜色蓝色，其他人都不知道。爱丽丝（Alice）和鲍勃（Bob）都采用了他们的原始私人色彩，并将它们添加到刚刚交换的私人色彩中。现在，如果它们将原始的私人色彩（红色和蓝色）混合到共享的颜色中，则它们最终都具有相同的颜色，棕色或砖红色。

您可以使用$ g^x pmod {p} $，而不是将颜色混合在一起，这样p是较大的素数，而g是p的原始根，因为如果您执行$ g^x pmod {p} $对于任何x，结果（零和p -1之间的数字）为 同样可能 成为其中的任何一个，这就是为什么有原始根源的原因。如果p是素数2N+1，因此n也是素数，那么您知道2是P的原始根（这意味着您不必费心计算原始根，这很难） bob共享秘密= $ a^x pmod {p} $，而爱丽丝（Alice）则为$ b^y pmod {p} $。

我认为您可以在卡上写下这样的东西：

该数字为3,5和7的倍数（例如）。

$（10）^n $（$ n $是数字的数量）可能性，而这个想法只会使对此有任何了解的人无效。因此，夏娃的解密不会发生。

只需要求鲍勃将数字乘以2或3或其他任何东西，然后用数字本身将数字乘以XOR。如果已知数字，则可以手动可行，并且可逆。没有SHA，RSA或MD5。只是简单的数学。

向鲍勃发送一个包含您电话号码的密码字；如果他向您发送代码单词，您会知道他有正确的号码。

弱点是夏娃可以模拟鲍勃，所以只需尝试每个电话号码，直到她得到鲍勃返回时给出一些代码字的电话号码。

因此，让Bob将非常大的随机数附加到代码字上，然后将其加密，然后再将其发送给您。这使EVES搜索空间尽可能大。

我将在卡中写出10个电话号码，其中我将确保我的电话号码将接近鲍勃的电话号码我会提到“嘿，鲍勃，我的电话号码紧邻您的电话号码，请验证” :)

我认为这个问题比每个人想象的要简单得多。我们必须验证鲍勃的数字是否正确（或可能是不正确的）。由于我们正在“检查”数字是否正确，因此可以假定Bob已经有您的电话号码。因此，无需在某些代码中向鲍勃发送您的电话。我的回答是：“亲爱的鲍勃，请给我的电话号码。谢谢，爱丽丝”

尝试这样的trik播放

解决方案1：如果数字为37，则哈希地图看起来像这样

01 07

15 12

25 20

31 36

49 43

53 50

60 62

72 72

85 82

91 94

并为10位数字做同样的事情，甚至更多地使其混淆：P

解决方案2：或构建一个多项式，其中您的数字成为其他独特的数字

解决方案3：在字母“ Dude Call Me”中写下这篇文章

解决方案4：以这样的方式编写一个函数，以使其在每个数字上操作并返回0，然后他发送true或false解决方案5：如果两端共享一个共同的哈希功能...它使生活变得非常容易

我认为我们可以通过使用基本的明智操作来做到这一点，或者可以将其自定义用于纸和铅笔工作。如果爱丽丝的数量是ex：663，那么她只能使用此方法转换数字。将每个数字转换为等效的二进制表示形式说这是663-> 110 110 011，而不是反向每个单独的数字的相应位表示为b-> 011 011 110现在执行A和B-> 010 010 010现在将此编号发送到鲍勃（Bob）并要求这样做同样的话，如果结果相同，请他说“是”，否则。在这种情况下，夏娃将无法解码该数字，并且具有不同数字结束相同表示形式的可能性很低。夏娃只能猜测的唯一方法是编写所有可能的组合，然后尝试所有这些组合，但除了迎合我们可以通过使用左或右移并添加虚拟碎片更复杂的情况，我们可以更复杂。

请给我打电话（我的名字是1001001）。如果您无法联系我，请写下您拥有的电话号码，并要求EVE返回我。

说明：如果鲍勃得到了正确的＃，他可以联系我，那我知道这是正确的＃；如果鲍勃没有得到我的正确＃，夏娃也无法阅读我的（正确）电话号码。这样，我已经检查了我的朋友鲍勃是否有正确的电话号码。

许可以下： CC-BY-SA 和 归因
不隶属于 cs.stackexchange
scroll top