# Bancarrota

**Categoría:** Crypto\
**Dificultad:** Hard

### Descripción del reto

El reto entrega un `output.txt` con los siguientes datos públicos:

```
n = 88414814868035811675053476790757183219833077857790658518374191743395116845115061528008085663634920575725860680618605233668935227198665125936037136388097458649126677107202112594942802316604869417510426361858052660647273709287613460403410412181509561538712695138630895924830183589161717870494320335995725649113
e = 65537
c = 30250981509850990129207765287429103048296430271684860662908644684691614716869020256328990837924296007698218340267714279683758265003409499090708049047183680954260669691735105649990968201405808149637466756340163849831054862762698907574073537414698212342127587114243405245474354105150576516832016218254233551030
p_msb = 6384482865957816600821075381730956442412139232241618654154874067983428432778076832168977
unknown_bits = 220
```

El enunciado indica que el sistema RSA de una entidad bancaria ha filtrado los bits más significativos de uno de los primos usados para generar la clave.

La pregunta real del reto es:

¿Se puede romper RSA si solo conocemos una parte de uno de sus factores?

La respuesta es sí, si esa parte filtrada es suficientemente grande y la parte desconocida es suficientemente pequeña como para usar un ataque de Coppersmith / small roots.

## 1. Análisis inicial

En un RSA estándar se publica:

* `n`
* `e`
* y a veces el ciphertext `c`

Pero aquí aparece además:

* `p_msb`
* `unknown_bits`

Eso ya indica que no estamos ante un RSA “normal”, sino ante un RSA con fuga parcial de clave.

Un jugador que vea esto debería pensar inmediatamente:

* `p_msb` representa la parte alta de `p`
* faltan `unknown_bits` bits por recuperar
* por tanto, `p` puede modelarse como una parte conocida más una parte pequeña desconocida

La observación clave es:

```
p = (p_msb << unknown_bits) + x
```

donde:

* `p_msb << unknown_bits` es la parte conocida de `p`
* `x` es la parte desconocida
* y `x < 2^unknown_bits`

En este reto:

* conocemos todos los bits altos de `p`
* faltan 220 bits bajos
* eso hace que `x` sea una raíz pequeña

Y ahí es donde entra Coppersmith.

## 2. Fundamento teórico

RSA usa dos primos `p` y `q` para construir:

```
n = p * q
```

La seguridad depende de que factorizar `n` sea difícil.

Pero si conocemos parcialmente uno de esos primos, podemos escribir:

```
p = a + x
```

donde:

* `a` es la parte conocida
* `x` es la parte desconocida y pequeña

En este caso:

```
a = p_msb << unknown_bits
```

y el primo real es:

```
p = a + x
```

Como `p` divide a `n`, si logramos recuperar `x`, recuperamos `p`, luego `q`, y RSA queda roto por completo.

El método de Coppersmith permite encontrar raíces pequeñas de polinomios módulo un entero compuesto. Aquí usamos el polinomio:

```
f(X) = a + X
```

y buscamos una raíz pequeña `x` tal que:

```
a + x = p
```

con `p` divisor de `n`.

## 3. Idea del ataque

El atacante piensa así:

1. Tengo `n`, `e`, `c` y una fuga parcial de `p`
2. Construyo la parte conocida:
3. Escribo:

```
p = a + x
```

4. Como `x` es pequeño, pruebo un ataque de `small_roots`
5. Recupero `p`
6. Calculo `q = n / p`
7. Recupero `d`
8. Descifro `c`

## 4. Solución con Sage

La forma práctica y estándar de resolver este tipo de reto en CTF es con **SageMath**.

### Script completo

