4.2 数论与密码：素数的金库

4.2 数论与密码：素数的金库

本节摘要：数论研究整除、同余与素数，曾被认为是最"无用"的纯数学，如今却是全球公钥体系的金库。本节从欧几里得算法与同余讲起，经中国剩余定理与欧拉定理，完整实现一遍小素数版 RSA，说明其安全性完全押在"大整数分解没有快速算法"上，最后看椭圆曲线密码与后量子密码如何接棒。

"无用"学科的世纪翻盘

哈代在《一个数学家的辩白》里颇为自豪地写道，数论是无用而纯洁的数学。他去世不到三十年，RSA 加密开始守护银行转账。命运的转折点是一个洞见："容易正向、极难反向"的数学操作可以当锁用。乘两个大素数是毫秒级的事，把乘积分解回去，用已知最好的算法在千亿位量级上需要宇宙年龄的算力。这种不对称性，加上欧拉定理这块数学齿轮，就拼成了公钥密码。

先备齐齿轮。欧几里得算法求最大公约数，其扩展版本顺便给出模逆元（第 2 章已用过）：

def ext_gcd(a, b):
    # 扩展欧几里得：返回 (g, x, y) 使 a*x + b*y = g = gcd(a, b)
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

g, x, _ = ext_gcd(240, 46)
print(g, x)              # 2, -9：240*(-9) + 46*47 = 2
# 模逆元：a 模 m 的逆 = ext_gcd(a, m) 的 x 对 m 取余（要求 gcd 为 1）
_, inv, _ = ext_gcd(7, 26)
print(inv % 26)          # 15：7*15 = 105 = 4*26 + 1 ≡ 1 (mod 26)
​

欧拉定理是 RSA 的主齿轮：若 n 与 a 互素，则 a 的欧拉函数次幂模 n 余一。欧拉函数统计小于 n 且与 n 互素的个数；当 n 是两个素数 p、q 的乘积时，欧拉函数等于 (p-1)(q-1)——这个值只有知道分解的人才能快速算出，锁芯正在这里。

from sympy import totient, isprime

print(totient(35))   # 24 = (5-1)*(7-1)，因为 35 = 5*7
# 验证欧拉定理：a^totient(n) ≡ 1 (mod n)
print(pow(4, totient(35), 35))   # 输出 1
# pow 的第三参数是快速模幂：平方-取模策略，指数按二进制位处理，多项式时间
​

手工拼装一台 RSA

完整流程五步：选两个素数 p、q；算 n 等于 pq 与欧拉函数；选加密指数 e（常取 65537）；算 d 为 e 模欧拉函数的逆；公开 (n, e)，私藏 d。加密是模幂 c 等于 m 的 e 次幂模 n，解密是 c 的 d 次幂模 n——正确性由欧拉定理保证（ed 是欧拉函数的倍数加一，模幂回到原点）。小素数全流程：

from sympy import nextprime

# 密钥生成（教学用小参数；真实参数是 2048 位以上）
p, q = nextprime(101), nextprime(197)        # p=101, q=199
n = p * q                                     # n = 20099，公开
phi = (p - 1) * (q - 1)                       # 只有知道分解才能快速算出
e = 65537                                     # 与 phi 互素的标准选择
_, d, _ = ext_gcd(e, phi)
d %= phi                                      # 私钥 d：e*d ≡ 1 (mod phi)

message = 1234
cipher = pow(message, e, n)
print(cipher)                                 # 密文
recovered = pow(cipher, d, n)
print(recovered, recovered == message)        # 1234 True：解密还原明文
# 攻击者视角：拿到 (n, e) 后必须分解 n 才能得到 phi 与 d——难度即安全性的全部来源
​

签名是同一台机器反向用：用私钥对消息摘要做模幂，任何人用公钥验证。加密与签名共用一套齿轮，这是 RSA 设计的经济性所在。

RSA 的锁与钥匙：数学依赖链

素数的分布与找法

素数有无穷多（第 1 章反证法样本），但它们在数轴上的密度按"数的对数分之一"衰减（素数定理，复分析方法证明，第 3 章留的伏笔在此兑现）。工程上找大素数不靠逐个试除：先随机取奇数，再用米勒—拉宾概率性素性测试快速筛掉绝大多数合数——注意这是概率算法，"可能漏判"换来速度，属于第 5 章随机算法的预告。

import random

def miller_rabin_round(n, a):
    # 单轮米勒-拉宾：n-1 = 2^s * d，检验 a^d 或其平方链是否出现 1 或 n-1
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2; s += 1
    x = pow(a, d, n)
    if x in (1, n - 1):
        return True
    for _ in range(s - 1):
        x = x * x % n
        if x == n - 1:
            return True
    return False

def is_probable_prime(n, rounds=20):
    return all(miller_rabin_round(n, random.randrange(2, n - 1))
               for _ in range(rounds))

print(is_probable_prime(2**127 - 1))    # True：梅森素数，欧拉时代的手工极限
print(is_probable_prime(2**128 + 1))    # False
​

接棒者：椭圆曲线与后量子

RSA 的密钥长度增长快（同等安全强度需 3072 位对比椭圆曲线 256 位），业界已大量迁移到椭圆曲线密码（ECC）：把点加法定义在曲线模素数的解集上，构成一个有限群（第 2 章的抽象结构在此上岗），难题从"分解"换成"离散对数"。量子计算是两者的共同威胁：Shor 算法在足够大的量子计算机上多项式时间解决分解与离散对数，后量子密码（格密码等）的标准化迁移已在进行——密码学是数学与算力的军备竞赛，每代锁都住在这代数学的难题上。

⚠️ 实现层警告：教科书 RSA 是确定性的，相同明文得相同密文，且对低指数攻击等毫无抵抗力；真实系统必须加入随机填充方案。密码工程的第一原则是"永远不要自己发明密码协议"。

本节要点回顾

• "正向易、反向难"的不对称性是公钥密码的锁芯，哈代的"无用数论"完成世纪翻盘；
• RSA 五步流程的数学齿轮是欧拉定理与扩展欧几里得算法，正确性一行模幂验证；
• 素性测试是概率算法，米勒—拉宾用"可能漏判"换速度，大素数生成工程可行；
• 椭圆曲线密码换用离散对数难题，同等安全下密钥短一个数量级；
• 量子威胁与后量子迁移提醒我们：密码安全性有保质期，数学与算力在赛跑。

秘密的世界告一段落，下一节转向不确定性本身：概率如何被公理化，运气如何被计算。