1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
| import random
import time
import math
# 幂模运算，快速计算(p^q) mod (n)，这里采用了蒙哥马利算法
def pow_mod(p, q, n):
res = 1
while q:
if q & 1:
res = (res * p) % n
q >>= 1 # 右移1位
p = (p * p) % n
return res
# 欧几里得算法求最大公约数
def gcd(a, b):
while a != 0:
a, b = b % a, a
return b
# 扩展欧几里得算法求模逆，取模负1的算法:计算x2= x^-1 (mod n)的值
def mod_1(x, n):
x0 = x
y0 = n
x1 = 0
y1 = 1
x2 = 1
y2 = 0
while n != 0:
q = x // n
(x, n) = (n, x % n)
(x1, x2) = ((x2 - (q * x1)), x1)
(y1, y2) = ((y2 - (q * y1)), y1)
if x2 < 0:
x2 += y0
if y2 < 0:
y2 += x0
return x2
# 随机产生一个非常大的奇数，w表示希望产生的位数
def largeOddNumber(w):
list = []
list.append('1') # 最高位定为1
for i in range(w - 2):
c = random.choice(['0', '1'])
list.append(c)
list.append('1') # 最低位定为1
res = int(''.join(list), 2)
return res
# 检测n是否为素数
def primeMillerRabin(a, n):
'''
第一步，模100以内的素数，初步排除很显然的合数
'''
# 100以内的素数，初步排除很显然的合数
Sushubiao = (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97)
for y in Sushubiao:
if n % y == 0:
return False
'''
第二步 用miller_rabin算法对n进行检测
'''
# 费马小定理
if pow_mod(a, n - 1, n) == 1: # 如果a^(n-1)!= 1 mod n, 说明n为合数
d = n - 1 # n-1 = (2^q )* m, 求q和m的值，用来判断二次定理
q = 0
while not (d & 1): # 末尾是0
q = q + 1
d >>= 1 # 右移1位
m = d
for i in range(q): # 0~q-1, 我们先找到最小的a^u，再逐步扩大到a^((n-1)/2)
u = m * (2 ** i) # u = 2^i * m
tmp = pow_mod(a, u, n)
if tmp == 1 or tmp == n - 1: # 如果满足，则a^(n−1) = 1 (mod n)有解。
# 满足条件
return True
return False
else:
return False
# 随机产生k个a，检验其是否都满足费马小定理和二次定理
def prime_test(n, k):
while k > 0:
a = random.randint(2, n - 1)
if not primeMillerRabin(a, n):
return False
k = k - 1
return True
# 产生一个大素数(bit位)
def get_prime(bit):
while True:
prime_number = largeOddNumber(512) # 产生一个512位的大奇数
for i in range(50): # 伪素数附近50个奇数都没有真素数的话，重新再产生一个伪素数
u = prime_test(prime_number, 5)
if u:
break
else:
prime_number = prime_number + 2 * i
if u:
return prime_number
else:
continue
if __name__ == '__main__':
# 密钥p
p = get_prime(500)
# 密钥q
q = get_prime(550)
# 公开n
n = p * q
# 欧拉函数
Euler = (p - 1) * (q - 1)
# 取一个合适的e，而且e和(p-1)*(q-1)互素
while True:
e = 65537
if gcd(e, Euler) == 1:
break
else:
e = e - 1
d = mod_1(e, Euler)
print('私钥p, q, d分别为:')
print('p:', p)
print('q:', q)
print('d:', d)
print()
print('公钥n, e分别为:')
print('n:', n)
print('e:', e)
print()
plaintext = input("请输入待加密的明文:")
M = []
for i in range(len(plaintext)):
M.append(ord(plaintext[i]))
print()
# 加密
ciphertext = []
for i in range(len(plaintext)):
ciphertext.append(pow_mod(M[i], e, n))
print('加密完成，得到的密文为:')
print(ciphertext)
print()
# 解密
mingWen = ''
for i in range(len(plaintext)):
mingWen += chr(pow_mod(ciphertext[i], d, n))
print('解密完成，得到的明文为:')
print(mingWen)
|
