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?
The Answer
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.”
Background
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.
Who provided the seeds?
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.
How were the seeds 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:
Verifiably at Random?
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:
- Choose an arbitrary bit string
seedof bit length L. - Compute
h = H(seed). - Derive the curve from
hand test if it has prime order. - Repeat if not.
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.
The Lost Passphrase Story
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").
Minghua Qu and the X9.62 Field2m Curve Seeds
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.
What next?
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:
- The “MinghuaQu” seeds co-mingled with the eventual NIST seeds in the same X9.62 document makes a conspiracy to
intentionally weaken the NIST seeds seem less credible. Why would the NSA influence just a few seeds out of a set of
many, which includes several arbitrary, but perfectly valid joke seeds?
Appendix: The Seeds
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.
NIST FIPS-186-2
-
P-192
3045AE6F C8422F64 ED579528 D38120EA E12196D5 -
P-224
BD713447 99D5C7FC DC45B59F A3B9AB8F 6A948BC5 -
P-256
C49D3608 86E70493 6A6678E1 139D26B7 819F7E90 -
P-384
A335926A A319A27A 1D00896A 6773A482 7ACDAC73 -
P-521
D09E8800 291CB853 96CC6717 393284AA A0DA64BA
ANSI X9.62
J.2.1 An Example with m = 191 (Trinomial Basis)
-
4E13CA54 2744D696 E6768756 1517552F 279A8C84
J.2.2 An Example with m = 239 (Trinomial Basis)
-
D34B9A4D 696E6768 75615175 CA71B920 BFEFB05D
J.3.1 An Example with a 192-bit Prime p
-
3045AE6F C8422F64 ED579528 D38120EA E12196D5
J.3.2 An Example with a 239-bit Prime p
-
E43BB460 F0B80CC0 C0B07579 8E948060 F8321B7D
J.4.1 3 Examples with m = 163
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
J.4.3 5 Examples with m = 191
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
J.4.5 5 Examples with m = 239
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
J.4.8 An Example with m = 359
Note: Notice the values in these seeds share bytes with
those for Field2239.
-
2B354920 B724D696 E6768756 1517585B A1332DC6
J.5.1 3 Examples with a 192-bit Prime
-
3045AE6F C8422F64 ED579528 D38120EA E12196D5 -
31A92EE2 029FD10D 901B113E 990710F0 D21AC6B6 -
C4696844 35DEB378 C4B65CA9 591E2A57 63059A2E
J.5.2 3 Examples with a 239-bit Prime
-
E43BB460 F0B80CC0 C0B07579 8E948060 F8321B7D -
E8B40116 04095303 CA3B8099 982BE09F CB9AE616 -
7D737416 8FFE3471 B60A8576 86A19475 D3BFA2FF
J.5.3 An Example with a 256-bit Prime
-
C49D3608 86E70493 6A6678E1 139D26B7 819F7E90
Selected seeds in JSON
[
{
"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"
}
]
}
]