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:
Por otro lado, el número
Para hallar
Una vez que tenemos
Donde
Entre los valores involucrados en las ecuaciones anteriores, disponemos de
Solución
La idea es buscar una combinación lineal entre
Nos podemos aprovechar de que el teorema del binomio se comporta algo distinto en módulo
Y al aplicar módulo
Análogamente, con el otro texto cifrado:
Entonces, podemos multiplicar
Entonces, tenemos:
Ahora, podemos elevar la primera ecuación a
Entonces, restamos ambas ecuaciones y obtenemos algo que tiene un factor común con
Con esto, ya podemos calcular
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}'