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

CM field discriminants

The number of rational points on an elliptic curve over F_p is p+1-t where t is the trace of the curve. Hasse's theorem states that t is between -2 sqrt(p) and 2 sqrt(p). The order of the base point is a prime divisor of p+1-t.

If s^2 is the largest square dividing t^2-4p then (t^2-4p)/s^2 is a squarefree negative integer. Define D as (t^2-4p)/s^2 if (t^2-4p)/s^2 mod 4 = 1, otherwise as 4(t^2-4p)/s^2. SafeCurves requires the absolute value of this complex-multiplication field discriminant D to be larger than 2^100.

The following table reports t for various curves:

Curve

Trace t

Anomalous

1

M-221

-3509210517603025598879416729141978

E-222

726130336278594909943533816892560

NIST P-224

4733100108545601916421827343930821

Curve1174

45330879683285730139092453152713398836

Curve25519

-221938542218978828286815502327069187962

BN(2,254)

129607518034317099905336561907183648775

brainpoolP256t1

300418416528525664980082381967979838673

ANSSI FRP256v1

-35197163533674495870879651530057169373

NIST P-256

89188191154553853111372247798585809583

secp256k1

432420386565659656852420866390673177327

E-382

4121212830778224615705967802929256988250492817320673387316

M-383

-1329890207450988128841758359484337226464313875646092906354

Curve383187

-2848646777738159098949497252265893762397593991823060136386

brainpoolP384t1

5973228999478432667446284273866865475630836211106699249391

NIST P-384

1388124618062372383606759648309780106643088307173319169677

Curve41417

266913126910041140166481421552787081431877817603289668716758056

Ed448-Goldilocks

28312320572429821613362531907042076847709625476988141958474579766324

M-511

-85798038077085980992356252112544974736566053019478664231724326470621400496530

E-521

1350219053034006823156430521675130544287619844856204906474540600343116434623060

The following table reports D for various curves:

Curve

|D| above 2^100?

CM field discriminant D

Anomalous

False

-11
= -1 * 11
≈ -2^3.5

M-221

True

-291353719179906265188530617286099241628963951767455785707930843028
= -1 * 2^2 * 565665984379 * 504842927415879955942747 * 255061103803346185973548526989
≈ -2^217.5

E-222

True

-6608170350471643616864756015049517704658839381741662384672256723787
= -1 * 17 * 53 * 937 * 12569 * 7544066725621 * 5576396455796813 * 14803246073281859780125586623
≈ -2^222.0

NIST P-224

True

-9493061114565352281698673660738078664961855212656825491744070162387
= -1 * 3 * 29 * 79 * 7523 * 40927 * 11549194661 * 388425074903852603481408727235725774844022299
≈ -2^222.5

Curve1174

True

-3104780625450999362585819446753918118449992865572619605369411600236483762515
= -1 * 5 * 7 * 293 * 33997 * 12320708804681 * 4473682817603206637471 * 161567415114024992333870349255799
≈ -2^250.8

Curve25519

True

-45581865488086735760375465490143625275457651809622790057958535113426043391588
= -1 * 2^2 * 16451 * 8312956054562778877481 * 83326725728999296701078628838522133333655224556987
≈ -2^254.7

BN(2,254)

False

-3
= -1 * 3
≈ -2^1.6

brainpoolP256t1

True

-8691544023946985377062942659708535371791103179088907241627919875068758335603
= -1 * 1867 * 11616307 * 66891682553 * 5991180651865208777371442029237375648904065304322611579
≈ -2^252.3

ANSSI FRP256v1

True

-436579445005972888745654076483329727173807379171830662730632433775066880362307
= -1 * 27748561 * 649570254101 * 1624594239517 * 1424961889141606181 * 10462814633518742617783767031
≈ -2^257.9

NIST P-256

True

-455213823400003756884736869668539463648899917731097708475249543966132856781915
= -1 * 3 * 5 * 456597257999 * 1428624589419343516204097 * 46523541035814968339936406074986559003387
≈ -2^258.0

secp256k1

False

-3
= -1 * 3
≈ -2^1.6

E-382

True

