Roll Your Own

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: linear_discrete_log, n_eq_q2_g_eq_1_plus_q, paillier_subgroup_trick, recover_private_key

Summary

Walkthrough of the CUSTOM Crypto Roll Your Own. 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: ch

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}"}

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

Key Takeaways / Lessons

• Mastering linear_discrete_log, n_eq_q2_g_eq_1_plus_q, paillier_subgroup_trick, recover_private_key was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-06-22 • CUSTOM • Roll Your Own • Difficulty: Medium