理论上一次性垫子是否容易破裂？

#1 楼

例如，对于100位的目标位串，我无法扫描所有100位的位串并对每个位与目标进行XOR，以期恢复消息。这种方法将产生所有可以用100位表示的消息。



这不是一次性垫被视为安全的原因。原因是，即使您尝试了所有可能的键，也将获得所有可能的纯文本，并且无法选择正确的键。明文/密文/密钥流的大小无关紧要。


但是，并非所有的位串都是随机的，例如111111111111的随机性小于01101001001101的随机性。这种观察似乎与牢不可破的一次性密码垫的思想相矛盾。


111111111111与01101001001101或同等大小的随机选择的其他值同等可能。证明：如果BS3是可压缩的，那么知道BS1将使我们能够以简短描述来描述BS2（即BS3）。然后，BS1和BS2都不都是随机的或者不是独立的。它们是随机的，但不是独立的，唯一的情况是一个是另一个的一部分。


如果值是某个集合的一部分，则其中某些值更有可能是可压缩的相对于其它的。如果$ K $是完全随机的，则$ C = P \ oplus K $不是这种情况。这是因为$ C $也将是完全随机的，而与$ P $是否随机无关。则BS1至少是BS2的一部分或包含BS2的一部分。


因为BS5不可压缩，所以永远不会这样。由于上述原因，BS5的每个可能值将与BS5的其他值一样。

#2 楼

首先，您对完美保密的定义是非标准的。标准定义给出了一个很好的答案，可以很好地回答OTP如何完全安全吗？。

本质上，完全保密意味着观察密文不会影响未知密钥下各种明文的相对可能性。 。因此，从理论的角度来看，不同的位串可能具有不同的随机性这一事实是无关紧要的。

此外，您可能会将Kolmogorov复杂度（又名算法随机性）与OTP参数中的随机性混为一谈。 Kolmogorov的复杂性确实是无可争议的。

#3 楼

我将尝试一个实际的例子：

我交易股票。给我的经纪人的指示使用简单的凯撒（Caesar）移位密码，但是该移位因一次性加密板上的值而异。常见的8个字符的指令包括：“多买”，“全部卖出”和“卖空”。

您截取给我的经纪人的指令：“ AAAAAAAA”

什么是我的指示？买，卖还是做空？

#4 楼

但是，并非所有的位串都是随机的，例如11111111111111的随机性比01101001001101的随机性小。此观察似乎与牢不可破的一次性时间垫的想法相矛盾。


当密码学家使用随机一词时，他们使用的是概率论。但是，您所说的“随机性”是Kolmogorov复杂性，“某种固定的通用描述语言中字符串的最短描述的长度”。您所说的“可压缩字符串”是一种字符串，其复杂度低于仅对字符串进行硬编码的描述的长度。当您说“随机字符串”时，您是在两个不可理解的字符串之间进行模棱两可的概念。

从所有长度为$ n $的比特串中随机选择的比特串都有一个预期的复杂度与$ n $成正比，这意味着到目前为止长度为$ n $的大多数字符串都是不可压缩的。但是，这样的随机选择很可能导致11111111111111变成01101001001101，因此您不能断言这样选择的字符串会很复杂-仅画出可压缩字符串的几率很小。

但是，这些都与一次性键盘的安全性无关，一次性键盘的安全性与密钥的复杂性或可压缩性无关，​​仅与密钥的统一随机选择有关。一次性填充的保密性基于以下定理：如果$ p $是在$ \ {0,1 \} ^ n $上有任何分布的随机变量，而$ k $是在$ \ {0上的统一随机变量，1 \} ^ n $，则$ c = p \ oplus k $是$ \ {0,1 \} ^ n $上的统一随机变量。
随机抽取的$ k $或计算出的$ c $可能是可压缩的字符串，但不太可能且无关紧要。

#5 楼

您无法破解一次性密码卡的原因是，暴力破解最终只会生成所有可能的解决方案。但是，您将更接近知道哪种解决方案是正确的！举个例子，假设有人使用一个时间垫对ip地址进行编码。您截获该消息。因此，您开始强行强迫它。您获得的大多数结果看起来都不像ip地址，因此您知道那些结果不正确。然后，您的破解软件将提供“ 127.0.0.1”！什么，那是合法的IP，所以那一定是对的！好吧，那么破解软件会提供“ 127.0.0.2”，然后是“ 127.0.0.3”，依此类推，等等。因为事实证明，每个可能的IP地址都是同等可能的解决方案。

