Implicit Twins — RSA Lattice Attack

Challenge

Two 1280-bit RSA keys, separated at birth. Neither of them will talk alone.

The challenge provides two RSA moduli, N1 and N2, a public exponent e = 65537, and a ciphertext ct. The flag is textbook RSA-encrypted under N1.

The source code reveals the weakness:

• N1 = p1 * q1 and N2 = p2 * q2.
• Each p is 1024 bits and each q is 256 bits.
• The two p primes share their lowest 530 bits.
• The ciphertext is pow(flag_as_integer, e, N1).

The shared low bits are the key to recovering the factors.

1. Derive a relation between the small factors

Write

[ N_1 = p_1q_1,\qquad {=tex}N_2 = p_2q_2. ]

The primes p1 and p2 have the same lowest 530 bits, so with (M=2^{530}),

[ p_1 \equiv {=tex}p_2 \pmod {=tex}M. ]

Using (p_1=N_1/q_1) and (p_2=N_2/q_2), multiply the congruence by (q_1q_2):

[ N_1q_2 \equiv {=tex}N_2q_1 \pmod {=tex}M. ]

Since N1 is odd, it is invertible modulo (M). Define

[ r \equiv {=tex}N_2N_1^{-1}\pmod {=tex}M. ]

Then

[ q_2 \equiv {=tex}rq_1 \pmod {=tex}M. ]

Both unknown q factors are only 256 bits, while the modulus of this congruence is 530 bits. This gives a short-vector problem in a two-dimensional lattice.

2. Construct the lattice and run LLL

The lattice generated by the row vectors

[ (1,r),\qquad {=tex}(0,M) ]

contains vectors of the form

[ (x, rx+kM). ]

Because (q_2 \equiv {=tex}rq_1 \pmod {=tex}M), the vector ((q_1,q_2)) belongs to this lattice. Its coordinates are only 256 bits, making it a short vector. LLL reduction exposes this vector for these challenge parameters.

3. Recover the factors and decrypt

Once q1 and q2 are recovered, calculate

[ p_1=N_1/q_1,\qquad {=tex}p_2=N_2/q_2. ]

Then compute the private exponent using

[ \varphi{=tex}(N_1)=(p_1-1)(q_1-1),\qquad{=tex} d=e^{-1}\pmod{\varphi(N_1)}{=tex}. ]

Finally, decrypt with (m=ct^d\bmod {=tex}N_1) and convert the integer to bytes.

Solver

Save the challenge's output(1).json beside this script as output(1).json. Install SymPy if needed with python -m pip install sympy.

#!/usr/bin/env python3
import json
from sympy import Matrix, Rational

with open("output(1).json", "r") as f:
    data = json.load(f)

N1 = data["N1"]
N2 = data["N2"]
e = data["e"]
ct = data["ct"]

# The p factors share their lowest 530 bits.
T = 530
M = 1 << T

# q2 = r*q1 (mod M)
r = (N2 * pow(N1, -1, M)) % M

# Row lattice generated by (1, r) and (0, M).
basis = Matrix([
    [1, r],
    [0, M],
])
reduced = basis.lll(delta=Rational(3, 4))

# Find the reduced vector whose coordinates divide their moduli.
for row in range(2):
    x, y = (abs(int(v)) for v in reduced.row(row))
    if x > 1 and y > 1 and N1 % x == 0 and N2 % y == 0:
        q1, q2 = x, y
        break
else:
    raise RuntimeError("Could not identify the factors from the LLL basis")

p1 = N1 // q1
p2 = N2 // q2

# Verify the recovered factors and the shared low bits.
assert p1 * q1 == N1
assert p2 * q2 == N2
assert p1 % M == p2 % M
print("[+] Recovered q1 and q2")
print("[+] Shared 530 low bits verified")

# Decrypt textbook RSA under N1.
phi = (p1 - 1) * (q1 - 1)
d = pow(e, -1, phi)
m = pow(ct, d, N1)

flag = m.to_bytes((m.bit_length() + 7) // 8, "big")
print("[+] Flag:", flag.decode())

Run it:

python solve.py

Flag

isfcr{1mpl1c1t_f4ct0r1ng_0f_tw1ns}

Takeaway

RSA's security depends on the difficulty of factoring each modulus. Here, the moduli do not share a prime, but their large prime factors share 530 low bits because of a flawed generator. That cross-key relationship creates a short lattice vector revealing the 256-bit factors. Once N1 is factored, textbook RSA decryption is straightforward.