4.6 密码学

相关笔记： 4.5 同余的应用 | 5.1 数学归纳法

概览

本节系统介绍了密码学（Cryptography）的基本概念与核心算法，从古典密码到现代公钥密码学，涵盖了密码学的主要分支。主要内容包括：

对称密钥密码（私钥密码）：凯撒密码、移位密码、仿射密码、维吉尼亚密码、换位密码

密码分析（Cryptanalysis）：基于字母频率分析破解移位密码

密码系统的形式化定义：五元组 $(P, C, K, E, D)$

公钥密码学的基本思想：加密密钥公开，解密密钥保密

RSA 密码系统的完整推导：密钥生成、加密 $c = m^{e} mod n$ 、解密 $m = c^{d} mod n$

RSA 安全性的数学基础：大整数分解的计算困难性

Diffie-Hellman 密钥交换协议：基于离散对数问题的安全密钥协商

数字签名：利用 RSA 实现消息认证与不可否认性

同态加密：RSA 的乘法同态性与全同态加密的前沿进展

一、知识结构总览

graph TB
    A["4.6 密码学 Cryptography"] --> B["古典密码学（对称密钥）"]
    A --> C["密码分析"]
    A --> D["密码系统形式化"]
    A --> E["公钥密码学"]
    A --> F["RSA 密码系统"]
    A --> G["密码协议"]
    A --> H["同态加密"]

    B --> B1["凯撒密码 Caesar Cipher"]
    B --> B2["移位密码 Shift Cipher"]
    B --> B3["仿射密码 Affine Cipher"]
    B --> B4["维吉尼亚密码 Vigenere Cipher"]
    B --> B5["换位密码 Transposition Cipher"]

    C --> C1["字母频率分析"]
    C --> C2["穷举攻击"]

    D --> D1["五元组 (P, C, K, E, D)"]
    D --> D2["加密函数 E_k"]
    D --> D3["解密函数 D_k"]

    E --> E1["公钥 vs 私钥"]
    E --> E2["加密不蕴含解密"]
    E --> E3["AES 私钥标准"]

    F --> F1["密钥生成：n=pq, gcd(e,φ)=1"]
    F --> F2["加密：c = m^e mod n"]
    F --> F3["解密：m = c^d mod n"]
    F --> F4["正确性证明（费马小定理+CRT）"]
    F --> F5["安全性：大整数分解困难"]

    G --> G1["Diffie-Hellman 密钥交换"]
    G --> G2["数字签名 Digital Signatures"]
    G --> G3["签名+加密的秘密通信"]

    H --> H1["RSA 乘法同态"]
    H --> H2["全同态加密 FHE"]

二、核心思想

核心思想

本节的核心思想是信息的加密与解密，即如何通过数学变换将明文（plaintext）转换为密文（ciphertext），使得只有拥有特定知识（密钥）的人才能恢复原始信息。密码学的发展经历了从对称密钥（加密和解密使用相同或易互推的密钥）到公钥密码学（加密密钥公开，解密密钥保密）的重大飞跃。RSA 系统是公钥密码学的里程碑，其安全性建立在大整数分解的计算困难性之上。而 Diffie-Hellman 密钥交换则利用了离散对数问题的计算困难性，使得双方可以在不安全信道上协商共享密钥。

1. 凯撒密码与移位密码

凯撒密码（Caesar Cipher）

凯撒密码是最古老的加密方法之一，由 Julius Caesar 使用。将每个字母在字母表中向后移动 3 位：

$f (p) = (p + 3) mod 26$

其中 $p \in Z_{26}$ 是字母的数值编码（ $A = 0, B = 1, \dots, Z = 25$ ）。

解密函数： $f^{- 1} (p) = (p - 3) mod 26$ 。

移位密码（Shift Cipher）

凯撒密码的推广，将移位量从固定的 3 推广为任意整数 $k$ ：

$f (p) = (p + k) mod 26$

解密函数： $f^{- 1} (p) = (p - k) mod 26$ 。

整数 $k$ 称为密钥（key）。

例1：凯撒密码加密

用凯撒密码加密 “MEET YOU IN THE PARK”：

将字母转为数值：M=12, E=4, E=4, T=19, Y=24, O=14, U=20, I=8, N=13, T=19, H=7, E=4, P=15, A=0, R=17, K=10

加密 $f (p) = (p + 3) mod 26$ ：15, 7, 7, 22, 1, 17, 23, 11, 16, 22, 10, 7, 18, 3, 20, 13

