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: , y . Los números y son de 1024 bits, y se multiplican para dar lugar al módulo de RSA.

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

Para hallar , podemos meter en factordb.com, y nos mostrará el valor de y de .

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

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

Entre los valores involucrados en las ecuaciones anteriores, disponemos de , , , y .

Solución

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

Nos podemos aprovechar de que el teorema del binomio se comporta algo distinto en módulo :

Y al aplicar módulo , se queda solamente:

Análogamente, con el otro texto cifrado:

Entonces, podemos multiplicar por y por para tener el mismo factor multiplicando a :

Entonces, tenemos:

Ahora, podemos elevar la primera ecuación a y la segunda ecuación a , y por cómo funciona el teorema del binomio en módulo , nos queda lo siguiente:

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

Con esto, ya podemos calcular usando el GCD con . Y una vez que tenemos un factor primo de , 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}'