binary basis
4 minutos de lectura
Se nos proporciona el código fuente en Python para cifrar la flag:
from Crypto.Util.number import getPrime, bytes_to_long
from math import prod
FLAG = open('flag.txt', 'rb').read()
primes = [getPrime(128) for _ in range(16)]
n = prod(primes)
e = 0x10001
m = bytes_to_long(FLAG)
c = pow(m, e, n)
treat = sum([primes[i]*2**(0x1337-158*(2*i+1)) for i in range(16)])
with open('output.txt', 'w') as f:
f.write(f'{n = }\n')
f.write(f'{e = }\n')
f.write(f'{c = }\n')
f.write(f'{treat = }\n')
Y esta es la salida del script:
n = 119493145368134756606524581488517378672235496744508597127639648421685629462649680337305664581985725401892086474314689141024498358715132868441978738105268336335778301627806695859205063825847290995872425532374614756539044160447358903375166525543471922868488499105664355206800751381027260462074705122647672994384365333260862845803962495145681040264675164695690862737006515315087470040757606517140071798300326022127659497206583492859643180260756285101547522674696613261207152550090000611298331939402585491230470733454735317291288404096144773097239721697692471487615973994925335486666529576878075473132154318910180009691
e = 65537
c = 78434014553061170529838401917720357645901208101352296269884472900978844319305951884764695717375322363272928093737865793113104432023794235229497701142692681415679549147532592802702053823324082733182072770779006523720442490771120987890027997070704393610765382574187921750560918055356164458340750383236011537901475045013520557031618820264221766743094536121925226791850895255993453048670745607742469934947653147879259892501050933253400391984499229656112961295969492487005786860006961292676090836472527246673699345029628224872195546099448661501561676622720260514226385260271583307493991971640825413235694692735476316469
treat = 41064122210117590309893920850940851964448573197364702312218652847563074658468550776049623436077059647900426409109763901345955202703985682630778316836716410976908994802298857481157910324003086887604087560484126319093760348302784031959884608690718739939531289130555241671099503557713216197592401241234208735819631180320413760718656876867323406561829316166491696103527500078153837145772310740455509956660694823144830260095551391236403182836214728060291251693690579998717099897785954779748569649102911569556210804834065634957865690729391572538723259866564481741517395331813459603466263827141279911919706281328288050460721861661990446597425850271364217052936489186818846863874578006688813944143685727931104321810713830759839918256937075645849871941798921033683465399959646136621559049887273682054277330663458615787744906360121329675910070999119357809181250170609599790023712764414191551844874675524795782430239120555096062003800058693423405350206617745916914116965357631650740005441388405061692790006508760971107741027556312990780727724371467017609554695371798159449361071175599514947307436760940029734313697931199508407965056916479246854944553994533969739046153764629534835323207379057477612661669942078609127146916601554609679997006901572586628537881511818938391905350113674432833361660748486019032622987316746412638187233454037252369980080224744837380800996358881451638758024280972061536248320550269641404509205922332930938158599125930491114698209185841465863646506532208640
Análisis del código fuente
El código fuente es realmente simple. Básicamente crea una clave privada de RSA multiprimo y utiliza la clave pública asociada para cifrar la flag.
Además, define una variable treat que depende de la lista primes de la clave privada:
primes = [getPrime(128) for _ in range(16)]
n = prod(primes)
e = 0x10001
m = bytes_to_long(FLAG)
c = pow(m, e, n)
treat = sum([primes[i]*2**(0x1337-158*(2*i+1)) for i in range(16)])
Contexto de RSA
En RSA, la clave privada se compone principalmente de dos números primos $p$ y $q$.Se supone que estos números son grandes (normalmente, tienen 1024 bits). Por otro lado, la clave pública posee el exponente $e = 65537$ y el módulo $n = p \cdot q$.
La seguridad de este criptosistema se basa en el hecho de que la factorización de números enteros es un problema computacionalmente difícil incluso para ordenadores potentes. Por lo tanto, dado el módulo público $n$, podemos decir que es imposible factorizarlo en $p$ y $q$ si no se proporciona más información.
RSA funciona de manera que, dado un mensaje $m$ en formato decimal, podemos cifrarlo como sigue:
$$ c = m^e \mod{n} $$
La clave pública está formada por $n$ y $e$. Y $n = p \cdot q$, que son dos números primos grandes (guardados como clave privada).
Por otro lado, para descifrar se necesitan dos valores más: $\phi(n) = (p - 1) (q - 1)$ y $d = e^{-1} \mod{\phi(n)}$, de manera que:
$$ m = c^d \mod{n} $$
Por lo tanto, la mejor manera de descifrar RSA es encontrar una factorización de $n$ (es decir, encontrar $p$ y $q$).
Para el caso de RSA multiprimo, $n$ es el producto de más de dos números primos. Sin embargo, el resto sigue siendo lo mismo. Necesitamos encontrar $\phi{(n)}$ para calcular el exponente privado $d$. Suponiendo que todos los primos $p_i$ que forman $n$ son diferentes, la fórmula para $\phi{(n)}$ es
$$ \phi{(n)} = \phi{\left(\prod_{i = 0}^{15} p_i \right)} = \prod_{i = 0}^{15} \phi{(p_i)} = \prod_{i = 0}^{15} (p_i - 1) $$
Solución
Echemos un vistazo más de cerca a treat:
treat = sum([primes[i]*2**(0x1337-158*(2*i+1)) for i in range(16)])
En términos matemáticos, podemos reescribir el código anterior a
$$ \begin{align*} \mathtt{treat} & = \sum_{i = 0}^{15} p_i \cdot 2^{\mathtt{0x1337} - 158 \cdot (2i + 1)} \\ & = \sum_{i = 0}^{15} p_i \cdot 2^{4761 - 316 i} \\ & = 2^{4761} p_0 + 2^{4445} p_1 + 2^{4129} p_2 + \dots + 2^{21} p_{15} \\ & = 2^{21} \left(2^{4740} p_0 + 2^{4424} p_1 + 2^{4108} p_2 + \dots + p_{15}\right) \\ & = 2^{21} \sum_{i = 0}^{15} p_i \cdot 2^{4740 - 316i} \\ & = 2^{21} \sum_{i = 0}^{15} p_i \cdot 2^{316 \cdot (15 - i)} \\ \end{align*} $$
Obsérvese que los números primos se generan como enteros de 128 bits. Esto significa que si expresamos treat en trozos de 316 bits (separados en el bit número 128 para resaltar los números primos respecto a los bits de relleno), los números primos no se superponen:
$ python3 -q
>>> n = 119493145368134756606524581488517378672235496744508597127639648421685629462649680337305664581985725401892086474314689141024498358715132868441978738105268336335778301627806695859205063825847290995872425532374614756539044160447358903375166525543471922868488499105664355206800751381027260462074705122647672994384365333260862845803962495145681040264675164695690862737006515315087470040757606517140071798300326022127659497206583492859643180260756285101547522674696613261207152550090000611298331939402585491230470733454735317291288404096144773097239721697692471487615973994925335486666529576878075473132154318910180009691
>>> e = 65537
>>> c = 78434014553061170529838401917720357645901208101352296269884472900978844319305951884764695717375322363272928093737865793113104432023794235229497701142692681415679549147532592802702053823324082733182072770779006523720442490771120987890027997070704393610765382574187921750560918055356164458340750383236011537901475045013520557031618820264221766743094536121925226791850895255993453048670745607742469934947653147879259892501050933253400391984499229656112961295969492487005786860006961292676090836472527246673699345029628224872195546099448661501561676622720260514226385260271583307493991971640825413235694692735476316469
>>> treat = 41064122210117590309893920850940851964448573197364702312218652847563074658468550776049623436077059647900426409109763901345955202703985682630778316836716410976908994802298857481157910324003086887604087560484126319093760348302784031959884608690718739939531289130555241671099503557713216197592401241234208735819631180320413760718656876867323406561829316166491696103527500078153837145772310740455509956660694823144830260095551391236403182836214728060291251693690579998717099897785954779748569649102911569556210804834065634957865690729391572538723259866564481741517395331813459603466263827141279911919706281328288050460721861661990446597425850271364217052936489186818846863874578006688813944143685727931104321810713830759839918256937075645849871941798921033683465399959646136621559049887273682054277330663458615787744906360121329675910070999119357809181250170609599790023712764414191551844874675524795782430239120555096062003800058693423405350206617745916914116965357631650740005441388405061692790006508760971107741027556312990780727724371467017609554695371798159449361071175599514947307436760940029734313697931199508407965056916479246854944553994533969739046153764629534835323207379057477612661669942078609127146916601554609679997006901572586628537881511818938391905350113674432833361660748486019032622987316746412638187233454037252369980080224744837380800996358881451638758024280972061536248320550269641404509205922332930938158599125930491114698209185841465863646506532208640
>>>
>>> binary = bin(treat)[2:]
>>> print('\n'.join(binary[i : i + 128] + '\n' + binary[i + 128: i + 316] for i in range(0, len(binary), 316)))
11000001001110001000000101110010111100001000001000110000000101110011101010001101000010101100100000001001011110010010110011001101
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
11101000101101110110100011001110011001111110011010000110000001111101010111100000101111010101010000010100100011010111011110010101
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
11110011101010010111000011001111001011010000000001101011000111010101110110110111000001100001001010100001010000000110011111011001
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10010111010101111100101101111110000100101001100100100100001111110001001100000101100101010100100100110111111010110000110101100111
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
11110100011001010100100000001000010100100000101101100000001010001101110110111111101110101101001100000011001100011011000100001011
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10101000111110001101000011000011111110001010101110111111011000100110001001011011000101111000111100000001011101111011110101011101
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
11011001001000110010110000110000010101011100111100011001010100101111111110100111000000000011101100111000000010001010110110111011
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
11011011100011111110010111101011011001111111110000101010011010010111011100111010110010001000010101100111111111011010010111011001
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10011011010110100100101111110011110110100001001100001100100111110111110110011101101110011001011010010111011000000101001010010001
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10010010010001111010011011011101001100100001111110001110100100110001100110111001010010010111100010011001100110101000010110010101
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10010000110010111100011111101111000011011000101110000111100100101001100011000110111000101110100111011001010010001111100101110111
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10010000001100001010101100110011111100011101111000001001110111111011111001101000000111101110001001100101010100000011010101010101
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10011010101001100100011000011011000000011010001110000001011100101101100111110010110111011111111010111100101110101111100111001001
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10000101011110010010100111110110001001101011011111001010001001000011100110001000000010111101000001111101001101111011001010001011
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
11111011110011010010100011010100110111110011110101110111001111010011100001001011110011101000100111111101111101010101000010011001
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10011100010010011001010110110001001100001110111111010001010100111101000010000111100111001100110001111000011101001000010101010101
000000000000000000000
¡Como resultado, la variable treat contiene los números primos! Por lo tanto, podremos descifrar RSA utilizando esta información:
>>> primes = [int(binary[i : i + 128], 2) for i in range(0, len(binary), 316)]
>>> prod(primes) == n
True
Otra forma de obtener los primos es utilizar una expresión similar de treat, cambiando el producto por una división entera y agregando la restricción de 128 bits:
>>> primes == [(treat // 2 ** (0x1337 - 158 * (2 * i + 1))) % 2 ** 128 for i in range(16)]
True
Flag
En este punto, solo necesitamos descifrar el texto cifrado, calculando $\phi{(n)}$ y $d$, y luego aplicando el método de descifrado:
>>> phi_n = prod(p - 1 for p in primes)
>>> d = pow(e, -1, phi_n)
>>>
>>> m = pow(c, d, n)
>>> bytes.fromhex(hex(m)[2:])
b'HTB{any_leak_related_to_the_primes_can_lead_to_full_factorization}'