DLP Easy

Platform: spbctf | Category: Crypto | Type: Challenge | Difficulty: Easy | OS: NA | Author: XESXOR | Date: 2026-03-09 | Status: Solved Techniques: brute_force_dlp, small_curve_enumeration

Summary

Task: Solve ECDLP on small curve y² = x³ - 3x + 1 mod 257, find secret scalar d where Q = d*P. Solution: Brute force all possible d values (1 to 251) since curve order is small prime.

DLP Easy — CryptoKids 2.0

Description

Elliptic curve discrete logarithm problem on a small curve. Given curve y² = x³ - 3x + 1 mod 257 and point Q = d*P = (255, 16). Find the secret scalar d.

Analysis

• Curve: y² = x³ - 3x + 1 (mod 257)
• Small prime modulus p = 257 means at most ~257 points on curve
• Actual curve order is 251 (prime)
• Q = (255, 16) is given as d*P
• Generator P was not explicitly specified in the task
• With such small order, brute force is trivial

Solution

Since the curve has at most 257 points and the order is 251 (prime), we can simply try all possible values of d from 1 to 251 and check which one gives Q. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
DLP Easy - CryptoKids 2.0
Brute force ECDLP on small curve
"""

# Curve parameters
p = 257
a = -3
b = 1

# Target point Q = d*P
Q = (255, 16)

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  # Point at infinity
    
    if P1 == P2:
        # Point doubling
        lam = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p
    else:
        # Point addition
        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 using double-and-add"""
    result = None
    addend = P
    
    while k:
        if k & 1:
            result = point_add(result, addend, a, p)
        addend = point_add(addend, addend, a, p)
        k >>= 1
    
    return result

def find_generator():
    """Find a generator point on the curve"""
    for x in range(p):
        rhs = (x**3 + a*x + b) % p
        # Check if rhs is a quadratic residue
        if pow(rhs, (p-1)//2, p) == 1:
            y = pow(rhs, (p+1)//4, p)  # Works for p ≡ 3 (mod 4)
            return (x, y)
    return None
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Find a generator
G = find_generator()
print(f"Generator G = {G}")

# Brute force: try all d from 1 to curve order
curve_order = 251  # Prime order

for d in range(1, curve_order + 1):
    R = scalar_mult(d, G, a, p)
    if R == Q:
        print(f"Found d = {d}")
        print(f"Verification: {d} * G = {R}")
        break
else:
    print("d not found with this generator, trying other points...")
    
    # Try all points as potential base
    for x in range(p):
        rhs = (x**3 + a*x + b) % p
        if pow(rhs, (p-1)//2, p) == 1:
            y = pow(rhs, (p+1)//4, p)
            P = (x, y)
            
            for d in range(1, curve_order + 1):
                R = scalar_mult(d, P, a, p)
                if R == Q:
                    print(f"Found: d = {d}, base point P = {P}")
                    break
            else:
                continue
            break
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Answer: d = REDACTED

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