Criteria for choice of prime field in secp256k1?

Question

In secp256k1, the prime order field $\mathbb F_p$ uses $$p=2^{256}-2^{32}-977$$ This is the largest prime $p$ less than $2^{256}-2^{32}$ allowing to construct a Koblitz curve $y^2\equiv x^3+b\bmod p$ of prime order, and $b=7$ is the smallest positive $b$ for this. The term $2^{256}$ is clearly to define the bit size of the coordinates, and the order of magnitude of the group order.

Similar criteria apply for the choice of the low-order bits of $p$, and for $b$, in secp224k1, secp192k1 (for the deprecated secp160k1, perhaps it was added a negative trace criteria). This roughly matches the account in sec2v1 (removed in v2):

The recommended parameters associated with a Koblitz curve were chosen by repeatedly selecting parameters admitting an efficiently computable endomorphism until a prime order curve was found.

but leaves two questions open:

What justifies the $-2^{32}$ term in $p$ ?

Was there further criteria in the choice of $p$, with what justification ?

---

Note 1: In Ed25519, $p=2^{255}-19$ is the largest 255-bit prime, without offset like $-2^{32}$.

Note 2: For discussion about the choice of secp256k1's generator, see this.

Note 3: This SageMath recomputes secpXXXk1 parameters $p$, $b$ and $n$. For secp160k1 that's the last line; for the others, the first one starting with the bit size.

for j in range(256, 128, -32):
    p = p0 = 2^j - 2^32
    s = True
    while s:
        p = previous_prime(p)
        F = GF(p)
        for b in range(1, 200):
            n = EllipticCurve([F(0), F(b)]).cardinality()
            if n.is_prime():
                print(j, p0-p, b, hex(p), hex(n))
                s = n<p # stop when p yields prime order n and negative trace
                break

256 977 7 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
256 7913 10 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffe117 0xffffffffffffffffffffffffffffffffc0ad397ea94d65ed5001a2f3f2812f4d
256 17681 12 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffbaef 0x100000000000000000000000000000000f2cfcb48012d9e76586a1c1564109bed
224 6803 2 0xfffffffffffffffffffffffffffffffffffffffffffffffeffffe56d 0x10000000000000000000000000001dce8d2ec6184caf0a971769fb1f7
192 4553 3 0xfffffffffffffffffffffffffffffffffffffffeffffee37 0xfffffffffffffffffffffffe26f2fc170f69466a74defd8d
192 13127 5 0xfffffffffffffffffffffffffffffffffffffffeffffccb9 0x1000000000000000000000001e58d67ad78297d7bbd3171ab
160 3929 12 0xfffffffffffffffffffffffffffffffefffff0a7 0xffffffffffffffffffff66fcc05801f00e15f6a5
160 16919 11 0xfffffffffffffffffffffffffffffffeffffbde9 0xfffffffffffffffffffe280724f449253bc2e9ab
160 18293 2 0xfffffffffffffffffffffffffffffffeffffb88b 0xfffffffffffffffffffe206e5eb5194f32e3ca55
160 20309 17 0xfffffffffffffffffffffffffffffffeffffb0ab 0xfffffffffffffffffffe01cf87c16ee51306af13
160 21389 7 0xfffffffffffffffffffffffffffffffeffffac73 0x100000000000000000001b8fa16dfab9aca16b6b3

Answer 1

Officially there does not seem to be any documented rationale for the prime choice of the Koblitz curves as evidenced by this response from the SECG chair in 2013. But we can make an educated guess.

We can start by looking at the other major set of curves in use—the NIST curves. The primes used in those (excluding P-521, which is a pure Mersenne prime) are so-called Solinas primes. Those are primes of the form $f(2^m)$, where $f$ is a polynomial with small (usually confined to $\{-1,0,1\}$) integer coefficients. P-256, for example, corresponds to $(x^8 - x^7 + x^6 + x^3 - 1)(2^{32}) = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1$. NSA's Jeremy Solinas came up with this prime shape and how to efficiently perform modular reduction on it.

Why bother coming up with this new prime shape instead of using the simpler to implement (and faster) $2^n-c$, for small $c$, as used in Curve25519 and already known at the time? Because this prime shape was (believed to be) patented. Richard Crandall filed 3 patents starting in 1991 relating to the implementation of elliptic curves, in which one of the claims was the choice of field primes $2^n-c$, which are often known today as Crandall primes for this reason. (Some have argued that there was prior art for this type of prime in an earlier Bender and Castagnoli paper.)

The SECG Koblitz curves were generated by a different party than the NIST curves, namely Certicom. But since the Crandall patents were not owned by Certicom but by NeXT (later acquired by Apple), they likely had a strong incentive to avoid it as well. In this case they seem to have done it by taking the patent claims quite literally, specifically claim 2 of 5159632:

2. The key generator of claim 1 wherein p is given by $2^q-C$, where $C$ is a binary number having a length no greater than 32 bits.

The primes selected by Certicom for the Koblitz curves are precisely the ones of the form $p=2^n-(2^{32}+c)$, where $c$ is the smallest positive integer such that $p$ is prime. This avoids the claim by going slightly above 32 bits, at the cost of modular reduction being more expensive on chips with 32-bit or smaller words, by needing to multiply by a $\ge 2$-word value instead of a $1$-word value. On 64-bit chips it makes little to no difference.

As an extra curiosity, there appears to be lesser known patent from the 90s, by Miyaji and Tatebayashi, that would have covered these primes: 5442707. It consists of primes $2^n\pm \alpha$, where $\alpha \le 2^{2n/3+15}$.