← COMP5521 全部讲次
L03a-2 · 第 3 周

L03a-2 一次一密:钥匙和明文一样长,用完就扔

先补上 XOR 这块逐位运算,再一步步看一次一密怎么加密、为什么同一段密文能解出两句都通顺的话,以及它为什么很少真的被拿来用。

一句话版

一次一密(one-time pad)给每条消息配一把和它一样长的随机密钥,用完就扔。攻击者把所有钥匙都试一遍,会得到无数句通顺的话,却挑不出哪句是真的。

凯撒密码只有 25 把钥匙,一试就穿,见上一页 L03a。这一页把钥匙撑到最大,看能换来什么、又要付出什么。

先认识这几个词

词 全称 / 读法 一句人话
比特 / bit binary digit 一个 0 或 1
XOR exclusive or,异或,记作 ⊕ 逐位比较,相同得 0、不同得 1
AND / OR 与 / 或 两位都是 1 才得 1 / 有一位是 1 就得 1
可逆 invertible 知道结果和密钥,能唯一推回原来的输入
一次一密 one-time pad 每条消息换一把和它一样长的随机密钥
完美保密 perfect secrecy 看到密文,对明文的判断一点没变

一个类比:每个字母各配一个骰子

凯撒密码是全句用同一个位移。整句只藏着一个秘密数字,猜中一个字母,全句就开了。

一次一密是给每个字母单独掷一次骰子,掷出几就挪几格。第一个字母挪 17 格,第二个挪 4 格,第三个挪 22 格,彼此毫无关系。攻击者猜中一个字母的位移,对下一个字母没有任何帮助。

再进一步:你随便想一句和密文一样长的通顺的话,总能凑出一组骰子点数,让密文「解」成这句话。所以攻击者手里的密文,和任何一句等长的话都对得上。

类比在哪里失效:

  • 骰子点数要真随机。拿某本书里的字当骰子点数,看似随机,其实带着语言的规律,会被统计方法利用。
  • 骰子掷一次只能用一次。两条消息用同一串点数加密,攻击者把两段密文一对比,就能抵消掉钥匙,这在真实历史上发生过。

从零讲起

1. 先补一块:XOR 和另外两种逐位运算(补充)

它解决什么问题

计算机里的消息是一串 0 和 1。要把它加密,最直接的办法是让明文的每一位和密钥的对应位做某种运算。候选运算有三个:AND、OR、XOR。问题是挑哪个,挑错了接收方解不回来。

直觉

把三种运算都当成「两个开关决定一盏灯」:

AND 是两个开关都开灯才亮。OR 是任一个开关开灯就亮。XOR 是两个开关状态不同灯才亮,相同就灭。

加密要求的是:知道密钥那一位和结果那一位,能倒推出明文那一位。只有 XOR 每一种情况都能倒推。

一步一步看

目标:依次列出 AND、OR、XOR 的真值表,看出只有 XOR 能从结果和密钥倒推回明文。

  1. 列 AND 的真值表:0 AND 0 = 0,0 AND 1 = 0,1 AND 0 = 0,1 AND 1 = 1。

  2. 看密钥位是 0 的两行:不管明文位是 0 还是 1,结果都是 0。拿到结果 0,推不回明文。

  3. 列 OR 的真值表:0 OR 0 = 0,0 OR 1 = 1,1 OR 0 = 1,1 OR 1 = 1。密钥位是 1 时结果恒为 1,同样推不回。

  4. 列 XOR 的真值表:0 ⊕ 0 = 0,0 ⊕ 1 = 1,1 ⊕ 0 = 1,1 ⊕ 1 = 0。密钥位是 0 时结果等于明文位,密钥位是 1 时结果是明文位翻转。两种情况都能倒推。

    并排三张真值表 AND、OR、XOR,每张四行列出输入 x、密钥 k 和结果;AND 表下注「k = 0 时结果恒为 0,丢信息」,OR 表下注「k = 1 时结果恒为 1,丢信息」,只有 XOR 表用青绿色框出,注明已知结果和 k 总能推回 x

  5. 结论:三个候选里只有 XOR 可逆。

怎么算

XOR 的规则一句话:两位相同得 0,不同得 1。

它有一条关键性质:(x ⊕ k) ⊕ k = x。

意思是:同一把密钥异或两次,等于没异或。第一次把明文变成密文,第二次把密文变回明文。所以加密和解密是同一个动作,用的也是同一把钥匙,一次一密因此是对称加密。

为什么成立:k 是 0 时,两次都不变;k 是 1 时,翻转两次又翻回原样。

常见误解

以为 XOR 就是二进制加法

它是不进位的加法:1 ⊕ 1 = 0,进位那个 1 直接扔掉。普通二进制加法 1 + 1 = 10,会往高位进位。

以为 AND 和 OR 完全不能用来做任何加密

课件的结论范围是:在二进制一次一密里逐位套用时,这三个候选中只有 XOR 保证可逆。别的加密构造里 AND、OR 照样会出现,只是不单独承担「可逆」这件事。

试一下

算 1010 ⊕ 0110,再把结果和 0110 异或一次。

1010 ⊕ 0110 = 1100(逐位:1 和 0 不同得 1,0 和 1 不同得 1,1 和 1 相同得 0,0 和 0 相同得 0)。1100 ⊕ 0110 = 1010,回到了开头。

2. 一次一密怎么加密

它解决什么问题

凯撒密码整句共用一个位移,钥匙只有 25 种。一次一密要把这个漏洞彻底堵上:让钥匙多到和所有可能的明文一样多,而且每个位置的钥匙互不相关。

从哪来(补充)

最早描述一次一密的是 Frank Miller,时间是 1882 年。后来 Gilbert Vernam 发明了电传打字机上逐位 XOR 的加密,拿到美国专利 1,310,719;Joseph Mauborgne 补上了「钥匙必须随机」这一条。课件把它叫 Vernam 密码的改进。

Claude Shannon 证明了它完美保密:1945 年写在保密报告里,1949 年公开发表。

出处:Wikipedia: One-time pad

直觉

把凯撒密码里那一个 k,换成一串 k₁、k₂、k₃……,每个字母各用一个,而且每个都是独立掷出来的随机数。

到了二进制世界,「每个字母挪几格」变成「每一位异或一个随机位」,做法完全一样。

一步一步看

目标:用 attack 和一串二进制各加密一次,看出随机位移怎样打乱凯撒的规律,同一把密钥再异或就能还原。

  1. 字母版:明文 attack,掷出六个随机位移 17、4、22、9、11、13。

  2. 逐个挪:a 挪 17 得 R,t 挪 4 得 X,t 挪 22 得 P,a 挪 9 得 J,c 挪 11 得 N,k 挪 13 得 X。密文 RXPJNX。

  3. 对比凯撒:同样的 attack,凯撒全用 3,得到 DWWDFN。两个 t 都变成 W,两个 a 都变成 D,规律露在外面;一次一密里两个 t 变成了 X 和 P。

    上下两行对比:凯撒那行把 attack 每个字母都加 3,得到 DWWDFN;一次一密那行每个字母各加一个独立随机数 17、4、22、9、11、13,用青绿色标出,得到 RXPJNX;底部注明密钥和明文一样长

  4. 二进制版:明文 11011011,密钥 01101001,逐位异或得密文 10110010。

  5. 解密:密文 10110010 再和同一把密钥 01101001 异或,得到 11011011,回到明文。

    二进制一次一密五行:明文 11011011,密钥 01101001,二者异或得密文 10110010 用青绿色标出;分隔线下密文再和同一把密钥 01101001 异或,回到明文 11011011

怎么算

二进制一次一密:密文 = 明文 ⊕ 密钥,明文 = 密文 ⊕ 密钥。

意思是:每一位明文和对应位置的那一位密钥做 XOR。因为 (x ⊕ k) ⊕ k = x,解密就是拿同一把密钥再做一次。

