《密码学及应用》零基础学习手册

假设 5 个人（A、B、C、D、E）要两两保密通信。

每对人需要一个共享密钥：A-B、A-C、A-D、A-E、B-C、B-D、B-E、C-D、C-E、D-E。

数一数：10 个。公式是 n(n−1)/2 = 5×4/2 = 10。

如果是 100 个人呢？100×99/2 = 4950 个密钥。每个人要记 99 个密钥——这根本管不过来。

换成公钥密码：100 个人，每人只要管好自己的 1 个私钥。答案就是"密钥管理简单"。

判断方法只有一句：数一数密文和明文的字母，是不是同一批？

• 是同一批（字母没变，只是顺序乱了）→ 换位
• 不是同一批（字母被换过了）→ 代替

课件给的例子是 (24 + 3) = 27 % 26 = 1。拆开看：

1. 数字 24 对应字母 y
2. 24 + 3 = 27，超过 25 了
3. 27 % 26 = 1（因为 27 − 26 = 1）
4. 数字 1 对应字母 b

所以 y 加密后变成 b。用"绕回来"的说法验证：y 往后数 3 个 → z → a → b ✓

解密就反过来减：课件写 (1 − 3) = −2 % 26 = 24。

1. 密文 1 对应 b
2. 1 − 3 = −2，是负数
3. −2 % 26 = 24（因为 −2 + 26 = 24）
4. 数字 24 对应字母 y ✓ 还原了

假设 a = 2，加密规则 y = (2x + b) % 26。逐个数试一遍：

看出来了吗？x=0 和 x=13 加密后都是 0！

这意味着：收到密文 0，你分不清原文是 0 还是 13。信息丢了，救不回来。

根子在哪？因为 gcd(2, 26) = 2 ≠ 1，2 和 26 有公约数，所以"乘 2"这个操作不是一一对应的——多个输入挤到同一个输出去了。

26 个明文只产生了 13 种密文——一半的密文根本用不上。

a 有多少种选法？ 26 = 2 × 13，所以和 26 互素的数就是"不是 2 的倍数、也不是 13 的倍数"的数。

在 1~25 里数一数：

（就是除了 13 之外的奇数）共 12 个。

b 有多少种选法？ b 可以是 0~25 任意一个，共 26 个。

所以总共 12 × 26 = 312 种。但其中 a=1、b=0 这一组是"什么都不做"（y = x），等于没加密，要去掉。

密钥空间 = 12 × 26 − 1 = 311

加密式：y = (9x + 3) % 26

逐个算：

• m = 12，(9×12 + 3) = 111，111 % 26 = 7 → h（因为 26×4 = 104，111−104 = 7）

课件给的结果是 meet me at midnight → hnns hn ds hxeqxfos，第一个字母确实是 h ✓

课件说这个密钥的解密式是 x = (3y + 17) % 26。这两个数不是拍脑袋来的，而是：

解密密钥 = (a⁻¹, −a⁻¹·b)

第一步：求 a⁻¹ = 9⁻¹ % 26

用 Euclid 算法（详细方法见 1.4 节，这里先看结果）：

得到 3×9 − 1×26 = 1，所以 9⁻¹ = 3。验算：9×3 = 27 = 26+1 ≡ 1 ✓

第二步：算 −a⁻¹b = −(3×3) = −9

是负数，加 26 变正：−9 + 26 = 17

所以解密式是 x = (3y + 17) % 26。

验算：密文 h = 7，(3×7 + 17) = 38，38 % 26 = 12 → m ✓ 还原了

如果攻击者知道了两组对应关系，就能反推密钥。课件给的公式：

a = (x − y)⁻¹ · (E(x) − E(y)) % 26

b = (E(x) − a·x) % 26

思路其实很朴素：列两个方程，一相减，b 就被消掉了，只剩一个未知数 a。

然后求 a：两边乘 5⁻¹（不能"除以 5"，模运算没有除法）。这就是 1.4 节要练的手艺。

明文字母 cat，密钥 key（三个字母）。

