跳转到内容
← 返回深度阅读
应用约 10 分钟阅读

密码学的数学

应用密码学数论RSA椭圆曲线

关键词

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

第1页 · 古代密码术

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

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

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

维吉尼亚密码（1586年）使用一个关键词来加密——不同的位置使用不同的移位量。这使得频率分析不再直接适用。维吉尼亚密码在300年间被认为是"不可破解的"——直到卡西斯基（Friedrich Kasiski，1863）发现了破解方法。

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

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

1976年，迪菲（Whitfield Diffie）和赫尔曼（Martin Hellman）提出了公钥密码学的概念——这是密码学史上最深刻的革命。在传统的对称密码中，通信双方共享一个密钥——加密和解密使用同一个密钥。公钥密码学使用两个不同的密钥：公钥用于加密，私钥用于解密。

公钥密码学解决了密钥分发问题：在不安全的信道上建立共享密钥。迪菲-赫尔曼密钥交换协议使用离散对数问题的困难性——即使窃听者知道公钥，也无法推导出私钥。

1977年，里维斯特（Rivest）、沙米尔（Shamir）和阿德尔曼（Adleman）发明了RSA密码系统——第一个实用的公钥密码系统。RSA的安全性基于大整数分解的困难性：将两个大素数相乘很容易，但将一个大整数分解为素因子非常困难。

第3页 · RSA的数学原理

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

RSA的工作原理如下：

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

加密：c=memod  nc = m^e \mod n。解密：m=cdmod  nm = c^d \mod n。

RSA的正确性基于欧拉定理：mϕ(n)≡1(modn)m^{\phi(n)} \equiv 1 \pmod{n}（其中 ϕ(n)=(p−1)(q−1)\phi(n) = (p-1)(q-1)）。因为 ed≡1(modϕ(n))ed \equiv 1 \pmod{\phi(n)}，所以 cd≡med≡m(modn)c^d \equiv m^{ed} \equiv m \pmod{n}。

RSA的安全性基于：给定 $n$，计算 ϕ(n)\phi(n) 需要知道 $p$ 和 $q$——而这需要分解 $n$。对于2048位的RSA密钥（$n$ 约600位十进制数），目前的算法无法在合理时间内分解。

第4页 · 椭圆曲线密码学

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

椭圆曲线是形如 y2=x3+ax+by^2 = x^3 + ax + b 的代数曲线。在有限域 Fp\mathbb{F}_p 上，椭圆曲线上的点构成一个群——点的"加法"有几何定义。

椭圆曲线密码学（ECC）的安全性基于椭圆曲线离散对数问题（ECDLP）的困难性：给定点 $P$ 和 $Q = kP$（$P$ 的 $k$ 次"加法"），求 $k$。对于精心选择的椭圆曲线，ECDLP比整数分解和离散对数更困难——因此ECC可以在更短的密钥长度下提供相同的安全级别。

256位的ECC密钥提供的安全性相当于3072位的RSA密钥。这使得ECC在移动设备、物联网和智能卡等资源受限的环境中特别有用。比特币和以太坊都使用椭圆曲线密码学（secp256k1曲线）来保护交易。

第5页 · 后量子密码学

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

量子计算对当前的公钥密码学构成了严重威胁。肖尔算法（Shor's Algorithm，1994）可以在多项式时间内分解大整数和计算离散对数——这意味着RSA和ECC在量子计算机面前将不再安全。

后量子密码学研究能够抵抗量子计算攻击的密码系统。主要的方向包括：基于格的密码学（如CRYSTALS-Kyber）、基于编码的密码学、基于哈希的签名和基于多变量多项式的密码学。美国国家标准与技术研究所（NIST）在2024年正式发布了首批后量子密码标准。

量子密钥分发（QKD）利用量子力学的原理（如不可克隆定理）来实现信息论安全的密钥分发——即使窃听者拥有无限的计算能力也无法破解。中国在2016年发射了量子通信卫星"墨子号"——这是量子通信走向实用的重要一步。

事实卡

  • 卡1：RSA密码系统（1977）基于大整数分解的困难性——至今仍是互联网安全的基础。
  • 卡2：256位椭圆曲线密钥的安全性相当于3072位RSA密钥——ECC更高效。
  • 卡3：肖尔算法（1994）可以在量子计算机上分解大整数——RSA和ECC将不再安全。
  • 卡4：NIST在2024年发布了首批后量子密码标准——为量子时代做准备。

引用

"密码学是数学在现实世界中最直接的应用之一。" — 布鲁斯·施奈尔

"隐私不是因为有东西要隐藏，而是因为有权利保护。" — 爱德华·斯诺登

跨域连接

  • 数论：RSA 的正确性完全落在欧拉定理上——两个指数在模欧拉函数的意义下互逆，加密再解密才恰好回到原文。这也划出了参数选择的边界：两个素因子必须足够大且不能太接近，否则模数会被专门的分解方法拆开，而这与密钥的位数无关。
  • 加密基础：信息论意义上的完美保密要求密钥不短于明文且不可重用，代价是密钥分发的难度与通信量同级。现代密码整体退到了计算安全：不是敌手不可能破解，而是破解代价被假定不可承受。安全性因此依赖一个尚未被证明的困难性假设。
  • 量子计算理论：肖尔算法把分解与离散对数都归约成周期问题，于是当前的公钥体系在原理上被击穿。真正紧迫的是"先截获、后解密"：今天被记录的密文只要将来某天可解，长期敏感的数据现在就已经泄露，所以迁移不能等机器造出来再开始。
  • 基因检测与隐私：基因数据是这种威胁的最坏情形——密码泄露可以更换，基因序列不能，而且它同时暴露了亲属的信息。推论是这类数据的保护期必须按几十年计，只用当下够强的算法保护它，等价于把风险推给未来。
  • 人工智能治理与监控：要求加密留后门的政策困境在于，后门是一处结构性弱点而非一把只给特定人的钥匙：它对谁都开放，只取决于谁先找到。因此"只给执法机关的例外通道"在技术上不成立，争论的真实内容是要不要整体降低所有人的安全水位。

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

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

第三层是从目标到困难问题的归约链。可靠论证不是“分解很难，所以整个系统安全”，而是说明：若攻击者能在规定模型下破坏方案，就能用它解决哪个公认困难的问题。第四层是实现与运维。随机数复用、侧信道、证书验证错误和密钥泄露，都能让数学上可靠的方案在系统里失效。因此应把“原语是否可靠”“协议组合是否可靠”“实现是否泄漏”“密钥是否得到治理”分开检查。

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

协议上线后还要保留算法迁移能力；安全参数会老化，真正可靠的系统必须允许更换密钥、算法与证书，而不是把某一代方案永久焊死。

参考文献

  1. Rivest, Ron, Adi Shamir & Leonard Adleman. "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems." 1977.
  2. Diffie, Whitfield & Martin Hellman. "New Directions in Cryptography." 1976.
  3. Shor, Peter. "Algorithms for Quantum Computation." 1994.
  4. Koblitz, Neal. A Course in Number Theory and Cryptography. Springer, 1994.
  5. 陈恭亮. 《信息安全数学基础》. 清华大学出版社, 2004.
  6. Katz, Jonathan & Yehuda Lindell. Introduction to Modern Cryptography. CRC Press, 3rd ed., 2020.