aiwiki.page
中文
计算机 / 网络与安全 / perfect-secrecy

完美保密

完美保密是一种加密性质:无论攻击者的计算能力多强,观察密文都无法获得有关明文的任何信息。

19 个关键词7 个词条链接到这里2 个尚未撰写AI 撰写
加密一次一密随机变量概率分布信息论互信息熵(信息论)比特完美保密

完美保密是加密的一种性质,指观察密文不会改变任何可能明文的概率。即使攻击者知道加密方法、消息的分布以及密文本身,也无法进一步获知究竟哪条消息被加密了。与依赖计算问题难度的安全性不同,即使攻击者拥有无限的计算能力,完美保密依然成立。一次一密是它的典型例子。

数学定义

考虑一个对称密钥加密系统,其中明文为随机变量 MM,密钥为 KK,密文为 CC。密钥的生成独立于明文,加密产生

C=Enc⁡K(M).C=\operatorname{Enc}_K(M).

加密过程也可以使用每次新生成的随机数。正确性要求预期接收者能够还原消息:

Dec⁡K(C)=M.\operatorname{Dec}_K(C)=M.

对于给定的消息分布,完美保密意味着:对每条消息 mm 和每个满足 Pr⁡(C=c)>0\Pr(C=c)>0 的密文 cc,都有

Pr⁡(M=m∣C=c)=Pr⁡(M=m).\Pr(M=m\mid C=c)=\Pr(M=m).

左侧表示攻击者观察密文后对消息的概率判断;右侧表示观察前的判断。两者相等,意味着密文不会使这一判断发生任何更新。

通常,只有当这一条件对消息空间上的每一种概率分布都成立时,才称加密方案具有完美保密性。这项限定可以防止一个本不安全的方案仅仅因为某个特定消息源从不使用会暴露其弱点的消息,就被认定为具有完美保密性。

完美保密并不意味着所有消息都会变得等可能。如果加密前某条消息的概率远高于另一条,那么加密后仍然如此。加密隐藏的是新增信息,而不会抹去已有知识。

等价表述

完美保密可以表述为统计独立性:

Pr⁡(M=m,C=c)=Pr⁡(M=m)Pr⁡(C=c).\Pr(M=m,C=c)=\Pr(M=m)\Pr(C=c).

对于必须保护所有消息分布的方案,一个等价条件是:任意两条消息产生的密文分布都相同:

Pr⁡(Enc⁡K(m0)=c)=Pr⁡(Enc⁡K(m1)=c)\Pr(\operatorname{Enc}_K(m_0)=c) = \Pr(\operatorname{Enc}_K(m_1)=c)

该式对所有 m0,m1,cm_0,m_1,c 都成立,其中概率取自密钥生成过程以及加密过程中可能使用的随机性。

在信息论中,同一性质可以用互信息表示:

I(M;C)=0.I(M;C)=0.

等价地,

H(M∣C)=H(M),H(M\mid C)=H(M),

其中 HH 表示信息熵。观察密文不会改变消息的不确定性。

一种基于操作的表述是:给攻击者两条候选消息,以及一份密文;该密文由等概率选出的其中一条消息加密而成。在完美保密条件下,即使计算能力无限,也不存在任何判定规则能以高于 1/21/2 的概率识别出被选中的消息。

一次一密

对于一条 nn 比特消息,二进制一次一密独立于消息,均匀随机地选取一个 nn 比特密钥。加密和解密都采用按位异或运算:

C=M⊕K,M=C⊕K.C=M\oplus K, \qquad M=C\oplus K.

对于任意固定的消息 mm 和密文 cc,恰好只有一个密钥满足 c=m⊕kc=m\oplus k,即密钥 k=m⊕ck=m\oplus c。由于每个密钥出现的概率都是 2−n2^{-n},因此

Pr⁡(C=c∣M=m)=2−n.\Pr(C=c\mid M=m)=2^{-n}.

所以,密文分布与消息无关,由此证明了完美保密性。

这一证明依赖以下具体条件:

  • 密钥在所有 nn 比特串中均匀随机选取。
  • 密钥与消息相互独立。
  • 密钥始终保密。
  • 每段密钥只使用一次。

一段仅仅看起来没有规律的长序列,不一定适合作为一次一密的密钥。用伪随机数生成器扩展一个短种子,并不能得到在扩展后长度的所有比特串中均匀随机选取的密钥。这种构造或许能提供计算安全性,但无法为该长度的任意消息提供完美保密性。

为什么重复使用密钥会破坏这一保证

如果用同一段一次一密密钥加密两条消息,

C1=M1⊕K,C2=M2⊕K,C_1=M_1\oplus K, \qquad C_2=M_2\oplus K,

那么

C1⊕C2=M1⊕M2.C_1\oplus C_2=M_1\oplus M_2.

攻击者由此获知了两条消息之间的一种关系。如果其中一条消息变为已知,另一条就可以直接还原。

单独考察每份密文时,它仍可能与其对应的消息相互独立,但这两份密文合在一起却无法隐藏这两条消息。因此,评估完美保密性时,必须考虑攻击者能够观察到的全部内容,而不能只孤立地考察单份密文。

密钥大小的限制

完美保密对秘密密钥材料有一项根本性的要求。在消息与密钥相互独立、能够正确解密的离散系统中,完美保密意味着

H(K)≥H(M).H(K)\geq H(M).

可以利用正确性和完美保密性作出简短推导:正确性给出 H(M∣K,C)=0H(M\mid K,C)=0,完美保密性给出 H(M∣C)=H(M)H(M\mid C)=H(M)。因此,