密文：mer

看明白了吗：每个位置用的移位量都不一样（10、4、24），而不是统一的 3。

重点看那三个 e（位置 1、2、5）：

同一个 e，在不同位置变成了不同的字母！ 这就是"多表代替"——频率被摊平了。

核心观察：密文里如果有一段重复出现，那这两段之间的距离，很可能是密钥长度的倍数。

为什么？ 因为只有"距离是 m 的倍数"时，两处才"对齐"（用同一套密钥字母）。此时如果明文也相同，密文就相同。

用一个具体例子看。假设密钥 abc（m=3）：

看，位置 0、3、6 用的都是 a（相差 3，是 m 的倍数）。

现在明文 thecatthedog，里面 the 出现在位置 0 和位置 6：

攻击者看到密文里 tig 出现了两次，距离是 6。 于是他知道：m 一定是 6 的约数（2、3 或 6）。再找几处重复，取所有距离的公约数，就能锁定 m = 3。

Kasiski 靠"找具体片段"，Friedman 靠"看整体统计"。核心工具叫重合指数。

什么叫重合指数？ 就是一个概率问题：

从一段文字里随机抓两个字母，它们相同的概率是多少？

算法就是把 26 个字母各自的出现频率算出来，然后求"频率的平方和"。

如果 m 猜对了：每组内部用的是同一个密钥字母 → 每组相当于一个普通移位密码 → 而移位只是"整体平移"，不改变字母分布的形状 → 所以每组还是"英文字符流" → 指数 ≈ 0.067 ✓

如果 m 猜错了：每组里混了不同密钥字母 → 等于被搅乱了 → 分布被摊平 → 指数下降，趋近 0.038 ✗

结论：把不同的 m 都试一遍，哪个 m 让各组重合指数的平均值最接近 0.067，哪个就是正确答案。

明文 canyouunderstand（16 个字母）。

第 1 步：按 4 个字符一行排列

第 2 步：按列读出来

第 3 步：解密就反过来 —— 把密文按 4 个一列排回去，再按行读出，就还原了。

一句话记住：加密 = 按行填、按列读；解密 = 按列填、按行读。

课件还展示了一个带关键词的版本，用关键词 type 给每列贴标签：

按标签的字母顺序排：e < p < t < y

所以读列的顺序是：第4列(e) → 第3列(p) → 第1列(t) → 第2列(y)

这个关键词就是密钥。不知道 type 这个词，就不知道按什么顺序读列。

课件写的是：

f = (1 2 3 4 / 2 4 1 3)

这个写法要这样读——上排是原位置，下排是搬到哪：

逐列读：第 1 位的字符搬到第 2 位；第 2 位的搬到第 4 位；第 3 位的搬到第 1 位；第 4 位的搬到第 3 位。

就是一张"搬运指令表"。

现在看密文的四个位置：

四组都这样处理：cany|ouun|ders|tand → ncya|uonu|rdse|ntda

密文：NCYAUONURDSENTDA ✓ 和课件一致

课件给的解密矩阵：f⁻¹ = (1 2 3 4 / 3 1 4 2)

拿密文第一组 n c y a 试：

为什么能还原？ 课件写：f ∘ f⁻¹ = (1 2 3 4 / 1 2 3 4) —— 最后这个矩阵上下排一模一样，叫恒等置换：谁都待在原位、没动。所以"搬过去再搬回来"就复原了。

求 −200 模 98 的约简。

方法：不断加 98，直到落进 0~97 的范围。

验算：94 − (−200) = 294 = 3 × 98，差是 98 的整数倍 ✓

换个说法理解：把模 98 想成一个 98 格的转盘。从 −200 出发往正方向走，走三步（每次 +98）就上了转盘。

① 加法和乘法可以直接对每个数取模

(x + y) % m = ((x % m) + (y % m)) % m

所以你算 (24 + 3) % 26 的时候，不用管 27 有多大，直接算就完了。

② 想"约掉"一个因数，必须先验证它与模数互素

