Bad Primes

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} :-) .