大整数分解问题与RSA算法

现代密码学的数学基础

大整数分解问题

问题定义：
给定一个合数 ，找到它的素数分解：

示例：

复杂度分类

Factoring ∈ NP

• 可以在多项式时间内验证一个分解是否正确
• 给定 和可能的因子 ，验证 是简单的

Factoring ∉ P (经典计算机)

• 没有已知的多项式时间算法
• 最佳经典算法：数域筛选法 (NFS)，时间复杂度：
  其中

复杂度分类（续）

Factoring ∉ NP-complete

• 如果大整数分解是NP完全的，则NP = co-NP
• 目前没有证据表明NP = co-NP
• 因此，大整数分解问题不属于NP完全问题

Factoring ∈ BQP

• 量子计算机上存在多项式时间算法
• Shor算法 (1994)：时间复杂度
• 对现有公钥密码系统构成威胁

RSA算法基础

Ron Rivest, Adi Shamir, Leonard Adleman (1977)

密钥生成：

1. 选择两个大素数 和
2. 计算 ，
3. 选择 使得 ，
4. 计算 使得

公钥:
私钥:

RSA加密与解密

加密：

对于明文 （）：

解密：

数学原理：

基于欧拉定理：

RSA的安全性基础

核心假设： RSA问题是困难的

给定：

• 公钥
• 密文

恢复明文 需要：

1. 计算 次方根模 （等价于大整数分解）
2. 或者直接分解 得到 和

等价的困难问题：

• 大整数分解问题
• RSA问题：求 次方根模合数

RSA正确性证明：

单向陷门函数——密码学算法的必须要求

一个单向陷门函数需要三个特性：

1. 正向计算容易：给定输入 x，计算 f(x) 是容易的。（在 RSA 中，f(x) 就是“用公钥加密”或“将两个质数相乘”）
2. 反向求逆困难：在没有额外信息的情况下，给定 f(x) 的值，想求出 x 是困难的。（在 RSA 中，就是“给定乘积 N，求其质因数 p 和 q”）
3. 反向求逆容易（当有陷门时）：如果拥有一个特殊的“陷门”信息，那么从 f(x) 计算 x 就变得容易。（在 RSA 中，“陷门”就是其中一个质因数，或者与欧拉函数相关的私钥）

量子计算的威胁：Shor算法

Peter Shor (1994)

算法步骤：

1. 经典部分：将分解问题转化为求阶问题
2. 量子部分：用量子傅里叶变换(QFT)快速求解

时间复杂度：

影响： 一旦大规模量子计算机实现，现有RSA系统将被破解

现状与未来

当前状况：

• RSA-2048：需要数千年经典计算时间
• 量子计算机：目前只能分解很小的数（如21=3×7）
• 抗量子密码学：正在发展中

建议：

• 短期：继续使用RSA（2048位以上）
• 长期：迁移到抗量子算法（如基于格的密码）

谢谢！

问题与讨论