NIST SP 800-186 日本語訳

Let \(E\) be an elliptic curve defined over the field \(\mathrm{GF}(q)\). The cardinality \(|E|\) of the curve is equal to the number of points defined over \(\mathrm{GF}(q)\) on the curve and satisfies the equation \(|E| = (q+1)-t\), where \(|t| \le 2\sqrt{q}\). Thus, \(|E|\) and \(q\) have the same order of magnitude.

The integer \(t\) is called the trace of \(E\) over the field \(\mathrm{GF}(q)\). The points on \(E\) form a commutative group under addition (for the group law for each curve form, see Appendix A). Any point \(P\) on the curve is the generator of a cyclic subgroup \(\langle P \rangle = \{kP \mid k = 0, 1, 2, \ldots\}\) of \(E\). The order of \(P\) in \(E\) is defined as the cardinality of \(\langle P \rangle\). A curve is cyclic if it is generated by some point on \(E\). All curves of prime order are cyclic, while all curves of order \(|E| = h \cdot n\), where \(n\) is a large prime number and \(h\) is a small number, have a large cyclic subgroup of prime order \(n\). If \(R\) is a point on the curve that is also contained in \(\langle P \rangle\), there is a unique integer \(k\) in the interval \([0, l-1]\) so that \(R = kP\), where \(l\) is the order of \(\mathrm{P}\) in \(E\). This number is called the discrete logarithm of \(R\) to the base \(P\). The discrete logarithm problem is the problem of finding the discrete logarithm of \(R\) to the base \(P\) for any two points \(P\) and \(R\) on the curve, if such a number exists. A quadratic twist of \(E\) is a curve \(E'\) related to \(E\), with cardinality \(|E'| = (q+1)+t\). If \(E\) is a curve in one of the curve forms specified in this Recommendation, a quadratic twist of this curve can be expressed using the same curve model, although with different curve parameters.

Let \(\mathrm{GF}(q)\) denote the finite field with \(q\) elements, where \(q\) is an odd prime power and is not divisible by three. Let \(W_{a,b}\) be the Weierstrass curve with the defining equation \(y^2 = x^3 + ax + b\),

where \(a\) and \(b\) are elements of \(\mathrm{GF}(q)\) with \(4a^3 + 27b^2 \ne 0\). When selecting curve parameters, a \(\mathit{Seed}\) value may be used to generate the parameters \(a\) and \(b\) as described in Appendix C.2.1.1. The points of \(W_{a,b}\) are the ordered pairs \((x, y)\) whose coordinates are elements of \(\mathrm{GF}(q)\) and that

satisfy the defining equation (i.e., the affine points) together with the special point \(\varnothing\) (the “point at infinity”). This set forms a group under the operation of addition on elliptic curves via the “chord-and-tangent” rule, where the point at infinity serves as the identity element. See Appendix A.1.1 for details of the group operation.

Let \(\mathrm{GF}(q)\) denote the finite field with \(q\) elements, where \(q\) is an odd prime power. Let \(E_{a,d}\) be the

twisted Edwards curve with defining equation \(ax^2 + y^2 = 1 + dx^2y^2\), where \(a\) and \(d\) are elements of \(\mathrm{GF}(q)\) with \(a, d \ne 0\), \(a \ne d\), and \(a\) is a square in \(\mathrm{GF}(q)\) while \(d\) is not. The points of \(E_{a,d}\) are the

ordered pairs \((x, y)\) whose coordinates are elements of \(\mathrm{GF}(q)\) and that satisfy the defining equation (i.e., the affine points). It can be shown that this set forms a group under the operation addition, where the point \((0, 1)\) serves as the identity element. The addition formulae are complete, meaning that the formulae work for all inputs on the curve. See Appendix A.1.3 for details of the group operation. An Edwards curve is a twisted Edwards curve with \(a = 1\).

Let \(\mathrm{GF}(q)\) denote the finite field with \(q\) elements, where \(q = 2^m\). Let \(B_{a,b}\) be the Weierstrass curve

with defining equation \(y^2 + xy = x^3 + ax^2 + b\), where \(a\) and \(b\) are elements of \(\mathrm{GF}(q)\) with \(b \ne 0\). The points of \(B_{a,b}\) are the ordered pairs \((x, y)\) whose coordinates are elements of \(\mathrm{GF}(q)\) and that

satisfy the defining equation (i.e., the affine points) together with the special point \(\varnothing\) (the “point at infinity”). This set forms a group under the operation of addition on elliptic curves via the “chord-and-tangent” rule, where the point at infinity serves as the identity element. See Appendix A.2.1 for details of the group operation.

This section specifies the elliptic curves recommended for U.S. Federal Government use and contains choices for the private key length and underlying fields. This includes elliptic curves over prime fields (Section 3.2) and elliptic curves over binary fields (Section 3.3), where each curve takes one of the forms described in Section 3 (referred to as “\(\mathit{Type}\)” below).

Each recommended curve is uniquely defined by its domain parameters \(D\), which indicate the field \(\mathrm{GF}(q)\) over which the elliptic curve is defined, the parameters of its defining equation, and principal parameters, such as the cofactor \(h\) of the curve, the order \(n\) of its prime-order subgroup, and a designated point \(G\) on the curve of order \(n\) (i.e., the “base point”). In the case \(q = 2^m\), the domain parameters also include a description of the representation chosen for \(\mathrm{GF}(q)\).

For details regarding the generation method of the elliptic curves, see Appendix C.

The principal parameters for elliptic curve cryptography are the elliptic curve \(E\) and a designated point \(G\) on \(E\) called the base point. The base point has order \(n\), which is a large prime. The number of points on the curve is \(h \cdot n\) for some integer \(h\) (the cofactor), which is not divisible by \(n\). For efficiency reasons, it is desirable for the cofactor to be small. All of the curves given below have cofactors 1, 2, 4, or 8. As a result, the private and public keys for a curve are approximately the same length.

1. A prime field is the field \(\mathrm{GF}(p)\), which contains a prime number \(p\) of elements. The elements of this field are the integers modulo \(p\), and the field arithmetic is implemented in terms of the arithmetic of integers modulo \(p\).

2. A binary field is the field \(\mathrm{GF}(2^m)\), which contains \(2^m\) elements for some \(m\) (called the degree of the field). The elements of this field are the bit strings of length \(m\), and the field arithmetic is implemented in terms of operations on the bits.

The approximate security strengths for the elliptic curves specified in this document are given in Table 1. The security strength of an elliptic curve is directly related to the order of the basepoint. In general, if an elliptic curve has a basepoint of order \(n\), then the security strength will be approximately one half of the bit length of \(n\).

• A polynomial basis is specified by an irreducible polynomial modulo 2 called the field polynomial. The bit string \((a_{m-1} \; \ldots \; a_2 \; a_1 \; a_0)\) is used to represent the polynomial

over \(\mathrm{GF}(2)\). The field arithmetic is implemented as polynomial arithmetic modulo \(p(t)\), where \(p(t)\) is the field polynomial.

• A normal basis is specified by an element \(\theta\) of a particular kind. The bit string \((a_0 \; a_1 \; a_2 \; \ldots \; a_{m-1})\) is used to represent the element

Normal basis field arithmetic is not easy to describe or efficient to implement in general except for a special class called Type \(T\) low-complexity normal bases. For a given field of degree \(m\), the choice of \(T\) specifies the basis and the field arithmetic (see Appendix G.3).

• Polynomial Basis: If an irreducible trinomial \(t^m + t^k + 1\) exists over \(\mathrm{GF}(2)\), then the field polynomial \(p(t)\) is chosen to be the irreducible trinomial with the lowest-degree middle term \(t^k\). If no irreducible trinomial exists, then a pentanomial \(t^m + t^a + t^b + t^c + 1\) is selected. The particular pentanomial chosen has the following properties: the second term \(t^a\) has the lowest degree among all irreducible pentanomials of degree \(m\); the third term \(t^b\) has the lowest degree among all irreducible pentanomials of degree \(m\) with the second term \(t^a\); and the fourth term \(t^c\) has the lowest degree among all irreducible pentanomials of degree \(m\) with the second term \(t^a\) and third term \(t^b\).

• Normal Basis: Choose the Type \(T\) low-complexity normal basis with the smallest \(T\).

For each curve size range, the following curves are given in Sections 3.2 and 3.3:
→ A pseudorandom curve over \(\mathrm{GF}(p)\)
→ A pseudorandom curve over \(\mathrm{GF}(2^{m})\)
→ A special curve over \(\mathrm{GF}(2^{m})\) called a Koblitz curve or anomalous binary curve

In addition, some special Edwards, Weierstrass, and Montgomery curves over \(\mathrm{GF}(p)\) are given for two size ranges.

This specification includes pseudorandom Weierstrass curves generated over prime fields P-192, P-224, P-256, P-384, and P-521 (see Sections 3.2.1.2 – 3.2.1.5) and special Weierstrass curves over prime fields W-25519 (Section 3.2.1.6) and W-448 (Section 3.2.1.7).

For each Weierstrass curve,

the following domain parameters \(D = (p, h, n, \mathit{Type}, a, b, G, \{\mathit{Seed}, c\})\) are given:

• The prime modulus \(p\)

• The cofactor \(h\)

o For pseudorandom curves, the cofactor \(h = 1\), so the order \(n\) is prime.
o For special curves, the cofactor \(h > 1\), so the order \(n\) is not prime.

• The \(\mathit{Type}\) is “Weierstrass curve”

• The coefficient \(a\)

o For pseudorandom curves, \(a = -3\) was made for reasons of efficiency; see IEEE Std 1363-2000.

• The coefficient \(b\)
o For pseudorandom curves, the coefficient \(b\) satisfies \(b^{2} c \equiv -27 \bmod p\).

• The base point \(G\) with \(x\) coordinate \(G_x\) and \(y\) coordinate \(G_y\)

• The 160-bit input \(\mathit{Seed}\) to the SHA-1 hash algorithm in Appendix C.3 for pseudorandom curves. \(\mathit{Seed}\) is not used with the special curves W-25519 (Section 3.2.1.6) and W-448 (Section 3.2.1.7).

• The output \(c\) of the SHA-1 hash algorithm used for pseudorandom curves. The value \(c\) is not used with the special curves W-25519 (Section 3.2.1.6) and W-448 (Section 3.2.1.7).

The elliptic curve P-224 is a Weierstrass curve \(W_{a,b}\) defined over the prime field \(\mathrm{GF}(p)\) that has order \(h \cdot n\), where \(h = 1\), and \(n\) is a prime number. The quadratic twist of this curve has order \(h_1 \cdot n_1\), where \(h_1\) = 3^2 × 11 × 47 × 3015283 × 40375823 × 267983539294927, and \(n_1\) is a prime number.¹ This curve has domain parameters \(D = (p, h, n, \mathit{Type}, a, b, G, \{\mathit{Seed}, c\})\), where the \(\mathit{Type}\) is “Weierstrass curve,” and the other parameters are defined as follows:

\(p\): \(2^{224} - 2^{96} + 1\)
= 26959946667150639794667015087019630673557916260026308143510066298881
(= 0xffffffff ffffffff ffffffff ffffffff 00000000 00000000 00000001)

\(h\): 1
\(n\): 26959946667150639794667015087019625940457807714424391721682722368061
(= 0xffffffff ffffffff ffffffff ffff16a2 e0b8f03e 13dd2945 5c5c2a3d)

\(\mathit{tr}\): 4733100108545601916421827343930821
(\(= (p+1) - h \cdot n =\) 0xe95c 1f470fc1 ec22d6ba a3a3d5c5)

\(a\): \(-3\)
= 26959946667150639794667015087019630673557916260026308143510066298878
(= 0xffffffff ffffffff ffffffff fffffffe ffffffff ffffffff fffffffe)

\(b\): 18958286285566608000408668544493926415504680968679321075787234672564
(= 0xb4050a85 0c04b3ab f5413256 5044b0b7 d7bfd8ba 270b3943 2355ffb4)

\(G_x\): 19277929113566293071110308034699488026831934219452440156649784352033 (\(=\)0xb70e0cbd 6bb4bf7f 321390b9 4a03c1d3 56c21122 343280d6 115c1d21)

\(G_y\): 19926808758034470970197974370888749184205991990603949537637343198772 (= 0xbd376388 b5f723fb 4c22dfe6 cd4375a0 5a074764 44d58199 85007e34)

\(\mathit{Seed}\): 0xbd713447 99d5c7fc dc45b59f a3b9ab8f 6a948bc5

\(c\): 9585649763196999776159690989286240671136085803543320687376622326267 (= 0x5b056c7e 11dd68f4 0469ee7f 3c7a7d74 f7d12111 6506d031 218291fb)

The elliptic curve P-256 is a Weierstrass curve \(W_{a,b}\) defined over the prime field \(\mathrm{GF}(p)\) that has order \(h \cdot n\), where \(h = 1\), and \(n\) is a prime number. The quadratic twist of this curve has order \(h_1 \cdot n_1\), where \(h_1 = 3 \times 5 \times 13 \times 179\), and \(n_1\) is a prime number. This curve has domain parameters \(D = (p, h, n, \mathit{Type}, a, b, G, \{\mathit{Seed}, c\})\), where the \(\mathit{Type}\) is “Weierstrass curve,” and the other parameters are defined as follows:

\(p\): \(2^{256} - 2^{224} + 2^{192} + 2^{96} - 1\) = 115792089210356248762697446949407573530086143415290314195533631308867097853951 (= 0xffffffff 00000001 00000000 00000000 00000000 ffffffff ffffffff ffffffff)

\(h\): 1
\(n\): 115792089210356248762697446949407573529996955224135760342422259061068512044369 (= 0xffffffff 00000000 ffffffff ffffffff bce6faad a7179e84 f3b9cac2 fc632551)

\(\mathit{tr}\): 89188191154553853111372247798585809583 (\(= (p+1) - h \cdot n =\) 0x43190553 58e8617b 0c46353d 039cdaaf)

\(a\): \(-3\) = 115792089210356248762697446949407573530086143415290314195533631308867097853948 (= 0xffffffff 00000001 00000000 00000000 00000000 ffffffff ffffffff fffffffc)

\(b\): 41058363725152142129326129780047268409114441015993725554835256314039467401291 (= 0x5ac635d8 aa3a93e7 b3ebbd55 769886bc 651d06b0 cc53b0f6 3bce3c3e 27d2604b)

\(G_x\): 48439561293906451759052585252797914202762949526041747995844080717082404635286 (= 0x6b17d1f2 e12c4247 f8bce6e5 63a440f2 77037d81 2deb33a0 f4a13945 d898c296)

\(G_y\): 36134250956749795798585127919587881956611106672985015071877198253568414405109 (= 0x4fe342e2 fe1a7f9b 8ee7eb4a 7c0f9e16 2bce3357 6b315ece cbb64068 37bf51f5)

\(\mathit{Seed}\): 0xc49d3608 86e70493 6a6678e1 139d26b7 819f7e90

\(c\): 57436011470200155964173534038266061871440426244159038175955947309464595790349 (= 0x7efba166 2985be94 03cb055c 75d4f7e0 ce8d84a9 c5114abc af317768 0104fa0d)

\(p\): \(2^{384} - 2^{128} - 2^{96} + 2^{32} - 1\) = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319 (= 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe ffffffff 00000000 00000000 ffffffff)

\(h\): 1
\(n\): 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643 (= 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff c7634d81 f4372ddf 581a0db2 48b0a77a ecec196a ccc52973)

\(\mathit{tr}\): 1388124618062372383606759648309780106643088307173319169677 (= \((p+1) - h \cdot n\) = 0x389cb27e 0bc8d21f a7e5f24c b74f5885 1313e696 333ad68d)

\(a\): \(-3\) = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112316 (= 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe ffffffff 00000000 00000000 fffffffc)

\(b\): 27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575 (= 0xb3312fa7 e23ee7e4 988e056b e3f82d19 181d9c6e fe814112 0314088f 5013875a c656398d 8a2ed19d 2a85c8ed d3ec2aef)

\(G_x\): 26247035095799689268623156744566981891852923491109213387815615900925518854738050089022388053975719786650872476732087 (= 0xaa87ca22 be8b0537 8eb1c71e f320ad74 6e1d3b62 8ba79b98 59f741e0 82542a38 5502f25d bf55296c 3a545e38 72760ab7)

\(G_y\): 8325710961489029985546751289520108179287853048861315594709205902480503199884419224438643760392947333078086511627871 (= 0x3617de4a 96262c6f 5d9e98bf 9292dc29 f8f41dbd 289a147c e9da3113 b5f0b8c0 0a60b1ce 1d7e819d 7a431d7c 90ea0e5f)

\(\mathit{Seed}\): 0xa335926a a319a27a 1d00896a 6773a482 7acdac73

\(c\): 1874980186709887347182107097135388878869033900306543902178\
0101954060871745882341382251168574711376101826101037376643 (\(=\)0x79d1e655 f868f02f ff48dcde e14151dd b80643c1 406d0ca1 0dfe6fc5 2009540a 495e8042 ea5f744f 6e184667 cc722483)

\(p\): \(2^{521} - 1\) = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151 (= 0x1ff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff)

\(h\): 1
\(n\): 6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449 (= 0x1ff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffa 51868783 bf2f966b 7fcc0148 f709a5d0 3bb5c9b8 899c47ae bb6fb71e 91386409)

\(\mathit{tr}\): 657877501894328237357444332315020117536923257219387276263472201219398408051703 (\(= (p+1) - h \cdot n =\) 0x5 ae79787c 40d06994 8033feb7 08f65a2f c44a3647 7663b851 449048e1 6ec79bf7)

\(a\): \(-3\) = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057148 (= 0x1ff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffc)

\(b\): 1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984 (= 0x051 953eb961 8e1c9a1f 929a21a0 b68540ee a2da725b 99b315f3 b8b48991 8ef109e1 56193951 ec7e937b 1652c0bd 3bb1bf07 3573df88 3d2c34f1 ef451fd4 6b503f00)

\(G_x\): 2661740802050217063228768716723360960729859168756973147706671368418802944996427808491545080627771902352094241225065558662157113545570916814161637315895999846 (= 0xc6 858e06b7 0404e9cd 9e3ecb66 2395b442 9c648139 053fb521 f828af60 6b4d3dba a14b5e77 efe75928 fe1dc127 a2ffa8de 3348b3c1 856a429b f97e7e31 c2e5bd66)

\(G_y\): 3757180025770020463545507224491183603594455134769762486694567779615544477440556316691234405012945539562144444537289428522585666729196580810124344277578376784 (= 0x118 39296a78 9a3bc004 5c8a5fb4 2c7d1bd9 98f54449 579b4468 17afbd17 273e662c 97ee7299 5ef42640 c550b901 3fad0761 353c7086 a272c240 88be9476 9fd16650)

\(\mathit{Seed}\): 0xd09e8800 291cb853 96cc6717 393284aa a0da64ba

\(c\): 2420736670956961470587751833778383872272949280174637971106318223956010636355557333899035866342650378575221277268886182704643828850020061383251826928984446519 (= 0x0b4 8bfa5f42 0a349495 39d2bdfc 264eeeeb 077688e4 4fbf0ad8 f6d0edb3 7bd6b533 28100051 8e19f1b9 ffbe0fe9 ed8a3c22 00b8f875 e523868c 70c1e5bf 55bad637)

The elliptic curve W-25519 is a Weierstrass curve \(W_{a,b}\) defined over the prime field \(\mathrm{GF}(p)\) with \(p = 2^{255} - 19\) that has order \(h \cdot n\), where \(h = 8\), and \(n\) is a prime number. The quadratic twist of this curve has order \(h_1 \cdot n_1\), where \(h_1 = 4\), and \(n_1\) is a prime number. This curve has domain parameters \(D = (p, h, n, \mathit{Type}, a, b, G)\), where the \(\mathit{Type}\) is “Weierstrass curve,” and the other parameters are defined as follows:

\(p\): \(2^{255} - 19\) (\(=\)0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffed)

\(h\): 8
\(n\): 7237005577332262213973186563042994240857116359379907606001950938285454250989 (\(= 2^{252} +\) 0x14def9de a2f79cd6 5812631a 5cf5d3ed)

\(\mathit{tr}\): −221938542218978828286815502327069187962 (\(= (p+1) - h \cdot n = -\) 0xa6f7cef5 17bce6b2 c09318d2 e7ae9f7a)

\(a\): 19298681539552699237261830834781317975544997444273427339909597334573241639236 (\(=\)0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaa98 4914a144)

\(b\): 55751746669818908907645289078257140818\
241103727901012315294400837956729358436 (\(=\)0x7b425ed0 97b425ed 097b425e d097b425 ed097b42 5ed097b4 260b5e9c 7710c864)

\(G_x\): 19298681539552699237261830834781317975\
544997444273427339909597334652188435546 (\(=\)0x2aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaad245a)

\(G_y\): 43114425171068552920764898935933967039\
370386198203806730763910166200978582548 (\(=\)0x5f51e65e 475f794b 1fe122d3 88b72eb3 6dc2b281 92839e4d d6163a5d 81312c14)

The elliptic curve W-448 is the Weierstrass curve \(W_{a,b}\) defined over the prime field \(\mathrm{GF}(p)\) with \(p = 2^{448}-2^{224}-1\) and has order \(h \cdot n\), where \(h = 4\), and \(n\) is a prime number. The quadratic twist of this curve has order \(h_1 \cdot n_1\), where \(h_1 = 4\), and \(n_1\) is a prime number. This curve has domain parameters \(D = (p, h, n, \mathit{Type}, a, b, G)\), where the \(\mathit{Type}\) is “Weierstrass curve,” and the other parameters are defined as follows:

\(p\): \(2^{448} - 2^{224} - 1\) (\(=\)0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff)

\(h\): 4
\(n\): 181709681073901722637330951972001133588410340171829515070372549795146003961539585716195755291692375963310293709091662304773755859649779 (=\(2^{446} -\) 0x8335dc16 3bb124b6 5129c96f de933d8d 723a70aa dc873d6d 54a7bb0d)

\(\mathit{tr}\): 28312320572429821613362531907042076847709625476988141958474579766324 (\(=(p+1) - h \cdot n =\) 0x1 0cd77058 eec492d9 44a725bf 7a4cf635 c8e9c2ab 721cf5b5 529eec34)

\(a\): 484559149530404593699549205258669689569094240458212040187660132787074885444487181790930922465784363953392589641229091574035657199637535 (=0xaaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaa9 ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe 1a76d41f)

\(b\): 269199527516891440944194002921483160871719022476784466770922295992819380802492878772739401369880202196329216467349495319191685664513904 (=0x5ed097b4 25ed097b 425ed097 b425ed09 7b425ed0 97b425ed 097b425e 71c71c71 c71c71c7 1c71c71c 71c71c71 c71c71c7 1c72c87b 7cc69f70)

\(G_x\): 4845591495304045936995492052586696895690942404582120401876601327870\
7488544448718179093092246578436395339258964122909157403566534562907 (\(=\)0xaaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa 00000000 00000000 00000000 00000000 00000000 00000000 0000cb91)

\(G_y\): 3552939267855681752641275020637833348089763993877142718318808984351\
69088786967410002932673765864550910142774147268105838985595290606362 (\(=\)0x7d235d12 95f5b1f6 6c98ab6e 58326fce cbae5d34 f55545d0 60f75dc2 8df3f6ed b8027e23 46430d21 1312c4b1 50677af7 6fd7223d 457b5b1a)

The elliptic curve Curve25519 is the Montgomery curve \(M_{A,B}\) defined over the prime field \(\mathrm{GF}(p)\) with \(p = 2^{255}-19\) and parameters \(A = 486662\) and \(B = 1\) [RFC_7748]. This curve has order \(h \cdot n\), where \(h = 8\), and \(n\) is a prime number. For this curve, \(A^2-4\) is not a square in \(\mathrm{GF}(p)\), whereas \(A+2\) is. The quadratic twist of this curve has order \(h_1 \cdot n_1\), where \(h_1 = 4\), and \(n_1\) is a prime number. This curve has domain parameters \(D = (p, h, n, \mathit{Type}, A, B, G)\), where the \(\mathit{Type}\) is “Montgomery curve,” and the other parameters are defined as follows:

\(p\): \(2^{255}-19\) (\(=\)0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffed)

\(h\): 8

\(n\): 72370055773322622139731865630429942408\
57116359379907606001950938285454250989 (\(=2^{252} +\) 0x14def9de a2f79cd6 5812631a 5cf5d3ed)

\(\mathit{tr}\): −221938542218978828286815502327069187962 (\(= (p+1) - h \cdot n = -\) 0xa6f7cef5 17bce6b2 c09318d2 e7ae9f7a)

\(A\): 486662

\(B\): 1

\(G_u\): 9 (=0x9)

\(G_v\): 43114425171068552920764898935933967039370386198203806730763910166200978582548 (=0x5f51e65e 475f794b 1fe122d3 88b72eb3 6dc2b281 92839e4d d6163a5d 81312c14)

The elliptic curve Curve448 is the Montgomery curve \(M_{A,B}\) defined over the prime field \(\mathrm{GF}(p)\) with \(p = 2^{448}-2^{224}-1\) and parameters \(A = 156326\) and \(B = 1\) [RFC_7748]. This curve has order \(h \cdot n\), where \(h = 4\), and \(n\) is a prime number. For this curve, \(A^2-4\) is not a square in \(\mathrm{GF}(p)\), whereas \(A-2\) is. The quadratic twist of this curve has order \(h_1 \cdot n_1\), where \(h_1 = 4\), and \(n_1\) is a prime number.

This curve has domain parameters \(D = (p, h, n, \mathit{Type}, A, B, G)\), where the \(\mathit{Type}\) is “Montgomery curve,” and the other parameters are defined as follows:

\(p\): \(2^{448}-2^{224}-1\) (=0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff)

\(h\): 4
\(n\): 181709681073901722637330951972001133588410340171829515070372549795146003961539585716195755291692375963310293709091662304773755859649779 (=\(2^{446} -\) 0x8335dc16 3bb124b6 5129c96f de933d8d 723a70aa dc873d6d 54a7bb0d)

\(\mathit{tr}\): 28312320572429821613362531907042076847709625476988141958474579766324 (\(=(p+1) - h \cdot n =\) 0x1 0cd77058 eec492d9 44a725bf 7a4cf635 c8e9c2ab 721cf5b5 529eec34)

\(A\): 156326

\(B\): 1

\(G_u\): 5 (=0x5)

\(G_v\): 355293926785568175264127502063783334808976399387714271831880898435169088786967410002932673765864550910142774147268105838985595290606362 (=0x7d235d12 95f5b1f6 6c98ab6e 58326fce cbae5d34 f55545d0 60f75dc2 8df3f6ed b8027e23 46430d21 1312c4b1 50677af7 6fd7223d 457b5b1a)

The elliptic curve Edwards25519 is the twisted Edwards curve \(E_{a,d}\) defined over the prime field

