按知识域组织：数论 → 代数结构 → 信息论与复杂度 → 安全形式化。

数论基础

参考：Boneh-Shoup 附录 A · CTF Wiki · 数论

• 同余与模运算：$a\equiv b(\mathrm{mod}n)$；模加、模乘封闭性
• 欧几里得算法：求 gcd；扩展形式求模逆 $a^{-1}modn$
• 中国剩余定理（CRT）：模合数分解为模素数幂的积，加速 RSA 运算
• 费马小定理 / 欧拉定理：$a^{p-1}\equiv 1(\mathrm{mod}p)$；$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$
• 欧拉函数 φ(n)：RSA 密钥生成与欧拉定理应用的核心

练习：手写扩展欧几里得求 $17^{-1} \bmod 3120$。

代数结构与有限域

参考：Boneh-Shoup 附录 B–C

• 群：封闭、结合、单位元、逆元；循环群、阶、生成元
• 环与域：有限域 GF(p)、GF(2^n)；AES 运算在 GF(2^8) 上
• 离散对数：给定 $g,g^x$，求 $x$ 困难——DH、ECDH 的安全基础
• 原根与二次剩余：Legendre 符号、Tonelli-Shanks（CTF 偶见）

练习：在 SageMath 中验证 GF(2^8) 的乘法表与 AES 不可约多项式。

信息论与复杂度

参考：Shannon 1949 · Katz-Lindell Ch.2–3

信息论

• 熵 H(X)：随机变量的不确定性度量
• 完美保密：$P(M=m\mid C=c)=P(M=m)$，等价于 $|K|\ge |M|$
• 计算不可区分性：多项式时间敌手无法区分两个分布

复杂度

• 单向函数：易算、难逆；候选：乘法、模幂、哈希
• 陷门函数：持陷门信息则易逆——RSA 构造基础
• 可忽略函数 negl(λ)：安全证明中「成功概率可忽略」的严格含义

安全形式化

参考：Boneh-Shoup Ch.1–2 · Katz-Lindell Ch.1–3

• Kerckhoffs 原则：算法公开，密钥保密
• 安全游戏：IND-CPA（选择明文）、IND-CCA（选择密文）、EUF-CMA（存在性不可伪造）
• 归约证明：若敌手攻破方案 A，则可构造敌手攻破困难问题 B
• 随机预言机（ROM）：将哈希建模为理想随机函数；标准模型不依赖此假设

攻击能力	安全目标	典型方案
选择明文（CPA）	IND-CPA	语义安全加密
选择密文（CCA）	IND-CCA	AEAD、RSA-OAEP
选择消息	EUF-CMA	数字签名

练习：将主页四种攻击类型各映射到一条安全定义。

工具与练习

语言	库	用途
Python	gmpy2、SymPy	大整数与符号运算
—	SageMath	数论与有限域实验
Rust	num-bigint、rug	大整数

• 随机数：secrets / OsRng；禁止浮点参与模运算
• 可汗学院密码学、Cryptopals Set 0–1

本站笔记 待撰写。