若 a·x ≡ a·y (mod m) 且 (a, m) = 1，则 x ≡ y (mod m)

这条特别重要。举个反例看看不注意会怎样：

问题在于 gcd(3, 6) = 3 ≠ 1，3 和模数 6 不互素，所以不能约。

算法分两步走，写在纸上是左右两列：

左列：辗转相除

右列：回代——从"1 = 8 − 1×7"这一行出发，一路往上代：

读答案：式子 3×100 + (−13)×23 = 1 里，23 的系数是 −13。

所以 23⁻¹ = −13。是负数，加 100 变正：−13 + 100 = 87。

验算：23 × 87 = 2001 = 20×100 + 1 ✓

左列：26 ÷ 5 = 5 余 1，一步就到 1！

右列：因为只除了一次，不用反复回代，直接把 1 整理成目标形式：

5 的系数是 −5，所以 5⁻¹ = −5 = 21（加 26 变正）。

验算：5 × 21 = 105 = 4×26 + 1 ✓

"逆元"的意思：找一个数，和它相加等于单位元（也就是 0）。

六个元素全都有逆元 ✓

每个箱子里的数，叫做一个剩余类（"剩余"就是"余数"的意思——按余数分出来的类）。

同一个箱子里的数，在模 6 下是"同一个东西"：0 ≡ 6 ≡ 12 ≡ −6 (mod 6)。

课件给了正式定义：模 m 的剩余类有 m 个（这里是 6 个）。

每个箱子里有无穷多个数，太啰嗦。那就每个箱子只挑一个代表。

比如都挑"最小的非负数"：

这就是一个"完全剩余系"。"完全"的意思是：6 个箱子全都有代表，一个都没落下。

换个挑法也行。比如都挑"最小的正数"：

这也是完全剩余系——只要"每个箱子恰好一个"，挑谁都行。

8 个箱子，编号 0~7，逐个查"和 8 互素吗"：

Z₈^* = {1, 3, 5, 7}，共 4 个。

发现了吗——1、3、5、7 正好是 1~8 里的奇数。因为 8 的因子只有 2，所以"不是偶数"就跟它互素。

φ(7) = ?（7 是素数）

1~7 里与 7 互素的：1,2,3,4,5,6 —— 全都可以，因为 7 是素数，1~6 里没有 7 的因子。

所以 φ(7) = 6 = 7 − 1 ✓

φ(8) = ?（8 = 2³）

1~8 里与 8 不互素的是偶数：2, 4, 6, 8，共 4 个。

所以 φ(8) = 8 − 4 = 4 ✓ 和上一节数出来的一致。

用公式验证：φ(2³) = (2−1) × 2³⁻¹ = 1 × 4 = 4 ✓

这条公式为什么长这样？把 8 − 4 改写一下：

就是"总数里减去一半（能被 p 整除的那些）"。

直接数？不可能。用三步走：

第一步：分解质因数　10000 = 2⁴ × 5⁴

第二步：每项单独套公式

第三步：乘起来

（课件写的是 8 × 4 × 125 = 4000，结果一样）

刚才转圈经过的数字是：2, 4, 8, 7, 5, 1

排个序：1, 2, 4, 5, 7, 8

而 Z₉^* = {1, 2, 4, 5, 7, 8}

一模一样！

为什么？因为 x = 2 与 9 互素，所以"每乘一次 2"结果还在 Z₉^* 里，永远不会跑到外面去。

（反例：如果取 x = 3，因为 gcd(3,9) = 3 ≠ 1，那么 3 × 3 = 9 ≡ 0，跑到 0 去了，出圈了，永远回不来。）

问题：算 3⁴⁵ mod 10。直接算？3⁴⁵ 是个 22 位数。

用欧拉定理：

一个 45 次方的题，变成了算 3¹。

而 φ(9) = 6。

看那一列阶：1, 6, 3, 6, 3, 2 —— 全都是 6 的约数！

(1|6 ✓, 2|6 ✓, 3|6 ✓, 6|6 ✓)

