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
| from Crypto.Util.number import *
import random
import math
import gmpy2
def AMM(residue,e,p):
t = 0
s = p - 1
while s % e == 0:
t += 1
s = s // e
d=gmpy2.invert(e,s)
if t==1:
return pow(residue,d,p)
noresidue = random.randint(1, p)
while pow(noresidue, (p - 1) // e, p) == 1:
noresidue = random.randint(1, p)
a=pow( noresidue , ( e ** ( t-1 )) * s, p )
b=pow( residue , e * d - 1, p )
c=pow( noresidue , s , p )
h=1
for i in range(1,t):
d=pow( b , e** ( t-1-i ) , p )
if d==1:
j=0
else:
j=-math.log(d,a)
b=pow( pow ( c , e , p ) , j , p ) * b % p
h=pow( c , j , p ) * h % p
c=pow( c , e , p )
return pow( residue , d , p ) * h % p
n = 211174039496861685759253930135194075344490160159278597570478160714793843648384778026214533259531963057737358092962077790023796805017455012885781079402008604439036453706912819711606916173828620000813663524065796636039272173716362247511054616756763830945978879273812551204996912252317081836281439680223663883250992957309172746671265758427396929152878633033380299036765665530677963287445843653357154379447802151146728382517702550201
c = 191928992610587693825282781627928404831411364407297375816921425636703444790996279718679090695773598752804431891678976685083991392082287393228730341768083530729456781668626228660243400914135691435374881498580469432290771039798758412160073826112909167507868640830965603769520664582121780979767127925146139051005022993085473836213944491149411881673257628267851773377966008999511673741955131386600993547529438576918914852633139878066
p = 31160882390461311665815471693453819123352546432384109928704874241292707178454748381602275005604671000436222741183159072136366212086549437801626015758789167455043851748560416003501637268653712148286072544482747238223
q = 6776895366785389188349778634427547683984792095011326393872759455291221057085426285502176493658280343252730331506803173791893339840460125807960788857396637337440004750209164671124188980183308151635629356496128717687
def find(e, p):
root = []
while len(root) < e:
a = random.randint(2, p - 1)
res = pow(a, (p - 1) // e, p)
if res not in root:
root.append(res)
return root
lp = []
e = 1009 * 7
c1 = c%p
m1 = AMM(c1,e,p)
root_list = find(e, p)
for i in range(len(root_list)):
a = m1 * root_list[i] % p
lp.append(int(a))
assert c1 == pow(lp[1], e, p)
lq=[]
c2 = c%q
c20 = pow(c2,inverse(7,q-1),q)
m2 = AMM(c20,1009,q)
root_list = find(1009, q)
for i in range(len(root_list)):
a = m2 * root_list[i] % q
lq.append(int(a))
assert c2 == pow(lq[1], e, q)
def Get_Mi(m_list, m):
M_list = []
for mi in m_list:
M_list.append(m // mi)
return M_list
def Get_resMi(M_list, m_list):
resM_list = []
for i in range(len(M_list)):
resM_list.append(Get_ni(M_list[i], m_list[i])[0])
return resM_list
def Get_ni(a, b):
if b == 0:
x = 1
y = 0
q = a
return x, y, q
ret = Get_ni(b, a % b)
x = ret[0]
y = ret[1]
q = ret[2]
temp = x
x = y
y = temp - a // b * y
return x, y, q
def result(a_list, m_list):
for i in range(len(m_list)):
for j in range(i + 1, len(m_list)):
if 1 != math.gcd(m_list[i], m_list[j]):
print("不能直接利用中国剩余定理")
return
m = 1
for mi in m_list:
m *= mi
Mi_list = Get_Mi(m_list, m)
Mi_inverse = Get_resMi(Mi_list, m_list)
x = 0
for i in range(len(a_list)):
x += Mi_list[i] * Mi_inverse[i] * a_list[i]
x %= m
return x
def RSA_dec(n,e,c):
phi=n-1
gcd1 = gmpy2.gcd(e, phi)
t1 = e // gcd1
dt = gmpy2.invert(t1, phi)
m_gcd1 = gmpy2.powmod(c, dt, n)
m = gmpy2.iroot(m_gcd1, gcd1)[0]
return m
from tqdm import tqdm
clis=[p,q]
ylis=[0,0]
for i in tqdm(lp, desc="Processing lp"):
for j in tqdm(lq, desc="Processing lq", leave=False):
ylis[0]=i
ylis[1]=j
if b'HECTF' in long_to_bytes(result(ylis,clis)):
print(long_to_bytes(result(ylis,clis)))
break
|