Reasonably Suspicious Acronym - Teaser CONFidence 2019

tl;dr Coppersmith’s Attack to recover RSA primes

Challenge Points: 200
Challenge Solves:
Solved by: s0rc3r3r, v4d3r, nsg99, 4lph4

The challenge is based on RSA and we are given the following script:

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)))

We are given ciphertext of two plaintext messages $ m_1 $ “You can’t factor the modulus” and $ m_2 $ “If you
don’t know the modulus!”, and encrypted text of the flag in output.txt:

msg1 = 4249729541274832324831915101850978041491970958978013333892918723306168770472089196478720527554982764987079625218029445015042835412969986610407794962546486526768377464483162272541733624521350257458334912357961557141551376502679112069746250223130120067678503609054343306910481618502449487751467838568736395758064426403381068760701434585433915614901796040740316824283643177505677105619002929103619338876322183416750542848507631412106633630984867562243228659040403724671325236096319784525457674398019860558530212905126133378508676777200538275088387251038714220361173376355185449239483472545370043145325106307606431828449482078191
msg2 = 13075855845498384344820257559893309320125843093107442572680776872299102248743866420640323500087788163238819301260173322187978140866718036292385520509724506487692001245730298675731681509412177547061396861961413760298064385526657135656283464759479388590822600747903100354135682624356454872283852822117199641700847558605700370117557855396952083088645477966782338316017387406733063346986224014837246404581562813312855644424128648363175792786282857154624788625411070173092512834181678732914231669616670515512774709315620233482515821178277673737845032672993814500177126048019814877397547310166915188341668439101769932492677363463422
flag = 1325070956009103489249194637347510588506729608784127511926628895543304940415297099207601498626181915901848862854995077315475674257593360012633818395699000501896896712855638114932274873636706679536094148084825113213348693669110684534612150434985589138003619494080556587882502882245480530148296233019306164832959924719530089539412878605051284492900919153291539285764067215954480046474237129247005910958854570936626494664674014970792183182621261776942952172643573955950074108555363333808330455648256916095619261620286120748266415219259665310637340092503523139379869446053982200858497231506892485419429178671743186148288407233657

Some observations:

1. We are not given the public modulus in this challenge.
2. Factors of the modulus n are derived and there exists a relation between them

Based on the above observations, one can say that the challenge can be solved in two steps:

1. Recover the public modulus using the ciphertext-plaintext pairs
2. Since there exists a relation between factors of n, recover factors based on this and decrypt the ciphertext of the flag.

Recovering the modulus

Let the ciphertext of message $ m_1 $ be $ c_1 $ and ciphertext of message $ m_2 $ be $ c_2 $. We can write:
$ m_1^e \equiv c_1\mod n $
$ m_2^e \equiv c_2\mod n $

This implies:
$ m_1^e - c_1 = k_1*n $
$ m_2^e - c_2 = k_2*n $
where $ k_1, k_2 \in \mathbb{Z}^+ $

Hence,
$ GCD(m_1^e - c_1, m_2^e - c_2) = GCD(k_1*n, k_2*n) = k’*n $

With the above equation we can recover a multiple of n, where k' is a small number and can be detected
simply by brute force. We wrote the following code using sagemath (python took longer time on our laptops
to calculate since the messages are quite large) to recover n

from Crypto.Util.number import *
from sage.all import *