您所说的关于随机性的内容根本不相关。

#6 楼

这取决于您所说的“裂纹”。如您在问题详细信息中所提示的那样，如果您意为“解密”，则取决于您对密码的实现。

从纯粹的数学POV来看，OTP是难以理解的。但是数学并不是唯一可以确保密文安全的事物：密文的实现，密匙的实现，密匙的管理，用于实施密文的硬件以及密匙和明文的社会方面。

破解密文的方法有很多。

关于密文的实现，如果使用非真随机数，则可以推导出密钥的位，如果一个可以访问最初加密的那种纯文本，可能可以推断出更多的密钥。例如，知道明文是文本文档或可执行文件，可以帮助解密更多密文。

关于密钥实现，如果您在算法中重用了密钥（例如，您使用长度比明文短的密钥，然后再次从密钥的开头开始），即密文的丧钟。在白盒破解中，可以访问正在实施的算法，这可以使您是否从头，尾，每个其他字符等开始重用密钥，而这是可用于解密的更多信息。 />
关于密钥管理，如果密钥存储在您的硬盘驱动器上，那么找到该密钥只是时间问题。您可以将密钥存储在一张纸上-但是您将其放在哪里？而且，如果您要加密的东西大小超过一兆字节-您要输入所有内容（无错误）？

对于硬件，获取实际的随机位是其中的一部分。但是，存储密钥，在加密过程中存储中间数据以及原始明文一旦被加密都会发生什么问题。如果您有一个包含Netflix帐户密码的文本文件，则可以使用OTP对其进行加密，然后右键单击并删除原始文本文件，则没有任何保护。

对于社交方面，让某人秘密安装密钥记录器，摄像机，给您下药，仿冒您，或者以其他方式诱骗您放弃密码密钥的内容或位置，这是“破解”代码的另一种方法。 />
有时候，我想这适用于解密的任何尝试，无论该算法，可以访问部分纯文本还是纯文本的类型足以获取其余部分。如果您被指控向敌人兜售国家机密，此类诉讼可能不会在法庭上站出来。有时候，这就是所需要的，尤其是如果可以证明的话。例如：netflix密码已知为四位数；如果由于未使用真正的随机数生成器而导致部分解密导致4位数字中的3位数字出现，那么用蛮力将自己的方式逼到丢失的数字很简单。证据？只需使用它，看看它是否有效。

密文的长度也是有用的信息。如果您正在调查下载非法音乐的过程，那么1MB的加密文件可能会很有趣。除非调查人员也可以访问实现源，并确定密文的文件大小也是混淆的一部分，否则可能会忽略长度为几KB或几GB的文件。

可以访问元数据-正在加密的明文类型-也可以提供帮助。如果知道明文是可执行文件或文本文件，则部分解密可以排除某些比特。

OTP在数学上证明是坚不可摧的。但这还不是全部，也不是破解密文的唯一考虑因素。重要的细节（难道不是细节中总是魔鬼吗？）在于密码，硬件，密钥管理以及所有方面的社会方面的实现。在确保密文的安全性方面，每一项都和另一项同样重要，并且任何一项执行不当都会泄露明文。

他们说，链条只能

关于随机性...的确，当今的PC在生成真正的随机数方面仅比其前辈略胜一筹-也就是说它们不能做到。但这也不完全正确。这取决于获得随机数所需的努力。如果您使用完全专用于抛出随机位的芯片，那么我会说结果看起来并不理想。毕竟，计算机的输出趋于一致。但是，如果算法依赖于模拟数据，例如房间或CPU温度，一天中当前的纳秒（刻度）或操作员的键入速度，或者选择了操作员随机输入的第n个字符，等等。 ，它可以创建真正的随机结果-但要花费大量时间和精力来实现它，并且某些用户可能不想要它。