不用一个个试！ 课件给了判定定理：

设 φ(n) 的素因子是 q₁, q₂, …, q_k，则 g 是原根的充要条件是：

g^φ(n)/q_i ≢ 1 (mod n)，对每个 i 都成立

大白话：只要"半路没提前回到 1"，就是原根。

41 是素数，φ(41) = 40。把 40 分解：40 = 2³ × 5，素因子是 2 和 5。

所以只需要验两个指数：40/2 = 20 和 40/5 = 8。

算 3⁸ mod 41（逐步平方）：

糟糕，3⁸ ≡ 1！

按定理，只要有一个 g^φ(n)/q_i 等于 1，就不是原根。

结论：3 不是模 41 的原根。

（补充：因为 3⁴ ≡ −1 ≠ 1、3⁸ ≡ 1，所以 3 的阶正好是 8。而 8 | 40 ✓，符合"非原根的阶整除 φ(n)"。）

只做了 4 步（4 次乘法），而不是乘 5 次。

课件演示了算 3⁸⁰ mod 1000 和 3¹⁰⁰ mod 1000：

（每一步都取了模，所以数字都不大。）

看这个置换：g = (1 2 3 4 5 6 7 / 4 3 2 5 7 6 1)

逐个跟一下：1 → 4 → 5 → 7 → 1（绕回来了！）；2 → 3 → 2；6 → 6

所以它可以写成：g = (1 4 5 7)(2 3)(6)

这叫不相交循环分解 —— "不相交"指各个循环里的数字没有重复。

课件说：任何置换都能表示成不相交循环的乘积，而且不考虑次序时是唯一的。

思路：把 5 拆成几段，让各段长度的 lcm 最大。

答：S₅ 的最大阶是 6（形如 (1 2 3)(4 5)）。

为什么是 3+2 而不是别的？ 因为 3 和 2 互素，lcm(3,2) = 3×2 = 6，乘积没浪费。换成 4+1，lcm 只有 4。

S₁₀ 呢？ 同理试：最优是 5+3+2（正好用完 10 个数），lcm(5,3,2) = 30。

2n = 8，所以模数 = 2n+1 = 9。洗牌规则：f(x) = (2x) mod 9。

洗一次的结果：

跟踪 1 号的轨迹：1 → 2 → 4 → 8 → 7 → 5 → 1

咦，走到 5 就回 1 了！ 只串了 6 个位置（1,2,4,8,7,5），还剩 3 和 6 没串到。

再另起一头，从 3 开始：3 → 6 → 3（串了 2 个）

所以循环分解是 (1 2 4 8 7 5)(3 6)，长度分别是 6 和 2。

洗牌次数 = lcm(6, 2) = 6 次 ✓ 和课件一致。

2n = 12，模数 = 13。规则：f(x) = (2x) mod 13。

从 1 开始跟踪，一路走：

（中间用到的取模：16 mod 13 = 3；24 mod 13 = 11；22 mod 13 = 9；18 mod 13 = 5；20 mod 13 = 7；14 mod 13 = 1）

这一趟把 12 个位置全部串完了，所以只有一个循环：

(1 2 4 8 3 6 12 11 9 5 10 7)

洗牌次数 = 12。

课件说 IP 和 IP⁻¹ 的作用主要是"打乱输入的 ASCII 码字划分关系，并将明文校验码变成 IP 输出的一个字节"。

为什么要先打乱位置？ 因为要让原来相邻的位分散开，这样后面每一轮的影响才能扩散得更均匀。

把 64 位劈成左右两半 L 和 R，每轮这样操作：

L_i = R_i−1　　R_i = L_i−1 ⊕ f(R_i−1, k_i)

逐项看懂：

• 右边那半原封不动变成左边的（L_i = R_i−1）
• 新的右边 = 老的左边 异或 一个"用右边和子密钥算出来的东西"
• ⊕ 是按位异或，规则：1⊕0=1，0⊕1=1，0⊕0=0，1⊕1=0

