密码学的数学

关键词#

密码学; 凯撒密码; RSA; 椭圆曲线; 素数; 模运算; 公钥密码; 数论

打破一个常见误解：密码学不是“把字搅乱”#

把密码学想成“算法越复杂越安全”，会漏掉真正起作用的东西。古典密码的失败，很少是因为移位不够花哨，而是因为明文的统计痕迹还在，密钥空间又小得可以穷举。

另一个流行说法是“量子计算机一出现，所有加密都会作废”。这同样过满。肖尔算法打击的是建立在分解与离散对数上的公钥方案；对称密码面对的是格罗弗式的平方根加速，通常加长密钥就能把安全边际找回来。密码学的数学，核心不是制造混乱，而是把安全性写成一个可以公开讨论的假设。

第1页 · 古代密码术#

标题：从凯撒密码到维吉尼亚密码——古典密码的数学

密码学的历史与文字一样古老。凯撒密码（约前50年）是最简单的替换密码——将每个字母移动固定的位数。例如，移动3位：A→D, B→E, ..., X→A, Y→B, Z→C。用数学语言表示：$E(x) = (x + 3) \mod 26$。

凯撒密码很容易被破解——只有25种可能的密钥（不计恒等变换）。频率分析是破解替换密码的基本方法：在英语中，E是最常见的字母——如果密文中某个字母出现的频率最高，它很可能对应E。

这套统计攻击并不是近代才有。9世纪，肯迪（al-Kindī）在《关于破译密码书信的论文》里系统写下了按字母频次还原单表替换的方法。密钥空间可以大到阶乘规模，可一旦每个明文字母始终映到同一个密文字母，语言的不均匀就会在密文里重新出现。

维吉尼亚密码常被标成1586年，但它的多表替换主体更早由贝拉索（Giovan Battista Bellaso）在1553年写出；维吉尼亚本人1586年发表的是一种自动密钥变体。它用一个关键词来加密，不同位置使用不同的移位量，单字母频率分析因此不再直接适用。

它在大约三百年里被称作“不可破解”，直到卡西斯基（Friedrich Kasiski）于1863年发表通用破译法。重复片段的间距会泄露关键词长度，密文随即被拆回若干个凯撒密码。

一次一密：信息论安全与计算安全#

1949年，香农在《保密系统的通信理论》里把“看密文等于什么都没看见”写成了数学。若明文与密文的互信息为零，方案就具有完美保密（perfect secrecy）。一次一密满足这条定义：用与明文等长、真正随机且从不重复的密钥逐位异或，密文对不知道密钥的人来说与均匀随机串不可区分。

香农同时证明了代价。任何完美保密方案的密钥空间都不能小于明文空间，密钥至少要和明文一样长，并且每个密钥只能用一次。你若要保护一条很长的消息，就得先安全送出一条同样长的密钥。密钥分发问题没有消失，只是被放大了。

现代公钥密码整体退到了计算安全：不是证明敌手不可能算出明文，而是假定在给定资源下算出来的代价不可承受。一次一密是定理；RSA、迪菲–赫尔曼和椭圆曲线是赌注。后文所有“安全”，除非另加说明，指的都是第二种。

第2页 · 公钥密码学的革命#

标题：从共享密钥到公钥——密码学的范式转换

1976年11月，迪菲（Whitfield Diffie）和赫尔曼（Martin Hellman）在《IEEE信息论汇刊》发表《密码学的新方向》。在传统的对称密码中，通信双方共享一个密钥，加密和解密使用同一把钥匙。公钥密码学使用两个不同的密钥：公钥用于加密，私钥用于解密。

公钥密码学要解决的是密钥分发：在不安全的信道上建立只有双方知道的共享秘密。迪菲–赫尔曼密钥交换把困难性放在离散对数上——即使窃听者看见 $g^a \bmod p$ 和 $g^b \bmod p$，目前也没有已知的经典高效算法从中恢复 $g^{ab}$。它给出的是密钥协商，还不是可以直接投递密文的公钥加密。

1977年，里维斯特（Rivest）、沙米尔（Shamir）和阿德尔曼（Adleman）给出了RSA；完整论文于1978年2月发表在《美国计算机学会通讯》。RSA是第一个长期仍在使用的实用公钥加密方案。它的安全性被建立在大整数分解显得很困难之上：把两个大素数相乘很容易，把乘积拆回去目前没有已知的经典多项式时间算法。

