--- 1/draft-ietf-lwig-curve-representations-14.txt 2020-12-02 08:13:10.443415535 -0800
+++ 2/draft-ietf-lwig-curve-representations-15.txt 2020-12-02 08:13:10.575417180 -0800
@@ -1,18 +1,18 @@
lwig R. Struik
Internet-Draft Struik Security Consultancy
-Intended status: Standards Track November 15, 2020
-Expires: May 19, 2021
+Intended status: Standards Track December 2, 2020
+Expires: June 5, 2021
Alternative Elliptic Curve Representations
- draft-ietf-lwig-curve-representations-14
+ draft-ietf-lwig-curve-representations-15
Abstract
This document specifies how to represent Montgomery curves and
(twisted) Edwards curves as curves in short-Weierstrass form and
illustrates how this can be used to carry out elliptic curve
computations using existing implementations of, e.g., ECDSA and ECDH
using NIST prime curves. We also provide extensive background
material that may be useful for implementers of elliptic curve
cryptography.
@@ -33,21 +33,21 @@
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
- This Internet-Draft will expire on May 19, 2021.
+ This Internet-Draft will expire on June 5, 2021.
Copyright Notice
Copyright (c) 2020 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
@@ -176,50 +176,50 @@
K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 87
K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 88
K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 89
K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 90
K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 90
K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 90
K.4.2. Mapping to High-Order Points of Montgomery Curve . . 91
K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 93
K.5. Randomized Representation of Curve Points . . . . . . . . 94
K.6. Completing the Mappings to Curve Points . . . . . . . . . 95
- Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 97
- L.1. Curve Definition and Alternative Representation . . . . . 97
- L.2. Switching Between Representations . . . . . . . . . . . . 98
- L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 98
- L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 100
- L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 100
- L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 100
- Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 101
- M.1. Curve Definition and Alternative Representations . . . . 101
- M.2. Switching between Alternative Representations . . . . . . 102
- M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 103
- Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 106
- N.1. Further Alternative Representations . . . . . . . . . . . 106
- N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 106
- N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 109
- N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 111
- N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 111
- N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 112
- Appendix O. Representation Examples Curve448 Family Members . . 112
- O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 113
- O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 116
- O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 119
- O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 122
- O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 124
- O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 127
- Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 130
- P.1. Conversion to Integers in Z_n via Modular Reduction . . . 131
- P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 132
- P.3. Conversion to Integers in Z_n via the Discard Method . . 133
- Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 133
+ Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 98
+ L.1. Curve Definition and Alternative Representation . . . . . 99
+ L.2. Switching Between Representations . . . . . . . . . . . . 99
+ L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 99
+ L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 101
+ L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 101
+ L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 102
+ Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 102
+ M.1. Curve Definition and Alternative Representations . . . . 102
+ M.2. Switching between Alternative Representations . . . . . . 103
+ M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 104
+ Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 107
+ N.1. Further Alternative Representations . . . . . . . . . . . 107
+ N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 107
+ N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 110
+ N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 112
+ N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 112
+ N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 113
+ Appendix O. Representation Examples Curve448 Family Members . . 113
+ O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 114
+ O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 117
+ O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 120
+ O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 123
+ O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 126
+ O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 128
+ Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 131
+ P.1. Conversion to Integers in Z_n via Modular Reduction . . . 132
+ P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 133
+ P.3. Conversion to Integers in Z_n via the Discard Method . . 134
+ Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 134
1. Fostering Code Reuse with New Elliptic Curves
Elliptic curves can be represented using different curve models.
Recently, IETF standardized elliptic curves that are claimed to have
better performance and improved robustness against "real world"
attacks than curves represented in the traditional short-Weierstrass
curve model. These so-called CFRG curves [RFC7748] use the
Montgomery curve model and the model of twisted Edwards curves.
@@ -319,21 +319,21 @@
specified in Appendix E.3 and Appendix G.3, see Appendix J.
4. Examples
4.1. Implementation of X25519
RFC 7748 [RFC7748] specifies the use of X25519, a co-factor Diffie-
Hellman key agreement scheme, with instantiation by the Montgomery
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
- 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
curve Curve25519 as a point of the Weierstrass curve Wei25519; (2)
instantiating the co-factor Diffie-Hellman key agreement scheme of
the NIST specification with the resulting point and Wei25519 domain
parameters; (3) representing the key resulting from this scheme
(which is a point of the curve Wei25519 in Weierstrass form) as a
point of the Montgomery curve Curve25519. The representation change
can be implemented via a simple wrapper and involves a single modular
addition (see Appendix E.2). Using this method has the additional
advantage that one can reuse the public-private key pair routines,
@@ -357,21 +357,21 @@
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
Ed25519. As before, the representation change can be implemented via
a simple wrapper. Note that the Montgomery ladder specified in
Section 5 of RFC7748 [RFC7748] does not provide sufficient
information to reconstruct R':=(u, v) (since it does not compute the
v-coordinate of R'). However, this deficiency can be remedied by
using a slightly modified version of the Montgomery ladder that
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
- 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
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
with other Weierstrass curves (that satisfy additional cryptographic
criteria). In particular, one can instantiate this scheme with the
Weierstrass curve Wei25519 and the hash function SHA-256
[FIPS-180-4], where an implementation may generate an ephemeral
public-private key pair for Wei25519 by (1) internally carrying out
@@ -525,21 +525,21 @@
elliptic curve group operations (via so-called Jacobian coordinates).
The NIST curves and the Montgomery curve Curve25519 are defined over
prime fields, where the prime number has a special form, whereas the
Brainpool curves - by design - use a generic prime number. None of
the NIST prime curves, nor the Brainpool curves, can be expressed as
Montgomery or twisted Edwards curves, whereas - conversely -
Montgomery curves and twisted curves can be expressed as Weierstrass
curves.
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
obviously does not result in an implementation of these CFRG curves
that exploits the specific structure of the underlying field or other
specific domain parameters (since generic). Reuse of generic code,
therefore, may result in a less computationally efficient curve
implementation than would have been possible if the implementation
had specifically targeted Curve25519 or Edwards25519 alone (with the
overall cost differential estimated to be somewhere in the interval
[1.00-1.25]). If existing generic code offers hardware support,
however, the overall speed may still be larger, since less efficient
@@ -644,21 +644,22 @@
indicates the entity holding this private key. Reuse of this public
key with more than one protocol or more than one protocol
instantiation may, therefore, allow traceability of this entity. It
may also allow correlation of meta-data communicated with this common
data element (e.g., different addressing information), even if an
observer cannot technically verify the binding of this meta-data.
The randomized representation described in Appendix K.5 allows random
curve points to be represented as random pairs of field elements,
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
This section defines algorithm encodings and representations enabling
the use of the curves Wei25519 and Wei448 and their use with ECDH and
ECDSA with JOSE [RFC7518] and COSE [RFC8152] messages.
All octet string encodings below use the MSB/msb-ordering conventions
as defined in Appendix I.7. For CBOR representation details, we
refer to [RFC7049]; for base64url encodings, we refer to [RFC4648].
@@ -796,76 +797,78 @@
defined in Section 4.4). Note that, in this case, the "alg" name
uniquely defines the curve (and, thereby, implicitly the underlying
"crv" parameter) and the underlying hash function.
10.2.1. Encoding of ECDSA Instantiations with COSE
Instantiations of ECDSA used with COSE use the following encodings of
inputs and outputs:
a. The message m is the COSE_Sign structure as specified in
- Section 4.1 of [RFC8152], converted to a bit-string, using the
+ Section 4.1 of [RFC8152], converted to a bit string, using the
OS2BS mapping of Appendix I.4;
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
name of the curve used with this particular instantiation of
ECDSA;
c. The Cose signature is encoded as the right-concatenation of the
octet string representations of the coordinates of the signature
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
ZnE2OS mapping of Appendix I.6, converted to a CBOR byte string.
Note that, since we use a tight representation, this right-
concatenated octet string has fixed size 2*l, where the parameter
- l is uniquely defined by the set Z_n in question. The inverse
- mapping results by checking that the purported encoded signature
- (after CBOR decoding) has indeed size 2*l, and by converting the
- left-side and right-side halves of this octet string (each of
- length l) to, respectively, the integers r and s in Z_n, via the
- strict OS2ZnE mapping of Appendix I.6.
+ l is uniquely defined by the set Z_n in question (where n is the
+ (prime) order of the base point of the curve in question). The
+ inverse mapping results by checking that the purported encoded
+ signature (after CBOR decoding) has indeed size 2*l, and by
+ converting the left-side and right-side halves of this octet
+ 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
present, it MUST be set to the (unique) name of this particular
instantiation of ECDSA and the "crv" parameter MUST be set to the
(unique) name of the corresponding curve; if the "key_ops" field is
present, it MUST include "sign" when creating an ECDSA signature and
it MUST include "verify" when verifying an ECDSA signature.
10.2.2. Encoding of ECDSA Instantiations with JOSE
Instantiations of ECDSA used with JOSE use the following encodings of
inputs and outputs:
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;
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
name of the curve used with this particular instantiation of
ECDSA;
c. The JWS signature is encoded as the right-concatenation of the
octet string representations of the coordinates of the signature
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
using the base64url encoding. Note that, since we use a tight
representation, this right-concatenated octet string has fixed
size 2*l, where the parameter l is uniquely defined by the set
- Z_n in question. The inverse mapping results by checking that
- the purported encoded signature (after base64url decoding) has
- indeed size 2*l, and by converting the left-side and right-side
- halves of this octet string (each of length l) to, respectively,
- the integers r and s in Z_n, via the strict OS2ZnE mapping of
- Appendix I.6.
+ Z_n in question (where n is the (prime) order of the base point
+ of the curve in question). The inverse mapping results by
+ checking that the purported encoded signature (after base64url
+ decoding) has indeed size 2*l, and by converting the left-side
+ and right-side halves of this octet 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 JOSE key for this algorithm, if the "alg" field is
present, it MUST be set to the (unique) name of this particular
instantiation of ECDSA and the "crv" parameter MUST be set to the
(unique) name of the corresponding curve; if the "key_ops" field is
present, it MUST include "sign" when creating an ECDSA signature and
it MUST include "verify" when verifying an ECDSA signature; if the
JWK _use_ field is present, its value MUST be "sig".
10.3. Using ECDH25519 and ECDH448 with COSE and JOSE
@@ -4337,25 +4340,25 @@
f(u0)*f(u).) Thus, Q(t,s) can be computed without the need to fully
compute P(t).
+----------------------------+------------------------+-------------+
| Curve | Fixed curve offset P0 | Non-Square |
+----------------------------+------------------------+-------------+
| 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-384 [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 |
- | Brainpool256r1 [RFC5639] | Base point (Gx, Gy) | -1 |
- | Brainpool320r1 [RFC5639] | Base point (Gx, Gy) | -1 |
- | Brainpool384r1 [RFC5639] | Base point (Gx, Gy) | -1 |
- | Brainpool512r1 [RFC5639] | P0:=(3,y), y even | -1 |
+ | brainpoolP224r1 [RFC5639] | Base point (Gx, Gy) | -1 |
+ | brainpoolP256r1 [RFC5639] | Base point (Gx, Gy) | -1 |
+ | brainpoolP320r1 [RFC5639] | Base point (Gx, Gy) | -1 |
+ | brainpoolP384r1 [RFC5639] | Base point (Gx, Gy) | -1 |
+ | brainpoolP512r1 [RFC5639] | P0:=(3,y), y even | -1 |
| Curve25519 [RFC7748] | P0:=(90,v), v even | 2 |
| Wei25519 [Appendix E.3] | P0:=(3,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 |
| Curve448 [RFC7748] | P0:=(50,v), v even | -1 |
| Wei448 [Appendix M.3] | P0:=(18,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 |
| secp256k1.m [Appendix L.3] | P0:=(0,y), y even | -1 |
+----------------------------+------------------------+-------------+
@@ -4502,55 +4505,116 @@
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)
(see, e.g., [Tibouchi-cleancut]). This allows generating u1 and u2,
e.g., each as random bit strings of length m-1, where m is the bit-
length of p, thereby allowing the pair (u1, u2) -- a random (2*m-2)-
bit string -- to be used unaltered in this construction, without the
need to carry out a reduction modulo p first. Table 2 illustrates
how this can be used to realize randomized representations and
completed mappings for each curve in Table 1, where these randomized
bit strings have the same byte-length as the (tight) representation
- of affine curve points. For each curve in Table 2, we refer to this
- version of the default completed mapping as being the "clean-cut"
- default completed mapping. Further details are out of scope of this
- document.
+ of affine curve points. (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.)
+ 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 |
+--------------------------+-----------------+----------------------+
| 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} |
+ | brainpoolP224r1 | {s1:1, u1:223} | {s2:1, u2:223} |
+ | [RFC5639] | | |
+ | brainpoolP256r1 | {s1:1, u1:255} | {s2:1, u2:255} |
+ | [RFC5639] | | |
+ | 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} |
| 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.
+ 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
This section illustrates how isogenies can be used to yield curves
with specific properties (here, illustrated for the "BitCoin" curve
secp256k1).
L.1. Curve Definition and Alternative Representation
The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined
@@ -6078,22 +6150,22 @@
We consider mappings that convert an output of the source
distribution to an integer in the interval [0,n-1] via modular
reduction (Appendix P.1), via scaling (Appendix P.2), or via a
membership test (Appendix P.3). For suitably picked N values and not
too poor source distributions, the first two mappings never fail and
any bias introduced by the conversion process can be made negligible
in practice, while the third mapping (if it does not fail) inflates
the bias by a small factor only in practice. (For details, see the
remarks following each of the mappings below.)
- NOTE: 1 Each of the mappings below may yield a zero output value.
- One can modify each such mapping to always yield nonzero outputs, by
+ NOTE: Each of the mappings below may yield a zero output value. One
+ can modify each such mapping to always yield nonzero outputs, by
setting output x to 1 if the original mapping would yield x=0 for a
specific input y and leaving the mapping the same otherwise
(henceforth called the modified conversion function). This
modification has negligible impact on the bias and does yield a
conversion function to integers in the interval [1,n-1]. 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
@@ -6125,52 +6197,52 @@
bit-length of N is sufficiently larger than that of n, the bias
introduced by the modular reduction operation is negligible in
practice. The same holds if N is close to a multiple of n (e.g., if
n is close to a power of two and the input distribution is generated
by a high-quality random bit generator with outputs of fixed bit-
length).
Note: In practice, one does not determine the maximum bias epsilon
from n and N, but rather specifies a required upper bound (usually
set to a value at most 2^{-64}) for epsilon and subsequently
- determines the minimal value of N for which this upper bound indeed
- applies, as a function of n. Table 3 illustrates this for several
- curves of practical interest.
+ determines the minimal value of N (where N is a power of two) for
+ which this upper bound indeed applies, as a function of n. Table 4
+ 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 |
+ | brainpoolP224r1 [RFC5639] | 287 | 323 |
+ | brainpoolP256r1 [RFC5639] | 319 | 354 |
+ | brainpoolP320r1 [RFC5639] | 379 | 417 |
+ | brainpoolP384r1 [RFC5639] | 445 | 482 |
+ | brainpoolP512r1 [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
+ Table 4: Minimum value of m for which the bias (epsilon) introduced
+ 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
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
This function maps each integer y in the interval [0,N-1] to the
integer x:=floor(n*y/N), where the floor function rounds real numbers
downwards to an integer (i.e., floor(z) is the unique integer i for
which z is an element of the interval [i,i+1) of real numbers).
One can show that the bias introduced by this conversion function is
at most epsilon:=2*rho*(1-rho)/(N/n), where r:=N (mod n) and where