RSA Cycle - TOH2025

Autor del reto: Alessandro Barenghi

Dificultad: Fácil

Enunciado

“Fed up with the amount of energy wasted in training LLMs, just to ask them the number of ‘r’s in strawberry, we decided to have our own take in helping the environment. Therefore, we chose to send our message to two different recipients, while recycling part of an RSA key, after all, they know each other, and they said they don’t mind. We are absolutely, positively, totally certain that there’s no issue in this.

Hint: Keep in mind that one char is not always eight bits”

Archivos

En este reto, tenemos el siguiente archivo.

• output.txt: Contiene la clave pública junto con los mensajes cifrados.

Archivos utilizados aquí.

Analizando el reto

Si abrimos el archivo output.txt encontramos lo siguiente.

Public key B 
 e: 11
 n:627253147779600482212911959448896075801144441970703518305910447639715306593800142387972523363871260996692775787924720453697369488089037440174523528694140782386624622354852694824314732576110035924610691142350502135386185193146426517142208053668457731521042942692915818502085708831007802585313612739808482907237624956237673669859672194292302380831914518477221836204323965569815966972318154142582249079800379151680749849388953480472504294619076276387924679990200097396224456883651544240752302620529235062065551404906929565334190263088594902903695645125211620207412297913835541252020221555816016975090778207008389294239198946154066845963706415260390241217463815791493846538819169851465732531573247187675185547701793210302009664728438541776379325265496184298304205303809425860420252614181663902903400366395885218461121109810432798773332674982851364440424578217528468194393911690073364339018457480207471090304034996328148136423070908778095425689187064031235044094603608670354951791712601736375861355494398054784586468945985443129921093373990829283870935441461283575474204591045086275985127129676791084906984348886870039378621499221464618448802404846782940488027098042054559686285435138883610791548827272220930467956149158931681993601303222843965688925341553411784989768456216605687867193705583942525056716245787967233173758590172385204997573381064727001250400509415278377732849634184088282043179516438282553262014299663015787309378822071712464065122773909369720896648445118481940875926296161816013972318627448383764367750821398848191556570954294437641663089131787324289412072109176126711364777159619631987396741830994168319735681736313828237048077684746637508324357450120277014720916578026633001808442207068764390535578860750434631334233592055731794857120681275084617507966025740861958512206450346170431449790820344162863829798932683214115516962207827502199681254249701681128887529600571554995514568401390139316128540179078987564312438608884362575224888199499951459038167825745024562704745465033050666787621844224462834612901475873730220410920162147634611621358398401678333821199752122943174308742026007215001894483703087751729765559509353673334746425065035269705216475754332694062662674658045276976181160256344815766595826388442985705105160555769386859917531686574561472097747663621357431096936741842095530023268616361796280585255819469680410697152645641290570690999203534623574858528751898392536310851040192980575075616175561183401397794223120240011876969776952447283841
