+*

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

Summary

Task: Compute k*P + Q on an elliptic curve over a large prime field GF(57245372123587). Solution: Implemented Double-and-Add algorithm for scalar multiplication, then point addition to get the result coordinates.

+* — CryptoKids20

Description

A combined task on scalar multiplication and point addition on an elliptic curve over a large field. Given a curve over GF(57245372123587), points P and Q, and scalar k. The goal is to find k*P + Q.

Analysis

1. Curve parameters:

   • Field: GF(57245372123587), p = 57245372123587 (large prime)
   • Coefficients: a, b (standard for the curve)
   • Equation: y² ≡ x³ + ax + b (mod p)

2. Input data:

   • P = (41809612914106, 53806132151013)
   • Q = (25468105522658, 18586975989899)
   • k = 40559753248081 ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

3. Operation:

   • First compute k*P (scalar multiplication)
   • Then add Q (point addition)
   • R = k*P + Q

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
Elliptic Curve Scalar Multiplication + Point Addition
Large field: GF(57245372123587)
Computes k*P + Q
"""

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)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def ec_multiply(k, P, a, p):
    """
    Scalar multiplication using Double-and-Add algorithm.
    Computes k*P efficiently in O(log k) operations.
    """
    result = None  # Point at infinity
    addend = P
    
    while k:
        if k & 1:
            result = ec_add(result, addend, a, p)
        addend = ec_add(addend, addend, a, p)  # Double
        k >>= 1
    
    return result

# Parameters (large field)
p = 57245372123587
a = -3  # Standard curve parameter
b = 1

# Points and scalar
P = (41809612914106, 53806132151013)
Q = (25468105522658, 18586975989899)
k = 40559753248081
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Calculate k*P
kP = ec_multiply(k, P, a, p)
print(f"k*P = {kP}")

# Calculate k*P + Q
R = ec_add(kP, Q, a, p)
print(f"k*P + Q = {R}")
# Output: k*P + Q = (31474310437587, 29113388180099)

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

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