Crack the Power writeup
Descripción
We received an encrypted message. The modulus is built from primes large enough that factoring them isn’t an option, at least not today. See if you can make sense of the numbers and reveal the flag.
Download the message.
Crack the Power writeup
Al descargar y abrir el mensaje veremos el siguiente contenido:
Tenemos tres variables, n, e y c, lo cual nos da a entender que el cifrado es RSA. Cada una de ellas se corresponde con lo siguiente:
- n: Es la multiplicación de dos números primos, p y q. Por el enunciado del CTF ese nuḿero no se puede factorizar para obtener p y q.
- e: Es el exponente utilizado en el cifrado. Normalmente se utiliza 65537.
- c: Es el mensaje cifrado por el algoritmo.
El cifrado se realiza de la siguiente forma:
C = M^e mod nY el descifrado para obtener el mensaje en claro (M) de esta:
M = C^d mod nComo no tenemos d, no podemos utilizar el procedimiento habitual de descifrado. Sin embargo, dado que e es pequeño, podemos comprobar si M^e<n. Si se cumple, el módulo no tiene ningún efecto y podemos recuperar M calculando la raíz e-ésima de c. Para ello, antes tenemos que realizar dos comprobaciones:
- Si mod n se llega a usar en algún momento: Dado que e es tan pequeño, es posible que m^e sea menor que n y mod n no se utilice nunca.
- Si m es una raíz exacta: Comprobando así que directamente m^e=c, haciendo que la operación de descifrar sea directa.
Ambas comprobaciones las realizaremos con el siguiente código:
import gmpy2
#Contenido del archivo
n = 410664186165191791402826020648772079727855370225121168329489558023676206903110917122249911944501914058167574154300515578639528319920053023867482073692484985287827372248686968550452147219495058219737726533198589146788106207104006141113375574066854852611259725786317821883172497842657985257908701482139090568993822965683214349918502719101583356882168338270447984584381812927858227415072514189838197665563968909219013964220237934124402478909876364171409578837503118525132848891505287317986848688438750873278654357181872934401664809196436196103395671068981692006881025785118124735403009761732676194557783341186696317289217601680762240946756099165359859285900990663149297784065325172930606950668533524438921457116354261722563783316401034088432522913099965625002265981169229586378601077820521982226216733874547440407450338648780337291742094848216093949046938054996321130253196977418170117347647315719448397122004966163394965123751185910309725139116961163368621449406198577849587926254211380551265442088456309106778455980283046226445371066856262215933615411567261989837352437927401685169541910706297673710978352664847844643089079402646094504545790754030992062817610552755382423490304761138904591244735268207666957111641348148546651263055711
e = 20
c = 640637430810406857500566702096274079868087131935153057078985716461078483409793615804311883296591203324452249008450521032645267345512046769994383635285244380705157432625570066632528925314552900669814963219369331313157534607620352061314683496525883016843153241425770911702563380247302073740850825452371063276867610414725164654421304873071774234683226777641240092032528116047489137507373500064099947304524782898265669628686091404044097235795818651902023996906668123465373292221934136216954999213086853380479136606214034827032162211811911299453884553459883192781319337391984912950371275232374262114220706295073924345743106413419931715570201067076471272561731959500262271837841417300230554359594018424813861589485400512131504027368400263321851762034719595379735999122340323973277638235482616225404363214027767922993075345559200374830345517529445328472713066257434684134913873359589576414681791333170123047390862933633440111883394760439698156048278154619895786259579727797488066274962774692244105308866923365722966155030681035814505674226605348055192323888099731031683511808581367884577911318683020417249790405911629045010877656025044271667195964670746001
m, exact = gmpy2.iroot(c, e)
#Comprobaciones previas
print("El módulo nunca se llega a usar (M^e < n):", pow(m, e) < n)
print("Es una raíz exacta (M^e=c):", exact)Al ejecutar el archivo obtendremos el siguiente resultado:
El módulo nunca se llega a usar (M^e < n): True
Es una raíz exacta (M^e=c): TrueCon lo cual, podemos descartar el módulo de la ecuación, obteniendo la siguiente:
C = M^eAhora despejar M se vuelve mucho más sencillo:
M = e √ cY en este caso, tenemos tanto e como c, por lo que podemos construir el siguiente programa en python que nos devuelva el contenido del mensaje sin encriptar. El problema es que lo obtendremos como un entero, por lo que será necesario codificarlo a UTF-8:
import gmpy2
#Contenido del archivo
n = 410664186165191791402826020648772079727855370225121168329489558023676206903110917122249911944501914058167574154300515578639528319920053023867482073692484985287827372248686968550452147219495058219737726533198589146788106207104006141113375574066854852611259725786317821883172497842657985257908701482139090568993822965683214349918502719101583356882168338270447984584381812927858227415072514189838197665563968909219013964220237934124402478909876364171409578837503118525132848891505287317986848688438750873278654357181872934401664809196436196103395671068981692006881025785118124735403009761732676194557783341186696317289217601680762240946756099165359859285900990663149297784065325172930606950668533524438921457116354261722563783316401034088432522913099965625002265981169229586378601077820521982226216733874547440407450338648780337291742094848216093949046938054996321130253196977418170117347647315719448397122004966163394965123751185910309725139116961163368621449406198577849587926254211380551265442088456309106778455980283046226445371066856262215933615411567261989837352437927401685169541910706297673710978352664847844643089079402646094504545790754030992062817610552755382423490304761138904591244735268207666957111641348148546651263055711
e = 20
c = 640637430810406857500566702096274079868087131935153057078985716461078483409793615804311883296591203324452249008450521032645267345512046769994383635285244380705157432625570066632528925314552900669814963219369331313157534607620352061314683496525883016843153241425770911702563380247302073740850825452371063276867610414725164654421304873071774234683226777641240092032528116047489137507373500064099947304524782898265669628686091404044097235795818651902023996906668123465373292221934136216954999213086853380479136606214034827032162211811911299453884553459883192781319337391984912950371275232374262114220706295073924345743106413419931715570201067076471272561731959500262271837841417300230554359594018424813861589485400512131504027368400263321851762034719595379735999122340323973277638235482616225404363214027767922993075345559200374830345517529445328472713066257434684134913873359589576414681791333170123047390862933633440111883394760439698156048278154619895786259579727797488066274962774692244105308866923365722966155030681035814505674226605348055192323888099731031683511808581367884577911318683020417249790405911629045010877656025044271667195964670746001
m, exact = gmpy2.iroot(c, e)
#Comprobaciones previas
print("El módulo nunca se llega a usar (m^e < n):", pow(m, e) < n)
print("Es una raíz exacta (hno hay padding):", exact)
if exact:
m_bytes = int(m).to_bytes((int(m).bit_length() + 7) // 8, byteorder="big")
mensaje = m_bytes.decode("utf-8")
print(mensaje)Obteniendo así la flag y completando el CTF.
Consultor de ciberseguridad especializado en continuidad de negocio y respuesta ante incidentes. Interesado en analizar tecnologías desde una perspectiva de seguridad y descubrir su comportamiento real.