same
2 minutos de lectura
Se nos proporciona un código fuente en Python para cifrar la 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))
Y tenemos la salida del programa:
88627598925887227793409704066287679810103408445903546693879278352563489802835708613718629728355698762251810901364530308365201192197988674078034209878433048946797619290221501750862580914894979204943093716650072734138749420932619469204815802746273252727013183568196402223549961607284086898768583604510696483111
45254947860172381004009381991735702721210786277711531577381599020185600496787746985669891424940792336396574951744089759764874889285927022268694128526139687661305707984329995359802337446670063047702309778972385903473896687843125261988493615328641864610786785749566148338268077425756876069789788618208807001704
16054811947596452078263236160429328686151351092304509270058479526590947874445940946506791900760052230887962479603369427120610506778471930164144528718052332194666418267005043709704814833963217926271924910466448499814399455203725279998913865531351070938872586642424346857094632491904168889134624707595846754719
El criptosistema utilizado es RSA, pero tiene una vulnerabilidad. La flag ($m$) se cifra dos veces como
$$ c_1 = m ^ {e_1} \mod{n} $$
$$ c_2 = m ^ {e_2} \mod{n} $$
El problema aquí es que el mismo mensaje se eleva a dos exponentes diferentes pero usando el mismo módulo $n$.
Por la identidad de Bezout, dados dos enteros $a, b$ no nulos, existen enteros $u, v$ tales que
$$ u \cdot a + v \cdot b = \gcd{(a, b)} $$
Como $\gcd{(e_1, e_2)} = 1$, podemos encontrar valores $u, v$ tales que
$$ u \cdot e_1 + v \cdot e_2 = 1 $$
La idea es hallar estos valores para calcular el mensaje $m$ de esta manera:
$$ 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} $$
Los valores $u, v$ se calculan usando el GCD extendido (Algoritmo de Euclides Extendido).
Por tanto, este es el código utilizado para conseguir la 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()