这里有一层常被说错的地基。密码学需要的不是“某个实例很难”，而是单向函数：正向容易，反向在平均情况下也难。单向函数是否存在，至今仍是信念，不是定理。

若单向函数存在，可以推出 P 不等于 NP（更精确地说，NP 不能含于 BPP）。反过来并不知道：即使将来证明了最坏情况下的分离，也不自动给出平均情况下的单向函数。

整数分解的判定形式属于 NP 与 co-NP 的交集；若它是 NP 完全的，则 NP 等于 co-NP，这被普遍视为极不可能。它因此不是已知的 NP 完全问题，也从未被证明是 NP 完全的。把“分解很难”写成“NP 完全”，是把两套不同的困难性语言焊在一起。

第3页 · RSA的数学原理#

标题：素数的秘密——RSA的工作原理

RSA 把“容易相乘、难分解”焊进一组互逆的模幂。密钥按下面的步骤生成，加密与解密则是同一模数上的两次乘方。

密钥生成：选择两个大素数 $p$ 和 $q$，计算 $n = pq$；选择 $e$ 使得 $\gcd(e, (p-1)(q-1)) = 1$；再计算 $d$ 使得 $ed \equiv 1 \pmod{(p-1)(q-1)}$。公钥是 $(n, e)$，私钥是 $(n, d)$。

加密：$c = m^e \mod n$。解密：$m = c^d \mod n$。

RSA的正确性基于欧拉定理：当 $\gcd(m, n) = 1$ 时，$m^{\phi(n)} \equiv 1 \pmod{n}$（其中 $\phi(n) = (p-1)(q-1)$）。因为 $ed \equiv 1 \pmod{\phi(n)}$，所以 $c^d \equiv m^{ed} \equiv m \pmod{n}$。对与 $n$ 不互素的 $m$，完整论证要走中国剩余定理；随机消息碰到 $p$ 或 $q$ 的概率可忽略，但不等于定义里可以省略这个条件。

RSA的安全性并不等于“分解很难，所以整个系统安全”。给定 $n$，计算 $\phi(n)$ 需要知道 $p$ 和 $q$，而由 $\phi(n)$ 与 $n$ 可以解出因子，所以求出私钥指数 $d$ 与分解 $n$ 在计算上相当。可是“解开一条密文”——求模 $n$ 下的 $e$ 次根——是否等价于分解，仍是开放问题。困难性不会自动从数论问题转移到协议：填充方式、随机数和实现泄漏都可以让数学上站得住的方案在系统里失效。

密钥长度必须按算法族来读，不能按比特数横比。NIST《密钥管理建议》SP 800-57 第1部分第5版（2020）的对照表把 2048 位 RSA 标成约 112 比特安全强度，把 3072 位 RSA 与 256 位椭圆曲线一起标成约 128 比特。

IETF RFC 9325（2022年11月）要求 TLS 服务器侧 RSA 证书模数至少 2048 位。这是互操作底线，不是“2048 已经等于 128 比特安全”。一般数域筛法把分解代价压到亚指数，所以 RSA 的模数必须比对称密钥长出一个数量级。

第4页 · 椭圆曲线密码学#

标题：更短的密钥，相同的安全——椭圆曲线的优势

椭圆曲线是形如 $y^2 = x^3 + ax + b$ 的代数曲线。在有限域 $\mathbb{F}_p$ 上，椭圆曲线上的点构成一个群——点的“加法”有几何定义。1985年，科布利茨（Neal Koblitz）与米勒（Victor Miller）各自提出，把离散对数搬到这条群上。

椭圆曲线密码学（ECC）的安全性基于椭圆曲线离散对数问题（ECDLP）：给定点 $P$ 和 $Q = kP$（$P$ 的 $k$ 次“加法”），求 $k$。有限域上的离散对数可以被指数演算法、数域筛一类亚指数方法削弱；这些方法要用域的乘法和光滑元素，在椭圆曲线的点群里对不上号。

目前对精心选择的曲线，公开的通用攻击仍接近指数级的波拉德 ρ。困难性并不是“从 RSA 搬过来了”，而是同一类“在群里求对数”的问题，换了群运算之后，原来的亚指数武器失效。因此 NIST 2020 年那张表里，256 位 ECC 才被拿来对标 3072 位 RSA。