转回字母：PHHW BRX LQ WKH SDUN

例2：移位密码加密（ $k = 11$ ）

加密 “STOP GLOBAL WARMING”，密钥 $k = 11$ ：

S=18→3, T=19→4, O=14→25, P=15→0, G=6→17, L=11→22, O=14→25, B=1→12, A=0→11, L=11→22, W=22→7, A=0→11, R=17→2, M=12→23, I=8→19, N=13→24, G=6→17

密文：DEZA RWZMLW HLCXTYR

例3：移位密码解密（ $k = 7$ ）

解密密文 “LEWLYPLUJL PZ H NYLHA ALHJOLY”，密钥 $k = 7$ ：

解密 $f^{- 1} (p) = (p - 7) mod 26$ ：

L=11→4(E), E=4→23(X), W=22→15(P), …

明文：EXPERIENCE IS A GREAT TEACHER

2. 仿射密码

仿射密码（Affine Cipher）

仿射密码使用形如

$f (p) = (a p + b) mod 26$

的加密函数，其中 $a, b$ 为整数。 $f$ 是双射当且仅当 $g cd (a, 26) = 1$ 。

解密方法：已知密文 $c = (a p + b) mod 26$ ，则

$c - b \equiv a p (mod 26)$ $p \equiv \overset{a}{ˉ} (c - b) (mod 26)$

其中 $\overset{a}{ˉ}$ 是 $a$ 模 $26$ 的逆元（由 Theorem 1 保证存在）。

例4：仿射密码加密

用 $f (p) = (7 p + 3) mod 26$ 加密字母 K：

K 的数值为 $10$ 。 $f (10) = (7 \times 10 + 3) mod 26 = 73 mod 26 = 21$ 。

$21$ 代表 V，因此 K 被替换为 V。

3. 密码分析

密码分析（Cryptanalysis）

密码分析是在不知道加密方法和密钥的情况下，从密文恢复明文的过程。

对于移位密码，主要工具是字母频率分析：

英文中最常见的 9 个字母及其近似频率：

字母 E T A O I N S H R
频率 13% 9% 8% 8% 7% 7% 7% 6% 6%

字母	E	T	A	O	I	N	S	H	R
频率	13%	9%	8%	8%	7%	7%	7%	6%	6%

例5：频率分析破解移位密码

截获密文 “ZNK KGXRE HOXJ MKZY ZNK CUXS”，已知使用移位密码。

统计密文字母频率，最常见字母为 K。

假设 K 对应明文 E： $10 = 4 + k (mod 26)$ ，得 $k = 6$ 。

用 $k = 6$ 解密（每个字母移位 $- 6$ ）：THE EARLY BIRD GETS THE WORM

消息有意义，假设正确。

4. 换位密码与维吉尼亚密码

换位密码（Transposition Cipher, Example 6）

换位密码是一种分组密码（block cipher），使用集合 ${1, 2, \dots, m}$ 的一个排列 $σ$ 作为密钥。将明文分成大小为 $m$ 的块，每块 $p_{1} p_{2} \dots p_{m}$ 加密为 $c_{1} c_{2} \dots c_{m} = p_{σ (1)} p_{σ (2)} \dots p_{σ (m)}$ 。

解密使用逆排列 $σ^{- 1}$ 。

例6：换位密码加密与解密

排列 $σ$ ： $σ (1) = 3, σ (2) = 1, σ (3) = 4, σ (4) = 2$ 。

(a) 加密 “PIRATE ATTACK”：分块 PIRA TEAT TACK → IAPR ETTA AKTC

(b) 解密 “SWUE TRAE OEHS”： $σ^{- 1}$ ： $1 \to 2, 2 \to 4, 3 \to 1, 4 \to 3$

SWUE → USEW, TRAE → ATER, OEHS → HOSE → USE WATER HOSE

维吉尼亚密码（Vigenere Cipher）

维吉尼亚密码是一种分组密码，密钥是一个字母串 $k_{1} k_{2} \dots k_{m}$ 。对明文块 $p_{1} p_{2} \dots p_{m}$ ，密文块为：

$(p_{1} + k_{1}) mod 26, (p_{2} + k_{2}) mod 26, \dots, (p_{m} + k_{m}) mod 26$

本质上是对每个位置使用不同的移位量。

维吉尼亚密码示例

