转载请注明出处:https://www.jzgwind.com/?p=612 by joey

RSA加密算法是非对称加密解决方案,是密码学的最核心原理之一。它的有效性是基于这样一个事实:一个很大的数,想要找到它是由哪两个质数相乘得到的难度是非常大,量子计算出现以前,以目前的算力几乎是不可能的。

非对称加密的特点

私钥加密后,可以用公钥解密(通常用于数字签名); 反之,用公钥加密后,可以用私钥解密(通常用于加密信息)。

算法的数学基础

算法的数学基础基于“数论”:

质数:

如果一个正整数,除了1和它本身外,不能被其他自然数分解,则该数为质数(素数)。

互质:

如果两个正整数,除了1之外没有其他的公因子,则称这两个数为“互质”关系。

欧拉函数:

已知正整数n,则φ(n)表示n的欧拉函数,其涵义是:小于等于n的正整数中,与n构成“互质”关系的正整数个数。例如求φ(8),小于等于8并且与8构成互质关系的正整数有1,3,5,7,一共有4个,因此φ(8)。

如果n是质数,则φ(n)  = n -1。

如果n可以分解成p和q两个质数,即n = p * q,p和q都为质数,则φ(n) = φ(p) * φ(q) = (p-1) * (q-1)。

欧拉定理:

如果两个正整数a与n互质,则aφ(n)  = 1 (mod n)

模反元素:

如果两个正整数a与n互质,则一定存在一个正整数b,使得ab除n的余数为1,即存在b,使得:

ab = 1 (mod n)。 b称为a对于n的模反元素。

模板元素存在性证明:

根据上述欧拉定理,aφ(n)  = 1 (mod n),即a * aφ(n)-1  = 1 (mod n),即a^[φ(n) – 1] 是a对于n的模反元素。

RSA算法过程

找到两个质数p和q,他们的乘积等于n,即n = p * q。 φ(n)代表n的欧拉函数。

随机选择一个整数e,使得1 < e < φ(n),且e与φ(n)互质。根据欧拉定理,e一定存在模反元素d:即一定存在整数d,使得ed = 1(mod φ(n))。

RSA算法将(e, n)作为公钥,将(d, n)作为私钥

模反元素d的求解

ed =1(mod φ(n)),即 ed = k*φ(n) + 1。在已经e和φ(n) 的情况下,d的求解可采用“扩展欧几里得算法”求解。

加密过程:

假设明文为m,密文为c,由以下取模运算得到密文c:

m= c (mod n),即m的e次方与n进行取模运算后的余数即为密文c。

解密过程:

c^d = m (mod n),即c的d次方与n进行取模运算后的余数即为明文m。

点击查看解密公式证明

上述算法为什么不易破解?

假设知道了公钥(e, n),要想得到私钥(d, n),由于ed = 1(mod φ(n)),即必须要得到φ(n)。

又由于φ(n) = φ(p*q) = φ(p) * φ(q) = (p – 1) * (q – 1),因此必须求解n的质因数p和q。

如果已知的n非常大,想要找到它的两个质数分解p和q是很难的,几乎不可能。

目前RSA算法的n的值对应的二进制位数是1024位,重要场合可以用2048位。而人类目前已知的最大质因数分解是找到了一个768位(二进制)的质因数分解。

注:算法要求明文m的整数值必须小于n解密公式证明需要用到这个条件)。

如果明文m大于n怎么办呢?一种办法是将m进行拆分,对m进行分段加密;另一种方法是先将m用对称加密算法进行加密,然后将“对称加密”的密钥进行RSA加密。

注:当明文m是字符串时,可以取其ascii值或unicode值表示。

实例:

假设p = 53, q = 59,则n = 53 * 59 = 3127,φ(n) = φ(53 * 59) = φ(53) * φ(59) = (53-1) * (59 – 1) = 3016。

假设要传输的明文m = 89,取e = 3(3与φ(n) 互质),公钥为(e, n) = (3, 3127),则密文 c = 893 mod 3127 = 1394

由于ed = 1 (mod φ(n) ),即ed = k * φ(n)  + 1,代入后得3 * d = k*3016 +1。

(d, k) = (2011, 2)是其中一组解。

密钥为(d, n) = (2011, 3127),则根据解密公式 cd = m mod (n) 可知

m = cd mod n = 13942011 mod 3127 = 89

附:指数取模运算python代码

result = 1394
t = 1394 % 3127
for i in range(1, 2011):
  result = result * t
  result = result % 3127
print(sum)

结果为89

参考文献:

阮一峰个人博客——RSA算法原理(二)

熊丽兵个人博客——RSA算法数学原理分析