密钥有三条硬要求:

  1. 随机,每一位独立、0 和 1 机会均等;
  2. 至少和明文一样长,每一位明文都有自己的一位密钥;
  3. 只用一次,用完就扔。

三条少一条,完美保密就不成立。

常见误解

以为密钥比明文短一点、循环着用也差不多

一循环就有两段明文用了同一段钥匙,等于用了两次,攻击者可以把两段密文异或,钥匙被抵消掉,剩下两段明文的异或,再用语言规律去拆。第 3 个概念会细讲。

试一下

明文 1001,密钥 0111,密文是什么?用同一把密钥解回来验算一次。

1001 ⊕ 0111 = 1110。1110 ⊕ 0111 = 1001,回到了明文。

3. 完美保密,以及它为什么很少真的被用

它解决什么问题

一次一密有多安全?「很难破」不够精确。这里要说清楚它为什么连暴力破解都不起作用,以及这么强的东西为什么日常通信里几乎见不到。

直觉

回到暴力破解的三个条件:算法已知、钥匙少、明文认得出。一次一密的钥匙和明文一样多,第二条没了。更要命的是第三条也没了:试出来的「明文」个个都通顺,你认不出哪句是真的。

代价落在钥匙上。钥匙和明文一样长、每次换新、还得安全送到对方手里,对称加密送钥匙的难题被放大到了极致。

一步一步看

目标:拿同一段密文换两把密钥去解,看出两句都通顺时,攻击者无从判断哪句是真明文。

  1. 截获一段密文 ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS。

  2. 攻击者拿一把等长密钥去解,得到 mr mustard with the candlestick in the hall。

  3. 再换一把等长密钥去解,得到 miss scarlet with the knife in the library。

  4. 两句都通顺,都像真的。只要密钥够随机,任意一句等长的话都能用某把密钥「解」出来。

    同一段密文 ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS 用两把不同的等长密钥解开,一次得到 mr mustard with the candlestick in the hall,另一次得到 miss scarlet with the knife in the library,两句都通顺,攻击者无法判断哪句是真的
    图片来源:COMP5521 Lecture 3 Cryptography, p.14
  5. 结论:试遍所有钥匙也挑不出真明文。暴力破解的第三个条件失效。

    暴力破解的条件 凯撒密码 一次一密
    算法已知 成立 成立
    密钥空间小 成立,只有 25 把 不成立,和明文一样多
    明文认得出来 成立,只有一行通顺 不成立,很多行都通顺

怎么判断

判断一种加密是否完美保密,问一句:攻击者看到密文以前和以后,对「明文是哪句」的判断有没有变化?

意思是:没看到密文时,明文可能是任何一句等长的话;看到密文后,仍然可能是任何一句等长的话,可能性一点没缩小。一次一密满足这一条,凯撒密码不满足(看到密文后只剩 25 种可能)。

再判断它实不实用,看课件给的两个困难:

  1. 要生成大量真正随机的密钥,消息有多长,钥匙就要多长;
  2. 这些钥匙要事先安全送到对方手里并保管好,每条消息一把。

所以它只在通信量小、安全要求极高的场合才用得上。

常见误解

以为同一把一次一密的钥匙用两次问题不大

问题很大。C₁ = P₁ ⊕ K,C₂ = P₂ ⊕ K,两式异或得 C₁ ⊕ C₂ = P₁ ⊕ P₂,钥匙被完全抵消。剩下的是两段自然语言的异或,可以用语言规律拆开。苏联重复使用钥匙本,被美方的 Venona 项目利用,就是这么回事(补充,出处同上 One-time pad 条目)。

以为一次一密只是理论玩具

它真的能实现完美保密,Shannon 给出了证明。少用是因为钥匙太贵,不是因为它不安全。

试一下

同一把钥匙加密了两条消息,密文分别是 1100 和 1010。不知道钥匙,能算出两条明文的异或吗?

能。1100 ⊕ 1010 = 0110,这就是两条明文的异或,钥匙被抵消了。

把它们串起来

一次一密靠的是 XOR。三种逐位运算里只有 XOR 每一位都能倒推,而且同一把钥匙异或两次就回到原样,加密和解密是同一个动作。