密钥 RED = (17, 4, 3)，明文 ORANGE = (14, 17, 0, 13, 6, 4)。

分块：(14, 17, 0) 和 (13, 6, 4)。

加密：(14+17, 17+4, 0+3) = (31, 21, 3) mod 26 = (5, 21, 3)

(13+17, 6+4, 4+3) = (30, 10, 7) mod 26 = (4, 10, 7)

密文：FVDEKH

5. 密码系统的形式化定义

密码系统（Cryptosystem, Definition 1）

一个密码系统是一个五元组 $(P, C, K, E, D)$ ，其中：

$P$ 是明文字符串集合

$C$ 是密文字符串集合

$K$ 是密钥空间（所有可能密钥的集合）

$E$ 是加密函数集合

$D$ 是解密函数集合

对每个密钥 $k \in K$ ，有加密函数 $E_{k} \in E$ 和解密函数 $D_{k} \in D$ ，满足：

$D_{k} (E_{k} (p)) = p 对所有明文 p$

例7：移位密码作为密码系统

$P = C = Z_{26}$ 上的字符串集合

$K = Z_{26}$ （密钥为移位量 $k$ ）

$E_{k} (p) = (p + k) mod 26$

$D_{k} (c) = (c - k) mod 26$

6. 公钥密码学

公钥密码学（Public Key Cryptography）

公钥密码学于 1970 年代被提出，其核心思想是：

加密密钥（公钥）公开，任何人都可以加密消息

解密密钥（私钥）保密，只有接收者可以解密

知道加密方法不等于知道解密方法

与私钥密码学（对称密钥）的区别：

私钥系统：加密密钥和解密密钥必须保密，通信双方需共享密钥

公钥系统：无需预先共享密钥，解决了密钥分发问题

公钥 vs 私钥密码学对比

特性私钥密码学公钥密码学
密钥加密/解密使用相同密钥加密密钥公开，解密密钥保密
密钥分发需要安全信道无需安全信道
速度快慢
代表 AES, DES RSA, ECC
典型用途大量数据加密密钥交换、数字签名

特性	私钥密码学	公钥密码学
密钥	加密/解密使用相同密钥	加密密钥公开，解密密钥保密
密钥分发	需要安全信道	无需安全信道
速度	快	慢
代表	AES, DES	RSA, ECC
典型用途	大量数据加密	密钥交换、数字签名

7. RSA 密码系统

RSA 密码系统（RSA Cryptosystem）

RSA 由 Rivest、Shamir 和 Adleman 于 1976 年在 MIT 提出（Clifford Cocks 于 1973 年在英国 GCHQ 秘密发现）。

密钥生成：

选择两个大素数 $p$ 和 $q$ （各约 300 位），计算 $n = pq$

计算 $φ (n) = (p - 1) (q - 1)$ （Euler 函数）

选择 $e$ 使得 $g cd (e, φ (n)) = 1$ （ $e$ 为公钥指数）

求 $e$ 模 $φ (n)$ 的逆元 $d$ （ $d$ 为私钥指数）

公钥： $(n, e)$ ；私钥： $d$

加密： $c = m^{e} mod n$

解密： $m = c^{d} mod n$

RSA 解密的正确性

设 $n = pq$ ， $d e \equiv 1 (mod (p - 1) (q - 1))$ ，则 $c^{d} \equiv m (mod n)$ 。

证明：因为 $d e \equiv 1 (mod (p - 1) (q - 1))$ ，存在整数 $k$ 使得 $d e = 1 + k (p - 1) (q - 1)$ 。

$c^{d} \equiv (m^{e})^{d} = m^{d e} = m^{1 + k (p - 1) (q - 1)} (mod n)$

由费马小定理（假设 $g cd (m, p) = g cd (m, q) = 1$ ）：

$m^{p - 1} \equiv 1 (mod p), m^{q - 1} \equiv 1 (mod q)$

因此：

$c^{d} \equiv m \cdot (m^{p - 1})^{k (q - 1)} \equiv m \cdot 1 = m (mod p)$ $c^{d} \equiv m \cdot (m^{q - 1})^{k (p - 1)} \equiv m \cdot 1 = m (mod q)$

因为 $g cd (p, q) = 1$ ，由中国剩余定理：

$c^{d} \equiv m (mod pq) = m (mod n)$

$■$

例8：RSA 加密

用 RSA 公钥 $(2537, 13)$ 加密消息 “STOP”。

