<- HACKON CTF

El cifrao del cuñao

4 minutos de lectura

Se nos proporciona un script en Python que cifra la flag con RSA:

from Crypto.Util.number import getPrime, bytes_to_long
import random


flag='HackOn{testing_flag}'

p = getPrime(1024)
q = getPrime(1024)
r = getPrime(24)

N1 = p * q * r
N = p * q


e1 = 34456075732829756714431696264844933736161425428678777444326530245267175496676105  
e2 = 66213320562378389542956020292848603326457400359492442893037745994906793456536650


c1 = pow(7 * p + random.randint(N,N1) * q, e1, N)
c2 = pow(5 * p + random.randint(2,N) * q, e2, N)

print (f'N1: {N1}\ne1: {e1}\ne2: {e2}\nc1: {c1}\nc2: {c2}')

flag_enc= pow(bytes_to_long(flag.encode()),0x10001,N)
print (f"flag_enc: {flag_enc}")

Y también tenemos la salida del script:

N1: 175067650953281050974609338975008206300624155348825595664106085967248998540617589741296346446924688724242605062233417184911333065108859297893274877902045993216986203079495828026354663317386440140270647809550473976974096628129591628284434963946783999869378111149217917648303508065328285929072381617978438470612874589596417613745039005251725210799071272826546175725224168805195456492444749329204834536327769184614475392674754321257754169752988706888110110854886262024581325203950655368202664487427493994718122501091228347564869440655164776355796295767478070623428032139757559412393093121138433999763436450288748369986859103207  
e1: 34456075732829756714431696264844933736161425428678777444326530245267175496676105
e2: 66213320562378389542956020292848603326457400359492442893037745994906793456536650
c1: 6451549454415106937054124906386205073222243394024359630462457026011516075453322110598440273419680741264449270624349464347792470300209994225871051817906071211422868952418491992463196228285205919371173656723348479276338927171156200258373946868108513210341715619135657733694945758701239603020350282490930923223040685524857825378664935954076777009286161163426015863451976127043646518744751008641471118799355737506530194673897401350560878119713588235864131464162613324379365056778461514972632453218452367994231300225730879806827703530704658426099425996148485094190653296415838854275518343410370771236791449822141459828741
c2: 962692207706212570956439147864349279649773113345655426314467693283718484612354279844043839717727068405496826210437866778756030633962827278103786266408189507399825183552809952197915820962569346678627273880805894119629683258989464814629538794918992935736967313768318129713814389945731392361973072114735327121558821584916746528122804041711257237956057904149848804653061211762199626222824628761726392699104681979458399805669073291307091763121332471373822692444415481403270868672559435581015624351087019008601980986815604227475289546705737298842219420062366361168396261671333779917844108475134254136718732987251213358163
flag_enc: 15465286692614275746593514754237742386723861276150927182475649162005944543455951013680150395056664962236242882064880238881068860224733875220632862364701169875117607762861097611036434484377717716522737041218148230761637401384647090841280793847093817991683060457776791068080281552363949410183822084792402759853630877454700951708809147788336138383950624542278364204457482947061715484392305381003183584082954722435919314472678081759451287929983648205030782429815775036186091814941726369980614237971458156295355908243600894532353339370750767776703572265634702300110928757229421759517414772239223719386574540374904804032054

Análisis del código fuente

En primer lugar, se calculan tres números primos: $p$, $q$ y $r$. Los números $p$ y $q$ son de 1024 bits, y se multiplican para dar lugar al módulo $N$ de RSA.

Por otro lado, el número $r$ es de 24 bits, y se multiplica con $N$ para dar lugar a $N_1$, que es un valor que nos proporcionan en el reto.

Para hallar $N$, podemos meter $N_1$ en factordb.com, y nos mostrará el valor de $r = 10085597$ y de $N$.

Una vez que tenemos $N$ ya podemos afrontar el reto de RSA. Los cifrados que calcula el script son:

$$ \begin{align*} c_1 = (7p + x \cdot q)^{e_1} \mod{N} \\ c_2 = (5p + y \cdot q)^{e_2} \mod{N} \end{align*} $$

Donde $x$ e $y$ son dos números aleatorios que no son relevantes.

Entre los valores involucrados en las ecuaciones anteriores, disponemos de $N$, $c_1$, $c_2$, $e_1$ y $e_2$.

Solución

La idea es buscar una combinación lineal entre $c_1$ y $c_2$ que dependa solo de $q$ (es decir, eliminar $p$). Entonces, podremos usar el máximo común divisor (GCD) para obtener uno de los factores primos de $N$.

Nos podemos aprovechar de que el binomio de Newton se comporta algo distinto en módulo $N$:

$$ \begin{split} c_1 = (7p + xq)^{e_1} & = (7p)^{e_1} + \\ & + (7p)^{e_1 - 1} xq + \\ & + (7p)^{e_1 - 2} (xq)^2 + \\ & + \dots + \\ & + (7p)^{2} (xq)^{e_1 - 2} + \\ & + 7p (xq)^{e_1 - 1} + \\ & + (xq)^{e_1} \end{split} $$

Y al aplicar módulo $N = p \cdot q$, se queda solamente:

$$ c_1 = (7p + xq)^{e_1} = (7p)^{e_1} + (xq)^{e_1} \mod{N} $$

Análogamente, con el otro texto cifrado:

$$ c_2 = (5p + yq)^{e_2} = (5p)^{e_2} + (yq)^{e_2} \mod{N} $$

Entonces, podemos multiplicar $c_1$ por $5^{e_1}$ y $c_2$ por $7^{e_2}$ para tener el mismo factor multiplicando a $p$:

$$ \begin{align*} 5^{e_1} c_1 = 5^{e_1} (7p)^{e_1} + 5^{e_1} (xq)^{e_1} \mod{N} \\ 7^{e_2} c_2 = 7^{e_2} (5p)^{e_2} + 7^{e_2} (yq)^{e_2} \mod{N} \end{align*} $$

Entonces, tenemos:

$$ \begin{align*} 5^{e_1} c_1 = (35p)^{e_1} + (5xq)^{e_1} \mod{N} \\ 7^{e_2} c_2 = (35p)^{e_2} + (7yq)^{e_2} \mod{N} \end{align*} $$

Ahora, podemos elevar la primera ecuación a $e_2$ y la segunda ecuación a $e_1$, y por cómo funciona el binomio de Newton en módulo $N$, nos queda lo siguiente:

$$ \begin{align*} (5^{e_1} c_1)^{e_2} = \left((35p)^{e_1} + (5xq)^{e_1}\right)^{e_2} = (35p)^{e_1 e_2} + (5xq)^{e_1 e_2} \mod{N} \\ (7^{e_2} c_2)^{e_1} = \left((35p)^{e_2} + (7yq)^{e_2}\right)^{e_1} = (35p)^{e_1 e_2} + (7yq)^{e_1 e_2} \mod{N} \end{align*} $$

Entonces, restamos ambas ecuaciones y obtenemos algo que tiene un factor común con $q$:

$$ \begin{split} (5^{e_1} c_1)^{e_2} - (7^{e_2} c_2)^{e_1} & = (5xq)^{e_1 e_2} - (7yq)^{e_1 e_2} \mod{N} \\ & = q^{e_1 e_2} \cdot \left((5x)^{e_1 e_2} - (7y)^{e_1 e_2}\right) \mod{N} \end{split} $$

Con esto, ya podemos calcular $q$ usando el GCD con $N$. Y una vez que tenemos un factor primo de $N$, es trivial descifrar RSA.

Flag

Las operaciones anteriores se pueden hacer rápidamente en un REPL de Python:

$ python3 -q
>>> N1 = 175067650953281050974609338975008206300624155348825595664106085967248998540617589741296346446924688724242605062233417184911333065108859297893274877902045993216986203079495828026354663317386440140270647809550473976974096628129591628284434963946783999869378111149217917648303508065328285929072381617978438470612874589596417613745039005251725210799071272826546175725224168805195456492444749329204834536327769184614475392674754321257754169752988706888110110854886262024581325203950655368202664487427493994718122501091228347564869440655164776355796295767478070623428032139757559412393093121138433999763436450288748369986859103207  
>>> e1 = 34456075732829756714431696264844933736161425428678777444326530245267175496676105
>>> e2 = 66213320562378389542956020292848603326457400359492442893037745994906793456536650
>>> c1 = 6451549454415106937054124906386205073222243394024359630462457026011516075453322110598440273419680741264449270624349464347792470300209994225871051817906071211422868952418491992463196228285205919371173656723348479276338927171156200258373946868108513210341715619135657733694945758701239603020350282490930923223040685524857825378664935954076777009286161163426015863451976127043646518744751008641471118799355737506530194673897401350560878119713588235864131464162613324379365056778461514972632453218452367994231300225730879806827703530704658426099425996148485094190653296415838854275518343410370771236791449822141459828741
>>> c2 = 962692207706212570956439147864349279649773113345655426314467693283718484612354279844043839717727068405496826210437866778756030633962827278103786266408189507399825183552809952197915820962569346678627273880805894119629683258989464814629538794918992935736967313768318129713814389945731392361973072114735327121558821584916746528122804041711257237956057904149848804653061211762199626222824628761726392699104681979458399805669073291307091763121332471373822692444415481403270868672559435581015624351087019008601980986815604227475289546705737298842219420062366361168396261671333779917844108475134254136718732987251213358163
>>> flag_enc = 15465286692614275746593514754237742386723861276150927182475649162005944543455951013680150395056664962236242882064880238881068860224733875220632862364701169875117607762861097611036434484377717716522737041218148230761637401384647090841280793847093817991683060457776791068080281552363949410183822084792402759853630877454700951708809147788336138383950624542278364204457482947061715484392305381003183584082954722435919314472678081759451287929983648205030782429815775036186091814941726369980614237971458156295355908243600894532353339370750767776703572265634702300110928757229421759517414772239223719386574540374904804032054
>>>
>>> r = 10085597
>>> assert N % r == 0
>>>
>>> from math import gcd
>>> N = N1 // r
>>> q = gcd(pow(pow(5, e1, N) * c1, e2, N) - pow(pow(7, e2, N) * c2, e1, N), N)
>>> assert N % q == 0 and 1 < q < N
>>>
>>> p = N // q
>>> d = pow(0x10001, -1, (p - 1) * (q - 1))
>>> m = pow(flag_enc, d, N)
>>>
>>> bytes.fromhex(hex(m)[2:])
b'HackOn{c4m4r3r0_7r4ig4_l4_mUlt4_a7b93daf}'