\(\mathrm{GF}(p)\) with \(p = 2^{255}-19\) and parameters \(a = -1\) and \(d = -121665/121666\) (i.e., 37095705934669439343138083508754565189542113879843219016388785533085940283555) [RFC_8032]. This curve has order \(h \cdot n\), where \(h = 8\), and \(n\) is a prime number. For this curve, \(a\) is a square in \(\mathrm{GF}(p)\), whereas \(d\) is not. The quadratic twist of this curve has order \(h_1 \cdot n_1\), where \(h_1 = 4\), and \(n_1\) is a prime number. This curve has domain parameters \(D = (p, h, n, \mathit{Type}, a, d, G)\), where the \(\mathit{Type}\) is “twisted Edwards curve,” and the other parameters are defined as follows:

\(p\): \(2^{255}-19\)
(=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffed)

\(h\): \(8\)
\(n\): 72370055773322622139731865630429942408\
57116359379907606001950938285454250989
(=\(2^{252} +\) 0x14def9de a2f79cd6 5812631a 5cf5d3ed)

\(\mathit{tr}\): −221938542218978828286815502327069187962
(=\((p+1) - h \cdot n = -\) 0xa6f7cef5 17bce6b2 c09318d2 e7ae9f7a)

\(a\): \(-1\)
\(d\): \(-121665/121666 =\) 37095705934669439343138083508754565189\
542113879843219016388785533085940283555
(=0x52036cee 2b6ffe73 8cc74079 7779e898 00700a4d 4141d8ab 75eb4dca 135978a3)

\(G_x\): 15112221349535400772501151409588531511\
454012693041857206046113283949847762202
(=0x216936d3 cd6e53fe c0a4e231 fdd6dc5c 692cc760 9525a7b2 c9562d60 8f25d51a)

\(G_y\): \(4/5 =\) 46316835694926478169428394003475163141\
307993866256225615783033603165251855960
(=0x66666666 66666666 66666666 66666666 66666666 66666666 66666666 66666658)

The elliptic curve Edwards448 is the Edwards curve \(E_{a,d}\) defined over the prime field \(\mathrm{GF}(p)\) with \(p = 2^{448}-2^{224}-1\) and parameters \(a = 1\) and \(d = -39081\) [RFC_8032]. This curve has order \(h \cdot n\), where \(h = 4\), and \(n\) is a prime number. For this curve, \(a\) is a square in \(\mathrm{GF}(p)\), whereas \(d\) is not. The quadratic twist of this curve has order \(h_1 \cdot n_1\), where \(h_1 = 4\), and \(n_1\) is a prime number. This curve has domain parameters \(D = (p, h, n, \mathit{Type}, a, d, G)\), where the \(\mathit{Type}\) is “twisted Edwards curve,” and the other parameters are defined as follows:

\(p\): \(2^{448}-2^{224}-1\)
(=0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff)

\(h\): \(4\)
\(n\): 1817096810739017226373309519720011335884103401718295150703725497951
46003961539585716195755291692375963310293709091662304773755859649779
(=\(2^{446} -\) 0x8335dc16 3bb124b6 5129c96f de933d8d 723a70aa dc873d6d 54a7bb0d)

\(\mathit{tr}\): 28312320572429821613362531907042076847709625476988141958474579766324 (= \((p+1) - h \cdot n\) = 0x1 0cd77058 eec492d9 44a725bf 7a4cf635 c8e9c2ab 721cf5b5 529eec34)

\(a\): \(1\)
\(d\): \(-39081\) = 726838724295606890549323807888004534353641360687318060281490199180612328166730772686396383698676545930088884461843637361053498018326358 (= 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffff6756)

\(G_x\): 224580040295924300187604334099896036246789641632564134246125461686950415467406032909029192869357953282578032075146446173674602635247710 (= 0x4f1970c6 6bed0ded 221d15a6 22bf36da 9e146570 470f1767 ea6de324 a3d3a464 12ae1af7 2ab66511 433b80e1 8b00938e 2626a82b c70cc05e)

\(G_y\): 298819210078481492676017930443930673437544040154080242095928241372331506189835876003536878655418784733982303233503462500531545062832660 (= 0x693f4671 6eb6bc24 88762037 56c9c762 4bea7373 6ca39840 87789c1e 05a0c2d7 3ad3ff1c e67c39c4 fdbd132c 4ed7c8ad 9808795b f230fa14)

The curve Edwards448 is \(4\)-isogenous to both the curves E448 and Curve448. See Appendix B.4 for details.

The elliptic curve E448 is the Edwards curve \(E_{a,d}\) defined over the prime field \(\mathrm{GF}(p)\) with \(p = 2^{448}-2^{224}-1\) and parameters \(a = 1\) and \(d = 39082/39081\). This curve has order \(h \cdot n\), where \(h = 4\), and \(n\) is a prime number. For this curve, \(a\) is a square in \(\mathrm{GF}(p)\), whereas \(d\) is not. The quadratic twist of this curve has order \(h_1 \cdot n_1\), where \(h_1 = 4\), and \(n_1\) is a prime number. This curve has domain parameters \(D = (p, h, n, \mathit{Type}, a, d, G)\), where the \(\mathit{Type}\) is a “twisted Edwards curve,” and the other parameters are defined as follows:

\(p\): \(2^{448}-2^{224}-1\) (=0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff)

\(h\): \(4\)
\(n\): 181709681073901722637330951972001133588410340171829515070372549795146003961539585716195755291692375963310293709091662304773755859649779 (= \(2^{446} -\) 0x8335dc16 3bb124b6 5129c96f de933d8d 723a70aa dc873d6d 54a7bb0d)

\(\mathit{tr}\): 28312320572429821613362531907042076847709625476988141958474579766324 (= \((p+1) - h \cdot n\) = 0x1 0cd77058 eec492d9 44a725bf 7a4cf635 c8e9c2ab 721cf5b5 529eec34)

\(a\): \(1\)
\(d\): \(39082/39081\) = 611975850744529176160423220965553317543219696871016626328968936415087860042636474891785599283666020414768678979989378147065462815545017 (= 0xd78b4bdc 7f0daf19 f24f38c2 9373a2cc ad461572 42a50f37 809b1da3 412a12e7 9ccc9c81 264cfe9a d0809970 58fb61c4 243cc32d baa156b9)

\(G_x\): 3453974930397295163740086041505374102666552600751832902164069702816\
45695073672344430481787759340633221708391583424041788924124567700732 (\(=\)0x79a70b2b 70400553 ae7c9df4 16c792c6 1128751a c9296924 0c25a07d 728bdc93 e21f7787 ed697224 9de732f3 8496cd11 69871309 3e9c04fc)

\(G_y\): \(3/2\) = 3634193621478034452746619039440022671768206803436590301407450995903\ 06164083365386343198191849338272965044442230921818680526749009182721 (=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 80000000 00000000 00000000 00000000 00000000 00000000 00000001)

This section specifies elliptic curves over binary fields where each curve takes the form of a curve in short-Weierstrass form and is either a Koblitz curve (Section 3.3.1) or a pseudorandom curve (Section 3.3.2). Due to their limited adoption, elliptic curves over binary fields (i.e., all of the curves specified in Section 3.3) are deprecated and may be removed from a subsequent revision to these guidelines to facilitate interoperability and simplify elliptic curve standards and implementations. New implementations should select an appropriate elliptic curve over a prime field from Section 3.2. Here, the domain parameters \(a\) and \(b\) for Koblitz curves are elements of the base field \(\mathrm{GF}(2)\) (i.e., \(b = 1\) and \(a = 0\) or \(a = 1\)), whereas for pseudorandom curves, \(a = 1\) and \(b\) is a non-zero element of \(\mathrm{GF}(2^m)\). For each field degree \(m\), a pseudorandom curve is given along with a Koblitz curve. The pseudorandom curve has the form

where \(a = 0\) or 1. For each pseudorandom curve, the cofactor is \(h = 2\). The cofactor of each Koblitz curve is \(h = 2\) if \(a = 1\), and \(h = 4\) if \(a = 0\). The coefficients of the pseudorandom curves and the coordinates of the base points of both kinds of curves are given in terms of both the polynomial and normal basis representations discussed in Section 3.1.3. For each \(m\), the following parameters are given: Field Representation:

• The normal basis type \(T\)

• The field polynomial (a trinomial or pentanomial) \(f(z)\)

• The coefficient \(a\)

• The base point order \(n\)

• The base point \(x\) coordinate \(G_x\)

• The base point \(y\) coordinate \(G_y\)

• The base point order \(n\)

• The coefficient \(b\)

• The base point \(x\) coordinate \(G_x\)

• The base point \(y\) coordinate \(G_y\)

• The 160-bit input \(\mathit{Seed}\) to the SHA-1 based algorithm (i.e., the domain parameter seed)

• The coefficient \(b\) (i.e., the output of the SHA-1 based algorithm)

• The base point \(x\) coordinate \(G_x\)

• The base point \(y\) coordinate \(G_y\)

Integers (such as \(T\), \(m\), and \(n\)) are given in decimal form. Bit strings and field elements are given in hexadecimal.

The elliptic curve K-233 is a Weierstrass curve \(B_{a,b}\) defined over the binary field \(\mathrm{GF}(2^m)\) with \(m = 233\) and parameters \(a = 0\) and \(b = 1\). This curve has order \(h \cdot n\), where \(h = 4\), and \(n\) is a prime number. This curve has domain parameters \(D = (m, f(z), T, h, n, \mathit{Type}, a, b, G, \{\mathit{Seed}, c\})\), where the \(\mathit{Type}\) is “Koblitz curve,” and the other parameters are defined as follows:

\(T\): 2

\(f(z)\): \(z^{233} + z^{74} + 1\)
\(h\): 4
\(n\): 345087317339528189371737793113851276057094098886225212\ 6328087024741343 (= 0x80 00000000 00000000 00000000 00069d5b b915bcd4 6efb1ad5 f173abdf)

\(\mathit{tr}\): −137381546011108235394987299651366779 (=\((2^m+1) - h \cdot n\) = −0x1a756e e456f351 bbec6b57 c5ceaf7b)

\(a\): 0 (=0x000 00000000 00000000 00000000 00000000 00000000 00000000 00000000)

\(b\): 1 (=0x000 00000000 00000000 00000000 00000000 00000000 00000000 00000001)

\(G_x\): 0x172 32ba853a 7e731af1 29f22ff4 149563a4 19c26bf5 0a4c9d6e efad6126

\(G_y\): 0x1db 537dece8 19b7f70f 555a67c4 27a8cd9b f18aeb9b 56e0c110 56fae6a3
Normal basis:

\(G_x\): 0x0fd e76d9dcd 26e643ac 26f1aa90 1aa12978 4b71fc07 22b2d056 14d650b3

\(G_y\): 0x064 3e317633 155c9e04 47ba8020 a3c43177 450ee036 d6335014 34cac978

\(\mathit{Seed}\): n/a (binary Koblitz curve)

The elliptic curve K-283 is a Weierstrass curve \(B_{a,b}\) defined over the binary field \(\mathrm{GF}(2^m)\) with \(m = 283\) and parameters \(a = 0\) and \(b = 1\). This curve has order \(h \cdot n\), where \(h = 4\), and \(n\) is a prime number. This curve has domain parameters \(D = (m, f(z), T, h, n, \mathit{Type}, a, b, G, \{\mathit{Seed}, c\})\), where the \(\mathit{Type}\) is “Koblitz curve,” and the other parameters are defined as follows:

\(T\): 6

\(f(z)\): \(z^{283} + z^{12} + z^7 + z^5 + 1\)
\(h\): 4
\(n\): 3885337784451458141838923813647037813284811733793061324295874997529815829704422603873 (=0x1ffffff ffffffff ffffffff ffffffff ffffe9ae 2ed07577 265dff7f 94451e06 1e163c61)

\(\mathit{tr}\): 7777244870872830999287791970962823977569917 (=\((2^m+1) - h \cdot n\) = 0x5947 44be2a23 66880201 aeeb87e7 87a70e7d)

\(a\): 0 (=0x0000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000)

\(b\): 1 (=0x0000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001)

\(G_x\): 0x503213f 78ca4488 3f1a3b81 62f188e5 53cd265f 23c1567a 16876913 b0c2ac24 58492836

\(G_y\): 0x1ccda38 0f1c9e31 8d90f95d 07e5426f e87e45c0 e8184698 e4596236 4e341161 77dd2259

\(G_x\): 0x3ab9593 f8db09fc 188f1d7c 4ac9fcc3 e57fcd3b db15024b 212c7022 9de5fcd9 2eb0ea60

\(G_y\): 0x2118c47 55e7345c d8f603ef 93b98b10 6fe8854f feb9a3b3 04634cc8 3a0e759f 0c2686b1

\(\mathit{Seed}\): n/a (binary Koblitz curve)

The elliptic curve K-409 is a Weierstrass curve \(B_{a,b}\) defined over the binary field \(\mathrm{GF}(2^m)\) with \(m = 409\) and parameters \(a = 0\) and \(b = 1\). This curve has order \(h \cdot n\), where \(h = 4\), and \(n\) is a prime number. This curve has domain parameters \(D = (m, f(z), T, h, n, \mathit{Type}, a, b, G, \{\mathit{Seed}, c\})\), where the \(\mathit{Type}\) is “Koblitz curve,” and the other parameters are defined as follows:

\(T\): 4