$n = 2537 = 43 \times 59$ ， $e = 13$ ， $g cd (13, 42 \times 58) = 1$ 。

将 STOP 转为数值：S=18, T=19, O=14, P=15。

分块（ $2525 < 2537 < 252525$ ，每块 4 位）： $1819$ 和 $1415$ 。

加密 $c = m^{13} mod 2537$ ：

$181 9^{13} mod 2537 = 2081$

$141 5^{13} mod 2537 = 2182$

密文：2081 2182

例9：RSA 解密

收到密文 “0981 0461”，用 $n = 2537, e = 13$ 解密。

由 Exercise 2， $d = 937$ 是 $13$ 模 $42 \times 58 = 2436$ 的逆元。

解密 $m = c^{937} mod 2537$ ：

$098 1^{937} mod 2537 = 0704$

$046 1^{937} mod 2537 = 1115$

数值： $07041115$ → H=07, E=04, L=11, P=15 → HELP

RSA 安全性分析

RSA 的安全性基于以下计算困难性假设：

大整数分解困难：已知 $n = pq$ （ $p, q$ 各约 300 位），目前没有多项式时间算法能分解 $n$

已知 $n$ 和 $e$ ，无法在不分解 $n$ 的情况下有效计算 $d$

没有分解 $n$ 的方法也无法解密消息

重要威胁：量子计算的发展可能在未来 20-30 年内使 RSA 不安全，因为 Shor 算法可以在多项式时间内分解大整数。

8. Diffie-Hellman 密钥交换

Diffie-Hellman 密钥交换协议（Diffie-Hellman Key Exchange）

由 Whitfield Diffie 和 Martin Hellman 于 1976 年提出（Malcolm Williamson 于 1974 年在英国 GCHQ 秘密发明）。

协议步骤（在 $Z_{p}$ 中计算）：

Alice 和 Bob 公开约定素数 $p$ 和 $p$ 的原根 $a$

Alice 选择秘密整数 $k_{1}$ ，发送 $a^{k_{1}} mod p$ 给 Bob

Bob 选择秘密整数 $k_{2}$ ，发送 $a^{k_{2}} mod p$ 给 Alice

Alice 计算 $(a^{k_{2}})^{k_{1}} mod p$

Bob 计算 $(a^{k_{1}})^{k_{2}} mod p$

共享密钥： $(a^{k_{2}})^{k_{1}} mod p = (a^{k_{1}})^{k_{2}} mod p = a^{k_{1} k_{2}} mod p$

安全性：窃听者知道 $p, a, a^{k_{1}} mod p, a^{k_{2}} mod p$ ，但要求出 $k_{1}$ 或 $k_{2}$ 需要解决离散对数问题，这在计算上是不可行的（当 $p$ 超过 300 位时）。

9. 数字签名

数字签名（Digital Signatures）

数字签名利用 RSA 实现消息认证：接收者可以确认消息确实来自声称的发送者。

签名协议（Alice 发送签名消息）：

Alice 的公钥为 $(n, e)$ ，私钥为 $d$

Alice 将消息分为块 $m_{1}, m_{2}, \dots, m_{k}$

Alice 对每块应用解密函数 $D_{(n, e)} (m_{i}) = m_{i}^{d} mod n$

Alice 将签名后的块发送给所有接收者

接收者对每块应用 Alice 的加密函数 $E_{(n, e)} (s_{i}) = s_{i}^{e} mod n$ 恢复原始消息

因为只有 Alice 知道私钥 $d$ ，所以只有 Alice 能产生有效的签名。

例10：RSA 数字签名

Alice 的 RSA 密钥： $n = 2537, e = 13, d = 937$ 。

Alice 要签名发送 “MEET AT NOON”：

转为数值块： $12040419001913141413$ 。

签名（对每块计算 $m^{937} mod 2537$ ）：

$120 4^{937} mod 2537 = 0817$

$041 9^{937} mod 2537 = 0555$

$001 9^{937} mod 2537 = 1310$

$131 4^{937} mod 2537 = 2173$

$141 3^{937} mod 2537 = 1026$

签名消息：0817 0555 1310 2173 1026

接收者用 $E_{(2537, 13)}$ （即 $s^{13} mod 2537$ ）验证签名。

签名 + 加密的秘密通信

若 Alice 要向 Bob 发送既签名又加密的消息：

