Skip to main content

Appendix A. Deterministic Generation

Appendix A. Deterministic Generation​

This section specifies the procedure that was used to generate the above curves; specifically, it defines how to generate the parameter A of the Montgomery curve y^2 = x^3 + A*x^2 + x. This procedure is intended to be as objective as can reasonably be achieved so that it's clear that no untoward considerations influenced the choice of curve. The input to this process is p, the prime that defines the underlying field. The size of p determines the amount of work needed to compute a discrete logarithm in the elliptic curve group, and choosing a precise p depends on many implementation concerns. The performance of the curve will be dominated by operations in GF(p), so carefully choosing a value that allows for easy reductions on the intended architecture is critical. This document does not attempt to articulate all these considerations.

The value (A-2)/4 is used in several of the elliptic curve point arithmetic formulas. For simplicity and performance reasons, it is beneficial to make this constant small, i.e., to choose A so that (A-2) is a small integer that is divisible by four.

For each curve at a specific security level:

  1. The trace of Frobenius MUST NOT be in {0, 1} in order to rule out the attacks described in [smart], [satoh], and [semaev], as in [brainpool] and [safecurves].

  2. MOV Degree [reducing]: the embedding degree MUST be greater than (order - 1) / 100, as in [brainpool] and [safecurves].

  3. CM Discriminant: discriminant D MUST be greater than 2^100, as in [safecurves].

A.1. p = 1 mod 4​

For primes congruent to 1 mod 4, the minimal cofactors of the curve and its twist are either {4, 8} or {8, 4}. We choose a curve with the latter cofactors so that any algorithms that take the cofactor into account don't have to worry about checking for points on the twist, because the twist cofactor will be the smaller of the two.

To generate the Montgomery curve, we find the minimal, positive A value such that A > 2 and (A-2) is divisible by four and where the cofactors are as desired. The find1Mod4 function in the following Sage script returns this value given p:

def findCurve(prime, curveCofactor, twistCofactor):
    F = GF(prime)

    for A in xrange(3, int(1e9)):
        if (A-2) % 4 != 0:
          continue

        try:
          E = EllipticCurve(F, [0, A, 0, 1, 0])
        except:
          continue

        groupOrder = E.order()
        twistOrder = 2*(prime+1)-groupOrder

        if (groupOrder % curveCofactor == 0 and
            is_prime(groupOrder // curveCofactor) and
            twistOrder % twistCofactor == 0 and
            is_prime(twistOrder // twistCofactor)):
            return A

def find1Mod4(prime):
    assert((prime % 4) == 1)
    return findCurve(prime, 8, 4)

Generating a curve where p = 1 mod 4

A.2. p = 3 mod 4​

For a prime congruent to 3 mod 4, both the curve and twist cofactors can be 4, and this is minimal. Thus, we choose the curve with these cofactors and minimal, positive A such that A > 2 and (A-2) is divisible by four. The find3Mod4 function in the following Sage script returns this value given p:

def find3Mod4(prime):
    assert((prime % 4) == 3)
    return findCurve(prime, 4, 4)

Generating a curve where p = 3 mod 4

A.3. Base Points​

The base point for a curve is the point with minimal, positive u value that is in the correct subgroup. The findBasepoint function in the following Sage script returns this value given p and A:

def findBasepoint(prime, A):
    F = GF(prime)
    E = EllipticCurve(F, [0, A, 0, 1, 0])

    for uInt in range(1, 1e3):
      u = F(uInt)
      v2 = u^3 + A*u^2 + u
      if not v2.is_square():
        continue
      v = v2.sqrt()

      point = E(u, v)
      pointOrder = point.order()
      if pointOrder > 8 and pointOrder.is_prime():
        return point

Generating the base point

Last updated on