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 能从结果和密钥倒推回明文。
-
列 AND 的真值表:0 AND 0 = 0,0 AND 1 = 0,1 AND 0 = 0,1 AND 1 = 1。
-
看密钥位是 0 的两行:不管明文位是 0 还是 1,结果都是 0。拿到结果 0,推不回明文。
-
列 OR 的真值表:0 OR 0 = 0,0 OR 1 = 1,1 OR 0 = 1,1 OR 1 = 1。密钥位是 1 时结果恒为 1,同样推不回。
-
列 XOR 的真值表:0 ⊕ 0 = 0,0 ⊕ 1 = 1,1 ⊕ 0 = 1,1 ⊕ 1 = 0。密钥位是 0 时结果等于明文位,密钥位是 1 时结果是明文位翻转。两种情况都能倒推。
-
结论:三个候选里只有 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 年公开发表。
直觉
把凯撒密码里那一个 k,换成一串 k₁、k₂、k₃……,每个字母各用一个,而且每个都是独立掷出来的随机数。
到了二进制世界,「每个字母挪几格」变成「每一位异或一个随机位」,做法完全一样。
一步一步看
目标:用 attack 和一串二进制各加密一次,看出随机位移怎样打乱凯撒的规律,同一把密钥再异或就能还原。
-
字母版:明文 attack,掷出六个随机位移 17、4、22、9、11、13。
-
逐个挪:a 挪 17 得 R,t 挪 4 得 X,t 挪 22 得 P,a 挪 9 得 J,c 挪 11 得 N,k 挪 13 得 X。密文 RXPJNX。
-
对比凯撒:同样的 attack,凯撒全用 3,得到 DWWDFN。两个 t 都变成 W,两个 a 都变成 D,规律露在外面;一次一密里两个 t 变成了 X 和 P。
-
二进制版:明文 11011011,密钥 01101001,逐位异或得密文 10110010。
-
解密:密文 10110010 再和同一把密钥 01101001 异或,得到 11011011,回到明文。
怎么算
二进制一次一密:密文 = 明文 ⊕ 密钥,明文 = 密文 ⊕ 密钥。
意思是:每一位明文和对应位置的那一位密钥做 XOR。因为 (x ⊕ k) ⊕ k = x,解密就是拿同一把密钥再做一次。
密钥有三条硬要求:
- 随机,每一位独立、0 和 1 机会均等;
- 至少和明文一样长,每一位明文都有自己的一位密钥;
- 只用一次,用完就扔。
三条少一条,完美保密就不成立。
常见误解
以为密钥比明文短一点、循环着用也差不多
一循环就有两段明文用了同一段钥匙,等于用了两次,攻击者可以把两段密文异或,钥匙被抵消掉,剩下两段明文的异或,再用语言规律去拆。第 3 个概念会细讲。
试一下
明文 1001,密钥 0111,密文是什么?用同一把密钥解回来验算一次。
1001 ⊕ 0111 = 1110。1110 ⊕ 0111 = 1001,回到了明文。
3. 完美保密,以及它为什么很少真的被用
它解决什么问题
一次一密有多安全?「很难破」不够精确。这里要说清楚它为什么连暴力破解都不起作用,以及这么强的东西为什么日常通信里几乎见不到。
直觉
回到暴力破解的三个条件:算法已知、钥匙少、明文认得出。一次一密的钥匙和明文一样多,第二条没了。更要命的是第三条也没了:试出来的「明文」个个都通顺,你认不出哪句是真的。
代价落在钥匙上。钥匙和明文一样长、每次换新、还得安全送到对方手里,对称加密送钥匙的难题被放大到了极致。
一步一步看
目标:拿同一段密文换两把密钥去解,看出两句都通顺时,攻击者无从判断哪句是真明文。
-
截获一段密文 ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS。
-
攻击者拿一把等长密钥去解,得到 mr mustard with the candlestick in the hall。
-
再换一把等长密钥去解,得到 miss scarlet with the knife in the library。
-
两句都通顺,都像真的。只要密钥够随机,任意一句等长的话都能用某把密钥「解」出来。
图片来源:COMP5521 Lecture 3 Cryptography, p.14 -
结论:试遍所有钥匙也挑不出真明文。暴力破解的第三个条件失效。
暴力破解的条件 凯撒密码 一次一密 算法已知 成立 成立 密钥空间小 成立,只有 25 把 不成立,和明文一样多 明文认得出来 成立,只有一行通顺 不成立,很多行都通顺
怎么判断
判断一种加密是否完美保密,问一句:攻击者看到密文以前和以后,对「明文是哪句」的判断有没有变化?
意思是:没看到密文时,明文可能是任何一句等长的话;看到密文后,仍然可能是任何一句等长的话,可能性一点没缩小。一次一密满足这一条,凯撒密码不满足(看到密文后只剩 25 种可能)。
再判断它实不实用,看课件给的两个困难:
- 要生成大量真正随机的密钥,消息有多长,钥匙就要多长;
- 这些钥匙要事先安全送到对方手里并保管好,每条消息一把。
所以它只在通信量小、安全要求极高的场合才用得上。
常见误解
以为同一把一次一密的钥匙用两次问题不大
问题很大。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 那组二进制自己异或一遍并解回去;最后说出一次一密钥匙的三条要求和两个实际困难。
必背
- 在 XOR、AND、OR 三种逐位运算中选 XOR,已知密钥可逆;AND、OR 不能保证可逆;11011011 ⊕ 01101001 = 10110010
- XOR 的规则:相同得 0、不同得 1;(x ⊕ k) ⊕ k = x,所以用同一把密钥再异或一次就解密
- 一次一密的密钥要独立均匀随机、至少与明文等长、用一次就扔,可实现完美保密
- 完美保密:看到密文,对明文的判断没有任何更新;同一段密文配不同等长密钥能解出任意一句等长的通顺话
- 一次一密很少真的使用:大量随机密钥难生成,和明文一样长的密钥难分发与保管
课件例题
例 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。
解法:
- C₁ = P₁ ⊕ K:01001000 ⊕ 10100110 = 11101110。
- C₂ = P₂ ⊕ K:01101001 ⊕ 10100110 = 11001111。
- 攻击者算 C₁ ⊕ C₂:11101110 ⊕ 11001111 = 00100001。
- 再看 P₁ ⊕ P₂:01001000 ⊕ 01101001 = 00100001,和第 3 步完全一样。钥匙被抵消了。
- 攻击者拿到了两条明文的异或。只要猜中其中一条的一部分,另一条对应部分立刻出来,再反推出那一段 K。
- (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。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。