Somkracht 65537 - ChallengetheCyberCTF2025

Autor del reto: Desconocido

Dificultad: Fácil

Enunciado

Is this how RSA works? I read something about p and q somewhere.

Archivos

challenge.py

from Crypto.Util.number import *

p = getPrime(1024)
q = getPrime(1024)
N = p*q

e = 65537

msg = bytes_to_long(b"flag{dummy_flag}")

ct1 = pow(msg, e, N)
ct2 = pow(msg, p+q, N)

print(f"{N = }")
print(f"{ct1 = }")
print(f"{ct2 = }")

"""
N = 13172635138210286640933237746072073728198869440440273861514688422430115450596963502627269613634657978751692320585777768877613321668778514462972611542147278205792418292362109100597755668571861738781190210255903465162483813897653948305531342676537057130369323555420200545974179860718822410192595079238246216026529376260568656408216009127973127738250617629330070723654601189310430802429585919291621479622419163092371272056180409609142738265178224163465585013019636286435078812898907472859171136422659050412212315590509027225331104292443193693974638004592849794819591007103879538185323581422819852185166422985403024630123
ct1 = 8499526321488266762028127474977263983474334713646962923180757984708039537289636737028409522654349845032612940144246996001396064450188534247830979105036627472087587636695469693411422088223080856169980341928057477564688506588678465277896123712776169270866525885072607021419929184184301722442524104467963680432737243478200661224741027413690099507128782156810842444314483076587935222998920241102484844741597333281611874849648935849985954902264102662618041817365284648356127737145896858259709819593359264714426125676691235985164360773645489923563993927995838346085066937602961724919392025887999986486672200850129835569774
ct2 = 2263178005282615069738169250508811825030372342139636879043114251227029802177975391784856426659871916802959302578620910469427367218786299839311310420522660987052055310279591316813828952756984548230575321772825193775083404279028090110850848262192595930920326368607665856808251531130234210906413358662814500632504899088517752958423466186872534450108628371006268110210630017230741670440780982809417986017372337888735465439382827207990030719121834402226087906249993820193417658352914727984318783025375497623944699995700474418221251293446038111913247755996471673024017921092527032486774115935601292346440934530921157935322
"""

Archivos utilizados en mi repositorio de Github.

Analizando el reto

De forma muy resumida, el código anterior está basado en un sistema que genera claves RSA, las cuales son usadas para cifrar la flag ct1. Posteriormente, se vuelve a cifrar usando p+q generando ct2

Solver

En el código anterior, cifrar una segunda vez la flag usando p+q genera una vulnerabilidad en la que por medio de N y ct2, se puede recuperar p+q obteniendo los primos p y q y revirtiendo el cifrado de manera simple.

Esto ocurre porque \(\text{ct2} = \text{msg}^{(p+q)} \bmod N\) filtra indirectamente el valor de p+q.

Para ello, se tendrá que realizar los siguientes pasos:

1. Calcular k (inverso modular de e módulo N+1)
2. Calcular t como \(\left\lfloor \frac{ek - 1}{N + 1} \right\rfloor\)
3. Calcular \(\text{ct2}^{t} \bmod N\)
4. Verificar si A es coprimo con N

from math import gcd
from Crypto.Util.number import long_to_bytes

N = 13172635138210286640933237746072073728198869440440273861514688422430115450596963502627269613634657978751692320585777768877613321668778514462972611542147278205792418292362109100597755668571861738781190210255903465162483813897653948305531342676537057130369323555420200545974179860718822410192595079238246216026529376260568656408216009127973127738250617629330070723654601189310430802429585919291621479622419163092371272056180409609142738265178224163465585013019636286435078812898907472859171136422659050412212315590509027225331104292443193693974638004592849794819591007103879538185323581422819852185166422985403024630123
ct1 = 8499526321488266762028127474977263983474334713646962923180757984708039537289636737028409522654349845032612940144246996001396064450188534247830979105036627472087587636695469693411422088223080856169980341928057477564688506588678465277896123712776169270866525885072607021419929184184301722442524104467963680432737243478200661224741027413690099507128782156810842444314483076587935222998920241102484844741597333281611874849648935849985954902264102662618041817365284648356127737145896858259709819593359264714426125676691235985164360773645489923563993927995838346085066937602961724919392025887999986486672200850129835569774
ct2 = 2263178005282615069738169250508811825030372342139636879043114251227029802177975391784856426659871916802959302578620910469427367218786299839311310420522660987052055310279591316813828952756984548230575321772825193775083404279028090110850848262192595930920326368607665856808251531130234210906413358662814500632504899088517752958423466186872534450108628371006268110210630017230741670440780982809417986017372337888735465439382827207990030719121834402226087906249993820193417658352914727984318783025375497623944699995700474418221251293446038111913247755996471673024017921092527032486774115935601292346440934530921157935322
e = 65537

# Paso 1
k = pow(e, -1, N + 1)

# Paso 2
t = (e * k - 1) // (N + 1)

# Paso 3
A = pow(ct2, t, N)

# Paso 4
d = gcd(A, N)
if d == 1:
    # A es invertible módulo N
    inv_A = pow(A, -1, N)
    m = (pow(ct1, k, N) * inv_A) % N
    flag = long_to_bytes(m)
    print(flag.decode())
elif 1 < d < N:
    # Caso raro: factorizamos N
    p = d
    q = N // d
    phi = (p - 1) * (q - 1)
    d_rsa = pow(e, -1, phi)
    m = pow(ct1, d_rsa, N)
    flag = long_to_bytes(m)
    print(flag.decode())
else:  # d == N (muy raro)
    print("No se pudo recuperar la bandera (d == N)")

Flag

flag{31470335203860e47f0c3b1dd50e1da9}