Multik

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Easy | OS: N/A | **Author: XESXOR Techniques: double_and_add, elliptic_curve_scalar_multiplication

Summary

Walkthrough of the CUSTOM Crypto Multik. Task: Scalar multiplication on elliptic curve y² = x³ - 3x + 1 over GF(257), given point P(255,241) and scalar k=167. Solution: Implemented Double-and-Add algorithm to compute k*P efficiently, result

Description

A task on scalar multiplication of a point on an elliptic curve. Given curve y² = x³ - 3x + 1 over finite field GF(257), point P(255,241) and scalar k=167. The goal is to find k*P.

Analysis

1. Curve parameters:

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

2. Input data:

   • P = (255, 241)
   • k = 167

3. Double-and-Add algorithm:

   • Efficient method to compute k*P in O(log k) operations
   • Break k into bits and sequentially double/add ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
Elliptic Curve Scalar Multiplication on GF(257)
Curve: y² = x³ - 3x + 1
Using Double-and-Add algorithm
"""

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
p = 257
a = -3
b = 1

# Point and scalar
P = (255, 241)
k = 167

# Calculate k*P
R = ec_multiply(k, P, a, p)
print(f"{k}*P = {R}")
# Output: 167*P = (107, 115)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

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

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

Key Takeaways / Lessons

• Mastering double_and_add, elliptic_curve_scalar_multiplication was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-03-09 • CUSTOM • Multik • Difficulty: Easy