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/ |