比特币和以太坊使用 secp256k1 保护交易签名。更短的密钥让 ECC 在移动设备和智能卡上更有用，但曲线参数本身可以成为争议点。

DualECDRBG 是一个用椭圆曲线点对 $(P,Q)$ 生成伪随机比特的标准。若有人知道满足 $Q = eP$ 的秘密 $e$，就可以从输出反推内部状态。2007年，舒莫与弗格森公开指出这条陷门结构；2013年《纽约时报》依据斯诺登披露的文件报道，这份标准中的弱点像是被有意放进去的。NIST 于2014年4月将其从建议中撤回。

必须把两件事分开。Dual_EC 是随机数生成器里一个机制清楚的陷门；NIST P-256 等标准化曲线的种子来源不够透明，这构成合理怀疑，却不等于已经证明曲线本身被装了后门。不透明参数与可验证的“袖中无物”曲线，是两条不同的信任路径。

第5页 · 后量子密码学#

标题：量子计算的威胁——密码学的未来挑战

量子计算对当前的公钥密码学构成了严重威胁。肖尔算法（Shor, 1994，FOCS）可以在多项式时间内分解大整数并计算离散对数。这意味着：一旦出现足够大且可容错的量子计算机，RSA、有限域迪菲–赫尔曼和 ECC 在原理上会被击穿。没有“再加长一点密钥”可以救这三类方案，因为被改写的是问题的复杂度类，不是常数因子。

对称密码不是同一张讣告。格罗弗算法（Grover, 1996）对无结构搜索给出平方根加速，AES-256 的穷举代价从 $2^{256}$ 量级降到约 $2^{128}$ 次量子查询，仍然远超可承受范围。后量子迁移的真实形状是：换掉握手与签名，对称层多半只需改用更长的密钥。把这句话说成“量子杀死全部密码”，是把肖尔的射程写成了整个学科的终点。

后量子密码学研究能在普通计算机上运行、又希望抵抗量子算法的方案。主要方向包括基于格的密码学、基于编码的密码学、基于哈希的签名和基于多变量多项式的密码学。NIST 于2024年8月13日发布首批标准：FIPS 203（ML-KEM，源自 CRYSTALS-Kyber）用于密钥封装，FIPS 204（ML-DSA）与 FIPS 205（SLH-DSA）用于签名。2025年3月11日，NIST 又选定基于编码的 HQC 作为第二套密钥封装方案进入标准化，目的是数学基础的多样性，而不是再贴一张“量子安全”标签。

真正紧迫的是迁移，不是口号。今天的密文可以被先存储、等机器造出来再解；证书链、固件签名和嵌入式设备的更换周期以年计。后量子方案被公开分析的年头也短得多，2022年 SIKE 在经典计算机上被攻破，提醒的是“新困难问题”同样可能在量子出现之前塌掉。因此工程上走的是可替换算法的混合部署，而不是赌某一族格问题永不会被打开。

量子密钥分发（QKD）走另一条路：在特定物理假设下，用不可克隆定理做信息论意义的密钥分发。它不自动解决身份认证，也不能靠软件补丁升级到已有主机。中国于2016年8月发射量子科学实验卫星“墨子号”（QUESS），是空间尺度量子通信实验的一步，不是把互联网上的 RSA 证书整批替换掉的方案。

事实卡#

1. 卡1

   RSA 于1977年提出、1978年发表，其安全性依赖分解在经典计算机上仍然困难——它仍广泛用于证书与签名，但 TLS 1.3 已不再用 RSA 传输会话密钥。

2. 卡2

   按 NIST SP 800-57 第1部分第5版（2020），256 位椭圆曲线与 3072 位 RSA 同被标为约 128 比特安全强度；256 对 2048 不是同一档。

3. 卡3

   肖尔算法（1994）在足够大的量子计算机上会击穿 RSA 与 ECC；格罗弗算法只把对称密钥的有效强度大约减半，AES-256 仍被当作可用。

4. 卡4

   NIST 于2024年8月13日发布 FIPS 203/204/205——后量子首先是证书、协议与设备的迁移问题。

引用#

跨域连接#

