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
| from sage.all import *
from random import choice
from math import gcd
import sys
from Crypto.Util.number import *
from tqdm import tqdm
import time
sys.setrecursionlimit(100000)
def polynomial_xgcd(a, b):
"""
Computes the extended GCD of two polynomials using Euclid's algorithm.
:param a: the first polynomial
:param b: the second polynomial
:return: a tuple containing r, s, and t
"""
assert a.base_ring() == b.base_ring()
r_prev, r = a, b
s_prev, s = 1, 0
t_prev, t = 0, 1
while r:
try:
q = r_prev // r
r_prev, r = r, r_prev - q * r
s_prev, s = s, s_prev - q * s
t_prev, t = t, t_prev - q * t
except RuntimeError:
raise ArithmeticError("r is not invertible", r)
return r_prev, s_prev, t_prev
def polynomial_inverse(p, m):
"""
Computes the inverse of a polynomial modulo a polynomial using the extended GCD.
:param p: the polynomial
:param m: the polynomial modulus
:return: the inverse of p modulo m
"""
g, s, t = polynomial_xgcd(p, m)
return s * g.lc() ** -1
def factorize(N, D):
"""
Recovers the prime factors from a modulus using Cheng's elliptic curve complex multiplication method.
More information: Sedlacek V. et al., "I want to break square-free: The 4p - 1 factorization method and its RSA backdoor viability"
:param N: the modulus
:param D: the discriminant to use to generate the Hilbert polynomial
:return: a tuple containing the prime factors
"""
assert D % 8 == 3, "D should be square-free"
zmodn = Zmod(N)
pr = zmodn["x"]
H = pr(hilbert_class_polynomial(-D))
Q = pr.quotient(H)
j = Q.gen()
try:
k = j * polynomial_inverse((1728 - j).lift(), H)
except ArithmeticError as err:
p = gcd(int(err.args[1].lc()), N)
return int(p), int(N // p)
E = EllipticCurve(Q, [3 * k, 2 * k])
while True:
x = zmodn.random_element()
z = E.division_polynomial(N, x=Q(x))
try:
d, _, _ = polynomial_xgcd(z.lift(), H)
except ArithmeticError as err:
p = gcd(int(err.args[1].lc()), N)
return int(p), int(N // p)
p = gcd(int(d), N)
if 1 < p < N:
return int(p), int(N // p)
n=330961752887996173328854935965112588884403584531022561119743740650364958220684640754584393850796812833007843940336784599719224428969119533284286424077547165101460469847980799370419655082069179038497637761333327079374599506574723892143817226751806802676013225188467403274658211563655876500997296917421904614128056847977798146855336939306463059440416150493262973269431000762285579221126342017624118238829230679953011897314722801993750454924627074264353692060002758521401544361385231354313981836056855582929670811259113019012970540824951139489146393182532414878214182086999298397377845534568556100933934481180701997394558264969597606662342898026915506749002491326250792107348176681795942799954526068501499100232598658650184565873243525176833451664254917655703178472944744658628534195346977023418550761620254528178516972066618936960223660362493931786389085393392950207048675797593816271435700130995225483316625836104802608163745376633884840588575355936746173068655319645572100149515524131883813773486917122153248495022372690912572541775943614626733948206252900473118240712831444072243770979419529210034883903111038448366933374841531126421441232024514486168742686297481063089161977054825621099768659097509939405315056325336120929492838479309609958696957890570295444494277819063443427972643459784894450787015151715676537385237767990406742547664321563688829289809321534752244260529319454316532580416182438749849923354060125229328043961355894086576238519138868298499249023773237770103057707912709725417033309061308880583988666463892828633292839968866953776989722310954204550783825704710017434214644199415756584929214239679433211393230307782953067246529626136446314941258877439356094775337541321331600788042698664632064112896956898222397445497695982546922871549828242938368486774617350420790711093069910914135319635330786253331223459637232106417577225350441291
e=65537
c=187275367513186345104534865239994699892170904489725413330767115192172530253625393062151741036312498277557971553595091826062438445856091864605758318579599363539202154625683947568962358702545878760994434813222953503460910447662183200334960821110618746899798165363389255347363192576250804362413854445821046755759458439443253294822553986237695607000569717855942461517564526611106601774100617668231506539201297550376834067118784548951699927659889815770492684106287801610261026674778509245649501695344652216367741171392139049785280654043804502329999760613658697298671602787929199239524617160567336634126185042907593427921016129734757065504417112269027028799047579450965076835882020261162192475637278445255805339324893626400179818784574957669576516363342104273184813708475202313539634027764340858242764934872804570810575764191987921655276520658100755510986290562980055133376750812535713567917823663134974180449002466833109112866681229626239871954125027501071383217816313440079294139254989413050731511516498127225020975071747314764552267845933494600295296885808466296844091612401062566502515356974852161817112538289440970059783116540091633055220150093646069438113246518726017868258339512247175386052684861670431148484455765445960495130308147156436998327553854387741014177421559585683382003377803158283603889312107837885491964835073892174406797445622388505256985237867456926792546588756970045576002345376035346727906264683596628903417932566383221754976804148878057310066885140776352202510584461556988179369177560403923399529842871087532495739921906849249072433614545319458973155343802539527630971239359995893495205324483418191744545506744253222956232506980824457995662900264427265978239540089825733734306363153471606200228841997928021468359645661221933848545854596097640552489404777927679709089475954033350287287833943519423030861868256961619722983499902810335
a = [35,51,91,115,123,187,235,267,403,427]
b = [427,403,267,235,187,123,115,91,51,35]
def roots_of_unity(e, phi, n, rounds=250):
phi_coprime = phi
while gcd(phi_coprime, e) != 1:
phi_coprime //= gcd(phi_coprime, e)
roots = set(pow(i, phi_coprime, n) for i in range(1, rounds))
assert all(pow(root, e, n) == 1 for root in roots)
return roots, phi_coprime
start_time = time.time()
for D in b:
p, q = factorize(n, D)
assert p*q == n
phi = (p - 1) * (q-1)
roots, phi_coprime = roots_of_unity(e, phi, n)
d = inverse_mod(e, phi_coprime)
pt = pow(c, d, n)
assert pow(pt, e, n) == c
pts = [(pt * root) % n for root in roots]
pts = [long_to_bytes(int(pt)) for pt in pts]
for pt in pts:
if b'flag' in pt:
end_time = time.time()
print(pt, 'time:', end_time-start_time)
break
|
