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 )的方法。

参考: