RSA 的基本数学运算为:公钥 ,私钥 ,加密 ,解密 。其中 ,p、q 是两个不同的大素数,,且 。消息代表元满足 。
这里的幂表示数学乘方;在 Python、Go、C 等语言中,^ 通常是按位异或,不能直接当作乘方运算符。
数论基础
- 质数:大于 1,且正因数只有 1 和自身的整数。
- 模运算:求除以正整数 m 后的余数,写作 。
- 同余:a、b 除以 m 的余数相同,记为 。
- 最大公因数:a、b 的最大公因数记为 gcd(a,b)。
- 互质:若 gcd(a,b)=1,则 a、b 互质。多个整数整体互质不等同于两两互质。
- 欧拉函数: 表示 1 到 n 中与 n 互质的整数个数,特别地 。
- 欧拉定理:当 gcd(a,n)=1 时,。
- 模反元素:当 gcd(a,n)=1 且 n>1 时,存在整数 b 满足 ,b 称为 a 模 n 的逆元。
例如,3 模 11 的逆元为 4,因为 。由欧拉定理也可得 是 a 模 n 的一个逆元。
同余相关性质
- 若 、,则 。
- 在同样的条件下,。
- 若 ,则对非负整数 k,有 。
- 若 ,且正整数 n 整除 m,则 。这不意味着
a mod m与a mod n的余数一定相等。
互质相关性质
以下均讨论正整数。
- 两个不同的质数互质。
- 一个数是质数,另一个数不是它的倍数,则两数互质。
- 两个不同的正整数中,较大者为质数时,两数互质。
- 1 与任意正整数互质。
- 2 与任意奇数互质。
- 相邻两个正整数互质。
- 相邻两个正奇数互质。
欧拉函数相关性质
- ,。
- p 为质数时,。
- p 为质数、k 为正整数时,。
- a、b 互质时,;因此 n 为奇数时,。
- 每个大于 1 的正整数都能分解为质数之积。
在 1 到 中,不与 互质的恰好是 p 的倍数,共 个;从总数中去掉它们就得到第三条公式。
算法
- 选择两个不同的大素数 p、q。
- 计算 和 。
- 选择 ,使 gcd(e,ϕ(n))=1。
- 计算 e 模 ϕ(n) 的逆元 d。
- 公钥为 ,私钥包含 d 和 n;实际私钥格式通常还保存 p、q 及 CRT 加速参数。
- 对 ,计算 ,再用 恢复 M。
以上是 RSA 的无填充数学原理。实际加密应通过密码库使用 RSA-OAEP 等标准方案;签名采用 RSA-PSS 等签名方案及其编码规则,不能简单称为“私钥加密摘要、公钥解密”。
大质数生成
随机产生满足位数要求的奇数候选,再采用 Miller–Rabin 等素性检测方法。费马测试可能被卡迈克尔数等合数通过,不能单独据此断定候选是素数。逐个试除到平方根的方法适合小数演示,不适合生成 RSA 使用的大素数。
查找互质数
使用欧几里得算法(辗转相除法)求 gcd;结果为 1 即互质。
计算模反元素
常用扩展欧几里得算法求 ,则 x 模 n 就是逆元。不能随意选取 k 后把 当成逆元,因为它未必是整数。
Python 3.8 及以后可用 pow(a, -1, n) 求逆元;要求 n>1 且 gcd(a,n)=1,否则不存在逆元。
快速幂模算法
将指数不断除以 2,利用平方和乘法减少运算次数。对非负指数 b、正模数 n:
def mod_pow(a, b, n):
if b < 0 or n <= 0:
raise ValueError("require b >= 0 and n > 0")
result = 1 % n
a %= n
while b:
if b & 1:
result = result * a % n
a = a * a % n
b //= 2
return result
也可直接使用 Python 的三参数 pow(a, b, n)。指数为 0 时结果为 1 mod n,不能仅以指数为 1 作为终止情形。
安全性
- 素数生成使用密码学安全随机源。
- 新生成的 RSA 密钥不应再使用 1024 位;按 NIST SP 800-131A Rev.2,签名生成使用的 RSA 模数至少为 2048 位。具体位数还需根据安全强度和保护期限确定。
- 不同密钥不得共享素因子;常用公钥指数为 65537,私钥与填充方案交给成熟密码库生成和处理。
正确性证明
设 p、q 为不同素数,。证明对每个 ,都有 。
先模 p 考察:
- 若 p 整除 M,则 。
- 若 p 不整除 M,由费马小定理 ,于是
同理,。因为 p、q 互质,由中国剩余定理得到
又因为加密后 ,所以 。解密结果和 M 都位于 0 到 n−1 之间,因此两者相等。这个证明也覆盖 M 为 p 或 q 的倍数以及 M=0 的情况。