Alice 先用自己的私钥 $d_{A}$ 签名： $s = D_{(n_{A}, e_{A})} (m)$

再用 Bob 的公钥 $(n_{B}, e_{B})$ 加密： $c = E_{(n_{B}, e_{B})} (s)$

Bob 收到后先用自己的私钥 $d_{B}$ 解密： $s = D_{(n_{B}, e_{B})} (c)$

再用 Alice 的公钥 $(n_{A}, e_{A})$ 验证： $m = E_{(n_{A}, e_{A})} (s)$

这样既保证了机密性（只有 Bob 能读），又保证了认证性（只有 Alice 能签）。

10. 同态加密

同态加密（Homomorphic Encryption）

同态加密允许在密文上直接执行计算，计算结果解密后等于对明文执行相同计算的结果。

RSA 是乘法同态的（Example 11）：

$E_{(n, e)} (M_{1}) \cdot E_{(n, e)} (M_{2}) mod n = (M_{1}^{e} mod n) (M_{2}^{e} mod n) mod n = (M_{1} M_{2})^{e} mod n = E_{(n, e)} (M_{1} M_{2})$

即密文相乘等于明文乘积的加密。

但 RSA 不是加法同态的： $E (M_{1}) + E (M_{2}) \neq = E (M_{1} + M_{2})$ 。

全同态加密（Fully Homomorphic Encryption, FHE）

全同态加密允许在密文上执行任意计算（包括加法和乘法），由 Craig Gentry 于 2009 年首次实现（基于格密码学）。

FHE 的意义：可以在不解密的情况下对加密数据运行程序，输出是明文结果的加密。这在云计算中具有重大应用价值，但目前尚无实用的 FHE 方案（计算和内存开销过大）。

三、补充理解与易混淆点

补充理解

补充1：RSA 的历史与 Clifford Cocks 的秘密发现

RSA 公钥密码系统通常归功于 MIT 的 Rivest、Shamir 和 Adleman（1976 年发表）。然而，英国 GCHQ 的 Clifford Cocks 在 1973 年就独立发现了相同的方案，但由于保密原因直到 1997 年才解密公开。类似地，Diffie-Hellman 密钥交换也由 Malcolm Williamson 于 1974 年在英国 GCHQ 秘密发明。这段历史揭示了密码学研究中学术公开与政府保密之间的张力。RSA 的安全性依赖于大整数分解问题的计算困难性，目前最快的经典算法是普通数域筛法（GNFS），其时间复杂度为亚指数级 $O (exp ((64/9)^{1/3} (ln n)^{1/3} (ln ln n)^{2/3}))$ 。截至 2020 年，被分解的最大 RSA 数为 829 位（250 个十进制位）。

RSA Factoring Challenge - Wikipedia — RSA 分解挑战的历史记录

The Code Book by Simon Singh — 密码学通俗历史

来源：Cocks, C. (1973). “A Note on ‘Non-Secret Encryption’.” CESG Memorandum (declassified 1997). 来源：Rivest, R. L., Shamir, A. & Adleman, L. (1978). “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems.” Communications of the ACM, 21(2), 120–126.

补充2：量子计算对密码学的威胁与后量子密码学

1994 年，Peter Shor 提出了Shor 算法，可以在多项式时间内分解大整数和求解离散对数问题，这意味着一旦大规模量子计算机成为现实，RSA 和 Diffie-Hellman 等基于数论的密码系统将不再安全。为此，NIST 于 2024 年正式发布了首批后量子密码标准，包括基于格的 ML-KEM（密钥封装）和 ML-DSA（数字签名）等。这些方案的安全性基于格问题（如最短向量问题 SVP），这些问题即使对量子计算机也被认为是困难的。同态加密领域也受益于格密码学——Gentry 的 FHE 方案正是基于格的。

Post-Quantum Cryptography - NIST — NIST 后量子密码标准化项目

Shor’s Algorithm - Wikipedia — Shor 算法详解

来源：Shor, P. W. (1994). “Algorithms for Quantum Computation: Discrete Logarithms and Factoring.” Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 124–134. 来源：NIST (2024). “Post-Quantum Cryptography Standardization.” Federal Information Processing Standards (FIPS) 203, 204, 205.

易混淆点

误区1：混淆公钥密码与私钥密码的安全性

❌ 认为”公钥密码比私钥密码更安全”

