一、实验目的
深度理解RSA算法的工作原理，查阅欧几里得扩展算法计算模运算的逆元，并编程序实现。学会生成不同大小的素数，体会模指数运算的困难性和模指数运算的快速算法。
二、实验器材
pycharm+python3.11
三、实验内容
1.实验要求：自己配置python环境，编写RSA算法实现程序，运行RSA程序，演示RSA加密与解密的过程。
RSA加密过程：
（1）编写程序调用gmpy.2的大素数生成算法，生成不同的素数。
程序代码：
1 import gmpy2 2 from gmpy2 import mpz 3 def gen_prime(rs): 4 """生成二进制位数为1024的随机素数""" 5 p = gmpy2.mpz_urandomb(rs, 1024) 6 while not gmpy2.is_prime(p): 7 p = p + 1 8 return p
（2）编写RSA程序，在程序中调用大素数生成算法生成需要的素数。
程序代码：
1 import gmpy2
2 from gmpy2 import mpz
3 import binascii
4
5
6 def gen_prime(rs):
7 """生成二进制位数为1024的随机素数"""
8 p = gmpy2.mpz_urandomb(rs, 1024)
9 while not gmpy2.is_prime(p):
10 p = p + 1
11 return p
12
13
14 def gen_key():
15 """生成密钥"""
16 rs = gmpy2.random_state()
17 p = gen_prime(rs)
18 q = gen_prime(rs)
19 return p, q
20
21
22 def encrypt(e, n, message):
23 """将输入消息转换成16进制数字并加密，支持utf-8字符串"""
24 M = mpz(binascii.hexlify(message.encode('utf-8')), 16)
25 C = gmpy2.powmod(M, e, n)
26 return C
27
28
29 def decrypt(d, n, C):
30 """对输入的密文进行解密并解码"""
31 M = gmpy2.powmod(C, d, n)
32 return binascii.unhexlify(format(M, 'x')).decode('utf-8')
33
34
35 def main():
36 # 密钥生成
37 p, q = gen_key()
38 n = p * q
39 phi = (p - 1) * (q - 1)
40 e = 3674911
41 d = gmpy2.invert(e, phi)
42
43 # 输入消息
44 message = input('输入待加密的消息：\n')
45
46 # 加密
47 C = encrypt(e, n, message)
48 print('16进制密文：', hex(C))
49
50 # 解密
51 print('解密后的消息：', decrypt(d, n, C))
52
53
54 if __name__ == '__main__':
55 main()
运行结果：
（3）用较小的x<1,000,000,000尝试采用传统方法计算模指数，即ax+1 mod n = [ (ax mod n) × a] mod n 的方法。
程序代码：
1 from math import sqrt
2
3 def Cnotrol():
4 d = 0
5 x = int(input('请输入你的选择的功能::RSA加密为0，RSA解密为1，分解查找P与Q为2,退出请按9:'))
6 qt = 1
7 while qt:
8 if x == 0:
9 print('----------------加密----------------')
10 print('---------请输入P,Q,E,M(明文)---------')
11 p = int(input('输入P:'))
12 q = int(input('输入Q:'))
13 e = int(input('输入E:'))
14 Flag = apnjudg(p, q, e)
15 if Flag == 0:
16 m = int(input('请输入M:'))
17 encryption(m, e, p * q)
18 Cnotrol()
19 else:
20 break
21 elif x == 1:
22 print('----------------解密----------------')
23 print('---------请输入P,Q,E,C(密文)---------')
24 p = int(input('输入P:'))
25 q = int(input('输入Q:'))
26 e = int(input('输入E:'))
27 fi = (p - 1) * (q - 1)
28 for i in range(fi): # 求逆元d
29 if e * i % fi == 1:
30 d = i
31 break
32 print("逆元d的值为：", d)
33 apnjudg(p, q, d)
34 c = int(input('请输入C:'))
35 decode(c, d, p * q)
36 Cnotrol()
37
38 elif x == 2:
39 print('----------------拆解素数乘积----------------')
40 n = int(input('输入乘积N:'))
41 broken(n)
42 Cnotrol()
43
44 else:
45 print("感谢您的使用")
46 break
47 qt = 0
48 def encryption(m, e, n)://传统方法计算模指数
49 s = m % n
50 for i in range(1, e):
51 s = (s * (m % n)) % n
52 print('你所加密的密文是：', s)
53 # 解密
54 def decode(c, d, n):
55 s = c % n
56 for i in range(1, d):
57 s = (s * (c % n)) % n
58 print('你所解密的明文是：', s)
59 # p,q,e质数判断
60 def apnjudg(p, q, e):
61 Li = [p, q, e]
62 flag = 0
63 for x in range(0, 3):
64 if int(Li[x]) > 2:
65 # 查看因子
66 # sqrt()平方根函数减小计算周期
67 for i in range(2, int(sqrt(Li[x]))+1):
68 if (int(Li[x]) % i) == 0:
69 print(int(Li[x]), "不是质数")
70 print(i, "乘于", int(Li[x]) // i, "是", int(Li[x]))
71 flag += 1
72 break
73 else:
74 continue
75 if flag == 0:
76 print(int(Li[x]), "是质数")
77 else:
78 print("QAQ您的输入有误(存在非质数)，程序退出QAQ")
79 break
80 # 如果输入的数字小于或等于 2，不是质数
81 else:
82 print(int(Li[x]), "不是质数")
83 flag += 1
84 continue
85 return flag
86 # 拆解获得素数p,q
87 def broken(n):
88 if n < 10000000:
89 for i in range(1, 10000):
90 for t in range(1, 10000):
91 if n == i * t:
92 print(i, t)
93 break
94 if __name__ == '__main__':
95 Cnotrol()
运行结果：
(4)尝试用模运算的快速算法计算模指数(称为重复平方相乘法)，即将指数写成二进制的形式，如果b=35，可以写成b=1000011，则
ab mod n = (a32)1*(a16)0*(a8)0*(a4)0*(a2)0*(a1)1*(a0)1 mod n
算法原理：
程序代码：
1 def fastExpMod(b,n,m): 2 ''' 3 return : b^n mod m 4 ''' 5 result = 1 6 while n != 0: 7 if (n & 1) == 1: #按位与&操作 8 result = (result * b) % m 9 b = (b*b) % m 10 n = n >> 1 #位数右移>>操作 11 return result
(5)利用快速模指数运算法实现RSA加密与解密算法
程序代码：
1 '''
2 RSA加解密算法
3 2023.11.11
4 1.模平方算法 2.欧几里得算法 3.费马素性检测算法
5 '''
6 import random
7
8
9 def fastExpMod(b, n, m):
10 '''
11 return : b^n mod m
12 '''
13 result = 1
14 while n != 0:
15 if (n & 1) == 1: # 按位与操作
16 result = (result * b) % m
17 b = (b * b) % m
18 n = n >> 1 # 位数右移操作
19 return result
20
21
22 def Euclid(a,b):
23 '''
24 欧几里得算法 ax + by = gcd(a,b)
25 Return : [x , y , gcd(a,b)]
26 '''
27 X = [1,0,a]
28 Y = [0,1,b]
29 while Y[2] !=0 :
30 Q = X[2]//Y[2]
31 NEW_Y = [i*Q for i in Y]
32 T = list(map(lambda x: x[0]-x[1], zip(X, NEW_Y)))
33 X = Y.copy()
34 Y = T.copy()
35 return X
36
37
38 def fermatPrimeTest(m, k):
39 '''
40 费马素性检验算法
41 m : 给定整数
42 k : 安全参数，重复K次
43 '''
44 if m % 2 == 0:
45 return False
46 for i in range(k):
47 a = random.randint(2, m - 2)
48 g = Euclid(a, m)
49 if g[2] == 1:
50 r = fastExpMod(a, m - 1, m)
51 if r == 1:
52 continue
53 else:
54 return False
55 else:
56 return False
57 return True
58 def findPrime(lower, upper):
59 '''
60 return : 一个位于upper和lower之间的素数
61 '''
62 while True:
63 n = random.randint(lower, upper)
64 if fermatPrimeTest(n, 6) == True:
65 return n
66
67
68 def selectE(fn):
69 '''
70 fn : euler function
71 Return : e
72 '''
73 while True:
74 e = random.randint(1, fn)
75 temp = Euclid(e, fn)
76 if temp[2] == 1:
77 return e
78
79
80 def keyGenerate(lower, upper):
81 '''
82 给定两个素数p和q生成的区间
83 return : e,n,d
84 '''
85 p = findPrime(lower, upper)
86 q = findPrime(lower, upper)
87 print("p:" + str(p) + " q:" + str(q))
88 # print("q:"+str(q))
89 n = p * q
90 fn = (p - 1) * (q - 1)
91 e = selectE(fn)
92 temp = Euclid(e, fn) # 欧几里得算法求逆元
93 d = temp[0]
94 if d < 0: # 由于e和fn互素故一定存在逆元
95 d = d + fn # 保证d为正数
96 return e, n, d
97
98
99 def start():
100 e, n, d = keyGenerate(1000, 10000) # 密钥生成
101 # 更改keyGenerate函数的两个参数，可以改变生成素数的位数大小。
102 print("public key (e,n):", end="")
103 print("(" + str(e) + " , " + str(n) + ")\n")
104 print("private key d: " + str(d) + "\n")
105 m = random.randint(1, n) # m < n m为明文
106 print("Plaintext: " + str(m))
107 c = fastExpMod(m, e, n) # 加密 c为密文 m^e mod n
108 print("\nEncryption of PlainText: " + str(c))
109 x = fastExpMod(c, d, n) # 解密 c^d mod n
110 print("\nDecryption of CipherText: " + str(x))
111 if x == m:
112 print("\nThe plaintext and ciphertext are the same.")
113
114
115 if __name__ == "__main__":
116 start()
运行结果：
