<- IMAGINARYCTF

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 () se cifra dos veces como

El problema aquí es que el mismo mensaje se eleva a dos exponentes diferentes pero usando el mismo módulo .

Por la identidad de Bezout, dados dos enteros no nulos, existen enteros tales que

Como , podemos encontrar valores tales que

La idea es hallar estos valores para calcular el mensaje de esta manera:

Los valores 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()