✅ 两种密码学的安全性取决于不同的数学问题：私钥密码（如 AES）的安全性基于密码设计的复杂性；公钥密码（如 RSA）的安全性基于数学问题的计算困难性

❌ 认为”RSA 可以完全取代 AES”

✅ 实际应用中两者互补使用：RSA 用于密钥交换和数字签名，AES 用于大量数据的加密（因为 RSA 加解密比 AES 慢约 1000 倍）

⚠️ 典型组合：用 RSA 协商一个随机的 AES 会话密钥，然后用 AES 加密实际数据

误区2：混淆 RSA 加密与数字签名中公钥/私钥的使用顺序

❌ 认为”签名就是加密，验证就是解密”

✅ 在 RSA 数字签名中，Alice 用自己的私钥 $d$ 签名（对消息应用”解密”变换），接收者用 Alice 的公钥 $e$ 验证（对签名应用”加密”变换）

❌ 混淆”用自己的私钥签名”和”用对方的公钥加密”

✅ 正确理解：

加密（保密）：用接收者的公钥加密，只有接收者能用其私钥解密

签名（认证）：用发送者的私钥签名，任何人都能用发送者的公钥验证

⚠️ 当同时需要保密和认证时，先签名再用对方公钥加密

四、习题精选

习题概览

题号范围核心考点难度
1-3 凯撒密码/移位密码/仿射密码加密 ⭐
4-5 凯撒密码/移位密码解密 ⭐
6-9 频率分析破解移位密码 ⭐⭐
10-12 仿射密码的解密函数与自逆密钥 ⭐⭐
13 频率分析破解仿射密码 ⭐⭐⭐
14-16 换位密码加密/解密/破解 ⭐⭐
18-22 维吉尼亚密码加密/解密/破解 ⭐⭐⭐
23 已知 $φ (n)$ 时分解 $n$ ⭐⭐⭐
24-27 RSA 加密/解密计算 ⭐⭐⭐
28 RSA 解密正确性证明（ $g cd (M, pq) > 1$ 情形） ⭐⭐⭐⭐
29-30 Diffie-Hellman 密钥交换计算 ⭐⭐⭐
31-32 RSA 数字签名/签名+加密 ⭐⭐⭐
33 私钥密码学密钥交换协议 ⭐⭐⭐
34-35 Paillier 密码系统与加法同态 ⭐⭐⭐⭐

题号范围	核心考点	难度
1-3	凯撒密码/移位密码/仿射密码加密	⭐
4-5	凯撒密码/移位密码解密	⭐
6-9	频率分析破解移位密码	⭐⭐
10-12	仿射密码的解密函数与自逆密钥	⭐⭐
13	频率分析破解仿射密码	⭐⭐⭐
14-16	换位密码加密/解密/破解	⭐⭐
18-22	维吉尼亚密码加密/解密/破解	⭐⭐⭐
23	已知 $φ (n)$ 时分解 $n$	⭐⭐⭐
24-27	RSA 加密/解密计算	⭐⭐⭐
28	RSA 解密正确性证明（ $g cd (M, pq) > 1$ 情形）	⭐⭐⭐⭐
29-30	Diffie-Hellman 密钥交换计算	⭐⭐⭐
31-32	RSA 数字签名/签名+加密	⭐⭐⭐
33	私钥密码学密钥交换协议	⭐⭐⭐
34-35	Paillier 密码系统与加法同态	⭐⭐⭐⭐

题1：凯撒密码加密

题目

用凯撒密码 $f (p) = (p + 3) mod 26$ 加密消息 “DO NOT PASS GO”。

解答

将字母转为数值：

D=3, O=14, N=13, O=14, T=19, P=15, A=0, S=18, S=18, G=6, O=14

加密 $f (p) = (p + 3) mod 26$ ：

3→6(G), 14→17(R), 13→16(Q), 14→17(R), 19→22(W), 15→18(S), 0→3(D), 18→21(V), 18→21(V), 6→9(J), 14→17(R)

密文：GR QRW SDVV JR

$■$

解题思路提示

凯撒密码加密步骤：(1) 字母→数值（A=0, B=1, …, Z=25）；(2) 每个数值加 3 后取模 26；(3) 数值→字母。注意空格保持不变。

题2：仿射密码加密

题目

用仿射密码 $f (p) = (3 p + 7) mod 26$ 加密消息 “DO NOT PASS GO”。

解答

字母数值：D=3, O=14, N=13, O=14, T=19, P=15, A=0, S=18, S=18, G=6, O=14