\(f(z)\): \(z^{409} + z^{87} + 1\)
\(h\): 4
\(n\): 330527984395124299475957654016385519914202341482140609642324395022880711289249191050673258457777458014096366590617731358671
(\(=\) 0x7fffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffe5f 83b2d4ea 20400ec4 557d5ed3 e3e7ca5b 4b5c83b8 e01e5fcf)

\(\mathit{tr}\): 10457288737315625927447685387048320737638796957687575791173829
(\(= (2^m + 1) - h \cdot n =\) 0x681 f134ac57 7effc4ee aa0a84b0 7060d692 d28df11c 7f8680c5)

\(a\): 0
(\(=\) 0x0000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000)

\(b\): 1
(\(=\) 0x0000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001)

\(G_x\): 0x060f05f 658f49c1 ad3ab189 0f718421 0efd0987 e307c84c 27accfb8 f9f67cc2 c460189e b5aaaa62 ee222eb1 b35540cf e9023746

\(G_y\): 0x1e36905 0b7c4e42 acba1dac bf04299c 3460782f 918ea427 e6325165 e9ea10e3 da5f6c42 e9c55215 aa9ca27a 5863ec48 d8e0286b

\(G_x\): 0x1b559c7 cba2422e 3affe133 43e808b5 5e012d72 6ca0b7e6 a63aeafb c1e3a98e 10ca0fcf 98350c3b 7f89a975 4a8e1dc0 713cec4a

\(G_y\): 0x16d8c42 052f07e7 713e7490 eff318ba 1abd6fef 8a5433c8 94b24f5c 817aeb79 852496fb ee803a47 bc8a2038 78ebf1c4 99afd7d6

\(\mathit{Seed}\): n/a (binary Koblitz curve)

The elliptic curve K-571 is a Weierstrass curve \(B_{a,b}\) defined over the binary field \(\mathrm{GF}(2^m)\) with \(m = 571\) and parameters \(a = 0\) and \(b = 1\). This curve has order \(h \cdot n\), where \(h = 4\), and \(n\) is a prime number. This curve has domain parameters \(D = (m, f(z), T, h, n, \mathit{Type}, a, b, G, \{\mathit{Seed}, c\})\), where the \(\mathit{Type}\) is “Koblitz curve,” and the other parameters are defined as follows:

\(T\): 10

\(f(z)\): \(z^{571} + z^{10} + z^5 + z^2 + 1\)
\(h\): 4
\(n\): 1932268761508629172347675945465993672149463664853217499328617625725759571144780212268133978522706711834706712800825351461273674974066617311929682421617092503555733685276673 (= 0x2000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 131850e1 f19a63e4 b391a8db 917f4138 b630d84b e5d63938 1e91deb4 5cfe778f 637c1001)

\(\mathit{tr}\): −148380926981691413899619140297051490364542574180493936232912339534208516828973111459843 (\(= (2^m + 1) - h \cdot n =\) -0x4c614387 c6698f92 ce46a36e 45fd04e2 d8c3612f 9758e4e0 7a477ad1 73f9de3d 8df04003)

\(a\): 0 (= 0x0000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000) 00000000 00000000 00000000 00000000 00000000)

\(b\): 1 (= 0x0000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000) 00000000 00000000 00000000 00000000 00000001)

\(G_x\): 0x26eb7a8 59923fbc 82189631 f8103fe4 ac9ca297 0012d5d4 60248048 01841ca4 43709584 93b205e6 47da304d b4ceb08c bbd1ba39 494776fb 988b4717 4dca88c7 e2945283 a01c8972

\(G_y\): 0x349dc80 7f4fbf37 4f4aeade 3bca9531 4dd58cec 9f307a54 ffc61efc 006d8a2c 9d4979c0 ac44aea7 4fbebbb9 f772aedc b620b01a 7ba7af1b 320430c8 591984f6 01cd4c14 3ef1c7a3

\(G_x\): 0x04bb2db a418d0db 107adae0 03427e5d 7cc139ac b465e593 4f0bea2a b2f3622b c29b3d5b 9aa7a1fd fd5d8be6 6057c100 8e71e484 bcd98f22 bf847642 37673674 29ef2ec5 bc3ebcf7

\(G_y\): 0x44cbb57 de20788d 2c952d7b 56cf39bd 3e89b189 84bd124e 751ceff4 369dd8da c6a59e6e 745df44d 8220ce22 aa2c852c fcbbef49 ebaa98bd 2483e331 80e04286 feaa2530 50caff60

\(\mathit{Seed}\): n/a (binary Koblitz curve)

The elliptic curve B-233 is a Weierstrass curve \(B_{a,b}\) defined over the binary field \(\mathrm{GF}(2^m)\) with \(m = 233\) and parameter \(a = 1\). This curve has order \(h \cdot n\), where \(h = 2\), and \(n\) is a prime number. This curve has domain parameters \(D = (m, f(z), T, h, n, \mathit{Type}, a, b, G, \{\mathit{Seed}, c\})\), where the \(\mathit{Type}\) is “Weierstrass curve,” and the other parameters are defined as follows:

\(T\): 2

\(f(z)\): \(z^{233} + z^{74} + 1\)
\(h\): 2
\(n\): 6901746346790563787434755862277025555839812737345013555379383634485463 (= 0x100 00000000 00000000 00000000 0013e974 e72f8a69 22031d26 03cfe0d7)

\(\mathit{tr}\): −206777407530349254000433718821372333 (\(= (2^m + 1) - h \cdot n =\) −0x27d2e9 ce5f14d2 44063a4c 079fc1ad)

\(a\): 1 (= 0x000 00000000 00000000 00000000 00000000 00000000 00000000 00000001)

Polynomial basis:
\(b\): 0x066 647ede6c 332c7f8c 0923bb58 213b333b 20e9ce42 81fe115f 7d8f90ad

\(G_x\): 0x0fa c9dfcbac 8313bb21 39f1bb75 5fef65bc 391f8b36 f8f8eb73 71fd558b

\(G_y\): 0x100 6a08a419 03350678 e58528be bf8a0bef f867a7ca 36716f7e 01f81052
Normal basis:
\(b\): 0x1a0 03e0962d 4f9a8e40 7c904a95 38163adb 82521260 0c7752ad 52233279

\(G_x\): 0x18b 863524b3 cdfefb94 f2784e0b 116faac5 4404bc91 62a363ba b84a14c5

\(G_y\): 0x049 25df77bd 8b8ff1a5 ff519417 822bfedf 2bbd7526 44292c98 c7af6e02

\(\mathit{Seed}\): 0x74d59ff0 7f6b413d 0ea14b34 4b20a2db 049b50c3

The elliptic curve B-283 is a Weierstrass curve \(B_{a,b}\) defined over the binary field \(\mathrm{GF}(2^m)\) with \(m = 283\) and parameter \(a = 1\). This curve has order \(h \cdot n\), where \(h = 2\), and \(n\) is a prime number. This curve has domain parameters \(D = (m, f(z), T, h, n, \mathit{Type}, a, b, G, \{\mathit{Seed}, c\})\), where the \(\mathit{Type}\) is “Weierstrass curve,” and the other parameters are defined as follows:

\(T\): 6

\(f(z)\): \(z^{283} + z^{12} + z^7 + z^5 + 1\)
\(h\): 2
\(n\): 7770675568902916283677847627294075626569625924376904889109196526770044277787378692871 (= 0x3ffffff ffffffff ffffffff ffffffff ffffef90 399660fc 938a9016 5b042a7c efadb307)

\(\mathit{tr}\): 2863663306391796106224371145726066910599667 (\(= (2^m + 1) - h \cdot n =\) 0x 20df8cd33e06d8eadfd349f7ab0620a499f3)

\(a\): 1 (= 0x0000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001)

Polynomial basis:
\(b\): 0x27b680a c8b8596d a5a4af8a 19a0303f ca97fd76 45309fa2 a581485a f6263e31 3b79a2f5

\(G_x\): 0x5f93925 8db7dd90 e1934f8c 70b0dfec 2eed25b8 557eac9c 80e2e198 f8cdbecd 0x86b12053

\(G_y\): 0x3676854 fe24141c b98fe6d4 b20d02b4 516ff702 350eddb0 826779c8 13f0df45 be8112f4
Normal basis:
\(b\): 0x157261b 894739fb 5a13503f 55f0b3f1 0c560116 66331022 01138cc1 80c0206b dafbc951

\(G_x\): 0x749468e 464ee468 634b21f7 f61cb700 701817e6 bc36a236 4cb8906e 940948ea a463c35d

\(G_y\): 0x62968bd 3b489ac5 c9b859da 68475c31 5bafcdc4 ccd0dc90 5b70f624 46f49c05 2f49c08c
\(\mathit{Seed}\): 0x77e2b073 70eb0f83 2a6dd5b6 2dfc88cd 06bb84be

The elliptic curve B-409 is a Weierstrass curve \(B_{a,b}\) defined over the binary field \(\mathrm{GF}(2^m)\) with \(m = 409\) and parameter \(a = 1\). This curve has order \(h \cdot n\), where \(h = 2\), and \(n\) is a prime number. This curve has domain parameters \(D = (m, f(z), T, h, n, \mathit{Type}, a, b, G, \{\mathit{Seed}, c\})\), where the \(\mathit{Type}\) is “Weierstrass curve,” and the other parameters are defined as follows:

\(T\): 4

\(f(z)\): \(z^{409} + z^{87} + 1\)
\(h\): 2
\(n\): 661055968790248598951915308032771039828404682964281219284648798304157774827374805208143723762179110965979867288366567526771 (= 0x1000000 00000000 00000000 00000000 00000000 00000000 000001e2 aad6a612 f33307be 5fa47c3c 9e052f83 8164cd37 d9a21173)

\(\mathit{tr}\): -6059503967182126918765909026644927652236777310526686418445029 (\(= (2^m + 1) - h \cdot n =\) -0x3c5 55ad4c25 e6660f7c bf48f879 3c0a5f07 02c99a6f b34422e5)

\(a\): 1 (\(=\) 0x0000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001)

Polynomial basis:
\(b\): 0x021a5c2 c8ee9feb 5c4b9a75 3b7b476b 7fd6422e f1f3dd67 4761fa99 d6ac27c8 a9a197b2 72822f6c d57a55aa 4f50ae31 7b13545f

\(G_x\): 0x15d4860 d088ddb3 496b0c60 64756260 441cde4a f1771d4d b01ffe5b 34e59703 dc255a86 8a118051 5603aeab 60794e54 bb7996a7

\(G_y\): 0x061b1cf ab6be5f3 2bbfa783 24ed106a 7636b9c5 a7bd198d 0158aa4f 5488d08f 38514f1f df4b4f40 d2181b36 81c364ba 0273c706

Normal basis:
\(b\): 0x124d065 1c3d3772 f7f5a1fe 6e715559 e2129bdf a04d52f7 b6ac7c53 2cf0ed06 f610072d 88ad2fdc c50c6fde 72843670 f8b3742a

\(G_x\): 0x0ceacbc 9f475767 d8e69f3b 5dfab398 13685262 bcacf22b 84c7b6dd 981899e7 318c96f0 761f77c6 02c016ce d7c548de 830d708f

\(G_y\): 0x199d64b a8f089c6 db0e0b61 e80bb959 34afd0ca f2e8be76 d1c5e9af fc7476df 49142691 ad303902 88aa09bc c59c1573 aa3c009a

\(\mathit{Seed}\): 0x4099b5a4 57f9d69f 79213d09 4c4bcd4d 4262210b

The elliptic curve B-571 is a Weierstrass curve \(B_{a,b}\) defined over the binary field \(\mathrm{GF}(2^m)\) with \(m = 571\) and parameter \(a = 1\). This curve has order \(h \cdot n\), where \(h = 2\), and \(n\) is a prime number. This curve has domain parameters \(D = (m, f(z), T, h, n, \mathit{Type}, a, b, G, \{\mathit{Seed}, c\})\), where the \(\mathit{Type}\) is “Weierstrass curve,” and the other parameters are defined as follows:

\(T\): 10

\(f(z)\): \(z^{571} + z^{10} + z^5 + z^2 + 1\)
\(h\): 2
\(n\): 386453752301725834469535189093198734429892732970643499865\ 723525145151914228956042453614399938941577308313388112192\ 6944486246872462816813070234528288303332411393191105285703
(= 0x3fffff ffffffff ffffffff fffffffff ffffffff ffffffff ffffffff ffffffff ffffffff e661ce18 ff559873 08059b18 6823851e c7dd9ca1 161de93d 5174d66e 8382e9bb 2fe84e47)

\(\mathit{tr}\): 9953438501360975865946981915046538223641239\
6452349171016760770327496674607579419075443
(=\((2^m+1) - h \cdot n\) = 0x333c63ce 0154cf19 eff4c9cf 2fb8f5c2 7044c6bd d3c42d85 5d165322 f8fa2c89 a02f6373)

\(a\): 1 (= 0x0000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001)

Polynomial basis:
\(b\): 0x2f40e7e 2221f295 de297117 b7f3d62f 5c6a97ff cb8ceff1 cd6ba8ce 4a9a18ad 84ffabbd 8efa5933 2be7ad67 56a66e29 4afd185a 78ff12aa 520e4de7 39baca0c 7ffeff7f 2955727a

\(G_x\): 0x303001d 34b85629 6c16c0d4 0d3cd775 0a93d1d2 955fa80a a5f40fc8 db7b2abd bde53950 f4c0d293 cdd711a3 5b67fb14 99ae6003 8614f139 4abfa3b4 c850d927 e1e7769c 8eec2d19

