What Every Programmer Should Know About Twists of Elliptic Curves

Given 13 faults and a good PC, one can break secp256k1 (and Bitcoin) in 1 min.

Paulo S.L.M. Barreto.

Subscribe now

This free article is part of our series on Practical Elliptic Curve Theory For Programmers:

Part 1: Hacking Dormant Bitcoin Wallets in C.

Part 2: Smart Attack on Anomalous Curves.

Part 3: Finding Anomalous Curves.

Part 4: Division Polynomials of Elliptic Curves in Python.

Part 5: Applying Division Polynomials to Point Counting.

Part 6: Fast Point Multiplication on Curves With Efficient Endomorphisms.

Part 7 (we are here): Twists of Elliptic Curves in Sage/Python.

Part 8: Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval.

Barreto is the B in the BLS family of elliptic curves

1.0 Introduction

Elliptic curve theory is somewhat esoteric and the twists of an elliptic curve are pretty obscure. This guide demonstrates the workings of elliptic curve twists to a programming audience.

In typical LeetArxiv style, we show you actual code in lieu of dense math equations.

We teach programmers how to turn advanced math papers into code. Subscribe

Our primary source is Twists of Elliptic Curves (Ono, 1997)1.

Abstract for Twists of Elliptic Curves (Ono, 1997)

1.1 Definition of ‘Twist of Elliptic Curves’

The term ‘twist’ of an elliptic curve is somewhat vague. When people say twist without a modifier, they tend to mean the quadratic twist of an elliptic curve (Cook, 2019)2. Cubic, sextic, and other twists exist however.

Informally*, the twist of an elliptic curve is another algebraic curve that shares some x or y coordinates and a group law with the original elliptic curve.

*The pedantic will crucify me.

For instance, the bitcoin secp256k1 curve has these sextic twists (Lundkvist, 2020)3 corresponding somewhat with the GLV endomorphism from Part 6:

y^2 = x^3 + 7 //secp curve

Sextic Twists of secp
E1: y^2 = x^3 + 1
E2: y^2 = x^3 + 2
E3: y^2 = x^3 + 3
E4: y^2 = x^3 + 4
E6: y^2 = x^3 + 6

The modifier before twist indicates how many equivalence…