它把凯撒密码的一个位移换成一串独立随机的位移,钥匙和明文一样长。于是暴力破解的第二、第三个条件同时失效:钥匙多到试不完,试出来的话又个个通顺。这就是完美保密。

代价全压在钥匙上:随机钥匙难生成,和消息一样长的钥匙难送达、难保管,而且绝不能重用。对称加密送钥匙的老问题,在这里被放大到了最大。

下一页换个思路:干脆不送钥匙。RSA 让人人都能拿公钥加密,只有主人能解。

课件里的坑

  • [XOR 的范围] p.13 问的是「二进制一次一密能否改用 AND 或 OR」,结论只说这三个候选里 XOR 可逆,不要推广成「加密只能用 XOR」(p.13)
  • [完美保密的前提] 课件把一次一密写成 unbreakable;成立的前提是钥匙独立随机、等长、只用一次,少一条就不成立(p.10–11)
  • [两个困难] 课件列出的两个实际困难是生成大量随机密钥、分发与保护这些密钥,考试问「为什么少用」要两条都答(p.15)
  • [例子来源] p.14 那段密文出自教材的 Cluedo 例子,两句话是两把不同密钥分别解出的,题目问的是这说明了什么性质(p.14)

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写 AND、OR、XOR 三张真值表;再把例 1 那组二进制自己异或一遍并解回去;最后说出一次一密钥匙的三条要求和两个实际困难。

必背

  1. 在 XOR、AND、OR 三种逐位运算中选 XOR,已知密钥可逆;AND、OR 不能保证可逆;11011011 ⊕ 01101001 = 10110010
  2. XOR 的规则:相同得 0、不同得 1;(x ⊕ k) ⊕ k = x,所以用同一把密钥再异或一次就解密
  3. 一次一密的密钥要独立均匀随机、至少与明文等长、用一次就扔,可实现完美保密
  4. 完美保密:看到密文,对明文的判断没有任何更新;同一段密文配不同等长密钥能解出任意一句等长的通顺话
  5. 一次一密很少真的使用:大量随机密钥难生成,和明文一样长的密钥难分发与保管

课件例题

例 5(课件 p.12):二进制一次一密加密

题面:明文 11011011,密钥 01101001,按位异或求密文。怎么解密?

提示

上下对齐写两行,逐位比较:相同写 0,不同写 1。

解答
明文  1 1 0 1 1 0 1 1
密钥  0 1 1 0 1 0 0 1
密文  1 0 1 1 0 0 1 0

密文 10110010。解密用同一把密钥再异或一次,因为 (x ⊕ k) ⊕ k = x。

例 6(课件 p.13):能不能用 AND 或 OR 代替 XOR

题面:课件列出 AND、OR、XOR 三张真值表,问二进制一次一密能否改用 AND 或 OR。

提示

对每张表问:固定密钥位以后,两个不同的明文位会不会得到同一个结果?

解答

不能,看可逆性。AND:密钥位为 0 时结果恒为 0,原来那一位丢了。OR:密钥位为 1 时结果恒为 1,同样丢了。XOR:已知结果和密钥,总能唯一推回原位。答题写「XOR 可逆,另外两个会丢信息」即可。

例 7(课件 p.14):同一段密文解出两句话说明了什么

题面:密文 ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS。一把密钥解出 mr mustard with the candlestick in the hall,另一把等长密钥解出 miss scarlet with the knife in the library。这说明一次一密有什么性质?

提示

想想暴力破解的三个条件里,哪一条在这里不成立了。

解答

攻击者把所有密钥都试一遍,会得到很多句通顺的明文,却没有依据挑出真的那句。暴力枚举的第三个条件「明文认得出来」在这里失效。这就是完美保密的直观含义:看到密文,对明文的判断没有任何更新。

完整例题

题面(改编自课件 p.12–14):Alice 用一次一密给 Bob 发了两条 8 位消息,偷懒用了同一把钥匙 K = 10100110。两条明文是 P₁ = 01001000、P₂ = 01101001。(a) 求两段密文 C₁、C₂;(b) 攻击者不知道 K,只拿到 C₁、C₂,他能算出什么;(c) 说明这违反了哪一条要求。