这个结构叫 Feistel 结构，妙处在于：加密和解密用同一套操作，只是子密钥的顺序反过来。所以硬件实现很省事。

函数 f 里面最要紧的是一个S 盒（替换盒）：

每个 S 盒：输入 6 位，输出 4 位。

为什么 S 盒这么关键？ 因为其他步骤（置换、异或）都是线性的——线性的东西可以用数学方程解出来。而 S 盒是一张查表替换表，非线性的，让攻击者无法用解方程的办法攻破。

DES 的安全性，几乎全押在这 8 个 S 盒上。

AES 把 128 位明文排成 4×4 的字节矩阵（共 16 个字节），然后做四件事：

这四步重复 10~14 轮（最后一轮不做列混合）。

课件给的例子：字节 d4 = 二进制 11010100

从高到低对应 x⁷, x⁶, …, x⁰：

在这个"多项式世界"里，运算规则变了：

课件在旁边标了"15 mod 11"作类比——意思就是：就像十进制里"15 模 11 降下来"，这里是"9 次多项式模掉一个 8 次多项式，降回 8 次以下"。

这样既保证了结果还是一个字节（8 位），又保证了每个非零元素都有逆元（能做除法）。

意义：密钥相同，洗出来的牌序就相同（这符合"密钥独立于明文"）；密钥不同，就是两副完全不同的牌。

加密：明文 ⊕ 密钥流 → 密文；解密反过来再来一次异或。

速度优势就在这：初始化要几百次运算，但之后每个明文字节只需要一次异或（加解密完全对称）。

取 a=2, b=7, m=17，则 s_n+1 = (2s_n + 7) mod 17。取种子 s₀ = 1：

课件写的序列：1, 9, 8, 6, 2, 11, 12, 14, 1, 9, 8, 6, …

注意：只走了 7 步就回到 1，后面开始原封不动地重复。周期只有 7。

课件还列了 a=7, b=1，种子 s₀=14 的情况：

这一串走了 16 步才回到 1。

同样是模 17，为什么差别这么大？ 这就是"周期"要讲的内容。

求 s_n+1 = 7s_n + 2 (mod 13) 的坏种子。

a=7, b=2, p=13，代入公式：

先求 6⁻¹ mod 13（用 Euclid）：

所以 6⁻¹ = −2 = 11（加 13 变正）。

验算：把 s = 4 代进去，(7×4 + 2) = 30，30 mod 13 = 4 —— 果然算完还是 4，卡死了 ✓

4 位 LFSR，抽头第 1、4 位，即 b_n+1 = b_n + b_n−3（最左位和最右位异或）。初始值 1111。

把每一步挤出去的位收集起来：111101011001000… ✓ 和课件一致。

注意：输出序列是"从右端挤出去的那一位"，不是寄存器当前的内容。这两者容易混。

把抽头序列写成一个多项式。比如抽头第 1、4 位（抽头序列记为 (4,1,0)）：

（第 4 位给 x⁴，第 1 位给 x，最后那个"0"就是课件说的"加上常数 1"。）

"本原多项式"的含义和"本原根"是一回事——它能让寄存器跑满所有非零状态，一个不漏。

课件对比了两个抽头：

右边那个能被分解（不是不可约的，更谈不上本原），所以提前循环，周期短。

结论：同样 4 位寄存器，抽头选得对不对，周期天差地别。

课件还给了一组 32 位的：抽头序列 (32,7,5,3,2,1,0) 和 (32,7,6,2,0) 具有最大周期 2³²−1。

散列函数要求输入长度是 512 的整数倍。但消息长度任意，所以要"补齐"。

规则：在消息后填一串 1000…，使长度满足 |x| ≡ 448 mod 512，然后在后面再补 64 位表示原始长度。

课件举例：x = "abc"

为什么要补长度？ 防止"长度扩展攻击"——如果不记录原始长度，攻击者可能构造出另一条消息得到同样的摘要。

用法一：保密通信

用法二：数字签名

课件取 p=3, q=5。

