我想对“完全保密”一词的含义进行清楚(但可能不那么深入)的解释。假设某个变量将是某个密文的密钥。除非我混淆了一些概念,否则一次性密码是唯一已知的具有完全保密性的密码,因为没有足够的资源足以破解它。的弱点,这就是为什么我不理解大多数有关它的文档。

#1 楼

完全保密(或信息理论上的安全)意味着密文不传送有关明文内容的信息。实际上,这意味着,无论您拥有多少密文,它都不会传达有关明文和密钥是什么的任何信息。可以证明,任何这样的方案都必须至少使用与纯文本一样多的密钥材料进行加密。就概率而言,这意味着可能的明文的概率分布与密文无关。
我们将其与语义安全性进行对比,我通过引用Goldwasser&Micali 1984年的开创性论文来定义语义安全性:

在给定密文的情况下,无论是关于明文的有效计算方法,还是在没有密文的情况下也可以有效计算的方法。正确使用时,One Time Pad(OTP)是信息理论上安全的,这意味着它不能通过密码分析来破坏。但是,可证明的安全性的一部分在于,需要与要加密的明文一样多的密钥材料。这样的密钥需要在两个通信者之间共享,这基本上意味着您必须通过完全安全的协议(例如,通过人工/受信快递)将其提供给其他人。因此,实际上,它只允许您提前召开可信任的会议,而不是在传输秘密信息时进行。
为了说明这一点,请考虑如果尝试强行使用OTP会发生什么?由于您已允许攻击者无限的计算资源,因此攻击者可以继续猜测密钥并计算适当的明文,直到测试完每个密钥为止。假设该消息的长度为$ b $位,这将给他留下$ 2 ^ b $个可能的键,每个键都会生成一个唯一的纯文本,从而使$ 2 ^ b $个纯文本。在这里重要的是,这意味着它们将具有与可能的长度$ b $的位字符串相对应的候选纯文本。这意味着,即使您知道消息是“在2 ?:15在体育场与我见面”(其中?为0、1,2或3),您仍然不知道?是什么,因为可能的纯文本将包含具有每个可能值?的字符串。
我们现在使用的大多数密码方法在计算上都是安全的。有很多不同的方法可以做到这一点,我将简要介绍其中的一些。我们可能想出了一个很难解决的问题(例如,Diffie-Hellman问题或离散对数问题)。也就是说,我们证明“如果您可以破解密码,就可以解决[硬问题]”,这意味着我们的问题至少像[硬问题]一样难以解决。因此,如果确实难以解决问题,则必须破解我们的加密。


#2 楼

完全保密的概念是,给定来自完全安全的加密系统(或密码)的加密消息(或密文),密文绝对不会泄露未加密的消息(或明文)。

完全秘密的密文还具有其他几个等效属性:


即使给定了两个明文,一个是真实的,对于密文,也无法区分哪个明文是真实的(完美的消息不可区分性)
有一个密钥可以将每种可能的明文加密为每种可能的密文(完美的密钥歧义性)(*仅当所用密钥的大小与消息的大小相同时才如此) >
在实践中,完全保密的意思是,对密文进行任何计算都不会给您带来任何有关明文或密钥的知识。
这显然是密码的一种理想特性,并且确实存在完全秘密的密码:例如一次性密钥。

完全保密的缺点是,可以证明,所使用的密钥比纯文本短的密码不能完全保密,因此实际上您只需更改从明文的传输到密钥的传输,安全地传输消息的问题。 (一次性密码夹存在此问题,也存在其他实际问题。)

在实践中,可以使用一次性密码夹的外部利基应用程序中,密码的密钥长度通常短得多(通常在128个之间)和几千位)。这些密码当然不能具有完美的保密性(因为密钥比消息短),因此(尤其是在破解时)也可以屈服于泄露明文甚至密钥信息的计算攻击(有些是实践的,有些是理论的)。

我们使用语义安全性或密文不可区分性的相对较弱(但实际上仍然很强)的概念来评估和描述各种情况下非完美保密密码的安全性。不完全秘密的密码的强度通常用最著名的破坏密码攻击的计算复杂性(在计算和/或内存中)来表示。

#3 楼

非正式地,如果您从一个完全安全的加密系统中截取密文,则可以找到一个密钥,该密文可使密文解密为您想要的任何消息(长度正确)。因此,在不知道作者实际选择了哪个键的情况下,您永远不会学到有关该消息的任何信息。即使您尝试所有可能的密钥(因为所有密钥都会将密文解密为可能有效的消息),该设置仍然有效

评论


