--- 1/draft-ietf-lwig-curve-representations-11.txt 2020-08-24 09:13:15.038578617 -0700
+++ 2/draft-ietf-lwig-curve-representations-12.txt 2020-08-24 09:13:15.270584509 -0700
@@ -1,18 +1,18 @@
lwig R. Struik
Internet-Draft Struik Security Consultancy
-Intended status: Informational July 13, 2020
-Expires: January 14, 2021
+Intended status: Informational August 24, 2020
+Expires: February 25, 2021
Alternative Elliptic Curve Representations
- draft-ietf-lwig-curve-representations-11
+ draft-ietf-lwig-curve-representations-12
Abstract
This document specifies how to represent Montgomery curves and
(twisted) Edwards curves as curves in short-Weierstrass form and
illustrates how this can be used to carry out elliptic curve
computations using existing implementations of, e.g., ECDSA and ECDH
using NIST prime curves. We also provide extensive background
material that may be useful for implementers of elliptic curve
cryptography.
@@ -33,81 +33,81 @@
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
- This Internet-Draft will expire on January 14, 2021.
+ This Internet-Draft will expire on February 25, 2021.
Copyright Notice
Copyright (c) 2020 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Fostering Code Reuse with New Elliptic Curves . . . . . . . . 5
- 2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 5
+ 2. Specification of Wei25519 . . . . . . . . . . . . . . . . . . 6
3. Use of Representation Switches . . . . . . . . . . . . . . . 6
4. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.1. Implementation of X25519 . . . . . . . . . . . . . . . . 7
- 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 7
+ 4.2. Implementation of Ed25519 . . . . . . . . . . . . . . . . 8
4.3. Specification of ECDSA25519 . . . . . . . . . . . . . . . 8
- 4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 8
+ 4.4. Other Uses (Wei448, ECDH448, ECDSA448, and Others) . . . 9
5. Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
- 5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 9
- 5.2. Representation Conventions . . . . . . . . . . . . . . . 9
+ 5.1. Wire Format . . . . . . . . . . . . . . . . . . . . . . . 10
+ 5.2. Representation Conventions . . . . . . . . . . . . . . . 10
5.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 10
6. Implementation Considerations . . . . . . . . . . . . . . . . 11
7. Implementation Status . . . . . . . . . . . . . . . . . . . . 12
8. Security Considerations . . . . . . . . . . . . . . . . . . . 13
- 9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 13
+ 9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 14
10. Using Wei25519 and Wei448 with COSE and JOSE . . . . . . . . 14
10.1. Using Wei25519 and Wei448 Keys with COSE and JOSE . . . 14
- 10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 14
- 10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 15
+ 10.1.1. Encoding of Short-Weierstrass Curves with COSE . . . 15
+ 10.1.2. Encoding of Short-Weierstrass Curves with JOSE . . . 16
10.2. Using ECDSA25519 and ECDSA448 with COSE and JOSE . . . . 16
10.2.1. Encoding of ECDSA Instantiations with COSE . . . . . 17
10.2.2. Encoding of ECDSA Instantiations with JOSE . . . . . 18
- 10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 18
- 10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 19
+ 10.3. Using ECDH25519 and ECDH448 with COSE and JOSE . . . . . 19
+ 10.3.1. Encoding of co-factor ECDH with COSE . . . . . . . . 20
10.3.2. Encoding of co-factor ECDH with JOSE . . . . . . . . 20
11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20
- 11.1. IANA Considerations for Wei25519 . . . . . . . . . . . . 20
- 11.1.1. COSE Elliptic Curves Registration . . . . . . . . . 20
+ 11.1. IANA Considerations for Wei25519 . . . . . . . . . . . . 21
+ 11.1.1. COSE Elliptic Curves Registration . . . . . . . . . 21
11.1.2. COSE Algorithms Registration (1/2) . . . . . . . . . 21
11.1.3. COSE Algorithms Registration (2/2) . . . . . . . . . 21
11.1.4. JOSE Elliptic Curves Registration . . . . . . . . . 22
11.1.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 22
- 11.1.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 22
+ 11.1.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 23
11.2. IANA Considerations for Wei448 . . . . . . . . . . . . . 23
11.2.1. COSE Elliptic Curves Registration . . . . . . . . . 23
- 11.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 23
+ 11.2.2. COSE Algorithms Registration (1/2) . . . . . . . . . 24
11.2.3. COSE Algorithms Registration (2/2) . . . . . . . . . 24
11.2.4. JOSE Elliptic Curves Registration . . . . . . . . . 24
- 11.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 24
+ 11.2.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 25
11.2.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 25
- 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 25
+ 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 26
13. References . . . . . . . . . . . . . . . . . . . . . . . . . 26
13.1. Normative References . . . . . . . . . . . . . . . . . . 26
13.2. Informative References . . . . . . . . . . . . . . . . . 28
Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 30
A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 30
A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 30
A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 30
Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 31
B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 31
B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 33
@@ -205,35 +205,56 @@
P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 118
P.3. Conversion to Integers in Z_n via the Discard Method . . 119
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 119
1. Fostering Code Reuse with New Elliptic Curves
Elliptic curves can be represented using different curve models.
Recently, IETF standardized elliptic curves that are claimed to have
better performance and improved robustness against "real world"
attacks than curves represented in the traditional "short"
- Weierstrass model. This document specifies an alternative
- representation of points of Curve25519, a so-called Montgomery curve,
- and of points of Edwards25519, a so-called twisted Edwards curve,
- which are both specified in [RFC7748], as points of a specific so-
- called "short" Weierstrass curve, called Wei25519. We also define
- how to efficiently switch between these different representations.
+ Weierstrass curve model. These so-called CFRG curves [RFC7748] use
+ the Montgomery curve model and the model of twisted Edwards curves.
- Use of Wei25519 allows easy definition of new instantiations of
- signature schemes and key agreement schemes already specified for
- traditional NIST prime curves, thereby allowing easy integration with
- existing specifications, such as NIST SP 800-56a [SP-800-56a], FIPS
- Pub 186-4 [FIPS-186-4], and ANSI X9.62-2005 [ANSI-X9.62], and
- fostering code reuse on platforms that already implement some of
- these schemes using elliptic curve arithmetic for curves in "short"
- Weierstrass form (see Appendix C.1).
+ In this document, we specify these curves using the traditional
+ "short" Weierstrass model and also define how to efficiently switch
+ between representations in these different curve models. In
+ particular, we specify Wei25519, which allows an alternative
+ representation of points of Curve25519 (a Montgomery curve) and of
+ points of Edwards25519 (a twisted Edwards curve), as points of a
+ corresponding "short" Weierstrass curve. Similarly, we specify
+ Wei448, which allows an alternative representation of points of
+ Curve448 (a Montgomery curve) and of points of Ed448 (an Edwards
+ curve), as points of a corresponding "short" Weierstrass curve.
+
+ Use of Wei25519 and Wei448 allows easy definition of new
+ instantiations of signature schemes and key agreement schemes already
+ specified for traditional NIST prime curves, thereby allowing easy
+ integration with existing specifications, such as NIST SP 800-56a
+ [SP-800-56a], FIPS Pub 186-4 [FIPS-186-4], and ANSI X9.62-2005
+ [ANSI-X9.62], and fostering code reuse on platforms that already
+ implement some of these schemes using elliptic curve arithmetic for
+ curves in "short" Weierstrass form (see Appendix C.1). To illustrate
+ this, we specify how to use Wei25519 and Wei448 with co-factor ECDH
+ and with ECDSA, thereby giving rise to the key agreement schemes
+ ECDH25519 and ECDH448 and the signature schemes ECDSA25519 and
+ ECDSA448. In all these cases, implementors may use the curve
+ arithmetic for the curve model of their choosing (where they can
+ efficiently switch between representations in different curve models,
+ if required).
+
+ For ease of exposition, we consider Wei25519 first and introduce
+ Wei448 simply as an illustration of how to create other "offspring"
+ objects and protocols (see Section 4.4). We also provide extensive
+ background material that we hope may be useful for implementors of
+ elliptic curve cryptography or for cross-referencing with future
+ specification work.
2. Specification of Wei25519
For the specification of Wei25519 and its relationship to Curve25519
and Edwards25519, see Appendix E. For further details and background
information on elliptic curves, we refer to the other appendices.
The use of Wei25519 allows reuse of existing generic code that
implements short-Weierstrass curves, such as the NIST curve P-256, to
also implement the CFRG curves Curve25519 and Edwards25519. (Here,
@@ -345,21 +366,21 @@
criteria). In particular, one can instantiate this scheme with the
Weierstrass curve Wei25519 and the hash function SHA-256
[FIPS-180-4], where an implementation may generate an ephemeral
public-private key pair for Wei25519 by (1) internally carrying out
these computations on the Montgomery curve Curve25519, the twisted
Edwards curve Edwards25519, or even the Weierstrass curve Wei25519.-3
(with hardcoded a=-3 domain parameter); (2) representing the result
as a key pair for the curve Wei25519. Note that, in either case, one
can implement these schemes with the same representation conventions
as used with existing NIST specifications, including bit/byte-
- ordering, compression functions, and the-like. This allows generic
+ ordering, compression functions, and the like. This allows generic
implementations of ECDSA with the hash function SHA-256 and with the
NIST curve P-256 or with the curve Wei25519 specified in this
specification to reuse the same implementation (instantiated with,
respectively, the NIST P-256 elliptic curve domain parameters or with
the domain parameters of curve Wei25519 specified in Appendix E). We
denote by ECDSA25519 the instantiation of ECDSA with SHA-256 and with
curve Wei25519, where the signature (r,s) is represented as the
right-concatenation of the integers r and s, each represented as
fixed-size strings with tight MSB/msb ordering (see Appendix I).
@@ -368,23 +389,23 @@
Any existing specification of cryptographic schemes using elliptic
curves in Weierstrass form and that allows introduction of a new
elliptic curve (here: Wei25519) is amenable to similar constructs,
thus spawning "offspring" protocols, simply by instantiating these
using the new curve in "short" Weierstrass form, thereby allowing
code and/or specifications reuse and, for implementations that so
desire, carrying out curve computations "under the hood" on
Montgomery curve and twisted Edwards curve cousins hereof (where
these exist). This would simply require definition of a new object
identifier for any such envisioned "offspring" protocol. This could
- significantly simplify standardization of schemes and help keeping
- the resource and maintenance cost of implementations supporting
- algorithm agility [RFC7696] at bay.
+ significantly simplify standardization of schemes and help keeping at
+ bay the resource and maintenance cost of implementations supporting
+ algorithm agility [RFC7696].
We illustrate the construction of such offspring protocols for
Curve448, another Montgomery curve recently standardized by IETF (see
[RFC7748]). Similar to the case with Curve25519, one can represent
points of this curve via different curve models, viz. as points of an
Edwards curve (Ed448) or as points of a short-Weierstrass curve
(Wei448). For the specification of Wei448 and its relationship to
Curve448 and Ed448, see Appendix M. As with ECDH25519, one can now
easily define a NIST-compliant version of co-factor Diffie-Hellman
key agreement (denoted by ECDH448), by simply reusing the example of
@@ -433,21 +454,21 @@
5.3. Domain Parameters
All traditional NIST curves are Weierstrass curves with domain
parameter a=-3, while all Brainpool curves [RFC5639] are isomorphic
to a Weierstrass curve of this form. Thus, one can expect there to
be existing Weierstrass implementations with a hardcoded a=-3 domain
parameter ("Jacobian-friendly"). For those implementations,
including the curve Wei25519 as a potential vehicle for offering
support for the CFRG curves Curve25519 and Edwards25519 is not
- possible, since not of the required form. Instead, one has to
+ possible, since it is not of the required form. Instead, one has to
implement Wei25519.-3 and include code that implements the isogeny
and dual isogeny from and to Wei25519. The lowest odd-degree isogeny
has degree l=47 and requires roughly 9kB of storage for isogeny and
dual-isogeny computations (see the tables in Appendix G.4). Note
that storage would have reduced to a single 64-byte table if only the
Curve25519 curve would have been generated so as to be isomorphic to
a Weierstrass curve with hardcoded a=-3 parameter (this corresponds
to l=1).
NOTE 1: An example of a Montgomery curve defined over the same field
@@ -752,25 +774,25 @@
All inputs and outputs are uniquely determined by specifying the
encodings of the message m, the private key d, the public key Q, the
signature, and the values "valid" and "invalid".
The encodings below specify the use of instantiations of ECDSA with
COSE (see Section 10.2.1) and JOSE (see Section 10.2.2), where the
encoding for a specific ECDSA instantiation (i.e., with a specific
short-Weierstrass curve and specific hash function) results by
setting the "crv" parameter to the unique name of the underlying
curve in question and the "alg" parameter to the unique name of the
- specific signature scheme scheme instantiation (e.g., "ECDSA25519"
- for the ECDSA scheme defined in Section 4.3 and "ECDSA448" for the
- scheme defined in Section 4.4). Note that, in this case, the "alg"
- name uniquely defines the curve (and, thereby, implicitly the
- underlying "crv" parameter) and the underlying hash function.
+ specific signature scheme instantiation (e.g., "ECDSA25519" for the
+ ECDSA scheme defined in Section 4.3 and "ECDSA448" for the scheme
+ defined in Section 4.4). Note that, in this case, the "alg" name
+ uniquely defines the curve (and, thereby, implicitly the underlying
+ "crv" parameter) and the underlying hash function.
10.2.1. Encoding of ECDSA Instantiations with COSE
Instantiations of ECDSA used with COSE use the following encodings of
inputs and outputs:
a. The message m is the COSE_Sign structure as specified in
Section 4.1 of [RFC8152], converted to a bit-string, using the
OS2BS mapping of Appendix I.4;
@@ -916,22 +939,22 @@
private key.
11. IANA Considerations
Code points are requested for curves Wei25519 and Wei448 and their
use with ECDSA and co-factor ECDH, using the representation
conventions of this document.
New code points would be required in case one wishes to specify one
or more other "offspring" protocols beyond those exemplified in
- Section 4.4. Specification hereof is, however, outside scope of the
- current document.
+ Section 4.4. Specification hereof is, however, outside the scope of
+ the current document.
11.1. IANA Considerations for Wei25519
11.1.1. COSE Elliptic Curves Registration
This section registers the following value in the IANA "COSE Elliptic
Curves" registry [IANA.COSE.Curves].
Name: Wei25519;
@@ -1519,23 +1542,23 @@
multiplication modulo the irreducible polynomial f(z). By
definition, each element x of GF(q) is a polynomial in z of degree
smaller than m and can, therefore, be uniquely represented as a
vector (x_{m-1}, x_{m-2}, ..., x_1, x_0) of length m with
coefficients in GF(p), where x_i is the coefficient of z^i of
polynomial x. Note that this representation depends on the
irreducible polynomial f(z) of the field GF(p^m) in question (which
is often fixed in practice). Note that GF(q) contains the prime
field GF(p) as a subset. If m=1, the definitions of GF(p) and
GF(p^1) above coincide, since each nonzero element of GF(p) can be
- viewed as a polynomial in z of degree zero. If m>1, then GF(q) is
- called a (nontrivial) extension field of GF(p). The number p is
- called the characteristic of GF(q).
+ viewed as a polynomial in z of degree zero. If m>1 (i.e., if if q is
+ a strict prime power), then GF(q) is called a (nontrivial) extension
+ field of GF(p). The number p is called the characteristic of GF(q).
A field element y is called a square in GF(q) if it can be expressed
as y:=x^2 for some x in GF(q); it is called a non-square in GF(q)
otherwise. If y is a square in GF(q), we denote by sqrt(y) one of
its square roots (the other one being -sqrt(y)). For methods for
computing square roots and inverses in GF(q) - if these exist - see
Appendix K.1 and Appendix K.2, respectively. For methods for mapping
a nonzero field element that is not a square in GF(q) to a point of a
curve, see Appendix K.3 (or see Appendix K.4, if one wishes to always
obtain a high-order point of the curve in question).
@@ -2131,21 +2154,21 @@
(X,Y):=(u'(X')/w'(X')^2,Y'*v'(X')/w'(X')^3) of W_{a,b}, where --
again -- u'(X'), v'(X'), and w'(X') are polynomials in X' that depend
on the isogeny in question. These mappings have the property that
their composition is not the identity mapping (as was the case with
the isomorphic mappings discussed in Appendix F.3), but rather a
fixed multiple hereof: if this multiple is l then the isogeny is
called an isogeny of degree l (or l-isogeny) and u, v, and w (and,
similarly, u', v', and w') are polynomials of degrees l, 3*(l-1)/2,
and (l-1)/2, respectively. Note that an isomorphism is simply an
isogeny of degree l=1. Details of how to determine isogenies are out
- of scope of this document. The above formulas assume that the
+ of the scope of this document. The above formulas assume that the
isogeny has odd degree (i.e., l is odd); detailed formulas for even-
degree isogenies are similar, but out of scope.
Implementations may take advantage of this mapping to carry out
elliptic curve group operations originally defined for a Weierstrass
curve with a generic domain parameter a on a corresponding isogenous
Weierstrass curve with domain parameter a'=-3 (mod p), where one can
use so-called Jacobian coordinates with a particular projective
version of the addition laws of Appendix C.1. Since all traditional
NIST curves have domain parameter a=-3, while all Brainpool curves
@@ -2295,22 +2318,22 @@
38d80c77 985f0329)
G.4. Isogeny Details
The isogeny and dual isogeny are both isogenies with degree l=47.
Both are specified by a triple of polynomials u, v, and w (resp. u',
v', and w') of degree 47, 69, and 23, respectively, with coefficients
in GF(p). The coeffients of each of these polynomials are specified
in Appendix G.4.1 (for the isogeny) and in Appendix G.4.2 (for the
dual isogeny). For each polynomial in variable x, the coefficients
- are tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in
- hexadecimal format.
+ are tabulated as the sequence of coefficients of x^0, x^1, x^2, ...,
+ in hexadecimal format.
G.4.1. Isogeny Parameters
G.4.1.1. Coefficients of u(x)
0 0x670ed14828b6f1791ceb3a9cc0edfe127dee8729c5a72ddf77bb1abaebbba1e8
1 0x1135ca8bd5383cb3545402c8bce2ced14b45c29b241e4751b035f27524a9f932
2 0x3223806ff5f669c430efd74df8389f058d180e2fcffa5cdef3eacecdd2c34771
@@ -3159,23 +3182,23 @@
mapping is called strict if it operates as the OS2ZnE(X,l) function,
except that it fails whenever it would require at least one modular
reduction. Notice that the tight ZnE2OS mapping followed by the
strict OS2ZnE mapping is the identity map (and, hence, ZnE2OS never
fails in this case).
Note that if n is a prime number p, the conversions ZnE2OS and FE2OS
are consistent, as are OS2ZnE and OS2FE. This is, however, no longer
the case if n is a strict prime power.
- The conversion rules for composite n values may be useful, e.g., when
- encoding RSA parameters (or elements of any other non-prime size set
- Z_n, for that matter).
+ The conversion rules for composite (i.e., non-prime) n values may be
+ useful, e.g., when encoding RSA parameters (or elements of any other
+ non-prime size set Z_n, for that matter).
I.7. Ordering Conventions
One can consider various representation functions, depending on bit-
ordering and octet-ordering conventions.
The description below makes use of an auxiliary function (the
reversion function), where the reverse of the string X:=str(x_{l-1},
x_{l-2}, ..., x_1, x_0) is defined to be the string
X':=rev(X):=str(x_0, x_1, ..., x_{l-2}, x_{l-1}). Below, we use this
@@ -3268,32 +3291,33 @@
coordinates (in left-to-right order). Since each coordinate has
known length, this operation is reversible. When appropriate, we
refer to the latter as the octet (rather than the pair)
representation of a point.
NOTE 2: The octet representation of compressed points above
identifies the parity bit t of the curve point in question via the
1-octet representations of the integers 0 and 1. Obviously, other
1-1 mappings are also possible. As an example, with [SEC1], the
parity bit t is represented by 0x02 or 0x03 depending on whether t=0
- or t=1, respectively The same [SEC1] specification represents affine
- points as above (as octet string), but prepends this with the 1-octet
- prefix 0x04, and represents the identity element of the curve as the
- 1-octet string 0x00. This variable-size point representation has the
- property that its 1-octet prefix identifies whether it encodes an
- affine curve point, a compressed point (including parity bit), or the
- identity element, while the remainder of this representation uniquely
- determines the curve point's value. While the description in [SEC1]
- only applies to Weierstrass curves, the description above applies to
- each of the curve models we consider (i.e., these apply to Montgomery
- curves and twisted Edwards curves as well). Collectively, we simply
- refer to this as the "SEC1" point representation.
+ or t=1, respectively. The same [SEC1] specification represents
+ affine points as above (as octet string), but prepends this with the
+ 1-octet prefix 0x04, and represents the identity element of the curve
+ as the 1-octet string 0x00. This variable-size point representation
+ has the property that its 1-octet prefix identifies whether it
+ encodes an affine curve point, a compressed point (including parity
+ bit), or the identity element, while the remainder of this
+ representation uniquely determines the curve point's value. While
+ the description in [SEC1] only applies to Weierstrass curves, the
+ description above applies to each of the curve models we consider
+ (i.e., these apply to Montgomery curves and twisted Edwards curves as
+ well). Collectively, we simply refer to this as the "SEC1" point
+ representation.
Note that elements of a prime field GF(p), where p is a 255-bit prime
number, have a tight representation as a 32-octet string, where a
fixed bit position is always set to zero. (This is the leftmost bit
position of this octet string if one follows the MSB/msb
representation conventions.) This allows the parity bit of a
compressed point (see Appendix H) to be encoded in this bit position
and, thereby, allows a compressed point and an element of GF(p) to be
represented by an octet string of the same length. This is called
the "squeezed" point representation. (We will use this squeezed
@@ -4212,22 +4236,22 @@
value of s). In the second case, one first maps the pair (u1, u2) to
the pair (t1, t2):=(delta*u1^2, delta*u2^2) and subsequently computes
P2compl(t1, t2):=Pcompl(t1) + Pcompl(t2), where Pcompl(t):=P(t) if t
is nonzero and where Pcompl(0):=P1 otherwise. In either case, again,
the resulting mapping is uniquely defined after fixing the points P0
and P1 and the non-square element delta of GF(q).
Appendix L. Curve secp256k1 and Friend
This section illustrates how isogenies can be used to yield curves
- with specific properties (here, for illustrated for the "BitCoin"
- curve secp256k1).
+ with specific properties (here, illustrated for the "BitCoin" curve
+ secp256k1).
L.1. Curve Definition and Alternative Representation
The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined
over the prime field GF(p), with p:=2^256-2^32-2^9-2^8-2^7-2^6-2^4-1,
where a:=0 and b:=7. This curve has order h*n, where h=1 and where n
is a prime number. For this curve, domain parameter a is zero,
whereas b is not. The quadratic twist of this curve has order h1*n1,
where h1 is a 37-bit integer and where n1 is a prime number. For
this curve, the base point is the point (GX, GY).
@@ -4332,21 +4356,21 @@
f976c6a7 8611c800)
L.4. Isogeny Details
The isogeny and dual isogeny are both isogenies with degree l=3.
Both are specified by a triple of polynomials u, v, and w (resp. u',
v', and w') of degree 3, 3, and 1, respectively, with coefficients in
GF(p). The coeffients of each of these polynomials are specified in
Appendix L.4.1 (for the isogeny) and in Appendix L.4.2 (for the dual
isogeny). For each polynomial in variable x, the coefficients are
- tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in
+ tabulated as the sequence of coefficients of x^0, x^1, x^2, ..., in
hexadecimal format.
L.4.1. Isogeny Parameters
L.4.1.1. Coefficients of u(x)
0 0x54
1 0xa4d89db3ed06c81e6143ec2eca9f761d8d17260dc229e1da1f73f714506872a9
@@ -4848,21 +4872,21 @@
f230fa14)
N.4. Isogeny Details
The isogeny and dual isogeny are both isogenies with degree l=2.
Both are specified by a triple of polynomials u, v, and w (resp. u',
v', and w') of degree 2, 2, and 1, respectively, with coefficients in
GF(p). The coeffients of each of these polynomials are specified in
Appendix N.4.1 (for the isogeny) and in Appendix N.4.2 (for the dual
isogeny). For each polynomial in variable x, the coefficients are
- tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in
+ tabulated as the sequence of coefficients of x^0, x^1, x^2, ..., in
hexadecimal format.
N.4.1. Isogeny Parameters
N.4.1.1. Coefficients of u(x)
0 0x01
1 0x55555555555555555555555555555555555555555555555555555554ffffffff
ffffffffffffffffffffffffffffffffffffffffffff3473