SafeCurves:
choosing safe curves for elliptic-curve cryptography


Introduction
Curve parameters:
Fields
Equations
Base points
Prime proofs
ECDLP security:
Rho
Transfers
Discriminants
Rigidity
ECC security:
Ladders
Twists
Completeness
Indistinguishability
More information:
References
Verification

Fields

To specify an elliptic curve one specifies a prime number p and then an elliptic-curve equation "over" the finite field F_p, i.e., an elliptic-curve equation with coefficients in that field. The following table shows p for various curves:

Curve

p prime?

p

Anomalous

True

17676318486848893030961583018778670610489016512983351739677143
= 0xb0000000000000000000000953000000000000000000001f9d7
= 17676318486848893030961583018778670610489016512983351739677143

M-221

True

3369993333393829974333376885877453834204643052817571560137951281149
= 0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffd
= 2^221 - 3

E-222

True

6739986666787659948666753771754907668409286105635143120275902562187
= 0x3fffffffffffffffffffffffffffffffffffffffffffffffffffff8b
= 2^222 - 117

NIST P-224

True

26959946667150639794667015087019630673557916260026308143510066298881
= 0xffffffffffffffffffffffffffffffff000000000000000000000001
= 2^224 - 2^96 + 1

Curve1174

True

3618502788666131106986593281521497120414687020801267626233049500247285301239
= 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7
= 2^251 - 9

Curve25519

True

57896044618658097711785492504343953926634992332820282019728792003956564819949
= 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
= 2^255 - 19

BN(2,254)

True

16798108731015832284940804142231733909889187121439069848933715426072753864723
= 0x2523648240000001ba344d80000000086121000000000013a700000000000013
= 16798108731015832284940804142231733909889187121439069848933715426072753864723

brainpoolP256t1

True

76884956397045344220809746629001649093037950200943055203735601445031516197751
= 0xa9fb57dba1eea9bc3e660a909d838d726e3bf623d52620282013481d1f6e5377
= 76884956397045344220809746629001649093037950200943055203735601445031516197751

ANSSI FRP256v1

True

109454571331697278617670725030735128145969349647868738157201323556196022393859
= 0xf1fd178c0b3ad58f10126de8ce42435b3961adbcabc8ca6de8fcf353d86e9c03
= 109454571331697278617670725030735128145969349647868738157201323556196022393859

NIST P-256

True

115792089210356248762697446949407573530086143415290314195533631308867097853951
= 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
= 2^256 - 2^224 + 2^192 + 2^96 - 1

secp256k1

True

115792089237316195423570985008687907853269984665640564039457584007908834671663
= 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
= 2^256 - 2^32 - 977

E-382

True

9850501549098619803069760025035903451269934817616361666987073351061430442874302652853566563721228910201656997576599
= 0x3fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff97
= 2^382 - 105

M-383

True

19701003098197239606139520050071806902539869635232723333974146702122860885748605305707133127442457820403313995153221
= 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff45
= 2^383 - 187

Curve383187

True

19701003098197239606139520050071806902539869635232723333974146702122860885748605305707133127442457820403313995153221
= 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff45
= 2^383 - 187

brainpoolP384t1

True

21659270770119316173069236842332604979796116387017648600081618503821089934025961822236561982844534088440708417973331
= 0x8cb91e82a3386d280f5d6f7e50e641df152f7109ed5456b412b1da197fb71123acd3a729901d1a71874700133107ec53
= 21659270770119316173069236842332604979796116387017648600081618503821089934025961822236561982844534088440708417973331

NIST P-384

True

39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319
= 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff
= 2^384 - 2^128 - 2^96 + 2^32 - 1

Curve41417

True

42307582002575910332922579714097346549017899709713998034217522897561970639123926132812109468141778230245837569601494931472367
= 0x3fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffef
= 2^414 - 17

Ed448-Goldilocks

True

726838724295606890549323807888004534353641360687318060281490199180612328166730772686396383698676545930088884461843637361053498018365439
= 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffffffffffffffffffffffffffffffffffffffffffffffffffff
= 2^448 - 2^224 - 1

M-511

True

6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503041861
= 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff45
= 2^511 - 187

E-521

True

6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
= 0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
= 2^521 - 1

There are other types of elliptic curves. In particular, there are many ECC papers that consider elliptic curves over non-prime finite fields. However, SafeCurves requires prime fields.

Is ECDLP broken for non-prime fields?

No. However, the security story for non-prime fields (e.g., binary extension fields) is more complicated and less stable than the security story for prime fields, as illustrated by 1998 Frey, 2002 Gaudry–Hess–Smart, 2009 Gaudry, and 2012 Petit–Quisquater.

2006 Bernstein stated that prime fields "have the virtue of minimizing the number of security concerns for elliptic-curve cryptography". Similarly, the Brainpool standard and NSA's Suite B standards require prime fields. There is general agreement that prime fields are the safe, conservative choice for ECC.

Are primes required to be 3 mod 4?

All of the SafeCurves requirements can be met by primes that are 1 mod 4, and by primes that are 3 mod 4.

Brainpool requires each prime p to be 3 mod 4. Brainpool does not claim that this has a security justification but claims that it has an efficiency justification. Evaluation of this claim is outside the scope of SafeCurves.

Are special primes dangerous?

Special primes help index calculus, but the point of ECC has always been to avoid index calculus. All of the SafeCurves requirements can be met by special primes.

Brainpool prohibits the NIST primes. However, this is labeled as a patent-avoidance requirement ("avoid patented fast arithmetic"), not a security requirement. Patents are outside the scope of SafeCurves.


Version: This is version 2013.10.13 of the field.html web page.