\(G_y\): 0x37bf273 42da639b 6dccfffe b73d69d7 8c6c27a6 009cbbca 1980f853 3921e8a6 84423e43 bab08a57 6291af8f 461bb2a8 b3531d2f 0485c19b 16e2f151 6e23dd3c 1a4827af 1b8ac15b

Normal basis:
\(b\): 0x3762d0d 47116006 179da356 88eeaccf 591a5cde a7500011 8d9608c5 9132d434 26101a1d fb377411 5f586623 f75f0000 1ce61198 3c1275fa 31f5bc9f 4be1a0f4 67f01ca8 85c74777

\(G_x\): 0x0735e03 5def5925 cc33173e b2a8ce77 67522b46 6d278b65 0a291612 7dfea9d2 d361089f 0a7a0247 a184e1c7 0d417866 e0fe0feb 0ff8f2f3 f9176418 f97d117e 624e2015 df1662a8

\(G_y\): 0x04a3642 0572616c df7e606f ccadaecf c3b76dab 0eb1248d d03fbdfc 9cd3242c 4726be57 9855e812 de7ec5c5 00b4576a 24628048 b6a72d88 0062eed0 dd34b109 6d3acbb6 b01a4a97

\(\mathit{Seed}\): 0x2aa058f7 3a0e33ab 486b0f61 0410c53a 7f132310

For each point \(P\) on the Weierstrass curve \(W_{a,b}\), the point at infinity \(\varnothing\) serves as the identity element (i.e., \(P + \varnothing = \varnothing + P = P\)).

For each point \(P = (x, y)\) on the Weierstrass curve \(W_{a,b}\), the point \(-P\) is the point \((x, -y)\), and one has \(P + (-P) = \varnothing\).

Let \(P_1 = (x_1, y_1)\) and \(P_2 = (x_2, y_2)\) be points on the Weierstrass curve \(W_{a,b}\), where \(P_1 \ne \pm P_2\), and let \(Q = P_1 + P_2\). Then \(Q = (x, y)\), where

Let \(P = (x_1, y_1)\) be a point on the Weierstrass curve \(W_{a,b}\), where \(P \ne -P\), and let \(Q = 2P\). Then \(Q = (x, y)\), where

For each point \(P\) on the Montgomery curve \(M_{A,B}\), the point at infinity \(\varnothing\) serves as the identity element (i.e., \(P + \varnothing = \varnothing + P = P\)).

For each point \(P = (u, v)\) on the Montgomery curve \(M_{A,B}\), the point \(-P\) is the point \((u, -v)\), and one has \(P + (-P) = \varnothing\).

Let \(P_1 = (u_1, v_1)\) and \(P_2 = (u_2, v_2)\) be points on the Montgomery curve \(M_{A,B}\), where \(P_1 \ne \pm P_2\), and let \(Q = P_1 + P_2\). Then \(Q = (u, v)\), where

Let \(P = (u_1, v_1)\) be a point on the Montgomery curve \(M_{A,B}\), where \(P \ne -P\), and let \(Q = 2P\). Then \(Q = (u, v)\), where

Let \(P_1 = (x_1, y_1)\) and \(P_2 = (x_2, y_2)\) be points on the twisted Edwards curve \(E_{a,d}\), and let \(Q = P_1 + P_2\). Then \(Q = (x, y)\), where

For the twisted Edwards curves specified in this Recommendation, the domain parameter \(a\) is always a square in \(\mathrm{GF}(q)\), whereas \(d\) is not. In this case, the addition formula above is defined for each pair of points. In particular, for each point \(P = (x_1, y_1)\) on the twisted Edwards curve \(E_{a,d}\), point doubling yields the point \(Q = 2P\), where \(Q = (x, y)\) and

Note that \((0, 1)\) is the identity element since for each point \(P = (x, y)\) on the twisted Edwards curve \(E_{a,d}\), one has \(P + (0, 1) = (x, y) + (0, 1) = (x, y) = P\).

For each point \(P = (x, y)\) on the twisted Edwards curve \(E_{\mathrm{A,B}}\), the inverse point \(-P\) is the point \((-x, y)\), and one has \(P + (-P) = (0, 1)\). The point \((0, -1)\) has order 2.

For each point \(P\) on the Weierstrass curve \(B_{a,b}\), the point at infinity \(\varnothing\) serves as the identity element (i.e., \(P + \varnothing = \varnothing + P = P\)).

For each point \(P = (x, y)\) on the Weierstrass curve \(B_{a,b}\), the point \(-P\) is the point \((x, x + y)\), and one has \(P + (-P) = \varnothing\).

Let \(P_1 = (x_1, y_1)\) and \(P_2 = (x_2, y_2)\) be points on the Weierstrass curve \(B_{a,b}\), where \(P_1 \ne \pm P_2\), and let \(Q = P_1 + P_2\). Then, \(Q = (x, y)\), where

Let \(P = (x_1, y_1)\) be a point on the Weierstrass curve \(B_{a,b}\), where \(P \ne -P\), and let \(Q = 2P\). Then, \(Q = (x, y)\), where

The non-binary curves specified in this Recommendation are expressed in different curve models defined over the same field \(\mathrm{GF}(q)\) – namely as curves in short-Weierstrass form, as Montgomery curves, or as twisted Edwards curves. These curve models are related as follows.

One can map points on the Montgomery curve \(M_{A,B}\) to points on the twisted Edwards curve \(E_{a,d}\), where \(a = (A+2)/B\) and \(d = (A-2)/B\) and, conversely, map points on the twisted Edwards curve \(E_{a,d}\) to points on the Montgomery curve \(M_{A,B}\), where \(A = 2(a+d)/(a-d)\) and \(B = 4/(a-d)\). Here, it is assumed that \(a \ne 0, d \ne 0, A \ne -2, 2\), and \(B \ne 0\). For the curves in this specification, this

defines a birational equivalence between \(M_{A,B}\) and \(E_{a,d}\), thereby showing that the discrete logarithm problem in either curve model is equally hard.

For the Montgomery curves and twisted Edwards curves in this specification, the mapping from \(M_{A,B}\) to \(E_{a,d}\) is defined by mapping the point at infinity \(\varnothing\) and the point \((0, 0)\) of order two on \(M_{A,B}\) to the point \((0, 1)\) and the point \((0, -1)\), respectively, of order two on \(E_{a,d}\), while mapping every other point \((u, v)\) on \(M_{A,B}\) to the point \((x, y) = \left(\frac{u}{v}, \frac{u-1}{u+1}\right)\) on \(E_{a,d}\). The inverse mapping from \(E_{a,d}\) to \(M_{A,B}\) is defined by mapping the point \((0, 1)\) and the point \((0, -1)\) of order two on \(E_{a,d}\) to the point at infinity \(\varnothing\) and the point \((0, 0)\), respectively, of order two on \(M_{A,B}\), while every other point \((x, y)\) on \(E_{a,d}\) is mapped to the point \((u, v) = \left(\frac{1+y}{1-y}, \frac{1+y}{(1-y)x}\right)\) on \(M_{A,B}\).

Specifically, for the curves defined in Section 3, the following is true:

Using the above maps, the base point of Curve25519 corresponds to the base point of Edwards25519. For points \((u, v) \ne \varnothing, (0,0)\) on Curve25519, the image under the mapping corresponds to the point \(\left(\alpha \frac{u}{v}, \frac{u-1}{u+1}\right)\) on Edwards25519. Here \(\alpha\) is the element of \(\mathrm{GF}(p)\) defined by:

\(\alpha\): 51042569399160536130206135233146329284152202253034631822681833788666877215207
(= 0x70d9120b 9f5ff944 2d84f723 fc03b081 3a5e2c2e b482e57d 3391fb55 00ba81e7).

The inverse mapping from Edwards25519 to Curve25519 maps points \((x,y)\) (other than the points \((0, 1)\) and \((0, -1)\)) to \(\left(\frac{1+y}{1-y}, \alpha\frac{1+y}{(1-y)x}\right)\).

Similarly, the base point of Curve448 corresponds to the base point of E448. Every other point \((u, v) \ne \varnothing, (0,0)\) on Curve448 corresponds to the point \(\left(\alpha \frac{u}{v}, \frac{u+1}{u-1}\right)\) on E448, where \(\alpha\) is the element of \(\mathrm{GF}(p)\) defined by:

\(\alpha\): 197888467295464439538354009753858038256835152591059802148199779196087404232002515713604263127793030747855424464185691766453844835192428
(= 0x45b2c5f7 d649eed0 77ed1ae4 5f44d541 43e34f71 4b71aa96 c945af01 2d182975 0734cde9 faddbda4 c066f7ed 54419ca5 2c85de1e 8aae4e6c)

For points that are not the point at infinity \(\varnothing\) and the point \((0,0)\) of order two, the inverse mapping from E448 to Curve448 sends \((x, y)\) to the point \(\left(\frac{y+1}{y-1}, \alpha\frac{y+1}{(y-1)x}\right)\).

One can map points on the Montgomery curve \(M_{A,B}\) to points on the Weierstrass curve \(W_{a,b}\), where \(a = \frac{3-A^2}{3B^2}\) and \(b = \frac{2A^3-9A}{27B^3}\). For the curves in this specification, this defines a one-to-one correspondence, which is an isomorphism between \(M_{A,B}\) and \(W_{a,b}\), thereby showing that the discrete logarithm problem in either curve model is equally hard.

For the Montgomery curves in this specification, the mapping from \(M_{A,B}\) to \(W_{a,b}\) is defined by mapping the point at infinity \(\varnothing\) on \(M_{A,B}\) to the point at infinity \(\varnothing\) on \(W_{a,b}\), while mapping every other point \((u, v)\) on \(M_{A,B}\) to the point \((x, y) = \left(\frac{u}{B}+\frac{A}{3B}, \frac{v}{B}\right)\) on \(W_{a,b}\).

Note that not all Weierstrass curves can be mapped to Montgomery curves since the latter have a point of order two and the former may not. In particular, if a Weierstrass curve has prime order – as with the curves P-224, P-256, P-384, and P-521 specified in this Recommendation – this mapping is not defined.

This mapping can be used to implement elliptic curve group operations that were originally defined for a twisted Edwards curve or for a Montgomery curve using group operations on the corresponding elliptic curve in short-Weierstrass form and translating the result back to the original curve to potentially allow for code reuse.

Note that implementations for elliptic curves with short-Weierstrass form that hard-code the domain parameter \(a\) to \(a = -3\) cannot always be used this way since the curve \(W_{a,b}\) may not always be expressed in terms of a Weierstrass curve with \(a = -3\) via a coordinate transformation. This is, unfortunately, the case with the Montgomery curves and twisted Edwards curves specified in this Recommendation.

Specifically, for the curves in Section 3, the following is true:

The curve W-25519 is isomorphic to Curve25519, where the base point of Curve25519 corresponds to the base point of W-25519, the point at infinity \(\varnothing\) of Curve25519 corresponds to the point at infinity \(\varnothing\) on W-25519, and the point \((u, v)\) on Curve25519 corresponds to the point \((x, y) = (u+\mathrm{A}/3, v)\) on \(W_{a,b}\). Note that Curve25519 is not isomorphic with a Weierstrass curve with domain parameter \(a = -3\), although it is isogenous to such a Weierstrass curve (see [IETF_draft_Struik]).

The curve W-448 is isomorphic to Curve448, where the base point of Curve448 corresponds to the base point of W-448, the point at infinity \(\varnothing\) of Curve448 corresponds to the point at infinity \(\varnothing\) on W-448, and the point \((u, v)\) on Curve448 corresponds to the point \((x, y) = (u+\mathrm{A}/3, v)\) on \(W_{a,b}\). Note that Curve448 is not isomorphic with a Weierstrass curve with domain parameter \(a = -3\). In particular, this means that one cannot reuse an implementation for curves with short-Weierstrass form that hardcodes the domain parameter \(a\) to \(-3\) to implement Curve448.

The curve Edwards448 (Section 3.2.3.2) is 4-isogenous to the curve E448 (Section 3.2.3.3), where the base point of Edwards448 corresponds to the base point of E448 and where the identity element \((0, 1)\) and the point \((0, -1)\) of order two of Edwards448 correspond to the identity element \((0, 1)\) on E448. Every other point \((x, y)\) on Edwards448 corresponds to the point on E448, where \(\alpha\) is the element of \(\mathrm{GF}(p)\) defined in Section 3.2.2.2:

1. Underlying finite field. The underlying finite field \(\mathrm{GF}(q)\) shall be either a prime field or \(q = 2^m\), where \(m\) is a prime number.

2. Curve order. Each curve \(E\) defined over the finite field \(\mathrm{GF}(q)\) shall have order \(|E| = h \cdot n\), where \(n\) is a large prime number, \(h\) is co-prime with \(n\), and \(h\) is small (\(h\) is called the cofactor of \(E\)). Each curve shall have cofactor \(h \le 2^{10}\).

3. Base point. Each curve \(E\) shall have a fixed base point \(G\) of prime order \(n\).

4. Avoiding anomalous curve attack. Each curve \(E\) defined over the finite field \(\mathrm{GF}(q)\) shall have order \(|E| \ne q\) so as to avoid attacks using additive transfers.

5. Large embedding degree. The elliptic curve discrete logarithm problem in \(E\) can be converted to an ordinary discrete logarithm problem defined over the finite field \(\mathrm{GF}(q^k)\), where \(k\) is the smallest positive integer so that \(q^k \equiv 1 \bmod n\), called the embedding degree. Each curve shall have embedding degrees \(k \ge 2^{10}\). All of the elliptic curves specified in this document have much larger embedding degrees that are close to the order \(n\) (which is typical for elliptic curves).