约定:逐位异或,相同得 0、不同得 1。

解法:

  1. C₁ = P₁ ⊕ K:01001000 ⊕ 10100110 = 11101110。
  2. C₂ = P₂ ⊕ K:01101001 ⊕ 10100110 = 11001111。
  3. 攻击者算 C₁ ⊕ C₂:11101110 ⊕ 11001111 = 00100001。
  4. 再看 P₁ ⊕ P₂:01001000 ⊕ 01101001 = 00100001,和第 3 步完全一样。钥匙被抵消了。
  5. 攻击者拿到了两条明文的异或。只要猜中其中一条的一部分,另一条对应部分立刻出来,再反推出那一段 K。
  6. (c) 违反的是「只用一次」。

要点:C₁ ⊕ C₂ = (P₁ ⊕ K) ⊕ (P₂ ⊕ K) = P₁ ⊕ P₂,同一把钥匙用两次,完美保密立刻没了。

答题格式:先写两次加密的竖式,再写 C₁ ⊕ C₂ 的竖式,点出它等于 P₁ ⊕ P₂,最后一句点名违反的要求。

变式题(先自己做)

(1) 改编自课件 p.12:明文 10011100,密钥 11110000,求密文,并解密验算。 (2) 改编自课件 p.13:明文位未知,密钥位是 1,用 OR 运算得到结果 1。明文位可能是几?换成 XOR 呢? (3) 改编自课件 p.14:密文 0110,攻击者想让它「解」出明文 1111,需要哪把钥匙?想让它解出 0000 呢?这说明什么?

提示

(1) 逐位比较。(2) 把明文位 0 和 1 都代进去试。(3) 钥匙 = 密文 ⊕ 想要的明文。

判分点与答案(非官方评分标准)

判分点:① (1) 加密和解密两个竖式都要写;② (2) 两种运算分开答,说出能不能唯一确定;③ (3) 两把钥匙都给出,并点明「任何等长明文都对得上」。

(1) 10011100 ⊕ 11110000 = 01101100。解密 01101100 ⊕ 11110000 = 10011100 ✓。

(2) OR:0 OR 1 = 1,1 OR 1 = 1,明文位是 0 或 1 都可能,推不回。XOR:x ⊕ 1 = 1 只有 x = 0,唯一确定。

(3) 解出 1111 要钥匙 0110 ⊕ 1111 = 1001;解出 0000 要钥匙 0110 ⊕ 0000 = 0110。任何等长明文都能配出一把钥匙,所以光看密文无法判断明文,这就是完美保密。

闪卡自测

1. XOR 的规则是什么?为什么同一把钥匙能加密也能解密?

相同得 0、不同得 1。(x ⊕ k) ⊕ k = x,异或两次等于没异或(p.12)。

2. 为什么一次一密不用 AND 或 OR?

AND 在密钥位为 0 时结果恒为 0,OR 在密钥位为 1 时结果恒为 1,都会丢掉明文那一位,解不回来;XOR 已知密钥总能倒推(p.13)。

3. 11011011 ⊕ 01101001 等于多少?

10110010(p.12)。

4. 一次一密的钥匙要满足哪三条?

随机、至少和明文一样长、只用一次(p.10–11)。

5. 同一段密文解出两句通顺的话,说明什么?

试遍所有钥匙也挑不出真明文,暴力破解的「明文认得出来」失效,这就是完美保密(p.14)。

6. 一次一密为什么很少用?

两个实际困难:要生成大量真正随机的钥匙;和消息一样长的钥匙要安全分发和保管(p.15)。

下一讲

对称加密不管多强,钥匙总得先送到。下一页的 RSA 让人人都能用公钥加密、只有主人能用私钥解开,送钥匙这一步直接取消,见 L03a-3。

下一讲 →
L03a-3 L03a-3 RSA:谁都能锁、只有你能开

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。