RSA 算法

星期日, 8月 4, 2024 | 6分钟阅读 | 更新于 星期日, 9月 1, 2024

@

RSA 的基本数学运算为:公钥 (e,n)(e,n),私钥 (d,n)(d,n),加密 C=Me mod nC=M^e\bmod n,解密 M=Cd mod nM=C^d\bmod n。其中 n=pqn=pq,p、q 是两个不同的大素数,φ(n)=(p−1)(q−1)\varphi(n)=(p-1)(q-1),且 ed≡1(modφ(n))ed\equiv1\pmod{\varphi(n)}。消息代表元满足 0≤M<n0\le M<n。

这里的幂表示数学乘方;在 Python、Go、C 等语言中,^ 通常是按位异或,不能直接当作乘方运算符。

数论基础

  1. 质数:大于 1,且正因数只有 1 和自身的整数。
  2. 模运算:求除以正整数 m 后的余数,写作 a mod ma\bmod m。
  3. 同余:a、b 除以 m 的余数相同,记为 a≡b(modm)a\equiv b\pmod m。
  4. 最大公因数:a、b 的最大公因数记为 gcd(a,b)。
  5. 互质:若 gcd(a,b)=1,则 a、b 互质。多个整数整体互质不等同于两两互质。
  6. 欧拉函数:φ(n)\varphi(n) 表示 1 到 n 中与 n 互质的整数个数,特别地 φ(1)=1\varphi(1)=1。
  7. 欧拉定理:当 gcd(a,n)=1 时,aφ(n)≡1(modn)a^{\varphi(n)}\equiv1\pmod n。
  8. 模反元素:当 gcd(a,n)=1 且 n>1 时,存在整数 b 满足 ab≡1(modn)ab\equiv1\pmod n,b 称为 a 模 n 的逆元。

例如,3 模 11 的逆元为 4,因为 3×4=12≡1(mod11)3\times4=12\equiv1\pmod{11}。由欧拉定理也可得 aφ(n)−1a^{\varphi(n)-1} 是 a 模 n 的一个逆元。

同余相关性质

  1. 若 a≡b(modm)a\equiv b\pmod m、c≡d(modm)c\equiv d\pmod m,则 a±c≡b±d(modm)a\pm c\equiv b\pm d\pmod m。
  2. 在同样的条件下,ac≡bd(modm)ac\equiv bd\pmod m。
  3. 若 a≡b(modm)a\equiv b\pmod m,则对非负整数 k,有 ak≡bk(modm)a^k\equiv b^k\pmod m。
  4. 若 a≡b(modm)a\equiv b\pmod m,且正整数 n 整除 m,则 a≡b(modn)a\equiv b\pmod n。这不意味着 a mod m 与 a mod n 的余数一定相等。

互质相关性质

以下均讨论正整数。

  1. 两个不同的质数互质。
  2. 一个数是质数,另一个数不是它的倍数,则两数互质。
  3. 两个不同的正整数中,较大者为质数时,两数互质。
  4. 1 与任意正整数互质。
  5. 2 与任意奇数互质。
  6. 相邻两个正整数互质。
  7. 相邻两个正奇数互质。

欧拉函数相关性质

  1. φ(1)=1\varphi(1)=1,φ(2)=1\varphi(2)=1。
  2. p 为质数时,φ(p)=p−1\varphi(p)=p-1。
  3. p 为质数、k 为正整数时,φ(pk)=pk−pk−1\varphi(p^k)=p^k-p^{k-1}。
  4. a、b 互质时,φ(ab)=φ(a)φ(b)\varphi(ab)=\varphi(a)\varphi(b);因此 n 为奇数时,φ(2n)=φ(n)\varphi(2n)=\varphi(n)。
  5. 每个大于 1 的正整数都能分解为质数之积。

在 1 到 pkp^k 中,不与 pkp^k 互质的恰好是 p 的倍数,共 pk−1p^{k-1} 个;从总数中去掉它们就得到第三条公式。

算法

  1. 选择两个不同的大素数 p、q。
  2. 计算 n=pqn=pq 和 φ(n)=(p−1)(q−1)\varphi(n)=(p-1)(q-1)。
  3. 选择 1<e<φ(n)1<e<\varphi(n),使 gcd(e,ϕ(n))=1。
  4. 计算 e 模 ϕ(n) 的逆元 d。
  5. 公钥为 (e,n)(e,n),私钥包含 d 和 n;实际私钥格式通常还保存 p、q 及 CRT 加速参数。
  6. 对 0≤M<n0\le M<n,计算 C=Me mod nC=M^e\bmod n,再用 Cd mod nC^d\bmod n 恢复 M。

以上是 RSA 的无填充数学原理。实际加密应通过密码库使用 RSA-OAEP 等标准方案;签名采用 RSA-PSS 等签名方案及其编码规则,不能简单称为“私钥加密摘要、公钥解密”。

大质数生成

随机产生满足位数要求的奇数候选,再采用 Miller–Rabin 等素性检测方法。费马测试可能被卡迈克尔数等合数通过,不能单独据此断定候选是素数。逐个试除到平方根的方法适合小数演示,不适合生成 RSA 使用的大素数。

查找互质数

使用欧几里得算法(辗转相除法)求 gcd;结果为 1 即互质。

计算模反元素

常用扩展欧几里得算法求 ax+ny=1ax+ny=1,则 x 模 n 就是逆元。不能随意选取 k 后把 (kn+1)/a(kn+1)/a 当成逆元,因为它未必是整数。

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 作为终止情形。

安全性

  1. 素数生成使用密码学安全随机源。
  2. 新生成的 RSA 密钥不应再使用 1024 位;按 NIST SP 800-131A Rev.2,签名生成使用的 RSA 模数至少为 2048 位。具体位数还需根据安全强度和保护期限确定。
  3. 不同密钥不得共享素因子;常用公钥指数为 65537,私钥与填充方案交给成熟密码库生成和处理。

正确性证明

设 p、q 为不同素数,ed=1+k(p−1)(q−1)ed=1+k(p-1)(q-1)。证明对每个 0≤M<pq0\le M<pq,都有 Med≡M(modpq)M^{ed}\equiv M\pmod{pq}。

先模 p 考察:

  • 若 p 整除 M,则 Med≡0≡M(modp)M^{ed}\equiv0\equiv M\pmod p。
  • 若 p 不整除 M,由费马小定理 Mp−1≡1(modp)M^{p-1}\equiv1\pmod p,于是
Med=M1+k(p−1)(q−1)≡M(Mp−1)k(q−1)≡M(modp). M^{ed}=M^{1+k(p-1)(q-1)} \equiv M\left(M^{p-1}\right)^{k(q-1)} \equiv M\pmod p.

同理,Med≡M(modq)M^{ed}\equiv M\pmod q。因为 p、q 互质,由中国剩余定理得到

Med≡M(modpq). M^{ed}\equiv M\pmod{pq}.

又因为加密后 C≡Me(modn)C\equiv M^e\pmod n,所以 Cd≡Med≡M(modn)C^d\equiv M^{ed}\equiv M\pmod n。解密结果和 M 都位于 0 到 n−1 之间,因此两者相等。这个证明也覆盖 M 为 p 或 q 的倍数以及 M=0 的情况。

参考

© 2026 我的博客

🌱 Powered by Hugo with theme Dream.

关于这个博客

关于博客

记录软件开发过程的一些知识和技巧,提升自我

关于博主

除了才华一无所有~~ 薪尽自然凉~~ 强迫症患者~~ 热爱古风~~