taocp2_rsa_story
RSA公钥加密算法故事文件
确保互联网安全的算法：RSA 解析
5W1H分析
What（是什么）
RSA（Rivest-Shamir-Adleman）是一种非对称公钥加密算法，由Ron Rivest、Adi Shamir和Leonard Adleman于1977年提出。它是目前最广泛使用的公钥密码系统之一，基于大整数分解的数学难题：将两个大素数的乘积分解回原始素数在计算上是不可行的。
Why（为什么）
在RSA之前，密码学主要依赖对称加密，存在密钥分发问题：
- 通信双方必须事先安全地共享密钥
- 密钥数量随用户数量平方增长（n个用户需要n(n-1)/2个密钥）
RSA的革命性在于：
- 公钥可以公开传输，无需保密
- 私钥只需保存在本地
- 解决了密钥分发这一密码学核心难题
Who（谁）
- 发明者: Ron Rivest、Adi Shamir、Leonard Adleman（1977年，MIT）
- 命名: 取三位发明者姓氏首字母
- 理论先驱: Clifford Cocks（1973年，英国GCHQ，保密至1997年）
- 使用者: 互联网安全（HTTPS/TLS）、数字签名、安全邮件等
When（何时）
- 1977年：RSA算法公开发表
- 1983年：获得美国专利（2000年过期）
- 1990年代：成为互联网安全标准
- 至今：仍是公钥加密的主流选择
Where（何地）
- 标准应用: SSL/TLS协议、SSH、PGP/GPG、数字证书
- 硬件实现: 智能卡、安全芯片、硬件安全模块(HSM)
- TAOCP位置: 第2卷第4.5.2节 “Rivest-Shamir-Adleman Method”
How（如何）
RSA的核心数学原理：
密钥生成:
- 选择两个不同的大素数 p 和 q
- 计算 n = p × q（模数）
- 计算 φ(n) = (p-1) × (q-1)（欧拉函数）
- 选择 e 满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1
- 计算 d ≡ e⁻¹ mod φ(n)（扩展欧几里得算法）
- 公钥: (n, e)，私钥: (n, d)
加密: c = mᵉ mod n
解密: m = cᵈ mod n
数学正确性基于欧拉定理：若 gcd(m, n) = 1，则 m^φ(n) ≡ 1 (mod n)
需求定义
功能需求
密钥生成函数
rsa_keygen(p, q, e, *pub, *priv)- 输入：素数p、素数q、公钥指数e
- 输出：公钥结构体、私钥结构体
- 约束：p和q必须是不同的素数，e必须与φ(n)互质
加密函数
rsa_encrypt(m, pub_key)- 输入：明文消息m（整数），公钥
- 输出：密文c
- 约束：m必须小于n
解密函数
rsa_decrypt(c, priv_key)- 输入：密文c，私钥
- 输出：明文m
辅助函数
mod_exp(base, exp, mod): 快速模幂运算（二进制幂）mod_inverse(e, phi): 模逆元计算（扩展欧几里得）
非功能需求
- 安全性: 使用64位整数，支持小素数演示（实际应用需要1024位以上）
- 正确性: 严格验证输入参数（素数检查、边界检查）
- 可移植性: 纯C99实现，无外部依赖
- 教学性: 代码清晰注释，便于理解算法原理
约束条件
- 明文消息 m 必须满足 m < n
- 使用
unsigned long long（64位）进行计算 - 素数选择限制在32位以内（演示目的）
- 实际安全应用需要至少2048位的n
验收标准
功能验收
- 正确生成RSA密钥对（公钥和私钥）
- 加密"HEL"等字节序列后正确解密还原
- 公钥(n,e)可公开，不包含私钥信息
- 使用错误私钥解密失败
- m >= n时正确拒绝并返回错误
- 完整文本消息加密解密流程正确
数学正确性验收
- 验证 e × d ≡ 1 (mod φ(n))
- 验证加密和解密是互逆操作
- 扩展欧几里得算法正确计算模逆元
- 快速模幂运算结果正确
边界测试验收
- 最小素数情况（p=3, q=5）正确工作
- 边界消息值（0, n-1）正确处理
- 非法输入（非素数、相同素数、无效e）正确拒绝
代码质量验收
- 使用C99标准编译无警告（gcc -std=c99 -Wall）
- 包含完整的测试框架
- 代码注释清晰，解释数学原理
- 所有测试通过
安全说明
本实现仅用于教学演示，不适用于实际安全应用：
- 密钥长度: 使用小素数（32位以内），实际RSA需要2048位或更长
- 素数生成: 使用简单试除法，实际应用需要概率素性测试（Miller-Rabin）
- 填充方案: 未实现OAEP等填充，易受攻击
- 侧信道: 未考虑时序攻击等侧信道防护
- 随机数: 未涉及密钥生成所需的真随机数
实际应用请使用OpenSSL、libsodium等经过审计的密码学库。
参考
- TAOCP Volume 2, Section 4.5.2: “Rivest-Shamir-Adleman Method”
- Rivest, R.L., Shamir, A., and Adleman, L. (1978). “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”
- PKCS #1: RSA Cryptography Specifications (RFC 8017)