信息计算2019级2班32号王诗琪

王诗琪

4.19

4.22

王诗琪

04.29

王诗琪

大数版本的RSA
环境：PyCharm3.7.9
生成素数：

1. import random
   
2. from random import randint
   
3. 
   
4. 
   
5. def proBin(w):  # w是产生位数，生成伪素数
   
6.     list = []
   
7.     list.append('1')  
   
8.     for _ in range(w - 2):
   
9.         c = random.choice(['0', '1'])
   
10.         list.append(c)
    
11.     list.append('1')
    
12.     res = int(''.join(list), 2)
    
13.     return res
    
14. 
    
15. 
    
16. # 幂模运算
    
17. def X_n_mod_P(base, exponent, n):
    
18.     bin_array = bin(exponent)[2:][::-1]
    
19.     r = len(bin_array)
    
20.     base_array = []
    
21. 
    
22.     pre_base = base
    
23.     base_array.append(pre_base)
    
24. 
    
25.     for _ in range(r - 1):
    
26.         next_base = (pre_base * pre_base) % n
    
27.         base_array.append(next_base)
    
28.         pre_base = next_base
    
29. 
    
30.     a_w_b = __multi(base_array, bin_array, n)
    
31.     return a_w_b % n
    
32. 
    
33. 
    
34. def __multi(array, bin_array, n):
    
35.     result = 1
    
36.     for index in range(len(array)):
    
37.         a = array[index]
    
38.         if not int(bin_array[index]):
    
39.             continue
    
40.         result *= a
    
41.         result = result % n
    
42.     return result
    
43. 
    
44. 
    
45. def MillerRabin(a, p):
    
46.     if X_n_mod_P(a, p - 1, p) == 1:
    
47.         u = (p - 1) >> 1
    
48.         while (u & 1) == 0:
    
49.             t = X_n_mod_P(a, u, p)
    
50.             if t == 1:
    
51.                 u = u >> 1
    
52.             else:
    
53.                 if t == p - 1:
    
54.                     return True
    
55.                 else:
    
56.                     return False
    
57.         else:
    
58.             t = X_n_mod_P(a, u, p)
    
59.             if t == 1 or t == p - 1:
    
60.                 return True
    
61.             else:
    
62.                 return False
    
63.     else:
    
64.         return False
    
65. 
    
66. 
    
67. def testMillerRabin(p, k):
    
68.     while k > 0:
    
69.         a = randint(2, p - 1)
    
70.         if not MillerRabin(a, p):
    
71.             return False
    
72.         k = k - 1
    
73.     return True
    
74. 
    
75. 
    
76. def makeprime(w):  # 产生w位素数
    
77.     while 1:
    
78.         d = proBin(w)
    
79.         for i in range(50):  # 伪素数附近50个奇数都没有真素数的话，重新再产生一个伪素数
    
80.             u = testMillerRabin(d + 2 * (i), 5)
    
81.             if u:
    
82.                 b = d + 2 * (i)
    
83.                 break
    
84.             else:
    
85.                 continue
    
86.         if u:
    
87.             return b
    
88.         else:
    
89.             continue

复制代码

算法：

1. from makeprime import makeprime
   
2. 
   
3. # 构造字典
   
4. dict = {'a': '31', 'b': '32', 'c': '33', 'd': '34', 'e': '35', 'f': '36', 'g': '37',
   
5.         'h': '38', 'i': '39', 'j': '10', 'k': '11', 'l': '12', 'm': '13', 'n': '14',
   
6.         'o': '15', 'p': '16', 'q': '17', 'r': '18', 's': '19', 't': '20', 'u': '21',
   
7.         'v': '22', 'w': '23', 'x': '24', 'y': '25', 'z': '26', '1': '41', '2': '42',
   
8.         '3': '43', '4': '44', '5': '45', '6': '46', '7': '47', '8': '48', '9': '49',
   
9.         '0': '40', ' ': '50'}
   
10. 
    
11. 
    
12. # 字符与数字之间的转换
    
13. def transferToNum(str):
    
14.     m = ""
    
15.     for d in str:
    
16.         m += dict[d]
    