• 数论：RSA 的正确性落在欧拉定理与中国剩余定理上——两个指数在模 $\phi(n)$ 的意义下互逆，加密再解密才回到原文。这也划出了参数选择的边界：两个素因子必须足够大且不能太接近，否则模数会被专门的分解方法拆开，而这与“看起来有多少比特”不是一回事。
• 计算复杂性：单向函数是平均情况的困难性，不是最坏情况的 NP 完全。分解属于 NP ∩ co-NP，因此它不是已知的 NP 完全问题；即便将来证明 P 与 NP 分离，也不自动得到可公开验证的单向函数。密码学把安全性放在一条尚未证明的信念上，复杂性理论则提醒这条信念比课堂里的 P 对 NP 更强。
• RSA：能分解就能求出私钥，但能解密一条密文并不自动等于会分解。困难性从数论问题转到方案，必须经过归约，而不能用“问题出名所以协议安全”代替。填充、随机数与侧信道都会在归约之外打开缺口，这也是密钥长度对照表不能单独保证一个实现安全的原因。
• 信息论：一次一密给出互信息为零的完美保密，代价是密钥不短于明文且不可重用。现代公钥体系整体退到计算安全：密文可以泄漏关于明文的信息，只要目前没有可行算法把它提取出来。两种“安全”不是程度差别，而是定义差别。
• 量子计算理论：肖尔算法把分解与离散对数都变成周期问题，于是当前公钥在原理上被击穿；格罗弗算法只平方根地加速穷举，对称层通常加长密钥即可。真正紧迫的是“先截获、后解密”：今天被记录的密文只要将来可解，长期敏感的数据现在就已经暴露，所以迁移不能等机器造出来再开始。

怎样判断一个密码方案是否真的安全#

密码学最容易被误解成“算法足够复杂”。真正的评估至少分四层。第一层是安全目标：究竟要保密、认证身份、保证完整性，还是防止发送者抵赖？不同目标需要不同原语，只有加密并不会自动提供完整性。第二层是威胁模型：攻击者能看到多少密文，能否选择明文、篡改通信、取得设备或观察耗时？不写攻击能力，“无法破解”就没有可检验含义。

第三层是从目标到困难问题的归约链。可靠论证不是“分解很难，所以整个系统安全”，而是说明：若攻击者能在规定模型下破坏方案，就能用它解决哪个公认困难的问题。

第四层是实现与运维。随机数复用、侧信道、证书验证错误和密钥泄露，都能让数学上可靠的方案在系统里失效。因此应把“原语是否可靠”“协议组合是否可靠”“实现是否泄漏”“密钥是否得到治理”分开检查。

这套分层也解释了为什么自创密码通常危险：设计者往往只检查“我看不出规律”，没有给出明确目标、攻击接口与公开分析。密码学的信任不来自秘密算法，而来自定义清楚的问题经受了长期、对抗性的复核。

协议上线后还要保留算法迁移能力；安全参数会老化，真正可靠的系统必须允许更换密钥、算法与证书，而不是把某一代方案永久焊死。后量子迁移把这件事从建议变成了硬约束：不能替换的密码，等于把未来的计算模型写进了今天的风险。

参考文献#

1. 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. Diffie, W. & Hellman, M. (1976). New Directions in Cryptography. IEEE Transactions on Information Theory, 22(6), 644–654.
3. Shannon, C. E. (1949). Communication Theory of Secrecy Systems. Bell System Technical Journal, 28(4), 656–715.
4. Shor, P. W. (1994). Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 124–134.
5. NIST (2020). Recommendation for Key Management, Part 1: General (SP 800-57 Part 1 Rev. 5).
6. NIST (2024). FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard (13 August 2024).
7. Katz, J. & Lindell, Y. (2020). Introduction to Modern Cryptography. 3rd ed. CRC Press.
8. Menezes, A. J., van Oorschot, P. C. & Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.

延伸阅读#

• Koblitz, N. (1994). A Course in Number Theory and Cryptography. 2nd ed. Springer.
• Miller, V. S. (1986). Use of Elliptic Curves in Cryptography. In Advances in Cryptology — CRYPTO '85, Springer, pp. 417–426.
• Grover, L. K. (1996). A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 212–219.
• 陈恭亮. 《信息安全数学基础》. 清华大学出版社, 2004.
• Sheffer, Y., Saint-Andre, P. & Fossati, T. (2022). Recommendations for Secure Use of Transport Layer Security (TLS) and Datagram Transport Layer Security (DTLS). RFC 9325.