same
2 minutes to read
We are given the source code in Python to encrypt the flag:
from Crypto.Util.number import getPrime, bytes_to_long
m = bytes_to_long(open("flag", "rb").read())
n = getPrime(512)*getPrime(512)
e = [1337,31337]
print(n)
print(pow(m,e[0],n))
print(pow(m,e[1],n))
And we have the output of the program:
88627598925887227793409704066287679810103408445903546693879278352563489802835708613718629728355698762251810901364530308365201192197988674078034209878433048946797619290221501750862580914894979204943093716650072734138749420932619469204815802746273252727013183568196402223549961607284086898768583604510696483111
45254947860172381004009381991735702721210786277711531577381599020185600496787746985669891424940792336396574951744089759764874889285927022268694128526139687661305707984329995359802337446670063047702309778972385903473896687843125261988493615328641864610786785749566148338268077425756876069789788618208807001704
16054811947596452078263236160429328686151351092304509270058479526590947874445940946506791900760052230887962479603369427120610506778471930164144528718052332194666418267005043709704814833963217926271924910466448499814399455203725279998913865531351070938872586642424346857094632491904168889134624707595846754719
The cryptosystem is RSA, but there’s a vulnerability. The flag ($m$) is being encrypted two times as
$$ c_1 = m ^ {e_1} \mod{n} $$
$$ c_2 = m ^ {e_2} \mod{n} $$
The problem here is that the same message is raised to a different power but using the same modulus $n$.
From Bezout’s identity, given non-zero integers $a, b$ there exist integers $u, v$ such that
$$ u \cdot a + v \cdot b = \gcd{(a, b)} $$
Since $\gcd{(e_1, e_2)} = 1$, we can find $u$ and $v$ such that
$$ u \cdot e_1 + v \cdot e_2 = 1 $$
The idea is find those values to calculate the message $m$ in this way:
$$ c_1^u \cdot c_2^v = (m^{e_1})^u \cdot (m^{e_2})^v = m^{u \cdot e_1} \cdot m^{v \cdot e_2} = m^{u \cdot e_1 + v \cdot e_2} = m \mod{n} $$
The values $u, v$ can be calculated using the extended GCD (Extended Euclidean algorithm).
So this is the code used to get the flag:
$ python3 -q
>>> def extended_gcd(a, b):
... if a % b:
... u, v, d = extended_gcd(b, a % b)
... return v, (d - a * v) // b, d
... return 0, 1, b
...
>>> e1, e2 = 1337, 31337
>>> n = 88627598925887227793409704066287679810103408445903546693879278352563489802835708613718629728355698762251810901364530308365201192197988674078034209878433048946797619290221501750862580914894979204943093716650072734138749420932619469204815802746273252727013183568196402223549961607284086898768583604510696483111
>>> c1 = 45254947860172381004009381991735702721210786277711531577381599020185600496787746985669891424940792336396574951744089759764874889285927022268694128526139687661305707984329995359802337446670063047702309778972385903473896687843125261988493615328641864610786785749566148338268077425756876069789788618208807001704
>>> c2 = 16054811947596452078263236160429328686151351092304509270058479526590947874445940946506791900760052230887962479603369427120610506778471930164144528718052332194666418267005043709704814833963217926271924910466448499814399455203725279998913865531351070938872586642424346857094632491904168889134624707595846754719
>>> u, v, _ = extended_gcd(e1, e2)
>>> m = pow(c1, u, n) * pow(c2, v, n) % n
>>> bytes.fromhex(hex(m)[2:])
b'ictf{n3ver_r3use_m0dul1}\n'
>>> exit()