密码学从诞生之初就与数学紧密结合。现代密码学的安全性建立在计算复杂性理论的基础上——解决某些数学问题（如大整数分解、离散对数）在计算上被认定是困难的。理解密码学，首先需要掌握其核心数学工具。
模运算是密码学中最基础的数学工具。对于整数 a、b 和正整数 n，有：
a≡b(modn)⟺n∣(a−b)
模运算满足加法、减法和乘法的封闭性：
(a+b)modn=((amodn)+(bmodn))modn
(a×b)modn=((amodn)×(bmodn))modn
模逆元是密码学中的关键概念。整数 a 在模 n 下的逆元 a−1 满足：
a×a−1≡1(modn)
逆元存在的充要条件是 gcd(a,n)=1，即 a 和 n 互质。计算模逆元的经典算法是扩展欧几里得算法。
欧拉函数 φ(n) 表示小于等于 n 的正整数中与 n 互质的数的个数。若 n=p⋅q（p、q 为不同素数）：
φ(n)=(p−1)(q−1)
欧拉定理是 RSA 等公钥密码系统的理论基石：
aφ(n)≡1(modn),gcd(a,n)=1
当 n 为素数 p 时，欧拉定理退化为费马小定理：
ap−1≡1(modp)
¶ 中国剩余定理（Chinese Remainder Theorem, CRT）
中国剩余定理指出，给定一组两两互质的模数 n1,n2,…,nk，同余方程组：
x≡a1(modn1)
x≡a2(modn2)
⋮
x≡ak(modnk)
在模 N=n1n2…nk 下有唯一解。CRT 在 RSA 解密加速中发挥重要作用——利用 CRT 可以将 RSA 解密的计算速度提升约 4 倍。
群是抽象代数中描述对称性和变换的核心结构。一个群 (G,⋅) 是集合 G 和二元运算 ⋅ 的组合，满足：
- 封闭性：∀a,b∈G，a⋅b∈G
- 结合律：∀a,b,c∈G，(a⋅b)⋅c=a⋅(b⋅c)
- 单位元：∃e∈G，使得 ∀a∈G，e⋅a=a⋅e=a
- 逆元：∀a∈G，∃a−1∈G，使得 a⋅a−1=a−1⋅a=e
密码学中最重要的群是乘法群 Zn∗（模 n 下与 n 互质的整数构成的乘法群）和椭圆曲线群。
如果一个群 G 的所有元素都可以表示成某个元素 g 的幂：
G={gk∣k∈Z}
则称 G 为循环群，g 为生成元。循环群在 Diffie-Hellman 密钥交换和 ElGamal 加密中处于核心地位。离散对数问题的困难性正是建立在循环群之上：
给定生成元 g 和群元素 h=gx，计算 x（称为离散对数）在精心选择的循环群中是计算上不可行的。
现代密码学的安全性依赖于以下假设：某些数学问题不存在多项式时间的求解算法。
- 大整数分解问题：给定两个大素数 p、q 的乘积 N=p⋅q，求出 p 和 q。RSA 的安全性建立于此。
- 离散对数问题（DLP）：在循环群 G 中，给定 g 和 h=gx，求 x。Diffie-Hellman 和 ElGamal 的安全性建立于此。
- 椭圆曲线离散对数问题（ECDLP）：在椭圆曲线上，给定点 P 和 Q=kP，求 k。ECC 的安全性建立于此。ECDLP 被认为比传统 DLP 更困难——在同等安全强度下，ECC 的密钥长度远小于 RSA。
| 安全性（位） |
RSA 密钥长度 |
ECC 密钥长度 |
对比优势 |
| 80 |
1024 位 |
160 位 |
ECC 短 6 倍 |
| 112 |
2048 位 |
224 位 |
ECC 短 9 倍 |
| 128 |
3072 位 |
256 位 |
ECC 短 12 倍 |
| 256 |
15360 位 |
512 位 |
ECC 短 30 倍 |
对称加密使用同一个密钥完成加密和解密。在公钥密码学出现之前，这是唯一可用的加密方式。
对称密码分为两大类：
流密码（Stream Cipher）：将密钥通过密钥流生成器扩展为无限长的伪随机密钥流，与明文逐位异或：
ci=mi⊕ki
其中 ⊕ 表示按位异或。经典流密码包括 RC4、ChaCha20。流密码的优点是速度快、延迟低，适合实时通信。
分组密码（Block Cipher）：将明文分割为固定长度的块，逐块加密。经典算法包括 AES（块大小 128 位，密钥长度 128/192/256 位）和 SM4（中国国家标准，块大小 128 位，密钥长度 128 位）。
分组密码需要与工作模式配合，才能安全地加密任意长度的消息：
- ECB（电子密码本模式）：每块独立加密。不安全——相同明文块生成相同密文块，泄露模式信息。
- CBC（密码分组链接模式）：每个明文块先与前一个密文块异或再加密。需要初始化向量（IV）。
- CTR（计数器模式）：将计数器值加密后与明文异或，将分组密码转换为流密码。支持并行加密。
- GCM（伽罗瓦计数器模式）：CTR 模式基础上添加认证标签，同时提供加密和完整性验证。ChaCha20-Poly1305 是类似方案。
香农在 1949 年提出了**完善保密性（Perfect Secrecy）**的概念：密文不泄露明文的任何信息。数学上：
P(M∣C)=P(M)
即密文与明文统计独立。**一次性密码本（One-Time Pad）**是唯一达到完善保密性的加密方案：
ci=mi⊕ki,ki 为真随机
但实际限制是：密钥长度必须等于消息长度，且密钥只能使用一次。这使其在实际系统中几乎不可用——这就是为什么我们退而求其次追求计算安全性，而非信息论安全性。
AES 是最广泛使用的对称加密算法，由 Rijndael 算法经 NIST 标准化而来。AES-128 执行 10 轮，每轮包含四个操作：
- SubBytes：字节代换（S-盒非线性变换）
- ShiftRows：行移位（提供扩散）
- MixColumns：列混合（提供扩散）
- AddRoundKey：轮密钥加（与轮密钥异或）
AES 的安全性经过了 20 多年的全球密码学界的检验。目前已知的最佳攻击（Biclique 攻击）的计算复杂度约为 2126.1，仅比暴力穷举快一个常数因子，不影响实际安全性。
公钥密码学是密码学史上的革命性突破。1976 年，Diffie 和 Hellman 发表了《密码学的新方向》，首次提出了公钥密码的概念。
RSA（Rivest-Shamir-Adleman，1977）是应用最广泛的公钥加密算法。
密钥生成：
- 选择两个大素数 p、q
- 计算 n=p⋅q，φ(n)=(p−1)(q−1)
- 选择公钥指数 e，满足 gcd(e,φ(n))=1
- 计算私钥 d≡e−1(modφ(n))
- 公钥：(e,n)；私钥：(d,n)
加密：c=memodn
解密：m=cdmodn
RSA 的正确性由欧拉定理保证：
cd≡(me)d≡me⋅d≡m1+k⋅φ(n)≡m⋅(mφ(n))k≡m(modn)
实际使用中，RSA 还需防御多种攻击：
- 填充方案：直接加密小数值明文容易被低指数攻击。使用 OAEP（最优非对称加密填充）防止。
- 计时攻击：私钥操作的耗时可能泄露位信息。使用常数时间算法。
- 共模攻击：同一 n 下不同 e1、e2 给两个用户，攻击者可用扩展欧几里得算法恢复明文。
Diffie-Hellman（DH）协议允许双方在公开信道上协商共享秘密，是公钥密码学的基础性构造。该协议在 1976 年由 Whitfield Diffie 和 Martin Hellman 提出。
协议过程：
- 双方公开商定一个大素数 p 和生成元 g∈Zp∗
- Alice 选择随机数 a，计算 A=gamodp 并发送给 Bob
- Bob 选择随机数 b，计算 B=gbmodp 并发送给 Alice
- Alice 计算共享密钥 K=Ba=(gb)a=gabmodp
- Bob 计算共享密钥 K=Ab=(ga)b=gabmodp
窃听者只能获取 p、g、A=ga、B=gb。从这些信息计算 gab 需要求解离散对数问题，在精心选择的大素数下是不可行的。
**椭圆曲线 Diffie-Hellman（ECDH）**是 DH 的椭圆曲线版本，使用更短的密钥提供同等安全性，被 TLS 1.3 和现代区块链广泛采用。
椭圆曲线密码学是公钥密码学的重要分支，由 Neal Koblitz 和 Victor Miller 于 1985 年独立提出。
椭圆曲线方程（Weierstrass 标准形式）：
y2=x3+ax+b,4a3+27b2=0
椭圆曲线上的点构成一个阿贝尔群。点加法定义如下：给定曲线上两个点 P=(x1,y1) 和 Q=(x2,y2)，直线 PQ 与曲线的第三个交点关于 x 轴的对称点即为 P+Q。
标量乘法是 ECC 的核心操作：kP=P+P+⋯+P（k 次相加）。从 P 和 kP 求 k 即为椭圆曲线离散对数问题（ECDLP）。
比特币和以太坊使用 secp256k1 曲线：
y2=x3+7
该曲线的参数经过精心选择，确保安全性和计算效率。其密钥生成过程为：
- 随机生成私钥 k（256 位整数）
- 计算公钥 K=k⋅G（G 为生成元基点）
- 对公钥进行哈希得到地址
数字签名满足三个核心需求：认证（确认发送者身份）、完整性（消息未被篡改）、不可否认性（发送者不能否认已签名的消息）。
签名与验证的一般框架：
- 签名：s=Sign(sk,m)，使用私钥 sk 对消息 m 签名
- 验证：Verify(pk,m,s)∈{true,false}，使用公钥 pk 验证签名有效性
**ECDSA（椭圆曲线数字签名算法）**是区块链中最广泛使用的签名方案：
- 对消息 m 计算哈希 h=H(m)
- 选择随机数 k，计算 R=k⋅G=(x1,y1)
- 计算 r=x1modn
- 计算 s=k−1(h+r⋅d)modn（d 为私钥）
- 签名结果为 (r,s)
Schnorr 签名是 ECDSA 的替代方案，近年备受关注。其优势包括：
- 安全性有正式证明：在随机预言机模型下安全
- 签名聚合：多个签名可合并为一个，大大减少多签交易的大小
- 线性性质：支持门限签名，为更复杂的多签方案奠定基础
比特币已通过 Taproot 升级引入 Schnorr 签名。
BLS 签名（Boneh-Lynn-Shacham）利用双线性配对实现更强大的聚合能力：
e(σ,g)=e(H(m),pk)
其中 e 是双线性映射：e(ga,gb)=e(g,g)ab。BLS 签名可以将任意多个签名聚合为一个，大幅提升链上效率。
哈希函数在密码学中扮演着多重角色——它既是数据完整性工具，又是数字签名的基础构件，也是区块链共识算法的核心。
哈希函数 H:{0,1}∗→{0,1}n 将任意长度的二进制串映射为固定长度 n 的摘要值。
- 抗原像性（单向性）：给定 y，找到 x 使得 H(x)=y 在计算上不可行
- 抗第二原像性：给定 x，找到 x′=x 使得 H(x′)=H(x) 在计算上不可行
- 抗碰撞性：找到任意 x=x′ 使得 H(x)=H(x′) 在计算上不可行
生日攻击给出碰撞安全性的下限：由于生日悖论，寻找碰撞只需要尝试 O(2n/2) 次，而非 O(2n)。因此，SHA-256 提供 128 位的碰撞安全性。
SHA-256 使用的 Merkle-Damgård 构造将任意长度消息处理为固定长度哈希：
消息 → [填充（含长度编码）] → [分块 M₁ ‖ M₂ ‖ ... ‖ Mₖ]
↓ ↓ ↓
IV → [压缩函数 f] → [压缩函数 f] → ... → [压缩函数 f] → 最终哈希
SHA-3（Keccak）采用海绵构造，对长度扩展攻击具有天然免疫性。
- 消息认证码（HMAC）：HMAC(K,m)=H((K′⊕opad)∥H((K′⊕ipad)∥m))
- 密钥派生函数（KDF）：从主密钥派生出多个子密钥，如 HKDF
- 承诺方案：c=H(m∥r)，隐藏消息 m 的同时保证事后不可篡改
- Merkle 树：用哈希树结构高效证明元素属于大型集合
零知识证明允许一方（证明者）向另一方（验证者）证明某个命题为真，而不泄露任何超出命题真假本身的信息。这一概念由 Goldwasser、Micali 和 Rackoff 在 1985 年提出。
零知识证明必须满足三个性质：
- 完备性（Completeness）：如果命题为真，诚实的证明者总能说服验证者
- 可靠性（Soundness）：如果命题为假，不诚实的证明者几乎不可能说服验证者
- 零知识性（Zero-Knowledge）：验证者在交互过程中除了命题的真假外，学不到任何其他信息
- 交互式零知识证明：证明者和验证者之间进行多轮交互。如经典的图的 3-着色问题证明。
- 非交互式零知识证明（NIZK）：证明者一次性生成证明，验证者独立验证。通过Fiat-Shamir 转换将交互式协议转为非交互式——将验证者的随机挑战替换为哈希函数输出。
zk-SNARKs（零知识简洁非交互式知识论证）：
- 证明短（通常几百字节）
- 验证快（毫秒级）
- 需要可信设置（Trusted Setup）
- 使用多项式委员会和配对椭圆曲线
zk-STARKs（零知识可扩展透明知识论证）：
- 无需可信设置（透明）
- 证明大（几十到几百 KB）
- 抗量子
- 使用哈希函数和纠错码
Bulletproofs：
- 无需可信设置
- 证明大小随声明复杂度对数增长
- 特别适合范围证明（Range Proof）
从高层面看，零知识证明的构造遵循以下路线：
- 算数电路：将计算问题编码为加法和乘法门的电路
- 多项式约束：将电路满足性转化为多项式方程的可满足性
- 概率检验：验证者通过随机采样多项式上的点来高效验证
具体地，令 t(x) 为目标多项式（在电路的所有约束点上为零），证明者需要证明存在多项式 p(x) 使得：
p(x)=h(x)⋅t(x)
其中 h(x) 是某个商多项式。通过在随机点 s 上求值并检查 p(s)=h(s)⋅t(s)，验证者可以确信约束成立，而无需看到完整的 p(x)。
- 区块链隐私：Zcash 使用 zk-SNARKs 隐藏交易金额和发送方/接收方
- Layer 2 扩展：zk-Rollups 将大量交易打包，仅将零知识证明提交到主链
- 身份验证：证明年龄大于 18 岁而不泄露具体出生日期
- 可验证计算：将计算外包，验证结果的正确性
Shor 算法（1994）证明了量子计算机可以在多项式时间内解决大整数分解和离散对数问题：
O(log3N)
这意味着 RSA、ECC、Diffie-Hellman 等主流公钥密码系统在足够大的量子计算机面前将被彻底攻破。后量子密码学研究的是能抵抗量子攻击的密码系统。
NIST 于 2016 年启动了后量子密码标准化项目，2024 年选定了首批标准算法：
| 类别 |
算法 |
安全基础 |
密钥大小 |
特点 |
| 格密码 |
CRYSTALS-Kyber（KEM） |
带错误学习（LWE） |
中等 |
高效率，主选方案 |
| 格密码 |
CRYSTALS-Dilithium（签名） |
带错误学习（LWE） |
中等 |
快速签名 |
| 签名 |
FALCON |
NTRU 格 |
小 |
紧凑签名 |
| 签名 |
SPHINCS+ |
哈希函数 |
大 |
无陷门，仅依赖哈希安全 |
格密码基于带错误学习问题（Learning With Errors, LWE）：
给定矩阵 A∈Zqm×n 和 b=A⋅s+e（s 为秘密向量，e 为小噪声向量），在计算上难以恢复 s。LWE 问题在最坏情况下与某些格问题的困难性等价，具有扎实的理论基础。
- 比特币和以太坊的 ECDSA 签名将被 Shor 算法攻破
- 现有地址中的资产需要迁移到后量子安全的地址
- 哈希函数受 Grover 算法影响较小（平方加速），增加输出长度即可缓解
- 区块链的不可篡改性依赖哈希函数，量子攻击对 PoW 的影响约为 O(2n/3) 的加速
过渡期采用混合密码方案，结合传统公钥和后量子密钥封装机制。TLS 1.3 已支持混合密钥交换方案：
K=KDF(K传统∥K后量子)
这确保了在后量子算法被攻破之前，安全性至少等价于传统方案的安全性。
安全多方计算允许多个参与方在不泄露各自私有输入的条件下联合计算一个函数。其概念由 Yao 在 1982 年通过百万富翁问题提出：两个百万富翁想知道谁更富有，但都不愿透露自己的具体财产数额。
混淆电路（Garbled Circuits）（Yao 协议）：
- 将计算函数表示为布尔电路
- 对每条线路上的真值表进行加密和置换
- 一方生成混淆电路，另一方在不暴露输入的情况下评估
秘密共享（Secret Sharing）：
- 将秘密 s 拆分为 n 份份额，任意 t 份可以恢复
- Shamir 秘密共享使用多项式插值：
f(x)=s+a1x+a2x2+⋯+at−1xt−1
份额为 f(1),f(2),…,f(n)。任意 t 个点唯一确定 f(x)，从而恢复 s=f(0)。
同态加密（Homomorphic Encryption）：
- 支持在密文上直接进行计算
- 部分同态：仅支持加法（Paillier）或乘法（ElGamal）
- 全同态加密（FHE）：同时支持加法和乘法，由 Gentry 在 2009 年首次实现
全同态加密的构造基于理想格上的噪声。每次乘法运算会放大噪声，当噪声超过阈值时解密失败。Gentry 的突破性贡献是**自举（Bootstrapping）**技术——通过对解密电路的密文评估来"刷新"密文，重置噪声水平，从而支持任意深度的计算：
FHE(m)=Eval(Dec,Enc(sk),Enc(Enc(m)))
- 门限签名：私钥被拆分为多份，需 t 方联合签名
- 密封拍卖：在不泄露各自出价的情况下确定最高价
- 隐私保护机器学习：多个机构在不共享原始数据的情况下联合训练模型
- 区块链钱包：MPC 钱包将私钥分布在多个设备上，消除单点故障
- 自己实现密码算法：这是导致安全漏洞的首要原因。始终使用经过充分审查的标准库。
- ECB 模式：泄露明文模式，已被明文禁止。
- 静态 IV：CBC 和 GCM 模式下 IV 必须每次随机生成，不可重复。
- 不安全的随机数生成器：密码学安全随机数应使用
/dev/urandom 或类似系统调用，而非普通随机数函数。
- 短密钥：RSA 密钥长度低于 2048 位已被视为不安全。
- 填充 Oracle 攻击：对于 CBC 模式的解密，应避免泄露填充错误信息。
- 对称加密：推荐使用 AES-256-GCM 或 ChaCha20-Poly1305（同时提供加密和认证）
- 公钥加密：使用 ECC（Curve25519 或 secp256k1）替代 RSA，或 RSA-OAEP（3072 位以上）
- 密钥交换：使用 X25519 ECDH（Curve25519）
- 哈希：使用 SHA-256 或 SHA-3
- 对称认证：使用 HMAC-SHA256
- 密码哈希：使用 bcrypt、scrypt 或 Argon2（慢哈希，抗暴力破解）
- TLS：使用 TLS 1.3，禁用旧版本和弱密码套件
香农熵 H(X) 衡量随机变量 X 的不确定性：
H(X)=−i=1∑npilog2pi
在密码学中，密钥的熵决定了暴力穷举的难度。一个 128 位密钥的熵为 128 比特，意味着平均需要 2127 次尝试才能猜中。
条件熵表达了在观察到 Y 后 X 剩余的不确定性：
H(X∣Y)=−x,y∑p(x,y)log2p(x∣y)
互信息衡量两个变量之间的依赖程度：
I(X;Y)=H(X)−H(X∣Y)
完善保密性的等价表述为：I(M;C)=0，即密文和明文之间的互信息为零。这是评估密码算法泄漏信息量的理论基础。
**消息认证码（MAC）**保证消息的完整性和真实性。CMAC 和 HMAC 是最常用的构造。GCM 模式则将加密和认证合二为一，在单一操作中同时提供机密性和完整性保障。
VDF 是一类需要固定计算时间才能求值的函数，且验证比求值快得多。VDF 要求：
- 顺序性：即使使用大规模并行计算也无法加速（通过重复平方运算实现）
- 高效验证：验证者可以快速检查结果正确性
VDF 在区块链中用于随机信标和共识协议：构造 (g,T)，计算 y=g2TmodN，其中 T 是延迟参数。由于计算平方操作本质上是串行的，并行计算无法加速。
承诺方案允许一方承诺一个值，事后打开时接收方可以验证该值与承诺一致。同态承诺还支持对承诺值进行代数运算：
如果 c1=Com(m1) 和 c2=Com(m2)，则 c1+c2=Com(m1+m2)。
Pedersen 承诺是典型的同态承诺：
Com(m)=gmhr
其中 r 为随机盲化因子。Pedersen 承诺在离散对数假设下满足计算绑定性和信息理论隐藏性。
密码学是数学、计算机科学和信息理论的交叉学科。从模运算和群论等基本数学工具，到 AES 的分组密码构造，再到 ECC 的椭圆曲线群、零知识证明的多项式协议、安全多方计算的秘密共享方案——每一层都建立在严谨的数学基础之上。
| 密码学分支 |
数学基础 |
典型算法 |
主要应用 |
| 对称加密 |
置换、代换、异或代数 |
AES, ChaCha20 |
数据加密、通信安全 |
| 公钥加密 |
数论（因子分解、离散对数）、椭圆曲线 |
RSA, ECC, ElGamal |
密钥交换、数字签名 |
| 哈希函数 |
压缩函数、海绵构造 |
SHA-256, SHA-3 |
完整性、地址生成、工作量证明 |
| 零知识证明 |
多项式、电路、配对椭圆曲线 |
Groth16, PLONK, STARKs |
隐私保护、可扩展性 |
| 安全多方计算 |
秘密共享、混淆电路、格密码 |
SPDZ, Yao's GC |
门限签名、隐私计算 |
| 后量子密码 |
格、编码、哈希 |
Kyber, Dilithium, SPHINCS+ |
量子安全通信 |
随着量子计算的发展，后量子密码将逐步取代现有的 RSA 和 ECC 体系。同时，全同态加密和零知识证明在性能上的持续突破，正在引领隐私计算和可验证计算的新范式。理解密码学的数学原理，是安全工程师在持续演进的安全格局中保持竞争力的核心能力。