Roll Your Own

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-22 | Status: Solved Techniques: linear_discrete_log, n_eq_q2_g_eq_1_plus_q, paillier_subgroup_trick, recover_private_key

Summary

Task: a discrete-log 'prove me wrong' game. Server picks a 512-bit prime q, you submit (g,n) with pow(g,q,n)==1, it returns h=pow(g,x,n) for a secret x in [0,q] and asks you to recover x. Solution: choose n=q^2 and g=1+q (the Paillier generator). Then pow(g,q,n)=(1+q)^q = 1 mod q^2 (binomial higher terms vanish), and g^x = 1 + q*x mod q^2, so the discrete log is linear: x = ((h-1)//q) mod q. Submit x and get the flag.

Roll Your Own — cryptohack (Mathematics)

Description

"Cracking discrete logarithms is hard. Change my mind. I'll even let you use your own parameters, as long as the modulus is of the given order." Connect at socket.cryptohack.org 13403.

Server flow (13403.py):

 python read-only • copy allowed Copy
self.q = getPrime(512)
self.x = random.randint(2, self.q)
# Step 1: server sends hex(q), asks for (g, n)
def check_params(self, data):
    self.g = int(data['g'], 16); self.n = int(data['n'], 16)
    if self.g < 2:  return False
    if self.n < 2:  return False
    if pow(self.g, self.q, self.n) != 1: return False   # g must have order dividing q mod n
    return True
# Step 2: server sets x = randint(0, q), sends h = pow(g, x, n), asks for x
def check_secret(self, data):
    return self.x == int(data['x'], 16)                  # exact match -> flag

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

We freely choose g and n, the only constraint being pow(g, q, n) == 1. Then we must recover the secret exponent x from h = g^x mod n.

Analysis

If n is prime with q | n-1, then g lives in an order-q subgroup and the discrete log is a genuinely hard 512-bit DLP. The intended escape is to pick parameters that make the DLP trivial — the Paillier structure.

Choose:

n = q^2
g = 1 + q

Check the constraint: by the binomial theorem (1 + q)^q = 1 + q·q + C(q,2)·q^2 + ... ≡ 1 (mod q^2) (every term from the second onward carries a factor q^2). So pow(g, q, n) == 1. ✓ ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Now the discrete log is linear. For any exponent x:

g^x = (1 + q)^x = 1 + q·x  (mod q^2)

again because all higher binomial terms vanish mod q^2. Hence given h = g^x mod q^2:

x = (h - 1) / q   (mod q)

This is exactly the decryption step of the Paillier cryptosystem (the L function L(u) = (u - 1) / n).

Solution

 python read-only • copy allowed Copy
import socket, json, re
s = socket.create_connection(('socket.cryptohack.org', 13403), timeout=30)
f = s.makefile('rwb')
def readline(): return f.readline().decode()
def send(o): f.write((json.dumps(o) + '\n').encode()); f.flush()
def hexval(line): return int(re.search(r'"(0x[0-9a-fA-F]+)"', line).group(1), 16)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

q = hexval(readline())              # Step 1: server's prime q
n = q * q
g = 1 + q
send({"g": hex(g), "n": hex(n)})

h = hexval(readline())              # Step 2: h = g^x mod n
x = ((h - 1) // q) % q              # linear discrete log
send({"x": hex(x)})
print(readline())                   # flag

Output:

What is my private key: {"flag": "crypto{REDACTED}"}

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