$ \ begingroup $
请注意,只有当密钥空间至少与明文空间一样大时,才能满足此属性(因此,除OTP之外的所有现代密码都会自动无法提供完美的保密性)
$ \ endgroup $
–托马斯
2012年9月28日下午3:54

$ \ begingroup $
谢谢!我对现在的情况有一个清晰的认识。因此,如果以某种转换密码将每个明文块分配给一个完全随机的密钥...这是否实现了完美的保密性?似乎是这样,因为您不可能仅凭密文就无法从中学习任何东西……但是,由于缺少xor,它与一次性填充垫有所不同,因此它“不能”具有完美的保密性, 对?如果我要提出另一个问题,我深表歉意。
$ \ endgroup $
–艾米尔
2012年9月28日下午4:11

$ \ begingroup $
@Emyr:在换位密码中(至少,据我所知),没有密钥可以将“ 1111”映射到“ 0000”,因此,当接收到0000密文时,我们知道1111不是纯文本。因此,这不是一个完美的密码。
$ \ endgroup $
–PaŭloEbermann
2012年9月28日7:31

#4 楼

完全保密本质上意味着这些概念:


$ P(M = m | C = c)= P(M = m)$,即看到密文不会给您任何额外的信息关于明文。
$ P(C = c | M = m_0)= P(C = c | M = m_1)$,即密文$ c $的概率同样适用于2条不同的消息。
密钥只要消息和密钥应唯一地使用,概率为$ 1 / | K | $,其中$ | K | $是密钥空间。


#5 楼

用最简单的术语来说,完美的保密是完全,完全无模式的数据。然而,在它里面仍然是您的秘密。 ArtofTheProblem提供了一个很好的简单解释。

#6 楼

重要说明:


一次性键盘不会“不提供有关邮件内容的任何信息”。这是一个谬论。它仍然显示信息。例如,仅知道存在交换的消息就可以告诉我们一些信息。
如果满足一次性使用的假设,我们将拥有的一种加密方法可以最大程度地减少泄漏的信息。这不同于“不提供信息”或“零信息”。

请进一步阅读信息理论:https://en.wikipedia.org/wiki/Information_theory

评论


$ \ begingroup $
通常假定消息长度(及其存在)是公共的,因为任何有限密码都会泄漏一些有关它的信息。 OTP隐藏了有关邮件内容的所有其他内容。
$ \ endgroup $
–otus
16年1月18日在16:01

$ \ begingroup $
具有“通常假定”的东西并不能消除这样的事实,即它确实揭示了一些大于0位的信息。
$ \ endgroup $
–洞穴人
16年1月18日在23:01

$ \ begingroup $
如果您不知道信息,则不透露信息。但是,是的,这是一个警告,有时需要考虑到。
$ \ endgroup $
–otus
16年1月19日在6:57

$ \ begingroup $
当然,如果我们知道内容,则消息的熵= 0位,并且任何操作都无法获得任何信息。但是,我们正在讨论消息为“未知”的情况。信息论的事实是,揭示一条消息的长度确实会揭示一些大于0位的信息。在大多数情况下,它是一个很小的数目,但是仍然大于0。揭示一条消息的长度不揭示信息的唯一情况是,世界上所有消息的长度都是恒定的(不是),因此可以揭示。
$ \ endgroup $
–洞穴人
16年1月19日在11:01

$ \ begingroup $
我的意思是前提是,攻击者知道消息的长度,但对消息的内容一无所知。 (并不是说他们已经知道内容了。)在这种情况下,OTP不会放弃有关该内容的任何其他信息。有时,这种前提并不合理,但它是标准的前提,因为一般而言,没有什么更强大的了。
$ \ endgroup $
–otus
16年1月19日在15:31

#7 楼

在完全保密的情况下,如果提供了密文数据,则无法在密文和明文之间派生任何模式或联系。密钥大小等于明文的地方。这会导致完全保密。 >密钥共享:密钥需要亲自或非常可靠的快递人员共享


评论


$ \ begingroup $
您可能不是说“此解决方案可行”,不是吗?
$ \ endgroup $
–otus
18年1月3日,11:23

$ \ begingroup $
仍然被否决为1.答案的第一部分不包含其他答案中尚未发布的任何内容,并且2.第二部分是错误的,因为OTP确实用于特定的使用场景-也不可行措辞强硬(过去我曾因措辞不强而受到批评,这不是人身攻击,我也犯了罪;))。
$ \ endgroup $
–马腾·博德威斯♦
18年1月3日在13:09

#8 楼

简而言之:这意味着无法确定该消息是否以及何时被破解。

因此您可以破解该消息,但您永远不会知道它是否被破解。