draft-ietf-lwig-curve-representations-13.txt | draft-ietf-lwig-curve-representations-14.txt | |||
---|---|---|---|---|

lwig R. Struik | lwig R. Struik | |||

Internet-Draft Struik Security Consultancy | Internet-Draft Struik Security Consultancy | |||

Intended status: Informational November 2, 2020 | Intended status: Standards Track November 15, 2020 | |||

Expires: May 6, 2021 | Expires: May 19, 2021 | |||

Alternative Elliptic Curve Representations | Alternative Elliptic Curve Representations | |||

draft-ietf-lwig-curve-representations-13 | draft-ietf-lwig-curve-representations-14 | |||

Abstract | Abstract | |||

This document specifies how to represent Montgomery curves and | This document specifies how to represent Montgomery curves and | |||

(twisted) Edwards curves as curves in short-Weierstrass form and | (twisted) Edwards curves as curves in short-Weierstrass form and | |||

illustrates how this can be used to carry out elliptic curve | illustrates how this can be used to carry out elliptic curve | |||

computations using existing implementations of, e.g., ECDSA and ECDH | computations using existing implementations of, e.g., ECDSA and ECDH | |||

using NIST prime curves. We also provide extensive background | using NIST prime curves. We also provide extensive background | |||

material that may be useful for implementers of elliptic curve | material that may be useful for implementers of elliptic curve | |||

cryptography. | cryptography. | |||

skipping to change at page 1, line 44 ¶ | skipping to change at page 1, line 44 ¶ | |||

Internet-Drafts are working documents of the Internet Engineering | Internet-Drafts are working documents of the Internet Engineering | |||

Task Force (IETF). Note that other groups may also distribute | Task Force (IETF). Note that other groups may also distribute | |||

working documents as Internet-Drafts. The list of current Internet- | working documents as Internet-Drafts. The list of current Internet- | |||

Drafts is at https://datatracker.ietf.org/drafts/current/. | Drafts is at https://datatracker.ietf.org/drafts/current/. | |||

Internet-Drafts are draft documents valid for a maximum of six months | Internet-Drafts are draft documents valid for a maximum of six months | |||

and may be updated, replaced, or obsoleted by other documents at any | and may be updated, replaced, or obsoleted by other documents at any | |||

time. It is inappropriate to use Internet-Drafts as reference | time. It is inappropriate to use Internet-Drafts as reference | |||

material or to cite them other than as "work in progress." | material or to cite them other than as "work in progress." | |||

This Internet-Draft will expire on May 6, 2021. | This Internet-Draft will expire on May 19, 2021. | |||

Copyright Notice | Copyright Notice | |||

Copyright (c) 2020 IETF Trust and the persons identified as the | Copyright (c) 2020 IETF Trust and the persons identified as the | |||

document authors. All rights reserved. | document authors. All rights reserved. | |||

This document is subject to BCP 78 and the IETF Trust's Legal | This document is subject to BCP 78 and the IETF Trust's Legal | |||

Provisions Relating to IETF Documents | Provisions Relating to IETF Documents | |||

