--- 1/draft-ietf-lwig-curve-representations-13.txt 2020-11-15 16:13:12.660907984 -0800
+++ 2/draft-ietf-lwig-curve-representations-14.txt 2020-11-15 16:13:12.908914262 -0800
@@ -1,18 +1,18 @@
lwig R. Struik
Internet-Draft Struik Security Consultancy
-Intended status: Informational November 2, 2020
-Expires: May 6, 2021
+Intended status: Standards Track November 15, 2020
+Expires: May 19, 2021
Alternative Elliptic Curve Representations
- draft-ietf-lwig-curve-representations-13
+ draft-ietf-lwig-curve-representations-14
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,21 +33,21 @@
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 May 6, 2021.
+ This Internet-Draft will expire on May 19, 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
@@ -105,38 +105,38 @@
12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 25
12.3.2. COSE Algorithms Registration (1/2) . . . . . . . . . 26
12.3.3. COSE Algorithms Registration (2/2) . . . . . . . . . 26
12.3.4. JOSE Elliptic Curves Registration . . . . . . . . . 26
12.3.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 27
12.3.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 27
13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 28
14. References . . . . . . . . . . . . . . . . . . . . . . . . . 28
14.1. Normative References . . . . . . . . . . . . . . . . . . 28
14.2. Informative References . . . . . . . . . . . . . . . . . 31
- Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 32
+ Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 33
A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 33
A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 33
A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 33
- Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 33
+ Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 34
B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 34
- B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 35
- Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 36
+ B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 36
+ Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 37
C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 37
- C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 37
- C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 38
- Appendix D. Relationships Between Curve Models . . . . . . . . . 39
+ C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 38
+ C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 39
+ Appendix D. Relationships Between Curve Models . . . . . . . . . 40
D.1. Mapping between Twisted Edwards Curves and Montgomery
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 40
D.2. Mapping between Montgomery Curves and Weierstrass Curves 40
D.3. Mapping between Twisted Edwards Curves and Weierstrass
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 41
- Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 41
+ Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 42
E.1. Curve Definition and Alternative Representations . . . . 42
E.2. Switching between Alternative Representations . . . . . . 42
E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 44
Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 46
F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 46
F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 46
F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 47
F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 48
Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 50
G.1. Further Alternative Representations . . . . . . . . . . . 50
@@ -167,59 +167,59 @@
J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 77
J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 79
J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 82
J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 84
Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 86
K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 86
K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 86
K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 86
K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 87
K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 87
- K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 87
+ K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 88
K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 89
K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 90
K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 90
K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 90
K.4.2. Mapping to High-Order Points of Montgomery Curve . . 91
K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 93
K.5. Randomized Representation of Curve Points . . . . . . . . 94
K.6. Completing the Mappings to Curve Points . . . . . . . . . 95
- Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 96
- L.1. Curve Definition and Alternative Representation . . . . . 96
- L.2. Switching Between Representations . . . . . . . . . . . . 97
- L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 97
- L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 99
- L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 99
- L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 99
- Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 100
- M.1. Curve Definition and Alternative Representations . . . . 100
- M.2. Switching between Alternative Representations . . . . . . 101
- M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 102
- Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 105
- N.1. Further Alternative Representations . . . . . . . . . . . 105
- N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 105
- N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 108
- N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 110
- N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 110
- N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 111
- Appendix O. Representation Examples Curve448 Family Members . . 111
- O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 112
- O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 115
- O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 118
- O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 121
- O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 123
- O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 126
- Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 129
- P.1. Conversion to Integers in Z_n via Modular Reduction . . . 129
- P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 130
- P.3. Conversion to Integers in Z_n via the Discard Method . . 130
- Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 131
+ Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 97
+ L.1. Curve Definition and Alternative Representation . . . . . 97
+ L.2. Switching Between Representations . . . . . . . . . . . . 98
+ L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 98
+ L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 100
+ L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 100
+ L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 100
+ Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 101
+ M.1. Curve Definition and Alternative Representations . . . . 101
+ M.2. Switching between Alternative Representations . . . . . . 102
+ M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 103
+ Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 106
+ N.1. Further Alternative Representations . . . . . . . . . . . 106
+ N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 106
+ N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 109
+ N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 111
+ N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 111
+ N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 112
+ Appendix O. Representation Examples Curve448 Family Members . . 112
+ O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 113
+ O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 116
+ O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 119
+ O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 122
+ O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 124
+ O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 127
+ Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 130
+ P.1. Conversion to Integers in Z_n via Modular Reduction . . . 131
+ P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 132
+ P.3. Conversion to Integers in Z_n via the Discard Method . . 133
+ Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 133
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
curve model. These so-called CFRG curves [RFC7748] use the
Montgomery curve model and the model of twisted Edwards curves.
@@ -507,23 +507,24 @@
optimized formulae exist, such as the use of so-called Montgomery
ladders with Montgomery curves [Mont-Ladder] or with Weierstrass
curves [Wei-Ladder], the use of hardcoded a=-3 domain parameter for
Weierstrass curves [ECC-Isogeny], and the use of hardcoded a=-1
domain parameters for twisted Edwards curves [tEd-Formulas]. These
all target reduction of the number of finite field operations
(primarily, finite field multiplications and squarings). Other
optimizations target more efficient modular reductions underlying
these finite field operations, by specifying curves defined over a
field GF(q), where the field size q has a special form or a specific
- bit-size (typically, close to a multiple of a machine word).
- Depending on the implementation strategy, the bit-size of q may also
- facilitate reduced so-called "carry-effects" of integer arithmetic.
+ bit-length (typically, close to a multiple of a machine word).
+ Depending on the implementation strategy, the bit-length of q may
+ also facilitate reduced so-called "carry-effects" of integer
+ arithmetic.
Most curves use a combination of these design philosophies. All NIST
curves [FIPS-186-4] and Brainpool curves [RFC5639] are Weierstrass
curves with a=-3 domain parameter, thus facilitating more efficient
elliptic curve group operations (via so-called Jacobian coordinates).
The NIST curves and the Montgomery curve Curve25519 are defined over
prime fields, where the prime number has a special form, whereas the
Brainpool curves - by design - use a generic prime number. None of
the NIST prime curves, nor the Brainpool curves, can be expressed as
Montgomery or twisted Edwards curves, whereas - conversely -
@@ -966,59 +967,60 @@
Section 2.2 of [RFC5480], after correcting for the error in [SEC1]
(for the correction, see Note in Appendix H.1).
11.2. Encoding of ECDSA Instantiations with PKIX
ECDSA25519, as defined in Section 4.3, is the instantiation of ECDSA
with SHA-256 and with curve Wei25519. With [RFC5480], ECDSA can be
instantiated with suitable elliptic curves and hash functions. This
allows support for ECDSA25519 by instantiating ECDSA with the curve
Wei25519 and the hash function SHA256, where curve Wei25519 is
- identified by its object identifier id-wei25519 (see Section 11.1),
+ identified by its object identifier id-Wei25519 (see Section 11.1),
where ECDSA with SHA256 is identified by the object identifier id-
ecdsa-with-SHA256 (see [RFC5480]), and where all other aspects are
specified in [RFC5480].
ECDSA448, as defined in Section 4.4, is the instantiation of ECDSA
with SHAKE256 with output size d=512 bits and with curve Wei448.
With [RFC5480], ECDSA can be instantiated with suitable elliptic
curves and hash functions. This allows support for ECDSA448 by
instantiating ECDSA with the curve Wei448 and the hash function
SHAKE256 with output size of d=512 bits, where curve Wei448 is
- identified by its object identifier id-wei448 (see Section 11.1),
+ identified by its object identifier id-Wei448 (see Section 11.1),
where ECDSA with SHAKE256 with output size of d=512 bits is
identified by the object identifier id-ecdsa-with-shake256 (see
[RFC8692]), and where all other aspects are specified in [RFC5480].
11.3. Encoding of co-factor ECDH and Other Algorithms with PKIX
With [RFC5480], the algorithm field in the SubjectPublicKeyInfo
structure indicates the algorithm and the elliptic curve domain
parameters for a specific curve, where that specification defines
- three algorithm identifiers (viz. id-ecPublicKey, id-ecdh, and id-
- ecmqv). Each of these algorithms can be instantiated with suitable
+ three algorithm identifiers (viz. id-ecPublicKey, id-ecDH, and id-
+ ecMQV). Each of these algorithms can be instantiated with suitable
alliptic curves, thereby allowing support for their use with the
curves Wei25519 and Wei448, where these curves are identified by
their unique object identifiers id-wei25519 and id-wei448,
- respectively, and where all other aspects are specified in [RFC5480].
+ respectively, (see Section 11.1) and where all other aspects are
+ specified in [RFC5480].
11.4. Encoding of Elliptic-Curve-Based Algorithms with CMS
With [RFC5753], elliptic-curve based algorithms should use one of the
elliptic curve domain parameters specified in [RFC5480], where the
unique name of each such curve is identified by the object identifier
of this curve defined in that document. Each of these algorithms can
be instantiated with suitable elliptic curves, thereby allowing
support for their use with the curves Wei25519 and Wei448, where
these curves are identified by their unique object identifiers id-
- wei25519 and id-wei448, respectively, and where all other aspects are
- specified in [RFC5753].
+ wei25519 and id-wei448, respectively, (see Section 11.1) and where
+ all other aspects are specified in [RFC5753].
12. 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 the scope of
@@ -1490,20 +1492,25 @@
Edwards Curves Revisited", ASIACRYPT 2008, Lecture Notes
in Computer Science, Vol. 5350, New York: Springer-Verlag,
2008.
[Tibouchi]
M. Tibouchi, "Elligator Squared -- Uniform Points on
Elliptic Curves of Prime Order as Uniform Random Strings",
Financial Cryptography 2014, Lecture Notes in Computer
Science, Vol. 8437, New York: Springer-Verlag, 2014.
+ [Tibouchi-cleancut]
+ T. Kim, M. Tibouchi, "Improved Elliptic Curve Hashing and
+ Point Representation", DCC 2017, Des. Codes Cryptogr.,
+ Vol. 82, pp. 161-177, New York: Springer-Verlag, 2017.
+
[Wei-Ladder]
T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve
Multiplication Resistant Against Side Channel Attacks",
Centre for Applied Cryptographic Research, Corr 2002-03,
2002.
Appendix A. Some (Non-Binary) Elliptic Curves
This section defines the three different curve models we consider,
viz. short-Weierstrass curves, Montgomery curves, and twisted Edwards
@@ -1591,20 +1598,27 @@
n*P=O and if it is not the identity element O. (The latter order
check is commonly called full public key validation.)
If R is a point of the curve that is also contained in (P), there is
a unique integer k in the interval [0, l-1] so that R=k*P, where l is
the order of P. 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
of the curve, if such a number exists.
+ Random points R of (P), where P has order l, can be computed by
+ generating a random integer k in the interval [0, l-1] and by
+ subsequently computing R:=k*P, where R has order l/gcd(k,l). In
+ particular, if P is a high-order point, then so is R, unless k is a
+ multiple of n (in which case R is a low-order point). For methods
+ for generating k, see Appendix P.
+
If P is a fixed base point G of the curve, the pair (k, R:=k*G) is
commonly called a public-private key pair, the integer k the private
key, and the point R the corresponding public key. The private key k
can be represented as an integer in the interval [0,n-1], where G has
order n. If this representation is nonzero, R has order n;
otherwise, it has order one and is the identity element O of the
curve.
In this document, a quadratic twist of a curve E defined over a field
GF(q) is a specific curve E' related to E defined over the same
@@ -3443,21 +3456,21 @@
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
representation in Appendix J.) Obviously, other representations
(e.g., those of elements of Z_n) may also have fixed bit values in
certain positions, which can be used to squeeze-in additional
information. Further details are out of scope.
Notice that elements of a prime field GF(p), where p is a prime
- number with bit-size m divisible by eight, have a tight
+ number with bit-length m divisible by eight, have a tight
representation as an (m/8)-octet string, but do not have a bit
position that is always set to zero. Thus, in this case, one cannot
represent a compressed point as an octet string of the same length as
an element of GF(p). However, one can still encode this as an octet
string of length (m/8)+1 (see Note 1 above). If one uses right-
concatenation as in Note 1, but (for historial reasons) represents
the parity bit t of the compressed point in question by 0x00 or 0x80
depending on whether t=0 or t=1, respectively, this is again called
the "squeezed' representation (despite this being somewhat a
misnomer, since each point is now represented as an octet string that
@@ -3791,21 +3804,21 @@
corresponds to the right-concatenation of its X- and Y-coordinates,
each in tight MSB/msb-order, prepended by the string 0x04, where the
reverse procedure is uniquely defined, since elements of GF(p) have a
unique fixed-size representation. The (squeezed) compressed format
repr(Pw) corresponds to the SEC1-compliant compressed format by
extracting the parity bit t from the leftmost bit of the leftmost
octet of repr(Pw), replacing the bit position by the value zero, and
prepending the octet string with 0x02 or 0x03, depending on whether
t=0 or t=1, respectively, where the reverse procedure is uniquely
defined, since GF(p) is a 255-bit prime field. For further details,
- see [SEC1]. Note that, due to the bit-size of the prime p, the
+ see [SEC1]. Note that, due to the bit-length of the prime p, the
squeezed compressed format repr(Pw) is one octet shorter than the
SEC1-compliant compressed format compr(Pw).
A randomized representation (t1, t2) of the point k*Pw in tight MSB/
msb order is given by
t1 446363445988889734093446280484122107283059206243307955388
84223152228795899590
(=0x62af4697 4dd469ac 96c64809 c16c8517 b6a0cee5 40ba0e2e
@@ -4075,21 +4088,27 @@
1/y:=y^{q-2} (since y^{q-1}=1).
If inverses are easy to compute in GF(q), then so are these in
GF(q^2). Further details are out of scope.
The inverses of two nonzero elements y1 and y2 of GF(q) can be
computed by first computing the inverse z of y1*y2 and by
subsequently computing y2*z=:1/y1 and y1*z=:1/y2.
- NOTE: This method can also be used to compute the inverse and a
+ NOTE 1: This method can be used to compute the inverse of a nonzero
+ element y of GF(q) indirectly, as lambda*(lambda*y)^{-1}, where
+ lambda is a random nonzero element of GF(q). This yields an
+ inversion routine (commonly called "blinded inversion") where the
+ inversion operation itself does not leak information on y.
+
+ NOTE 2: This method can also be used to compute the inverse and a
square root, respectively, of two nonzero elements x and y of GF(q)
by first computing a square root z of 1/(y*x^2) (see Appendix K.1)
and by subsequently computing a square root of y as x*y*z and the
inverse of x as x*y*z^2.
K.3. Mappings to Curve Points
One can map elements of GF(q) that are not a square in GF(q) to
points of a Weierstrass curve (see Appendix K.3.1), to points of a
Montgomery curve (see Appendix K.3.2), or to points of a twisted
@@ -4475,26 +4493,64 @@
distribution properties as the original mapping (see NOTE 2 of
Appendix K.5). For each curve in Table 1, these completed mappings
are uniquely defined by the mentioned fixed curve offset P0 and non-
square element delta of GF(q), if one defines P2:=P1:=P0 (henceforth
called the default completed mappings).
NOTE 2: For elliptic curves defined over prime fields (i.e., q:=p)
one can relax the completed mappings above and show that the
statistical properties for randomized representations still hold if
u1 is a random element of a sufficiently large interval in GF(p) and
- if u2 is a random element of a sufficiently large subset of GF(p).
- This allows generating u1 and u2, e.g., each as random bit strings of
- length m-1, where m is the bit-size of p, thereby allowing the pair
- (u1, u2) -- a random (2*m-2)-bit string -- to be used unaltered in
- this construction, without the need to carry out a reduction modulo p
- first. Further details are out of scope of this document.
+ if u2 is a random element of a sufficiently large subset of GF(p)
+ (see, e.g., [Tibouchi-cleancut]). This allows generating u1 and u2,
+ e.g., each as random bit strings of length m-1, where m is the bit-
+ length of p, thereby allowing the pair (u1, u2) -- a random (2*m-2)-
+ bit string -- to be used unaltered in this construction, without the
+ need to carry out a reduction modulo p first. Table 2 illustrates
+ how this can be used to realize randomized representations and
+ completed mappings for each curve in Table 1, where these randomized
+ bit strings have the same byte-length as the (tight) representation
+ of affine curve points. For each curve in Table 2, we refer to this
+ version of the default completed mapping as being the "clean-cut"
+ default completed mapping. Further details are out of scope of this
+ document.
+
+ +--------------------------+-----------------+----------------------+
+ | Curve | left-side | right-side |
+ +--------------------------+-----------------+----------------------+
+ | NIST P-224 [FIPS-186-4] | {u1:224} | {s1:1, s2:1, u2:222} |
+ | NIST P-256 [FIPS-186-4] | {s1:1, u1:255} | {s2:1, u2:255} |
+ | NIST P-384 [FIPS-186-4] | {u1:384} | {s1:1, s2:1, u2:382} |
+ | NIST P-521 [FIPS-186-4] | {s1:1, u1:527} | {s2:1, u2:527} |
+ | Brainpool224r1 [RFC5639] | {s1:1, u1:223} | {s2:1, u2:223} |
+ | Brainpool256r1 [RFC5639] | {s1:1, u1:255} | {s2:1, u2:255} |
+ | Brainpool320r1 [RFC5639] | {s1:1, u1:319} | {s2:1, u2:319} |
+ | Brainpool384r1 [RFC5639] | {s1:1, u1:383} | {s2:1, u2:383} |
+ | Brainpool512r1 [RFC5639] | {s1:1, u1:511} | {s2:1, u2:511} |
+ | Curve25519 [RFC7748] | {s1:1, u1:255} | {s2:1, u2:255} |
+ | Wei25519 [Appendix E.3] | {s1:1, u1:255} | {s2:1, u2:255} |
+ | Wei25519.2 | {s1:1, u1:255} | {s2:1, u2:255} |
+ | [Appendix G.3] | | |
+ | Wei25519.-3 | {s1:1, u1:255} | {s2:1, u2:255} |
+ | [Appendix G.3] | | |
+ | Curve448 [RFC7748] | {u1:448} | {s1:1, s2:1, u2:446} |
+ | Wei448 [Appendix M.3] | {u1:448} | {s1:1, s2:1, u2:446} |
+ | Wei448.1 [Appendix N.3] | {u1:448} | {s1:1, s2:1, u2:446} |
+ | Wei448.-3 [Appendix N.3] | {u1:448} | {s1:1, s2:1, u2:446} |
+ | secp256k1.m | {u1:256} | {s1:1, s2:1, u2:254} |
+ | [Appendix L.3] | | |
+ +--------------------------+-----------------+----------------------+
+
+ Table 2: Randomized representation of curve points, for some curves
+ of practical interest, including curve-specific relative ordering and
+ bit-length of substrings representing the tuple ((u1,s1),(u2,s2)),
+ resulting in the bit string left-side || right-side.
Appendix L. Curve secp256k1 and Friend
This section illustrates how isogenies can be used to yield curves
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
@@ -5318,21 +5372,21 @@
the v-coordinate of the point of Curve448 in question (which, in this
case, are both one, since v and v1 are odd). See Appendix H.2 and
Appendix I for further detail on (squeezed) point compression.
The scalar representation and (squeezed) point representation
illustrated above are consistent with the representations specified
in [RFC7748], except that in [RFC7748] only an affine point's
u-coordinate is represented (i.e., the v-coordinate of any point is
always implicitly assumed to have an even value) and that the
representation of the point at infinity is not specified. (Note that
- due to the bit-size of the prime p, the lossless representation
+ due to the bit-length of the prime p, the lossless representation
requires an additional octet compared to the lossy representation
without v-coordinate.) Another difference is that [RFC7748] allows
non-unique representations of some elements of GF(p), whereas our
representation conventions do not (since tight).
A randomized representation (t1, t2) of the point k*Pm in tight LSB/
msb order is given by
t1 642695971489808425948939115432957219707501931105169269237
122551860533279049805112466411050091592893048844749561382
@@ -5597,23 +5651,23 @@
The SEC1-compliant uncompressed format aff(Pw) of an affine point Pw
corresponds to the right-concatenation of its X- and Y-coordinates,
each in tight MSB/msb-order, prepended by the string 0x04, where the
reverse procedure is uniquely defined, since elements of GF(p) have a
unique fixed-size representation. The (squeezed) compressed format
repr(Pw) corresponds to the SEC1-compliant compressed format by
extracting the parity bit t from the leftmost bit of the leftmost
octet of repr(Pw), and replacing this leftmost octet with 0x02 or
0x03, depending on whether t=0 or t=1, respectively, where the
reverse procedure is uniquely defined. For further details, see
- [SEC1]. Note that, due to the bit-size of the prime p, the squeezed
- compressed format repr(Pw) and the SEC1-compliant compressed format
- compr(Pw) have the same size.
+ [SEC1]. Note that, due to the bit-length of the prime p, the
+ squeezed compressed format repr(Pw) and the SEC1-compliant compressed
+ format compr(Pw) have the same size.
A randomized representation (t1, t2) of the point k*Pw in tight MSB/
msb order is given by
t1 655783099225353926682910498535559663266263823350679216116
172951494291735730803127024621397533084891460609898061397
896825551162064841608
(=0xe6f93655 2765628b accfe61c 7dc6a594 e06fb243 70195ded
74d88a53 fdedc2e8 077e0eff 62fa6a80 fa26b499 1f8796f5
@@ -6006,44 +6060,56 @@
Curve448 of Appendix N.2.
Appendix P. Random Integers in Z_n
Any probability distribution on the interval [0,N-1] can be converted
to a probability distribution on [0,n-1], via a suitable function
that maps inputs from the source distribution [0,N-1] to values in
the interval [0,n-1]. We consider three such functions, each with
the property that if the source distribution on [0,N-1] is
statistically close to the uniform distribution, then so is the
- output distribution on [0,n-1]. In practical applications, one can
- use these functions to convert the output of a cryptographically
- strong random bit generator (where N is a power of two and after
- conversion of the random bit string to an integer via the BS2I
- mapping of Appendix I.2) to a pseudo-random integer in the interval
- [0,n-1], where the bias is small if N is suitably picked.
+ output distribution on [0,n-1]. (Here, we assume n and N to be
+ integers of cryptographic interest, so large.) In practical
+ applications, one can use these functions to convert the output of a
+ cryptographically strong random bit generator (where N is a power of
+ two and after conversion of the random bit string to an integer via
+ the BS2I mapping of Appendix I.2) to a pseudo-random integer in the
+ interval [0,n-1], where the bias is small if N is suitably picked.
We consider mappings that convert an output of the source
distribution to an integer in the interval [0,n-1] via modular
reduction (Appendix P.1), via scaling (Appendix P.2), or via a
membership test (Appendix P.3). For suitably picked N values and not
too poor source distributions, the first two mappings never fail and
any bias introduced by the conversion process can be made negligible
in practice, while the third mapping (if it does not fail) inflates
the bias by a small factor only in practice. (For details, see the
remarks following each of the mappings below.)
- NOTE: Each of the mappings below may yield a zero output value. One
- can modify each such mapping to always yield nonzero outputs, by
+ NOTE: 1 Each of the mappings below may yield a zero output value.
+ One can modify each such mapping to always yield nonzero outputs, by
setting output x to 1 if the original mapping would yield x=0 for a
specific input y and leaving the mapping the same otherwise
(henceforth called the modified conversion function). This
modification has negligible impact on the bias and does yield a
- conversion function to integers in the interval [1,n-1].
+ conversion function to integers in the interval [1,n-1]. A similar
+ remark applies if n=h*n1, where h is a small integer: in that case,
+ one can locally modify each mapping to always yield outputs in the
+ interval [0, h*n1-1] that are not divisible by n1, simply by setting
+ output x to x+1 if the original mapping would otherwise yield x=0
+ (mod n1). (Notice that both modifications coincide if h=1.) These
+ modifications may be useful if one wishes to generate integers in an
+ interval of size n and where one wishes to avoid specific output
+ values (e.g., if one wishes to generate high-order points of a curve
+ of order h*n1, with co-factor h (see Appendix B.1)). For simplicity,
+ we again refer to this as "the" modified conversion function (or
+ h-modified conversion function, if h is not clear from context).
P.1. Conversion to Integers in Z_n via Modular Reduction
This function maps each integer y in the interval [0,N-1] to its
remainder modulo n, i.e., y is mapped to x:= y (mod n).
One can show that the bias introduced by this conversion function is
at most epsilon:=2*rho*(1-rho)/(N/n), where r:=N (mod n) and where
rho:=r/n. Details are out of scope.
@@ -6060,21 +6126,51 @@
introduced by the modular reduction operation is negligible in
practice. The same holds if N is close to a multiple of n (e.g., if
n is close to a power of two and the input distribution is generated
by a high-quality random bit generator with outputs of fixed bit-
length).
Note: In practice, one does not determine the maximum bias epsilon
from n and N, but rather specifies a required upper bound (usually
set to a value at most 2^{-64}) for epsilon and subsequently
determines the minimal value of N for which this upper bound indeed
- applies, as a function of n.
+ applies, as a function of n. Table 3 illustrates this for several
+ curves of practical interest.
+
+ +----------------------------+--------------+----------------+
+ | Curve | eps0=2^{-64} | eps0=2^{-100} |
+ +----------------------------+--------------+----------------+
+ | NIST P-224 [FIPS-186-4] | 224 | 224 |
+ | NIST P-256 [FIPS-186-4] | 288 | 352 |
+ | NIST P-384 [FIPS-186-4] | 384 | 384 |
+ | NIST P-521 [FIPS-186-4] | 521 | 521 |
+ | Brainpool224r1 [RFC5639] | 287 | 323 |
+ | Brainpool256r1 [RFC5639] | 319 | 354 |
+ | Brainpool320r1 [RFC5639] | 379 | 417 |
+ | Brainpool384r1 [RFC5639] | 445 | 482 |
+ | Brainpool512r1 [RFC5639] | 575 | 608 |
+ | Curve25519 [RFC7748] | 252 | 252 |
+ | Wei25519 [Appendix E.3] | 252 | 252 |
+ | Wei25519.2 [Appendix G.3] | 252 | 252 |
+ | Wei25519.-3 [Appendix G.3] | 252 | 252 |
+ | Curve448 [RFC7748] | 446 | 446 |
+ | Wei448 [Appendix M.3] | 446 | 446 |
+ | Wei448.1 [Appendix N.3] | 446 | 446 |
+ | Wei448.-3 [Appendix N.3] | 446 | 446 |
+ | secp256k1.m [Appendix L.3] | 256 | 256 |
+ +----------------------------+--------------+----------------+
+
+ Table 3: Minimum bit-length of N for which the bias (epsilon)
+ introduced by converting integers in Z_N to integers in Z_n via
+ modular reduction or via scaling is lower than the indicated eps0
+ value, for some curves of practical interest (where n is the order of
+ the base point of the curve in question)
P.2. Conversion to Integers in Z_n via Scaling
This function maps each integer y in the interval [0,N-1] to the
integer x:=floor(n*y/N), where the floor function rounds real numbers
downwards to an integer (i.e., floor(z) is the unique integer i for
which z is an element of the interval [i,i+1) of real numbers).
One can show that the bias introduced by this conversion function is
at most epsilon:=2*rho*(1-rho)/(N/n), where r:=N (mod n) and where