以 100% 的准确率猜测随机位

信息安全 密码学
2021-08-26 13:46:33

我很快就要开始义务兵役了。我申请了芬兰军队的网络战部队。对申请人进行了测试。由于测试完成,问题现已发布在这里:http ://erityistehtavat.puolustusvoimat.fi/cyberchallenge.html

这是问题4:

两个完全隔离的程序分别从不同的硬件随机数生成器获得一个随机位。在得到位之后,每个程序都会猜测另一个程序的随​​机位是什么。程序可以不同,并使用不同的猜测策略。运行一次后,如果至少有一个程序猜对了,程序的作者将获得奖励。

是否有可能设计一个提供 100% 机会中奖的策略?如果是,请解释策略。

我回答no是因为我想不出获胜的策略。这是正确的答案还是我错过了什么?

4个回答

实际上有一个总是会成功的解决方案:程序 A 将猜测它接收到的值的相反值,程序 B 将猜测与它接收到的值相同的值。

你也可以这样想: A 猜测他们会收到不同的数字;B 猜测他们收到相同的信息。其中之一肯定是正确的。如果您查看下表(r 表示接收,g 表示猜测),您将看到 A 或 B 始终正确(* 表示正确响应):

rA | rB | gA | gB
0     0    1    0*
0     1    1*   1
1     0    0*   0
1     1    0    1*

由于这看起来像一个诡计问题,这里是一个诡计答案(即它是“作弊”)。

让程序 A 执行以下操作:

  • 如果接收到 0,则输出“1”并退出。
  • 否则,永远循环,直到收到“Ctrl-C”信号,在这种情况下程序输出“0”并退出。

让程序 B 执行以下操作:

  • 如果接收到 0,则输出“0”并退出。
  • 否则,永远循环,直到收到“Ctrl-C”信号,在这种情况下程序输出“1”并退出。

分析:

  • 如果两个程序都得到 0,程序 B 输出“0”,这是正确的 -> win。
  • 如果程序 A 得到 0 而程序 B 得到 1,则程序 A 输出“1”,这是正确的 -> win。
  • 如果程序 A 得到 1 而程序 B 得到 0,则程序 A 永远循环,而程序 B 输出“0”(这是错误的);在某些时候,运行实验的操作员失去了耐心,在终端运行程序 A 中键入 Ctrl-C,并看到“0”,即正确答案 -> 获胜。
  • 如果两个程序都得到 1,那么这两个程序将永远循环。操作员尝试使用 Ctrl-C 杀死两者,此时程序 A 输出 0,程序 B 输出 1;后者是正确的-> 赢。

100% 获胜的策略。

编辑:如果你忘记了整个“等到 Ctrl-C”的事情,那么你基本上会得到@Helm 的答案,这是正确的,而且不那么棘手。该等待过程的唯一目的是获得一个旁通道,通过该通道,程序不仅可以猜测该值,而且“知道”它猜测了该值(无论如何这不是挑战的一部分)。

你是对的。你能得到的最接近的结果是至少其中一个是正确的有 75% 的机会,两台计算机总是猜测另一台的否定。

既然这是信息战,我想知道是否允许有“作弊”的场景。可能存在系统级工件,程序可以在生成随机数后检查该工件,或者其中一个程序可以挂接到该进程,对其进行监视。

要求说这些程序是相互隔离的,但不一定在单独的系统上。如果它们都在同一个系统上,您也可以检测或影响其他应用程序使用的种子值。如果您正在编写两个应用程序,您甚至可以让每个应用程序打印出该值并让另一个系统读取该值。即使它们在单独的盒子上,您理论上也可以提出使用某种类型的热量或声学监控的解决方案.

我认为“猜测”这个词是一种抛弃,如果你只是猜测,你就无法确定。这个问题听起来更像是一种思考打破影响系统的不同方式以及理解如何影响或预测随机值的方式。