一次一密是一种加密方法:将消息与秘密且均匀随机的密钥结合,密钥长度至少与消息相同,并且绝不重复使用。满足这些条件时,对于不知道密钥的观察者,密文不会泄露任何有关消息内容的信息。这种性质称为完善保密性,即使对手拥有无限的计算能力也依然成立。一次一密是密码学中的一项基础性成果,但它对密钥的生成、分发、存储和使用有着严格要求,因此实际应用受到限制。
工作原理
在二进制形式中,一次一密将消息和密钥表示为等长的比特序列。加密时,对相应位置的比特进行异或运算,通常记作 :
其中, 为明文, 为密钥, 为密文。异或运算在两个输入不同时输出 1,相同时输出 0。
解密时,使用同一密钥执行相同的运算:
这一方法成立,是因为 。例如:
明文: 10110010
密钥: 01101101
密文: 11011111
将密钥与密文进行异或运算,即可恢复明文:
密文: 11011111
密钥: 01101101
明文: 10110010
同样的原理也适用于比特以外的符号。如果用 0 至 25 的数字表示字母,加密时可将每个明文符号与对应的密钥符号相加,再对 26 取模;解密时则减去密钥,并对 26 取模。密钥符号必须从同一字母表中独立、均匀地选取。
英文名称中的 pad(本册)一词源自早期的实体实现方式:通信双方各持有一本内容相同、记录随机密钥材料的密码本,每页或每一部分只使用一次,随后销毁。这一数学构造并不依赖纸张,密钥也可以采用电子形式存储。
实现完善保密性的条件
只有同时满足以下所有条件,一次一密才能提供其标志性的安全保证:
- **均匀随机:**所需长度的每一个可能密钥出现的概率都相同。对于二进制密钥,这意味着各比特相互独立,且取 0 或 1 的概率相等。
- **独立性:**密钥的生成独立于消息。
- **长度充足:**每个消息比特或符号,都要消耗一个对应的、尚未使用的密钥比特或符号。
- **仅使用一次:**无论是在同一条消息内,还是在不同消息之间,密钥的任何部分都不能用于加密不止一个明文片段。
- **密钥保密:**对手无法获得用于加密该消息的密钥材料。
这些条件针对的是密钥实际的生成和管理方式,而不只是其外观。一段看似杂乱的长序列不一定具有随机性。书籍中的文字、反复使用的密码以及可预测的序列,都不符合这些要求。
伪随机数生成器将有限的内部状态或种子扩展为更长的序列。即使生成器在密码学意义上足够安全,使用其输出作为密码本,通常也无法获得真正的一次一密所具有的信息论保证。此时,安全性依赖的是有关区分或预测所生成序列之难度的假设。
为什么密文不泄露任何信息
完善保密性是信息论中的一个概念。将消息、密钥和密文分别表示为随机变量 、 和 。假设消息的长度固定为 比特,密钥从所有 个可能的比特串中独立、均匀地选取。
对于每个候选消息 和观测到的密文 ,恰好只有一个密钥能使二者对应:
由于该密钥出现的概率为 ,
因此,无论加密的是哪条消息,密文都具有相同的概率分布。由此可得:
观测密文不会改变对手对任何候选消息的概率判断。
这并不意味着每个明文出现的可能性都相同。观察者可能事先就知道,某些消息比其他消息更有可能出现。完善保密性意味着,密文不会提供任何额外证据,帮助观察者在这些消息之间作出选择。
这也解释了为什么穷举密钥无法唯一确定一次一密消息的原文:尝试所有密钥,会得到相应长度的所有可能明文。仅凭密文,无法判断哪一个才是原文。
密钥长度要求
对于能够无差错解密的完善保密加密,在标准假设下,香农界指出:
其中, 表示信息熵。
如果每个 比特消息都可能出现,且出现的概率相等,那么消息熵就是 比特,因此密钥熵至少也需要 比特。更一般地说,要对全部 个可能消息提供完善保密性,可能的密钥数量至少必须与消息数量相同。
因此,一次一密并不是某种低效的实现,仿佛换一种方法就能用极短的秘密提供同样不受计算能力限制的保证。它对密钥的要求反映了信息论的一项根本限制。
密钥重用及其他失效方式
重复使用密码本
如果两条消息使用同一密钥加密,
则有:
密钥被抵消,从而暴露两份明文之间的关系。这通常称为两次一密问题。
这并不意味着在所有情况下都会自动泄露两条消息的全部内容。然而,自然语言、文档格式、协议头以及其他结构化数据都包含大量冗余。对一份明文的猜测可能暴露另一份明文的对应部分。如果攻击者知道某个明文片段,就能直接得到对应的密钥片段:
使用同一密钥片段加密的其他内容也就随之暴露。即使只重复使用密码本的一部分,也会危及消息中的对应部分。
存在偏差或可预测的密钥
如果某些密钥比其他密钥更容易出现,那么观测密文就可能使某些明文比其他明文显得更有可能。密钥比特之间的相关性、随机数生成过程中的缺陷以及确定性模式,同样可能使完善保密性的证明不再成立。
物理随机源需要经过工程设计和统计特性评估;仅仅来自物理过程,并不能保证输出相互独立且均匀分布。
已存储密钥的泄露
密码本包含解密相应密文所需的全部信息。因此,存储中的副本、备份、打印记录或被攻陷设备中的副本,都可能使系统失守,而无须进行任何密码分析攻击。
实际实现还必须记录哪些密钥位置已经使用。状态丢失、恢复备份或分配范围重叠,都可能导致意外重用。
保密性不等于身份认证
一次一密本身不提供身份认证,也不保证消息完整性。攻击者可以通过修改密文,以可预测的方式改变解密后的明文。
如果攻击者将 替换为
接收方得到的就是:
因此,翻转密文中选定的比特,会导致明文中相同位置的比特发生翻转。攻击者不需要知道密钥,不过,要作出有实际意义的修改,可能需要了解消息格式。
这种性质称为可篡改性。要防止主动修改,需要额外的机制,例如消息认证码,并配合恰当的密钥分离和协议设计。信息论安全的认证是可以实现的,但它属于另一种构造,有其自身的假设和伪造概率界限。
一次一密本身也不会隐藏消息长度、传输时间、通信双方或其他元数据。采用固定长度的消息和填充,可以减少一部分长度信息泄露,但加密运算本身并不提供通信流保密性。
历史
1882 年,弗兰克·米勒在一份方案中给出了一种相关随机密钥密码的早期描述。1917 年,吉尔伯特·弗纳姆开发了一种电传打字机加密系统,将消息信号与密钥流结合。在这一发展过程中,约瑟夫·莫博涅被认为认识到了随机且不重复的密钥材料的重要性。
“弗纳姆密码”一词有时用于指一次一密,但这一用法并不总是准确:只有当密钥流满足一次一密的要求时,将文本与密钥流结合才能实现完善保密性。
克劳德·香农在其 1949 年的论文《保密系统的通信理论》中建立了完善保密性的数学理论。他的工作既解释了一次一密的安全性,也阐明了完善保密加密所受到的限制。
20 世纪,一次一密曾用于军事、外交和情报通信。“维诺纳计划”是密钥重用造成后果的一个著名案例:苏联密钥材料的重复使用,使原本受到保护的部分通信得以被密码分析破解。弱点在于密钥材料的管理和重用,而非完善保密性的数学结论遭到了推翻。
实际用途与局限
阻碍一次一密广泛应用的主要因素是密钥分发。要交换一吉字节的加密数据,通信双方就需要一吉字节内容相同、事先共享的秘密密钥材料。分发这些材料可能需要可信信使、安全的实物交接,或其他机制,而这些机制的安全性必须另行评估。
不过,在通信量有限且能够提前安全分发密钥材料的场景中,一次一密仍然有用。其加密运算简单,既可手工完成,也可通过电子设备实现,而且安全性不依赖计算困难性假设。
多数现代通信系统则使用短密钥,配合实用的对称加密算法,例如高级加密标准,或使用流密码。流密码在操作方式上类似一次一密,因为它们同样将明文与密钥流结合,但其密钥流由较短的秘密密钥生成。它们提供的是计算安全性,而非完善保密性。
使用公钥密码学传送密码本,并不会自动使整个系统获得信息论意义上的保密性:如果攻击者日后破解了密钥传输机制,就可能恢复密码本。同样,量子密钥分发可以为一次一密提供密钥材料,但它需要一条经过认证的经典信道,而且仍然受实现层面假设的约束。
正确实现的一次一密所具有的数学保证,不会因量子计算机或任何其他计算能力的提升而受到影响。不过,它无法防范终端被攻陷、密码本被窃取、随机性存在缺陷、密钥重用,或消息在缺乏认证保护的情况下被修改。