公钥 (e, n) = (3, 15)，私钥 d = 3。（这个例子太小了，现实中 p、q 是几百位的大素数。）

加密消息 m = 7：

解密 c = 13：

x ≡ 2 (mod 3)，x ≡ 3 (mod 5)，x ≡ 2 (mod 7)

答：23（也就是"23 个"）

【密钥生成】和 RSA 加密一样：公钥 (e,n)，私钥 (d,p,q)

【签名】s = m^d mod n　　　←　用私钥
【验证】验证 s^e mod n 是否等于 m　　←　用公钥

对比一下 RSA 加密：

看出规律了吗——正好反过来。这就是为什么有人把签名叫"用私钥加密"。

前提：Alice 和 Bob 公开约定一个大素数 p 和一个原根 g。（注意：这两个数不需要保密，公开都行。）

课件给的小例子：p=7, g=2 → 3；p=7, g=3 → 6

用 Alice 自己的私钥 k_Av 签名，公钥 k_Ap 验证：

缺点：运算速度慢，效率低（因为要对整段消息做 RSA 运算）。

这就是课件里那个 sha256RSA 的含义——先用 SHA256 摘要，再用 RSA 签名。

为什么安全？ 因为散列函数有抗碰撞性：攻击者找不到另一条消息产生相同摘要，所以他改不了 m。

就是把"保密通信"和"数字签名"拧在一起：

特点：只有指定的授权人才能验证签名（因为只有他有对应的私钥解密）。

课件留了一道设计题："利用混合密码协议和哈希+公钥的数字签名协议优化带加密的数字签名协议。" 思路就是：把公钥运算换成"公钥协商 + 对称加密"，把直接签名换成"hash + 签名"。

目的：让签名"必须在线验证"，从而防止复制和重用。

为什么这样能防重用？ 因为每次验证都要签名方实时参与（他就是那个知道 d 的人）。签名被复制了也没用——离开签名方就没法完成验证。

准备阶段：服务器（课件里用的是"银行"）根据一个随机数 r 算出一条链：

服务器只保存 x₁₀₀，把 x₀~x₉₉ 全部交给 Alice。

登录时（注意：倒着用！）：

① 简单分割——物理上切开

问题：每份里直接含有明文片段，安全性差。拿到任意一段都能猜出信息。

② 加密分割——用异或藏起来

好处：明文被隐藏了。单独任何一份都看不出信息。

但还是不够好：必须收齐全部五份才能恢复。有没有"凑够几份就行"的办法？

课件用的多项式是：f(x) = 13 + 10x + 2x² (mod 17)

（3 个份额能恢复，所以是 2 次多项式；5 是分给 5 个人。）

计算 5 个份额：

把 8、7、10、0、11 这五个份额分给五个人。

恢复：拿其中 3 个（比如 D₁=8, D₃=10, D₅=11）

设 f(x) = m + a₁x + a₂x²，代入三个点：

三个方程解三个未知数，得到 m = 13 ✓

（也可以直接用拉格朗日插值算出 f(0) = 13。）

验证：13 正好是多项式 f(x) = 13 + 10x + 2x² 的常数项 ✓

选 n 个两两互素的数 m₁ < m₂ < … < m_n，秘密 x 发布时就分发 a_i = x mod m_i。

恢复时用 CRT（中国剩余定理）解同余方程组。

课件算例：m₁=9, m₂=11, m₃=13, m₄=14，取 k=3, n=4，秘密 x = 500

得到 (3,4) 门限方案：{(5,9) (5,11) (6,13) (10,14)}

取 (5,9)、(5,11)、(6,13)：

用 CRT 解得 x ≡ 500 (mod 1287) ✓（1287 = 9×11×13）

取 (5,9)、(6,13)：

但 117 = 9×13，而 x 的真实范围是 182 < x < 1287。

所以满足条件的 x 可能是：266, 383, 500, 617, 734, …

无法唯一确定！ 这就保证了安全性。

看明白了吗：全程没有一个"密钥"被传输过，但两人通过"重重加密、依次解密"完成了保密通信。

