draft-ietf-lwig-curve-representations-13.txt   draft-ietf-lwig-curve-representations-14.txt 
lwig R. Struik lwig R. Struik
Internet-Draft Struik Security Consultancy Internet-Draft Struik Security Consultancy
Intended status: Informational November 2, 2020 Intended status: Standards Track November 15, 2020
Expires: May 6, 2021 Expires: May 19, 2021
Alternative Elliptic Curve Representations Alternative Elliptic Curve Representations
draft-ietf-lwig-curve-representations-13 draft-ietf-lwig-curve-representations-14
Abstract Abstract
This document specifies how to represent Montgomery curves and This document specifies how to represent Montgomery curves and
(twisted) Edwards curves as curves in short-Weierstrass form and (twisted) Edwards curves as curves in short-Weierstrass form and
illustrates how this can be used to carry out elliptic curve illustrates how this can be used to carry out elliptic curve
computations using existing implementations of, e.g., ECDSA and ECDH computations using existing implementations of, e.g., ECDSA and ECDH
using NIST prime curves. We also provide extensive background using NIST prime curves. We also provide extensive background
material that may be useful for implementers of elliptic curve material that may be useful for implementers of elliptic curve
cryptography. cryptography.
skipping to change at page 1, line 44 skipping to change at page 1, line 44
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." 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 Notice
Copyright (c) 2020 IETF Trust and the persons identified as the Copyright (c) 2020 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 3, line 26 skipping to change at page 3, line 26
12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 25 12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 25
12.3.2. COSE Algorithms Registration (1/2) . . . . . . . . . 26 12.3.2. COSE Algorithms Registration (1/2) . . . . . . . . . 26
12.3.3. COSE Algorithms Registration (2/2) . . . . . . . . . 26 12.3.3. COSE Algorithms Registration (2/2) . . . . . . . . . 26
12.3.4. JOSE Elliptic Curves Registration . . . . . . . . . 26 12.3.4. JOSE Elliptic Curves Registration . . . . . . . . . 26
12.3.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 27 12.3.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 27
12.3.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 27 12.3.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 27
13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 28 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 28
14. References . . . . . . . . . . . . . . . . . . . . . . . . . 28 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 28
14.1. Normative References . . . . . . . . . . . . . . . . . . 28 14.1. Normative References . . . . . . . . . . . . . . . . . . 28
14.2. Informative References . . . . . . . . . . . . . . . . . 31 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.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 33
A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 33 A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 33
A.3. Twisted Edwards 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.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 34
B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 35 B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 36
Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 36 Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 37
C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 37 C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 37
C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 37 C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 38
C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 38 C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 39
Appendix D. Relationships Between Curve Models . . . . . . . . . 39 Appendix D. Relationships Between Curve Models . . . . . . . . . 40
D.1. Mapping between Twisted Edwards Curves and Montgomery D.1. Mapping between Twisted Edwards Curves and Montgomery
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 40 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 40
D.2. Mapping between Montgomery Curves and Weierstrass Curves 40 D.2. Mapping between Montgomery Curves and Weierstrass Curves 40
D.3. Mapping between Twisted Edwards Curves and Weierstrass D.3. Mapping between Twisted Edwards Curves and Weierstrass
Curves . . . . . . . . . . . . . . . . . . . . . . . . . 41 Curves . . . . . . . . . . . . . . . . . . . . . . . . . 41
Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 41 Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 42
E.1. Curve Definition and Alternative Representations . . . . 42 E.1. Curve Definition and Alternative Representations . . . . 42
E.2. Switching between Alternative Representations . . . . . . 42 E.2. Switching between Alternative Representations . . . . . . 42
E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 44 E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 44
Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 46 Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 46
F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 46 F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 46
F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 46 F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 46
F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 47 F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 47
F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 48 F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 48
Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 50 Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 50
G.1. Further Alternative Representations . . . . . . . . . . . 50 G.1. Further Alternative Representations . . . . . . . . . . . 50
skipping to change at page 4, line 39 skipping to change at page 4, line 39
J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 77 J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 77
J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 79 J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 79
J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 82 J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 82
J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 84 J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 84
Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 86 Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 86
K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 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.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.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 86
K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 87 K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 87
K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 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.2. Mapping to Points of Montgomery Curve . . . . . . . . 89
K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 90 K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 90
K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 90 K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 90
K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 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.2. Mapping to High-Order Points of Montgomery Curve . . 91
K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 93 K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 93
K.5. Randomized Representation of Curve Points . . . . . . . . 94 K.5. Randomized Representation of Curve Points . . . . . . . . 94
K.6. Completing the Mappings to Curve Points . . . . . . . . . 95 K.6. Completing the Mappings to Curve Points . . . . . . . . . 95
Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 96 Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 97
L.1. Curve Definition and Alternative Representation . . . . . 96 L.1. Curve Definition and Alternative Representation . . . . . 97
L.2. Switching Between Representations . . . . . . . . . . . . 97 L.2. Switching Between Representations . . . . . . . . . . . . 98
L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 97 L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 98
L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 99 L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 100
L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 99 L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 100
L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 99 L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 100
Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 100 Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 101
M.1. Curve Definition and Alternative Representations . . . . 100 M.1. Curve Definition and Alternative Representations . . . . 101
M.2. Switching between Alternative Representations . . . . . . 101 M.2. Switching between Alternative Representations . . . . . . 102
M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 102 M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 103
Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 105 Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 106
N.1. Further Alternative Representations . . . . . . . . . . . 105 N.1. Further Alternative Representations . . . . . . . . . . . 106
N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 105 N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 106
N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 108 N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 109
N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 110 N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 111
N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 110 N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 111
N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 111 N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 112
Appendix O. Representation Examples Curve448 Family Members . . 111 Appendix O. Representation Examples Curve448 Family Members . . 112
O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 112 O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 113
O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 115 O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 116
O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 118 O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 119
O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 121 O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 122
O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 123 O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 124
O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 126 O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 127
Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 129 Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 130
P.1. Conversion to Integers in Z_n via Modular Reduction . . . 129 P.1. Conversion to Integers in Z_n via Modular Reduction . . . 131
P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 130 P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 132
P.3. Conversion to Integers in Z_n via the Discard Method . . 130 P.3. Conversion to Integers in Z_n via the Discard Method . . 133
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 131 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 133
1. Fostering Code Reuse with New Elliptic Curves 1. Fostering Code Reuse with New Elliptic Curves
Elliptic curves can be represented using different curve models. Elliptic curves can be represented using different curve models.
Recently, IETF standardized elliptic curves that are claimed to have Recently, IETF standardized elliptic curves that are claimed to have
better performance and improved robustness against "real world" better performance and improved robustness against "real world"
attacks than curves represented in the traditional short-Weierstrass attacks than curves represented in the traditional short-Weierstrass
curve model. These so-called CFRG curves [RFC7748] use the curve model. These so-called CFRG curves [RFC7748] use the
Montgomery curve model and the model of twisted Edwards curves. Montgomery curve model and the model of twisted Edwards curves.
skipping to change at page 11, line 45 skipping to change at page 11, line 45
optimized formulae exist, such as the use of so-called Montgomery optimized formulae exist, such as the use of so-called Montgomery
ladders with Montgomery curves [Mont-Ladder] or with Weierstrass ladders with Montgomery curves [Mont-Ladder] or with Weierstrass
curves [Wei-Ladder], the use of hardcoded a=-3 domain parameter for curves [Wei-Ladder], the use of hardcoded a=-3 domain parameter for
Weierstrass curves [ECC-Isogeny], and the use of hardcoded a=-1 Weierstrass curves [ECC-Isogeny], and the use of hardcoded a=-1
domain parameters for twisted Edwards curves [tEd-Formulas]. These domain parameters for twisted Edwards curves [tEd-Formulas]. These
all target reduction of the number of finite field operations all target reduction of the number of finite field operations
(primarily, finite field multiplications and squarings). Other (primarily, finite field multiplications and squarings). Other
optimizations target more efficient modular reductions underlying optimizations target more efficient modular reductions underlying
these finite field operations, by specifying curves defined over a 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 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). bit-length (typically, close to a multiple of a machine word).
Depending on the implementation strategy, the bit-size of q may also Depending on the implementation strategy, the bit-length of q may
facilitate reduced so-called "carry-effects" of integer arithmetic. also facilitate reduced so-called "carry-effects" of integer
arithmetic.
Most curves use a combination of these design philosophies. All NIST Most curves use a combination of these design philosophies. All NIST
curves [FIPS-186-4] and Brainpool curves [RFC5639] are Weierstrass curves [FIPS-186-4] and Brainpool curves [RFC5639] are Weierstrass
curves with a=-3 domain parameter, thus facilitating more efficient curves with a=-3 domain parameter, thus facilitating more efficient
elliptic curve group operations (via so-called Jacobian coordinates). elliptic curve group operations (via so-called Jacobian coordinates).
The NIST curves and the Montgomery curve Curve25519 are defined over The NIST curves and the Montgomery curve Curve25519 are defined over
prime fields, where the prime number has a special form, whereas the prime fields, where the prime number has a special form, whereas the
Brainpool curves - by design - use a generic prime number. None of Brainpool curves - by design - use a generic prime number. None of
the NIST prime curves, nor the Brainpool curves, can be expressed as the NIST prime curves, nor the Brainpool curves, can be expressed as
Montgomery or twisted Edwards curves, whereas - conversely - Montgomery or twisted Edwards curves, whereas - conversely -
skipping to change at page 21, line 32 skipping to change at page 21, line 32
Section 2.2 of [RFC5480], after correcting for the error in [SEC1] Section 2.2 of [RFC5480], after correcting for the error in [SEC1]
(for the correction, see Note in Appendix H.1). (for the correction, see Note in Appendix H.1).
11.2. Encoding of ECDSA Instantiations with PKIX 11.2. Encoding of ECDSA Instantiations with PKIX
ECDSA25519, as defined in Section 4.3, is the instantiation of ECDSA ECDSA25519, as defined in Section 4.3, is the instantiation of ECDSA
with SHA-256 and with curve Wei25519. With [RFC5480], ECDSA can be with SHA-256 and with curve Wei25519. With [RFC5480], ECDSA can be
instantiated with suitable elliptic curves and hash functions. This instantiated with suitable elliptic curves and hash functions. This
allows support for ECDSA25519 by instantiating ECDSA with the curve allows support for ECDSA25519 by instantiating ECDSA with the curve
Wei25519 and the hash function SHA256, where curve Wei25519 is 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- where ECDSA with SHA256 is identified by the object identifier id-
ecdsa-with-SHA256 (see [RFC5480]), and where all other aspects are ecdsa-with-SHA256 (see [RFC5480]), and where all other aspects are
specified in [RFC5480]. specified in [RFC5480].
ECDSA448, as defined in Section 4.4, is the instantiation of ECDSA 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 SHAKE256 with output size d=512 bits and with curve Wei448.
With [RFC5480], ECDSA can be instantiated with suitable elliptic With [RFC5480], ECDSA can be instantiated with suitable elliptic
curves and hash functions. This allows support for ECDSA448 by curves and hash functions. This allows support for ECDSA448 by
instantiating ECDSA with the curve Wei448 and the hash function instantiating ECDSA with the curve Wei448 and the hash function
SHAKE256 with output size of d=512 bits, where curve Wei448 is 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 where ECDSA with SHAKE256 with output size of d=512 bits is
identified by the object identifier id-ecdsa-with-shake256 (see identified by the object identifier id-ecdsa-with-shake256 (see
[RFC8692]), and where all other aspects are specified in [RFC5480]. [RFC8692]), and where all other aspects are specified in [RFC5480].
11.3. Encoding of co-factor ECDH and Other Algorithms with PKIX 11.3. Encoding of co-factor ECDH and Other Algorithms with PKIX
With [RFC5480], the algorithm field in the SubjectPublicKeyInfo With [RFC5480], the algorithm field in the SubjectPublicKeyInfo
structure indicates the algorithm and the elliptic curve domain structure indicates the algorithm and the elliptic curve domain
parameters for a specific curve, where that specification defines parameters for a specific curve, where that specification defines
three algorithm identifiers (viz. id-ecPublicKey, id-ecdh, and id- three algorithm identifiers (viz. id-ecPublicKey, id-ecDH, and id-
ecmqv). Each of these algorithms can be instantiated with suitable ecMQV). Each of these algorithms can be instantiated with suitable
alliptic curves, thereby allowing support for their use with the alliptic curves, thereby allowing support for their use with the
curves Wei25519 and Wei448, where these curves are identified by curves Wei25519 and Wei448, where these curves are identified by
their unique object identifiers id-wei25519 and id-wei448, 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 11.4. Encoding of Elliptic-Curve-Based Algorithms with CMS
With [RFC5753], elliptic-curve based algorithms should use one of the With [RFC5753], elliptic-curve based algorithms should use one of the
elliptic curve domain parameters specified in [RFC5480], where the elliptic curve domain parameters specified in [RFC5480], where the
unique name of each such curve is identified by the object identifier unique name of each such curve is identified by the object identifier
of this curve defined in that document. Each of these algorithms can of this curve defined in that document. Each of these algorithms can
be instantiated with suitable elliptic curves, thereby allowing be instantiated with suitable elliptic curves, thereby allowing
support for their use with the curves Wei25519 and Wei448, where support for their use with the curves Wei25519 and Wei448, where
these curves are identified by their unique object identifiers id- these curves are identified by their unique object identifiers id-
wei25519 and id-wei448, respectively, and where all other aspects are wei25519 and id-wei448, respectively, (see Section 11.1) and where
specified in [RFC5753]. all other aspects are specified in [RFC5753].
12. IANA Considerations 12. IANA Considerations
Code points are requested for curves Wei25519 and Wei448 and their Code points are requested for curves Wei25519 and Wei448 and their
use with ECDSA and co-factor ECDH, using the representation use with ECDSA and co-factor ECDH, using the representation
conventions of this document. conventions of this document.
New code points would be required in case one wishes to specify one New code points would be required in case one wishes to specify one
or more other "offspring" protocols beyond those exemplified in or more other "offspring" protocols beyond those exemplified in
Section 4.4. Specification hereof is, however, outside the scope of Section 4.4. Specification hereof is, however, outside the scope of
skipping to change at page 32, line 38 skipping to change at page 32, line 38
Edwards Curves Revisited", ASIACRYPT 2008, Lecture Notes Edwards Curves Revisited", ASIACRYPT 2008, Lecture Notes
in Computer Science, Vol. 5350, New York: Springer-Verlag, in Computer Science, Vol. 5350, New York: Springer-Verlag,
2008. 2008.
[Tibouchi] [Tibouchi]
M. Tibouchi, "Elligator Squared -- Uniform Points on M. Tibouchi, "Elligator Squared -- Uniform Points on
Elliptic Curves of Prime Order as Uniform Random Strings", Elliptic Curves of Prime Order as Uniform Random Strings",
Financial Cryptography 2014, Lecture Notes in Computer Financial Cryptography 2014, Lecture Notes in Computer
Science, Vol. 8437, New York: Springer-Verlag, 2014. 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] [Wei-Ladder]
T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve
Multiplication Resistant Against Side Channel Attacks", Multiplication Resistant Against Side Channel Attacks",
Centre for Applied Cryptographic Research, Corr 2002-03, Centre for Applied Cryptographic Research, Corr 2002-03,
2002. 2002.
Appendix A. Some (Non-Binary) Elliptic Curves Appendix A. Some (Non-Binary) Elliptic Curves
This section defines the three different curve models we consider, This section defines the three different curve models we consider,
viz. short-Weierstrass curves, Montgomery curves, and twisted Edwards viz. short-Weierstrass curves, Montgomery curves, and twisted Edwards
skipping to change at page 34, line 45 skipping to change at page 34, line 51
n*P=O and if it is not the identity element O. (The latter order n*P=O and if it is not the identity element O. (The latter order
check is commonly called full public key validation.) check is commonly called full public key validation.)
If R is a point of the curve that is also contained in (P), there is 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 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 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 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 the discrete logarithm of R to the base P for any two points P and R
of the curve, if such a number exists. 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 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 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 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 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; order n. If this representation is nonzero, R has order n;
otherwise, it has order one and is the identity element O of the otherwise, it has order one and is the identity element O of the
curve. curve.
In this document, a quadratic twist of a curve E defined over a field 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 GF(q) is a specific curve E' related to E defined over the same
skipping to change at page 74, line 13 skipping to change at page 74, line 13
compressed point (see Appendix H) to be encoded in this bit position 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 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 represented by an octet string of the same length. This is called
the "squeezed" point representation. (We will use this squeezed the "squeezed" point representation. (We will use this squeezed
representation in Appendix J.) Obviously, other representations representation in Appendix J.) Obviously, other representations
(e.g., those of elements of Z_n) may also have fixed bit values in (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 certain positions, which can be used to squeeze-in additional
information. Further details are out of scope. information. Further details are out of scope.
Notice that elements of a prime field GF(p), where p is a prime 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 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 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 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 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- string of length (m/8)+1 (see Note 1 above). If one uses right-
concatenation as in Note 1, but (for historial reasons) represents concatenation as in Note 1, but (for historial reasons) represents
the parity bit t of the compressed point in question by 0x00 or 0x80 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 depending on whether t=0 or t=1, respectively, this is again called
the "squeezed' representation (despite this being somewhat a the "squeezed' representation (despite this being somewhat a
misnomer, since each point is now represented as an octet string that misnomer, since each point is now represented as an octet string that
skipping to change at page 81, line 31 skipping to change at page 81, line 31
corresponds to the right-concatenation of its X- and Y-coordinates, corresponds to the right-concatenation of its X- and Y-coordinates,
each in tight MSB/msb-order, prepended by the string 0x04, where the 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 reverse procedure is uniquely defined, since elements of GF(p) have a
unique fixed-size representation. The (squeezed) compressed format unique fixed-size representation. The (squeezed) compressed format
repr(Pw) corresponds to the SEC1-compliant compressed format by repr(Pw) corresponds to the SEC1-compliant compressed format by
extracting the parity bit t from the leftmost bit of the leftmost 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 octet of repr(Pw), replacing the bit position by the value zero, and
prepending the octet string with 0x02 or 0x03, depending on whether prepending the octet string with 0x02 or 0x03, depending on whether
t=0 or t=1, respectively, where the reverse procedure is uniquely 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, 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 squeezed compressed format repr(Pw) is one octet shorter than the
SEC1-compliant compressed format compr(Pw). SEC1-compliant compressed format compr(Pw).
A randomized representation (t1, t2) of the point k*Pw in tight MSB/ A randomized representation (t1, t2) of the point k*Pw in tight MSB/
msb order is given by msb order is given by
t1 446363445988889734093446280484122107283059206243307955388 t1 446363445988889734093446280484122107283059206243307955388
84223152228795899590 84223152228795899590
(=0x62af4697 4dd469ac 96c64809 c16c8517 b6a0cee5 40ba0e2e (=0x62af4697 4dd469ac 96c64809 c16c8517 b6a0cee5 40ba0e2e
skipping to change at page 87, line 29 skipping to change at page 87, line 29
1/y:=y^{q-2} (since y^{q-1}=1). 1/y:=y^{q-2} (since y^{q-1}=1).
If inverses are easy to compute in GF(q), then so are these in If inverses are easy to compute in GF(q), then so are these in
GF(q^2). Further details are out of scope. GF(q^2). Further details are out of scope.
The inverses of two nonzero elements y1 and y2 of GF(q) can be 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 computed by first computing the inverse z of y1*y2 and by
subsequently computing y2*z=:1/y1 and y1*z=:1/y2. 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) 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) 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 and by subsequently computing a square root of y as x*y*z and the
inverse of x as x*y*z^2. inverse of x as x*y*z^2.
K.3. Mappings to Curve Points K.3. Mappings to Curve Points
One can map elements of GF(q) that are not a square in GF(q) to 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 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 Montgomery curve (see Appendix K.3.2), or to points of a twisted
skipping to change at page 96, line 27 skipping to change at page 96, line 27
distribution properties as the original mapping (see NOTE 2 of distribution properties as the original mapping (see NOTE 2 of
Appendix K.5). For each curve in Table 1, these completed mappings Appendix K.5). For each curve in Table 1, these completed mappings
are uniquely defined by the mentioned fixed curve offset P0 and non- 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 square element delta of GF(q), if one defines P2:=P1:=P0 (henceforth
called the default completed mappings). called the default completed mappings).
NOTE 2: For elliptic curves defined over prime fields (i.e., q:=p) NOTE 2: For elliptic curves defined over prime fields (i.e., q:=p)
one can relax the completed mappings above and show that the one can relax the completed mappings above and show that the
statistical properties for randomized representations still hold if statistical properties for randomized representations still hold if
u1 is a random element of a sufficiently large interval in GF(p) and 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). 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 (see, e.g., [Tibouchi-cleancut]). This allows generating u1 and u2,
length m-1, where m is the bit-size of p, thereby allowing the pair e.g., each as random bit strings of length m-1, where m is the bit-
(u1, u2) -- a random (2*m-2)-bit string -- to be used unaltered in length of p, thereby allowing the pair (u1, u2) -- a random (2*m-2)-
this construction, without the need to carry out a reduction modulo p bit string -- to be used unaltered in this construction, without the
first. Further details are out of scope of this document. 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 Appendix L. Curve secp256k1 and Friend
This section illustrates how isogenies can be used to yield curves This section illustrates how isogenies can be used to yield curves
with specific properties (here, illustrated for the "BitCoin" curve with specific properties (here, illustrated for the "BitCoin" curve
secp256k1). secp256k1).
L.1. Curve Definition and Alternative Representation L.1. Curve Definition and Alternative Representation
The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined
skipping to change at page 114, line 24 skipping to change at page 115, line 24
the v-coordinate of the point of Curve448 in question (which, in this 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 case, are both one, since v and v1 are odd). See Appendix H.2 and
Appendix I for further detail on (squeezed) point compression. Appendix I for further detail on (squeezed) point compression.
The scalar representation and (squeezed) point representation The scalar representation and (squeezed) point representation
illustrated above are consistent with the representations specified illustrated above are consistent with the representations specified
in [RFC7748], except that in [RFC7748] only an affine point's in [RFC7748], except that in [RFC7748] only an affine point's
u-coordinate is represented (i.e., the v-coordinate of any point is u-coordinate is represented (i.e., the v-coordinate of any point is
always implicitly assumed to have an even value) and that the always implicitly assumed to have an even value) and that the
representation of the point at infinity is not specified. (Note that 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 requires an additional octet compared to the lossy representation
without v-coordinate.) Another difference is that [RFC7748] allows without v-coordinate.) Another difference is that [RFC7748] allows
non-unique representations of some elements of GF(p), whereas our non-unique representations of some elements of GF(p), whereas our
representation conventions do not (since tight). representation conventions do not (since tight).
A randomized representation (t1, t2) of the point k*Pm in tight LSB/ A randomized representation (t1, t2) of the point k*Pm in tight LSB/
msb order is given by msb order is given by
t1 642695971489808425948939115432957219707501931105169269237 t1 642695971489808425948939115432957219707501931105169269237
122551860533279049805112466411050091592893048844749561382 122551860533279049805112466411050091592893048844749561382
skipping to change at page 120, line 18 skipping to change at page 121, line 18
The SEC1-compliant uncompressed format aff(Pw) of an affine point Pw The SEC1-compliant uncompressed format aff(Pw) of an affine point Pw
corresponds to the right-concatenation of its X- and Y-coordinates, corresponds to the right-concatenation of its X- and Y-coordinates,
each in tight MSB/msb-order, prepended by the string 0x04, where the 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 reverse procedure is uniquely defined, since elements of GF(p) have a
unique fixed-size representation. The (squeezed) compressed format unique fixed-size representation. The (squeezed) compressed format
repr(Pw) corresponds to the SEC1-compliant compressed format by repr(Pw) corresponds to the SEC1-compliant compressed format by
extracting the parity bit t from the leftmost bit of the leftmost extracting the parity bit t from the leftmost bit of the leftmost
octet of repr(Pw), and replacing this leftmost octet with 0x02 or octet of repr(Pw), and replacing this leftmost octet with 0x02 or
0x03, depending on whether t=0 or t=1, respectively, where the 0x03, depending on whether t=0 or t=1, respectively, where the
reverse procedure is uniquely defined. For further details, see reverse procedure is uniquely defined. For further details, see
[SEC1]. Note that, due to the bit-size of the prime p, the squeezed [SEC1]. Note that, due to the bit-length of the prime p, the
compressed format repr(Pw) and the SEC1-compliant compressed format squeezed compressed format repr(Pw) and the SEC1-compliant compressed
compr(Pw) have the same size. format compr(Pw) have the same size.
A randomized representation (t1, t2) of the point k*Pw in tight MSB/ A randomized representation (t1, t2) of the point k*Pw in tight MSB/
msb order is given by msb order is given by
t1 655783099225353926682910498535559663266263823350679216116 t1 655783099225353926682910498535559663266263823350679216116
172951494291735730803127024621397533084891460609898061397 172951494291735730803127024621397533084891460609898061397
896825551162064841608 896825551162064841608
(=0xe6f93655 2765628b accfe61c 7dc6a594 e06fb243 70195ded (=0xe6f93655 2765628b accfe61c 7dc6a594 e06fb243 70195ded
74d88a53 fdedc2e8 077e0eff 62fa6a80 fa26b499 1f8796f5 74d88a53 fdedc2e8 077e0eff 62fa6a80 fa26b499 1f8796f5
skipping to change at page 129, line 13 skipping to change at page 130, line 13
Curve448 of Appendix N.2. Curve448 of Appendix N.2.
Appendix P. Random Integers in Z_n Appendix P. Random Integers in Z_n
Any probability distribution on the interval [0,N-1] can be converted Any probability distribution on the interval [0,N-1] can be converted
to a probability distribution on [0,n-1], via a suitable function 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 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 interval [0,n-1]. We consider three such functions, each with
the property that if the source distribution on [0,N-1] is the property that if the source distribution on [0,N-1] is
statistically close to the uniform distribution, then so is the statistically close to the uniform distribution, then so is the
output distribution on [0,n-1]. In practical applications, one can output distribution on [0,n-1]. (Here, we assume n and N to be
use these functions to convert the output of a cryptographically integers of cryptographic interest, so large.) In practical
strong random bit generator (where N is a power of two and after applications, one can use these functions to convert the output of a
conversion of the random bit string to an integer via the BS2I cryptographically strong random bit generator (where N is a power of
mapping of Appendix I.2) to a pseudo-random integer in the interval two and after conversion of the random bit string to an integer via
[0,n-1], where the bias is small if N is suitably picked. 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 We consider mappings that convert an output of the source
distribution to an integer in the interval [0,n-1] via modular distribution to an integer in the interval [0,n-1] via modular
reduction (Appendix P.1), via scaling (Appendix P.2), or via a reduction (Appendix P.1), via scaling (Appendix P.2), or via a
membership test (Appendix P.3). For suitably picked N values and not membership test (Appendix P.3). For suitably picked N values and not
too poor source distributions, the first two mappings never fail and too poor source distributions, the first two mappings never fail and
any bias introduced by the conversion process can be made negligible any bias introduced by the conversion process can be made negligible
in practice, while the third mapping (if it does not fail) inflates 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 the bias by a small factor only in practice. (For details, see the
remarks following each of the mappings below.) remarks following each of the mappings below.)
NOTE: Each of the mappings below may yield a zero output value. One NOTE: 1 Each of the mappings below may yield a zero output value.
can modify each such mapping to always yield nonzero outputs, by 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 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 specific input y and leaving the mapping the same otherwise
(henceforth called the modified conversion function). This (henceforth called the modified conversion function). This
modification has negligible impact on the bias and does yield a 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 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 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). 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 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 at most epsilon:=2*rho*(1-rho)/(N/n), where r:=N (mod n) and where
rho:=r/n. Details are out of scope. rho:=r/n. Details are out of scope.
skipping to change at page 130, line 18 skipping to change at page 131, line 34
introduced by the modular reduction operation is negligible in 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 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 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- by a high-quality random bit generator with outputs of fixed bit-
length). length).
Note: In practice, one does not determine the maximum bias epsilon Note: In practice, one does not determine the maximum bias epsilon
from n and N, but rather specifies a required upper bound (usually from n and N, but rather specifies a required upper bound (usually
set to a value at most 2^{-64}) for epsilon and subsequently set to a value at most 2^{-64}) for epsilon and subsequently
determines the minimal value of N for which this upper bound indeed 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 P.2. Conversion to Integers in Z_n via Scaling
This function maps each integer y in the interval [0,N-1] to the 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 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 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). 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 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 at most epsilon:=2*rho*(1-rho)/(N/n), where r:=N (mod n) and where
 End of changes. 28 change blocks. 
76 lines changed or deleted 176 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/