Diskretna Enkripcija (Discreet Encryption)

Task description

Diskretnost je bitan faktor enkripcije. Možeš li ju učiniti indiskretnom? (Discretion is an important part of encryption. Can you make it indiscreet?)

The task’s title is a pun: “diskretna” (discrete, as in the discrete logarithm problem) sounds like “diskretna” (discreet), and the hint plays on both meanings at once.

What the server does

On connection, it generates a keypair for an ElGamal-style scheme and prints the public key, (y, g, N), then acts as a decryption oracle for anything sent to it. The private key x is the flag’s 12 ASCII digits, read as one large number, so recovering x from y = g^x mod N directly recovers the flag.

Why the modulus gives it away

N isn’t a random large prime; the key generation builds it as a product of twenty primes, with bit sizes stepping up from 10 bits to 105 bits, multiplied by a small adjustment factor k chosen just large enough to make the whole product prime. That construction makes N - 1 highly composite (a product of many small factors), which is exactly the condition that makes the discrete logarithm problem solvable: the Pohlig-Hellman algorithm reduces solving y = g^x mod N to solving it separately modulo each prime factor of N - 1, each one a far smaller and easier problem, then combining the per-factor answers with the Chinese Remainder Theorem.

Since the flag’s 12 ASCII digits make x roughly 96 bits, only enough of N - 1’s smaller prime factors need to be found, enough that their product exceeds about 96 bits, not all twenty.

The attack

1. Connect and read the public key.
2. Partially factor N - 1. Trial division up to about 2^22 picks off every prime factor in the 2 to 20 bit range (roughly 50 bits of product); Pollard’s rho factoring handles a few medium-sized factors in the 25 to 30+ bit range on top of that, enough together to clear the 96-bit threshold.
3. Solve the discrete log modulo each factor. For each prime power factor p^e of N - 1:
   • compute g_i = g^((N-1)/p^e) mod N and y_i = y^((N-1)/p^e) mod N, reducing the problem into the small subgroup of order p^e,
   • solve g_i^{x_i} = y_i mod N for x_i with baby-step giant-step, practical here because p^e itself is small,
   • that gives x mod p^e.
4. Combine with the Chinese Remainder Theorem across every factor solved this way to recover x modulo the product of all of them, which is large enough to pin x down exactly.
5. Decode. Converting the recovered integer back to bytes gives the flag’s 12-digit content directly.

The exploit

from pwn import remote
from sympy import factorint
from Crypto.Util.number import long_to_bytes
import gmpy2

r = remote('chal.live.hackultet.hr', 14023)
data = r.recvuntil(b'\n', drop=False).decode()
y, g, N = (int(v) for v in data.split())   # public key, read from the banner

def bsgs(g, y, p, e, N):                    # discrete log in the small subgroup of order p**e
    order = p ** e
    table = {}
    step = gmpy2.iroot(order, 2)[0] + 1
    cur = 1
    for j in range(step):
        table[cur] = j
        cur = (cur * g) % N
    factor = gmpy2.invert(pow(g, step, N), N)
    cur = y
    for i in range(step):
        if cur in table:
            return i * step + table[cur]
        cur = (cur * factor) % N

# partially factor N - 1: trial division for the small primes, Pollard's rho for the rest
small_factors = trial_division(N - 1, bound=1 << 22)
remaining = (N - 1) // product(p ** e for p, e in small_factors.items())
medium_factors = pollards_rho(remaining)
factors = {**small_factors, **medium_factors}

residues, moduli = [], []
for p, e in factors.items():
    pe = p ** e
    gi = pow(g, (N - 1) // pe, N)
    yi = pow(y, (N - 1) // pe, N)
    residues.append(bsgs(gi, yi, p, e, N))
    moduli.append(pe)

x = gmpy2.mpz(0)
M = 1
for a, m in zip(residues, moduli):           # Chinese Remainder Theorem
    x = crt_combine(x, M, a, m)
    M *= m

print(long_to_bytes(int(x)))   # CTF2026[364988916431]

trial_division, pollards_rho and crt_combine are standard, and gmpy2/pycryptodome handle the large-integer arithmetic; the sketch keeps the shape of the actual Pohlig-Hellman loop, which is the part that matters here.

Why this matters beyond the puzzle

The security of any discrete-log-based scheme depends entirely on the group having large prime-order subgroups. A modulus built, even unintentionally, from many small prime factors turns what looks like a hard problem into a sequence of easy ones; this is exactly why real-world discrete-log and Diffie-Hellman setups are specified with primes chosen so that p - 1 has at least one very large prime factor.