L03a 对称加密与凯撒密码:一把钥匙锁两头
从零讲对称密码模型和它送钥匙的难题,补上字母编号与 mod 26,再把凯撒密码的加密、解密和暴力破解一步步走一遍。
一句话版
对称加密是收发双方共用同一把密钥的加密方式。凯撒密码是最古老的一种:每个字母往后挪固定几位。它告诉我们两件事:钥匙得先安全送到对方手里,钥匙的种类太少就会被逐个试穿。
上一讲造好了模运算这些零件,这一讲开始用它们搭真正的密码。这一页从零讲对称加密和凯撒密码。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 明文 / 密文 | plaintext / ciphertext | 加密前能读懂的原话 / 加密后的乱码 |
| 密钥 | key | 决定怎么加密的那个秘密参数 |
| 对称加密 | symmetric encryption | 加密和解密用同一把密钥 |
| 凯撒密码 | Caesar cipher | 每个字母往后挪固定几位 |
| mod 26 | 读「模 26」 | 除以 26 取余数,超过 z 就绕回 a |
| 暴力破解 | brute-force attack | 把所有可能的密钥一个个试过去 |
一个类比:一把普通挂锁,配两把一样的钥匙
你和朋友要传一只上锁的箱子。锁是普通挂锁,配两把一模一样的钥匙,你俩各拿一把。箱子在路上被谁截到都打不开,只有你俩能开。
这套办法安全要两个前提。第一,锁本身够结实,撬不开。第二,钥匙只在你俩手里。
麻烦出在第二条。两把钥匙得先见一面才能分到手。你要是能安全地把钥匙送过去,为什么不直接把信送过去?对称加密自己解决不了这件事,只能假设有一条安全通道。
凯撒密码像一把只有 25 个刻度的密码锁。一个个拨过去,最多拨 25 次一定打开。
类比在哪里失效:
- 挂锁撬没撬过能看出痕迹。密文被人看过,你完全不知道。
- 密码锁拨对了会「咔哒」一声。凯撒密码试对了也没有提示,要靠攻击者自己认出「这句是通顺的英文」,这正是暴力破解的第三个条件。
从零讲起
1. 对称密码模型
它解决什么问题
两个人隔着一条会被偷听的线路说话,想让偷听的人看不懂。对称密码模型把这件事拆成几个固定角色:谁出明文、谁加密、线路上跑什么、攻击者看得到什么、钥匙从哪来。角色说清楚了,才能讨论「安全」指的是什么。
从哪来(补充)
「算法可以公开,只有钥匙保密」这条原则有名字,叫 Kerckhoffs 原则。荷兰密码学家 Auguste Kerckhoffs 在 1883 年的军事科学杂志上提出:除了密钥以外,系统的一切都被敌人知道,系统也应当安全。
课件要求「加密算法要够强,攻击者知道算法也解不开」,说的就是这条。
出处:Wikipedia: Kerckhoffs’s principle
直觉
整套模型里真正保密的只有一样东西:密钥 K。算法 E 和 D 写在教科书里,密文 Y 在公开线路上跑,攻击者都看得到。
所以安全全压在 K 上。K 要事先送到接收方手里,而且送的路上不能被人看到。
一步一步看
目标:跟着明文从发送方走到接收方,看出算法和密文可以公开,那把 K 必须另走安全通道。
-
发送方手里有明文 X,比如一句话。
-
发送方把 X 和密钥 K 一起交给加密算法 E,得到密文 Y = E(K, X)。
-
Y 走公开线路。攻击者在线路上能看到 Y。
-
接收方把 Y 和同一把 K 交给解密算法 D,拿回 X = D(K, Y)。
-
那把 K 怎么到接收方手里的?从密钥源单独走一条安全通道(Secure Channel)。
怎么算
两条式子:Y = E(K, X),X = D(K, Y)。
意思是:加密是一个把「钥匙 + 原话」变成「乱码」的函数;解密把「同一把钥匙 + 乱码」变回原话。两条式子里的 K 是同一个,这就是「对称」两个字的来源。
攻击者手里有 Y,也知道 E 和 D 长什么样。他的目标有两个层次:猜出这一条的 X,或者干脆猜出 K。猜出 K 更糟,以后所有用这把 K 加密的消息都能读。
安全的两个前提由此而来:算法够强,光看 Y 推不出 X 和 K;K 事先在双方之间安全共享。第二条要靠模型之外的东西来保证。
常见误解
以为算法保密才安全
按 Kerckhoffs 原则,要假设攻击者知道算法。靠「算法没人知道」撑着的系统,算法一泄露就全完了,而且换算法比换钥匙难得多。
以为 Secure Channel 是模型解决掉的问题
模型只是把它画成一根线,假设它存在。现实里它是见面、快递员、外交邮袋,每一种都慢、贵、难扩展。这正是对称加密的死结,后面的公钥密码和 DH 就是为了绕开它。
试一下
模型里有 X、Y、K、E、D 五样东西。攻击者能拿到哪几样?
能拿到 Y(线路上公开跑),也知道 E 和 D(算法公开)。拿不到 X 和 K,这两样正是他想猜的。
2. 先补一块:字母编号与 mod 26(补充)
它解决什么问题
凯撒密码要「把字母往后挪 3 位」。字母不能直接做加法,得先换成数字。挪到 z 后面还要绕回 a,这需要一种「转圈的加法」。mod 26 就是这种加法。
直觉
把 26 个字母排成一圈,像钟面。a 是 0,b 是 1,一直到 z 是 25。往后挪就是顺时针走几格。走过 z 不会掉出去,而是接着回到 a。
钟面上过了 12 点又从 1 开始,是同一个道理,只是这里一圈有 26 格。
一步一步看
目标:用 t、x、b 三个字母分别挪位,看出越界和负数都靠 mod 26 绕回圈上。
-
给字母编号:a = 0,b = 1,c = 2,……,t = 19,w = 22,x = 23,z = 25。
-
普通加法:t 往后挪 3 位,19 + 3 = 22,对应 w,没越界。
-
越界的情况:x 往后挪 3 位,23 + 3 = 26。26 已经超出 0–25。
-
除以 26 取余数:26 mod 26 = 0,对应 a。就像在圈上走过 z 回到了起点。
-
往回挪也一样。b 往回挪 3 位:1 − 3 = −2,是负数。加一圈 26 折回来:−2 + 26 = 24,对应 y。
怎么算
a mod 26 = a 除以 26 的余数,结果总在 0 到 25 之间。
意思是:不管加多少、减多少,最后都把结果拉回到这一圈 26 个位置里。
结果是负数时,加 26,直到落进 0–25。例如 (1 − 3) mod 26:先算 1 − 3 = −2,再算 −2 + 26 = 24。
常见误解
以为负数取模就是把负号去掉
−2 mod 26 是 24,不是 2。在圈上往回走 2 格,从 a 往回是 z、y,落在 y(24)。去掉负号相当于往前走,方向反了。
试一下
w 往后挪 5 位是哪个字母?c 往回挪 4 位呢?
w = 22,22 + 5 = 27,27 mod 26 = 1,是 b。c = 2,2 − 4 = −2,−2 + 26 = 24,是 y。
3. 凯撒密码
它解决什么问题
最简单的保密写法:两个人约好一个数 k,写信时每个字母往后挪 k 位,读信时往回挪 k 位。不知道 k 的人看到的是一串乱字母。这里的 k 就是密钥。
从哪来(补充)
名字来自 Julius Caesar。罗马史学家 Suetonius 记载,凯撒写机密信件时把每个字母换成字母表里往后第 3 个字母,和课件开头例子的位移一样。
直觉
把字母表写两行,下一行比上一行错开 k 格。加密时在上一行找明文字母,抄下正下方那个;解密反过来,在下一行找,抄正上方那个。
整套密码只有一个秘密:错开了几格。
一步一步看
目标:用 k = 3 把一句话加密再解密,看出凯撒密码只是让每个字母统一挪同样的位数。
-
约好 k = 3。
-
写两行字母表,下行比上行往后错 3 格:a 对 D,b 对 E,……,w 对 Z,x 对 A,y 对 B,z 对 C。
-
加密 meet:m→P,e→H,e→H,t→W,得到 PHHW。
-
整句 meet me after the toga party 变成 PHHW PH DIWHU WKH WRJD SDUWB。空格保留,只换字母。
-
解密时每个字母往回挪 3 位:P 编号 15,15 − 3 = 12,是 m。
怎么算
把 a 到 z 编号 0 到 25,三条公式:
- 位移 3 的加密:C = E(3, p) = (p + 3) mod 26
- 一般位移 k 的加密:C = E(k, p) = (p + k) mod 26
- 解密:p = D(k, C) = (C − k) mod 26
意思是:加密是在字母圈上顺时针走 k 格,解密是逆时针走 k 格,mod 26 负责绕圈。
k 能取 1 到 25。k 等于 0 等于没加密;k 等于 26 走了整整一圈,又回到原地。所以有用的密钥一共 25 个。
常见误解
以为凯撒密码的 k 就是 3
3 只是凯撒当年用的位移。课件后面电影里那段密文用的是 4。考试问「凯撒密码」时,k 是未知数,要自己判断。
以为明文小写、密文大写是规则的一部分
这只是教材的排版习惯,方便一眼分清哪边是明文、哪边是密文。大小写不影响加解密。
试一下
k = 3 时,hello 加密成什么?
h→K,e→H,l→O,l→O,o→R,得到 KHOOR。验一个:o = 14,14 + 3 = 17,是 r。
4. 暴力破解:把 25 把钥匙都试一遍
它解决什么问题
攻击者截到一段凯撒密文,不知道 k。问题是:他能不能不靠任何巧劲,硬把明文找出来?能,而且很快。这一节说清楚为什么能,以及「能暴力破解」需要哪几个条件同时成立。
直觉
凯撒密码只有 25 种可能的 k。把每一种都拿来解一遍,就得到 25 行候选明文。其中只有一行是通顺的话,一眼就能挑出来。
钥匙太少,是凯撒密码致命的地方。
一步一步看
目标:把密钥从 1 往上逐个试解密文,看出只有 KEY = 3 读得通,25 把钥匙很快就能试完。
-
拿到密文 PHHW PH DIWHU WKH WRJD SDUWB,只知道它是凯撒密码。
-
设 KEY = 1,每个字母往回挪 1 位,得到 oggv og chvgt vjg vqic rctva,读不通。
-
设 KEY = 2,得到 nffu nf bgufs uif uphb qbsuz,还是读不通。
-
设 KEY = 3,得到 meet me after the toga party,是通顺的英文。
-
为保险可以把 4 到 25 也试完,其余各行都读不通。答案是 KEY = 3。
怎么判断
一种密码能不能被暴力破解,看三个条件是否同时成立:
- 加密和解密算法已知;
- 要试的密钥只有很少几个;
- 明文的语言认得出来,试对了能看出来。
意思是:攻击者要知道怎么试,试得完,还得认得出哪次试对了。凯撒密码三条都满足:算法公开,密钥只有 25 个,明文是英文。
只要拿掉任何一条,暴力破解就不灵了。下一页的一次一密拿掉的是第二条和第三条。
常见误解
以为暴力破解一定要试完所有密钥
找到通顺的那行就可以停了,平均只要试一半左右。课件让你列满 25 行,是为了展示密钥空间就这么大。
以为密钥多就一定安全
密钥多只拿掉了第二个条件。如果明文结构太明显,还可能有比逐个试更快的办法,比如课件破译电影密文时,先盯最短的单词。
试一下
密文 KHOOR 用暴力破解,KEY = 1 和 KEY = 3 各得到什么?
KEY = 1:jgnnq,读不通。KEY = 3:hello,读通了,停。
把它们串起来
对称密码模型把保密通信拆成固定角色,并指出整套系统只有密钥 K 是秘密。由此得到两个前提:算法够强,钥匙安全送达。
凯撒密码是这个模型最简单的实例。它把字母编号,在 mod 26 的圈上挪 k 格,加密和解密用同一个 k,正好是「对称」。
它的弱点直接落在第一个前提上:钥匙只有 25 种,算法又公开,明文认得出,三个条件凑齐,暴力破解几十秒就做完。
第二个前提,钥匙怎么送,它一点没动。下一页的一次一密把钥匙空间撑到最大,换来完美保密;但它让送钥匙这件事变得更难。
课件里的坑
- [位移不同] p.6–8 的例子位移是 3,p.9 电影《模仿游戏》那句密文的位移是 4。别把 3 当成凯撒密码的固定值;猜 k 时先盯最短的单词(p.8–9)
- [k 的范围] 公式里 k 取 1 到 25;k = 0 和 k = 26 都等于没加密(p.8)
- [负数取模] 解密公式 (C − k) mod 26 会出现负数,要加 26 折回;课件公式没单独提醒这一步(p.8)
- [Secure Channel] p.5 模型图里那条安全通道是假设,不是对称加密自己提供的功能;本讲后半段的公钥密码与 DH 都在回答它(p.4–5)
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写对称模型的两条式子和凯撒的三条公式;再把下面例 3 和例 4 不看解答做一遍;最后回查暴力破解的三个条件,能不能一口气说出来。
必背
- 对称加密安全的两个前提:算法够强、密钥事先在收发双方之间安全共享;第二条是它自己解不掉的死结,密钥要走 Secure Channel
- 对称密码模型:Y = E(K, X),X = D(K, Y);攻击者看得到 Y、知道算法,目标是猜出 X 或 K
- 凯撒密码三条公式:C = E(3, p) = (p + 3) mod 26;C = E(k, p) = (p + k) mod 26;p = D(k, C) = (C − k) mod 26
- 凯撒密码的 k 只能取 1 到 25,减法取模出负数要加 26 折回,例如 (1 − 3) mod 26 = 24
- 暴力枚举可行的三个条件:算法已知、密钥空间小(凯撒只有 25 种)、明文认得出来
课件例题
例 1(课件 p.6):用凯撒密码加密一句话
题面:凯撒密码把每个字母换成它后面第 3 个字母,z 之后绕回 a。加密明文 meet me after the toga party。
提示
对着两行错开 3 格的字母表逐个抄,空格照留。
解答
逐个字母后移 3 位:m→P,e→H,t→W,a→D,f→I,r→U。密文是 PHHW PH DIWHU WKH WRJD SDUWB。验一个:t 编号 19,19 + 3 = 22,对应 W。
例 2(课件 p.7):暴力破解上面那段凯撒密文
题面:只拿到密文 PHHW PH DIWHU WKH WRJD SDUWB,知道用的是凯撒密码。要试多少个密钥?怎么判断哪个对?
提示
数一数凯撒密码一共有几个有用的 k,再想想试对的那一行长什么样。
解答
把 KEY 从 1 到 25 逐个回退,一共 25 行。只有 KEY = 3 那行是可读英文 meet me after the toga party。能这样破,靠三个条件:算法已知、密钥只有 25 个、明文语言认得出来。
例 3(课件 p.8):填出凯撒密码的三条公式
题面:字母编号 a = 0 到 z = 25。填空:C = E(3, p) = _;C = E(k, p) = _;p = D(k, C) = _。k 能取哪些值?
提示
加密是往后挪,解密是往回挪,两头都要绕圈。
解答
依次是 (p + 3) mod 26、(p + k) mod 26、(C − k) mod 26。k 取 1 到 25:k = 0 等于没加密,k = 26 又绕回原位。
减法取模可能出负数,要折回正数。例如 C = 1(字母 B)、k = 3,(1 − 3) mod 26 = 24,对应 y。
例 4(课件 p.9):破译电影里的一段凯撒密文
题面:电影《模仿游戏》里有一段凯撒密文 WII CSY MR XAS PSRK AIIOW HIEVIWX JVMIRH,位移量未知。解出明文,并说明怎么定位移。
提示
先别硬试 k = 3。盯住两个字母的那个词 MR,英文里常见的两字母词就那么几个。
解答
先用 k = 3 试,得到 TFF ZPV JO UXP…,不成词。改盯最短的词 MR:英文常见两字母词有 in、to、of、is。M 退 4 位是 I,R 退 4 位是 N,所以 k = 4。
全句回退 4 位:SEE YOU IN TWO LONG WEEKS DEAREST FRIEND。验一个:W 编号 22,22 − 4 = 18,对应 S。
完整例题
题面:截获凯撒密文 DWWDFN DW GDZQ(改编自课件 p.6–9 的方法)。(a) 用暴力破解的思路写出前几把 KEY 的回退结果,找出明文;(b) 写出对应的加密公式;(c) 说明这次破解用到了哪三个条件。
约定:字母编号 a = 0 到 z = 25;解密公式 p = (C − k) mod 26。
解法:
- 先看结构:DWWDFN 有六个字母,第 2、3 个相同;DW 是两字母词。
- KEY = 1:cvvcem cv fcyp,读不通。
- KEY = 2:buubdl bu ebxo,读不通。
- KEY = 3:attack at dawn,读通了。验一个:D 编号 3,3 − 3 = 0,是 a;Z 编号 25,25 − 3 = 22,是 w。
- (b) 加密公式 C = E(3, p) = (p + 3) mod 26。验 w:22 + 3 = 25,是 Z,和密文对上。
- (c) 三个条件:算法已知(凯撒密码);密钥空间小(25 个);明文认得出(英文 attack at dawn)。
要点:两字母词 DW 是最好的突破口,DW 退 3 位是 at。从最短的词入手常常比按顺序硬试快。
答题格式:先写编号约定和解密公式,再列出试过的 KEY 和结果,在读通的那一行停下并验算一个字母,最后点名三个条件。
变式题(先自己做)
(1) 改编自课件 p.6:k = 7,加密 secret。 (2) 改编自课件 p.8:C 是字母 c(编号 2),k = 5,算 p = D(k, C),写出取模的每一步。 (3) 自编情境:一种「加强版凯撒」用两个字母一组的密钥,奇数位挪 k₁ 格、偶数位挪 k₂ 格,k₁ 和 k₂ 各取 1 到 25。暴力破解最多要试几把钥匙?三个条件里哪一条被削弱了?
提示
(1) 注意 s、t 往后挪 7 位要绕圈。(2) 先减,出了负数再加 26。(3) 两把钥匙各自独立取值,种数相乘。
判分点与答案(非官方评分标准)
判分点:① (1) 绕圈的字母要写对;② (2) 必须写出负数再折回的过程;③ (3) 要给出数字并点名是哪个条件。
(1) s = 18,18 + 7 = 25 → Z;e = 4 → 11 → L;c = 2 → 9 → J;r = 17 → 24 → Y;e → L;t = 19,19 + 7 = 26,26 mod 26 = 0 → A。密文 ZLJYLA。
(2) 2 − 5 = −3,−3 + 26 = 23,p 是 x。验算:x 往后挪 5 位,23 + 5 = 28,28 mod 26 = 2,是 c。
(3) 25 × 25 = 625 把。被削弱的是第二个条件「密钥空间小」,但 625 把仍然很快试完,算法已知、明文认得出两条照旧成立,所以仍可暴力破解。
闪卡自测
1. 对称加密安全的两个前提是什么?哪一条它自己解决不了?
算法够强;密钥事先在双方之间安全共享。第二条要靠模型外的安全通道,它自己解决不了(p.4–5)。
2. 对称模型里攻击者能看到什么、想得到什么?
能看到密文 Y,知道算法 E 和 D。想猜出明文 X,或者更进一步猜出密钥 K(p.3–4)。
3. 凯撒密码的加密和解密公式各是什么?
C = (p + k) mod 26,p = (C − k) mod 26,字母按 a = 0 到 z = 25 编号(p.8)。
4. 凯撒密码一共有几把有用的密钥?为什么不是 26 把?
25 把,k 取 1 到 25。k = 0 等于没加密,k = 26 走一整圈回到原位(p.7–8)。
5. (1 − 3) mod 26 等于多少?
24。1 − 3 = −2,再加 26 折回到 0–25 之间(p.8)。
6. 暴力破解要同时满足哪三个条件?
算法已知、密钥空间小、明文认得出来(p.7)。
7. 破译电影里那段凯撒密文时,怎么最快定出位移?
盯最短的单词 MR。英文两字母词常见的是 in、to、of、is,M 对 I、R 对 N,位移是 4(p.9)。
下一讲
凯撒密码的钥匙太少,一试就穿。下一页把钥匙撑到和明文一样长、每个位置单独随机:一次一密。它用 XOR 逐位加密,能做到完美保密,见 L03a-2。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。