RSA算法背后的数学原理
1. 引言
RSA算法(RSA algorithm)是一种非对称加密算法, 广泛应用在互联网和电子商务中. 它使用一对密钥进行加密和解密, 分别称为公钥(public key)和私钥(private key). 使用公钥加密的内容只能用私钥解密, 使用私钥加密的内容只能用公钥解密, 并且不能通过公钥在可行的时间内计算出私钥. 这使得加密通信不需要交换私钥, 保证了通信的安全. 那么它是怎么做到这一点的呢? 背后有哪些数学原理? 这篇文章我们来讨论这个问题.
本文会先介绍RSA算法中用到的数论概念和定理: 模算术, 最大公约数与贝祖定理, 线性同余方程, 中国余数定理, 费马小定理; 然后再介绍RSA算法的原理, 并证明其是有效的. 本文会假设你了解数论的基本概念, 如素数, 最大公约数, 互素等.
2. 模算术
2.1 整数除法
我们用一个正整数去除一个整数, 可以得到一个商和一个余数. 形式化定义为:
定理 1 令 a 为整数, d 为正整数, 则存在唯一的整数 q 和 r, 满足
当
整除有以下基本性质:
定理 2 令 a, b, c 为整数, 其中
2.2 模算术
在数论中我们特别关心一个整数被一个正整数除时的余数. 我们用
定义 1 如果 a 和 b 是整数而 m 是正整数, 则当 m 整除 a - b 时称 a 模 m 同余 b. 记作
模算术有下列性质:
定理 3 如果 m 是正整数, a, b 是整数, 则有
根据定理3, 可得以下推论
推论 1 设 m 是正整数, a, b, c 是整数; 如果
证明
需要注意的是, 推论1反之不成立. 来看推论2:
推论 2 设 m 是正整数, a, b 是整数, c 是不能被 m 整除的整数; 如果
证明
3. 最大公约数
如果一个整数 d 能够整除另一个整数 a, 则称 d 是 a 的一个约数(divisor); 如果 d 既能整除 a 又能整除 b, 则称 d 是 a 和 b 的一个公约数(common divisor). 能整除两个整数的最大整数称为这两个整数的最大公约数(greatest common divisor).
定义 2 令 a 和 b 是不全为零的两个整数, 能使
3.1 求最大公约数
如何求两个已知整数的最大公约数呢? 这里我们讨论一个高效的求最大公约数的算法, 称为辗转相除法. 因为这个算法是欧几里得发明的, 所以也称为欧几里得算法. 辗转相除法基于以下定理:
引理 1 令
证明 我们假设 d 是 a 和 b 的公约数, 即
类似地, 假设 d 是 b 和 r 的公约数, 即
因此, a 与 b 和 b 与 r 拥有相同的公约数. 所以
辗转相除法就是利用引理1, 把大数转换成小数. 例如, 求
我们有
有
因为 7 整除 14, 所以
我们可以很快写出辗转相除法的代码:
1 |
|
3.2 贝祖定理
现在我们讨论最大公约数的一个重要性质:
定理 4 贝祖定理 如果整数 a, b 不全为零, 则
证明 令
又
同理, 用
设 a 和 b 的最大公约数是 d, 那么
我们可以对辗转相除法稍作修改, 让它在计算出最大公约数的同时计算出贝祖系数.
1 |
|
4. 线性同余方程
现在我们来讨论求解形如
定理 5 如果 a 和 m 为互素的整数且
证明 由贝祖定理可知,
这蕴含着
这样我们就可以调用辗转相除法 gcd(a, m)
求得 a 模 m 的逆.
a 模 m 的逆也被称为 a 在模m乘法群
中的逆元. 这里我并不想引入群论, 有兴趣的同学可参阅算法导论
求得了 a 模 m 的逆
把
例 1 求线性同余方程
解 调用 gcd(34, 89)
, 得
5. 中国余数定理
中国南北朝时期数学著作 孙子算经 中提出了这样一个问题:
有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?
用现代的数学语言表述就是: 下列同余方程组的解释多少?
孙子算经 中首次提到了同余方程组问题及其具体解法. 因此中国剩余定理称为孙子定理.
定理 6 中国余数定理 令
有唯一的模
证明 我们使用构造证明法, 构造出这个方程组的解. 首先对于
即,
上式等号两边同时乘
就是第 i 个方程的一个解; 那么怎么构造出方程组的解呢? 我们注意到, 根据
就是方程组的解.
有了这个结论, 我们可以解答 孙子算经 中的问题了: 对方程组的每个方程, 求出 gcd(M_i, m_i)
求出
最后求出
6. 费马小定理
现在我们来看数论中另外一个重要的定理, 费马小定理(Fermat’s little theorem)
定理 7 费马小定理 如果 a 是一个整数, p 是一个素数, 那么
特别地, 当 a 不是 p 的倍数时, 有
证明 假设 n 是整数, p 是素数, 考虑组合数
当 n 不为 p 或 0 时, 由于分子有质数p, 但分母不含p; 故分子的p能保留, 不被约分而除去. 即
令 b 为任意整数, 根据二项式定理, 我们有
对上式模 p, 可得同余式
通过不断地令
依次代入, 得
令
当 p 不整除 a 时, 根据推论 2, 有
7. RSA算法
我们终于可以来看 RSA 算法了. 先来看 RSA 算法是怎么运作的:
RSA 算法按照以下过程创建公钥和私钥: 1. 随机选取两个大素数 p 和 q,
要把明文
要把密文
下面证明 RSA 算法是有效的:
证明 要证明 RSA 加密算法的有效性, 我们只需要证明
这蕴含着存在整数 k, 使得
如果
如果
类似地, 对于所有的
由于 p, q 都是素数, 所以
所以 RSA 加密算法是有效的.
(1) 式表明, 不仅可以用公钥加密, 私钥解密, 还可以用私钥加密, 公钥解密. 即加密计算
RSA 算法的安全性基于大整数的质因数分解的困难性. 由于目前没有能在多项式时间内对整数作质因数分解的算法, 因此无法在可行的时间内把 n 分解成 p 和 q 的乘积. 因此就无法求得 e 模
8. 总结
RSA 算法是一个能体现数学之美的算法. 因为有 RSA 这样的非对称加密算法, 我们的互联网才变得安全, 电子商务, 移动支付, 网银等才得以存在. 在这些的背后都是数学家和计算机科学家的研究成果. 本文主要讨论的是 RSA 算法背后的数学原理而不是其实现, 因此, 限于篇幅, 像模取幂, 寻找大素数, 大整数运算之类的算法未予讨论. 感兴趣的同学可参阅参考资料中的文献.
参考资料 - 离散数学及其应用(原书第7版), 机械工程出版社 - 算法导论第三版, 机械工业出版社 - 费马小定理