DLP Medium

Platform: spbctf | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-03-09 | Status: Solved Techniques: baby_step_giant_step, chinese_remainder_theorem, pohlig_hellman

Summary

Task: ECC discrete logarithm on a curve with smooth order. Solution: Pohlig-Hellman attack decomposing DLP into small subgroups, solving each with BSGS, combining via CRT.

DLP Medium — CryptoKids 2.0

Description

Elliptic curve discrete logarithm problem on a larger curve. Given:

• Prime p = 412220184797
• Generator G = (56797798272, 349018778637)
• Public point Q = d*G = (191614453055, 323626010179)
• Find the secret scalar d

Analysis

• Curve modulus p = 412220184797 (~40 bits)
• Direct brute force infeasible
• Curve order = 412220625192 = 2³ × 3² × 1123 × 5098207
• Order of generator G = 137406875064
• Smooth order enables Pohlig-Hellman attack
• Solve DLP in each prime power subgroup, combine with CRT ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

The Pohlig-Hellman algorithm exploits smooth group order:

1. Factor the order: n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ
2. For each prime power pᵢ^eᵢ:
   • Compute Gᵢ = (n/pᵢ^eᵢ) × G (generator of subgroup)
   • Compute Qᵢ = (n/pᵢ^eᵢ) × Q
   • Solve DLP: dᵢ ≡ d (mod pᵢ^eᵢ) using BSGS
3. Combine results using Chinese Remainder Theorem

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
DLP Medium - CryptoKids 2.0
Pohlig-Hellman attack on ECC with smooth order
"""

from math import isqrt, gcd
from functools import reduce
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Curve parameters (Weierstrass form: y² = x³ + ax + b mod p)
p = 412220184797
# a and b would be given in the task

# Points
G = (56797798272, 349018778637)
Q = (191614453055, 323626010179)

# Curve order and factorization
curve_order = 412220625192
# 412220625192 = 2^3 * 3^2 * 1123 * 5098207
order_factors = [(2, 3), (3, 2), (1123, 1), (5098207, 1)]

# Order of generator G
G_order = 137406875064
# 137406875064 = 2^3 * 3^2 * 1123 * 1699402 + 1? 
# Actually: 137406875064 = 8 * 9 * 1123 * 1699402.something
# Let's use the factorization that works
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def point_add(P1, P2, a, p):
    """Add two points on elliptic curve"""
    if P1 is None:
        return P2
    if P2 is None:
        return P1
    
    x1, y1 = P1
    x2, y2 = P2
    
    if x1 == x2 and y1 == (-y2) % p:
        return None
    
    if P1 == P2:
        lam = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p
    else:
        lam = (y2 - y1) * pow(x2 - x1, -1, p) % p
    
    x3 = (lam * lam - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p
    
    return (x3, y3)

def scalar_mult(k, P, a, p):
    """Scalar multiplication"""
    if k == 0 or P is None:
        return None
    
    result = None
    addend = P
    k = k % (curve_order + 1)  # Reduce k
    
    while k:
        if k & 1:
            result = point_add(result, addend, a, p)
        addend = point_add(addend, addend, a, p)
        k >>= 1
    
    return result
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def bsgs(G, Q, n, a, p):
    """Baby-step Giant-step algorithm for ECDLP"""
    m = isqrt(n) + 1
    
    # Baby steps: compute j*G for j = 0, 1, ..., m-1
    baby_steps = {}
    current = None  # Point at infinity = 0*G
    for j in range(m):
        if current is not None:
            baby_steps[current] = j
        else:
            baby_steps["inf"] = j
        current = point_add(current, G, a, p)
    
    # Giant step factor: -m*G
    mG = scalar_mult(m, G, a, p)
    neg_mG = (mG[0], (-mG[1]) % p) if mG else None
    
    # Giant steps: compute Q + i*(-m*G) for i = 0, 1, ..., m-1
    gamma = Q
    for i in range(m):
        key = gamma if gamma is not None else "inf"
        if key in baby_steps:
            j = baby_steps[key]
            x = (i * m + j) % n
            return x
        gamma = point_add(gamma, neg_mG, a, p)
    
    return None
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def pohlig_hellman(G, Q, order, factors, a, p):
    """Pohlig-Hellman algorithm"""
    remainders = []
    moduli = []
    
    for (prime, exp) in factors:
        pe = prime ** exp
        
        # Compute subgroup generator and target
        cofactor = order // pe
        Gi = scalar_mult(cofactor, G, a, p)
        Qi = scalar_mult(cofactor, Q, a, p)
        
        if Gi is None:
            continue
        
        # Solve DLP in subgroup of order pe
        di = bsgs(Gi, Qi, pe, a, p)
        
        if di is not None:
            remainders.append(di)
            moduli.append(pe)
            print(f"d ≡ {di} (mod {pe})")
    
    # Chinese Remainder Theorem
    return crt(remainders, moduli)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def crt(remainders, moduli):
    """Chinese Remainder Theorem"""
    M = reduce(lambda x, y: x * y, moduli)
    result = 0
    
    for ri, mi in zip(remainders, moduli):
        Mi = M // mi
        yi = pow(Mi, -1, mi)
        result += ri * Mi * yi
    
    return result % M

# Solve (need actual curve parameter a)
# a = ...  # From task
# d = pohlig_hellman(G, Q, G_order, order_factors, a, p)
# print(f"Secret d = {d}")

# Answer found: d = REDACTED
print("Flag: REDACTED")

Pohlig-Hellman Algorithm Step by Step:

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

1. Factor the order: 412220625192 = 2³ × 3² × 1123 × 5098207

2. For each prime power:

   • Compute point in subgroup: Gᵢ = (n/pᵢᵉⁱ) × G
   • Compute image: Qᵢ = (n/pᵢᵉⁱ) × Q
   • Solve DLP in small subgroup using BSGS

3. Combine via CRT:

   • d ≡ d₁ (mod 8)
   • d ≡ d₂ (mod 9)
   • d ≡ d₃ (mod 1123)
   • d ≡ d₄ (mod 5098207)
   • → d (mod 412220625192) ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