课件原文总结：三次传输协议的特点——重重加密，依次解密；加解密的运算顺序可交换。

关键在哪：KDC 用私钥解密后，得到的是"被 Alice 公钥锁着的东西"——他能认出这是自己发的某个密钥，但不知道是哪一个（因为他没有 Alice 的私钥）。

协议特点：保证密钥的保密性，减弱对 KDC 安全性的依赖。

妙处：Bob 挑牌时是"盲挑"的（他解不开 Alice 的加密）；Alice 也不会知道 Bob 挑的是哪 5 张。

看明白了吗：Alice 不知道 Bob 用了哪对公钥，所以不知道他拿到的是 m₁ 还是 m₂；Bob 也只能拿到其中一个。

为什么安全？ 因为每个人看到的都是"带着随机数 r 的和"，从里面推不出任何一个人的单独工资。

比如 Alice 拿到的是 s₂ + r —— 她知道 s₂ + r 这个值，但不知道 r 是多少，所以不知道 s₂。

最后公开的也是 s₁+s₂+s₃+r，还是不知道 r。

只有把 r 去掉，才能得到总和。 而 r 是 Bob 私下选的。

场景：Alice 想让 KDC（密钥分配中心，算力强）帮忙找回私钥 x，但不想让 KDC 知道 x。公钥 y 与私钥 x 的关系是 y = g^x mod p。

可解性验证（用费马小定理）：

KDC 只看到 y′ 和 x′——他能算出 x′，但不知道 r，所以永远得不到真正的 x。

问题：Alice 有 x，Bob 有 y，在不泄露 x 和 y 的情况下比较大小。

课件参数：1 ≤ x, y ≤ 4，x=4，y=2，Bob 公钥 k_p=7、私钥 k_v=23，n=55

协议流程：

判定规则：

为什么这样能判断？

• 如果 x ≤ y，那么第 x 个数没被加 1，它等于 D(c−x+x) = D(c) = k
• 如果 x > y，那么第 x 个数被加了 1，等于 k+1 ≠ k

妙在哪：把"比较大小"巧妙地转换成了"位置的先后关系"。Alice 只看到一串数字，从里面推不出 y 是多少（因为她不知道哪些被加了 1）。

代价：A 做 4 次加密计算，广播 4 个数据包。接收方要做 3 或 4 次解密。

思路：不用一个个加密，而是构造一个数 R，让有权限的人"模一下"就能拿到密钥，没权限的人拿不到。

代价：A 做 1 次加密 + 1 次 CRT 计算，广播 2 个数据包。接收方做 1 次模运算，0 或 1 次解密。

对称密码方案的对应关系（课件原话）：

• "随机数 r 保证 Alice 不能篡改承诺结果"
• "密钥 k 用来让 Bob 验证承诺结果"

想象一个环形洞穴，有左右两个入口 C 和 D，中间有一道门，只有会念咒语的人才能打开。

协议过程：

为什么这能证明？

• 如果 A 会咒语 → 无论 B 要求从哪边出，她都能打开门绕过去 → 每次都成功
• 如果 A 不会咒语 → 她进去时在哪边，就只能从哪边出来。所以每次被指定的边刚好是她所在的那边的概率是 1/2。重复 n 次都碰巧猜对的概率是 (1/2)ⁿ，趋近于 0

最关键的一点：整个过程，B 没有获得关于咒语的任何信息——他只知道"A 一定知道咒语"，但不知道咒语是什么。

这就是"零知识"——知识为零，信心满满。

为什么这就安全了？ 因为如果 Alice 想作弊（比如把 n 个文件里塞一个"欠条"），那 Bob 检查的 n−1 个里很可能包括它。

Alice 能成功欺骗的概率是 1/n —— n 越大越安全。

（"分割选择"这个名字的意思就是：把一批文件分成"检查的"和"签名的"两部分。）

简单可靠，但需要信任 TTP（而且 TTP 可能是瓶颈）。

