Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
ashutosh1206
GitHub Repository: ashutosh1206/crypton
 Path: blob/master/RSA-encryption/Attack-Coppersmith/Challenges/Really-Suspicious-Acronym/exploit.sage
1403 views
1
from Crypto.Util.number import *

2
from sage.all import *

3


4
c1 = 4249729541274832324831915101850978041491970958978013333892918723306168770472089196478720527554982764987079625218029445015042835412969986610407794962546486526768377464483162272541733624521350257458334912357961557141551376502679112069746250223130120067678503609054343306910481618502449487751467838568736395758064426403381068760701434585433915614901796040740316824283643177505677105619002929103619338876322183416750542848507631412106633630984867562243228659040403724671325236096319784525457674398019860558530212905126133378508676777200538275088387251038714220361173376355185449239483472545370043145325106307606431828449482078191

5
c2 = 13075855845498384344820257559893309320125843093107442572680776872299102248743866420640323500087788163238819301260173322187978140866718036292385520509724506487692001245730298675731681509412177547061396861961413760298064385526657135656283464759479388590822600747903100354135682624356454872283852822117199641700847558605700370117557855396952083088645477966782338316017387406733063346986224014837246404581562813312855644424128648363175792786282857154624788625411070173092512834181678732914231669616670515512774709315620233482515821178277673737845032672993814500177126048019814877397547310166915188341668439101769932492677363463422

6
flag = 1325070956009103489249194637347510588506729608784127511926628895543304940415297099207601498626181915901848862854995077315475674257593360012633818395699000501896896712855638114932274873636706679536094148084825113213348693669110684534612150434985589138003619494080556587882502882245480530148296233019306164832959924719530089539412878605051284492900919153291539285764067215954480046474237129247005910958854570936626494664674014970792183182621261776942952172643573955950074108555363333808330455648256916095619261620286120748266415219259665310637340092503523139379869446053982200858497231506892485419429178671743186148288407233657

7
m1 = bytes_to_long("You can't factor the modulus")

8
m2 = bytes_to_long("If you don't know the modulus!")

9
e = 65537

10


11
N = 34825223743402829383680359547814183240817664070909938698674658390374124787235739502688056639022131897715513587903467527066065545399622834534513631867145432553730850980331789931667370903396032758515681278057031496814054828419443822343986117760958186984521716807347123949922837482460532728350223473430713058522361175980521908817215812291272284241848086260180382693014713901303747444753828636575351349026883294939561001468099252543181336195746032718177937417431101756313823635150129601855358558635996348271242920308406268552606733676301725088348399264293936151662467456410825402303921583389167882090767423931762347825907802328053

12


13
c = flag

14


15
hidden = 500

16
tmp = isqrt((N)/(0xdead * 0xbeef))

17
print "tmp: ", tmp

18
q_approx = 0xbeef*tmp - 2**500

19
print q_approx

20


21
F.<x> = PolynomialRing(Zmod(N), implementation='NTL')

22
f = x - q_approx

23


24
roots = f.small_roots(X=2**hidden, beta=0.1)

25
for delta in roots:

26
    print('delta', delta)

27
    print('q_approx - delta', q_approx-delta)

28
    q = q_approx-delta

29
    p = int(N)/int(q)

30
    d = inverse_mod(65537, (p-1)*(q-1))

31
    print("d", d)

32
    decrypted = hex(int(pow(c,d,N)))

33
    print('flag =', decrypted[2:-1].decode("hex"))

34


35