A deep analysis of X-only computations on Montgomery curves, their projection onto Bitcoin cryptography (BIP-340 / Taproot), and an implementation on Google Colab

Abstract. This paper examines the mathematical foundations of working with the X-only coordinate on Montgomery elliptic curves, including the Montgomery staircase and differential addition. Particular attention is given to the cryptanalysis of X-only implementations: quadratic twist attacks, invalid curve attacks, and fault injection. It shows how these principles underpinned Bitcoin’s transition to X-only public keys in the BIP-340 standard (Schnorr signatures). For each critical concept, ready-made scripts for Google Colab (Python + SageMath) are provided, allowing one to reproduce the attacks and verify the correctness of X-only multiplication.

Keywords: cryptanalysis, Montgomery curves, X-only, Montgomery staircase, torsion attack, invalid point, Bitcoin, Taproot, BIP-340

1. Introduction: Why the X-coordinate is important

Elliptic curve cryptography traditionally operates with pairs of coordinates $(x, y)$ , satisfying the equation of the curve. However, for many operations, in particular for scalar multiplication, it is sufficient to know only $x$ – the coordinate of the point. Montgomery curves have a unique property: the doubling and differential addition formulas do not use y if the difference between the points is known $P_{n - m}$ .

Equation of the Montgomery curve over a field $F_{p}$ :

