SafeCurves:
choosing safe curves for elliptic-curve cryptography

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.