β¬… BACK
Crypto CTF 2021 Writeups

There were many nice challenges in this year's Crypto CTF. Here are writeups for just a few. Thanks to the organisers for the fun CTF.

It was nice to watch the scoreboard. The performance of some of the solo players was really impressive and of course, it was unsurprising that Super Guesser and CryptoHackers did so well. I played with πŸ›ΉπŸ» and we finished in 9th.


Challenge Tags Points Solves
Triplet RSA primes 91 50
Ferman diophantine equations 134 31
RSAphantine RSA diophantine equations 142 29

Triplet

Fun with RSA, three times!

nc 07.cr.yp.toc.tf 18010

To get the flag, we need to send the server 3 pairs of primes (p1,q1),(p2,q2),(p3,q3)(p_1, q_1), (p_2, q_2), (p_3, q_3) for 3 RSA moduli N1=p1q1,N2=p2q2,N3=p3q3N_1 = p_1 q_1, N_2 = p_2 q_2, N_3 = p_3 q_3 and an exponent pair (e,d)(e, d) such that ed≑1(modΟ†(Ni))ed \equiv 1 \pmod{\varphi(N_i)} for i=1,2,3i = 1, 2, 3.

Our primes and exponent pair must satisfy the following:

  • pip_i and qiq_i are at least 160 bits
  • Niβ‰ NjN_i \neq N_j for iβ‰ ji \neq j (the three moduli must be unique)
  • 1<e,d<Ο†(Ni)1 < e, d < \varphi(N_i) (the exponent pair must be smaller than the smallest value of Ο†(Ni)\varphi(N_i))

Solution

We first note that if we choose the RSA moduli NiN_i such that all have the same phi value, then the task of finding the exponent pair is equivalent to finding an exponent pair for just one of the moduli; in this case, we can just take e = 0x10001 and compute the inverse modulo Ο†(Ni)\varphi(N_i) as usual.

The idea will be to choose an initial pair of primes (p1,q1)(p_1, q_1) such that they are both quite a bit larger than 160 bits, and that p1βˆ’1p_1 - 1 and q1βˆ’1q_1 - 1 are very smooth. Then, we consider the prime factorisation of Ο†(N1)\varphi(N_1):

Ο†(N1)=Ο†(p1q1)=(p1βˆ’1)(q1βˆ’1)=r1e1β‹―rkek\varphi(N_1) = \varphi(p_1 q_1) = (p_1 - 1)(q_1 - 1) = r_1^{e_1} \cdots r_k^{e_k}

To find primes different to p1p_1 and q1q_1, but still satisfy the desired property of having the same phi value, we split the prime factors of Ο†(N1)\varphi(N_1) into two almost equally sized partitions to get ri1ei1β‹―rimeimr_{i_1}^{e_{i_1}} \cdots r_{i_m}^{e_{i_m}} and rj1ej1β‹―rjkβˆ’mejkβˆ’mr_{j_1}^{e_{j_1}} \cdots r_{j_{k-m}}^{e_{j_{k-m}}}. To put it in simpler words, and without the potentially confusing notation, we aim to find two similarly sized divisors s1,s2s_1, s_2 of Ο†(N1)\varphi(N_1). Then, we simply check if p2=s1+1p_2 = s_1 + 1 and q2=s2+1q_2 = s_2 + 1 are prime. If they are, then clearly

Ο†(p2q2)=(p2βˆ’1)(q2βˆ’1)=s1s2=Ο†(N1)\varphi(p_2q_2) = (p_2 - 1)(q_2 - 1) = s_1 s_2 = \varphi(N_1)

We can repeat this (by choosing different divisors s1,s2s_1, s_2) as many times as we need to to get different prime pairs.

Note that we need s1s_1 and s2s_2 to be even to have a chance of s1+1s_1 + 1 and s2+1s_2 + 1 being prime, so we make sure to include a factor of 22 in both of them.