c1 = 4249729541274832324831915101850978041491970958978013333892918723306168770472089196478720527554982764987079625218029445015042835412969986610407794962546486526768377464483162272541733624521350257458334912357961557141551376502679112069746250223130120067678503609054343306910481618502449487751467838568736395758064426403381068760701434585433915614901796040740316824283643177505677105619002929103619338876322183416750542848507631412106633630984867562243228659040403724671325236096319784525457674398019860558530212905126133378508676777200538275088387251038714220361173376355185449239483472545370043145325106307606431828449482078191
c2 = 13075855845498384344820257559893309320125843093107442572680776872299102248743866420640323500087788163238819301260173322187978140866718036292385520509724506487692001245730298675731681509412177547061396861961413760298064385526657135656283464759479388590822600747903100354135682624356454872283852822117199641700847558605700370117557855396952083088645477966782338316017387406733063346986224014837246404581562813312855644424128648363175792786282857154624788625411070173092512834181678732914231669616670515512774709315620233482515821178277673737845032672993814500177126048019814877397547310166915188341668439101769932492677363463422
flag = 1325070956009103489249194637347510588506729608784127511926628895543304940415297099207601498626181915901848862854995077315475674257593360012633818395699000501896896712855638114932274873636706679536094148084825113213348693669110684534612150434985589138003619494080556587882502882245480530148296233019306164832959924719530089539412878605051284492900919153291539285764067215954480046474237129247005910958854570936626494664674014970792183182621261776942952172643573955950074108555363333808330455648256916095619261620286120748266415219259665310637340092503523139379869446053982200858497231506892485419429178671743186148288407233657
m1 = bytes_to_long("You can't factor the modulus")
m2 = bytes_to_long("If you don't know the modulus!")
e = 65537

N = GCD(pow(m1, e) - c1, pow(m2, e) - c2)
print N

Coincidentally, GCD gave us the exact value of n. We can verify this by simply encrypting the given messages $ m_1 $ and $ m_2 $ with our recovered modulus value and given exponent e, and check if they match with their corresponding given ciphertexts $ c_1 $ and $ c_2 $.

Running the above code gives the value of n as:

N = 34825223743402829383680359547814183240817664070909938698674658390374124787235739502688056639022131897715513587903467527066065545399622834534513631867145432553730850980331789931667370903396032758515681278057031496814054828419443822343986117760958186984521716807347123949922837482460532728350223473430713058522361175980521908817215812291272284241848086260180382693014713901303747444753828636575351349026883294939561001468099252543181336195746032718177937417431101756313823635150129601855358558635996348271242920308406268552606733676301725088348399264293936151662467456410825402303921583389167882090767423931762347825907802328053

Now that we have value of N, let’s move to the second and final step in solving the challenge!

Factoring N using Coppersmith’s Theorem

This step is almost the same as part-3 of Old-School challenge from Meepwn CTF 2018:
https://github.com/p4-team/ctf/tree/master/2018-07-13-meepwn-ctf/crypto_old_school#part3

We are given the following relation between p and q:

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

We can approximate the value of tmp and then try to recover p and q based on the approximation:

$ \Delta_1 = randint(2^{500}) $
$ \Delta_2 = randint(2^{500}) $
$ tmp = randint(2^{1023}, 2^{2014}) $

$ N = (0xdead*tmp + \Delta_1) * (0xbeef*tmp + \Delta_2)$
$ N = (0xdead*0xbeef)*tmp^2 + (0xdead*\Delta_2)*tmp + (0xbeef*\Delta_1)*tmp + (\Delta_1*\Delta_2) $
$ N = (0xdead*0xbeef)*tmp^2 + (0xdead*\Delta_2 + 0xbeef*\Delta_1)*tmp + (\Delta_1*\Delta_2) $
$ (0xdead*0xbeef)*tmp^2 + (0xdead*\Delta_2 + 0xbeef*\Delta_1)*tmp + (\Delta_1*\Delta_2 - N) == 0 $

We can take the approximate value of tmp as:
$ tmp\_approx = \sqrt{\frac{N}{0xdead*0xbeef}}$

With the above approximation, we can calculate the upper bound of one of
the factors of N, let’s say q_approx as:

$ q\_approx = 0xbeef*tmp\_approx - 2^{500} $

Note: We still don’t have a strong mathematical explanation as to why $ q\_approx = 0xbeef*tmp\_approx - 2^{500} $ and not $ q\_approx = 0xbeef*tmp\_approx + 2^{500} $, we
deduced the formula based on the writeup for Meepwn CTF challenge mentioned earlier.

s0rc3r3r discussed it with Shalom (challenge author) about this, but the reason is still not clear; here is an
excerpt of the conversation from IRC:

So if you have a mathematical explanation, feel free to comment! I would love it!

/EONote

Now that we have q_approx, we can use Coppersmith’s Theorem to recover the actual value of q. I wrote the following script for this:

hidden = 500
tmp = isqrt((N)/(0xdead * 0xbeef))
print "tmp: ", tmp
q_approx = 0xbeef*tmp - 2**500
print q_approx

