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