Ciphertext B: 2474475492040024528464429550466082040192346962362392401727343912178246244029216364523622122090577166293793718247317342575808466946802854902613219810943705799042755407193458891712359816997083119880303233707889471495002009564982085393086520712017300747722172226827978020112883673081016844407497075998266270460077101461665235622321746197700892765845113468379110361388192129595814582767932595903664806572222035369774720577333433025105543855427992359237391615170298426172302284905219009911425868116846001391785734157278293268149865200036993563799558088231873248505219932506581447771064618126582155042585664185933969501587498855253977637050772095300475799291117469224131234117994373774092206270832297405216099052314738435195719382334426313124800126389531015147370295820080444659458308989384715936416192321316171027886406856365724536173216692942433206820318578100441990994653547127153577086504439834879688137931952171014092256480331638784068764721100842407277380672041790430786797437532141504486747889259192440543030051287808500988978680127291893366895607693099566203102859054726915340012450682618146873657111797927697774036237111997927097190883885466826083644108229427263417026656162333098670329208281028255212347012238737099913404029897133126230755106777702232252411475853991813731594686219604799480281638275332127229637899918820477472312256110678402941262811994600261873743648632173941858243989662513091492191357953045677800331401633411909316249759201236141646098077400791370506628721571957328953329920582279061462083970134949744457477499596939290356732420120118219877684577955976732202754616691975518737434248542456061061676321012242842828281060842263948769060964871243335346397651610770487813
Public key C 
 e: 7
 n:627253147779600482212911959448896075801144441970703518305910447639715306593800142387972523363871260996692775787924720453697369488089037440174523528694140782386624622354852694824314732576110035924610691142350502135386185193146426517142208053668457731521042942692915818502085708831007802585313612739808482907237624956237673669859672194292302380831914518477221836204323965569815966972318154142582249079800379151680749849388953480472504294619076276387924679990200097396224456883651544240752302620529235062065551404906929565334190263088594902903695645125211620207412297913835541252020221555816016975090778207008389294239198946154066845963706415260390241217463815791493846538819169851465732531573247187675185547701793210302009664728438541776379325265496184298304205303809425860420252614181663902903400366395885218461121109810432798773332674982851364440424578217528468194393911690073364339018457480207471090304034996328148136423070908778095425689187064031235044094603608670354951791712601736375861355494398054784586468945985443129921093373990829283870935441461283575474204591045086275985127129676791084906984348886870039378621499221464618448802404846782940488027098042054559686285435138883610791548827272220930467956149158931681993601303222843965688925341553411784989768456216605687867193705583942525056716245787967233173758590172385204997573381064727001250400509415278377732849634184088282043179516438282553262014299663015787309378822071712464065122773909369720896648445118481940875926296161816013972318627448383764367750821398848191556570954294437641663089131787324289412072109176126711364777159619631987396741830994168319735681736313828237048077684746637508324357450120277014720916578026633001808442207068764390535578860750434631334233592055731794857120681275084617507966025740861958512206450346170431449790820344162863829798932683214115516962207827502199681254249701681128887529600571554995514568401390139316128540179078987564312438608884362575224888199499951459038167825745024562704745465033050666787621844224462834612901475873730220410920162147634611621358398401678333821199752122943174308742026007215001894483703087751729765559509353673334746425065035269705216475754332694062662674658045276976181160256344815766595826388442985705105160555769386859917531686574561472097747663621357431096936741842095530023268616361796280585255819469680410697152645641290570690999203534623574858528751898392536310851040192980575075616175561183401397794223120240011876969776952447283841
Ciphertext C: 11710628142649231139943597951350054966995607118105331592596412204055176237341022956420972055387239792446053846712470436743485760857772779123121937674091356482797914430491354395087980523413724349844444751875754572602156218615065461349616077149407847495906965432869211865178716649812073537170332952774591779243903110581864211409305510038110221749952076990755471487201336248079823386519507071873235618009500955596303227133917559304010251045505282555051946791730715211756416119340444106332023591526673716439667672062331677060914666013628165022318943899513385097584393226378852972614139816323873763575969653327095731714573852869936960881704196279020447570053572679085950007257584057587010212082905062334457508373165080068647236309125722471945797634175607091374523872331372026827521218744052038148720033788841503576649857734760131493175737968071768474968855606275575178731010141309445070892522850240282285937829922312369375401070895585520392890695025827821908823752049904168827106837181257929150948844505346035266416772499111138999985276176487556226960494328850551055280589248322933

Si observamos el output, podemos ver como ambos comparten el mismo módulo n, lo que implica que ambos mensajes están cifrados con la misma clave privada, pero con exponentes públicos distintos siendo $e1 = 11$ y $e2 = 7$

Además, los dos mensajes (Ciphertext B y Ciphertext C) fueron cifrados con la misma n y diferente e con los mensajes originales dados.

Solución

