The various elliptic curves used in ellitpic curve cryptography (ECC) have different properties, and we’ve looked at several of them before. For example, Curve25519 is implemented very efficiently, and the parameters were transparently chosen. Curve1174 is interesting because it’s an Edwards curve and has a special addition formula.
This post looks at curve P-384. What’s special about this curve? It’s the elliptic curve that the NSA recommends everyone use until post-quantum methods have been standardized. It provides 192 bits of security, whereas more commonly used curves provide 128 bits.
Does the NSA recommend this method because they know how to get around it? Possibly, but they also need to recommend methods that they believe foreign governments cannot break.
The equation of the P-384 curve is
y² = x³ + ax + b
working over the field of integers modulo a prime p. We will go into each of the specific parameters a, b, and p, and discuss how they were chosen.
Modulus p
Consisting with the naming conventions for elliptic curves used in cryptography, the name “P-384” tells you that the curve is over a prime field where the prime is a 384-bit integer. Specifically, the order of the field is
p = 2384 – 2128 – 296 + 232 – 1
For a given number of bits, in this case 384, you want to pick a prime that’s relatively near the maximum size for that number of bits. In our case, our prime p is a prime near 2384 with a convenient bit pattern. (The special pattern allows implementation tricks that increase efficiency.)
Hasse’s theorem says that the number of points on a curve modulo a large prime is on the order of magnitude equal to the prime, so P-384 contains approximately 2384 points. In fact, the number of points n on the curve is
39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
or approximately 2384 – 2190. The number n is a prime, and so it is the order of P-384 as a group.
Linear coefficient a
According to a footnote in the standard defining P-384, FIPS PUB 186-4,
The selection a ≡ -3 for the coefficient of x was made for reasons of efficiency; see IEEE Std 1363-2000.
All the NIST elliptic curves over prime fields use a = -3 because this makes it possible to use special algorithms for elliptic curve arithmetic.
Constant coefficient b
The curve P-384 has Weierstrass form
y² = x³ – 3x + b
where b is
27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575.
The parameter b is between 2383 and 2384 but doesn’t have any particular binary pattern:
101100110011000100101111101001111110001000111110111001111110010010011000100011100000010101101011111000111111100000101101000110010001100000011101100111000110111011111110100000010100000100010010000000110001010000001000100011110101000000010011100001110101101011000110010101100011100110001101100010100010111011010001100111010010101010000101110010001110110111010011111011000010101011101111
The specification says that b was chosen at random. How can you convince someone that you chose a parameter at random?
The standard gives a 160-bit seed s, and a hash-based algorithm that s was run through to create a 384-bit parameter c. Then b is the solution to
b² c = -27 mod p.
The algorithm going from the s to c is given in Appendix D.6 and is a sort of key-stretching algorithm. The standard cites ANS X9.62 and IEEE Standard 1363-2000 as the source of the algorithm.
If b was designed to have a back door, presumably a tremendous amount of computation had to go into reverse engineering the seed s.
Koblitz and Menezes wrote a paper in which they suggest a way that the NSA might have picked seeds that lead to weak elliptic curves, but then argue against it.
It is far-fetched to speculate that the NSA would have deliberately selected weak elliptic curves in 1997 for U.S. government usage … confident that no one else would be able to discover the weakness in these curves in the ensuing decades. Such a risky move by the NSA would have been inconsistent with the Agency’s mission.