draft-ietf-lwig-curve-representations-14.txt   draft-ietf-lwig-curve-representations-15.txt 
lwig R. Struik lwig R. Struik
Internet-Draft Struik Security Consultancy Internet-Draft Struik Security Consultancy
Intended status: Standards Track November 15, 2020 Intended status: Standards Track December 2, 2020
Expires: May 19, 2021 Expires: June 5, 2021
Alternative Elliptic Curve Representations Alternative Elliptic Curve Representations
draft-ietf-lwig-curve-representations-14 draft-ietf-lwig-curve-representations-15
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 19, 2021. This Internet-Draft will expire on June 5, 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 4, line 48 skipping to change at page 4, line 48
K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 87 K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 87
K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 88 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 . . . . . . . . . . . . . 97 Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 98
L.1. Curve Definition and Alternative Representation . . . . . 97 L.1. Curve Definition and Alternative Representation . . . . . 99
L.2. Switching Between Representations . . . . . . . . . . . . 98 L.2. Switching Between Representations . . . . . . . . . . . . 99
L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 98 L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 99
L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 100 L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 101
L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 100 L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 101
L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 100 L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 102
Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 101 Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 102
M.1. Curve Definition and Alternative Representations . . . . 101 M.1. Curve Definition and Alternative Representations . . . . 102
M.2. Switching between Alternative Representations . . . . . . 102 M.2. Switching between Alternative Representations . . . . . . 103
M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 103 M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 104
Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 106 Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 107
N.1. Further Alternative Representations . . . . . . . . . . . 106 N.1. Further Alternative Representations . . . . . . . . . . . 107
N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 106 N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 107
N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 109 N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 110
N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 111 N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 112
N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 111 N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 112
N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 112 N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 113
Appendix O. Representation Examples Curve448 Family Members . . 112 Appendix O. Representation Examples Curve448 Family Members . . 113
O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 113 O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 114
O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 116 O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 117
O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 119 O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 120
O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 122 O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 123
O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 124 O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 126
O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 127 O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 128
Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 130 Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 131
P.1. Conversion to Integers in Z_n via Modular Reduction . . . 131 P.1. Conversion to Integers in Z_n via Modular Reduction . . . 132
P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 132 P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 133
P.3. Conversion to Integers in Z_n via the Discard Method . . 133 P.3. Conversion to Integers in Z_n via the Discard Method . . 134
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 133 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 134
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 7, line 48 skipping to change at page 7, line 48
specified in Appendix E.3 and Appendix G.3, see Appendix J. specified in Appendix E.3 and Appendix G.3, see Appendix J.
4. Examples 4. Examples
4.1. Implementation of X25519 4.1. Implementation of X25519
RFC 7748 [RFC7748] specifies the use of X25519, a co-factor Diffie- RFC 7748 [RFC7748] specifies the use of X25519, a co-factor Diffie-
Hellman key agreement scheme, with instantiation by the Montgomery Hellman key agreement scheme, with instantiation by the Montgomery
curve Curve25519. This key agreement scheme was already specified in curve Curve25519. This key agreement scheme was already specified in
Section 6.1.2.2 of NIST SP 800-56a [SP-800-56a] for elliptic curves Section 6.1.2.2 of NIST SP 800-56a [SP-800-56a] for elliptic curves
in short Weierstrass form. Hence, one can implement X25519 using in short-Weierstrass form. Hence, one can implement X25519 using
existing NIST routines by (1) representing a point of the Montgomery existing NIST routines by (1) representing a point of the Montgomery
curve Curve25519 as a point of the Weierstrass curve Wei25519; (2) curve Curve25519 as a point of the Weierstrass curve Wei25519; (2)
instantiating the co-factor Diffie-Hellman key agreement scheme of instantiating the co-factor Diffie-Hellman key agreement scheme of
the NIST specification with the resulting point and Wei25519 domain the NIST specification with the resulting point and Wei25519 domain
parameters; (3) representing the key resulting from this scheme parameters; (3) representing the key resulting from this scheme
(which is a point of the curve Wei25519 in Weierstrass form) as a (which is a point of the curve Wei25519 in Weierstrass form) as a
point of the Montgomery curve Curve25519. The representation change point of the Montgomery curve Curve25519. The representation change
can be implemented via a simple wrapper and involves a single modular can be implemented via a simple wrapper and involves a single modular
addition (see Appendix E.2). Using this method has the additional addition (see Appendix E.2). Using this method has the additional
advantage that one can reuse the public-private key pair routines, advantage that one can reuse the public-private key pair routines,
skipping to change at page 8, line 38 skipping to change at page 8, line 38
generating a public-private key pair (k, R':=k*G') for Curve25519; generating a public-private key pair (k, R':=k*G') for Curve25519;
(2) representing this public-private key as the pair (k, R:=k*G) for (2) representing this public-private key as the pair (k, R:=k*G) for
Ed25519. As before, the representation change can be implemented via Ed25519. As before, the representation change can be implemented via
a simple wrapper. Note that the Montgomery ladder specified in a simple wrapper. Note that the Montgomery ladder specified in
Section 5 of RFC7748 [RFC7748] does not provide sufficient Section 5 of RFC7748 [RFC7748] does not provide sufficient
information to reconstruct R':=(u, v) (since it does not compute the information to reconstruct R':=(u, v) (since it does not compute the
v-coordinate of R'). However, this deficiency can be remedied by v-coordinate of R'). However, this deficiency can be remedied by
using a slightly modified version of the Montgomery ladder that using a slightly modified version of the Montgomery ladder that
includes reconstruction of the v-coordinate of R':=k*G' at the end of includes reconstruction of the v-coordinate of R':=k*G' at the end of
the Montgomery ladder (which uses the v-coordinate of the base point the Montgomery ladder (which uses the v-coordinate of the base point
of Curve25519 as well). For details, see Appendix C.1. of Curve25519 as well). For details, see Appendix C.2.
4.3. Specification of ECDSA25519 4.3. Specification of ECDSA25519
FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and FIPS Pub 186-4 [FIPS-186-4] specifies the signature scheme ECDSA and
can be instantiated not just with the NIST prime curves, but also can be instantiated not just with the NIST prime curves, but also
with other Weierstrass curves (that satisfy additional cryptographic with other Weierstrass curves (that satisfy additional cryptographic
criteria). In particular, one can instantiate this scheme with the criteria). In particular, one can instantiate this scheme with the
Weierstrass curve Wei25519 and the hash function SHA-256 Weierstrass curve Wei25519 and the hash function SHA-256
[FIPS-180-4], where an implementation may generate an ephemeral [FIPS-180-4], where an implementation may generate an ephemeral
public-private key pair for Wei25519 by (1) internally carrying out public-private key pair for Wei25519 by (1) internally carrying out
skipping to change at page 12, line 15 skipping to change at page 12, line 15
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 -
Montgomery curves and twisted curves can be expressed as Weierstrass Montgomery curves and twisted curves can be expressed as Weierstrass
curves. curves.
While use of Wei25519 allows reuse of existing generic code that While use of Wei25519 allows reuse of existing generic code that
implements short Weierstrass curves, such as the NIST curve P-256, to implements short-Weierstrass curves, such as the NIST curve P-256, to
also implement the CFRG curves Curve25519 or Edwards25519, this also implement the CFRG curves Curve25519 or Edwards25519, this
obviously does not result in an implementation of these CFRG curves obviously does not result in an implementation of these CFRG curves
that exploits the specific structure of the underlying field or other that exploits the specific structure of the underlying field or other
specific domain parameters (since generic). Reuse of generic code, specific domain parameters (since generic). Reuse of generic code,
therefore, may result in a less computationally efficient curve therefore, may result in a less computationally efficient curve
implementation than would have been possible if the implementation implementation than would have been possible if the implementation
had specifically targeted Curve25519 or Edwards25519 alone (with the had specifically targeted Curve25519 or Edwards25519 alone (with the
overall cost differential estimated to be somewhere in the interval overall cost differential estimated to be somewhere in the interval
[1.00-1.25]). If existing generic code offers hardware support, [1.00-1.25]). If existing generic code offers hardware support,
however, the overall speed may still be larger, since less efficient however, the overall speed may still be larger, since less efficient
skipping to change at page 14, line 39 skipping to change at page 14, line 39
indicates the entity holding this private key. Reuse of this public indicates the entity holding this private key. Reuse of this public
key with more than one protocol or more than one protocol key with more than one protocol or more than one protocol
instantiation may, therefore, allow traceability of this entity. It instantiation may, therefore, allow traceability of this entity. It
may also allow correlation of meta-data communicated with this common may also allow correlation of meta-data communicated with this common
data element (e.g., different addressing information), even if an data element (e.g., different addressing information), even if an
observer cannot technically verify the binding of this meta-data. observer cannot technically verify the binding of this meta-data.
The randomized representation described in Appendix K.5 allows random The randomized representation described in Appendix K.5 allows random
curve points to be represented as random pairs of field elements, curve points to be represented as random pairs of field elements,
thereby assisting in obfuscating the presence of these curve points thereby assisting in obfuscating the presence of these curve points
in some applications. in some applications. For representations as random binary strings,
see Appendix K.6.
10. Using Wei25519 and Wei448 with COSE and JOSE 10. Using Wei25519 and Wei448 with COSE and JOSE
This section defines algorithm encodings and representations enabling This section defines algorithm encodings and representations enabling
the use of the curves Wei25519 and Wei448 and their use with ECDH and the use of the curves Wei25519 and Wei448 and their use with ECDH and
ECDSA with JOSE [RFC7518] and COSE [RFC8152] messages. ECDSA with JOSE [RFC7518] and COSE [RFC8152] messages.
All octet string encodings below use the MSB/msb-ordering conventions All octet string encodings below use the MSB/msb-ordering conventions
as defined in Appendix I.7. For CBOR representation details, we as defined in Appendix I.7. For CBOR representation details, we
refer to [RFC7049]; for base64url encodings, we refer to [RFC4648]. refer to [RFC7049]; for base64url encodings, we refer to [RFC4648].
skipping to change at page 17, line 49 skipping to change at page 17, line 49
defined in Section 4.4). Note that, in this case, the "alg" name defined in Section 4.4). Note that, in this case, the "alg" name
uniquely defines the curve (and, thereby, implicitly the underlying uniquely defines the curve (and, thereby, implicitly the underlying
"crv" parameter) and the underlying hash function. "crv" parameter) and the underlying hash function.
10.2.1. Encoding of ECDSA Instantiations with COSE 10.2.1. Encoding of ECDSA Instantiations with COSE
Instantiations of ECDSA used with COSE use the following encodings of Instantiations of ECDSA used with COSE use the following encodings of
inputs and outputs: inputs and outputs:
a. The message m is the COSE_Sign structure as specified in a. The message m is the COSE_Sign structure as specified in
Section 4.1 of [RFC8152], converted to a bit-string, using the Section 4.1 of [RFC8152], converted to a bit string, using the
OS2BS mapping of Appendix I.4; OS2BS mapping of Appendix I.4;
b. The public key Q and the private key d are encoded as specified b. The public key Q and the private key d are encoded as specified
in Section 10.1.1, where the "crv" parameter is set to the unique in Section 10.1.1, where the "crv" parameter is set to the unique
name of the curve used with this particular instantiation of name of the curve used with this particular instantiation of
ECDSA; ECDSA;
c. The Cose signature is encoded as the right-concatenation of the c. The Cose signature is encoded as the right-concatenation of the
octet string representations of the coordinates of the signature octet string representations of the coordinates of the signature
pair (r, s), in left-to-right order, where r and s are each pair (r, s), in left-to-right order, where r and s are each
represented as octet strings in tight MSB/msb-order using the represented as octet strings in tight MSB/msb-order using the
ZnE2OS mapping of Appendix I.6, converted to a CBOR byte string. ZnE2OS mapping of Appendix I.6, converted to a CBOR byte string.
Note that, since we use a tight representation, this right- Note that, since we use a tight representation, this right-
concatenated octet string has fixed size 2*l, where the parameter concatenated octet string has fixed size 2*l, where the parameter
l is uniquely defined by the set Z_n in question. The inverse l is uniquely defined by the set Z_n in question (where n is the
mapping results by checking that the purported encoded signature (prime) order of the base point of the curve in question). The
(after CBOR decoding) has indeed size 2*l, and by converting the inverse mapping results by checking that the purported encoded
left-side and right-side halves of this octet string (each of signature (after CBOR decoding) has indeed size 2*l, and by
length l) to, respectively, the integers r and s in Z_n, via the converting the left-side and right-side halves of this octet
strict OS2ZnE mapping of Appendix I.6. string (each of length l) to, respectively, the integers r and s
in Z_n, via the strict OS2ZnE mapping of Appendix I.6.
When using a COSE key for this algorithm, if the "alg" field is When using a COSE key for this algorithm, if the "alg" field is
present, it MUST be set to the (unique) name of this particular present, it MUST be set to the (unique) name of this particular
instantiation of ECDSA and the "crv" parameter MUST be set to the instantiation of ECDSA and the "crv" parameter MUST be set to the
(unique) name of the corresponding curve; if the "key_ops" field is (unique) name of the corresponding curve; if the "key_ops" field is
present, it MUST include "sign" when creating an ECDSA signature and present, it MUST include "sign" when creating an ECDSA signature and
it MUST include "verify" when verifying an ECDSA signature. it MUST include "verify" when verifying an ECDSA signature.
10.2.2. Encoding of ECDSA Instantiations with JOSE 10.2.2. Encoding of ECDSA Instantiations with JOSE
Instantiations of ECDSA used with JOSE use the following encodings of Instantiations of ECDSA used with JOSE use the following encodings of
inputs and outputs: inputs and outputs:
a. The message m is the JWS Signing Input as specified in [RFC7515], a. The message m is the JWS Signing Input as specified in [RFC7515],
converted to a bit-string, using the OS2BS mapping of converted to a bit string, using the OS2BS mapping of
Appendix I.4; Appendix I.4;
b. The public key and the private key are encoded as specified in b. The public key and the private key are encoded as specified in
Section 10.1.2, where the "crv" parameter is set to the unique Section 10.1.2, where the "crv" parameter is set to the unique
name of the curve used with this particular instantiation of name of the curve used with this particular instantiation of
ECDSA; ECDSA;
c. The JWS signature is encoded as the right-concatenation of the c. The JWS signature is encoded as the right-concatenation of the
octet string representations of the coordinates of the signature octet string representations of the coordinates of the signature
pair (r, s), in left-to-right order, where r and s are each pair (r, s), in left-to-right order, where r and s are each
represented in tight MSB/msb-order (see Appendix I.7), converted represented in tight MSB/msb-order (see Appendix I.7), converted
using the base64url encoding. Note that, since we use a tight using the base64url encoding. Note that, since we use a tight
representation, this right-concatenated octet string has fixed representation, this right-concatenated octet string has fixed
size 2*l, where the parameter l is uniquely defined by the set size 2*l, where the parameter l is uniquely defined by the set
Z_n in question. The inverse mapping results by checking that Z_n in question (where n is the (prime) order of the base point
the purported encoded signature (after base64url decoding) has of the curve in question). The inverse mapping results by
indeed size 2*l, and by converting the left-side and right-side checking that the purported encoded signature (after base64url
halves of this octet string (each of length l) to, respectively, decoding) has indeed size 2*l, and by converting the left-side
the integers r and s in Z_n, via the strict OS2ZnE mapping of and right-side halves of this octet string (each of length l) to,
Appendix I.6. respectively, the integers r and s in Z_n, via the strict OS2ZnE
mapping of Appendix I.6.
When using a JOSE key for this algorithm, if the "alg" field is When using a JOSE key for this algorithm, if the "alg" field is
present, it MUST be set to the (unique) name of this particular present, it MUST be set to the (unique) name of this particular
instantiation of ECDSA and the "crv" parameter MUST be set to the instantiation of ECDSA and the "crv" parameter MUST be set to the
(unique) name of the corresponding curve; if the "key_ops" field is (unique) name of the corresponding curve; if the "key_ops" field is
present, it MUST include "sign" when creating an ECDSA signature and present, it MUST include "sign" when creating an ECDSA signature and
it MUST include "verify" when verifying an ECDSA signature; if the it MUST include "verify" when verifying an ECDSA signature; if the
JWK _use_ field is present, its value MUST be "sig". JWK _use_ field is present, its value MUST be "sig".
10.3. Using ECDH25519 and ECDH448 with COSE and JOSE 10.3. Using ECDH25519 and ECDH448 with COSE and JOSE
skipping to change at page 93, line 12 skipping to change at page 93, line 12
f(u0)*f(u).) Thus, Q(t,s) can be computed without the need to fully f(u0)*f(u).) Thus, Q(t,s) can be computed without the need to fully
compute P(t). compute P(t).
+----------------------------+------------------------+-------------+ +----------------------------+------------------------+-------------+
| Curve | Fixed curve offset P0 | Non-Square | | Curve | Fixed curve offset P0 | Non-Square |
+----------------------------+------------------------+-------------+ +----------------------------+------------------------+-------------+
| NIST P-224 [FIPS-186-4] | Base point (Gx,Gy) | 11 | | NIST P-224 [FIPS-186-4] | Base point (Gx,Gy) | 11 |
| NIST P-256 [FIPS-186-4] | P0:=(0,y), y even | -1 | | NIST P-256 [FIPS-186-4] | P0:=(0,y), y even | -1 |
| NIST P-384 [FIPS-186-4] | P0:=(0,y), y even | -1 | | NIST P-384 [FIPS-186-4] | P0:=(0,y), y even | -1 |
| NIST P-521 [FIPS-186-4] | P0:=(0,y), y even | -1 | | NIST P-521 [FIPS-186-4] | P0:=(0,y), y even | -1 |
| Brainpool224r1 [RFC5639] | Base point (Gx, Gy) | -1 | | brainpoolP224r1 [RFC5639] | Base point (Gx, Gy) | -1 |
| Brainpool256r1 [RFC5639] | Base point (Gx, Gy) | -1 | | brainpoolP256r1 [RFC5639] | Base point (Gx, Gy) | -1 |
| Brainpool320r1 [RFC5639] | Base point (Gx, Gy) | -1 | | brainpoolP320r1 [RFC5639] | Base point (Gx, Gy) | -1 |
| Brainpool384r1 [RFC5639] | Base point (Gx, Gy) | -1 | | brainpoolP384r1 [RFC5639] | Base point (Gx, Gy) | -1 |
| Brainpool512r1 [RFC5639] | P0:=(3,y), y even | -1 | | brainpoolP512r1 [RFC5639] | P0:=(3,y), y even | -1 |
| Curve25519 [RFC7748] | P0:=(90,v), v even | 2 | | Curve25519 [RFC7748] | P0:=(90,v), v even | 2 |
| Wei25519 [Appendix E.3] | P0:=(3,y), y even | 2 | | Wei25519 [Appendix E.3] | P0:=(3,y), y even | 2 |
| Wei25519.2 [Appendix G.3] | P0:=(244,y), y even | 2 | | Wei25519.2 [Appendix G.3] | P0:=(244,y), y even | 2 |
| Wei25519.-3 [Appendix G.3] | P0:=(41,y), y even | 2 | | Wei25519.-3 [Appendix G.3] | P0:=(41,y), y even | 2 |
| Curve448 [RFC7748] | P0:=(50,v), v even | -1 | | Curve448 [RFC7748] | P0:=(50,v), v even | -1 |
| Wei448 [Appendix M.3] | P0:=(18,y), y even | -1 | | Wei448 [Appendix M.3] | P0:=(18,y), y even | -1 |
| Wei448.1 [Appendix N.3] | P0:=(10,y), y even | -1 | | Wei448.1 [Appendix N.3] | P0:=(10,y), y even | -1 |
| Wei448.-3 [Appendix N.3] | P0:=(8,y), y even | -1 | | Wei448.-3 [Appendix N.3] | P0:=(8,y), y even | -1 |
| secp256k1.m [Appendix L.3] | P0:=(0,y), y even | -1 | | secp256k1.m [Appendix L.3] | P0:=(0,y), y even | -1 |
+----------------------------+------------------------+-------------+ +----------------------------+------------------------+-------------+
skipping to change at page 96, line 36 skipping to change at page 96, line 36
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)
(see, e.g., [Tibouchi-cleancut]). This allows generating u1 and u2, (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- 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)- 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 bit string -- to be used unaltered in this construction, without the
need to carry out a reduction modulo p first. Table 2 illustrates need to carry out a reduction modulo p first. Table 2 illustrates
how this can be used to realize randomized representations and how this can be used to realize randomized representations and
completed mappings for each curve in Table 1, where these randomized completed mappings for each curve in Table 1, where these randomized
bit strings have the same byte-length as the (tight) representation 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 of affine curve points. (Here, the field elements u1 and u2 are
version of the default completed mapping as being the "clean-cut" obtained from their bit string representations using the b2O mapping
default completed mapping. Further details are out of scope of this of Appendix I.2 and the (non-strict) OS2FE mapping of Appendix I.5.)
document. For each curve in Table 2, we refer to this version of the default
completed mapping as being the "clean-cut" default completed mapping.
+--------------------------+-----------------+----------------------+ +--------------------------+-----------------+----------------------+
| Curve | left-side | right-side | | Curve | left-side | right-side |
+--------------------------+-----------------+----------------------+ +--------------------------+-----------------+----------------------+
| NIST P-224 [FIPS-186-4] | {u1:224} | {s1:1, s2:1, u2:222} | | 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-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-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} | | NIST P-521 [FIPS-186-4] | {s1:1, u1:527} | {s2:1, u2:527} |
| Brainpool224r1 [RFC5639] | {s1:1, u1:223} | {s2:1, u2:223} | | brainpoolP224r1 | {s1:1, u1:223} | {s2:1, u2:223} |
| Brainpool256r1 [RFC5639] | {s1:1, u1:255} | {s2:1, u2:255} | | [RFC5639] | | |
| Brainpool320r1 [RFC5639] | {s1:1, u1:319} | {s2:1, u2:319} | | brainpoolP256r1 | {s1:1, u1:255} | {s2:1, u2:255} |
| Brainpool384r1 [RFC5639] | {s1:1, u1:383} | {s2:1, u2:383} | | [RFC5639] | | |
| Brainpool512r1 [RFC5639] | {s1:1, u1:511} | {s2:1, u2:511} | | brainpoolP320r1 | {s1:1, u1:319} | {s2:1, u2:319} |
| [RFC5639] | | |
| brainpoolP384r1 | {s1:1, u1:383} | {s2:1, u2:383} |
| [RFC5639] | | |
| brainpoolP512r1 | {s1:1, u1:511} | {s2:1, u2:511} |
| [RFC5639] | | |
| Curve25519 [RFC7748] | {s1:1, u1:255} | {s2:1, u2:255} | | Curve25519 [RFC7748] | {s1:1, u1:255} | {s2:1, u2:255} |
| Wei25519 [Appendix E.3] | {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} | | Wei25519.2 | {s1:1, u1:255} | {s2:1, u2:255} |
| [Appendix G.3] | | | | [Appendix G.3] | | |
| Wei25519.-3 | {s1:1, u1:255} | {s2:1, u2:255} | | Wei25519.-3 | {s1:1, u1:255} | {s2:1, u2:255} |
| [Appendix G.3] | | | | [Appendix G.3] | | |
| Curve448 [RFC7748] | {u1:448} | {s1:1, s2:1, u2:446} | | Curve448 [RFC7748] | {u1:448} | {s1:1, s2:1, u2:446} |
| Wei448 [Appendix M.3] | {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.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} | | Wei448.-3 [Appendix N.3] | {u1:448} | {s1:1, s2:1, u2:446} |
| secp256k1.m | {u1:256} | {s1:1, s2:1, u2:254} | | secp256k1.m | {u1:256} | {s1:1, s2:1, u2:254} |
| [Appendix L.3] | | | | [Appendix L.3] | | |
+--------------------------+-----------------+----------------------+ +--------------------------+-----------------+----------------------+
Table 2: Randomized representation of curve points, for some curves Table 2: Randomized representation of curve points, for some curves
of practical interest, including curve-specific relative ordering and of practical interest, including curve-specific relative ordering and
bit-length of substrings representing the tuple ((u1,s1),(u2,s2)), bit-length of substrings representing the tuple ((u1,s1),(u2,s2)),
resulting in the bit string left-side || right-side. resulting in the bit string left-side || right-side. (Tailored
towards avoiding modular reductions in mappings to curve points.)
Table 3 shows an alternative arrangement, tailored towards optimizing
the efficiency of computing randomized representations of curve
points (see Appendix K.5), rather than towards avoiding modular
reductions in the mappings to curve points. (Here, we used
randomized representations of elements of GF(p), when appropriate,
and the bias upper bound 2^{-64} from Table 4.) For each curve in
Table 3, we refer to this version of the default completed mapping as
being the "point-randomization-optimized" default completed mapping
(where both versions coincide if the prime number p is relatively
close to a power of two). (Here, the field elements u1 and u2 are
obtained from their bit string representations using the b2O mapping
of Appendix I.2 and the (non-strict) OS2FE mapping of Appendix I.5.)
Suitability of each of these completed mappings is application-
specific (and also depends on the maximum bias one can tolerate).
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] | {u1:288} | {s1:1, s2:1, u2:222} |
| 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} |
| brainpoolP224r1 | {s1:1, u1:287} | {s2:1, u2:159} |
| [RFC5639] | | |
| brainpoolP256r1 | {s1:1, u1:319} | {s2:1, u2:191} |
| [RFC5639] | | |
| brainpoolP320r1 | {s1:1, u1:383} | {s2:1, u2:255} |
| [RFC5639] | | |
| brainpoolP384r1 | {s1:1, u1:447} | {s2:1, u2:319} |
| [RFC5639] | | |
| brainpoolP512r1 | {s1:1, u1:575} | {s2:1, u2:447} |
| [RFC5639] | | |
| 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 3: 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. (Tailored
towards efficient computation of randomized representations of curve
points.)
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 130, line 31 skipping to change at page 131, line 36
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: 1 Each of the mappings below may yield a zero output value. NOTE: Each of the mappings below may yield a zero output value. One
One can modify each such mapping to always yield nonzero outputs, by 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]. A similar 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, 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 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 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 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 (mod n1). (Notice that both modifications coincide if h=1.) These
skipping to change at page 131, line 33 skipping to change at page 132, line 35
bit-length of N is sufficiently larger than that of n, the bias bit-length of N is sufficiently larger than that of n, the bias
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 (where N is a power of two) for
applies, as a function of n. Table 3 illustrates this for several which this upper bound indeed applies, as a function of n. Table 4
curves of practical interest. illustrates this for several curves of practical interest.
+----------------------------+--------------+----------------+ +----------------------------+--------------+----------------+
| Curve | eps0=2^{-64} | eps0=2^{-100} | | Curve | eps0=2^{-64} | eps0=2^{-100} |
+----------------------------+--------------+----------------+ +----------------------------+--------------+----------------+
| NIST P-224 [FIPS-186-4] | 224 | 224 | | NIST P-224 [FIPS-186-4] | 224 | 224 |
| NIST P-256 [FIPS-186-4] | 288 | 352 | | NIST P-256 [FIPS-186-4] | 288 | 352 |
| NIST P-384 [FIPS-186-4] | 384 | 384 | | NIST P-384 [FIPS-186-4] | 384 | 384 |
| NIST P-521 [FIPS-186-4] | 521 | 521 | | NIST P-521 [FIPS-186-4] | 521 | 521 |
| Brainpool224r1 [RFC5639] | 287 | 323 | | brainpoolP224r1 [RFC5639] | 287 | 323 |
| Brainpool256r1 [RFC5639] | 319 | 354 | | brainpoolP256r1 [RFC5639] | 319 | 354 |
| Brainpool320r1 [RFC5639] | 379 | 417 | | brainpoolP320r1 [RFC5639] | 379 | 417 |
| Brainpool384r1 [RFC5639] | 445 | 482 | | brainpoolP384r1 [RFC5639] | 445 | 482 |
| Brainpool512r1 [RFC5639] | 575 | 608 | | brainpoolP512r1 [RFC5639] | 575 | 608 |
| Curve25519 [RFC7748] | 252 | 252 | | Curve25519 [RFC7748] | 252 | 252 |
| Wei25519 [Appendix E.3] | 252 | 252 | | Wei25519 [Appendix E.3] | 252 | 252 |
| Wei25519.2 [Appendix G.3] | 252 | 252 | | Wei25519.2 [Appendix G.3] | 252 | 252 |
| Wei25519.-3 [Appendix G.3] | 252 | 252 | | Wei25519.-3 [Appendix G.3] | 252 | 252 |
| Curve448 [RFC7748] | 446 | 446 | | Curve448 [RFC7748] | 446 | 446 |
| Wei448 [Appendix M.3] | 446 | 446 | | Wei448 [Appendix M.3] | 446 | 446 |
| Wei448.1 [Appendix N.3] | 446 | 446 | | Wei448.1 [Appendix N.3] | 446 | 446 |
| Wei448.-3 [Appendix N.3] | 446 | 446 | | Wei448.-3 [Appendix N.3] | 446 | 446 |
| secp256k1.m [Appendix L.3] | 256 | 256 | | secp256k1.m [Appendix L.3] | 256 | 256 |
+----------------------------+--------------+----------------+ +----------------------------+--------------+----------------+
Table 3: Minimum bit-length of N for which the bias (epsilon) Table 4: Minimum value of m for which the bias (epsilon) introduced
introduced by converting integers in Z_N to integers in Z_n via by converting integers in Z_N, where N:=2^m, to integers in Z_n via
modular reduction or via scaling is lower than the indicated eps0 modular reduction or via scaling is lower than the indicated eps0
value, for some curves of practical interest (where n is the order of value, for some curves of practical interest (where n is the order of
the base point of the curve in question) 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. 21 change blocks. 
80 lines changed or deleted 144 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/