-
Notifications
You must be signed in to change notification settings - Fork 2
/
roca_attack.py
86 lines (73 loc) · 3.15 KB
/
roca_attack.py
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
from sage.all import *
def solve(M, n, a, m):
# I need to import it in the function otherwise multiprocessing doesn't find it in its context
from sage_functions import coppersmith_howgrave_univariate
base = int(65537)
# the known part of p: 65537^a * M^-1 (mod N)
known = int(pow(base, a, M) * inverse_mod(M, n))
# Create the polynom f(x)
F = PolynomialRing(Zmod(n), implementation='NTL', names=('x',))
(x,) = F._first_ngens(1)
pol = x + known
beta = 0.1
t = m+1
# Upper bound for the small root x0
XX = floor(2 * n**0.5 / M)
# Find a small root (x0 = k) using Coppersmith's algorithm
roots = coppersmith_howgrave_univariate(pol, n, beta, m, t, XX)
# There will be no roots for an incorrect guess of a.
for k in roots:
# reconstruct p from the recovered k
p = int(k*M + pow(base, a, M))
if n%p == 0:
return p, n//p
def roca(n):
keySize = n.bit_length()
if keySize <= 960:
M_prime = 0x1b3e6c9433a7735fa5fc479ffe4027e13bea
m = 5
elif 992 <= keySize <= 1952:
M_prime = 0x24683144f41188c2b1d6a217f81f12888e4e6513c43f3f60e72af8bd9728807483425d1e
m = 4
print("Have you several days/months to spend on this ?")
elif 1984 <= keySize <= 3936:
M_prime = 0x16928dc3e47b44daf289a60e80e1fc6bd7648d7ef60d1890f3e0a9455efe0abdb7a748131413cebd2e36a76a355c1b664be462e115ac330f9c13344f8f3d1034a02c23396e6
m = 7
print("You'll change computer before this scripts ends...")
elif 3968 <= keySize <= 4096:
print("Just no.")
return None
else:
print("Invalid key size: {}".format(keySize))
return None
a3 = Zmod(M_prime)(n).log(65537)
order = Zmod(M_prime)(65537).multiplicative_order()
inf = a3 // 2
sup = (a3 + order) // 2
# Search 10 000 values at a time, using multiprocess
# too big chunks is slower, too small chunks also
chunk_size = 10000
for inf_a in range(inf, sup, chunk_size):
# create an array with the parameter for the solve function
inputs = [((M_prime, n, a, m), {}) for a in range(inf_a, inf_a+chunk_size)]
# the sage builtin multiprocessing stuff
from sage.parallel.multiprocessing_sage import parallel_iter
from multiprocessing import cpu_count
for k, val in parallel_iter(cpu_count(), solve, inputs):
if val:
p = val[0]
q = val[1]
print("found factorization:\np={}\nq={}".format(p, q))
return val
if __name__ == "__main__":
# Normal values
#p = 88311034938730298582578660387891056695070863074513276159180199367175300923113
#q = 122706669547814628745942441166902931145718723658826773278715872626636030375109
#a = 551658, interval = [475706, 1076306]
# won't find if beta=0.5
p = 80688738291820833650844741016523373313635060001251156496219948915457811770063
q = 69288134094572876629045028069371975574660226148748274586674507084213286357069
#a = 176170, interval = [171312, 771912]
n = p*q
# For the test values chosen, a is quite close to the minimal value so the search is not too long
roca(n)