## Hack.lu 2020 - Bad Primes [EN]

This was a crypto challenge at Hack.lu 2020, solved by 86 teams.

We are given the following script:

#!/usr/bin/env python2
import binascii

# https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
def xgcd(a, b):
x0, x1, y0, y1 = 0, 1, 1, 0
while a != 0:
(q, a), b = divmod(b, a), a
y0, y1 = y1, y0 - q * y1
x0, x1 = x1, x0 - q * x1
return b, x0, y0

# https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
def modinv(a, m):
g, x, y = xgcd(a, m)
if g != 1:
return None
else:
return x % m

n = 3283820208958447696987943374117448908009765357285654693385347327161990683145362435055078968569512096812028089118865534433123727617331619214412173257331161
p = 34387544593670505224894952205499074005031928791959611454481093888481277920639
q = 95494466027181231798633086231116363926111790946014452380632032637864163116199
e = 65537

# flag = "flag{...}"
# flag = int(binascii.hexlify(flag), 16)
# flag = pow(flag, e, n)
flag = 2152534604028570372634288477962037445130495144236447333908131330331177601915631781056255815304219841064038378099612028528380520661613873180982330559507116
d = modinv(e, (p - 1) * (q - 1))
if d == None:
print "definitely too primitive..."
else:
print pow(flag, d, n)


which is written in python 2 D: .

The problem can be formalised as follows. We have a standard RSA modulus, formed of two primes $$p$$ and $$q$$, which are given. We also have $$e$$, and the ciphertext ($$c$$) , which is the RSA encryption of the flag.

The issue here is that $$e$$ is not coprime to $$\varphi(n) = (p-1) \times (q - 1)$$. Thus, $$e$$ has no invert mod $$\varphi(n)$$ and we can't proceed to the classical RSA decryption, despite having the factorisation of $$n$$.

# nth root for the win

The RSA cryptosystem's security depends on the factorisation of $$n$$, but also on the fact that computing the $$e$$th root of some number modulo a composite modulus without knowing its factorisation is hard.

But here, we have that factorisation. The solution I found is to split the problem in two subproblems, mod $$p$$ and mod $$q$$. Finding the $$e$$th root of $$c_q = c \mod q$$ is easy, because $$q$$ is prime (one can find the solution using a generalisation of the Tonneli-Shanks algorithm for instance. Check this stackexchange thread for more informations about that.)

After computing $$r_q$$ and $$r_p$$, two $$e$$th roots of $$c_q$$ and $$c_p$$ mod $$q$$ and $$p$$ respectively, one can combine the two results to find $$r \mod n$$ using the Chinese Remainder Theorem.

However, as explained in the stackexchange above, we still have an issue regarding the roots : $$r_p$$ and $$r_q$$ are not necessarly unique.

Here, $$p - 1 = 2 \times 65537 \times 262352141490078163670102020274799533126569180706773360502320016849117887$$ and $$q - 1 = 2 \times 47747233013590615899316543115558181963055895473007226190316016318932081558099$$.

We have $$gcd(e, p - 1) = e$$, so we'll have to find the right $$r_p$$ between exactly $$e$$ possible roots. But $$gcd(e, q - 1) = 1$$, so $$r_q$$ is actually unique.

Here is an implementation of this attack using sagemath:

from Crypto.Util.number import long_to_bytes
from sage.all import *
e = 65537
n = 3283820208958447696987943374117448908009765357285654693385347327161990683145362435055078968569512096812028089118865534433123727617331619214412173257331161
p = 34387544593670505224894952205499074005031928791959611454481093888481277920639
q = 95494466027181231798633086231116363926111790946014452380632032637864163116199
c = 2152534604028570372634288477962037445130495144236447333908131330331177601915631781056255815304219841064038378099612028528380520661613873180982330559507116

rmodp = Mod(c % p, p).nth_root(e, all=True)
rq = Mod(c % q, q).nth_root(e)

for rp in rmodp:

r = crt(int(rp), int(rq), p, q)
flag = long_to_bytes(r)

if b"flag" in flag:
print(flag.decode())


which yields flag{thanks_so_much_for_helping_me_with_these_primitive_primes} :-) .