Binfo

RSA 算法--粗略数学推导

之前一篇我们介绍完 RSA 算法的基本原理了，了解了 RSA 算法的加密锁就是先幂后模的运算。这个锁的特点是正向运算很容易，也就是加密过程很容易，但是解密过程很难，也就是要直接反向运算是不可能的。而要想让反向运算成为可能，就要在先幂后模运算的各项参数上做文章，让各项参数之间通过整数分解问题建立关系，这样只要我们把握住这种关系，那么反向运算就变得容易了。所以本节就来深入到整数分解问题，看看如何来构建先幂后模中的各项参数之间的关系，进而引申出如何生成公钥和私钥。

提出问题

下面我们把要解决的问题进一步明确一下，抽象成具体的数学任务。先幂后模函数的正向运算，从信息 m 获得密文 c 是简单的，而反向运算，从 c 运算获得 m 是很难的。但是如果我们能够合理的构建 e 和 N 之间的关系，同时把握体现 e 和 N 之间关系的关键信息，这个反向运算将不再困难。

实际上，我们总能找到一个合适的 d ，使得 c 的 d 次方对 N 求模的结果就是 m 。所以问题进一步的就是要构建 e , d 以及 N 的数学联系。显然，这种联系要保证根据 e 和 N 是很难算出 d 来的。

实际上我们要做到的是，给定两个大素数 p1 和 p2 ，让 p1p2 = N ，由 e 容易算出 d 的前提是我们知道 p1p2 ，也就是是知道 N 的整数分解的结果。而如果不知道 ，那么根据 e 和 N 算出 d 的难度就相当于对两个大素数的乘积做反向分解，这个是很难的。说明一下，“很难”在这里的意思就是没有有效的求解方法，只能靠暴力搜索去解决。

好，看到这里，我们要解决的问题就描述清楚了，怎么解决呢？来继续看下面的数学推导。

解决步骤

问题的关键就是使用欧拉函数。

在 RSA 这里，欧拉函数的本来目的不重要，重要的是要使用的是它的一个属性：也就是，只有满足特定条件下才容易计算出它的结果，否则，就很难。推导过程我们就不说了，那这个特定条件是什么呢？其实就是当 N 是两个素数 p1 和 p2 的乘积的时候，因为此时可以保证下面的等式成立。

φ(N) = (p1-1)(p2-1)

例如 ，77 的欧拉函数其实是很难运算出来了，但是如果我们知道77可以分解为7和11，那么就可以很容易得到结果60了。

φ(77) = (7-1)*(11-1) = 60

基于欧拉函数的这个特点，只要我们能推导出 e ，d 跟 φ(n) 的关系，那就能保证在 φ（n) 能够运算出结果的时候，从 e 很容易得到 d ，否则，从 e 就很难算出 d 。推导过程要基于欧拉定理来进行。欧拉定理的具体意义我们不必深究。

其中三个横杠是组成的等式叫做同余式。例如，正整数 a，b 对 p 取模，它们的余数相同，就记做 a ≡ b (mod p)。

推导过程我们也从略了。最终，经过欧拉定义和上面其他结论进行推导，可以得到下面两个等式是同时成立的。

这样，就可以得到 e 和 d 的关系了：也就是 e 和 d 的乘积，等于 k 乘以 φ(N) 加1 ：

d = (k*φ(N) + 1)/e

只要知道 φ(N) ，d 就可以算出来了。而如果不知道 φ(N) ，有了 e 也根本算不出 d 来。上面的 k 没有预先的固定值，而是要在运算过程中算出来的。k 的取值要保证给定一个 e 的数值， d 最终可以算出整数来。

通过上面的讨论，如何生成公钥和私钥的方法就有了，公钥是 N 和 e ，e 是在一定范围内随机选择的，而且是公开的。私钥是由 N 和 d 组成的，而 d 是在知道 N 的整数分解结果的条件下，通过上面的运算计算出来的。同时，加密函数也有了，就是信息 m 的 e 次方对 N 取模，解密函数就是密文 c 的 d 次方对 N 取模。

运算公钥和私钥

下面我们就来实际使用一下上面的结论，生成一下公钥和私钥，并且做一遍加密和解密。

首先选择两个比较大的素数，实际中一般是几百位，但是我们这里为了演示方便，选择小的一点的。p1 = 53 , p2 = 59 ，这样 N = 53*59=3127 。

首先来生成公钥和私钥，Alice 选取 e = 3 。于是公钥就是 e 和 N 这两个数的组合。公钥有了。下一步来生成私钥，也就是去运算 d 。 因为知道 p1 和 p2 的值，所以 φ(N) 很容易算出结果，就是 3016 。根据上面运算 d 的公式，当 k 等于 2 的时候，d 可以取得整数值，d 就等于

d = (2*3016+1)/3 = 2011

私钥就是 N 和 d 的组合。

接下来看加密和解密过程。Alice 把 e 和 N ，也就是公钥发送给了 Bob 。

89^3 mod 3127 = 1394

Bob 把原文 89 ，e 和 N 带入到加密函数中，最终得到密文 c = 1394 。加密过程完成。

Alice 收到密文之后，可以用私钥进行解密。

1394^2011 mod 3127 = 89

也就是，把密文，d 和 n 都带入解密函数，这样就得到了信息 m = 89 。

这样我们就完成了整个的过程。

总结

最后总结一下本文的内容。我们的问题是，如何构建先幂后模运算的各项参数之间的关系，从而保证如果一个人掌握了这种关系，是可以对加密锁进行反向运算的。那个关系是通过整数分解问题去构建的，推导过程中会用到欧拉函数的一个重要特性，也就是如果参数的整数分解结果是知道的，那么欧拉函数的结果也就很容易算出来，否则欧拉函数很难被求解。于是经过推导，我们可以得出 e*d 跟欧拉函数的值有着固定的联系，于是得到了从公钥（也就是 e ）运算出私钥（也就是 d ）的方法。

参考：