En este caso, este reto de esquema RSA es vulnerable a un ataque de claves públicas comunes (Common Modulus Attack)

Esto se debe a que se cumplen ciertas condiciones de usabilidad.

En RSA, un mensaje $m$ se cifra así:

\[c = m^e \mod n\]

En nuestro caso, tenemos dos claves públicas diferentes usadas con el mismo módulo n, con la siguiente información.

• Clave B: $e_1 = 11$
• Clave C: $e_2 = 7$
• Ambos usan el mismo $n$.
• Ambos cifran el mismo mensaje $m$.

Entonces sabemos que:

\[\begin{cases} c_1 = m^{e_1} \mod n \\ c_2 = m^{e_2} \mod n \end{cases} \Rightarrow \begin{cases} c_1 = m^{11} \mod n \\ c_2 = m^7 \mod n \end{cases}\]

En este caso, podemos resolver el sistema de ecuaciones para obtener $m$ sin necesidad de conocer la clave privada ni factorizar n ya que se está utilizando el mismo módulo n y el mismo mensaje $m$ se cifra con ambas claves.

Para romperlo simplemente podemos realizar una implementación casera del algoritmo extendido de Euclides o simplemente utilizar la librería de CryptoAttacks.

Implementando el algoritmo extendido de Euclides, para encontrar enteros $a$, $b$ haríamos lo siguiente.

\[a \cdot e_1 + b \cdot e_2 = 1\]

Con esto, se hace:

\[m = (c_1^a \cdot c_2^b) \mod n\]

Y como:

\[m^{e_1 \cdot a + e_2 \cdot b} \equiv m^1 \mod n \Rightarrow m\]

Revertiríamos el mensaje m sin necesidad de calcular la clave privada.

Una vez revertido, en el enunciado nos dicen que la codificación de un char no siempre es de 8 bits. Esto quiere decir que está codificado con un número diferente de bits no estándar. , probaremos con distinta cantidad de bits hasta obtener un mensaje legible.

El script solución es el siguiente.

from Crypto.Util.number import inverse, long_to_bytes
from math import gcd
from sage.all import ZZ
from sage.all import xgcd

