1, 2, 3...Fusión, ya!.md

1, 2, 3...Fusión, ya!

Description

🧬🧬🧬🧬🧬🧬

Archivos:

• output.txt
• fusion.py

Solution

El archivo output.txt proporciona las claves públicas RSA y el entero r de 1024 bits. r se compone de bits impares de p y bits pares de q.

Aplicamos una solución adecuada para r y recuperamos bits impares de p y bits pares de q.

Usando estas dos partes y N, podemos recuperar p y q. Si conocemos los k bits más bajos de p y q, los k bits más bajos de pq son iguales a los k bits más bajos de N. Entonces, en esta situación, conocemos los k bits más bajos de p y los k-1 bits más bajos de q. Por fuerza bruta en el bit k de q y aplicamos el bit que resulta si el bit más bajo de pq es igual al k bit más bajo de N. Esto es porque el k bit de q tiene solo dos posibilidades, 0 o 1.

En el solver hay que tener cuidado en intercambiar alternativamente p y q en una sola iteración.

with open("output.txt") as f:
    n = int(f.readline().split()[-1])
    e = int(f.readline().split()[-1])
    encrypt = int(f.readline().split()[-1])
    r = int(f.readline().split()[-1])

# split p and q from r
pq = []
mask = int("55" * 128, 16)
pq.append(r & mask)
mask <<= 1
pq.append(r & mask)
if pq[0] > pq[1]:
    pq[0], pq[1] = pq[1], pq[0]

# recover p and q
for bit in range(0, 8 * 128 + 1):
    target = int(bit % 2 == 0)
    candidate = pq[target] + (1 << bit)
    mask = int("1" * (bit + 1), 2)
    n_sub = n & mask
    if (candidate * pq[target - 1]) & mask == n_sub:
        pq[target] = candidate
assert pq[0] * pq[1] == n

# decrypt
phi = (pq[0] - 1) * (pq[1] - 1)
d = pow(e, -1, phi)
plain = pow(encrypt, d, n)
print(plain.to_bytes(64, byteorder="big").decode())

Flag

LetsCTF{0n3_tw0_thr33_f4ct0riz4t10n}