17.     return m
    
18. 
    
19. 
    
20. def transferTostr(num):
    
21.     n = ""
    
22.     for i in range(0, len(num), 2):
    
23.         n += {value: key for key, value in dict.items()}[num[i] + num[i + 1]]
    
24.     return n
    
25. 
    
26. 
    
27. def ext_gcd(a, b):
    
28.     if b == 0:
    
29.         x1 = 1
    
30.         y1 = 0
    
31.         x = x1
    
32.         y = y1
    
33.         r = a
    
34.         return r, x, y
    
35.     else:
    
36.         r, x1, y1 = ext_gcd(b, a % b)
    
37.         x = y1
    
38.         y = x1 - a // b * y1
    
39.         return r, x, y
    
40. 
    
41. 
    
42. '''
    
43. 大整数大次幂然后取模
    
44. (base ^ exponent) mod n
    
45. '''
    
46. 
    
47. 
    
48. def exp_mode(base, exponent, n):
    
49.     bin_array = bin(exponent)[2:][::-1]
    
50.     r = len(bin_array)
    
51.     base_array = []
    
52. 
    
53.     pre_base = base
    
54.     base_array.append(pre_base)
    
55. 
    
56.     for _ in range(r - 1):
    
57.         next_base = (pre_base * pre_base) % n
    
58.         base_array.append(next_base)
    
59.         pre_base = next_base
    
60. 
    
61.     a_w_b = __multi(base_array, bin_array, n)
    
62.     return a_w_b % n
    
63. 
    
64. 
    
65. def __multi(array, bin_array, n):
    
66.     result = 1
    
67.     for index in range(len(array)):
    
68.         a = array[index]
    
69.         if not int(bin_array[index]):
    
70.             continue
    
71.         result *= a
    
72.         result = result % n
    
73.     return result
    
74. 
    
75. 
    
76. # 生成公钥私钥，p、q为两个大质数
    
77. def gen_key(p, q):
    
78.     n = p * q
    
79.     fy = (p - 1) * (q - 1)  # 计算与n互质的整数个数 欧拉函数
    
80.     e = 65537  # 选取e 65537
    
81.     a = e
    
82.     b = fy
    
83.     x = ext_gcd(a, b)[1]
    
84. 
    
85.     if x < 0:
    
86.         d = x + fy
    
87.     else:
    
88.         d = x
    
89.     print("公钥:" + "(" + str(n) + "," + str(e) + ")\n私钥:" + "(" + str(n) + "," + str(d) + ")")
    
90.     return (n, e), (n, d)
    
91. 
    
92. 
    
93. # 加密 m是被加密的信息 加密成为c
    
94. def encrypt(m, pubkey):
    
95.     n = pubkey[0]
    
96.     e = pubkey[1]
    
97. 
    
98.     c = exp_mode(m, e, n)
    
99.     return c
    
100. 
     
101. 
     
102. # 解密 c是密文，解密为明文m
     
103. def decrypt(c, selfkey):
     
104.     n = selfkey[0]
     
105.     d = selfkey[1]
     
106. 
     
107.     m = exp_mode(c, d, n)
     
108.     return m
     
109. 
     
110. 
     
111. if __name__ == "__main__":
     
112.     print("1.生成大于64位的质数p和q(以100位为例):")
     
113.     p = makeprime(100)
     
114.     print("p:", p)
     
115.     q = makeprime(100)
     
116.     print("q:", q)
     
117. 
     
118.     print("2.生成公钥、私钥")
     
119.     pubkey, selfkey = gen_key(p, q)
     
120. 
     
121.     print("3.输入明文(小写英文与数字的组合)")
     
122.     plaintext = str(input())
     
123.     m = int(transferToNum(plaintext))
     
124. 
     
125.     print("4.用公钥加密信息")
     
126.     c = encrypt(m, pubkey)
     
127.     print("密文:", c)
     
128. 
     
129.     print("5.用私钥解密")
     
130.     d = decrypt(c, selfkey)
     
131.     print("明文:", transferTostr(str(d)))
     

复制代码

运行截图：

王诗琪

5.3观看截图