我了解OTP的基础知识:$ | \ text {key space} | = | \ text {plaintext space} | $意味着完美的安全性,密钥重用会破坏这一点。

在$ N $ -Time Pad上以$ N> 1 $进行密码分析涉及在密文中查找模式;但是,这似乎都是基于模式存在于明文(例如英语)中的前提。

我的问题是:如果$ m_1 $和$ m_2 $是两个真正的随机字符串,并且它们都使用相同的OTP密钥加密以产生$ c_1 $和$ c_2 $,是否有可能从$ c_1 $和$ c_2 $中恢复$ m_1 $和$ m_2 $?

换句话说:虽然“完美的安全性”(又名完美的可区分性)显然丢失了(为两个消息构造一个区分符是微不足道的),但明文仍然安全吗?

#1 楼

是的,使用相同的“填充”加密两个不同的随机“纯文本”与使用两个不同的随机“一个”填充来加密相同的纯文本是无法区分的。在后一种情况下,您可以获得完美的保密性,因此在前一种情况下,您也将获得相应的保密性。没有考虑。更准确地说,接收者通常会在解密后使用纯文本来“执行操作”,因此,上述论点可能会失败。

例如,如果随机消息是针对易受相关密钥攻击的密码的对称加密密钥,则显然不安全地传输使用重复使用的密钥加密的消息。

评论


$ \ begingroup $
我不太确定你最初的论点。如果使用两个独立的小键盘加密单个消息,则不会降低消息的熵。在使用相同填充加密两个随机消息的情况下,您可以将随机消息上的熵降低到填充的熵(即,熵减半)。因此,在后一种情况下,您不能主张“完全保密”。
$ \ endgroup $
– Guut Boy
16年1月27日在15:28

$ \ begingroup $
a xor b || a xor c = b xor a ||异或熵完全相同。
$ \ endgroup $
–亨里克·赫尔斯特伦
16年1月27日在16:17

$ \ begingroup $
这就是我的意思,熵是相同的,但在一种情况下,您的信息是两倍长。由于完全保密性要求您保留消息的熵,因此在这种情况下,您只有应有的熵的一半。
$ \ endgroup $
– Guut Boy
16年1月27日在17:41

$ \ begingroup $
我的答案第二段没有涵盖您的观点吗?如果在传输后立即丢弃消息,则将保留消息的熵,但只有在那时,这才是您通常不希望对消息执行的操作。
$ \ endgroup $
–亨里克·赫尔斯特伦
16年1月27日在17:52

$ \ begingroup $
不,不是。我也没有看到在对手的观点中丢弃消息如何改变随机消息的熵。可以这样考虑:为了猜测两个长度为n位的随机消息,给定正确的OTP密文,您必须猜测2n位。您最多可以以2 ^ {-2n}的概率执行此操作。但是,如果使用相同的密钥对这两个消息进行了OTP加密,那么您只需要猜测n位密钥即可。您可以以2 ^ {-n}的概率执行此操作。也就是说,您滥用OTP至少损失了n位熵。
$ \ endgroup $
– Guut Boy
16年1月27日在21:36

#2 楼

如果您使用填充板$ p $加密消息$ m_1 $和$ m_2 $为

$$ \ begin {aligned} c_1&= m_1 \ oplus p,\\ c_2&= m_2 \ oplus p,\ end {aligned} $$

其中$ \ oplus $表示有限组的二进制运算(例如,对以整数nn $取模的整数进行加法,或对位串进行XOR等)和$ p $是组中的随机元素,因此,确实,仅拦截$ c_1 $和$ c_2 $的攻击者将无法恢复$ m_1 $或$ m_2 $。
但是,攻击者可以恢复

$$ \开始{对齐} c_1 \ oplus c_2 ^ {-1}&= m_1 \ oplus p \ oplus(m_2 \ oplus p)^ {-1} \\&= m_1 \ oplus p \ oplus p ^ {-1} \ oplus m_2 ^ {-1} \\&= m_1 \ oplus m_2 ^ {-1},\ end {aligned} $$

其中$ x ^ {-1} $表示$ x $的组逆。

(有趣的是,该组甚至不需要是阿贝尔语即可工作:我们需要的只是一个实际的计算逆并应用分组运算的方法。)

因此,攻击者确实获得了有关关系的信息p在$ m_1 $和$ m_2 $之间。特别是,如果他们以后发现其中一条消息,他们也将知道另一条消息,而且,更一般而言,攻击者获得的关于其中一条消息的任何信息都将为他们提供有关另一条消息的信息。 br />实质上,如果键空间(即从中随机选择$ p $的组)具有$ n $个元素,则知道$ c_1 \ oplus c_2 ^ {-1} = m_1 \ oplus m_2 ^ {-1} $将$(m_1,m_2)$的可能值数从$ n ^ 2 $缩小到$ n $。

不管如何选择消息$ m_1 $和/或$ m_2 $,以上所有内容均成立。如果它们中的两个(或什至只是一个,但全部除外)都是完全随机的,并且如果您可以保证攻击者将永远不会获得随机消息中从密文获得的信息以外的任何信息,那么,这些知识的确是,对他们没有好处。但是,正如其他人指出的那样,这几乎排除了将消息用于任何事情的可能性。 (特别是,使用$ m_1 $和$ m_2 $作为一次性垫来传输更多消息将是一个非常糟糕的主意。)

#3 楼

在所描述的情况下,您将保持完美的安全。

反过来考虑您的问题。使用密文作为OTP,并使用n-time-pad作为密文。由于您的密文是随机的,因此它们的连接结果也是随机的,可以视为OTP。在这一点上,无论OTP是什么,都已经满足了实现完美安全性的条件。

这个结论有点令人震惊。只要数据与随机数据是不可区分的(基本上必须是随机数据),就可以重用OTP来安全地传输数据。

但是您不能以可观察的方式使用随机数据。

考虑:爱丽丝有两个通讯渠道。一个人只能使用Bob知道的秘密n-time-pad传输随机数据。爱丽丝还使用OTP加密将消息发送给鲍勃。这些OTP通过第一个通讯通道发送给Bob。如果夏娃可以同时观察到这两个频道,她就可以像秘密密码一样粗暴地使用秘密的n-time-pad。

评论


$ \ begingroup $
我在stackoverflow上给出了这个答案,并被立即降低了:)
$ \ endgroup $
–马腾·博德威斯♦
2012年4月4日在18:54