6. Endomorphism field. For each curve \(E\) over \(\mathrm{GF}(q)\) with trace \(t\), the (negative) number \(\mathit{Disc} = t^2 - 4q\) is closely related to the discriminant of the endomorphism field of \(E\). As of the publication of this document, there is no technical rationale for imposing a large lower bound on the square-free part of \(|\mathit{Disc}|\), although this value is often large except for curves used in pairing-based cryptography. This Recommendation does not impose restrictions on the value of the square-free part of \(|\mathit{Disc}|\).

Each of the curves P-224 (Section 3.2.1.2), P-256 (Section 3.2.1.3), P-384 (Section 3.2.1.4), and P-521 (Section 3.2.1.5) is a curve \(W_{a,b}\) in short-Weierstrass form with prime order (and, thus, cofactor \(h = 1\)). Each curve is defined over a prime field \(\mathrm{GF}(p)\) where the prime number is of a special form to allow efficient modular reduction (see Appendix G.1).
The NIST prime curves were generated using the procedure in Appendix C.3.1 with \(\mathit{hdigest} = 160\) and SHA-1 hash function.

1. The parameter \(a\) was set to \(a \equiv -3 \bmod p\), which allows for optimizations of the group law if implemented via projective coordinates in Weierstrass form.

2. The parameter \(b\) was derived in a hard-to-invert way using the procedure in Appendix C.3.1 from a pseudorandom \(\mathit{Seed}\) value so that the following conditions were satisfied simultaneously:
a. \(4a^3 + 27b^2 \ne 0\) in \(\mathrm{GF}(p)\);

b. The curve has prime order \(n\), which implies that \(h = 1\); and
c. The curve satisfies the cryptographic criteria in Appendix C.1.

3. Select a base point \(G = (G_x, G_y)\) of order \(n\).

Curve25519 was specified in IETF 7748 by the Crypto Forum Research Group (CFRG). This curve is a Montgomery curve \(M_{\mathrm{A},\mathrm{B}}\) defined over the field \(\mathrm{GF}(p)\), where \(p = 2^{255}-19\), the curve has cofactor \(h = 8\), and the quadratic twist \(E_1\) has cofactor \(h_1 = 4\). The prime number is of a special form to allow efficient modular reduction and finite field operations that try and minimize carry effects of operands. The curve parameters \(\mathrm{A}\) and \(\mathrm{B}\) are:

1. The parameter \(\mathrm{B}\) was set to \(\mathrm{B} = 1\).

2. The parameter \(\mathrm{A}\) was selected as the minimum value of \(|\mathrm{A}|\) so that the following conditions were satisfied simultaneously:
a. The group is cyclic, which implies that \(\mathrm{A}^2-4\) is not a square in \(\mathrm{GF}(p)\);

b. The curve has cofactor \(h = 8\), which implies that \(\mathrm{A}+2\) is a square in \(\mathrm{GF}(p)\);
c. The quadratic twist has cofactor \(h_1 = 4\);
d. \(\mathrm{A}\) has the form \(\mathrm{A} \equiv 2 \bmod 4\), which allows optimized implementations of the group law using the Montgomery ladder; and
e. The curve and the quadratic twist both satisfy the cryptographic criteria in Appendix C.1.

3. Select the base point \(G = (G_x, G_y)\) of order \(n\), where \(|G_x|\) is minimal, and \(G_y\) is even.

1. The parameter \(\mathrm{B}\) was set to \(\mathrm{B} = 1\).

2. The parameter \(\mathrm{A}\) was selected as the minimum value of \(|\mathrm{A}|\) so that the following conditions were satisfied simultaneously:
a. The group is cyclic, which implies that \(\mathrm{A}^2 - 4\) is not a square in \(\mathrm{GF}(p)\);

b. The curve has cofactor \(h = 4\), which implies that \(\mathrm{A} + 2\) is not a square in \(\mathrm{GF}(p)\);
c. The quadratic twist has cofactor \(h_1 = 4\);
d. \(\mathrm{A}\) has the form \(\mathrm{A} \equiv 2 \bmod 4\), which allows optimized implementations of the group law using the Montgomery ladder; and
e. The curve and the quadratic twist both satisfy the cryptographic criteria in Appendix C.1.

3. Select the base point \(G = (G_x, G_y)\) of order \(n\), where \(|G_x|\) is minimal, and \(G_y\) is even.

Each of the curves K-233 (Section 3.3.1.2), K-283 (Section 3.3.1.3), K-409 (Section 3.3.1.4), and K-571 (Section 3.3.1.5) is a curve \(B_{a,b}\) in short-Weierstrass form with cofactor \(h = 2\) or \(h = 4\). Each curve is defined over a binary field \(\mathrm{GF}(2^m)\), where \(m\) is a prime number. For Koblitz curves, the curve parameters \(a\) and \(b\) are elements of \(\mathrm{GF}(2)\) with \(b = 1\). Hence, for each parameter \(m\), there are only two Koblitz curves with \(a = 0\) and \(a = 1\). Koblitz curves with \(a = 0\) have order 0 modulo 4, while those with \(a = 1\) have order 2 modulo 4.

The curve parameters \(a\) and \(m\) were chosen to satisfy the following:

1. The parameter \(a\) was set to \(a = 0\).

2. The set of integers \(m\) in the interval \([160,600]\) was determined so that the following conditions were satisfied simultaneously:

3. Select a pair \((a, m)\) from the set determined above.

4. Select an irreducible polynomial \(f(z)\) of degree \(m\), where \(f(z)\) is selected of a special form so as to allow efficient modular reduction (\(f(z)\) is a trinomial or pentanomial).

5. Select a base point \(G = (G_x, G_y)\) of order \(n\).

Each of the curves B-233 (Section 3.3.2.2), B-283 (Section 3.3.2.3), B-409 (Section 3.3.2.4), and B-571 (Section 3.3.2.5) is a curve \(B_{a,b}\) in short-Weierstrass form with cofactor \(h = 2\). Each curve is defined over a binary field \(\mathrm{GF}(2^m)\), where \(m\) is a prime number, and the prime number is among those values for which a binary Koblitz curve exists. The NIST prime curves were generated using the procedure in Appendix C.3.3,with \(\mathit{hdigest} = 160\) and SHA-1 hash function. The curve parameters \(a\) and \(b\) are:

1. The parameter \(a\) was set to \(a = 1\) (this ensures that curves with cofactor \(h = 2\) may exist).

2. The parameter \(b\) was derived in a hard-to-invert way using the procedure in Appendix C.3.3 from a pseudorandom \(\mathit{Seed}\) value so that the following conditions were satisfied simultaneously:

a. \(b \ne 0\) in \(\mathrm{GF}(p)\);
b. The curve has cofactor \(h = 2\); and
c. The curve satisfies the cryptographic criteria in Appendix C.1.

3. Select a base point \(G = (G_x, G_y)\) of order \(n\).

When generating the NIST pseudorandom curves (i.e, those in Section 3.2.1), \(\mathit{hdigest} = 160\) and SHA-1 hash were used. Inputs:

1. Positive integer \(l\)

2. Bit-string \(s\) of length \(\mathit{hdigest}\)

3. Approved hash function \(\mathit{HASH}\) with output length of \(\mathit{hdigest}\) bits and security design strength of at least \(\mathit{requested\_security\_strength}\).

Output: Coefficient \(b\) used to generate a pseudorandom prime curve

Let \(l\) be the bit length of \(p\), and define

1. Choose an arbitrary \(\mathit{hdigest}\)-bit string \(s\) as the domain parameter \(\mathit{Seed}\).

2. Compute \(H = \mathit{HASH}(s)\).

3. Let \(H_0\) be the bit string obtained by taking the \(w\) rightmost bits of \(H\).

4. Let \(z\) be the integer whose binary expansion is given by the \(\mathit{hdigest}\)-bit string \(s\).

5. For \(i\) from 1 to \(v\):
5.1 Define the \(\mathit{hdigest}\)-bit string \(s_i\) to be the binary expansion of the integer \((z + i) \bmod (2^{\mathit{hdigest}})\).
5.2 Compute \(h_i = \mathit{HASH}(s_i)\).

6. Let \(h\) be the bit string obtained by the concatenation of \(h_0, h_1, \ldots, h_v\) as follows:

7. Let \(c\) be the integer whose binary expansion is given by the bit string \(h\).

8. If (\((c = 0)\) or \((4c + 27 \equiv 0 \bmod p)\)), then go to Step 1.

9. Choose integers \(a, b \in \mathrm{GF}(p)\), such that

(The simplest choice is \(a = c\) and \(b = c\). However, they may be chosen differently for performance reasons. For example, the pseudorandom prime curves in this document all have \(a = -3\).)

10. Check that the elliptic curve \(E\) over \(\mathrm{GF}(p)\) given by \(y^2 = x^3 + ax + b\) has suitable order. If not, go to Step 1.

Given the \(\mathit{hdigest}\) domain parameter seed value \(s\), verify that the coefficient \(b\) was obtained from \(s\) via the cryptographic hash function \(\mathit{HASH}\) as follows:
Inputs:

1. Positive integer \(l\)

2. The coefficient \(b\)

3. Bit-string \(s\) of length \(\mathit{hdigest}\)

4. Approved hash function \(\mathit{HASH}\) with output length of \(\mathit{hdigest}\) bits and security design strength of at least \(\mathit{requested\_security\_strength}\)

Output: Verification that the coefficient \(b\) was obtained from \(s\) via the cryptographic hash function \(\mathit{HASH}\)
Process:

Let \(l\) be the bit length of \(p\), and define

1. Compute \(h = \mathit{HASH}(s)\).

2. Let \(h_0\) be the bit string obtained by taking the \(w\) rightmost bits of \(h\).

3. Let \(z\) be the integer whose binary expansion is given by the \(\mathit{hdigest}\)-bit string \(s\).

4. For \(i = 1\) to \(v\) do
4.1 Define the \(\mathit{hdigest}\)-bit string \(s_i\) to be the binary expansion of the integer \((z + i) \bmod (2^{\mathit{hdigest}})\).
4.2 Compute \(h_i = \mathit{HASH}(s_i)\).

5. Let \(h\) be the bit string obtained by the concatenation of \(h_0\), \(h_1\), \(\ldots\), \(h_v\) as follows:

6. Let \(c\) be the integer whose binary expansion is given by the bit string \(h\).

7. Verify that \(b^2 c \equiv -27 \bmod p\).

1. Prime number \(m\)

2. Bit-string \(s\) of length \(\mathit{hdigest}\)

3. Approved hash function \(\mathit{HASH}\) with output length of \(\mathit{hdigest}\) bits and security design strength of at least \(\mathit{requested\_security\_strength}\)

Output: Coefficient \(b\) used to generate a pseudorandom binary curve

1. Choose an arbitrary \(\mathit{hdigest}\)-bit string \(s\) as the domain parameter seed.

2. Compute \(h = \mathit{HASH}(s)\).

3. Let \(h_0\) be the bit string obtained by taking the \(w\) rightmost bits of \(h\).

4. Let \(z\) be the integer whose binary expansion is given by the \(\mathit{hdigest}\)-bit string \(s\).

5. For \(i\) from 1 to \(v\), do:
5.1 Define the \(\mathit{hdigest}\)-bit string \(s_i\) to be the binary expansion of the integer \((z + i) \bmod (2^{\mathit{hdigest}})\)
5.2 Compute \(h_i = \mathit{HASH}(s_i)\).

6. Let \(h\) be the bit string obtained by the concatenation of \(h_0\), \(h_1\), \(\ldots\), \(h_v\) as follows:

7. Let \(b\) be the element of \(\mathrm{GF}(2^m)\), which is represented by the bit string \(h\) in the Gaussian Normal Basis (see Appendix G.3.1).
8. Choose an element \(a\) of \(\mathrm{GF}(2^m)\).
9. Check that the elliptic curve \(\mathrm{E}\) over \(\mathrm{GF}(2^m)\) given by \(y^2 + xy = x^3 + ax^2 + b\) has suitable order. If not, go to Step 1.

Given the \(\mathit{hdigest}\)-bit domain parameter seed value \(s\), verify that the coefficient \(b\) was obtained from \(s\) via the cryptographic hash function \(\mathit{HASH}\) as follows:
Inputs:

1. Prime number \(m\)

2. The coefficient \(b\) (using the normal basis representation)

3. Bit-string \(s\) of length \(\mathit{hdigest}\)

4. Approved hash function \(\mathit{HASH}\) with output length of \(\mathit{hdigest}\) bits and security design strength of at least \(\mathit{requested\_security\_strength}\)

Output: Verification that the coefficient \(b\) was obtained from \(s\) via the cryptographic hash function \(\mathit{HASH}\)

1. Compute \(h = \mathit{HASH}(s)\).

2. Let \(h_0\) be the bit string obtained by taking the \(w\) rightmost bits of \(h\).

3. Let \(z\) be the integer whose binary expansion is given by the \(\mathit{hdigest}\)-bit string \(s\).

4. For \(i = 1\) to \(v\), do:
4.1 Define the \(\mathit{hdigest}\)-bit string \(s_i\) to be binary expansion of the integer \((z + i) \bmod (2^{160})\).
4.2 Compute \(h_i = \mathit{HASH}(s_i)\).

5. For \(i = 1\) to \(v\), do:

6. Let \(c\) be the element of \(\mathrm{GF}(2^m)\), which is represented by the bit string \(h\) in the Gaussian Normal Basis (see Section G.3.1).

7. Verify that \(c = b\).

1. Weierstrass curve \(\mathrm{W}_{a,b}\) defined over the prime field \(\mathrm{GF}(p)\)