\[ B y^2 = x^3 + A x^2 + x, \quad A,B \in \mathbb{F}_p, \quad B \neq 0.

The Montgomery ladder performs scalar multiplication $[k] P$ for a constant number of iterations (by the number of bits $k$ ), which makes it resistant to timing attacks. However, failure to check $y$ – coordinates and membership of a point in a group generates a whole class of vulnerabilities.

2. Unified X-only formulas

Let the points be given $P_{n} = (X_{n} : Z_{n})$ And $P_{m} = (X_{m} : Z_{m})$ in projective coordinates, and $P_{n - m} = (X_{n - m} : Z_{n - m})$ known. Then:

Doubling: $X_{2 n} = (X_{n}^{2} - Z_{n}^{2})^{2}, Z_{2 n} = 4 X_{n} Z_{n} ((X_{n} - Z_{n})^{2} + \frac{A + 2}{4} \cdot 4 X_{n} Z_{n}) .$

Differential addition (add): $X_{n + m} = Z_{n - m} ((X_{n} - Z_{n}) (X_{m} + Z_{m}) + (X_{n} + Z_{n}) (X_{m} - Z_{m}))^{2},$ $Z_{n + m} = X_{n - m} ((X_{n} - Z_{n}) (X_{m} + Z_{m}) - (X_{n} + Z_{n}) (X_{m} - Z_{m}))^{2} .$

These formulas form the basis of the X25519 (Diffie-Hellman on Curve25519) implementation and are used in many libraries.

3. Cryptanalysis: attacks on implementations without checking Y

3.1. Twist attack (quadratic twist attack)

If the implementation does not check that the received $X$ If the coordinate actually lies on the original curve, the attacker can submit a point belonging to a quadratic twist . The twist has a different group order, often containing small prime divisors. By submitting points of low order, the attacker, based on the system’s response (for example, the success of decryption), recovers the private key bits using the Chinese remainder theorem.

🔐 Protection in Curve25519. The curve is designed so that both the curve itself and its twist have cofactor 8 and contain a subgroup of prime order. $\approx 2^{252}$

, which makes the twist attack ineffective.

3.2. Invalid curve attack

If the receiving party does not check the curve equation for the incoming point, the attacker can choose a point on another curve with the same parameter $A$ (or with another $A$ , if the parameter is not checked). Then, discrete logarithm on a weak curve becomes trivial. A classic example is the CVE-2015-6924 vulnerability in the MatrixSSL library, which lacked a membership check.

3.3. Fault injection

During the execution of the Montgomery ladder, a temporary glitch in a register can shift a point to a different curve, which, under certain conditions, allows the secret scalar to be calculated. Security is achieved by duplicating the calculations and verifying the result.

4. Experimental scripts for Google Colab

Below are ready-to-use Python and SageMath code snippets that can be run in Google Colab (or locally) to demonstrate key aspects of X-only computation and attacks.

4.1. Implementation of the Montgomery Staircase (X25519)

Standard implementation of X-only multiplication on Curve25519. Demonstrates correct operation with the X-coordinate only.

# ========== montgomery_ladder.py ==========
# Код для Google Colab / Python 3.8+
# Вычисление [k] * u на Curve25519 (X-only)

p = 2**255 - 19
A24 = 121665  # (A-2)/4 для Curve25519, A = 486662

def cswap(swap, x2, x3):
    # условный обмен (без ветвлений)
    dummy = swap * (x2 ^ x3)
    x2 ^= dummy
    x3 ^= dummy
    return x2, x3

def montgomery_ladder(k, u):
    # k - секретный скаляр (int), u - X-координата точки (int)
    x1 = u % p
    x2, z2 = 1, 0
    x3, z3 = x1, 1
    swap = 0

    for t in range(255, -1, -1):
        k_t = (k >> t) & 1
        swap ^= k_t
        x2, x3 = cswap(swap, x2, x3)
        z2, z3 = cswap(swap, z2, z3)
        swap = k_t

        # удвоение (x2, z2)
        A = (x2 + z2) % p
        AA = (A * A) % p
        B = (x2 - z2) % p
        BB = (B * B) % p
        E = (AA - BB) % p
        # сложение (x3, z3) с (x2, z2)
        C = (x3 + z3) % p
        D = (x3 - z3) % p
        DA = (D * A) % p
        CB = (C * B) % p
        x3 = ((DA + CB) ** 2) % p
        z3 = (x1 * ((DA - CB) ** 2)) % p
        x2 = (AA * BB) % p
        z2 = (E * (AA + A24 * E)) % p

    x2, x3 = cswap(swap, x2, x3)
    z2, z3 = cswap(swap, z2, z3)
    # обратное к z2 по модулю p
    return (x2 * pow(z2, p-2, p)) % p

# === Тест ===
u = 9   # базовая точка X25519
k = 0x123456789abcdef
res = montgomery_ladder(k, u)
print(f"[{k}] * {u} = {res}")

▶ Open in Colab (simulated)

4.2. Twist attack – demonstration on a small curve (SageMath)

Shows how an attacker exploits a point on a low-order twist to extract key bits. A small curve with a small cofactor is used for clarity.

# ========== twist_attack_demo.sage ==========
# SageMath (можно запустить в CoCalc или локально)
# Демонстрация атаки на квадратичное скручивание

p = 101
A = 2
B = 3
# Оригинальная кривая: B*y^2 = x^3 + A*x^2 + x
E = EllipticCurve(GF(p), [0, A, 0, B, 0])
print("Порядок оригинальной кривой:", E.order())

# Квадратичное скручивание: B' = B * non_residue
non_res = GF(p)(3)  # 3 - невычет по модулю 101
Et = EllipticCurve(GF(p), [0, A, 0, B*non_res, 0])
print("Порядок скручивания:", Et.order())

# Находим точку малого порядка на скручивании (например, 2)
P_t = Et.lift_x(17)   # произвольная точка на скручивании
print("P_t порядок:", P_t.order())

# Моделируем: сервер умножает секретный скаляр k на поданную X-координату
k = 25   # секретный ключ (малый для демонстрации)
Q = k * P_t
# Атакующий видит Q (X-координату) и, зная порядок точки, восстанавливает k mod order
print("k mod order(P_t) =", k % P_t.order())
# Повторяя для точек разных порядков, по CRT восстанавливаем полный k

4.3. Invalid curve attack (Python using small fields)

Demonstration of how to pick a point on another curve with the same parameter $A$ , but with little order.

# ========== invalid_curve_demo.py ==========
# Python с библиотекой tinyec (установите: pip install tinyec)
# Показывает принцип invalid curve attack на упрощённом примере

from tinyec import registry
import secrets

# Используем стандартную кривую secp192r1 для демонстрации
curve = registry.get_curve('secp192r1')
# Создаём фальшивую кривую с другим параметром B (но тем же A)
# В реальной атаке параметр B подбирается так, чтобы получить малый порядок
fake_curve = registry.get_curve('secp192r1')  # заменим параметры вручную
# В tinyec нельзя просто изменить B, поэтому используем эмуляцию:
# В реальном коде мы бы задали свою кривую через класс.

print("Оригинальная кривая:", curve)
print("Порядок оригинальной группы:", curve.field.n)

# Создаём точку на "фальшивой" кривой (в реальности мы бы нашли её через подбор)
# Здесь просто иллюстрируем концепцию: если проверки нет, атакующий подаёт
# точку, не лежащую на исходной кривой.

Note: For a full-fledged Invalid curve attack, it is necessary to generate a curve with a low order and find a point on it whose $X$ -coordinate coincides with some point on the original curve. More detailed code is provided in open research.

4.4 X-only Schnorr Signatures (BIP-340) – Proof of Concept

The BIP-340 standard uses X-only keys, where Y is always considered even. Below is a sketch of signature verification without recovering Y.

# ========== schnorr_xonly_check.py ==========
# Упрощённая проверка подписи Шнорра с X-only ключом (только логика)
# Для реальной работы требуется библиотека secp256k1 (python-schnorr)

import hashlib
import secrets

# Параметры secp256k1 (упрощённо, без оптимизаций)
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
# ... полный код опущен для краткости, но идея:
# Публичный ключ – это X-координата (32 байта)
# При верификации восстанавливается R = s*G - e*P, и проверяется, что X(R) == r

print("BIP-340 использует X-only ключи, что исключает пластичность.")

5. Bitcoin’s X-Only Transition: BIP-340 and Taproot

Before Taproot was activated, Bitcoin used public keys in either compressed (33 bytes: X + 1 parity byte Y) or uncompressed (65 bytes) format. This created a transaction malleability problem : the same signature could be represented with $y$ And $- y$ , changing the TXID without violating its validity.

With the introduction of BIP-340 (Schnorr signatures), public keys now only have X-coordinates (32 bytes). The Y-coordinate is implicitly considered even. This is:

Eliminates plasticity at the serialization level;
Saves space in transactions;
Simplifies multi-signatures (e.g. MuSig).

📜 Historical background. In 2014–2015, malleability attacks were used by attackers to delay transactions (e.g., the Mt.Gox incident). The transition to X-only keys in Taproot structurally eliminates the possibility of Y-coordinate spoofing.

It is important to emphasize that although Bitcoin uses the Weierstrass curve (secp256k1) rather than Montgomery, the principle of working only with the X-coordinate was borrowed from the Curve25519 implementations and adapted for Schnorr signatures.

Analysis of X-coordinate computations on Montgomery curves and projection onto Bitcoin cryptography. The mathematics of Montgomery curves.

The Montgomery form of an elliptic curve is given by the equation: $B y^{2} = x^{3} + A x^{2} + x$ over a finite field $F_{p}$ Using the Montgomery ladder algorithm, one can calculate the scalar product $[k] P$ in constant time using only $X$ And $Z$ coordinates in projective space, where $x = X / Z$ .

Unified Formulas (X-coordinate only)

For the point $P_{n} = (X_{n}, Z_{n})$ And $P_{m} = (X_{m}, Z_{m})$ , the difference of which is equal to $P_{n - m} = (X_{n - m}, Z_{n - m})$ , the operations of addition and doubling are performed as follows:

Doubling: $X_{2 n} = (X_{n} - Z_{n})^{2} (X_{n} + Z_{n})^{2}$ $Z_{2 n} = (4 X_{n} Z_{n}) ((X_{n} - Z_{n})^{2} + \frac{A + 2}{4} (4 X_{n} Z_{n}))$

Differential addition: $X_{n + m} = Z_{n - m} ((X_{n} - Z_{n}) (X_{m} + Z_{m}) + (X_{n} + Z_{n}) (X_{m} - Z_{m}))^{2}$ $Z_{n + m} = X_{n - m} ((X_{n} - Z_{n}) (X_{m} + Z_{m}) - (X_{n} + Z_{n}) (X_{m} - Z_{m}))^{2}$

Cryptanalysis: Attacks on X-only implementations and defenses

Omitting the Y-coordinate opens up specific attack vectors if the implementation does not take into account the check for a point being in a subgroup or curve.

Twist Attacks: Since the Y-coordinate is not recovered or verified initially, an attacker can transmit an X-coordinate that does not lie on the original curve, but rather belongs to its quadratic twist. The twist curve has a different group order, which can have small prime factors, allowing the private key to be extracted via the Chinese Remainder Theorem (CRT).
Curve25519 (Twist Security): The problem is solved by parameter selection. Curve25519 is designed so that both the curve itself and its twist have the order of $h \cdot q$ , Where $q$ — is a large prime number.
Fault Attacks: Injecting a fault into a register during the execution of the Montgomery ladder resets a point from the safe curve to a random (weak) one, resulting in key bit leakage.

A historical example: vulnerability CVE-2015-6924 in the MatrixSSL library. The ECDH implementation did not verify the identity of incoming curve points. This allowed an Invalid Curve Attack to be performed and private keys of servers to be extracted in minutes.

Integration of the concept into Bitcoin (BIP-340 and secp256k1)

Bitcoin uses the Weierstrass curve secp256k1. Before the Taproot update, Bitcoin used public keys consisting of X and Y coordinates. However, the Y coordinate created a problem with transaction malleability (dot $P$ And $- P$ have the same X-coordinate but different Y-coordinates).

Transition to X-only (BIP-340): In Bitcoin Schnorr signatures (Taproot), public keys now consist only of the X-coordinate (32 bytes). The Y-coordinate is implicitly assumed to be even. This directly aligns with the X-only computing principles in Curve25519, reducing storage overhead and completely eliminating signature malleability at the serialization level.

Historical example: Before the introduction of hard normalization standards (BIP-62) and later Taproot, attackers could change the Y-coordinate in Bitcoin transaction signatures (e.g., the Mt.Gox incident and malleability attack) by changing the TXID without compromising cryptographic validity. Schnorr x-only keys structurally preclude this possibility.

Code Examples (Scalar X-only Multiplication)

Python

# Curve25519 X-only Ladder
def cswap(swap, x2, x3):
    dummy = swap * (x2 ^ x3)
    return x2 ^ dummy, x3 ^ dummy

def montgomery_ladder(k, u, p=2**255-19, a24=121665):
    x1, x2, z2, x3, z3 = u, 1, 0, u, 1
    swap = 0
    for t in reversed(range(255)):
        k_t = (k >> t) & 1
        swap ^= k_t
        x2, x3 = cswap(swap, x2, x3)
        z2, z3 = cswap(swap, z2, z3)
        swap = k_t

        A = (x2 + z2) % p
        AA = (A * A) % p
        B = (x2 - z2) % p
        BB = (B * B) % p
        E = (AA - BB) % p
        C = (x3 + z3) % p
        D = (x3 - z3) % p

        DA = (D * A) % p
        CB = (C * B) % p

        x3 = ((DA + CB)**2) % p
        z3 = (x1 * (DA - CB)**2) % p
        x2 = (AA * BB) % p
        z2 = (E * (AA + a24 * E)) % p

    x2, x3 = cswap(swap, x2, x3)
    z2, z3 = cswap(swap, z2, z3)
    return (x2 * pow(z2, p-2, p)) % p

SageMath

p = 2^255 - 19
A = 486662
F = GF(p)
E = EllipticCurve(F, [0, A, 0, 1, 0])
P = E.lift_x(9)
k = randint(1, p-1)
Q = k * P
print("X-coordinate:", Q[0])

Conclusion

In this article, we examined the mathematical apparatus of X-only computations on Montgomery curves, identified the main attack vectors (twist, invalid curve, fault), and demonstrated how this knowledge was transformed into practical Bitcoin standards. The provided Google Colab scripts allow researchers to independently reproduce:

Correct operation of the Montgomery ladder;
The twist attack principle on small fields;
General logic of X-only signatures.

Bitcoin’s move to X-only is not just an optimization, but a major step toward improving security and reducing overhead, motivated by decades of cryptanalysis.