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
| #p,q=k*M+(65537**a %M)
# Hardcoded parameters for efficiency
# Found using params.py
param = \
{
512: {
"n": 39,
"a_max": 62,
"k_max": 37,
"M": 0x924cba6ae99dfa084537facc54948df0c23da044d8cabe0edd75bc6,
"M_prime": 0x1b3e6c9433a7735fa5fc479ffe4027e13bea,
"m": 5,
"t": 6,
"c_a": 0x80000
}
}
# https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/coppersmith.sage
def coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX):
"""
Coppersmith revisited by Howgrave-Graham
finds a solution if:
* b|N, b >= N^beta , 0 < beta <= 1
* |x| < XX
"""
#
# init
#
dd = pol.degree()
nn = dd * mm + tt
#
# checks
#
if not 0 < beta <= 1 :
raise ValueError("beta should belongs in (0, 1]")
if not pol.is_monic():
raise ArithmeticError("Polynomial must be monic.")
#
# Coppersmith revisited algo for univariate
#
# change ring of pol and x
polZ = pol.change_ring(ZZ)
x = polZ.parent().gen()
# compute polynomials
gg = []
for ii in range(mm):
for jj in range(dd):
gg.append((x * XX)**jj * N**(mm - ii) * polZ(x * XX)**ii)
for ii in range(tt):
gg.append((x * XX)**ii * polZ(x * XX)**mm)
# construct lattice B
BB = Matrix(ZZ, nn)
for ii in range(nn):
for jj in range(ii+1):
BB[ii, jj] = gg[ii][jj]
# LLL
BB = BB.LLL(early_red=True, use_siegel=True)
# transform shortest vector in polynomial
new_pol = 0
for ii in range(nn):
new_pol += x**ii * BB[0, ii] / XX**ii
# factor polynomial
potential_roots = new_pol.roots()
return [i[0] for i in potential_roots]
# Top level of the attack, feeds the queue for the workers
def roca(N):
# Key is not always of perfect size, infer from size
keylength = int(log(N, 2))
if keylength < 1000 :
keylength = 512
elif keylength < 2000 :
keylength = 1024
elif keylength < 4000 :
keylength = 2048
else:
keylength = 4096
# bruteforce
M_prime = param[keylength]['M_prime']
c_prime = discrete_log(N, Mod(65537, M_prime))
ord_prime = Zmod(M_prime)(65537).multiplicative_order()
top = (c_prime + ord_prime)/2
beta = 0.5
mm = param[keylength]['m']
tt = param[keylength]['t']
XX = int((2*pow(N, beta)) / M_prime)
# Bruteforce until p, q are found
a_prime = floor(c_prime/2)
while a_prime < top:
# Construct polynomial
m_inv = int(inverse_mod(M_prime, N))
k_tmp = int(pow(65537, a_prime, M_prime))
known_part_pol = int(k_tmp * m_inv)
F = PolynomialRing(Zmod(N), implementation='NTL', names=('x',))
(x,) = F._first_ngens(1)
pol = x + known_part_pol
# Get roots of polynomial using coppersmith
roots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)
# Check if roots are p, q
for root in roots:
factor1 = k_tmp + abs(root) * M_prime
if mod(N, factor1) == 0:
factor2 = N // factor1
return int(factor1), int(factor2)
a_prime += 1
N=787190064146025392337631797277972559696758830083248285626115725258876808514690830730702705056550628756290183000265129340257928314614351263713241
print ("[+] Factoring %i" % N)
factor1, factor2 = roca(N)
print ("[+] Found factors of N:")
print ("[+] p =" , factor1)
print ("[+] q =" , factor2)
|