2. Point \(Q\)

Output: ACCEPT or REJECT \(Q\) as an affine point on \(\mathrm{W}_{a,b}\).

1. If \(Q\) is the point at infinity \(\varnothing\), output REJECT.

2. Let \(Q = (x, y)\). Verify that \(x\) and \(y\) are integers in the interval \([0, p-1]\). Output REJECT if verification fails.

3. Verify that \((x, y)\) is a point on \(\mathrm{W}_{a,b}\) by checking that \((x, y)\) satisfies the defining equation \(y^2 = x^3 + a x + b\), where computations are carried out in \(\mathrm{GF}(p)\). Output REJECT if verification fails.

1. Weierstrass curve \(\mathrm{W}_{a,b}\) defined over the prime field \(\mathrm{GF}(p)\)

2. Point \(Q\)

Output: ACCEPT or REJECT \(Q\) as a point on \(\mathrm{W}_{\mathrm{a,b}}\) of order \(n\).

1. Perform partial public key validation on \(Q\) using the procedure of Appendix D.1.1.1. Output REJECT if this procedure outputs REJECT.

2. Verify that \(n Q = \varnothing\). Output REJECT if verification fails.

1. Montgomery curve \(\mathrm{M}_{A,B}\) defined over the prime field \(\mathrm{GF}(p)\)

2. Point \(Q\)

Output: ACCEPT or REJECT \(Q\) as an affine point on \(\mathrm{M}_{A,B}\).

1. If \(Q\) is the point at infinity \(\varnothing\), output REJECT.

2. Let \(Q = (u, v)\). Verify that both \(u\) and \(v\) are integers in the interval \([0, p-1]\). Output REJECT if verification fails.

3. Verify that \((u, v)\) is a point on \(\mathrm{M}_{A,B}\) by checking that \((u, v)\) satisfies the defining equation \(Bv^2 = u (u^2 + A u + 1)\), where computations are carried out in \(\mathrm{GF}(p)\). Output REJECT if verification fails.

1. Montgomery curve \(\mathrm{M}_{A,B}\) defined over the prime field \(\mathrm{GF}(p)\)

2. Point \(Q\)

Output: ACCEPT or REJECT \(Q\) as a point on \(\mathrm{M}_{A,B}\) of order \(n\).

1. Perform partial public key validation on \(Q\) using the procedure of Appendix D.1.2.1. Output REJECT if this procedure outputs REJECT.

2. Verify that \(nQ = \varnothing\). Output REJECT if verification fails.

1. Edwards curve \(\mathrm{E}_{a,d}\) defined over the prime field \(\mathrm{GF}(p)\)

2. Point \(Q\)

Output: ACCEPT or REJECT \(Q\) as an affine point on \(\mathrm{E}_{\mathrm{a,d}}\).

1. Verify that both \(x\) and \(y\) are integers in the interval \([0, p-1]\). Output REJECT if verification fails.

2. Let \(Q = (x, y)\). Verify that \((x, y)\) is a point on \(\mathrm{E}_{\mathrm{a,d}}\) by checking that \((x, y)\) satisfies the defining equation \(a x^2 + \mathrm{y}^2 = 1 + d x^2 y^2\), where computations are carried out in \(\mathrm{GF}(p)\). Output REJECT if verification fails.

1. Edwards curve \(\mathrm{E}_{\mathrm{a,d}}\) defined over the prime field \(\mathrm{GF}(p)\)

2. Point \(Q\)

Output: ACCEPT or REJECT \(Q\) as a point on \(\mathrm{E}_{\mathrm{a,d}}\) of order \(n\).

1. Perform partial public key validation on \(Q\) using the procedure of Appendix D.1.3.1. Output REJECT if this procedure outputs REJECT.

2. If \(Q = (0,1)\), output REJECT.

3. Verify that \(nQ = (0,1)\). Output REJECT if verification fails.

1. Weierstrass curve \(B_{\mathrm{a,b}}\) defined over the binary field \(\mathrm{GF}(2^m)\)

2. Point \(Q\)

Output: ACCEPT or REJECT \(Q\) as an affine point on \(B_{\mathrm{a,b}}\).

1. If \(Q\) is the point at infinity \(\varnothing\), output REJECT.

2. Let \(Q = (x, y)\). Verify that both \(x\) and \(y\) are binary polynomials in \(\mathrm{GF}(2^m)\) according to the field representation indicated by the parameter \(\mathit{FR}\). Output REJECT if verification fails.

3. Verify that \((x, y)\) is a point on the \(B_{\mathrm{a,b}}\) by checking that \((x, y)\) satisfies the defining equation \(y^2 + x y = x^3 + a x^2 + b\), where computations are carried out in \(\mathrm{GF}(2^m)\) according to the field representation indicated by the parameter \(\mathit{FR}\). Output REJECT if verification fails.

1. Weierstrass curve \(B_{\mathrm{a,b}}\) defined over the binary field \(\mathrm{GF}(2^m)\)

2. Point \(Q\)

Output: ACCEPT or REJECT \(Q\) as a point on \(B_{\mathrm{a},\mathrm{b}}\) of order \(n\).

1. Perform partial public key validation on \(Q\) using the procedure of Appendix D.1.4.1. Output REJECT if this procedure outputs REJECT.

2. Verify that \(nQ = \varnothing\). Output REJECT if verification fails.

1. Weierstrass curve \(\mathrm{W}_{\mathrm{a},\mathrm{b}}\) defined over the prime field \(\mathrm{GF}(p)\)

2. Point \(P\) on \(\mathrm{W}_{\mathrm{a},\mathrm{b}}\)

Output: Compressed point \(\underline{P}\)

1. If \(P\) is the point at infinity \(\varnothing\), set \(\underline{P} = P\).

2. If \(P = (x, y)\), set \(\underline{P} = (x, \underline{y})\), where \(\underline{y} = y \bmod 2\).

3. Output \(\underline{P}\).

Point decompression of an object \(\underline{P}\) with respect to this Weierstrass curve is defined as follows:

1. Object \(\underline{P}\)

2. Weierstrass curve \(\mathrm{W}_{\mathrm{a},\mathrm{b}}\) defined over the prime field \(\mathrm{GF}(p)\)

Output: Point \(P\) on \(\mathrm{W}_{\mathrm{a},\mathrm{b}}\) or INVALID

1. If \(\underline{P}\) is the point at infinity \(\varnothing\), output \(P = \underline{P}\).

2. If \(\underline{P}\) is the ordered pair \((x, t)\), where \(\mathrm{x}\) is an element of \(\mathrm{GF}(p)\), and \(t\) is an element of \(\{0, 1\}\):
2.1 Compute \(w = x^3 + ax + b\).

2.2 Compute a square root \(y\) of \(w\) in \(\mathrm{GF}(p)\) using the procedure of Appendix E.3. Output INVALID if that procedure outputs INVALID.
2.3 If \(y = 0\) and \(t = 1\), output INVALID.
2.4 If \(t \ne y \bmod 2\), set \(y = p - y\).
2.5 Output \(P = (x, y)\).

1. Weierstrass curve \(B_{\mathrm{a},\mathrm{b}}\) defined over the binary field \(\mathrm{GF}(2^m)\)

2. Point \(P\) on \(B_{\mathrm{a},\mathrm{b}}\)

Output: Compressed point \(\underline{P}\)

1. If \(P\) is the point at infinity \(\varnothing\), set \(\underline{P} = P\).

2. If \(P = (x, y)\) and \(x = 0\), set \(\underline{P} = (x, \underline{y})\), where \(\underline{y} = 0\).

3. If \(P = (x, y)\) and \(x \ne 0\):
3.1 Compute \(a = y/x\), where \(a = a_0 + a_1 z + \cdots + a_{m-1} z^{m-1}\).
3.2 Set \(\underline{P} = (x, \underline{y})\), where \(\underline{y} = a_0\).

4. Output \(\underline{P}\).

Consequently, for each affine point \(P = (x, y)\) on the Weierstrass curve \(\mathrm{B}_{\mathrm{a},\mathrm{b}}\), the compressed

point \(\underline{P}\) is an ordered pair \((x, t)\), where \(x\) is an element of \(\mathrm{GF}(2^m)\), and \(t\) is an element of \(\mathrm{GF}(2)\). Point decompression of an object \(\underline{P}\) with respect to this Weierstrass curve is defined as follows: Inputs:

1. Object \(\underline{P}\)

2. Weierstrass curve \(B_{\mathrm{a},\mathrm{b}}\) defined over the binary field \(\mathrm{GF}(2^m)\), where \(m\) is an odd integer

Output: Point \(P\) on \(B_{\mathrm{a},\mathrm{b}}\) or INVALID

1. If \(\underline{P}\) is the point at infinity \(\emptyset\), output \(P = \underline{P}\).

2. If \(\underline{P}\) is the ordered pair \((x, t)\), where \(x\) is an element of \(\mathrm{GF}(2^m)\) and \(t\) is an element of \(\mathrm{GF}(2)\), perform the following:
2.1 If \(x = 0\), perform the following steps:
2.1.1 If \(t = 1\), output INVALID.
2.1.2 Set \(y\) to the square root of \(b\) in \(\mathrm{GF}(2^m)\) using the algorithm of Appendix E.1.
2.2 If \(x \ne 0\), perform the following steps:
2.2.1 Compute \(w = (x^3 + a x^2 + b)/x^2 = x + a + b/x^2\).

2.2.2 Compute a solution \(\alpha\) in \(\mathrm{GF}(2^m)\) of the equation \(\alpha^2 + \alpha = w\) using the algorithm of Appendix E.2. Output INVALID if that procedure outputs INVALID.

2.2.3 If \(t \ne a_0\), where \(a = a_0 + a_1 z + \cdots + a_{m-1} z^{m-1}\), set \(\alpha = \alpha + 1\).

2.2.4 Set \(y = \alpha x\).

2.3 Output \(P = (x, y)\).

If \(x\) is an element of \(\mathrm{GF}(2^m)\), then its square root is the element \(x^{2^{m-1}}\).

E.2. Solving the Equation \(x^2 + x = w\) in Binary Fields

Input: Field element \(\mathrm{w}\) in \(\mathrm{GF}(2^m)\), where \(m\) is an odd integer
Output: Solution \(\alpha\) in \(\mathrm{GF}(2^m)\) of the equation \(\alpha^2 + \alpha = w\) or INVALID
Process:

1. Compute \(\mathrm{Tr}(w) = w^{2^0} + w^{2^1} + w^{2^2} + w^{2^3} + \ldots + w^{2^{m-1}}\) (the trace of \(w\)).

2. If \(\mathrm{Tr}(w) = 1\), output INVALID.

3. Compute \(\alpha := \mathrm{Hf}(x) = w^{2^0} + w^{2^2} + w^{2^4} + \ldots + w^{2^{m-1}}\) (the half-trace of \(w\)).

4. Output \(\alpha\).

E.3. Computing Square Roots in Non-Binary Fields \(\mathrm{GF}(q)\)

The Tonelli-Shanks algorithm can be used to compute a square root given an equation of the form \(x^2 \equiv n \bmod p\), where \(n\) is an integer – which is a quadratic residue mod \(p\) – and \(p\) is an odd prime. Find \(q\) and \(s\) (with \(q\) odd), such that \(p - 1 = q2^s\) by factoring out the powers of 2. Note that if \(\mathrm{s} = 1\), as for primes \(\mathrm{p} \equiv 3 \bmod 4\), this reduces to finding \(x = n^{(p+1)/4} \bmod p\). Check to see if \(n^q = 1\). If so, then the root \(x = n^{(q+1)/2} \bmod p\).

Otherwise, select a \(z\), which is a quadratic non-residue modulo \(p\). The Legendre symbol \(\left(\frac{a}{p}\right)\), where \(p\) is an odd prime and \(a\) is an integer, can be used to test candidate values for \(z\) to see if a value of \(-1\) is returned. Search for a solution as follows:

1. Set \(x = n^{(q+1)/2} \bmod p\).

2. Set \(\mathrm{t} = n^q \bmod p\).

3. Set \(m = s\).

4. Set \(c = z^q \bmod p\).

5. While \(t \ne 1\), repeat the following steps:

a) Using repeated squaring, find the smallest \(i\), such that \(t^{2^i} = 1\), where \(0 < i < m\).

Let \(e = 2\).
Loop for \(i = 1\) until \(i = m\).
If \(t^e \bmod p = 1\), then exit the loop.

Set \(e = 2e\).
b) Update values:

The solution is \(x\), and the second solution is \(p - x\). If the least \(i\) found is \(m\), then no solution exists.

Square roots in a non-binary field \(\mathrm{GF}(q)\) are relatively efficient to compute if \(q\) has the special form \(q \equiv 3 \bmod 4\) or \(q \equiv 5 \bmod 8\). All but one of the elliptic curves recommended in this Recommendation are defined over such fields. The following routines describe simplified cases to compute square roots for \(p \equiv 3 \bmod 4\) or \(p \equiv 5 \bmod 8\).
To find a square root of \((u/v)\) if \(p \equiv 3 \bmod 4\) (as in E448), first compute the candidate root \(x = (u/v)^{(p+1)/4} = u^3 v (u^5 v^3)^{(p-3)/4} \bmod \mathrm{p}\). If \(v x^2 = u\), the square root is \(x\). Otherwise, no square root exists.
To find a square root of \((u/v)\) if \(p \equiv 5 \bmod 8\) (as in Edwards25519), first compute the candidate root \(x = (u/v)^{(p+3)/8} = u v^3 (u v^7)^{(p-5)/8} \bmod p\). To find the root, check three cases:

