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
| from Crypto.Util.number import *
## Coppersmith-howgrave
def coppersmith_howgrave(f, N, beta, m, t, R):
#Check if parameters are within bounds
assert 0 < beta <= 1, 'beta not in (0, 1]'
assert f.is_monic(), 'f is not monic'
#get delta and the matrix dimension
delta = f.degree()
n = delta * m + t
#Building the polynomials
fZ = f.change_ring(ZZ) #change the ring from Zmod(N) to ZZ
x = fZ.parent().gen() #make x a variable in ZZ
f_list = []
for ii in range(m):
for j in range(delta):
#We want them ordered that's we have N^(m-ii1) and fZ^ii
f_list.append(((x*R)^j) * N^(m-ii) * fZ(x*R)^(ii)) #the g_{i,j}
for ii in range(t):
f_list.append((x*R)^ii * fZ(x*R)^m) #the h_i
#Build the lattice
B = matrix(ZZ, n) # n = delta * m + t
for ii in range(n):
for j in range(ii+1):
B[ii, j] = f_list[ii][j]
#LLL it
B_lll = B.LLL(early_red = True, use_siegel = True)
#take the shortest vector to construct our new poly g
g = 0
for ii in range(n):
g += x^ii * B_lll[0, ii] / R^ii
#factor the polynomial
potential_roots = g.roots()
#print('potential roots:', potential_roots)
#we don't need to do this Since our we test in our roca function
# #test roots
# roots = []
# for r in potential_roots:
# if r[0].is_integer():
# res = fZ(ZZ(r[0]))
# if gcd(N, res) >= N^beta:
# roots.append(ZZ(r[0]))
#print('roots:', roots)
return potential_roots
#return roots
def roca(N, M_prime, g, m, t, beta):
g = int(g)
c_prime = discrete_log(Zmod(M_prime)(N), Zmod(M_prime)(g))
ord_M_prime = Zmod(M_prime)(g).multiplicative_order()
#search boundaries
bottom = c_prime // 2
top =(c_prime + ord_M_prime) // 2
print('numbers to check', top - bottom, ' between ', (bottom, top))
#constants for coppersmith
P.<x> = PolynomialRing(Zmod(N))
epsilon = beta / 7
X = floor(2 * N^beta / M_prime)
#the search
for i, a in enumerate(range(bottom, top)):
if i % 1000 == 0: #count iterations
print(i)
#construct polynomial
f = x + int((inverse_mod(M_prime, N)) * int(pow(g, a, M_prime)))
#roots = f.small_roots(X, beta, epsilon) #coppersmith
roots = coppersmith_howgrave(f, N, beta, m, t, X)
#check solutions
for k_prime, _ in roots:
p = int(k_prime * M_prime) + int(pow(g, a, M_prime))
if N % p == 0:
return p, N//p
return -1, -1
n=787190064146025392337631797277972559696758830083248285626115725258876808514690830730702705056550628756290183000265129340257928314614351263713241
e=65537
def get_M1_m_t_values(key_size):
if 512 <= key_size < 1024:
m = 5
M1=0x1b3e6c9433a7735fa5fc479ffe4027e13bea
elif 1024 <= key_size < 2048:
m = 4
M1=0x24683144f41188c2b1d6a217f81f12888e4e6513c43f3f60e72af8bd9728807483425d1e
elif 2048 <= key_size < 3072:
m = 6
M1=0x016928dc3e47b44daf289a60e80e1fc6bd7648d7ef60d1890f3e0a9455efe0abdb7a748131413cebd2e36a76a355c1b664be462e115ac330f9c13344f8f3d1034a02c23396e6
elif 3072 <= key_size < 4096:
m = 25
else:
m = 7
return M1,m, m+1
M_prime,m, t = get_M1_m_t_values(512)
p, q = roca(n, M_prime, e, m, t, .5)
assert(p*q==n)
print(p)
print(q)
enc=365164788284364079752299551355267634718233656769290285760796137651769990253028664857272749598268110892426683253579840758552222893644373690398408
print(long_to_bytes(int(pow(enc,inverse_mod(e,(p-1)*(q-1)),n))))
"""
24000
954455861490902893457047257515590051179337979243488068132318878264162627
824752716083066619280674937934149242011126804999047155998788143116757683
b'hgame{ROCA_ROCK_and_ROll!}'
"""
|