(https://trustee.ietf.org/license-info) in effect on the date of | (https://trustee.ietf.org/license-info) in effect on the date of | |||

publication of this document. Please review these documents | publication of this document. Please review these documents | |||

skipping to change at page 3, line 26 ¶ | skipping to change at page 3, line 26 ¶ | |||

12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 25 | 12.3.1. COSE Elliptic Curves Registration . . . . . . . . . 25 | |||

12.3.2. COSE Algorithms Registration (1/2) . . . . . . . . . 26 | 12.3.2. COSE Algorithms Registration (1/2) . . . . . . . . . 26 | |||

12.3.3. COSE Algorithms Registration (2/2) . . . . . . . . . 26 | 12.3.3. COSE Algorithms Registration (2/2) . . . . . . . . . 26 | |||

12.3.4. JOSE Elliptic Curves Registration . . . . . . . . . 26 | 12.3.4. JOSE Elliptic Curves Registration . . . . . . . . . 26 | |||

12.3.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 27 | 12.3.5. JOSE Algorithms Registration (1/2) . . . . . . . . . 27 | |||

12.3.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 27 | 12.3.6. JOSE Algorithms Registration (2/2) . . . . . . . . . 27 | |||

13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 28 | 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 28 | |||

14. References . . . . . . . . . . . . . . . . . . . . . . . . . 28 | 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 28 | |||

14.1. Normative References . . . . . . . . . . . . . . . . . . 28 | 14.1. Normative References . . . . . . . . . . . . . . . . . . 28 | |||

14.2. Informative References . . . . . . . . . . . . . . . . . 31 | 14.2. Informative References . . . . . . . . . . . . . . . . . 31 | |||

Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 32 | Appendix A. Some (Non-Binary) Elliptic Curves . . . . . . . . . 33 | |||

A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 33 | A.1. Curves in Short-Weierstrass Form . . . . . . . . . . . . 33 | |||

A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 33 | A.2. Montgomery Curves . . . . . . . . . . . . . . . . . . . . 33 | |||

A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 33 | A.3. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 33 | |||

Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 33 | Appendix B. Elliptic Curve Nomenclature and Finite Fields . . . 34 | |||

B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 34 | B.1. Elliptic Curve Nomenclature . . . . . . . . . . . . . . . 34 | |||

B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 35 | B.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 36 | |||

Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 36 | Appendix C. Elliptic Curve Group Operations . . . . . . . . . . 37 | |||

C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 37 | C.1. Group Laws for Weierstrass Curves . . . . . . . . . . . . 37 | |||

C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 37 | C.2. Group Laws for Montgomery Curves . . . . . . . . . . . . 38 | |||

C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 38 | C.3. Group Laws for Twisted Edwards Curves . . . . . . . . . . 39 | |||

Appendix D. Relationships Between Curve Models . . . . . . . . . 39 | Appendix D. Relationships Between Curve Models . . . . . . . . . 40 | |||

D.1. Mapping between Twisted Edwards Curves and Montgomery | D.1. Mapping between Twisted Edwards Curves and Montgomery | |||

Curves . . . . . . . . . . . . . . . . . . . . . . . . . 40 | Curves . . . . . . . . . . . . . . . . . . . . . . . . . 40 | |||

D.2. Mapping between Montgomery Curves and Weierstrass Curves 40 | D.2. Mapping between Montgomery Curves and Weierstrass Curves 40 | |||

D.3. Mapping between Twisted Edwards Curves and Weierstrass | D.3. Mapping between Twisted Edwards Curves and Weierstrass | |||

Curves . . . . . . . . . . . . . . . . . . . . . . . . . 41 | Curves . . . . . . . . . . . . . . . . . . . . . . . . . 41 | |||

Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 41 | Appendix E. Curve25519 and Cousins . . . . . . . . . . . . . . . 42 | |||

E.1. Curve Definition and Alternative Representations . . . . 42 | E.1. Curve Definition and Alternative Representations . . . . 42 | |||

E.2. Switching between Alternative Representations . . . . . . 42 | E.2. Switching between Alternative Representations . . . . . . 42 | |||

E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 44 | E.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 44 | |||

Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 46 | Appendix F. Further Mappings . . . . . . . . . . . . . . . . . . 46 | |||

F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 46 | F.1. Isomorphic Mapping between Twisted Edwards Curves . . . . 46 | |||

F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 46 | F.2. Isomorphic Mapping between Montgomery Curves . . . . . . 46 | |||

F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 47 | F.3. Isomorphic Mapping between Weierstrass Curves . . . . . . 47 | |||

F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 48 | F.4. Isogenous Mapping between Weierstrass Curves . . . . . . 48 | |||

Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 50 | Appendix G. Further Cousins of Curve25519 . . . . . . . . . . . 50 | |||

G.1. Further Alternative Representations . . . . . . . . . . . 50 | G.1. Further Alternative Representations . . . . . . . . . . . 50 | |||

skipping to change at page 4, line 39 ¶ | skipping to change at page 4, line 39 ¶ | |||

J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 77 | J.2. Example with Edwards25519 . . . . . . . . . . . . . . . . 77 | |||

J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 79 | J.3. Example with Wei25519 . . . . . . . . . . . . . . . . . . 79 | |||

J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 82 | J.4. Example with Wei25519.2 . . . . . . . . . . . . . . . . . 82 | |||

J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 84 | J.5. Example with Wei25519.-3 . . . . . . . . . . . . . . . . 84 | |||

Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 86 | Appendix K. Auxiliary Functions . . . . . . . . . . . . . . . . 86 | |||

K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 86 | K.1. Square Roots in GF(q) . . . . . . . . . . . . . . . . . . 86 | |||

K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 86 | K.1.1. Square Roots in GF(q), where q = 3 (mod 4) . . . . . 86 | |||

K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 86 | K.1.2. Square Roots in GF(q), where q = 5 (mod 8) . . . . . 86 | |||

K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 87 | K.2. Inversion . . . . . . . . . . . . . . . . . . . . . . . . 87 | |||

K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 87 | K.3. Mappings to Curve Points . . . . . . . . . . . . . . . . 87 | |||

K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 87 | K.3.1. Mapping to Points of Weierstrass Curve . . . . . . . 88 | |||

K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 89 | K.3.2. Mapping to Points of Montgomery Curve . . . . . . . . 89 | |||

K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 90 | K.3.3. Mapping to Points of Twisted Edwards Curve . . . . . 90 | |||

K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 90 | K.4. Mappings to High-Order Curve Points . . . . . . . . . . . 90 | |||

K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 90 | K.4.1. Mapping to High-Order Points of Weierstrass Curve . . 90 | |||

K.4.2. Mapping to High-Order Points of Montgomery Curve . . 91 | K.4.2. Mapping to High-Order Points of Montgomery Curve . . 91 | |||

K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 93 | K.4.3. Mapping to High-Order Points of Twisted Edwards Curve 93 | |||

K.5. Randomized Representation of Curve Points . . . . . . . . 94 | K.5. Randomized Representation of Curve Points . . . . . . . . 94 | |||

K.6. Completing the Mappings to Curve Points . . . . . . . . . 95 | K.6. Completing the Mappings to Curve Points . . . . . . . . . 95 | |||

Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 96 | Appendix L. Curve secp256k1 and Friend . . . . . . . . . . . . . 97 | |||

L.1. Curve Definition and Alternative Representation . . . . . 96 | L.1. Curve Definition and Alternative Representation . . . . . 97 | |||

L.2. Switching Between Representations . . . . . . . . . . . . 97 | L.2. Switching Between Representations . . . . . . . . . . . . 98 | |||

L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 97 | L.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 98 | |||

L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 99 | L.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 100 | |||

L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 99 | L.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 100 | |||

L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 99 | L.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 100 | |||

Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 100 | Appendix M. Curve448 and Cousins . . . . . . . . . . . . . . . . 101 | |||

M.1. Curve Definition and Alternative Representations . . . . 100 | M.1. Curve Definition and Alternative Representations . . . . 101 | |||

M.2. Switching between Alternative Representations . . . . . . 101 | M.2. Switching between Alternative Representations . . . . . . 102 | |||

M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 102 | M.3. Domain Parameters . . . . . . . . . . . . . . . . . . . . 103 | |||

Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 105 | Appendix N. Further Cousins of Curve448 . . . . . . . . . . . . 106 | |||

N.1. Further Alternative Representations . . . . . . . . . . . 105 | N.1. Further Alternative Representations . . . . . . . . . . . 106 | |||

N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 105 | N.2. Further Switching . . . . . . . . . . . . . . . . . . . . 106 | |||

N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 108 | N.3. Further Domain Parameters . . . . . . . . . . . . . . . . 109 | |||

N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 110 | N.4. Isogeny Details . . . . . . . . . . . . . . . . . . . . . 111 | |||

N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 110 | N.4.1. Isogeny Parameters . . . . . . . . . . . . . . . . . 111 | |||

N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 111 | N.4.2. Dual Isogeny Parameters . . . . . . . . . . . . . . . 112 | |||

Appendix O. Representation Examples Curve448 Family Members . . 111 | Appendix O. Representation Examples Curve448 Family Members . . 112 | |||

O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 112 | O.1. Example with Curve448 . . . . . . . . . . . . . . . . . . 113 | |||

O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 115 | O.2. Example with Ed448 . . . . . . . . . . . . . . . . . . . 116 | |||

O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 118 | O.3. Example with Wei448 . . . . . . . . . . . . . . . . . . . 119 | |||

O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 121 | O.4. Example with Wei448.1 . . . . . . . . . . . . . . . . . . 122 | |||

O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 123 | O.5. Example with Wei448.-3 . . . . . . . . . . . . . . . . . 124 | |||

O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 126 | O.6. Example with Edwards448 . . . . . . . . . . . . . . . . . 127 | |||

Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 129 | Appendix P. Random Integers in Z_n . . . . . . . . . . . . . . . 130 | |||

P.1. Conversion to Integers in Z_n via Modular Reduction . . . 129 | P.1. Conversion to Integers in Z_n via Modular Reduction . . . 131 | |||

P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 130 | P.2. Conversion to Integers in Z_n via Scaling . . . . . . . . 132 | |||

P.3. Conversion to Integers in Z_n via the Discard Method . . 130 | P.3. Conversion to Integers in Z_n via the Discard Method . . 133 | |||

Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 131 | Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 133 | |||

1. Fostering Code Reuse with New Elliptic Curves | 1. Fostering Code Reuse with New Elliptic Curves | |||

Elliptic curves can be represented using different curve models. | Elliptic curves can be represented using different curve models. | |||

Recently, IETF standardized elliptic curves that are claimed to have | Recently, IETF standardized elliptic curves that are claimed to have | |||

better performance and improved robustness against "real world" | better performance and improved robustness against "real world" | |||

attacks than curves represented in the traditional short-Weierstrass | attacks than curves represented in the traditional short-Weierstrass | |||

curve model. These so-called CFRG curves [RFC7748] use the | curve model. These so-called CFRG curves [RFC7748] use the | |||

Montgomery curve model and the model of twisted Edwards curves. | Montgomery curve model and the model of twisted Edwards curves. | |||

skipping to change at page 11, line 45 ¶ | skipping to change at page 11, line 45 ¶ | |||

optimized formulae exist, such as the use of so-called Montgomery | optimized formulae exist, such as the use of so-called Montgomery | |||

ladders with Montgomery curves [Mont-Ladder] or with Weierstrass | ladders with Montgomery curves [Mont-Ladder] or with Weierstrass | |||

curves [Wei-Ladder], the use of hardcoded a=-3 domain parameter for | curves [Wei-Ladder], the use of hardcoded a=-3 domain parameter for | |||

Weierstrass curves [ECC-Isogeny], and the use of hardcoded a=-1 | Weierstrass curves [ECC-Isogeny], and the use of hardcoded a=-1 | |||

domain parameters for twisted Edwards curves [tEd-Formulas]. These | domain parameters for twisted Edwards curves [tEd-Formulas]. These | |||

all target reduction of the number of finite field operations | all target reduction of the number of finite field operations | |||

(primarily, finite field multiplications and squarings). Other | (primarily, finite field multiplications and squarings). Other | |||

optimizations target more efficient modular reductions underlying | optimizations target more efficient modular reductions underlying | |||

these finite field operations, by specifying curves defined over a | these finite field operations, by specifying curves defined over a | |||

field GF(q), where the field size q has a special form or a specific | field GF(q), where the field size q has a special form or a specific | |||

bit-size (typically, close to a multiple of a machine word). | bit-length (typically, close to a multiple of a machine word). | |||

Depending on the implementation strategy, the bit-size of q may also | Depending on the implementation strategy, the bit-length of q may | |||

facilitate reduced so-called "carry-effects" of integer arithmetic. | also facilitate reduced so-called "carry-effects" of integer | |||

arithmetic. | ||||

Most curves use a combination of these design philosophies. All NIST | Most curves use a combination of these design philosophies. All NIST | |||

curves [FIPS-186-4] and Brainpool curves [RFC5639] are Weierstrass | curves [FIPS-186-4] and Brainpool curves [RFC5639] are Weierstrass | |||

curves with a=-3 domain parameter, thus facilitating more efficient | curves with a=-3 domain parameter, thus facilitating more efficient | |||

elliptic curve group operations (via so-called Jacobian coordinates). | elliptic curve group operations (via so-called Jacobian coordinates). | |||

The NIST curves and the Montgomery curve Curve25519 are defined over | The NIST curves and the Montgomery curve Curve25519 are defined over | |||

prime fields, where the prime number has a special form, whereas the | prime fields, where the prime number has a special form, whereas the | |||

Brainpool curves - by design - use a generic prime number. None of | Brainpool curves - by design - use a generic prime number. None of | |||

the NIST prime curves, nor the Brainpool curves, can be expressed as | the NIST prime curves, nor the Brainpool curves, can be expressed as | |||

Montgomery or twisted Edwards curves, whereas - conversely - | Montgomery or twisted Edwards curves, whereas - conversely - | |||

skipping to change at page 21, line 32 ¶ | skipping to change at page 21, line 32 ¶ | |||

Section 2.2 of [RFC5480], after correcting for the error in [SEC1] | Section 2.2 of [RFC5480], after correcting for the error in [SEC1] | |||

(for the correction, see Note in Appendix H.1). | (for the correction, see Note in Appendix H.1). | |||

11.2. Encoding of ECDSA Instantiations with PKIX | 11.2. Encoding of ECDSA Instantiations with PKIX | |||

ECDSA25519, as defined in Section 4.3, is the instantiation of ECDSA | ECDSA25519, as defined in Section 4.3, is the instantiation of ECDSA | |||

with SHA-256 and with curve Wei25519. With [RFC5480], ECDSA can be | with SHA-256 and with curve Wei25519. With [RFC5480], ECDSA can be | |||

instantiated with suitable elliptic curves and hash functions. This | instantiated with suitable elliptic curves and hash functions. This | |||

allows support for ECDSA25519 by instantiating ECDSA with the curve | allows support for ECDSA25519 by instantiating ECDSA with the curve | |||

Wei25519 and the hash function SHA256, where curve Wei25519 is | Wei25519 and the hash function SHA256, where curve Wei25519 is | |||

identified by its object identifier id-wei25519 (see Section 11.1), | identified by its object identifier id-Wei25519 (see Section 11.1), | |||

where ECDSA with SHA256 is identified by the object identifier id- | where ECDSA with SHA256 is identified by the object identifier id- | |||

ecdsa-with-SHA256 (see [RFC5480]), and where all other aspects are | ecdsa-with-SHA256 (see [RFC5480]), and where all other aspects are | |||

specified in [RFC5480]. | specified in [RFC5480]. | |||

ECDSA448, as defined in Section 4.4, is the instantiation of ECDSA | ECDSA448, as defined in Section 4.4, is the instantiation of ECDSA | |||

with SHAKE256 with output size d=512 bits and with curve Wei448. | with SHAKE256 with output size d=512 bits and with curve Wei448. | |||

With [RFC5480], ECDSA can be instantiated with suitable elliptic | With [RFC5480], ECDSA can be instantiated with suitable elliptic | |||

curves and hash functions. This allows support for ECDSA448 by | curves and hash functions. This allows support for ECDSA448 by | |||

instantiating ECDSA with the curve Wei448 and the hash function | instantiating ECDSA with the curve Wei448 and the hash function | |||

SHAKE256 with output size of d=512 bits, where curve Wei448 is | SHAKE256 with output size of d=512 bits, where curve Wei448 is | |||

identified by its object identifier id-wei448 (see Section 11.1), | identified by its object identifier id-Wei448 (see Section 11.1), | |||

where ECDSA with SHAKE256 with output size of d=512 bits is | where ECDSA with SHAKE256 with output size of d=512 bits is | |||

identified by the object identifier id-ecdsa-with-shake256 (see | identified by the object identifier id-ecdsa-with-shake256 (see | |||

[RFC8692]), and where all other aspects are specified in [RFC5480]. | [RFC8692]), and where all other aspects are specified in [RFC5480]. | |||

11.3. Encoding of co-factor ECDH and Other Algorithms with PKIX | 11.3. Encoding of co-factor ECDH and Other Algorithms with PKIX | |||

With [RFC5480], the algorithm field in the SubjectPublicKeyInfo | With [RFC5480], the algorithm field in the SubjectPublicKeyInfo | |||

structure indicates the algorithm and the elliptic curve domain | structure indicates the algorithm and the elliptic curve domain | |||

parameters for a specific curve, where that specification defines | parameters for a specific curve, where that specification defines | |||

three algorithm identifiers (viz. id-ecPublicKey, id-ecdh, and id- | three algorithm identifiers (viz. id-ecPublicKey, id-ecDH, and id- | |||

ecmqv). Each of these algorithms can be instantiated with suitable | ecMQV). Each of these algorithms can be instantiated with suitable | |||

alliptic curves, thereby allowing support for their use with the | alliptic curves, thereby allowing support for their use with the | |||

curves Wei25519 and Wei448, where these curves are identified by | curves Wei25519 and Wei448, where these curves are identified by | |||

their unique object identifiers id-wei25519 and id-wei448, | their unique object identifiers id-wei25519 and id-wei448, | |||

respectively, and where all other aspects are specified in [RFC5480]. | respectively, (see Section 11.1) and where all other aspects are | |||

specified in [RFC5480]. | ||||

11.4. Encoding of Elliptic-Curve-Based Algorithms with CMS | 11.4. Encoding of Elliptic-Curve-Based Algorithms with CMS | |||

With [RFC5753], elliptic-curve based algorithms should use one of the | With [RFC5753], elliptic-curve based algorithms should use one of the | |||

elliptic curve domain parameters specified in [RFC5480], where the | elliptic curve domain parameters specified in [RFC5480], where the | |||

unique name of each such curve is identified by the object identifier | unique name of each such curve is identified by the object identifier | |||

of this curve defined in that document. Each of these algorithms can | of this curve defined in that document. Each of these algorithms can | |||

be instantiated with suitable elliptic curves, thereby allowing | be instantiated with suitable elliptic curves, thereby allowing | |||

support for their use with the curves Wei25519 and Wei448, where | support for their use with the curves Wei25519 and Wei448, where | |||

these curves are identified by their unique object identifiers id- | these curves are identified by their unique object identifiers id- | |||

wei25519 and id-wei448, respectively, and where all other aspects are | wei25519 and id-wei448, respectively, (see Section 11.1) and where | |||

specified in [RFC5753]. | all other aspects are specified in [RFC5753]. | |||

12. IANA Considerations | 12. IANA Considerations | |||

Code points are requested for curves Wei25519 and Wei448 and their | Code points are requested for curves Wei25519 and Wei448 and their | |||

use with ECDSA and co-factor ECDH, using the representation | use with ECDSA and co-factor ECDH, using the representation | |||

conventions of this document. | conventions of this document. | |||

New code points would be required in case one wishes to specify one | New code points would be required in case one wishes to specify one | |||

or more other "offspring" protocols beyond those exemplified in | or more other "offspring" protocols beyond those exemplified in | |||

Section 4.4. Specification hereof is, however, outside the scope of | Section 4.4. Specification hereof is, however, outside the scope of | |||

skipping to change at page 32, line 38 ¶ | skipping to change at page 32, line 38 ¶ | |||

Edwards Curves Revisited", ASIACRYPT 2008, Lecture Notes | Edwards Curves Revisited", ASIACRYPT 2008, Lecture Notes | |||

in Computer Science, Vol. 5350, New York: Springer-Verlag, | in Computer Science, Vol. 5350, New York: Springer-Verlag, | |||

2008. | 2008. | |||

[Tibouchi] | [Tibouchi] | |||

M. Tibouchi, "Elligator Squared -- Uniform Points on | M. Tibouchi, "Elligator Squared -- Uniform Points on | |||

Elliptic Curves of Prime Order as Uniform Random Strings", | Elliptic Curves of Prime Order as Uniform Random Strings", | |||

Financial Cryptography 2014, Lecture Notes in Computer | Financial Cryptography 2014, Lecture Notes in Computer | |||

Science, Vol. 8437, New York: Springer-Verlag, 2014. | Science, Vol. 8437, New York: Springer-Verlag, 2014. | |||

[Tibouchi-cleancut] | ||||

T. Kim, M. Tibouchi, "Improved Elliptic Curve Hashing and | ||||

Point Representation", DCC 2017, Des. Codes Cryptogr., | ||||

Vol. 82, pp. 161-177, New York: Springer-Verlag, 2017. | ||||

[Wei-Ladder] | [Wei-Ladder] | |||

T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve | T. Izu, Ts. Takagi,, "A Fast Parallel Elliptic Curve | |||

Multiplication Resistant Against Side Channel Attacks", | Multiplication Resistant Against Side Channel Attacks", | |||

Centre for Applied Cryptographic Research, Corr 2002-03, | Centre for Applied Cryptographic Research, Corr 2002-03, | |||

2002. | 2002. | |||

Appendix A. Some (Non-Binary) Elliptic Curves | Appendix A. Some (Non-Binary) Elliptic Curves | |||

This section defines the three different curve models we consider, | This section defines the three different curve models we consider, | |||

viz. short-Weierstrass curves, Montgomery curves, and twisted Edwards | viz. short-Weierstrass curves, Montgomery curves, and twisted Edwards | |||

skipping to change at page 34, line 45 ¶ | skipping to change at page 34, line 51 ¶ | |||

n*P=O and if it is not the identity element O. (The latter order | n*P=O and if it is not the identity element O. (The latter order | |||

check is commonly called full public key validation.) | check is commonly called full public key validation.) | |||

If R is a point of the curve that is also contained in (P), there is | If R is a point of the curve that is also contained in (P), there is | |||

a unique integer k in the interval [0, l-1] so that R=k*P, where l is | a unique integer k in the interval [0, l-1] so that R=k*P, where l is | |||

the order of P. This number is called the discrete logarithm of R to | the order of P. This number is called the discrete logarithm of R to | |||

the base P. The discrete logarithm problem is the problem of finding | the base P. The discrete logarithm problem is the problem of finding | |||

the discrete logarithm of R to the base P for any two points P and R | the discrete logarithm of R to the base P for any two points P and R | |||

of the curve, if such a number exists. | of the curve, if such a number exists. | |||

Random points R of (P), where P has order l, can be computed by | ||||

generating a random integer k in the interval [0, l-1] and by | ||||

subsequently computing R:=k*P, where R has order l/gcd(k,l). In | ||||

particular, if P is a high-order point, then so is R, unless k is a | ||||

multiple of n (in which case R is a low-order point). For methods | ||||

for generating k, see Appendix P. | ||||

If P is a fixed base point G of the curve, the pair (k, R:=k*G) is | If P is a fixed base point G of the curve, the pair (k, R:=k*G) is | |||

commonly called a public-private key pair, the integer k the private | commonly called a public-private key pair, the integer k the private | |||

key, and the point R the corresponding public key. The private key k | key, and the point R the corresponding public key. The private key k | |||

can be represented as an integer in the interval [0,n-1], where G has | can be represented as an integer in the interval [0,n-1], where G has | |||

order n. If this representation is nonzero, R has order n; | order n. If this representation is nonzero, R has order n; | |||

otherwise, it has order one and is the identity element O of the | otherwise, it has order one and is the identity element O of the | |||

curve. | curve. | |||

In this document, a quadratic twist of a curve E defined over a field | In this document, a quadratic twist of a curve E defined over a field | |||

GF(q) is a specific curve E' related to E defined over the same | GF(q) is a specific curve E' related to E defined over the same | |||

skipping to change at page 74, line 13 ¶ | skipping to change at page 74, line 13 ¶ | |||

compressed point (see Appendix H) to be encoded in this bit position | compressed point (see Appendix H) to be encoded in this bit position | |||

and, thereby, allows a compressed point and an element of GF(p) to be | and, thereby, allows a compressed point and an element of GF(p) to be | |||

represented by an octet string of the same length. This is called | represented by an octet string of the same length. This is called | |||

the "squeezed" point representation. (We will use this squeezed | the "squeezed" point representation. (We will use this squeezed | |||

representation in Appendix J.) Obviously, other representations | representation in Appendix J.) Obviously, other representations | |||

(e.g., those of elements of Z_n) may also have fixed bit values in | (e.g., those of elements of Z_n) may also have fixed bit values in | |||

certain positions, which can be used to squeeze-in additional | certain positions, which can be used to squeeze-in additional | |||

information. Further details are out of scope. | information. Further details are out of scope. | |||

Notice that elements of a prime field GF(p), where p is a prime | Notice that elements of a prime field GF(p), where p is a prime | |||

number with bit-size m divisible by eight, have a tight | number with bit-length m divisible by eight, have a tight | |||

representation as an (m/8)-octet string, but do not have a bit | representation as an (m/8)-octet string, but do not have a bit | |||

position that is always set to zero. Thus, in this case, one cannot | position that is always set to zero. Thus, in this case, one cannot | |||

represent a compressed point as an octet string of the same length as | represent a compressed point as an octet string of the same length as | |||

an element of GF(p). However, one can still encode this as an octet | an element of GF(p). However, one can still encode this as an octet | |||

string of length (m/8)+1 (see Note 1 above). If one uses right- | string of length (m/8)+1 (see Note 1 above). If one uses right- | |||

concatenation as in Note 1, but (for historial reasons) represents | concatenation as in Note 1, but (for historial reasons) represents | |||

the parity bit t of the compressed point in question by 0x00 or 0x80 | the parity bit t of the compressed point in question by 0x00 or 0x80 | |||

depending on whether t=0 or t=1, respectively, this is again called | depending on whether t=0 or t=1, respectively, this is again called | |||

the "squeezed' representation (despite this being somewhat a | the "squeezed' representation (despite this being somewhat a | |||

misnomer, since each point is now represented as an octet string that | misnomer, since each point is now represented as an octet string that | |||

skipping to change at page 81, line 31 ¶ | skipping to change at page 81, line 31 ¶ | |||

corresponds to the right-concatenation of its X- and Y-coordinates, | corresponds to the right-concatenation of its X- and Y-coordinates, | |||

each in tight MSB/msb-order, prepended by the string 0x04, where the | each in tight MSB/msb-order, prepended by the string 0x04, where the | |||

reverse procedure is uniquely defined, since elements of GF(p) have a | reverse procedure is uniquely defined, since elements of GF(p) have a | |||

unique fixed-size representation. The (squeezed) compressed format | unique fixed-size representation. The (squeezed) compressed format | |||

repr(Pw) corresponds to the SEC1-compliant compressed format by | repr(Pw) corresponds to the SEC1-compliant compressed format by | |||

extracting the parity bit t from the leftmost bit of the leftmost | extracting the parity bit t from the leftmost bit of the leftmost | |||

octet of repr(Pw), replacing the bit position by the value zero, and | octet of repr(Pw), replacing the bit position by the value zero, and | |||

prepending the octet string with 0x02 or 0x03, depending on whether | prepending the octet string with 0x02 or 0x03, depending on whether | |||

t=0 or t=1, respectively, where the reverse procedure is uniquely | t=0 or t=1, respectively, where the reverse procedure is uniquely | |||

defined, since GF(p) is a 255-bit prime field. For further details, | defined, since GF(p) is a 255-bit prime field. For further details, | |||

see [SEC1]. Note that, due to the bit-size of the prime p, the | see [SEC1]. Note that, due to the bit-length of the prime p, the | |||

squeezed compressed format repr(Pw) is one octet shorter than the | squeezed compressed format repr(Pw) is one octet shorter than the | |||

SEC1-compliant compressed format compr(Pw). | SEC1-compliant compressed format compr(Pw). | |||

A randomized representation (t1, t2) of the point k*Pw in tight MSB/ | A randomized representation (t1, t2) of the point k*Pw in tight MSB/ | |||

msb order is given by | msb order is given by | |||

t1 446363445988889734093446280484122107283059206243307955388 | t1 446363445988889734093446280484122107283059206243307955388 | |||

84223152228795899590 | 84223152228795899590 | |||

(=0x62af4697 4dd469ac 96c64809 c16c8517 b6a0cee5 40ba0e2e | (=0x62af4697 4dd469ac 96c64809 c16c8517 b6a0cee5 40ba0e2e | |||

skipping to change at page 87, line 29 ¶ | skipping to change at page 87, line 29 ¶ | |||

1/y:=y^{q-2} (since y^{q-1}=1). | 1/y:=y^{q-2} (since y^{q-1}=1). | |||

If inverses are easy to compute in GF(q), then so are these in | If inverses are easy to compute in GF(q), then so are these in | |||

GF(q^2). Further details are out of scope. | GF(q^2). Further details are out of scope. | |||

The inverses of two nonzero elements y1 and y2 of GF(q) can be | The inverses of two nonzero elements y1 and y2 of GF(q) can be | |||

computed by first computing the inverse z of y1*y2 and by | computed by first computing the inverse z of y1*y2 and by | |||

subsequently computing y2*z=:1/y1 and y1*z=:1/y2. | subsequently computing y2*z=:1/y1 and y1*z=:1/y2. | |||

NOTE: This method can also be used to compute the inverse and a | NOTE 1: This method can be used to compute the inverse of a nonzero | |||

element y of GF(q) indirectly, as lambda*(lambda*y)^{-1}, where | ||||

lambda is a random nonzero element of GF(q). This yields an | ||||

inversion routine (commonly called "blinded inversion") where the | ||||

inversion operation itself does not leak information on y. | ||||

NOTE 2: This method can also be used to compute the inverse and a | ||||

square root, respectively, of two nonzero elements x and y of GF(q) | square root, respectively, of two nonzero elements x and y of GF(q) | |||

by first computing a square root z of 1/(y*x^2) (see Appendix K.1) | by first computing a square root z of 1/(y*x^2) (see Appendix K.1) | |||

and by subsequently computing a square root of y as x*y*z and the | and by subsequently computing a square root of y as x*y*z and the | |||

inverse of x as x*y*z^2. | inverse of x as x*y*z^2. | |||

K.3. Mappings to Curve Points | K.3. Mappings to Curve Points | |||

One can map elements of GF(q) that are not a square in GF(q) to | One can map elements of GF(q) that are not a square in GF(q) to | |||

points of a Weierstrass curve (see Appendix K.3.1), to points of a | points of a Weierstrass curve (see Appendix K.3.1), to points of a | |||

Montgomery curve (see Appendix K.3.2), or to points of a twisted | Montgomery curve (see Appendix K.3.2), or to points of a twisted | |||

skipping to change at page 96, line 27 ¶ | skipping to change at page 96, line 27 ¶ | |||

distribution properties as the original mapping (see NOTE 2 of | distribution properties as the original mapping (see NOTE 2 of | |||

Appendix K.5). For each curve in Table 1, these completed mappings | Appendix K.5). For each curve in Table 1, these completed mappings | |||

are uniquely defined by the mentioned fixed curve offset P0 and non- | are uniquely defined by the mentioned fixed curve offset P0 and non- | |||

square element delta of GF(q), if one defines P2:=P1:=P0 (henceforth | square element delta of GF(q), if one defines P2:=P1:=P0 (henceforth | |||

called the default completed mappings). | called the default completed mappings). | |||

NOTE 2: For elliptic curves defined over prime fields (i.e., q:=p) | NOTE 2: For elliptic curves defined over prime fields (i.e., q:=p) | |||

one can relax the completed mappings above and show that the | one can relax the completed mappings above and show that the | |||

statistical properties for randomized representations still hold if | statistical properties for randomized representations still hold if | |||

u1 is a random element of a sufficiently large interval in GF(p) and | u1 is a random element of a sufficiently large interval in GF(p) and | |||

if u2 is a random element of a sufficiently large subset of GF(p). | if u2 is a random element of a sufficiently large subset of GF(p) | |||

This allows generating u1 and u2, e.g., each as random bit strings of | (see, e.g., [Tibouchi-cleancut]). This allows generating u1 and u2, | |||

length m-1, where m is the bit-size of p, thereby allowing the pair | e.g., each as random bit strings of length m-1, where m is the bit- | |||

(u1, u2) -- a random (2*m-2)-bit string -- to be used unaltered in | length of p, thereby allowing the pair (u1, u2) -- a random (2*m-2)- | |||

this construction, without the need to carry out a reduction modulo p | bit string -- to be used unaltered in this construction, without the | |||

first. Further details are out of scope of this document. | need to carry out a reduction modulo p first. Table 2 illustrates | |||

how this can be used to realize randomized representations and | ||||

completed mappings for each curve in Table 1, where these randomized | ||||

bit strings have the same byte-length as the (tight) representation | ||||

of affine curve points. For each curve in Table 2, we refer to this | ||||

version of the default completed mapping as being the "clean-cut" | ||||

default completed mapping. Further details are out of scope of this | ||||

document. | ||||

+--------------------------+-----------------+----------------------+ | ||||

| Curve | left-side | right-side | | ||||

+--------------------------+-----------------+----------------------+ | ||||

| NIST P-224 [FIPS-186-4] | {u1:224} | {s1:1, s2:1, u2:222} | | ||||

| NIST P-256 [FIPS-186-4] | {s1:1, u1:255} | {s2:1, u2:255} | | ||||

| NIST P-384 [FIPS-186-4] | {u1:384} | {s1:1, s2:1, u2:382} | | ||||

| NIST P-521 [FIPS-186-4] | {s1:1, u1:527} | {s2:1, u2:527} | | ||||

| Brainpool224r1 [RFC5639] | {s1:1, u1:223} | {s2:1, u2:223} | | ||||

| Brainpool256r1 [RFC5639] | {s1:1, u1:255} | {s2:1, u2:255} | | ||||

| Brainpool320r1 [RFC5639] | {s1:1, u1:319} | {s2:1, u2:319} | | ||||

| Brainpool384r1 [RFC5639] | {s1:1, u1:383} | {s2:1, u2:383} | | ||||

| Brainpool512r1 [RFC5639] | {s1:1, u1:511} | {s2:1, u2:511} | | ||||

| Curve25519 [RFC7748] | {s1:1, u1:255} | {s2:1, u2:255} | | ||||

| Wei25519 [Appendix E.3] | {s1:1, u1:255} | {s2:1, u2:255} | | ||||

| Wei25519.2 | {s1:1, u1:255} | {s2:1, u2:255} | | ||||

| [Appendix G.3] | | | | ||||

| Wei25519.-3 | {s1:1, u1:255} | {s2:1, u2:255} | | ||||

| [Appendix G.3] | | | | ||||

| Curve448 [RFC7748] | {u1:448} | {s1:1, s2:1, u2:446} | | ||||

| Wei448 [Appendix M.3] | {u1:448} | {s1:1, s2:1, u2:446} | | ||||

| Wei448.1 [Appendix N.3] | {u1:448} | {s1:1, s2:1, u2:446} | | ||||

| Wei448.-3 [Appendix N.3] | {u1:448} | {s1:1, s2:1, u2:446} | | ||||

| secp256k1.m | {u1:256} | {s1:1, s2:1, u2:254} | | ||||

| [Appendix L.3] | | | | ||||

+--------------------------+-----------------+----------------------+ | ||||

Table 2: Randomized representation of curve points, for some curves | ||||

of practical interest, including curve-specific relative ordering and | ||||

bit-length of substrings representing the tuple ((u1,s1),(u2,s2)), | ||||

resulting in the bit string left-side || right-side. | ||||

Appendix L. Curve secp256k1 and Friend | Appendix L. Curve secp256k1 and Friend | |||

This section illustrates how isogenies can be used to yield curves | This section illustrates how isogenies can be used to yield curves | |||

with specific properties (here, illustrated for the "BitCoin" curve | with specific properties (here, illustrated for the "BitCoin" curve | |||

secp256k1). | secp256k1). | |||

L.1. Curve Definition and Alternative Representation | L.1. Curve Definition and Alternative Representation | |||

The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined | The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined | |||

skipping to change at page 114, line 24 ¶ | skipping to change at page 115, line 24 ¶ | |||

the v-coordinate of the point of Curve448 in question (which, in this | the v-coordinate of the point of Curve448 in question (which, in this | |||

case, are both one, since v and v1 are odd). See Appendix H.2 and | case, are both one, since v and v1 are odd). See Appendix H.2 and | |||

Appendix I for further detail on (squeezed) point compression. | Appendix I for further detail on (squeezed) point compression. | |||

The scalar representation and (squeezed) point representation | The scalar representation and (squeezed) point representation | |||

illustrated above are consistent with the representations specified | illustrated above are consistent with the representations specified | |||

in [RFC7748], except that in [RFC7748] only an affine point's | in [RFC7748], except that in [RFC7748] only an affine point's | |||

u-coordinate is represented (i.e., the v-coordinate of any point is | u-coordinate is represented (i.e., the v-coordinate of any point is | |||

always implicitly assumed to have an even value) and that the | always implicitly assumed to have an even value) and that the | |||

representation of the point at infinity is not specified. (Note that | representation of the point at infinity is not specified. (Note that | |||

due to the bit-size of the prime p, the lossless representation | due to the bit-length of the prime p, the lossless representation | |||

requires an additional octet compared to the lossy representation | requires an additional octet compared to the lossy representation | |||

without v-coordinate.) Another difference is that [RFC7748] allows | without v-coordinate.) Another difference is that [RFC7748] allows | |||

non-unique representations of some elements of GF(p), whereas our | non-unique representations of some elements of GF(p), whereas our | |||

representation conventions do not (since tight). | representation conventions do not (since tight). | |||

A randomized representation (t1, t2) of the point k*Pm in tight LSB/ | A randomized representation (t1, t2) of the point k*Pm in tight LSB/ | |||

msb order is given by | msb order is given by | |||

t1 642695971489808425948939115432957219707501931105169269237 | t1 642695971489808425948939115432957219707501931105169269237 | |||

122551860533279049805112466411050091592893048844749561382 | 122551860533279049805112466411050091592893048844749561382 | |||

skipping to change at page 120, line 18 ¶ | skipping to change at page 121, line 18 ¶ | |||

The SEC1-compliant uncompressed format aff(Pw) of an affine point Pw | The SEC1-compliant uncompressed format aff(Pw) of an affine point Pw | |||

corresponds to the right-concatenation of its X- and Y-coordinates, | corresponds to the right-concatenation of its X- and Y-coordinates, | |||

each in tight MSB/msb-order, prepended by the string 0x04, where the | each in tight MSB/msb-order, prepended by the string 0x04, where the | |||

reverse procedure is uniquely defined, since elements of GF(p) have a | reverse procedure is uniquely defined, since elements of GF(p) have a | |||

unique fixed-size representation. The (squeezed) compressed format | unique fixed-size representation. The (squeezed) compressed format | |||

repr(Pw) corresponds to the SEC1-compliant compressed format by | repr(Pw) corresponds to the SEC1-compliant compressed format by | |||

extracting the parity bit t from the leftmost bit of the leftmost | extracting the parity bit t from the leftmost bit of the leftmost | |||

octet of repr(Pw), and replacing this leftmost octet with 0x02 or | octet of repr(Pw), and replacing this leftmost octet with 0x02 or | |||

0x03, depending on whether t=0 or t=1, respectively, where the | 0x03, depending on whether t=0 or t=1, respectively, where the | |||

reverse procedure is uniquely defined. For further details, see | reverse procedure is uniquely defined. For further details, see | |||

[SEC1]. Note that, due to the bit-size of the prime p, the squeezed | [SEC1]. Note that, due to the bit-length of the prime p, the | |||

compressed format repr(Pw) and the SEC1-compliant compressed format | squeezed compressed format repr(Pw) and the SEC1-compliant compressed | |||

compr(Pw) have the same size. | format compr(Pw) have the same size. | |||

A randomized representation (t1, t2) of the point k*Pw in tight MSB/ | A randomized representation (t1, t2) of the point k*Pw in tight MSB/ | |||

msb order is given by | msb order is given by | |||

t1 655783099225353926682910498535559663266263823350679216116 | t1 655783099225353926682910498535559663266263823350679216116 | |||

172951494291735730803127024621397533084891460609898061397 | 172951494291735730803127024621397533084891460609898061397 | |||

896825551162064841608 | 896825551162064841608 | |||

(=0xe6f93655 2765628b accfe61c 7dc6a594 e06fb243 70195ded | (=0xe6f93655 2765628b accfe61c 7dc6a594 e06fb243 70195ded | |||

74d88a53 fdedc2e8 077e0eff 62fa6a80 fa26b499 1f8796f5 | 74d88a53 fdedc2e8 077e0eff 62fa6a80 fa26b499 1f8796f5 | |||

skipping to change at page 129, line 13 ¶ | skipping to change at page 130, line 13 ¶ | |||

Curve448 of Appendix N.2. | Curve448 of Appendix N.2. | |||

Appendix P. Random Integers in Z_n | Appendix P. Random Integers in Z_n | |||

Any probability distribution on the interval [0,N-1] can be converted | Any probability distribution on the interval [0,N-1] can be converted | |||

to a probability distribution on [0,n-1], via a suitable function | to a probability distribution on [0,n-1], via a suitable function | |||

that maps inputs from the source distribution [0,N-1] to values in | that maps inputs from the source distribution [0,N-1] to values in | |||

the interval [0,n-1]. We consider three such functions, each with | the interval [0,n-1]. We consider three such functions, each with | |||

the property that if the source distribution on [0,N-1] is | the property that if the source distribution on [0,N-1] is | |||

statistically close to the uniform distribution, then so is the | statistically close to the uniform distribution, then so is the | |||

output distribution on [0,n-1]. In practical applications, one can | output distribution on [0,n-1]. (Here, we assume n and N to be | |||

use these functions to convert the output of a cryptographically | integers of cryptographic interest, so large.) In practical | |||

strong random bit generator (where N is a power of two and after | applications, one can use these functions to convert the output of a | |||

conversion of the random bit string to an integer via the BS2I | cryptographically strong random bit generator (where N is a power of | |||

mapping of Appendix I.2) to a pseudo-random integer in the interval | two and after conversion of the random bit string to an integer via | |||

[0,n-1], where the bias is small if N is suitably picked. | the BS2I mapping of Appendix I.2) to a pseudo-random integer in the | |||

interval [0,n-1], where the bias is small if N is suitably picked. | ||||

We consider mappings that convert an output of the source | We consider mappings that convert an output of the source | |||

distribution to an integer in the interval [0,n-1] via modular | distribution to an integer in the interval [0,n-1] via modular | |||

reduction (Appendix P.1), via scaling (Appendix P.2), or via a | reduction (Appendix P.1), via scaling (Appendix P.2), or via a | |||

membership test (Appendix P.3). For suitably picked N values and not | membership test (Appendix P.3). For suitably picked N values and not | |||

too poor source distributions, the first two mappings never fail and | too poor source distributions, the first two mappings never fail and | |||

any bias introduced by the conversion process can be made negligible | any bias introduced by the conversion process can be made negligible | |||

in practice, while the third mapping (if it does not fail) inflates | in practice, while the third mapping (if it does not fail) inflates | |||

the bias by a small factor only in practice. (For details, see the | the bias by a small factor only in practice. (For details, see the | |||

remarks following each of the mappings below.) | remarks following each of the mappings below.) | |||

NOTE: Each of the mappings below may yield a zero output value. One | NOTE: 1 Each of the mappings below may yield a zero output value. | |||

can modify each such mapping to always yield nonzero outputs, by | One can modify each such mapping to always yield nonzero outputs, by | |||

setting output x to 1 if the original mapping would yield x=0 for a | setting output x to 1 if the original mapping would yield x=0 for a | |||

specific input y and leaving the mapping the same otherwise | specific input y and leaving the mapping the same otherwise | |||

(henceforth called the modified conversion function). This | (henceforth called the modified conversion function). This | |||

modification has negligible impact on the bias and does yield a | modification has negligible impact on the bias and does yield a | |||

conversion function to integers in the interval [1,n-1]. | conversion function to integers in the interval [1,n-1]. A similar | |||

remark applies if n=h*n1, where h is a small integer: in that case, | ||||

one can locally modify each mapping to always yield outputs in the | ||||

interval [0, h*n1-1] that are not divisible by n1, simply by setting | ||||

output x to x+1 if the original mapping would otherwise yield x=0 | ||||

(mod n1). (Notice that both modifications coincide if h=1.) These | ||||

modifications may be useful if one wishes to generate integers in an | ||||

interval of size n and where one wishes to avoid specific output | ||||

values (e.g., if one wishes to generate high-order points of a curve | ||||

of order h*n1, with co-factor h (see Appendix B.1)). For simplicity, | ||||

we again refer to this as "the" modified conversion function (or | ||||

h-modified conversion function, if h is not clear from context). | ||||

P.1. Conversion to Integers in Z_n via Modular Reduction | P.1. Conversion to Integers in Z_n via Modular Reduction | |||

This function maps each integer y in the interval [0,N-1] to its | This function maps each integer y in the interval [0,N-1] to its | |||

remainder modulo n, i.e., y is mapped to x:= y (mod n). | remainder modulo n, i.e., y is mapped to x:= y (mod n). | |||

One can show that the bias introduced by this conversion function is | One can show that the bias introduced by this conversion function is | |||

at most epsilon:=2*rho*(1-rho)/(N/n), where r:=N (mod n) and where | at most epsilon:=2*rho*(1-rho)/(N/n), where r:=N (mod n) and where | |||

rho:=r/n. Details are out of scope. | rho:=r/n. Details are out of scope. | |||

skipping to change at page 130, line 18 ¶ | skipping to change at page 131, line 34 ¶ | |||

introduced by the modular reduction operation is negligible in | introduced by the modular reduction operation is negligible in | |||

practice. The same holds if N is close to a multiple of n (e.g., if | practice. The same holds if N is close to a multiple of n (e.g., if | |||

n is close to a power of two and the input distribution is generated | n is close to a power of two and the input distribution is generated | |||

by a high-quality random bit generator with outputs of fixed bit- | by a high-quality random bit generator with outputs of fixed bit- | |||

length). | length). | |||

Note: In practice, one does not determine the maximum bias epsilon | Note: In practice, one does not determine the maximum bias epsilon | |||

from n and N, but rather specifies a required upper bound (usually | from n and N, but rather specifies a required upper bound (usually | |||

set to a value at most 2^{-64}) for epsilon and subsequently | set to a value at most 2^{-64}) for epsilon and subsequently | |||

determines the minimal value of N for which this upper bound indeed | determines the minimal value of N for which this upper bound indeed | |||

applies, as a function of n. | applies, as a function of n. Table 3 illustrates this for several | |||

curves of practical interest. | ||||

+----------------------------+--------------+----------------+ | ||||

| Curve | eps0=2^{-64} | eps0=2^{-100} | | ||||

+----------------------------+--------------+----------------+ | ||||

| NIST P-224 [FIPS-186-4] | 224 | 224 | | ||||

| NIST P-256 [FIPS-186-4] | 288 | 352 | | ||||

| NIST P-384 [FIPS-186-4] | 384 | 384 | | ||||

| NIST P-521 [FIPS-186-4] | 521 | 521 | | ||||

| Brainpool224r1 [RFC5639] | 287 | 323 | | ||||

| Brainpool256r1 [RFC5639] | 319 | 354 | | ||||

| Brainpool320r1 [RFC5639] | 379 | 417 | | ||||

| Brainpool384r1 [RFC5639] | 445 | 482 | | ||||

| Brainpool512r1 [RFC5639] | 575 | 608 | | ||||

| Curve25519 [RFC7748] | 252 | 252 | | ||||

| Wei25519 [Appendix E.3] | 252 | 252 | | ||||

| Wei25519.2 [Appendix G.3] | 252 | 252 | | ||||

| Wei25519.-3 [Appendix G.3] | 252 | 252 | | ||||

| Curve448 [RFC7748] | 446 | 446 | | ||||

| Wei448 [Appendix M.3] | 446 | 446 | | ||||

| Wei448.1 [Appendix N.3] | 446 | 446 | | ||||

| Wei448.-3 [Appendix N.3] | 446 | 446 | | ||||

| secp256k1.m [Appendix L.3] | 256 | 256 | | ||||

+----------------------------+--------------+----------------+ | ||||

Table 3: Minimum bit-length of N for which the bias (epsilon) | ||||

introduced by converting integers in Z_N to integers in Z_n via | ||||

modular reduction or via scaling is lower than the indicated eps0 | ||||

value, for some curves of practical interest (where n is the order of | ||||

the base point of the curve in question) | ||||

P.2. Conversion to Integers in Z_n via Scaling | P.2. Conversion to Integers in Z_n via Scaling | |||

This function maps each integer y in the interval [0,N-1] to the | This function maps each integer y in the interval [0,N-1] to the | |||

integer x:=floor(n*y/N), where the floor function rounds real numbers | integer x:=floor(n*y/N), where the floor function rounds real numbers | |||

downwards to an integer (i.e., floor(z) is the unique integer i for | downwards to an integer (i.e., floor(z) is the unique integer i for | |||

which z is an element of the interval [i,i+1) of real numbers). | which z is an element of the interval [i,i+1) of real numbers). | |||

One can show that the bias introduced by this conversion function is | One can show that the bias introduced by this conversion function is | |||

at most epsilon:=2*rho*(1-rho)/(N/n), where r:=N (mod n) and where | at most epsilon:=2*rho*(1-rho)/(N/n), where r:=N (mod n) and where | |||

End of changes. 28 change blocks. | ||||

76 lines changed or deleted | | 176 lines changed or added | ||

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