LowkeyRSA - L3AK2025
Reto basado en romper un esquema RSA custom mediante un Wiener attack
Autor del reto: Black, White, Suvoni
Dificultad: Media
Enunciado
“This RSA might lowkey be insecure, no cap fr fr.”
Archivos
En este reto, tenemos el siguiente archivo.
chall.py
: Contiene el script principal de cifrado.
Archivos utilizados aquí.
Analizando el reto
Si abrimos el archivo chall.py
encontramos lo siguiente.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from Crypto.Util.number import *
def gen_primes(SIZE):
p = random_prime(1 << (SIZE - 1), 1 << SIZE)
while True:
q = random_prime(1 << (SIZE - 1), 1 << SIZE)
if p < q:
p, q = q, p
if q < p < 2*q:
break
return p, q
nbits = 1024
flag = b"L3AK{<REDACTED>}"
R = RealField(nbits)
p, q = gen_primes(nbits//2)
N = p*q
phi = (p**4-1)*(q**4-1)
N_s = R(N**2)
N_ss = R(N**4)
t = (2*N_ss-49*N_s + 2)/(4*N+170*N_s)
while True:
d = randint(1, round(sqrt(t)) - 1)
if gcd(phi-d, phi) == 1:
break
e = inverse_mod(phi-d, phi)
c = pow(bytes_to_long(flag), e, N)
print(f"e = {e}\nN = {N}\nc = {c}")
'''
e = 370641246943654763647982436393968410523035056803076571952063446221981054741105804986870907803130391736840420704227524827167178043545763070520011423497365360567040835216714988776285676818833967899487393611410406708467049153990487431775151667103817558875154145780446157545062795321820537740212495675608976163877567007753523774447008611976905578477758365862741282887079873779055623972564793977884741350325450634869927603664722967323341473363320613467433998603537242156610765948379449307405122629600556105209482040761323271134932553579828576227233549741862990693111061962892676568398083446001891012661453694340879845386900986024512140441823076068075531089610607812090402852586184229193699718454197060072575595570232588935191272416546819793045623275550409871218062357273309812154110783534714662063322116568964675372602159108306251453500390105034890229052958512010283429459687714879084097494098542745605324460172680461006303552579466987732938596341830436505942616479890554056163452471835707573885837976471753073413505028206370632139586750855217201926605743452826397576584492732225029497982216694648573014796836126574081158869231364821712046050068243878660143909750030922147254462228826952501087389154612318844202411291844150163167021
N = 10222014062768125922601962004686361136447658578111413896046596746110249358112354000488449664371774177977274016313103826803116662735101208575040021998413602496525815373151213550295992813258424882626853824039678993334143891154760939712139640336395595628492284893024078520796288685014103193630287988814952604029
c = 4323184196594280140760873888779221921406692838206184372853784052006066772207175604399047711017170078453742445880600303200397632746051500194774569530024097959399922254605516672962219900174336028512116159752401576376530557036245218800162889461620882177398454137759956927838320086276276377067055171421259852996
'''
En este reto, se cifra la bandera flag
con una clave pública e
y un módulo N
, pero la forma en que e
puede ser explotada si entendemos bien la estructura del phi(N)
modificado.
Si analizamos en detalle el código podemos desglosar el siguiente funcionamiento.
- Se generan los primos siguiendo una relación especial.
- Se genera dos primos
p
yq
de 512 bits cada uno (nbits // 2). - Se asegura que los primos tengan una relación específica \(q<p<2q\)
- Se genera dos primos
- Construcción del módulo y phi (no estándar).
1
2
N = p * q
phi = (p**4 - 1)*(q**4 - 1)
- Aquí,
phi
no es el clásico $(p-1)(q-1)$, sino un valor más extraño:
- Esto es claramente una modificación artificial del RSA tradicional.
- Si se reconstruyen los primos $p, q$ podemos computar $\phi$, lo cual permite calcular la clave privada.
- Se define el valor de
t
y la generación ded
.
1
2
3
4
5
6
7
8
N_s = R(N**2)
N_ss = R(N**4)
t = (2*N_ss-49*N_s + 2)/(4*N+170*N_s)
while True:
d = randint(1, round(sqrt(t)) - 1)
if gcd(phi-d, phi) == 1:
break
- Se computa un número real
t
a partir de $N$, y luego se escoge un valord < \sqrt{t}
. - Aquí,
d
es la clave privada y contienen propiedades controladas. - Se garantiza que $\gcd(\phi - d, \phi) = 1$ para que el siguiente paso funcione.
- Cálculo del exponente público
e
.
1
e = inverse_mod(phi - d, phi)
- Esta es la parte rara e interesante:
- En lugar de usar $d = e^{-1} \mod \phi$ como en RSA normal,
- se usa: $e = (\phi - d)^{-1} \mod \phi$
- Esto permite reconstruir $d = \phi - e^{-1} \mod \phi$, si conoces
phi
.
- Por último, se cifra la
flag
siguiendo el esquema básico de RSA $c = m^e \mod N$
Solver
Según lo descrito anteriormente, sabemos la siguiente información:
- El valor
phi
está basado en $p^4$ y $q^4$, no en $(p-1)(q-1)$, lo cual rompe cualquier esquema de seguridad estándar. - El exponente público
e
está vinculado a un valord
muy pequeño (elegido menor que $\sqrt{t}$). - La condición $q < p < 2q$ puede facilitar ataques de factorización de $N$.
En este caso, la resolución de este reto viene dada por aplicar un Wiener attack custom.
El ataque de Wiener es un ataque clásico contra RSA cuando el exponente privado $d$ es demasiado pequeño, concretamente:
Si $d < \frac{1}{3}N^{1/4}$, el ataque de Wiener puede recuperar $d$ a partir de $e$ y $N$ usando fracciones continuas.
Esto funciona ya que si $e$ y $d$ son inversos módulo $\phi(N)$, entonces:
\[\frac{e}{\phi(N)} \approx \frac{k}{d}\]para algún pequeño $k$. Así que al computar los convergentes de la fracción continua de $\frac{e}{N}$, puedes encontrar el par $(k, d)$.
En este caso, tenemos un esquema RSA custom en el que:
1
e = inverse_mod(phi - d, phi)
Esto implica:
\[e \cdot (\phi - d) \equiv 1 \mod \phi \quad \Rightarrow \quad e(\phi - d) = 1 + k\phi\]Despejando podemos obtener:
\[\frac{e}{\phi} \approx \frac{k}{\phi - d}\]Por ende:
\[\frac{e}{\phi} \approx \frac{k}{\phi - d} \Rightarrow \frac{e}{\phi - d} \approx \frac{k}{\phi}\]Pero como no tenemos el valor de $\phi$, entonces se recurre a un valor estimado de $\phi$.
El script solución es el siguiente.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from Crypto.Util.number import *
e = 370641246943654763647982436393968410523035056803076571952063446221981054741105804986870907803130391736840420704227524827167178043545763070520011423497365360567040835216714988776285676818833967899487393611410406708467049153990487431775151667103817558875154145780446157545062795321820537740212495675608976163877567007753523774447008611976905578477758365862741282887079873779055623972564793977884741350325450634869927603664722967323341473363320613467433998603537242156610765948379449307405122629600556105209482040761323271134932553579828576227233549741862990693111061962892676568398083446001891012661453694340879845386900986024512140441823076068075531089610607812090402852586184229193699718454197060072575595570232588935191272416546819793045623275550409871218062357273309812154110783534714662063322116568964675372602159108306251453500390105034890229052958512010283429459687714879084097494098542745605324460172680461006303552579466987732938596341830436505942616479890554056163452471835707573885837976471753073413505028206370632139586750855217201926605743452826397576584492732225029497982216694648573014796836126574081158869231364821712046050068243878660143909750030922147254462228826952501087389154612318844202411291844150163167021
N = 10222014062768125922601962004686361136447658578111413896046596746110249358112354000488449664371774177977274016313103826803116662735101208575040021998413602496525815373151213550295992813258424882626853824039678993334143891154760939712139640336395595628492284893024078520796288685014103193630287988814952604029
c = 4323184196594280140760873888779221921406692838206184372853784052006066772207175604399047711017170078453742445880600303200397632746051500194774569530024097959399922254605516672962219900174336028512116159752401576376530557036245218800162889461620882177398454137759956927838320086276276377067055171421259852996
def expansion(nominator, denominator):
a = []
residue = nominator % denominator
a.append(nominator // denominator)
while residue != 0:
nominator = denominator
denominator = residue
residue = nominator % denominator
a.append(nominator // denominator)
return a
def convergents(a):
nominators = []
denominators = []
for i in range(len(a)):
if i == 0:
nominators.append(a[i])
denominators.append(1)
elif i == 1:
nominators.append(1 + a[i] * a[i - 1])
denominators.append(a[i])
else:
nominators.append(nominators[i - 2] + a[i] * nominators[i - 1])
denominators.append(denominators[i - 2] + a[i] * denominators[i - 1])
return nominators, denominators
R = RealField(1024)
N_s = R(N**2)
N_ss = R(N**4)
t = (2*N_ss - 49*N_s + 2) / (4*N + 170*N_s)
a = expansion(e, N**4)
ks, ds = convergents(a)
for i in range(len(ks)):
if ds[i] < t and ds[i] > 0:
try:
phi = (ds[i] * e + 1) / ks[i]
flag =pow(c, phi - ds[i], N)
except:
continue
flag = long_to_bytes(flag)
print(f"[+] Flag: {flag}")
Flag
L3AK{L0wK3y_Th1S_RSA_i5_kiNda_ScuFf3D_LmA0}'