Rating: 4.5

We are given the following script:

```python

#!/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](https://crypto.stackexchange.com/questions/6518/finding-roots-in-mathbbz-p) 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](https://en.wikipedia.org/wiki/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 uniques.

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:

```python

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

Original writeup (https://www.w0nderland.fr/hacklu-2020-bad-primes-en.html).