Constructing Anomalous Elliptic Curves

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

A newsletter about Applied Math and Theoretical Computer Science.

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 : Twists of Elliptic Curves in Sage/Python.

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

Part 9 : Smart Attack on Anomalous Curves.

Part 10: Constructing Anomalous Curves.

1.0 Introduction

Part 9 introduced anomalous curves: insecure elliptic curves (easy-to-solve-ECDLP-curves) where the trace of Frobenius equals one.

(Leprévost et al., 2005) and (Olson, 1976) demonstrate practical techniques to construct these curves.

1.1 Finding Good Characteristic Primes

(Olson, 1976) proves in corollary 3.11 that if p=12s2+6s+1 is a prime, then there must exist an elliptic curve of the form y2=x3+b mod p that is anomalous (Ariana 1729, 2020):

(Leprévost et al., 2005) introduces the Complex Multiplication Search Method and asserts that anomalous elliptic curves also exist modulo prime numbers of the form:

These primes correspond to Heegner numbers that demonstrate large j-invariants (we saw this in the twists paper) and the discriminant D is neither 7 nor congruent to 3 modulo 8:

1.2 Curves That Cannot Be Anomalous

(Olson, 1976) proves in Corollary 2.2 that elliptic curves of the form y2=x3+ax cannot be anomalous:

(Leprévost et al., 2005) further proves that elliptic curves with complex multiplication, where the Heegner number d is small (like 1,2,3,7) cannot be anomalous:

Therefore, we must restrict our search to elliptic curves of the form y2=x3+b, y2=x3+ax+b and their twists.

2.0 Constructing Anomalous Curves in Python

We don’t need Schoof’s algorithm to find anomalous curves because we already know that a random point should take us to infinity when multiplied by the field prime:

There exists a sage library for constructing elliptic curves.

2.1 Curves of the form y2=x3+ax

We saw in Section 1.2 that these curves cannot be anomalous.

2.2 Curves of the form y2=x3+b

These are easy to find and are constructed by the method in (Olson, 1976) where we search for prime numbers of the form p=12s2+6s+1.

Note that p=12s2+6s+1 = 3(2s + 1)2 - 2.

Let n = 2s+1. Observe that n is odd. So we need only search for p=3n2-2.

In Python, we have

from sympy import isprime

def find_primes(limit):
    #loop over odd n
    for n in range(1, limit + 1, 2):
        p = 3 * n * n - 2
        if isprime(p):
            print(f"n = {n}, p = {p}")


find_primes(1000000)

Once we find a prime, then we know from Part 7 there are six possible twists and one of them must be anomalous as proven in (Olsen, 1976).

2.1 Curves of the form y2=x3+ax+b

These curves are rare somewhat. For instance, (Hofman, 2020) spent three weeks searching for a 64-bit curve of this form.

import math

def check_forms(p):
    forms = [
        (11, 3, “11m(m+1) + 3”),
        (19, 5, “19m(m+1) + 5”),
        (43, 11, “43m(m+1) + 11”),
        (67, 17, “67m(m+1) + 17”),
        (163, 41, “163m(m+1) + 41”)
    ]
    results = []
    for a, b, form_name in forms:
        #  solve: a*m(m+1) + b = p, ie a*m² + a*m + (b - p) = 0
        # Discriminant: D = a² - 4*a*(b-p) = a² - 4a(b-p)
        discriminant = a*a - 4*a*(b - p)
        if discriminant >= 0:
            sqrt_disc = math.isqrt(discriminant)
            
            # Check if discriminant is a perfect square
            if sqrt_disc * sqrt_disc == discriminant:
                # Check both possible solutions for m
                m1 = (-a + sqrt_disc) / (2*a)
                m2 = (-a - sqrt_disc) / (2*a)
                
                # Check if either solution is an integer
                for m in [m1, m2]:
                    if m >= 0 and abs(m - round(m)) < 1e-10:
                        m_int = round(m)
                        results.append((form_name, m_int, a*m_int*(m_int+1) + b))
                        break
    
    return results

def main():
    p = 43
    results = check_forms(p)
    print(results)

if __name__ == “__main__”:
    main()

Furthermore, (Hofman, 2020)

References

Leprévost, F., Monnerat, J., Varrette, S., & Vaudenay, S. (2005). Generating Anomalous Elliptic Curves. Information Processing Letters, 93(5), 225–230. DOI. PDF.

Olson, L. O. (1976). Hasse Invariants and Anomalous Primes for Elliptic curves with Complex Multiplication. Journal of Number Theory, 8(4), 397–414. DOI. PDF.

Ariana 1729. (2020). DEFCON 2020 Writeup: Anomalous Elliptic Curves. Online Blog.

Hofman, S,. J,. (2020). The Discrete Logarithm Problem on Anomalous Elliptic Curves. University of Groningen. Thesis.