Teaser CONFidence CTF 2019 - Really Suspicious Acronym
17 Mar 2019tldr; RSA factorization with approximated p/q ratio
Description:
You can't break my public key if you don't know it, amirite?
The flag format is: p4{letters_digits_and_special_characters}.
Task source code:
def bytes_to_long(data):
return int(data.encode("hex"),16)
def rsa(msg,e,n):
return pow(bytes_to_long(msg),e,n)
flag = open('flag.txt','r').read()
tmp = randint(2**1023, 2**1024)
e = 65537
p = next_prime(0xDEAD*tmp+randint(2, 2**500))
q = next_prime(0xBEEF*tmp+randint(2, 2**500))
N = p*q
print('msg1 = '+str(rsa("You can't factor the modulus",e,N)))
print('msg2 = '+str(rsa("If you don't know the modulus!",e,N)))
print('flag = '+str(rsa(flag,e,N)))
Data:
msg1 = 4249729541274832324831915101850978041491970958978013333892918723306168770472089196478720527554982764987079625218029445015042835412969986610407794962546486526768377464483162272541733624521350257458334912357961557141551376502679112069746250223130120067678503609054343306910481618502449487751467838568736395758064426403381068760701434585433915614901796040740316824283643177505677105619002929103619338876322183416750542848507631412106633630984867562243228659040403724671325236096319784525457674398019860558530212905126133378508676777200538275088387251038714220361173376355185449239483472545370043145325106307606431828449482078191
msg2 = 13075855845498384344820257559893309320125843093107442572680776872299102248743866420640323500087788163238819301260173322187978140866718036292385520509724506487692001245730298675731681509412177547061396861961413760298064385526657135656283464759479388590822600747903100354135682624356454872283852822117199641700847558605700370117557855396952083088645477966782338316017387406733063346986224014837246404581562813312855644424128648363175792786282857154624788625411070173092512834181678732914231669616670515512774709315620233482515821178277673737845032672993814500177126048019814877397547310166915188341668439101769932492677363463422
flag = 1325070956009103489249194637347510588506729608784127511926628895543304940415297099207601498626181915901848862854995077315475674257593360012633818395699000501896896712855638114932274873636706679536094148084825113213348693669110684534612150434985589138003619494080556587882502882245480530148296233019306164832959924719530089539412878605051284492900919153291539285764067215954480046474237129247005910958854570936626494664674014970792183182621261776942952172643573955950074108555363333808330455648256916095619261620286120748266415219259665310637340092503523139379869446053982200858497231506892485419429178671743186148288407233657
First we need to find the modulus. It’s quite easy:
\[\begin{eqnarray} pla_1^{e} \equiv msg_1 \mod n \nonumber \\ pla_2^{e} \equiv msg_2 \mod n \nonumber \\ \\ s_1 = pla_1^{e} - msg_1 = k_1 * n \nonumber \\ s_2 = pla_2^{e} - msg_2 = k_2 * n \nonumber \\ \nonumber \\ n = \frac{gcd(s1,s2)}{k} \nonumber \end{eqnarray}\]and $k$ should be small.
One the modulus is known, we need to factorize it. To do this, observe that:
\[\begin{eqnarray} n = p * q \nonumber \\ p = x_1 * y + a \nonumber \\ q = x_2 * y + b \\ \frac{p}{q} \approx \frac{x_1}{x_2} \nonumber \\ \end{eqnarray}\]We known approximation of p/q. Now we can calculate:
\[\begin{eqnarray} p' = \sqrt{n * \frac{x_1}{x_2}} \approx \sqrt{n * \frac{p}{q}} = p \end{eqnarray}\]Both $a$ and $b$ are about 500 bits long, and $p$, $q$ are about 1024 bits long. A difference between p’ and p should be about 500 bits, so it is small and we can use Coppersmith’s theorem to find p.
Solution:
#!/usr/bin/env sage
def bytes_to_long(data):
return int(data.encode("hex"),16)
msg1 = 4249729541274832324831915101850978041491970958978013333892918723306168770472089196478720527554982764987079625218029445015042835412969986610407794962546486526768377464483162272541733624521350257458334912357961557141551376502679112069746250223130120067678503609054343306910481618502449487751467838568736395758064426403381068760701434585433915614901796040740316824283643177505677105619002929103619338876322183416750542848507631412106633630984867562243228659040403724671325236096319784525457674398019860558530212905126133378508676777200538275088387251038714220361173376355185449239483472545370043145325106307606431828449482078191
msg2 = 13075855845498384344820257559893309320125843093107442572680776872299102248743866420640323500087788163238819301260173322187978140866718036292385520509724506487692001245730298675731681509412177547061396861961413760298064385526657135656283464759479388590822600747903100354135682624356454872283852822117199641700847558605700370117557855396952083088645477966782338316017387406733063346986224014837246404581562813312855644424128648363175792786282857154624788625411070173092512834181678732914231669616670515512774709315620233482515821178277673737845032672993814500177126048019814877397547310166915188341668439101769932492677363463422
flag = 1325070956009103489249194637347510588506729608784127511926628895543304940415297099207601498626181915901848862854995077315475674257593360012633818395699000501896896712855638114932274873636706679536094148084825113213348693669110684534612150434985589138003619494080556587882502882245480530148296233019306164832959924719530089539412878605051284492900919153291539285764067215954480046474237129247005910958854570936626494664674014970792183182621261776942952172643573955950074108555363333808330455648256916095619261620286120748266415219259665310637340092503523139379869446053982200858497231506892485419429178671743186148288407233657
pla1 = bytes_to_long("You can't factor the modulus")
pla2 = bytes_to_long("If you don't know the modulus!")
e = 65537
n = None
# n = 34825223743402829383680359547814183240817664070909938698674658390374124787235739502688056639022131897715513587903467527066065545399622834534513631867145432553730850980331789931667370903396032758515681278057031496814054828419443822343986117760958186984521716807347123949922837482460532728350223473430713058522361175980521908817215812291272284241848086260180382693014713901303747444753828636575351349026883294939561001468099252543181336195746032718177937417431101756313823635150129601855358558635996348271242920308406268552606733676301725088348399264293936151662467456410825402303921583389167882090767423931762347825907802328053
if n is None:
n1 = pla1^e - msg1
n2 = pla2^e - msg2
n = gcd(n1, n2)
x1, x2 = 0xDEAD, 0xBEEF
r = x1 / x2
nn = RealField(2000)(n)
pp = int(sqrt(nn*r)) # p', close to p
F.<x> = PolynomialRing(Zmod(n), implementation='NTL');
pol = x - pp
beta = 0.4 # p >= n^beta
X = 2**500 # |pp - p| < X
roots = pol.small_roots(X=X, beta=beta)
print 'roots:', roots
p = int(pp - roots[0])
assert n % p == 0
print 'p: ', p
q = n // p
d = inverse_mod(e, (p-1)*(q-1))
flag_plain = int(pow(flag, d, n))
print 'flag: ', hex(flag_plain).lstrip('0x').rstrip('L').decode('hex')
# p4{S3cur1ty_th0ru9h_0b5cur1ty_4t_i7s_fin3s7}