Alice 和 Bob 依次在合约上逐个签上自己名字的字母。

但这要求两人同时在场。

思路：每一步只增加一点点"接受概率"，让谁先违约都不划算。

判定规则：如果在完成日期之前完成协议，双方受合约约束；否则法官随机选一个 p，若 p < (p_A, p_B) 则双方受约束。

妙处：因为每一步只加一点点概率，所以"早违约"和"晚违约"的收益差很小。谁也没动力去赌那一点点时间差。

为什么这能做到"同时"？

因为信息是"要么都给，要么都不给"——第 ③ 步解出一半消息后，双方都处于"我拿到了半个合同"的状态。此时谁想退出，对方也拿不出完整的合同来害他。要么双方都完成，要么都作废。

（这里用到的"不经意传输"就是 4.1 节讲的 OT 协议。）

特点：主办方不知道投票者身份——匿名性没问题。

但问题来了：

• 投票次数不定（一个人可以投很多次）
• 无法确认投票者身份（张三可以冒充李四）

改进：保证了投票者身份和投票次数（因为签名唯一）。

但又冒出新问题：CTF 现在知道"谁投了谁的票"——因为签名暴露了身份，而且解密的选票内容也在他手里，两者可以对上号。

设计思路对照现场投票：

关键设计：选票的构建

匿名怎么保证：

• 采用 盲签名协议进行选票签名
• 切断投票者与选票的对应关系，但能鉴别
• 签名者知道在干什么，但不知签名的内容

防重复投票：CTF 通过"验证重复"来保证一人一票——同一张识别号的选票只能用一次。

为什么密钥会抵消？ 因为每个密钥都出现了两次：k₁₂ 在 m₁ 和 m₂ 里各一次，异或两次就抵消了。

外面的人看到的是：三个人都发了消息，但无法判断是哪一个真正发了内容。

（这就是 DC-Net 的基本思想。）

① 代理机制——借助可信第三方隐蔽真实身份

• 单代理：Penet、Anonymizer、LPWA
• 多代理：OR、Hordes、Morphmix（代理链，更安全）

② MIX 机制——这是最经典也最优雅的方案

MIX 是一些特殊节点，它做两件事：

• 通过加密或填充改变消息的外观
• 通过延迟或重排序改变消息的顺序

这样就能隐藏输入和输出的对应关系，攻击者无法推断通信关系。

每一个 MIX 只能剥掉自己那一层，只知道"上家"和"下家"，不知道全貌。

应用：匿名电子邮件（Babel、MixMaster、MixMinion）、匿名连接服务（OR、Tarzan、MorphMix、WonGoo）、匿名 Web 浏览（Crowds、Webmix）。

③ Crowds 系统——基于 P2P 对等网络思想

特点：对称加密机制；缺点是转发路径可能过长。

④ 广播/多播机制：DC-Net、Hordes、P5 系统等。每个节点发送所有共享密钥的异或值，发送者把消息加进去（就是前面那个技巧）。

要求：匿名，消息可以确认，但不可跟踪。同时银行和政府不愿意放弃审计追踪控制。

为什么匿名？ 因为银行签的那个信封他没打开过——不知道该汇票最终会流向谁。

区块里的内容大概是：A 存入 80 元 → A 取出 30 元 → A 存入 20 元……（每一笔都记着）

起源：2008 年，一个化名为中本聪的人，在《比特币：一个点对点的电子现金系统》论文中提出。2009 年系统开始运行。

记账权：工作量证明 POW。

挖矿：寻找一个数 Nonce，使得

h(Nonce ‖ Prev_Hash ‖ Tx) < Bits

大白话：就是不断试不同的 Nonce，算哈希，看结果是不是"以 48 个 0 开头"。因为哈希是随机的，只能一个个试——这就是"挖矿"。

奖励递减：50 BTC（210000 个块，约 4 年）→ 25 BTC → 12.5 BTC → …… 公式是 50×(1/2)ⁿ。预计 2140 年全部 BTC 被挖完（21×10⁶ 个）。