F. = PolynomialRing(Zmod(N), implementation='NTL')
f = x - q_approx

roots = f.small_roots(X=2**hidden, beta=0.1)
for delta in roots:
    print('delta', delta)
    print('q_approx - delta', q_approx-delta)
    q = q_approx-delta
    p = int(N)/int(q)
    d = inverse_mod(65537, (p-1)*(q-1))
    print("d", d)
    decrypted = hex(int(pow(c,d,N)))
    print('flag =', decrypted[2:-1].decode("hex"))

Let us see how the above script works:
We know that q_approx is basically the upper bound for possible value of q. To get the actual value we need to subtract a value x from q_approx such that the result becomes a factor of modulus N.
Hence we wrote the script implementing the above idea!

If you want to learn about Coppersmith’s Attack in detail you can refer to this article from Crypton library:
https://github.com/ashutosh1206/Crypton/tree/master/RSA-encryption/Attack-Coppersmith

The full script (sagemath):

from Crypto.Util.number import *
from sage.all import *

c1 = 4249729541274832324831915101850978041491970958978013333892918723306168770472089196478720527554982764987079625218029445015042835412969986610407794962546486526768377464483162272541733624521350257458334912357961557141551376502679112069746250223130120067678503609054343306910481618502449487751467838568736395758064426403381068760701434585433915614901796040740316824283643177505677105619002929103619338876322183416750542848507631412106633630984867562243228659040403724671325236096319784525457674398019860558530212905126133378508676777200538275088387251038714220361173376355185449239483472545370043145325106307606431828449482078191
c2 = 13075855845498384344820257559893309320125843093107442572680776872299102248743866420640323500087788163238819301260173322187978140866718036292385520509724506487692001245730298675731681509412177547061396861961413760298064385526657135656283464759479388590822600747903100354135682624356454872283852822117199641700847558605700370117557855396952083088645477966782338316017387406733063346986224014837246404581562813312855644424128648363175792786282857154624788625411070173092512834181678732914231669616670515512774709315620233482515821178277673737845032672993814500177126048019814877397547310166915188341668439101769932492677363463422
flag = 1325070956009103489249194637347510588506729608784127511926628895543304940415297099207601498626181915901848862854995077315475674257593360012633818395699000501896896712855638114932274873636706679536094148084825113213348693669110684534612150434985589138003619494080556587882502882245480530148296233019306164832959924719530089539412878605051284492900919153291539285764067215954480046474237129247005910958854570936626494664674014970792183182621261776942952172643573955950074108555363333808330455648256916095619261620286120748266415219259665310637340092503523139379869446053982200858497231506892485419429178671743186148288407233657
m1 = bytes_to_long("You can't factor the modulus")
m2 = bytes_to_long("If you don't know the modulus!")
e = 65537

N = 34825223743402829383680359547814183240817664070909938698674658390374124787235739502688056639022131897715513587903467527066065545399622834534513631867145432553730850980331789931667370903396032758515681278057031496814054828419443822343986117760958186984521716807347123949922837482460532728350223473430713058522361175980521908817215812291272284241848086260180382693014713901303747444753828636575351349026883294939561001468099252543181336195746032718177937417431101756313823635150129601855358558635996348271242920308406268552606733676301725088348399264293936151662467456410825402303921583389167882090767423931762347825907802328053

c = flag

hidden = 500
tmp = isqrt((N)/(0xdead * 0xbeef))
print "tmp: ", tmp
q_approx = 0xbeef*tmp - 2**500
print q_approx

F. = PolynomialRing(Zmod(N), implementation='NTL')
f = x - q_approx

roots = f.small_roots(X=2**hidden, beta=0.1)
for delta in roots:
    print('delta', delta)
    print('q_approx - delta', q_approx-delta)
    q = q_approx-delta
    p = int(N)/int(q)
    d = inverse_mod(65537, (p-1)*(q-1))
    print("d", d)
    decrypted = hex(int(pow(c,d,N)))
    print('flag =', decrypted[2:-1].decode("hex"))

Running the above script gives us the flag: p4{S3cur1ty_th0ru9h_0b5cur1ty_4t_i7s_fin3s7}