Plus Plus

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

Summary

Task: elliptic curve point addition on y² = x³ - 3x + 1 over GF(257), given points P(8,177) and Q(234,53). Solution: applied standard ECC point addition formulas to compute P + Q = (31, 245), flag is coordinate concatenation REDACTED.

Plus Plus — CryptoKids20

Description

A task on elliptic curve point addition. Given a curve y² = x³ - 3x + 1 over finite field GF(257), and two points P(8,177) and Q(234,53). Need to find the sum P + Q.

Analysis

1. Curve parameters:

   • Field: GF(257), p = 257
   • Coefficients: a = -3, b = 1
   • Equation: y² ≡ x³ - 3x + 1 (mod 257)

2. Input points:

   • P = (8, 177)
   • Q = (234, 53)

3. Point addition formulas (P ≠ Q):

   • λ = (y₂ - y₁) / (x₂ - x₁) mod p
   • x₃ = λ² - x₁ - x₂ mod p
   • y₃ = λ(x₁ - x₃) - y₁ mod p ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
Elliptic Curve Point Addition on GF(257)
Curve: y² = x³ - 3x + 1
"""

def mod_inverse(a, p):
    """Extended Euclidean Algorithm for modular inverse"""
    return pow(a, p - 2, p)

def ec_add(P, Q, a, p):
    """Add two points on elliptic curve y² = x³ + ax + b over GF(p)"""
    if P is None:
        return Q
    if Q is None:
        return P
    
    x1, y1 = P
    x2, y2 = Q
    
    if x1 == x2:
        if y1 == y2:
            # Point doubling: λ = (3x₁² + a) / (2y₁)
            lam = (3 * x1 * x1 + a) * mod_inverse(2 * y1, p) % p
        else:
            # P + (-P) = O (point at infinity)
            return None
    else:
        # Point addition: λ = (y₂ - y₁) / (x₂ - x₁)
        lam = (y2 - y1) * mod_inverse(x2 - x1, p) % p
    
    x3 = (lam * lam - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p
    
    return (x3, y3)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Parameters
p = 257
a = -3
b = 1

# Points
P = (8, 177)
Q = (234, 53)

# Calculate P + Q
R = ec_add(P, Q, a, p)
print(f"P + Q = {R}")
# Output: P + Q = (31, 245)

# Flag is concatenation of coordinates
flag = f"{R[0]}{R[1]}"
print(f"Flag: {flag}")
# Output: Flag: REDACTED

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