-5604402749955852942483724628413745392904283610682118766844071172345634654517408799240742719278662600282477660155635
= -1 * 5 * 11 * 48109 * 10266294221277769350489312192694310037089 * 206313008356732063557587210852462234703789278064725964307040844617657
≈ -2^381.2

M-383

True

-19258851107228731545828718129513456469296418076652378795412690502061347371969797807383872203606479878618074341759892
= -1 * 2^2 * 15625838027 * 18702316172396287 * 16475237022945471409272211849733819466846279153222801284256298041819798160529572178177777
≈ -2^383.0

Curve383187

True

-17672305982117740404685445619512526377032293120629323304512499228680297438813243605479730912727743795113378764867972
= -1 * 2^2 * 29 * 150041 * 869237302217 * 1168118569486389440308203361557649499676771110259307362471795835525621803683357571467152044105461
≈ -2^382.8

brainpoolP384t1

True

-421137342150968156401073657463902608517955808599119887457074293277751733352456681547155756681917575445787031884483
= -1 * 6857 * 379795560371 * 37573380636081815018124278995574282493401057 * 4303872990401223419424669070518309027547364146662699977
≈ -2^377.5

NIST P-384

True

-155681134830307109642776504688282010728208281558659670869973287018687614232295158412465272949685257139190903176164947
= -1 * 17299349 * 295429921339288635355502201959 * 30461532566489734432033897907025322605647670983785646081730729521647935009277217
≈ -2^386.0

Curve41417

True

-24496927673351978370659002191430888254029888724109400877661217070649404917203373976631385775391573863930040620883263221247583
= -1 * 3607 * 26662209338045324627822402579758961857427012457827101 * 254723693668765069288156859027433499782242697184918145687475956144269
≈ -2^413.2

Ed448-Goldilocks

True

-526441850246598665100130500130299249884327037339362573644758821004312655096754090084837687027570936497061571295914040961206462407247195
= -1 * 5 * 7 * 15041195721331390431432300003722835710980772495410359246993109171551790145621545430995362486502026757058902037026115456034470354492777
≈ -2^447.5

M-511

True

-4863578130502024585076720668569588706357183194522625427347901780103645321123110099471629956086341313364661087054760942075423952457607839254394891867531636
= -1 * 2^2 * 7 * 24808504515989 * 451891442863291858329691135763436236651 * 15493986128158476657348900881244458351785958199592331238146398726181728333640083540874179214877522733
≈ -2^510.5

E-521

True

-6409024787336597182452704638157849663902413445881799708062890073781848374600374526006907958947130616000016893207822517365554532226160588767463876510044116251
= -1 * 47 * 23658857317 * 3352477528785765665039059407454939 * 33155235381061135339413842529253257652930251589295381 * 51854008820489653721386166877183100314125013148827513519511
≈ -2^520.9

How do I verify the trace?

Verifying that the base point has order ℓ guarantees that the curve order p+1-t is a multiple of ℓ. Typically ℓ is above 4 sqrt(p), so there is only one multiple of ℓ between p+1-2 sqrt(p) and p+1+2 sqrt(p); this multiple must be p+1-t.

Is ECDLP broken for curves with small |D|?

Slightly. Specifically, there are speedups to the rho method for some curves where |D| is very small, using fast "endomorphisms" derived from D.

This is not a complete break. The limits of these speedups are reasonably well understood, and the literature does not indicate any mechanism that could allow further speedups for small |D|. Pairing-based cryptography relies heavily on curves where |D| is small. It is conceivable that these curves are much easier to break, but it is also conceivable that curves with large |D| are much easier to break.

To summarize, there is no evidence of serious problems with either small |D| or large |D|, but the security story is more complicated for small |D|. SafeCurves therefore requires large |D|.

Brainpool contains a related requirement: the class number, a quantity related to D, is required to be larger than 1000000. The generalized Riemann hypothesis (a standard conjecture in number theory, backed by extensive evidence) implies that the class number is not far from the square root of |D|; it is thus reasonably clear that the Brainpool requirement is much weaker than the SafeCurves requirement that |D| be larger than 2^100. With some computation one can compute exact class numbers, and with less computation one can verify the Brainpool class-number condition, but this has not been incorporated into SafeCurves.


Version: This is version 2013.10.29 of the disc.html web page.