摘要

网上有很多关于RSA的解密脚本，欧拉函数、欧几里得函数什么的，对于一个大专生的我来说，一窍不通，至此经历了三天三夜，我翻阅了RSA的加密原理，以及其底层算法，专研出了一套我自己的解密算法，尚有不足，欢迎评论吐槽！

RSA算法原理

RSA公开密钥密码体制的原理是：根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。

RSA算法的具体描述如下：
（1）任意选取两个不同的大素数p和q计算乘积 n = pq，n1 = (p-1)(q-1) ；
（2）任意选取一个大整数e，满足gcd(e,n1)=1，整数e用做加密钥（注意：e的选取是很容易的，例如，所有大于p和q的素数都可用）；
（3）确定的解密钥d，满足(de) mod n1 = 1，即de = k(n1)+1,k >= 1 是一个任意的整数；所以，若知道e和n1，则很容易计算出d；
（4）公开整数n和e，秘密保存d ；
（5）将明文m（m<n是一个整数）加密成密文c，加密算法为：c = E(m)=m^e mod n；
（6）将密文c解密为明文m，解密算法为：m = D(c) = c^d mod n；
然而只根据n和e（注意：不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密。

RSA解密算法思路

通过RSA算法原理的第三点可以看到，需要解密出明文m，就要知道密钥d，所以算法思路就围绕密钥d进行求解。

密钥d 通过辗转相除法 (欧几里得算法，我后面才知道的......) 进行求解：

1、根据算法原理的第三点我们得知：(de) mod n1 = 1，即 de - k(n1) = 1；

2、知道系数k 即可得到密钥d，且系数k 存在两种情况：

2.1 情况一：n1 != 1

2.1.1 先 n1 对 e 取模后得到的值赋值给 n1

2.1.2 然后 e 对赋值后的 n1 取模得到的值赋值给 e

......

以此类推，最后得到 k = 1 时即可停止；

令 d = 1 代入倒数第二条式子，得到k的值代入倒数第三条式子，以此类推当代入至第一条式子时，得到的 d 即为密钥d 的值；

2.2 情况二：n1 = 1

2.2.1 按照情况一的步骤，最后得到 n1 = 1 时即可停止；

根据情况一的步骤代入即可得到密钥d 的值。

3、使用python内置函数 pow函数即可得到明文m。

k的算法函数

 1 def rsa_k(p,q,e):

 2     e1 = e

 3     n1 = (p - 1) * (q - 1)

 4     i = 0

 5     n2 = []

 6     e2 = []

 7     n2.append(n1)

 8     e2.append(e)

 9     while True:

10         i += 1

11         n1 = n1%e1

12         n2.append(n1)

13         if n1 == 1:

14             if i == 1:

15                 d1 = 1

16                 k = (e1 * d1) - 1

17                 break

18             else:

19                 '''d * e - n1 * k = 1'''

20                 # 最后一步 k = e - 1

21                 k = (e2[i-1] * 1 - 1) / n2[i]

22                 for j in range(i-1):

23                     d1 = (1 + (k * n2[i - j - 1])) / e2[i - j - 1]

24                     k = (e2[i - (j + 1) - 1] * d1 - 1) / n2[i - j - 1]

25                 break

26         else:

27             e1 = e1 % n1

28             e2.append(e1)

29             if e1 == 1:

30                 if i == 1:

31                     d1 = 1

32                     k = (e * d1 -1) / n1

33                     break

34                 else:

35                     # k=0,d1=1 最后一步

36                     # 倒数第二步开始，往前求d

37                     # K != 1

38                     '''d * e - n1 * k = 1'''

39                     k = (e2[i-1] * 1 -1) / n2[i]

40                     for j in range(i-1):

41                         d1 = (1 + (k*n2[i-j-1])) / e2[i-j-1]

42                         k = (e2[i-(j+1)-1] * d1 -1) / n2[i-j-1]

43                     break

44     rsa_d(p,q,e,k)

密钥d的算法函数

1 def rsa_d(p,q,e,k):

2     n1 = (p - 1) * (q - 1)

3     # 第一步

4     # " / "就表示 浮点数除法，返回浮点结果;" // "表示整数除法

5     d = (1 + n1 * int(k)) // e

6     rsd_m(int(c),int(d),int(n))

明文m的算法函数

1 def rsd_m(c,d,n):

2     m = pow(c,d,n)

3     flag = long_to_bytes(m)

4     print('[+] 解密完成\nflag =',flag.decode('utf-8'))

源码已经放在github上，记得帮作者点一下Star哦~

声明

1、博客中标注原创的文章，版权归原作者 spmonkey 所有；
2、未经原作者允许不得转载本文内容，否则将视为侵权；
3、转载或者引用本文内容请注明来源及原作者；
4、对于不遵守此声明或者其他违法使用本文内容者，本人依法保留追究权等。

先联系原作者征得转载授权，并且注明文章原始出处和原作者。

联系原作者邮箱：spmonkey@hscsec.cn

巴特西

基于python的RSA解密算法

摘要

RSA算法原理

RSA解密算法思路

k的算法函数

密钥d的算法函数

明文m的算法函数

声明

最新文章

热门文章