def gen_smooth_prime(nbits):
    while True:
        p = 1
        for q in primes(2^nbits):
            r = randint(1, 2)
            p *= pow(q, r)
            if p.nbits() > nbits:
                break
        if is_prime(p+1):
            return p+1

p1, q1 = gen_smooth_prime(300), gen_smooth_prime(300)
phi1 = (p1 - 1)*(q1 - 1)

facs = list(factor(phi1))
count = 0
print('prime pairs:')
print(f'{p1},{q1}')
while True:
    t1 = sample(facs[1:], len(facs)//2 + randint(-4, 4))
    t2 = set(facs) - set(t1) - {facs[0]}
    p2 = 2*prod(f^e for f,e in t1) + 1
    q2 = 2^(facs[0][1] - 1)*prod(f^e for f,e in t2) + 1
    if p2.is_prime() and q2.is_prime():
        assert phi1 == (p2-1)*(q2-1)
        print(f'{p2},{q2}')
        if count == 1:
            break
        count += 1

e = 0x10001
d = pow(e, -1, phi1)
print()
print('exponent pair:')
print(f'{e},{d}')

Ferman

Modern cryptographic algorithms are the theoretical foundations and the core technologies of information security. Should we emphasize more?

nc 07.cr.yp.toc.tf 22010

The interactivity with the remote server is not particularly very important, so we grabbed some values and worked offline. Here's what the interaction with the server looks like:

❯ nc 07.cr.yp.toc.tf 22010
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+  hi talented participants, welcome to the FERMAN cryptography task!  +
+  Solve the given equations and decrypt the encrypted flag! Enjoy!    +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

| Parameters generation is a bit time consuming, so please be patient :P
| Options:
|	[P]rint encrypted flag
|	[R]eveal the parameters
|	[Q]uit
r
	e = 65537
	isPrime(p) = True
	isPrime(q) = True
	n = p * q
	(p - 656)**2 + (q - 963)**2 = 3320202784812492330524490070537298583580475358728548450007948498435239404111383935472261393153166267639712257379031535179757548500400989893135081700970178060731084720932889896961295442669803924366240918974546190378390524119382950641285466715346539970610795416980113620249722177226012210564608518035226805407159423864613167407510858568222756127114517158647307638966636861101918323443741159674068413027798613063956533716357312649744435105541692341025142443453616433300402390327321129
	m = bytes_to_long(flag)
	c = pow(m, e, n)
| Options:
|	[P]rint encrypted flag
|	[R]eveal the parameters
|	[Q]uit
p
| encrypt(flag) = 1104552869259054521320459367215205626307072267713253798487395615599865150615771104210691655958867232905435965207275223405884336508705421612571892516997702690774343722384031828549716175794614885021763173120483549596738691533657148009164935996329052504823588221426893090823846947987588608932372042376308326711740581622433481157049398998776013192643927768389651965126117335138857001495164685386619396295392630764239886619115390547376034863534317835500091461280756813701014618629853884
| Options:
|	[P]rint encrypted flag
|	[R]eveal the parameters
|	[Q]uit

We have the ciphertext for the flag encrypted with RSA, and a hint about the RSA primes. The hint ss is of the form

s=(pβˆ’Ξ±)2+(qβˆ’Ξ²)2s = (p - \alpha)^2 + (q - \beta)^2

So the task is essentially to solve this diophantine equation.

Solution

Let x=pβˆ’Ξ±x = p - \alpha and y=qβˆ’Ξ²y = q - \beta. Then we can write the hint as s=x2+y2s = x^2 + y^2.

Let's shift gears a bit and think about Gaussian integers. We know that Z[i]\mathbb{Z}[i] is a unique factorisation domain, and that

(x+iy)(xβˆ’iy)=(y+ix)(yβˆ’ix)=x2+y2(x + iy)(x - iy) = (y + ix)(y - ix) = x^2 + y^2

So, we consider the factorisation of the hint ss over the Gaussian integers. In our testing with challenge numbers, we get factorisations with not too many different prime factors. The powers of the primes are also 77, because the challenge is actually to solve x2+y2=z7x^2 + y^2 = z^7. Anyway, once we have the factorisation:

s=(a1+ib1)7(a1βˆ’ib1)7β‹―(ak+ibk)7(akβˆ’ibk)7s = (a_1 + ib_1)^7 (a_1 - ib_1)^7 \cdots (a_k + ib_k)^7 (a_k - ib_k)^7

we simply need to choose the (ajΒ±ibj)7(a_j \pm ib_j)^7 terms appropriately and take their product to get one of (x+iy),(xβˆ’iy),(y+ix),(yβˆ’ix)(x + iy), (x - iy), (y + ix), (y - ix). There aren't too many ways to do this, so we just did it manually. Once we have the correct values, we simply take the real and imaginary parts to recover xx and yy. Recovering the primes and thus the flag from this is easy.

from Crypto.Util.number import long_to_bytes

e = 0x10001
c = 2254884511760692550543677177759701327385916425638857251126801005946302220594969474007235171826406865116904613234708577176193957169044090181008427239149308498911578576404808085754865583458844853911431912414771393171813616723744945862448127037501972593643480664587668139499559072554986557545670814778161056994439017826806214489778370715050732844914879377800709399264478886080667231426416093924167450380285443383329398751446093707481626190287153066067239104010982192806032469953797692
alpha, beta = 376, 285
hint = 8932410804466210082068798293693440485791235351577787607682543627874077237652613687000149969398153796005182002677981273951231025004556834240441605542480699383049424620513640705965605366578690748579581927148477562534345010789773556995222478556690487069685566513042054146660803746131657685907282750658593623768822022360014471309514302308794051826808802146162347635902079732296897262491333163698159687407311734313946638466275288441219473689779526045432152213384544079326883483000826693

# GI = GaussianIntegers()
# print(GI(hint).factor())

f1 = (-101487776001296269045575*I + 3449364511579014288098614)^7
f2 = (-382409921*I - 947430964)^7
f3 = (-5*I + 4)^7
x_iy = f1*f2*f3
y = abs(x_iy.real())
x = abs(x_iy.imag())
p, q = x + alpha, y + beta
assert (p - alpha)^2 + (q - beta)^2 == hint
d = pow(e, -1, (p-1)*(q-1))
m = pow(c, int(d), p*q)
print(long_to_bytes(m).decode())

RSAphantine

RSA and solving equations, but should be a real mathematician to solve it with a diophantine equation?

2*z**5 - x**3 + y*z = 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613520747411963822349374260144229698759495359592287331083229572369186844312169397998958687629858407857496154424105344376591742814310010312178029414792153520127354594349356721
x**4 + y**5 + x*y*z = 89701863794494741579279495149280970802005356650985500935516314994149482802770873012891936617235883383779949043375656934782512958529863426837860653654512392603575042842591799236152988759047643602681210429449595866940656449163014827637584123867198437888098961323599436457342203222948370386342070941174587735051
y**6 + 2*z**5 + z*y = 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613609786612391835856376321085593999733543104760294208916442207908167085574197779179315081994735796390000652436258333943257231020011932605906567086908226693333446521506911058
p = nextPrime(x**2 + z**2 + y**2 << 76)
q = nextPrime(z**2 + y**3 - y*x*z ^ 67)
n, e = p * q, 31337
m = bytes_to_long(FLAG)
c = pow(m, e, n)
c = 486675922771716096231737399040548486325658137529857293201278143425470143429646265649376948017991651364539656238516890519597468182912015548139675971112490154510727743335620826075143903361868438931223801236515950567326769413127995861265368340866053590373839051019268657129382281794222269715218496547178894867320406378387056032984394810093686367691759705672

We are given the flag encrypted with RSA, and some hints about the prime generation. The task is essentially to recover x,yx, y and zz given the values c1,c2,c3c_1, c_2, c_3 satisfying:

2z5βˆ’x3+yz=c1x4+y5+xyz=c2y6+2z5+zy=c3\begin{aligned} 2z^5 - x^3 + yz &= c_1 \\ x^4 + y^5 + xyz &= c_2 \\ y^6 + 2z^5 + zy &= c_3 \end{aligned}

Solution

The first thing we noticed was that c1c_1 and c3c_3 are close. The terms 2z52z^5 and zyzy appear in both, so subtracting them seems like a good idea. We get

(y6+2z5+zy)βˆ’(2z5βˆ’x3+yz)=c3βˆ’c1β€…β€ŠβŸΉβ€…β€Šy6+x3=c3βˆ’c1β€…β€ŠβŸΉβ€…β€Š(y2)3+x3=c3βˆ’c1β€…β€ŠβŸΉβ€…β€Š(y2+x)(x2βˆ’xy2+y4)=c3βˆ’c1sumΒ ofΒ cubes\begin{aligned} (y^6 + 2z^5 + zy) - (2z^5 - x^3 + yz) &= c_3 - c_1 \\ \implies y^6 + x^3 &= c_3 - c_1 \\ \implies (y^2)^3 + x^3 &= c_3 - c_1 \\ \implies (y^2 + x)(x^2 - xy^2 + y^4) &= c_3 - c_1 \qquad \text{sum of cubes} \end{aligned}

We can then factor c3βˆ’c1c_3 - c_1 and notice that it has a suspicious and small factor Ξ΄\delta: 3133713317731333. Therefore, we suppose y2+x=Ξ΄y^2 + x = \delta. Write x=Ξ΄βˆ’y2x = \delta - y^2 and substitute this into y6+x3=c3βˆ’c1y^6 + x^3 = c_3 - c_1 to get:

y6+(Ξ΄βˆ’y2)3=c3βˆ’c1y^6 + (\delta - y^2)^3 = c_3 - c_1

We do not need to bother doing any more work; this is a univariate polynomial in yy and we can easily solve for its roots! This allows us to recover yy. Once we have yy, we get xx for free since x=Ξ΄βˆ’y2x = \delta - y^2. Finally, we recover zz by plugging in our values for xx and yy into the second equation x4+y5+xyz=c2x^4 + y^5 + xyz = c_2.

from Crypto.Util.number import long_to_bytes

c1 = 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613520747411963822349374260144229698759495359592287331083229572369186844312169397998958687629858407857496154424105344376591742814310010312178029414792153520127354594349356721
c2 = 89701863794494741579279495149280970802005356650985500935516314994149482802770873012891936617235883383779949043375656934782512958529863426837860653654512392603575042842591799236152988759047643602681210429449595866940656449163014827637584123867198437888098961323599436457342203222948370386342070941174587735051
c3 = 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613609786612391835856376321085593999733543104760294208916442207908167085574197779179315081994735796390000652436258333943257231020011932605906567086908226693333446521506911058

R.<x,y,z> = PolynomialRing(QQ)
delta = 3133713317731333
f1 = y^6 + (delta - y^2)^3 - (c3 - c1)
y = f1.univariate_polynomial().roots()[0][0]
x = delta - y^2
f2 = x^4 + y^5 + x*y*z - c2
z = f2.univariate_polynomial().roots()[0][0]

x = int(x)
y = int(y)
z = int(z)

p = Integer(x**2 + z**2 + y**2 << 76).next_prime()
q = Integer(z**2 + y**3 - y*x*z ^^ 67).next_prime()
n, e = p * q, 31337
c = 486675922771716096231737399040548486325658137529857293201278143425470143429646265649376948017991651364539656238516890519597468182912015548139675971112490154510727743335620826075143903361868438931223801236515950567326769413127995861265368340866053590373839051019268657129382281794222269715218496547178894867320406378387056032984394810093686367691759705672
d = pow(e, -1, (p-1)*(q-1))
m = pow(c, int(d), n)
print(long_to_bytes(m).decode())