e1 = 11
n = 627253147779600482212911959448896075801144441970703518305910447639715306593800142387972523363871260996692775787924720453697369488089037440174523528694140782386624622354852694824314732576110035924610691142350502135386185193146426517142208053668457731521042942692915818502085708831007802585313612739808482907237624956237673669859672194292302380831914518477221836204323965569815966972318154142582249079800379151680749849388953480472504294619076276387924679990200097396224456883651544240752302620529235062065551404906929565334190263088594902903695645125211620207412297913835541252020221555816016975090778207008389294239198946154066845963706415260390241217463815791493846538819169851465732531573247187675185547701793210302009664728438541776379325265496184298304205303809425860420252614181663902903400366395885218461121109810432798773332674982851364440424578217528468194393911690073364339018457480207471090304034996328148136423070908778095425689187064031235044094603608670354951791712601736375861355494398054784586468945985443129921093373990829283870935441461283575474204591045086275985127129676791084906984348886870039378621499221464618448802404846782940488027098042054559686285435138883610791548827272220930467956149158931681993601303222843965688925341553411784989768456216605687867193705583942525056716245787967233173758590172385204997573381064727001250400509415278377732849634184088282043179516438282553262014299663015787309378822071712464065122773909369720896648445118481940875926296161816013972318627448383764367750821398848191556570954294437641663089131787324289412072109176126711364777159619631987396741830994168319735681736313828237048077684746637508324357450120277014720916578026633001808442207068764390535578860750434631334233592055731794857120681275084617507966025740861958512206450346170431449790820344162863829798932683214115516962207827502199681254249701681128887529600571554995514568401390139316128540179078987564312438608884362575224888199499951459038167825745024562704745465033050666787621844224462834612901475873730220410920162147634611621358398401678333821199752122943174308742026007215001894483703087751729765559509353673334746425065035269705216475754332694062662674658045276976181160256344815766595826388442985705105160555769386859917531686574561472097747663621357431096936741842095530023268616361796280585255819469680410697152645641290570690999203534623574858528751898392536310851040192980575075616175561183401397794223120240011876969776952447283841
c1 = 2474475492040024528464429550466082040192346962362392401727343912178246244029216364523622122090577166293793718247317342575808466946802854902613219810943705799042755407193458891712359816997083119880303233707889471495002009564982085393086520712017300747722172226827978020112883673081016844407497075998266270460077101461665235622321746197700892765845113468379110361388192129595814582767932595903664806572222035369774720577333433025105543855427992359237391615170298426172302284905219009911425868116846001391785734157278293268149865200036993563799558088231873248505219932506581447771064618126582155042585664185933969501587498855253977637050772095300475799291117469224131234117994373774092206270832297405216099052314738435195719382334426313124800126389531015147370295820080444659458308989384715936416192321316171027886406856365724536173216692942433206820318578100441990994653547127153577086504439834879688137931952171014092256480331638784068764721100842407277380672041790430786797437532141504486747889259192440543030051287808500988978680127291893366895607693099566203102859054726915340012450682618146873657111797927697774036237111997927097190883885466826083644108229427263417026656162333098670329208281028255212347012238737099913404029897133126230755106777702232252411475853991813731594686219604799480281638275332127229637899918820477472312256110678402941262811994600261873743648632173941858243989662513091492191357953045677800331401633411909316249759201236141646098077400791370506628721571957328953329920582279061462083970134949744457477499596939290356732420120118219877684577955976732202754616691975518737434248542456061061676321012242842828281060842263948769060964871243335346397651610770487813
e2 = 7
c2 = 11710628142649231139943597951350054966995607118105331592596412204055176237341022956420972055387239792446053846712470436743485760857772779123121937674091356482797914430491354395087980523413724349844444751875754572602156218615065461349616077149407847495906965432869211865178716649812073537170332952774591779243903110581864211409305510038110221749952076990755471487201336248079823386519507071873235618009500955596303227133917559304010251045505282555051946791730715211756416119340444106332023591526673716439667672062331677060914666013628165022318943899513385097584393226378852972614139816323873763575969653327095731714573852869936960881704196279020447570053572679085950007257584057587010212082905062334457508373165080068647236309125722471945797634175607091374523872331372026827521218744052038148720033788841503576649857734760131493175737968071768474968855606275575178731010141309445070892522850240282285937829922312369375401070895585520392890695025827821908823752049904168827106837181257929150948844505346035266416772499111138999985276176487556226960494328850551055280589248322933

def attack(n, e1, c1, e2, c2):
    """
    Recovers the plaintext from two ciphertexts, encrypted using the same modulus and different public exponents.
    :param n: the common modulus
    :param e1: the first public exponent
    :param c1: the ciphertext of the first encryption
    :param e2: the second public exponent
    :param c2: the ciphertext of the second encryption
    :return: the plaintext
    """
    g, u, v = xgcd(e1, e2)
    p1 = pow(c1, u, n) if u > 0 else pow(pow(c1, -1, n), -u, n)
    p2 = pow(c2, v, n) if v > 0 else pow(pow(c2, -1, n), -v, n)
    return int(ZZ(int(p1 * p2) % n).nth_root(g))

n = attack(n, e1, c1, e2, c2)

# 1) binario de longitud múltiplo de 7
bits = bin(n)[2:].zfill((n.bit_length() + 6) // 7 * 7)

# 2) dividir en trozos de 7 bits y 3) decodificar
texto = ''.join(
    chr(int(bits[i:i+7], 2))
    for i in range(0, len(bits), 7)
)

print(texto)

Solución

Flag

toh{mod_reduce_reuse_recycle_save_for_primes}