Step 7 07. 数论与密码学

<!-- Title: 07. 数论与密码学：守护互联网的基石 --> <!-- ID: 246 --> <!-- Series: 程序员的数学修养 (ID: 16) --> <!-- Author: 潘卫 --> # 数论与密码学：守护互联网的基石 ## 1. 质数 (Prime)：数学的原子 质数是只能被 1 和自身整除的大于 1 的整数（2, 3, 5, 7, 11...）。 它们看起来平平无奇，却是现代密码学的核心。 **算术基本定理**：任何一个大于 1 的整数，都可以唯一地分解为一系列质数的乘积。 例如：$12 = 2 \times 2 \times 3$。 **核心难题**： * 把两个大质数乘起来很容易：$p \times q = N$。 * 但是把 $N$ 分解回 $p$ 和 $q$ 却**极度困难**（当 $N$ 足够大时，如 2048 位）。 这就是 RSA 加密算法安全性的物理基础——**大整数分解难题**。 ## 2. 模运算 (Modular Arithmetic)：钟表上的数学 模运算（取余数，`%`）是程序员最熟悉的运算之一。 $7 \mod 12 = 7$ $15 \mod 12 = 3$ ### 2.1 哈希表 (Hash Table) 我们将无限的数据映射到有限的数组空间中，最简单的方法就是模运算： `index = hash(key) % array_length` 为了减少碰撞，`array_length` 通常取**质数**。 ### 2.2 循环与周期 在生成伪随机数、循环队列（Ring Buffer）中，模运算用于限制数值范围，使其首尾相连。 ## 3. RSA 算法：公钥密码学的奇迹 在 1970 年代之前，密码学是对称的：加密和解密用同一把钥匙。这意味着你必须先把钥匙安全地交给对方（这本身就是个难题）。 RSA 引入了**非对称加密**： * **公钥 (Public Key)**: 可以公开给全世界。用来**加密**。 * **私钥 (Private Key)**: 只有自己知道。用来**解密**。 **比喻**： 我发给你一个打开的挂锁（公钥）。 你把信写好，放进箱子，用挂锁锁上（加密）。 箱子寄给我。 虽然路上谁都能看到箱子，但只有我有钥匙（私钥）能打开它。 **数学原理 (欧拉定理)**： $$m^{\phi(n)} \equiv 1 \pmod n$$ 利用模幂运算的单向性，构建了一个数字陷门。 ## 4. HTTPS 与数字签名 今天的互联网安全（HTTPS）依赖于数论。 1. **身份认证 (数字签名)**：服务器用私钥加密一段摘要，浏览器用公钥解密。如果成功，说明数据确实来自该服务器，且未被篡改。 2. **密钥交换**：利用非对称加密（RSA 或 ECC 椭圆曲线）协商出一个临时的会话密钥。 3. **传输加密**：使用协商好的会话密钥进行对称加密（AES），因为对称加密速度更快。 ## 结语 数论曾被认为是“最纯粹、最无用”的数学分支。 但随着计算机和互联网的诞生，数论摇身一变，成为了保护全球金融、通信和隐私的卫士。 每一笔微信支付，每一次 HTTPS 请求，背后都是质数和模运算在默默守护。