RSA加解密算法及题目解析

  一、算法原理

    算法本身基于一个简单的数论知识：给出两个素数，很容易将它们相乘，然而给出它们的乘积，想得到这两个素数就显得尤为困难。如果能够解决大整数（比如几百位的整数）分解的快速方法，那么 RSA 算法将轻易被破解。

1.1 公钥和私钥的生成

1.2 RSA 加密

1.3 RSA 解密

1.4 私钥解密证明

    我们要做的就是证明密文经过私钥的幂取模的结果等于明文，即如下等式成立：

证明

1）x 和 n 互素

    这种情况，我们主要用欧拉定理就可以证明，证明过程如下：

2）x 和 n 不互素

1.5 安全性证明

二、题目解析

2.1 软考网络工程师考试题目

    按照RSA算法，若选取两奇数p=5，q=3，公钥e=7，则私钥d为多少？

A.6    B.7    C.8    D.9

答案解析：

由p=5，q=3，e=7，可知n = p*q =15。φ(n)=(p−1)(q−1)=8

由ed除以φ(n)余数为1得，7d ≡ 1(mod 8)，求出d=7，答案为B

2.2 采用python编码，求解出d

答案：

#!/usr/bin/python  
#coding:utf-8  
#@Author:Mr.Aur0ra
 
import gmpy2  
p = 3487583947589437589237958723892346254777  
q = 8767867843568934765983476584376578389  
e = 65537  
phi = (p-1)*(q-1)#φ(n)在写的时候多用phi代替，因为键盘不好敲出来。
d = gmpy2.invert(e,phi)
#e模phi的逆为d, (e*d)%phi==1 原理上面讲过
print d

或者

#!/usr/bin/python  
#coding:utf-8  
#@Author:Mr.Aur0ra 
 
import libnum  
p = 3487583947589437589237958723892346254777  
q = 8767867843568934765983476584376578389  
e = 65537  
phi = (p-1)*(q-1)  
d = libnum.invmod(e,phi) #e模phi的逆为d,(e*d)%phi==1   
print d

    上面的两种解法只是调用的模块不同（gmpy2或libnum），但计算效果是一样的，后面的题目中也会经常使用这些模块，具体想用哪个模块看自己的心情就好。建议使用gmpy2模块，该模块的功能更强大。

    SageMath 是在GPL协议下发布的开源数学软件，并且整合了许多已有的开源软件包到一个基于Python的统一界面下。其目标是创造一个Magma，Maple，Mathematica和Matlab的开源替代品。

    SageMath 包含了从线性代数、微积分，到密码学、数值计算、组合数学、群论、图论、数论等各种初高等数学的计算功能。

    SageMath 的功能十分强大，现在很多CTF比赛的密码学题目都是能用Sage去求解的。建议大家花一部分时间去学习下。

2.3 RSA加解密

答案：

2.4 有如下公式:

 a＋b mod n ＝ (a mod n＋b mod n) mod n

a－b mod n ＝ (a mod n－b mod n) mod n

a×b mod n ＝ (a mod n×b mod n) mod n

试利用上述公式计算15^27(mod 33)的值。

解答：

2.5 令p=47,q=71,求用RSA算法加解密的公钥和私钥。已知20*d mod 2000001=1，求d的值。

答案：求d有三种方法：

① 凑数，尝试法
②扩展的欧几里得

参考文献：

https://zhuanlan.zhihu.com/p/450180396

https://zhuanlan.zhihu.com/p/76006823

https://blog.csdn.net/qq_44775675/article/details/122400841

原文始发于微信公众号（豆豆咨询）：RSA加解密算法及题目解析