Whenever a controversy about the National Security Agency (NSA) arises among the cryptographic community, it resurfaces a question that has been open for 25 years: How were the NIST ECDSA curve parameters generated?
tl;dr: The NIST ECDSA P-256 curve seeds are on a hard drive next to the Ark of the Covenant.
Update August 2024: Daniel Bernstein and Tanja Lange released emails in Appendix C of "Safe curves for elliptic-curve cryptography" from Jerry Solinas in 2015 which corroborate the post below. Here are excerpts of his responses:
D.J. Bernstein wrote on September 6th, 2014: "Out of curiosity, where _did_ you get the seeds for NIST P-256 etc.?"
Jerome A. Solinas responded over two emails:
"Interesting question. We built all the seeds via hashing (SHA-1, I think)
from the ASCII representation of a humorous message. Unfortunately, we can
remember neither the (exact) message nor the details of how we hashed. Too
bad, since we could prove our innocence by disclosing the details, if only
we could remember them."
"I believe there was a counter rather than multiple hashing, but I don't know details. The message was along the lines of "Give Bob and Jerry a raise" or "Bob and Jerry rule" or something like that. It was Bob Reiter who actually wrote the code, and he doesn't remember the details either. Nor were we able to find archives from so long ago. If they exist, they are no doubt sitting on a hard drive near the Ark of the Covenant."
ECDSA is the most widely used elliptic curve cryptography standard in practice. It originated in the 1999 ANSI X9.62 ECDSA specifications and was adopted by NIST in 2000 as part of the FIPS 186-2 Digital Signature Standard. Both specifications list a set of standard elliptic curves of varying sizes and security levels. For curves over prime fields, the specifications published a "seed" parameter whose hash value is used to define the other parameters of the curve. The provenance of these X9.62 seeds was questioned almost immediately on Usenet after publication in 1999.
These seed parameters were provided by the NSA and appear in the specifications with no explanation or
justification. An example is the NIST P-256 curve seed:
SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90. Why
this value and not another? Revelations of NSA interference in cryptographic
standards like Dual_EC_DRBG led to speculation of whether
the NIST curve seeds could have been intentionally chosen with a weakness or backdoor known only to the NSA.
Neal Koblitz and Alfred Menezes wrote an excellent summary on this controversy, "A Riddle Wrapped in an Enigma", which discusses the history and concerns around the seed values. Prof. Menezes was also the primary author of the ANSI X9.62 ECDSA standard. I contacted Prof. Menezes about where the seeds originated and he definitively answered at least who provided them: Jerry Solinas from the NSA.
"Jerry Solinas did provide the seeds to me sometime in Fall 1997. At the time, I was the primary author of the ANSI X9.62 ECDSA standard, and Jerry was attending the standards meetings as an NSA representative. I don't know if Jerry selected the seeds himself, but in any case he was the person who contributed the seeds to the ANSI standards committee. (Jerry is the "NSA representative" mentioned on page 8 of my article with Neal Koblitz.)"
Jerry Solinas was a long time employee of the NSA who authored multiple cryptographic standards and RFCs. Based on Menezes' account, Solinas provided the curve seeds as part of the X9.62 standards meeting. Dr. Solinas providing the seeds had been mentioned in several secondary sources and it's the first time I've heard someone with direct knowledge corroborate it. Unfortunately, Dr. Solinas died in early 2023 without publicly saying how the curve seeds were generated.
We don't know and probably won't know unless we find some documentation or a contemporary of Jerry Solinas who directly knows. In 2018, I tried to submit FOIA requests to both NIST and the NSA for any documents related to the choice of elliptic curves over prime fields. NIST claimed they had no documentation and the NSA ceased responding. These requests could likely be improved and reworded to have a better chance of finding something:
Jerry Solinas' own RFC 4753 says that the NIST curve's groups were "chosen verifiably at random using SHA-1 as specified in IEEE-1363 from the seed". That method is outlined in IEEE 1363 Section A.12.4 and is paraphrased as:
seed of bit length L.h = H(seed).h and test if it has prime order.Note that the IEEE 1363 specification, which Dr. Solinas directly said he used, does not specify that the seed S need to be random. Arbitrary means arbitrary.
Update August 2024: This story has been corroborated by emails from Jerry Solinas linked above.
I asked a few contemporaries of Jerry Solinas who were involved in cryptographic standards in the late 1990s. One person who has worked on several cryptographic standards and is unaffiliated with the NSA told me a relevant anecdote. They wished to remain anonymous:
"It was Jerry Solinas. I spoke to him about this very topic at least ten years ago [circa 2013]. [Jerry] told me that he used a seed that was something like:
SEED = SHA1("Jerry deserves a raise.")
After he did the work, his machine was replaced or upgraded, and the actual phrase that he used was lost.
When the controversy first came up, Jerry tried every phrase that he could think of that was similar to this, but none matched."
This corroborates hearsay from Dan Bernstein and Tanja Lange in these comments submitted to NIST:
"I have heard NSA employees claiming that the "random" inputs were actually generated as hashes of English text chosen (and later forgotten) by Jerry Solinas."
A third person who was affiliated with the NSA after Dr. Solinas' time repeated the anecdote, but heard it as a rumor repeated by someone else and did not have any direct knowledge.
Since posting this, a fourth person came forward saying that in 2013, Dr. Solinas recalled to them that the seed phrase had two names in it, like "Give Alice and Bob a raise.". Another source said that Dr. Solinas mentioned the phrase may contain a counter.
Does this contradict what Solinas said in his RFCs? I don't think so. If an "arbitrary" bit string is really arbitrary, a plain English phrase would suffice. That would technically be following IEEE 1363. You could hash passphrases until one generates a seed for a curve of sufficient order.
Summarizing all the rumors: The pre-seed phrases are English phrases which mention Jerry Solinas, possibly someone else,
and possibly a counter. An example guess might be SEED = SHA1("Jerry and Bob need raises123").
In the appendix below, I pasted all the seeds from the
September 20, 1998
version of the X9.62 specification. You can see that there are many that share repeated or bit-shifted byte values
for Field2m curves. Specifically 4D696 E6768756 15175 is repeated in 8 seeds.
This has been noticed multiple times before.
These bytes are the ASCII encoding of the string MinghuaQu. Minghua Qu is a cryptographer who
worked at Certicom at the time and is a co-author of Alfred Menezes on the
MQV key agreement protocol.
This is good evidence that the Field2m seeds are not based on hashes of any plaintext strings.
It's unsatisfying to have a few second-hand and off-the-the record anecdotes about how the seeds were generated. At the very least, it would be good to corroborate that the seeds are hashes of English phrases that were lost, either from documentation or someone with first hand knowledge at the NSA. One person to ask is Laurie E. Law, who was a co-author of Jerry Solinas on papers and RFCs from at least 1996 to 2011. I did not find any contact information for her and she is likely long retired.
A long shot chance is to try to bruteforce guess short English phrases and see if any collide with a seed from the specifications. If English phrases were used, there would have been many of them for all the examples in the X9.62 specification. IEEE 1363's method of generating curves was a trial & error approach. If might expect each pre-seed value to include a descriptor or a counter. However, the anecdote I heard claimed that Jerry Solinas tried remembering his own phrases after the fact and failed, so this is probably not worth the effort without more information.
Some open questions & comments:
These are some selected seeds from NIST and X9.62. This has more comprehensive details and was filtered from a larger set of curve data at the Standard curve database.
3045AE6F C8422F64 ED579528 D38120EA E12196D5
BD713447 99D5C7FC DC45B59F A3B9AB8F 6A948BC5
C49D3608 86E70493 6A6678E1 139D26B7 819F7E90
A335926A A319A27A 1D00896A 6773A482 7ACDAC73
D09E8800 291CB853 96CC6717 393284AA A0DA64BA
4E13CA54 2744D696 E6768756 1517552F 279A8C84
D34B9A4D 696E6768 75615175 CA71B920 BFEFB05D
3045AE6F C8422F64 ED579528 D38120EA E12196D5
E43BB460 F0B80CC0 C0B07579 8E948060 F8321B7D
Note: Notice the repeated and bitshifted values in these seeds. They were used to define curves over Field2163.
D2C0FB15 760860DE F1EEF4D6 96E67687 56151754
53814C05 0D44D696 E6768756 1517580C A4E29FFD
50CBF1D9 5CA94D69 6E676875 615175F1 6A36A3B8
Note: Notice the repeated values in these seeds. They were used to define curves over Field2191.
4E13CA54 2744D696 E6768756 1517552F 279A8C84
0871EF2F EF24D696 E6768756 151758BE E0D95C15
E053512D C684D696 E6768756 15175067 AE786D1F
A399387E AE54D696 E6768756 151750E5 8B416D57
2D88F7BC 545794D6 96E67687 56151759 73391555
Note: Notice the repeated values in these seeds. They were used to define curves over Field2239 and share bytes with those for Field2359.
D34B9A4D 696E6768 75615175 CA71B920 BFEFB05D
2AA6982F DFA4D696 E6768756 15175D26 6727277D
9E076F4D 696E6768 75615175 E11E9FDD 77F92041
F851638C FA4D696E 67687561 51755651 3841BFAC
2C04F44D 696E6768 75615175 C586B41F 6CA150C9
Note: Notice the values in these seeds share bytes with those for Field2239.
2B354920 B724D696 E6768756 1517585B A1332DC6
3045AE6F C8422F64 ED579528 D38120EA E12196D5
31A92EE2 029FD10D 901B113E 990710F0 D21AC6B6
C4696844 35DEB378 C4B65CA9 591E2A57 63059A2E
E43BB460 F0B80CC0 C0B07579 8E948060 F8321B7D
E8B40116 04095303 CA3B8099 982BE09F CB9AE616
7D737416 8FFE3471 B60A8576 86A19475 D3BFA2FF
C49D3608 86E70493 6A6678E1 139D26B7 819F7E90
[
{
"name": "ANSI x9.62",
"desc": "ANSI x9.62 example curves.",
"curves": [
{
"name": "prime192v1",
"desc": "",
"category": "x962",
"oid": "1.2.840.10045.3.1.1",
"aliases": [
"secg/secp192r1",
"nist/P-192"
],
"seed": "3045AE6FC8422F64ED579528D38120EAE12196D5"
},
{
"name": "prime192v2",
"desc": "",
"category": "x962",
"oid": "1.2.840.10045.3.1.2",
"seed": "31A92EE2029FD10D901B113E990710F0D21AC6B6"
},
{
"name": "prime192v3",
"desc": "",
"category": "x962",
"oid": "1.2.840.10045.3.1.3",
"seed": "C469684435DEB378C4B65CA9591E2A5763059A2E"
},
{
"name": "prime239v1",
"desc": "",
"category": "x962",
"oid": "1.2.840.10045.3.1.4",
"seed": "E43BB460F0B80CC0C0B075798E948060F8321B7D"
},
{
"name": "prime239v2",
"desc": "",
"category": "x962",
"oid": "1.2.840.10045.3.1.5",
"seed": "0E8B4011604095303CA3B8099982BE09FCB9AE616"
},
{
"name": "prime239v3",
"desc": "",
"category": "x962",
"oid": "1.2.840.10045.3.1.6",
"seed": "7D7374168FFE3471B60A857686A19475D3BFA2FF"
},
{
"name": "prime256v1",
"desc": "",
"category": "x962",
"oid": "1.2.840.10045.3.1.7",
"aliases": [
"secg/secp256r1",
"nist/P-256"
],
"seed": "C49D360886E704936A6678E1139D26B7819F7E90"
},
{
"name": "c2pnb163v1",
"desc": "",
"category": "x962",
"oid": "1.2.840.10045.3.0.1",
"aliases": [
"wtls/wap-wsg-idm-ecid-wtls5"
],
"seed": "D2C0FB15760860DEF1EEF4D696E6768756151754"
},
{
"name": "c2pnb163v2",
"desc": "",
"category": "x962",
"oid": "1.2.840.10045.3.0.2",
"seed": "53814C050D44D696E67687561517580CA4E29FFD"
},
{
"name": "c2pnb163v3",
"desc": "",
"category": "x962",
"oid": "1.2.840.10045.3.0.3",
"seed": "50CBF1D95CA94D696E676875615175F16A36A3B8"
},
{
"name": "c2tnb191v3",
"desc": "",
"category": "x962",
"oid": "1.2.840.10045.3.0.7",
"seed": "E053512DC684D696E676875615175067AE786D1F"
},
{
"name": "c2tnb191v2",
"desc": "",
"category": "x962",
"oid": "1.2.840.10045.3.0.6",
"seed": "0871EF2FEF24D696E6768756151758BEE0D95C15"
},
{
"name": "c2tnb191v1",
"desc": "",
"category": "x962",
"oid": "1.2.840.10045.3.0.5",
"seed": "4E13CA542744D696E67687561517552F279A8C84"
},
{
"name": "c2tnb239v3",
"desc": "",
"category": "x962",
"oid": "1.2.840.10045.3.0.13",
"seed": "9E076F4D696E676875615175E11E9FDD"
},
{
"name": "c2tnb239v2",
"desc": "",
"category": "x962",
"oid": "1.2.840.10045.3.0.12",
"seed": "2AA6982FDFA4D696E676875615175D266727277D"
},
{
"name": "c2tnb239v1",
"desc": "",
"category": "x962",
"oid": "1.2.840.10045.3.0.11",
"seed": "D34B9A4D696E676875615175CA71B920BFEFB05D"
},
{
"name": "c2tnb359v1",
"desc": "",
"category": "x962",
"oid": "1.2.840.10045.3.0.18",
"seed": "2B354920B724D696E67687561517585BA1332DC6"
},
{
"name": "c2onb191v4",
"desc": "A binary-field curve in optimal normal basis",
"category": "x962",
"oid": "1.2.840.10045.3.0.8",
"seed": "A399387EAE54D696E6768756151750E58B416D57"
},
{
"name": "c2onb191v5",
"desc": "A binary-field curve in optimal normal basis",
"category": "x962",
"oid": "1.2.840.10045.3.0.9",
"seed": "2D88F7BC545794D696E676875615175973391555"
},
{
"name": "c2onb239v4",
"desc": "A binary-field curve in optimal normal basis",
"category": "x962",
"oid": "1.2.840.10045.3.0.14",
"seed": "F851638CFA4D696E67687561517556513841BFAC"
},
{
"name": "c2onb239v5",
"desc": "A binary-field curve in optimal normal basis",
"category": "x962",
"oid": "1.2.840.10045.3.0.15",
"seed": "2C04F44D696E676875615175C586B41F6CA150C9"
}
]
},
{
"name": "NIST",
"desc": "RECOMMENDED ELLIPTIC CURVES FOR FEDERAL GOVERNMENT USE July 1999",
"curves": [
{
"name": "P-192",
"desc": "",
"category": "nist",
"oid": "1.2.840.10045.3.1.1",
"aliases": [
"secg/secp192r1",
"x962/prime192v1"
],
"seed": "3045AE6FC8422F64ED579528D38120EAE12196D5"
},
{
"name": "P-224",
"desc": "",
"category": "nist",
"oid": "1.3.132.0.33",
"aliases": [
"secg/secp224r1",
"wtls/wap-wsg-idm-ecid-wtls12",
"x963/ansip224r1"
],
"seed": "BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5"
},
{
"name": "P-256",
"desc": "",
"category": "nist",
"oid": "1.2.840.10045.3.1.7",
"aliases": [
"secg/secp256r1",
"x962/prime256v1"
],
"seed": "C49D360886E704936A6678E1139D26B7819F7E90"
},
{
"name": "P-384",
"desc": "",
"category": "nist",
"oid": "1.3.132.0.34",
"aliases": [
"secg/secp384r1",
"x963/ansip384r1"
],
"seed": "A335926AA319A27A1D00896A6773A4827ACDAC73"
},
{
"name": "P-521",
"desc": "",
"category": "nist",
"oid": "1.3.132.0.35",
"aliases": [
"secg/secp521r1",
"x963/ansip521r1"
],
"seed": "D09E8800291CB85396CC6717393284AAA0DA64BA"
},
{
"name": "B-163",
"desc": "",
"category": "nist",
"oid": "1.3.132.0.15",
"aliases": [
"secg/sect163r2",
"x963/ansit163r2"
],
"seed": "85E25BFE5C86226CDB12016F7553F9D0E693A268"
},
{
"name": "B-233",
"desc": "",
"category": "nist",
"oid": "1.3.132.0.27",
"aliases": [
"secg/sect233r1",
"wtls/wap-wsg-idm-ecid-wtls11",
"x963/ansit233r1"
],
"seed": "74D59FF07F6B413D0EA14B344B20A2DB049B50C3"
},
{
"name": "B-283",
"desc": "",
"category": "nist",
"oid": "1.3.132.0.17",
"aliases": [
"secg/sect283r1",
"x963/ansit283r1"
],
"seed": "77E2B07370EB0F832A6DD5B62DFC88CD06BB84BE"
},
{
"name": "B-409",
"desc": "",
"category": "nist",
"oid": "1.3.132.0.37",
"aliases": [
"secg/sect409r1",
"x963/ansit409r1"
],
"seed": "4099B5A457F9D69F79213D094C4BCD4D4262210B"
},
{
"name": "B-571",
"desc": "",
"category": "nist",
"oid": "1.3.132.0.39",
"aliases": [
"secg/sect571r1",
"x963/ansit571r1"
],
"seed": "2AA058F73A0E33AB486B0F610410C53A7F132310"
}
]
}
]