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³ - 7x + 10 over GF(97), given points P(3,4) and Q(87,27). Solution: Apply standard ECC point addition formulas to compute P + Q = (13, 51), flag is concatenated coordinates REDACTED.

Plus — CryptoKids20

Description

A task on basic elliptic curve point addition. Given the curve y² = x³ - 7x + 10 over the finite field GF(97), and two points P(3,4) and Q(87,27). The goal is to find the sum P + Q.

Analysis

1. Curve parameters:

   • Field: GF(97), p = 97
   • Coefficients: a = -7, b = 10
   • Equation: y² ≡ x³ - 7x + 10 (mod 97)

2. Input points:

   • P = (3, 4)
   • Q = (87, 27)

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(97)
Curve: y² = x³ - 7x + 10
"""

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 = 97
a = -7
b = 10

# Points
P = (3, 4)
Q = (87, 27)

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

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

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