计算 $f (p) = (3 p + 7) mod 26$ ：

D: $(3 \times 3 + 7) mod 26 = 16$ → Q

O: $(3 \times 14 + 7) mod 26 = 49 mod 26 = 23$ → X

N: $(3 \times 13 + 7) mod 26 = 46 mod 26 = 20$ → U

O: 23 → X

T: $(3 \times 19 + 7) mod 26 = 64 mod 26 = 12$ → M

P: $(3 \times 15 + 7) mod 26 = 52 mod 26 = 0$ → A

A: $(3 \times 0 + 7) mod 26 = 7$ → H

S: $(3 \times 18 + 7) mod 26 = 61 mod 26 = 9$ → J

S: 9 → J

G: $(3 \times 6 + 7) mod 26 = 25$ → Z

O: 23 → X

密文：QXUX MAHJJ ZX

$■$

解题思路提示

仿射密码加密：注意 $g cd (a, 26) = 1$ 是必要条件（此处 $a = 3$ ， $g cd (3, 26) = 1$ ✓）。计算时先乘后加再取模。

题3：频率分析破解移位密码

题目

密文 “DY CVOOZ ZOBMRKXMO DY NBOKW” 由移位密码加密，求明文。

解答

统计密文字母频率：O 出现 4 次，Z 出现 2 次，M 出现 2 次，K 出现 2 次。最常见字母为 O。

假设 O 对应 E： $14 = 4 + k (mod 26)$ ， $k = 10$ 。

用 $k = 10$ 解密（每个字母减 10 模 26）：