OTP对结果的随机性非常敏感。并不是说11111111比00101101或多或少是随机的。相反，如果可以推断出，例如，每8位始终为“ 1”，那么这对破解您的密文很有帮助。知道这样的模式可以放弃算法的实现，而后者又可以放弃有关可以推断出的其他位的更多信息。在这种情况下，知道位8始终为“ 0”可能会忽略明文是文本（而不是二进制）。

EDIT：

OTP并不总是最好的算法。这是一把双刃剑。
如果您被指控犯罪-例如，拥有国家机密-并且检察官知道您使用了OTP，并且检察官是不道德的，则他可以组成一个“密钥”来解密密文，并显示伪造的状态不利于您的秘密。

除了产生不同的密钥以将密文解密为变黑的鸡翅的配方外，您可以做完全相同的事情。

你们都证明了所提供的证据值得怀疑，而没有其他辅助证据：检察官将需要您的实际密钥以及密文和明文，并证明您拥有这三者。此外，他还需要证明您没有其他OTP密钥。

所以从理论上讲，您可以在“我的文档”文件夹中保留两个完全可见的OTP密钥，其中一个解密为状态机密，其他解密到变黑的鸡翅食谱。为了说服法官和陪审团，一个密文既是该死的非法国家机密，又是一个有用且美味的熏黑鸡翅配方，他将做大量的解释。

使用任何其他算法，检察官仅需要破解的密文（明文）-密钥是无关紧要的。他甚至不必证明您拥有密钥，甚至不需要明文，因为只有一个密钥，只能导致国家机密。

在这种情况下，与您的密文是否可破解或算法是否可破解无关紧要：即使可以，也需要其他支持证据。实际上，检察官似乎不想提任何有关密文的内容-即使在可见的情况下也带有“实际”密钥（注复数）。

除了检察官的情况外，这可能是雇员/雇主的情况-拥有健康记录。或正处于令人讨厌的离婚之中。

也可能是密文产生相似的结果：例如，有10,000个OTP密钥，每个密钥生成纯文本，而不是您的Netflix帐户的密钥。尝试窃取Netflix帐户的人会比用暴力破解更好的时间，而不是弄清楚您真正用来隐藏Netflix密码的10,000个密钥中的哪个。拥有一个可以产生多种有用或可理解的明文的密文，而OTP可以做到这一点，那么您就可以使用OTP了（或者令人头疼……如果您必须确定哪个是真实的，哪个是红鲱鱼）。

全面披露：我不是律师。我在法律领域也没有任何经验。所以我对法律的回答只是一种意见。

#7 楼

我有点不同意这里的共识论点。至于


11111111111111的随机性比01101001001101


是的，这确实有意义。您已经在对David Schwartz答案的评论中讨论了此问题。明显的区别在于Kolmogorov的复杂性。他指出了一个问题，即柯尔莫哥洛夫的复杂性取决于语言，而语言最终是任意的。好吧，原则上是正确的，但是对于任何一种实用语言，人们都可以选择11111111111111实际上比011101001001101的复杂度要低。这对于这个问题确实很重要，因为从随机算法中得出这样的“简并字符串”在指数上是不可能的。 （事实上​​，这就是它们具有较低的Kolmogorov复杂度的原因：任何一种语言都只能希望压缩非常不寻常的数据。）
这意味着，对于实际大小的消息，这些简陋的情况将永远不会发生。宇宙。这包括原始的纯文本，这意味着在现实世界中对一次性键盘的暴力攻击甚至无法考虑正确的密钥。

现在您说，如果，从理论上讲，我们有一个元宇宙，其中可以详尽地检查这些指数上不太可能的可能性。好吧，但这对您没有帮助，这是一次性键盘的特别之处。
因为一次性键盘与消息一样大，所以您需要考虑所有可能的按键。这就引出了无限的猴子定理：是的，这些家伙将设法产生原始的纯文本。但是，他们还将制作完整的《哈姆雷特》剧本，并且消息的形式略有变化，德国人期望诺曼底而不是加来海峡发动主要进攻。在物理学中，我们一直都在处理状态的概念，这些状态在原理上可以是随机的，就像其他状态一样，但是在非常真实的意义上可以区分。正是这些现象促使了熵的概念。

