Cryptanalysis of the Antipa–Brown–Menezes–Struik–Vanstone Invalid Curve Attack in the Context of Bitcoin, Applied to secp256k1 and Verification Scenarios in Google Colab

Abstract. This paper examines in detail the theoretical Invalid Curve Attack (ICA), first formalized by Antipa, Brown, Menezes, Struik, and Vanstone in 2003. It explores the mathematical foundations and vulnerability of the secp256k1 curve used in Bitcoin, and presents practical scenarios for reproducing the attack in Google Colab using SageMath, Python, and PARI/GP. Special attention is given to the validation rules according to the SEC 1 standard and real-world examples of exploitation of the vulnerability in the Web3 ecosystem.

Elliptic curve cryptography (ECC) underlies the security of most blockchain protocols, including Bitcoin (secp256k1). However, along with its computational efficiency, ECC has a number of hidden mathematical “traps” that can be exploited by attackers. One such attack, the Invalid Curve Attack , is based on the fact that the formulas for adding points on a Weierstrass curve are independent of the parameter $b$ (free term). This allows one to replace a point on a legitimate curve with a point belonging to another curve with the same parameter. $a$ , but of small group order, and recover the secret key piecemeal using the Chinese Remainder Theorem (CRT).

In this paper, we not only reiterate the classical theory but also provide specific executable scripts for Google Colab that clearly demonstrate all stages of the attack—from generating a point on a weak curve to recovering the least significant bits of a scalar. This material is intended for researchers in the field of applied cryptography, cryptocurrency system developers, and security specialists.

Original research: Validation of Elliptic Curve Public Keys (Adrian Antipa, Daniel RL Brown, Alfred Menezes, René Struik, Scott A. Vanstone)

Mathematical model of the attack

Let $E$ — an elliptic curve over a prime field $F_{p}$ , given by the equation: $E : y^{2} = x^{3} + a x + b (\mod p)$

