0xL4ughCTF 2025 - DORYA

just like tekken, spamming the same move, i mean encryption, many times is unbeatable.

Source code

from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, inverse

FLAG = b"0xL4ugh{long_redacted_flag_AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}"
KEY_BITS = 1024
X = 7 
def boke(m, coeffs):
    a, b, c_coef, d = coeffs

    key = RSA.generate(KEY_BITS, e=X)

    num = a * m + b
    den = c_coef * m + d
    den_inv = inverse(den, key.n)
    padded_m = (num * den_inv) % key.n

    c = pow(padded_m, key.e, key.n)

    coeffs[0] += 2**1024
    coeffs[1] += 4**1024
    coeffs[2] += 6**1024
    coeffs[3] += 8**1024

    return {"n": key.n, "c": c}


m = bytes_to_long(FLAG)
out = []
coeffs = [1 * 2**1024, 3 * 2**1024, 3 * 2**1024, 7 * 2**1024]

for i in range(7):
    out.append(boke(m, coeffs))

with open("out.txt", "w") as fp:
    print(out, file=fp)

Analysis

We are given an RSA padding scheme which is basically:
padded = $(a.m + b)/(c.m + d)$

The same message is encrypted 7 times with different values of $a,b,c,d$.
$e = 7$ , $N = p.q$
Bit length of $N$ is 1024 bits.

Parameters

\(a_i = 1*2^{1024} + i*2^{1024}\)
\(b_i = 3*2^{1024} + i*4^{1024}\)
\(c_i = 3*2^{1024} + i*6^{1024}\)
\(d_i = 7*2^{1024} + i*8^{1024}\)

for $0 \le i \le 6$

Solve Steps:

1. Construct 7 polynomials
2. Compute CRT
3. Coppersmith’s method to find its roots

1. Construct 7 polynomials

We have, for ciphertext $C_i$:
\(C_i \equiv ((a.m + b)/(c.m + d))^{7} \pmod{N_i}\)
\(C_i*(c.m + d)^7 \equiv (a.m+b)^7 \pmod{N_i}\)
\(C_i*(c.m + d)^7 - (a.m+b)^7 \equiv 0 \pmod{N_i}\)

We can construct the polynomial $P_i$
$P_i(x) = C_i*(c.x + d)^7 - (a.x+b)^7 \equiv 0 \pmod{N_i}$
Which has a root at $x=flag$

We have 7 such polynomials.
We can now do CRT on all of them since they are of the form:

$P_1(x) \equiv 0 \pmod{N_i}$
$P_2(x) \equiv 0 \pmod{N_2}$
$P_3(x) \equiv 0 \pmod{N_3}$
$\vdots$
$P_7(x) \equiv 0 \pmod{N_7}$

2. Compute CRT

CRT (Chinese Remainder Theorem) will give us a polynomial:
$P(x) \equiv 0 \pmod{N_1.N_2.N_3…N_7}$
(This can be made by taking the CRT of every coefficient corresponding to a particular power in each polynomial and constructing the new polynomial with that result, for all powers upto 7)

3. Coppersmith’s method to find its roots

This is a polynomial of degree 7, which would look something like this:
$P(x) = a_0 + a_1.x +a_2.x^2 + \ldots + a_7.x^7$

This polynomial’s roots can be computed with Coppersmith’s method, to get the flag.
Sagemath’s .small_roots() function can be used for this.

Solve Script

from Crypto.Util.number import long_to_bytes

with open("out.txt") as file:
    data = eval(file.read())

Ns, Cs = [], []

for i in data:
    Ns.append(i["n"])
    Cs.append(i["c"])

a,b,c,d = 1*2**1024, 3*2**1024, 3*2**1024, 7*2**1024
a_inc, b_inc, c_inc, d_inc = 2**1024, 4**1024, 6**1024, 8**1024

all_coeffs = []

for i in range(7):
    P_ring = PolynomialRing(Zmod(Ns[i]), "x")
    x = P_ring.gen()

    A = a + i*a_inc
    B = b + i*b_inc
    C = c + i*c_inc
    D = d + i*d_inc

    poly = (A*x + B)**7 - Cs[i]*(C*x + D)**7
    coeffs = poly.coefficients(sparse=False)
    all_coeffs.append(coeffs)

final_coeffs = []
for j in range(8):
    c_list = [int(all_coeffs[x][j]) for x in range(7)]
    crt_val = crt(c_list, Ns)
    final_coeffs.append(crt_val)

N = prod(Ns)
P = PolynomialRing(Zmod(N), "x")

final_poly = P(final_coeffs).monic()

x = int(final_poly.small_roots(epsilon=0.04)[0])
flag = long_to_bytes(x).decode()

print(flag)

Flag

0xL4ugh{long_long_long_long_long_long_long_long_long_long_long_flag56af09d36f}