一个例子：考虑具有室温下这种分子具有典型能量的数百万个氮分子。统计力学的热平衡现在是宏观状态，每个可能的微观状态均等可能发生。因此，其中包括某些区域看起来像这样的状态：



以及同一区域看起来像这样的状态：



以及同一区域的状态如下所示：



好吧，最后一个肯定是不同的野兽。这是固态。但是我们都知道氮在室温下不是固态的，不是吗？
–实际上我们不是。微观的物理定律绝对不能说固体空气的砖块不会突然凝结并掉落在你的头上。但是，这种状态的熵比气体状态的指数低。因此，我们完全有信心，这将永远不会发生在我们的一生或宇宙中。

#8 楼

假设密钥是随机选择的，并且密钥和消息的长度相同，并且密钥在消息之间不被重用，那么拥有密文会为您提供0个与明文有关的信息。

对于密文的每个位，都有两种可能性：相应的密钥位为0，相应的明文位与密文位相同；或密钥位为1，而明文位与密文位相反。通过假设密钥是未知的和随机的，两种可能性都是相同的-并且对称地说，无论密文位是0还是1，这都是正确的。因此，除非我们不加密码，我们对密文的知识无法做任何事情也有钥匙的知识。密码学完美的定义是所有安全性都在密钥中，因此按此标准，OTP是完美的。那么BS1至少是BS2的一部分或包含BS2的一部分。


该声明通常无效。您在这里隐式地做两件事。首先，您假设使用一种压缩算法（希望这是一种固定算法，否则我们将永远不会同意“可压缩”的含义）。然后，假设使用此算法可压缩正确的明文。也许这是真的，也许不是。如果您假设是这样，那么您将假设您具有有关纯文本的先验知识。尝试通过使用各种密钥解密密文来“破坏” OTP并查看哪一个为您提供最佳的可压缩性不会给您任何其他信息，因为OTP解密同样有可能产生任何给定的字符串作为压缩器的输入，因此，您也可以简单地为压缩器提供随机输入，并查看压缩效果良好的输入。这将完全一样。而且，如果一种不需要密文作为输入的算法的性能与您提出的算法完全一样，那么您实际上就无法解密任何东西，可以吗？您只需从压缩算法本身所隐含的先前分布中选择随机的合理消息即可。

#9 楼

可压缩性的概念仅适用于某些位模式比其他位模式更可能的方案。如果所有位模式都同样可能，那么没有压缩方案会比简单地将输入作为输出来效率更高。

由于我们在这里处理的是指定位数的每个可能的输出，并且每个都是同样有可能，没有任何一种压缩方案能比标识做得更好。因此，没有任何位模式是可压缩的。

如果BS3可压缩，那将是正确的。但是考虑到随机的一次性填充的属性，没有位模式是可压缩的。

#10 楼

当您使用“ 00000000…”之类的OTP时，可能看起来像是在向纯文本提供一些额外的信息（因为在这种情况下，纯文本等于密文），但这实际上是一种错觉。当攻击者看到消息“你好吗？”时，可能是消息“你好吗？”。 OTP为“ 000000000000”。但这可能是长度相同的任何其他消息，例如“您很臭！！”。由于可以以相同的概率生成任何OTP，因此攻击者无法从消息中做出比仅从消息长度中得出的更多猜测。

（也许攻击者可以猜测“如果您发臭了， !!!”比“你好吗”更有可能，反之亦然，但这必须是先验的知识。即使知道消息的长度，她也可以做出相同的猜测。）

实际上，确保OTP中没有某些类型的规则性会使该方案更弱（至少在理论上），而不是更强，因为攻击者可以排除某些可能的明文。

#11 楼

您已经有了许多漂亮的答案，但让我再加一个角度：

密钥

在有关加密算法的许多论点中，密钥与其他一切。关键是通常在技术性（数学密码分析）和“现实世界”之间进行“切割”。

轻松思考密码学的方法是“我真的不知道钥匙”。在错误的算法中，即使对密钥没有丝毫的了解（即使能够弄清楚原始密钥），也可以实现很多目标。但是，尽管如此，在进行密码分析的技术/数学部分时，您仍会认为该密钥是真正的秘密，并且未知-主要是因为这是该技术中最有趣的应用。是一个完全不同的攻击角度-您可以进行社交工程；您可以尝试安装按键记录器；您可以在受害者进入PW之后冻结受害者的笔记本电脑，并希望在某处未分配的RAM中找到它，依此类推。所有这些技术都是完全有效的，而且可能所有这些技术都比密码分析更容易/成本更低。因此，我们通过假设我们不知道密钥来将密钥管理与实际加密分开，因为在这种情况下，其他所有问题都将毫无意义。

算法

除此以外，该算法则相反。隐藏该算法从来都不是明智的选择，这仅仅是出于默默无闻的安全性，根本不会增加实际的安全性。因此，在评估加密方案的安全性时，我们可以放心地假设我们确实知道完整的算法。如果算法因为已知而变得不太安全，那么它首先就是不安全的。

OTP

因此，OTP很特别，因为它们将这种思路带到了极致：只有钥匙。这样的加密算法甚至还不够复杂，不值得使用“算法”的名称，它是一个简单的按位运算。进行OTP的前提是，在密钥是安全的假设下，甚至没有什么可攻击的。该算法非常简单，一旦您拥有了密文和密文，便立即拥有了完整的密钥。没问题，因为在正确的OTP中，无论如何您将只使用一次密钥。因此，如果攻击者已经知道明文和密文，那么通过简单地计算密钥就不会获得任何其他好处。

您的问题

我觉得很难遵循您提供的“证明”。我猜您实际上在问的是“ OTP到底是111111111 ....还是0000000 ....还是像0001000000000000 ...这样的病态。”。好吧，没有什么可以阻止您检查生成的OTP的某些非常基本的属性；例如，对于大量真正随机的位，您希望0的计数与1的计数大致相同；以及每个可能的数字对的计数大致相同，依此类推。您可以来回争论是否有必要确保“ 1 in 2 ^ 1024”的情况或您所拥有的位数不发生，但是如果您足够偏执，为什么不这样做呢？检查OTP的许多不同属性非常容易。

#12 楼

这个答案有两个层次：通用和特定。特定的问题解决了单个加密消息的解密问题，即特定加密系统产生的所有消息的解密问题。

起点是假定消息实际上包含数据。这就为它提供了某种模式，通常是某种语言，然后提供了解密的句柄。实际上，这就是我们在阅读纯文本时所做的；我们将解释写入语义的内容，使我们的大脑可以吸收。

一次性填充板的作用是阻止将第一级裂纹发展为整个系统的通用裂纹，因为应该没有共同点垫之间接地。但是，这不能完全保证，因为需要某种种子来生成伪随机序列。

关于加密的最重要的事情不是它永久地保存数据内容，而是保持足够长时间的密封性，以使其相关性降低，例如，如果某军方计划进行一次突击攻击，则该攻击将在代码被破坏之前发生。

我会留给其他人讨论数学，但是事实是存在一个关键，这意味着从理论上讲，任何信息在强力攻击下都是易碎的。有时，双重加密实际上会产生可利用的漏洞，有时，仅是简单的草率思维便会暴露出密钥。我亲自与一位系统管理员一起通过一次简单的检查就破解了一个主要系统，因此漏洞利用得到了迅速纠正：这是出于荣誉的动机。再说一次，我有一个天才的智商，曾受一位开国元勋的教育，在代码破坏者离开后，实际上是Dollis Hill的系统经理。

问题的反面是，加密的消息还必须能够在短时间内进行解密：如果时间紧迫的消息花费的解密时间比重要的时间长，则毫无意义。同样，解密设备本身也必须在所有位置都是安全的，丢失了数台加密机，使布莱奇利公园（Bletchley Park）有了指向通用谜团的巨大指针。这是安全专家方法的一个子集，安全专家的理想机器与电源断开，用铅包住，用二十粒饲料厚的混凝土石棺覆盖，然后掉入您最近的火山的火山口中（佛罗多解决方案！）。它可能非常安全，也完全不可用。折衷在于弱点。一次性垫被使用两次，以进行编码和解码。输掉任何一个，游戏就在进行中。曾经从未有过的男人就是一个很好的例子，该代码出售了赌博。