1. If \(v x^2 = u \bmod p\), the square root is \(x\).

2. If \(v x^2 = -u \bmod p\), the square root is \(x \times 2^{((p-1)/4)}\).

3. Otherwise, no square root exists for modulo \(p\).

If \(x = 0\) and \(x_0 = 1\), point decoding fails. If \(x \bmod 2 = x_0\), then the \(x\)-coordinate is \(x\).

Otherwise, the \(x\)-coordinate is \(p - x\).

E.4. Computing Inverses in \(\mathrm{GF}(q)\)

If \(x\) is an element of \(\mathrm{GF}(q)\) and \(x \ne 0\), its (multiplicative) inverse is the element \(x^{q-2}\).
If one is concerned about side-channel leakage, one should compute the inverse using a constant-time algorithm. For example, one could indirectly compute \(u^{-1}\) by first computing the inverse of the blinded element \(\lambda u\), where \(\lambda\) is a random non-zero element of \(\mathrm{GF}(q)\), and subsequently computing \(\lambda(\lambda u)^{-1} = u^{-1}\). This yields an inversion routine where the inversion operation itself does not require side-channel protection and which may have relatively low computational complexity. Note that there may be other more efficient constant-time inversion algorithms.

The following algorithm is used to convert a field element to an integer. The algorithm is given for reference purposes. Other algorithms that produce an equivalent result may be used.
Input: An element \(a\) of the field \(\mathrm{GF}(q)\)
Output: A non-negative integer \(x\) in the interval \([0, q-1]\)
Process:

1. If \(q\) is an odd prime, \(a\) is an integer in the interval \([0, q-1]\). In this case, set \(x = a\).

2. If \(q = 2^m\), \(a\) must be a binary polynomial of a degree smaller than \(m\), \(a = a(z) = a_{m-1} z^{m-1} + a_{m-2} z^{m-2} + \ldots + a_1 z + a_0\), where each coefficient \(a_i\) is 0 or 1. In this case, set \(x = a(2) = a_{m-1} 2^{m-1} + a_{m-2} 2^{m-2} + \ldots + a_1 2^1 + a_0 2^0\) computed over \(\mathbb{Z}\), not modulo 2.

3. Output \(x\).

The following algorithm is used to convert an integer to a field element. The algorithm is given for reference purposes. Other algorithms that produce an equivalent result may be used.
Inputs: Non-negative integer \(x\) and \(q\), where \(q\) is an odd prime or \(q = 2^m\)
Output: An element \(a\) of the field \(\mathrm{GF}(q)\)
Process:

1. Set \(x = x \bmod q\).

2. If \(q\) is an odd prime, \(x\) is an integer in the interval \([0, q-1]\). In this case, set \(a = x\).

3. If \(q = 2^m\), \(x\) can be uniquely written as \(x = a_{m-1} 2^{m-1} + a_{m-2} 2^{m-2} + \ldots + a_1 2 + x_0\), where each coefficient \(x_i\) is 0 or 1. In this case, set \(x = a(z) = a_{m-1} z^{m-1} + a_{m-2} z^{m-2} + \ldots + a_1 z^1 + a_0 2^0\);

4. Output \(a\).

The following algorithm is used to convert an integer to a bit string. The algorithm is given for reference purposes. Other algorithms that produce an equivalent result may be used.
Inputs: Non-negative integer \(x\) in the range \(0 \le x < 2^l\)
Output: Bit-string \(X\) of length \(l\)
Process:

1. The integer \(x\) can be uniquely written as \(x = x_{l-1} 2^{l-1} + x_{l-2} 2^{l-2} + \ldots + x_1 2 + x_0\), where each coefficient \(x_i\) is 0 or 1.

2. Set \(X\) to the bit string \((x_{l-1}, x_{l-2}, \ldots, x_1, x_0)\).

3. Output \(X\).

The following algorithm is used to convert a bit string to an integer. The algorithm is given for reference purposes. Other algorithms that produce an equivalent result may be used.
Input: Bit-string \(X\) of length \(l\)
Output: Non-negative integer \(x\), where \(x < 2^l\)
Process:

1. Let \(X\) be the bit string \((x_{l-1}, x_{l-2}, \ldots, x_1, x_0)\), where each coefficient \(x_i\) is 0 or 1.

2. Set \(x\) to the integer value \(x = x_{l-1} 2^{l-1} + x_{l-2} 2^{l-2} + \ldots + x_1 2 + x_0\).

3. Output \(x\).

The prime moduli of the above recommended curves are of a special type (generalized Mersenne numbers and Crandall primes) for which modular multiplication can be carried out more efficiently than in general. This section provides the rules for implementing faster arithmetic for each of these recommended prime moduli.
The usual way to multiply two integers mod \(m\) is to take the integer product and reduce it modulo \(m\). One, therefore, has the following problem: given an integer \(A\) less than \(m^2\), compute

In general, one must obtain \(B\) as the remainder of an integer division. If \(m\) is a generalized Mersenne number or a Crandall prime, however, then \(B\) can be expressed as a sum or difference mod \(m\) of a small number of terms. To compute this expression, the integer sum or difference can be evaluated and the result reduced modulo \(m\). The latter reduction can be accomplished by adding or subtracting a few copies of \(m\).
The prime modulus \(p\) for each of the four recommended P-x curves is a generalized Mersenne number.

The modulus for this curve is \(p = 2^{224} - 2^{96} + 1\). Each integer \(A\) less than \(p^2\) can be written as

where each \(A_i\) is a 32-bit integer. As a concatenation of 32-bit words, this can be denoted by

The expression for \(B\) is

The modulus for this curve is \(p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1\). Each integer \(A\) less than \(p^2\) can be written as

where each \(A_i\) is a 32-bit integer. As a concatenation of 32-bit words, this can be denoted by

The expression for \(B\) is

The modulus for this curve is \(p = 2^{384} - 2^{128} - 2^{96} + 2^{32} - 1\). Each integer \(A\) less than \(p^2\) can be written as

where each \(A_i\) is a 32-bit integer. As a concatenation of 32-bit words, this can be denoted by

The expression for \(B\) is

where the 384-bit terms are given by

The modulus for this curve is \(p = 2^{521} - 1\). Each integer \(A\) less than \(p^2\) can be written as

where each \(A_i\) is a 521-bit integer. As a concatenation of 521-bit words, this can be denoted by

The expression for \(B\) is

The modulus for this curve is \(p = 2^{255} - 19\). Each integer \(A\) less than \(p^2\) can be written

where each \(A_i\) is a 64-bit integer. As a concatenation of 64-bit words, this can be denoted by

The modulus for this curve is \(p = 2^{448} - 2^{224} - 1\). Each integer \(A\) less than \(p^2\) can be written

where each \(A_i\) is a 224-bit integer. As a concatenation of 224-bit words, this can be denoted by

The expression for \(B\) is

This section describes a particularly efficient method of computing the scalar multiple \(Q := kP\) on the Koblitz curve \(W_{a,b}\) over \(\mathrm{GF}(2^m)\).

The operation \(\tau\) is defined by

When the normal basis representation is used, then the operation \(\tau\) is implemented by performing right circular shifts on the bit strings representing \(x\) and \(y\). Given \(m\) and \(a\), define the following parameters:

• \(C\) is some integer greater than 5.

• \(\mu = (-1)^{1-a}\)

• For \(i = 0\) and \(i = 1\), define the sequence \(s_i(m)\) by

• Define the sequence \(V(m)\) by

For the recommended Koblitz curves, the quantities \(s_i(m)\) and \(V(m)\) are as follows:

Curve K-163:
\(s_0(163) =\) 2579386439110731650419537
\(s_1(163) =\) –755360064476226375461594

\(V(163) =\) –4845466632539410776804317

Curve K-233:
\(s_0(233) =\) –27859711741434429761757834964435883
\(s_1(233) =\) –44192136247082304936052160908934886

\(V(233) =\) –137381546011108235394987299651366779

Curve K-283:
\(s_0(283) =\) –665981532109049041108795536001591469280025
\(s_1(283) =\) 1155860054909136775192281072591609913945968

\(V(283) =\) 7777244870872830999287791970962823977569917

Curve K-409:
\(s_0(409) =\) –18307510456002382137810317198756461378590542487556869338419259
\(s_1(409) =\) –8893048526138304097196653241844212679626566100996606444816790

\(V(409) =\) 10457288737315625927447685387048320737638796957687575791173829

Curve K-571:
\(s_0(571) =\) –3737319446876463692429385892476115567147293964596131024123406420\
235241916729983261305

\(s_1(571) =\) –3191857706446416099583814595948959674131968912148564658610565117\
58982848515832612248752

\(V(571) =\) –1483809269816914138996191402970514903645425741804939362329123395\
34208516828973111459843

The following algorithm computes the scalar multiple \(Q := kP\) on the Koblitz curve \(W_{a,b}\) over \(\mathrm{GF}(2^m)\). The average number of elliptic additions and subtractions is at most \(\sim 1 + (m/3)\) and is at most \(\sim m/3\) with probability at least \(1 - 2^{5-C}\).

1. For \(i := 0\) to 1, do:
1.1 \(k' \leftarrow \lfloor k / 2^{a-C+(m-9)/2} \rfloor\)
1.2 \(g' \leftarrow s_i(m) \cdot k'\)
1.3 \(h' \leftarrow \lfloor g' / 2^m \rfloor\)
1.4 \(j' \leftarrow V(m) \cdot h'\)
1.5 \(l' \leftarrow \operatorname{Round}((g' + j') / 2^{(m+5)/2})\)
1.6 \(\lambda_i \leftarrow l' / 2^C\)
1.7 \(f_i \leftarrow \operatorname{Round}(\lambda_i)\)
1.8 \(\eta_i \leftarrow \lambda_i - f_i\).
1.9 \(h_i \leftarrow 0\)

2. \(\eta \leftarrow 2\eta_0 + \mu\eta_1\)

3. If \((\eta \ge 1)\),
then
if \((\eta_o - 3\mu\eta_1 < -1)\)
then set \(h_1 \leftarrow \mu\).
Else, set \(h_0 \leftarrow 1\).
Else,
if \((\eta_0 + 4\mu\eta_1 \ge 2)\),
then set \(h_1 \leftarrow \mu\).

4. If \((\eta < -1)\),
then
if \((\eta_0 - 3\mu\eta_1 \ge 1)\),
then set \(h_1 \leftarrow -\mu\).
Else, set \(h_0 \leftarrow -1\).
Else,
if \((\eta_0 + 4\mu\eta_1 < -2)\),
then set \(h_1 \leftarrow -\mu\).

5. \(q_0 \leftarrow f_0 + h_0\)

6. \(q_1 \leftarrow f_1 + h_1\)

7. \(r_0 \leftarrow n - (s_0 + \mu s_1) q_0 - 2 s_1 q_1\)

8. \(r_1 \leftarrow s_1 q_0 - s_0 q_1\)

9. Set \(Q \leftarrow O\)
10. \(P_0 \leftarrow P\)
11. While \(((r_0 \ne 0)\) or \((r_1 \ne 0))\)

11.1 If (\(r_0\) odd), then

11.1.1 Set \(u \leftarrow 2 - (r_0 - 2 r_1 \bmod 4)\).

11.1.2 Set \(r_0 \leftarrow r_0 - u\).

11.1.3 If \((u = 1)\), then set \(Q \leftarrow Q + P_0\).

11.1.4 If \((u = -1)\), then set \(Q \leftarrow Q - P_0\).

11.2 Set \(P_0 \leftarrow \tau P_0\).
11.3 Set \((r_0, r_1) \leftarrow (r_1 + \mu r_0/2, -r_0/2)\).

12. Output \(Q\).

The elements of \(\mathrm{GF}(2^m)\), where \(m\) is odd, are expressed in terms of the type \(T\) normal² basis \(B\) for \(\mathrm{GF}(2^m)\) for some \(T\). Each element has a unique representation as a bit string:

The arithmetic operations are performed as follows:

Addition: Addition of two elements is implemented by bit-wise addition modulo 2. Thus, for example,

Squaring: If

then

Multiplication: Multiplication depends on the following function \(F(\underline{u},\underline{v})\) on inputs:

and

1. Set \(p = Tm + 1\).

2. Let \(u\) be an integer having order \(T\) modulo \(p\).

3. Compute the sequence \(F(1), F(2), \ldots, F(p-1)\) as follows:
a. Set \(w = 1\).
b. For \(j\) from \(0\) to \(T-1\), do:
i. Set \(n = w\).
ii. For \(i = 0\) to \(m-1\), do:

1. Set \(F(n) = i\).

2. Set \(n = 2n \bmod p\).

iii. Set \(w = uw \bmod p\).

4. Output the formulae \(F(\underline{u}, \underline{v})\), where

² It is assumed in this section that \(m\) is odd and \(T\) is even since this is the only case considered in this standard.

This computation only needs to be performed once per basis. Given the function \(F\) for \(B\), the product

1. Set \((u_0\ u_1\ \ldots\ u_{m-1}) = (a_0\ a_1\ \ldots\ a_{m-1})\).

2. Set \((v_0\ v_1\ \ldots\ v_{m-1}) = (b_0\ b_1\ \ldots\ b_{m-1})\).

3. For \(k = 0\) to \(m - 1\), do:
a. Compute \(c_k = \mathrm{F}(\underline{u}, \underline{v})\).
b. Set \(u = \mathbf{LeftShift}(u)\) and \(v := \mathbf{LeftShift}(v)\), where \(\mathbf{LeftShift}\) denotes the circular left shift operation.