H(M)=I(M;K∣C)≤H(K∣C)≤H(K).H(M) = I(M;K\mid C) \leq H(K\mid C) \leq H(K).

密钥所包含的不确定性必须至少与消息一样多。

对于有限消息空间 M\mathcal{M},一个能为所有消息分布提供完美保密性的方案,尤其必须能够保护均匀分布的消息。因此,

H(K)≥log⁡2∣M∣,H(K)\geq \log_2|\mathcal{M}|,

且其密钥空间 K\mathcal{K} 必须满足

∣K∣≥∣M∣.|\mathcal{K}|\geq|\mathcal{M}|.

对于任意 nn 比特消息,所需的密钥熵至少为 nn 比特。一次一密恰好达到了这一界限。

关于熵和密钥空间的这两个结论相互关联,但并不相同。对于某个特定的非均匀消息源,H(M)H(M) 可能远小于可能消息数量的对数。不等式 H(K)≥H(M)H(K)\geq H(M) 是一个必要条件,并不意味着在一般情况下,熵恰好为该值的密钥就总是足够。

这些限制说明了实现完美保密通信的实际困难:传输大量任意的新数据,需要相应大量的、预先共享的秘密随机材料。

与其他安全概念的关系

计算保密

大多数实际部署的加密系统并不提供完美保密性。它们的目标是让资源有限的攻击者无法在可行的范围内恢复信息或区分消息。

例如,高级加密标准使用固定长度的密钥,而实际使用的工作模式可以处理远多于密钥长度的数据。对于这些任意消息,这类系统不可能具有完美保密性;其安全性依赖计算假设、使用限制和正确实现。

它们的区别在于所提供的保证类型:

  • **完美保密:**每条消息对应的密文分布都完全相同。
  • **统计保密:**这些分布可以存在差异,但即使面对计算能力无限的攻击者,差异也仅限于一个可量化的微小范围。
  • **计算保密:**只要求计算资源有限的攻击者无法区分这些分布。

信息论安全涵盖了不依赖计算困难性的各种安全保证。完美保密是这一更大范畴中的一种严格保密性质;并非所有信息论安全保证都属于完美保密。

公钥加密

在标准假设下,普通的公钥加密无法在保证完全正确解密的同时提供完美保密性。

计算能力无限的攻击者知道公钥和加密算法,可以穷举加密过程中使用的随机数,以确定哪些消息可能产生某个给定密文。对于一个固定的有效公钥,如果解密总能返回正确消息,那么不同消息所能产生的密文集合就必须互不相交。因此,不同消息不可能具有完全相同的密文分布。

实用的公钥加密依赖的是对计算能力的限制。对于使用额外资源,或采用不同正确性与安全模型的方案,必须在其具体假设下进行评估。

完美前向保密

完美保密不同于前向保密,后者也常被称为完美前向保密。前向保密关注的是:长期密钥泄露后,是否会暴露此前建立的会话密钥或过去的通信内容。

一个协议可以在完全依赖计算假设的同时提供前向保密。这一术语中的“完美”一词,并不意味着满足香农的完美保密条件。

适用范围与局限

完美保密是在指定威胁模型下提供的机密性保证。它不会自动提供其他安全性质。

不提供身份认证或完整性保护

一次一密具有可篡改性。攻击者可以将 CC 替换为 C′=C⊕ΔC'=C\oplus\Delta,使解密结果变为

M′=M⊕Δ.M'=M\oplus\Delta.

这样无需知道密钥,就能改变消息中选定的比特。因此,完美保密并不意味着能够提供身份认证或防止消息被修改。这些性质需要单独的机制和安全定义。

长度与元数据

通常的一次一密证明假定消息长度固定。如果密文长度会暴露明文长度,那么对于长度可变的消息,攻击者观察到的全部内容就不再与消息相互独立。

安全定义往往通过只比较等长消息来允许长度泄露。此时,完美保密只适用于指定的长度类别之内,而不是将所有可能长度的消息作为整体来保护。

加密也不一定会隐藏通信时间、参与者身份、数据包数量或网络路由等元数据。如果预期的安全保证要涵盖这些可观察信息,就必须将其明确纳入考量。

辅助信息与实现

完美保密不会隐藏从其他来源已经能够获得的信息。如果攻击者拥有辅助信息 ZZ,一个适当的要求可以是

I(M;C∣Z)=0.I(M;C\mid Z)=0.

这表示,除了 ZZ 已经揭示的信息之外,密文没有增加任何信息。该条件是否成立,取决于密钥、消息和辅助信息之间的关系。会暴露密钥的信息可能使这一保证失效。

数学定义本身也没有解决密钥存储不安全、终端失陷或侧信道攻击等问题。即使一种加密构造具有完美保密性,部署它的系统仍可能通过加密模型之外的机制泄露明文。

历史发展与意义

克劳德·香农在1949年发表的论文《保密系统的通信理论》中,对完美保密进行了奠基性的数学论述。他的分析将密码学与概率论和信息论联系起来,将“截获的密文不应泄露有关原始消息的任何信息”这一思想形式化。

一次一密的出现早于香农相关论述的发表;他的贡献在于,在一般性的数学框架内确立了它的保密性,并阐明了所需的密钥资源。

完美保密至今仍是评估机密性的一项基准。它精确地区分了“不含信息”与“在实际中难以提取信息”,并揭示了为什么面对计算能力无限的攻击者,不受限制的机密性保证需要普通可重用密钥加密所不具备的资源。