D=3→-7≡19(T), Y=24→14(O), C=2→-8≡18(S), V=21→11(L), O=14→4(E), O→E, Z=25→15(P), Z→P, O→E, B=1→-9≡17(R), M=12→2(C), R=17→7(H), K=10→0(A, X=23→13(N), M→C, O→E, D→T, Y→O, N=13→3(D), B→R, O→E, K→A, W=22→12(M)

明文：TO SLEEP PERCHANCE TO DREAM

$■$

解题思路提示

频率分析步骤：(1) 统计密文字母频率；(2) 假设最常见密文字母对应 E（或 T、A 等）；(3) 推算移位量 $k$ ；(4) 解密验证是否得到有意义的文本。

题4：RSA 加密计算

题目

用 RSA 系统 $n = 43 \times 59 = 2537$ ， $e = 13$ 加密消息 “ATTACK”。

解答

将 ATTACK 转为数值：A=00, T=19, T=19, A=00, C=02, K=10。

分块（ $2525 < 2537$ ，每块 4 位）： $0019$ 和 $1900$ ， $0210$ 。

加密 $c = m^{13} mod 2537$ ：

$1 9^{13} mod 2537$ ：需要用快速模幂算法计算

$0019 = 19$ ， $1 9^{13} mod 2537$

$190 0^{13} mod 2537$

$0210 = 210$ ， $21 0^{13} mod 2537$

（具体数值需要借助计算工具，此处展示方法）

$■$

解题思路提示

RSA 加密步骤：(1) 字母→两位数（A=00, B=01, …, Z=25）；(2) 拼接并分块（块大小使最大块 $2525 \dots 25 < n$ ）；(3) 对每块计算 $c = m^{e} mod n$ （使用快速模幂算法）。

题5：Diffie-Hellman 密钥交换

题目

Alice 和 Bob 使用 Diffie-Hellman 协议，约定素数 $p = 23$ ，原根 $a = 5$ 。Alice 选择 $k_{1} = 8$ ，Bob 选择 $k_{2} = 5$ 。求共享密钥。

解答

步骤 1：Alice 计算 $5^{8} mod 23$ ：

$5^{2} = 25 \equiv 2 (mod 23)$

$5^{4} \equiv 2^{2} = 4 (mod 23)$

$5^{8} \equiv 4^{2} = 16 (mod 23)$

Alice 发送 $16$ 给 Bob。

步骤 2：Bob 计算 $5^{5} mod 23$ ：

$5^{5} = 5^{4} \times 5 \equiv 4 \times 5 = 20 (mod 23)$

Bob 发送 $20$ 给 Alice。

步骤 3：Alice 计算共享密钥： $2 0^{8} mod 23$ ：

$2 0^{2} = 400 \equiv 8 (mod 23)$ （因为 $400 = 17 \times 23 + 9$ …）

$2 0^{2} = 400 = 17 \times 23 + 9$ ，所以 $2 0^{2} \equiv 9 (mod 23)$

$2 0^{4} \equiv 9^{2} = 81 \equiv 12 (mod 23)$ （ $81 = 3 \times 23 + 12$ ）

$2 0^{8} \equiv 1 2^{2} = 144 \equiv 6 (mod 23)$ （ $144 = 6 \times 23 + 6$ ）

步骤 4：Bob 计算共享密钥： $1 6^{5} mod 23$ ：

$1 6^{2} = 256 \equiv 3 (mod 23)$ （ $256 = 11 \times 23 + 3$ ）

$1 6^{4} \equiv 3^{2} = 9 (mod 23)$

$1 6^{5} = 1 6^{4} \times 16 \equiv 9 \times 16 = 144 \equiv 6 (mod 23)$

共享密钥： $6$ 。双方计算结果一致。 ✓

$■$

解题思路提示

Diffie-Hellman 协议要点：(1) 双方各自选择秘密整数 $k_{1}, k_{2}$ ；(2) 各自计算 $a^{k_{i}} mod p$ 并发送给对方；(3) 各自将收到的值取自己的秘密指数次幂；(4) 由于 $(a^{k_{1}})^{k_{2}} = (a^{k_{2}})^{k_{1}} = a^{k_{1} k_{2}}$ ，双方得到相同的共享密钥。计算大幂时使用快速模幂算法。

五、视频学习指南

视频资源

资源链接对应内容备注
Rosen 8e Section 4.6 教材原文完整定义、定理与例题英文教材
Computerphile - RSA 链接 RSA 原理可视化讲解英文，科普向
3Blue1Brown - Diffie-Hellman 链接 Diffie-Hellman 密钥交换动画英文，直观演示
Khan Academy - Cryptography 链接密码学完整课程英文，系统教学

资源	链接	对应内容	备注
Rosen 8e Section 4.6	教材原文	完整定义、定理与例题	英文教材
Computerphile - RSA	链接	RSA 原理可视化讲解	英文，科普向
3Blue1Brown - Diffie-Hellman	链接	Diffie-Hellman 密钥交换动画	英文，直观演示
Khan Academy - Cryptography	链接	密码学完整课程	英文，系统教学

六、教材原文

教材原文

“Number theory plays a key role in cryptography, the subject of transforming information so that it cannot be easily recovered without special knowledge.”

“In public key cryptography, knowing how to encrypt does not also tell someone how to decrypt. The most widely used public key system, called the RSA cryptosystem, encrypts messages using modular exponentiation, where the modulus is the product of two large primes.”

“The protocol we will describe is known as the Diffie-Hellman key agreement protocol. The protocol ensures that $k_{1}$ , $k_{2}$ , and the common key are kept secret. To find the secret information from this public information requires that an adversary solves instances of the discrete logarithm problem.”

“Not only can cryptography be used to secure the confidentiality of a message, but it also can be used so that the recipient of the message knows that it came from the person they think it came from.”

参见 Wiki

密码学 — 密码学的基本概念与分类
凯撒密码 — 凯撒密码与移位密码
仿射密码 — 仿射密码的加密与解密
维吉尼亚密码 — 维吉尼亚密码的原理与破解
换位密码 — 换位密码与分组密码
RSA密码系统 — RSA 的完整推导与安全性分析
公钥密码学 — 公钥密码学的基本思想
Diffie-Hellman密钥交换 — Diffie-Hellman 协议详解
数字签名 — 数字签名的原理与应用
同态加密 — 同态加密与全同态加密
密码分析 — 频率分析与密码破解技术

数论与密码学

CS Wiki

探索

一、知识结构总览

二、核心思想

1. 凯撒密码与移位密码

2. 仿射密码

3. 密码分析

4. 换位密码与维吉尼亚密码

5. 密码系统的形式化定义

6. 公钥密码学

7. RSA 密码系统

8. Diffie-Hellman 密钥交换

9. 数字签名

10. 同态加密

三、补充理解与易混淆点

补充理解

易混淆点

四、习题精选

题1：凯撒密码加密

题2：仿射密码加密

题3：频率分析破解移位密码

题4：RSA 加密计算

题5：Diffie-Hellman 密钥交换

五、视频学习指南

六、教材原文

参见 Wiki

关系图谱

目录

反向链接