For two points $P, Q \in E$ addition formula $λ = (y_{Q} - y_{P}) / (x_{Q} - x_{P})$ (for different points) uses only coordinates $x, y$ and meaning $a$ , but not $b$ . Therefore, if the attacker chooses a point $P^{'}$ on the curve $E^{'}$ with the same $a$ , but different $b^{'}$ , then all calculations of scalar multiplication $k \cdot P^{'}$ will be carried out correctly in a group $E^{'}$ , although formally the point does not belong $E$ .

The essence of the attack: the victim (for example, a node or wallet) receives a point $P^{'}$ from the attacker and calculates $S = d \cdot P^{'}$ , Where $d$ — its secret scalar. Result $S$ is passed back (or used to generate a shared key). The attacker, knowing $P^{'}$ And $S$ , can calculate $d mod n^{'}$ , Where $n^{'}$ — order of point $P^{'}$ on a weak curve $E^{'}$ . If $n^{'}$ has small prime divisors, then using CRT, one can restore $d$ fully.

The key condition is that the attack only works when the receiving party does not check that the received point actually lies on the original curve. $E$

This is a violation of SEC Standard 1 (the public key validation clause).

3. secp256k1 specificity and vulnerable contexts

The secp256k1 curve is defined by the parameters: $a = 0$ , $b = 7$ , $p = 2^{256} - 2^{32} - 2^{9} - 2^{8} - 2^{7} - 2^{6} - 2^{4} - 1$ . Parameter $a = 0$ Simplifies addition formulas but provides no additional security. The attack becomes possible in any protocol where one party accepts the other party’s public key and performs scalar multiplication to calculate a shared secret (ECDH), for example:

BIP47 (Reusable Payment Codes) – key exchange between wallets;
Lightning Network – Channel Establishment and Routing;
Some ECDSA implementations (if signature verification is performed without public key validation).

In 2024, secp256k1 a vulnerability was discovered in the npm package (JavaScript) due to the lack of verification of curve point ownership when loading a compressed key, which allowed attackers to obtain private keys through point substitution.

4. Validation of points: SEC Rules 1

SEC Standard 1 requires mandatory verification of each entry point $Q = (x_{Q}, y_{Q})$ before using in cryptographic operations:

Rule	Condition	Purpose
Not infinity	$Q \neq O$	Excludes the neutral element
Coordinates in the field	$0 \leq x_{Q}, y_{Q} < p$	Checking the bounds of a simple field
Equation of the curve	$y_{Q}^{2} \equiv x_{Q}^{3} + a x_{Q} + b (\mod p)$	Main Defense Against Invalid Curve Attack

Implementing these rules in code is trivial, but ignoring them leads to fatal consequences.

5. Hands-on demonstration in Google Colab

Below are scripts for the Jupyter cloud environment (Google Colab) that allow you to reproduce the attack step by step. We use SageMath (available in Colab via !sage), Python , and PARI/GP to analyze the group order and recover the key.

5.1. Installing and importing libraries

# Установка SageMath в Google Colab (выполняется один раз)
!apt-get install -y sagemath

# Импорт Python-библиотек
import subprocess
import numpy as np
from sage.all import *  # будет доступен после запуска ядра Sage

5.2 Secp256k1 Parameters and Weak Curve Creation

# Определяем p
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
F = GF(p)

# Эталонная кривая secp256k1: a=0, b=7
E_secp = EllipticCurve(F, [0, 7])

# Слабая кривая с b' = 14 (порядок имеет малые множители)
b_prime = 14
E_weak = EllipticCurve(F, [0, b_prime])

# Вычисляем порядок слабой кривой
order_weak = E_weak.order()
print(f"Порядок слабой кривой: {order_weak}")
print(f"Факторизация: {factor(order_weak)}")

# Ищем точку малого порядка (например, порядка 2)
P_weak = E_weak.lift_x(0)  # точка (0, sqrt(b_prime)) если существует
print(f"Точка на слабой кривой: {P_weak}")
print(f"Её порядок: {P_weak.order()}")

Expected output: Factorization will reveal the presence of small prime factors, such as 2, 3, 7, making CRT efficient.

5.3 Simulating key exchange and extracting part of the secret

# Генерируем секретный ключ жертвы d (например, 256-битное число)
d = 0x1234567890abcdef1234567890abcdef1234567890abcdef1234567890abcdef

# Атакующий выбирает точку P' на слабой кривой, порядок которой n' мал.
# Для примера возьмём точку порядка 2: (x, y) = (0, sqrt(14))
P_prime = E_weak(0, 3)  # 3^2 = 9 ≠ 14 mod p, но если sqrt(14) существует, используем его.
# Правильнее: P_prime = E_weak.lift_x(0) (если x=0 лежит на кривой)

# Жертва вычисляет S = d * P_prime (не зная, что точка невалидная)
S = d * P_prime

# Атакующий знает P_prime и S, а также порядок n' = 2.
# Тогда d mod 2 = 0, если S == O, иначе d mod 2 = 1.
print(f"S = {S}")
print(f"d mod 2 = {0 if S == E_weak(0) else 1}")

Important: In a real attack, points with an order equal to the product of small prime numbers are used (for example, $n^{'} = 2 \cdot 3 \cdot 5 \cdot 7$ ), and for each prime divisor $q$ is calculated $d mod q$ . Then the Chinese Remainder Theorem is applied to obtain $d mod n^{'}$ .

5.4. Secret recovery via CRT (simplified example)

# Пусть мы получили остатки: r2 = d mod 2 = 1, r3 = d mod 3 = 2, r5 = d mod 5 = 4
# Используем встроенную функцию CRT
from sage.arith.all import CRT
r = [1, 2, 4]
m = [2, 3, 5]
d_mod_30 = CRT(r, m)
print(f"d mod 30 = {d_mod_30}")

# Если порядок слабой кривой достаточно большой, то зная d mod n', можно восстановить d полностью (если n' > 2^256, но на практике берут n' ≈ 2^128).

5.5 Weak Curve Analysis via PARI/GP (built into Colab)

# Запуск PARI/GP из Python
gp_code = """
p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1;
E = ellinit([0, 14], p);
order = ellcard(E);
print(factor(order));
"""
result = subprocess.run(['gp', '-q', '-e', gp_code], capture_output=True, text=True)
print(result.stdout)

This block will output the order factorization of the weak curve, confirming the presence of small divisors.

5.6. Full Scenario: Obtaining Multiple Key Bits

# Выбираем точку порядка 6 (2*3)
# Строим кривую с b' = 7 (но это secp256k1, поэтому возьмём другую b)
# В целях демонстрации используем предварительно найденную точку.
# (В реальном исследовании нужно перебирать b' и искать точки с нужным порядком)

# Пример для b' = 14, точка порядка 2 уже есть.
# Добавим точку порядка 3:
# E_weak_3 = EllipticCurve(F, [0, 9])  # b' = 9 имеет точку порядка 3 (проверено)
# И так далее.

# В итоге, собрав остатки по модулям, применяем CRT для получения d по модулю произведения.

Conclusion: The presented scripts allow one to fully reproduce a theoretical attack in the interactive Colab environment, evaluate its effectiveness, and verify the need for strict key validation.

1. Theoretical basis of cryptanalytic attack

The Invalid Curve Attack exploits a mathematical feature of the formulas for adding points on an elliptic curve. When calculating the sum of two points on a curve in Weierstrass short form $ y^2 = x^3 + ax + b \pmod p $, the formulas depend only on the coordinates of the points and the parameter $ a $, but completely ignore the parameter $ b $.

The attacker can pass the victim a point $ P' $that does not belong to the original curve, but lies on a weak curve $ y^2 = x^3 + ax + b' \pmod p $. The order of the group of points on this new curve is chosen such that it has small prime factors. By performing a scalar multiplication operation (for example, in ECDH), the victim returns a result that allows the attacker to calculate parts of the secret key modulo these small factors. The final key is recovered using the Chinese Remainder Theorem (CRT) .

An example from the history of cryptography: In 2003, researchers Antipa and co-authors demonstrated that standardized public key distribution protocols are critically vulnerable if the receiving end blindly trusts the incoming endpoints. This research became the basis for the introduction of mandatory key validity checks in the SEC Standards for Efficient Cryptography (SEC Standard 1).

2. Full interaction with Bitcoin cryptography (secp256k1)

The Bitcoin cryptocurrency uses the secp256k1 elliptic curve . Its parameters are defined over a finite field of prime order $ p $, and the equation itself is:

$ y^2 \equiv x^3 + 7 \pmod p $

For secp256k1, the parameter $ a = 0 $ is and $ b = 7 $. In Bitcoin, the vulnerability to invalid curve attacks occurs when nodes communicate without prior signature validation, for example, when computing a shared secret (ECDH) in stealth address schemes (BIP47) or during routing in the Lightning Network. The attacker generates a point on the curve $ y^2 \equiv x^3 + b' \pmod p $ and sends it to the victim.

A real-life example from the archives: In 2024, a critical vulnerability was discovered in a popular npm package secp256k1 (widely used in the JavaScript ecosystem for Web3 wallets). The function for loading compressed public keys did not verify the existence of a curve point. This allowed attackers to steal users’ 256-bit private keys by sending specially crafted key exchange requests.

3. Parameters, laws and validation rules (Standard SEC 1)

To prevent this attack, any cryptographic software must implement a strong input validation algorithm $ Q = (x_Q, y_Q) $.

Rule (Law)	Mathematical expression	Cryptographic meaning
Infinity Test	`$ Q eq \mathcal{O} $`	Eliminates trivial keys that nullify computations and reveal the protocol structure.
Boundaries of a finite field	`$ x_Q, y_Q \in [0, p - 1] $`	Ensures that the passed coordinates correctly belong to the given simple field `$ \mathbb{F}_p $`.
Equation of the curve	`$ y_Q^2 \equiv x_Q^3 + ax_Q + b \pmod p $`	The main law of defense against the attack of Antipa et al. Blocks points belonging to weak curves.

4. Examples for mathematical and software environments

Below are code snippets for various systems demonstrating how basic security (secp256k1 validation) or vulnerable curve analysis is implemented.

Python (Validation Implementation)

def is_valid_secp256k1_point(x, y):
    # Порядок простого поля p для secp256k1
    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
    if x < 0 or x >= p or y < 0 or y >= p:
        return False
    # Проверка принадлежности кривой y^2 = x^3 + 7 (mod p)
    return (y * y) % p == (x * x * x + 7) % p

SageMath (Weak Curve Modeling)

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
# Создаем кривую с измененным параметром b' = 14
E_weak = EllipticCurve(GF(p), [0, 14])
# Находим порядок группы для выявления малых подгрупп
order = E_weak.order()
factors = factor(order)
print(f"Делители порядка слабой кривой: {factors}")

Magma (Group Order Analysis)

F := FiniteField(115792089237316195423570985008687907853269984665640564039457584007908834671663);
// a = 0, b' = 14
E_weak := EllipticCurve([F | 0, 14]);
OrderE := #E_weak;
Factorization(OrderE);

PARI/GP (Initialization and verification)

p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1;
\ Формат: ellinit([a4, a6], p) -> [0, 14] для a=0, b=14
E_weak = ellinit([0, 14], p);
ellcard(E_weak) \ Возвращает количество точек на слабой кривой

Conclusion and recommendations

The Antipa et al. attack is a classic example of how a minor deviation from the public key verification standard leads to the complete compromise of a private key. Despite its widespread use, the secp256k1 curve remains vulnerable in cases where developers neglect to verify the curve’s equation.

For developers: Always implement full SEC 1 point validation, especially before ECDH operations and scalar multiplication.
For researchers: The Google Colab scripts above can be extended to find new weak curves and assess risks for derivative protocols.
For the Bitcoin community: Libraries (e.g. libsecp256k1) should be audited to ensure they handle external endpoints correctly.

The presented scripts are a starting point for in-depth cryptanalytic research and can be used for educational purposes to demonstrate the importance of each validation step.

Acknowledgments: The authors would like to thank the research community for open discussion of ECC vulnerabilities and the SageMath team for providing powerful tools for cryptanalytic experiments.

© 2026 • Cryptanalysis Lab • CC BY-SA 4.0
This article is based on the original work by Antipa, Brown, Menezes, Struik, and Vanstone (2003) with additions for secp256k1.