Elliptic curve cryptography

Elliptic curve cryptography (ECC) refers to cryptographic schemes built on the arithmetic of points on elliptic curves over finite fields.¹² This is an unverified draft, not fact-checked. It covers the cryptographic uses of elliptic curves and is based only on the sources listed in the References section.

HistoryReport an errorSuggest an improvement

Elliptic curve cryptographic schemes were proposed independently in 1985 by Neal Koblitz and Victor Miller, according to a reference-work entry seen in search results but not opened for this draft.¹

According to Matthew Green, NIST and NSA released a pseudorandom number generator based on elliptic curve cryptography in 2005–2006.³ Scientific American states that NIST published the standard in 2006 and that the International Organization for Standardization later adopted it.⁴

Green says that shortly afterwards, Shumow and Ferguson pointed out that the algorithm might contain an NSA backdoor, and that in 2007 two Microsoft researchers argued that its weaknesses could combine to open a backdoor.³ Scientific American reports that the Microsoft engineers stopped short of accusing NIST or the NSA of inserting it intentionally.⁴

SEC 2 version 2.0 was published by Certicom Research and dated 27 January 2010.²

TechnologyReport an errorSuggest an improvement

SEC 2 defines elliptic curve domain parameters over a prime field Fp as a sextuple T = (p, a, b, G, n, h). These consist of a prime p defining the field, coefficients a and b, a base point G, the prime order n of G, and the cofactor h = #E(Fp)/n.²

SEC 2 states that for parameters where log₂ p = 2t, the curve gives about t bits of security, because solving the logarithm problem on the curve is believed to take about 2^t operations.²

SEC 2 recommends curves over Fp at 192, 224, 256, 384 and 521 bits. It describes Koblitz curves and “verifiably random” curves. SECG states that no trapdoors can have been placed in the verifiably random parameters during their generation; this is SECG's own claim, and this draft did not independently check it.²

SEC 2 specifies secp256k1 as a Koblitz curve with a = 0 and b = 7, a 256-bit prime field, and cofactor h = 1. It lists a strength of 128 bits, comparable to a 3072-bit RSA/DSA modulus.²

BIP-340 states that Bitcoin has traditionally authenticated transactions with ECDSA signatures over secp256k1 using SHA-256 hashes. It proposes 64-byte Schnorr signatures over the same curve and lists provable security among its motivations for Schnorr over ECDSA.⁵

GovernanceReport an errorSuggest an improvement

SEC 2 is published by Certicom Research, with copyright held by Certicom Corp. The document permits copying provided it is identified as SEC 2.²

SEC 2 states that the next scheduled review would take place in February 2015. This draft could not confirm whether that review happened.²

SEC 2 notes that compliance with the document may require use of an invention covered by patent rights.²

BIP-340 lists Pieter Wuille, Jonas Nick and Tim Ruffing as authors and is licensed under BSD-2-Clause. Its header links a bitcoin-dev discussion dated 2018-07-06.⁵

NIST removed Dual_EC_DRBG from its revised draft, SP 800-90A Rev. 1, and recommended that current users move to one of the three remaining approved algorithms.⁶

Incidents and controversiesReport an errorSuggest an improvement

Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) was one of four deterministic random bit generators in NIST's SP 800-90 standard.⁴ Green says it is up to a thousand times slower than its symmetric-key alternatives, while noting that slowness is not necessarily one of its flaws.³

In May 2006, researchers at Eindhoven University of Technology reported that the algorithm was insecure and that an attack against it was easy to launch on “an ordinary PC”.⁴

In September 2013, news reports based on documents leaked by Edward Snowden prompted public concern about the algorithm. Those reports said it was vulnerable to tampering that could allow a backdoor. This is a reported allegation, not a finding by NIST, and this draft does not establish whether such a backdoor was inserted.⁴

NIST said it “would not deliberately weaken a cryptographic standard”. Scientific American notes that NIST stood by that statement after an editor's note.⁴

After the 2013 reports, NIST immediately recommended against using the algorithm and reissued SP 800-90A for public comment.⁶ On 19 September 2013, RSA advised developers not to use the default Dual_EC_DRBG generator in its BSAFE product.³

Bruce Schneier, quoted by Scientific American, said that Microsoft, Cisco, Symantec and RSA included the algorithm in their cryptographic libraries primarily because they need it to be eligible for government contracts.⁴

Paul Kocher, quoted by Scientific American, said that “there's really nothing that impacts the fundamental mathematics underpinning encryption here”.⁴

TimelineReport an errorSuggest an improvement

ReferencesReport an errorSuggest an improvement