```
from sage.all import *

# Datos públicos del reto
n = Integer(88414814868035811675053476790757183219833077857790658518374191743395116845115061528008085663634920575725860680618605233668935227198665125936037136388097458649126677107202112594942802316604869417510426361858052660647273709287613460403410412181509561538712695138630895924830183589161717870494320335995725649113)

e = Integer(65537)

c = Integer(30250981509850990129207765287429103048296430271684860662908644684691614716869020256328990837924296007698218340267714279683758265003409499090708049047183680954260669691735105649990968201405808149637466756340163849831054862762698907574073537414698212342127587114243405245474354105150576516832016218254233551030)

p_msb = Integer(6384482865957816600821075381730956442412139232241618654154874067983428432778076832168977)

unknown_bits = Integer(220)

# Parte conocida de p
a = p_msb << unknown_bits

print("[*] Parte conocida de p reconstruida")
print("[*] Probando varias configuraciones de Coppersmith...")

# Polinomio f(x) = a + x sobre Z/nZ
PR.<x> = PolynomialRing(Zmod(n))
f = x + a

found = False
x0 = None

# Varias configuraciones para dar margen al ataque
for beta in [0.40, 0.45, 0.49]:
    for extra in [0, 4, 8, 12]:
        X = 2^(int(unknown_bits) + extra)
        print(f"[*] Intentando beta={beta}, X=2^({int(unknown_bits)+extra})")
        roots = f.small_roots(X=X, beta=beta)
        if roots:
            x0 = Integer(roots[0])
            found = True
            break
    if found:
        break

if not found:
    print("[-] No se encontró raíz pequeña con esta instancia.")
    raise SystemExit

p = a + x0

print("[+] Candidato a p encontrado")

if n % p != 0:
    print("[-] La raíz encontrada no factoriza n.")
    raise SystemExit

q = n // p

print("[+] Factorización correcta")
print(f"p = {p}")
print(f"q = {q}")

# Recuperar clave privada
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)

# Descifrar
m = power_mod(c, d, n)

# Convertir a bytes
msg = int(m).to_bytes((int(m).bit_length() + 7) // 8, "big")

print("[+] Flag:")
print(msg.decode())
```

## 5. Explicación detallada del script

### 5.1 Carga de datos

```
n = Integer(...)
e = Integer(...)
c = Integer(...)
p_msb = Integer(...)
unknown_bits = Integer(220)
```

Aquí se cargan los parámetros públicos del reto.

* `n` es el módulo RSA
* `e` es el exponente público
* `c` es el ciphertext
* `p_msb` es la parte alta filtrada del primo `p`
* `unknown_bits` indica cuántos bits faltan

### 5.2 Reconstrucción parcial de `p`

```
a = p_msb << unknown_bits
```

Desplazar a la izquierda `unknown_bits` posiciones equivale a colocar los bits altos en su posición correcta dentro del entero.

Eso construye la parte conocida del primo:

```
p ≈ a
```

pero aún faltan los bits bajos:

```
p = a + x
```

### 5.3 Construcción del polinomio

```
PR.<x> = PolynomialRing(Zmod(n))
f = x + a
```

Esto define el polinomio:

```
f(x) = a + x
```

trabajando módulo `n`.

La idea es que queremos encontrar un valor pequeño `x` tal que `a + x` sea realmente el factor `p` de `n`.

### 5.4 Búsqueda de raíz pequeña

```
roots = f.small_roots(X=X, beta=beta)
```

Esta es la parte central del ataque.

**Coppersmith** permite encontrar raíces pequeñas de polinomios módulo un entero compuesto. Aquí le decimos a Sage:

* `X` = tamaño máximo aproximado de la raíz
* `beta` = parámetro del algoritmo

El script prueba varias combinaciones porque en la práctica algunas instancias necesitan pequeños ajustes para converger.

### 5.5 Validación del candidato

```
p = a + x0
if n % p != 0:
    ...
```

Aunque `small_roots` devuelva algo, siempre hay que comprobar que de verdad factoriza `n`.

Si `p` divide a `n`, entonces hemos recuperado el primo correcto.

### 5.6 Recuperación de `q`

```
q = n // p
```

Una vez recuperado `p`, el otro factor es inmediato.

### 5.7 Cálculo de la clave privada

```
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
```

Con los factores ya obtenidos, RSA se rompe de forma estándar:

* calculamos `phi(n)`
* calculamos el inverso modular de `e`
* obtenemos `d`

### 5.8 Descifrado

```
m = power_mod(c, d, n)
```

Aplicamos la fórmula RSA de descifrado:

```
m = c^d mod n
```

### 5.9 Conversión a texto

```
msg = int(m).to_bytes((int(m).bit_length() + 7) // 8, "big")
print(msg.decode())
```

Esto transforma el entero descifrado en bytes y luego en texto legible.

## 6. Resultado

La salida del script es:

```
THL{...}
```

Este reto demuestra una idea muy importante en criptografía aplicada:

> RSA no solo falla si alguien factoriza `n` por fuerza bruta; también puede romperse si se filtra suficiente información parcial sobre uno de sus factores.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://beafn28.gitbook.io/beafn28/mis-ctfs/bancarrota.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.