rfc9380.original   rfc9380.txt 
CFRG A. Faz-Hernandez Internet Research Task Force (IRTF) A. Faz-Hernandez
Internet-Draft Cloudflare, Inc. Request for Comments: 9380 Cloudflare, Inc.
Intended status: Informational S. Scott Category: Informational S. Scott
Expires: 17 December 2022 Cornell Tech ISSN: 2070-1721 Oso Security, Inc.
N. Sullivan N. Sullivan
Cloudflare, Inc. Cloudflare, Inc.
R.S. Wahby R. S. Wahby
Stanford University Stanford University
C.A. Wood C. A. Wood
Cloudflare, Inc. Cloudflare, Inc.
15 June 2022 August 2023
Hashing to Elliptic Curves Hashing to Elliptic Curves
draft-irtf-cfrg-hash-to-curve-16
Abstract Abstract
This document specifies a number of algorithms for encoding or This document specifies a number of algorithms for encoding or
hashing an arbitrary string to a point on an elliptic curve. This hashing an arbitrary string to a point on an elliptic curve. This
document is a product of the Crypto Forum Research Group (CFRG) in document is a product of the Crypto Forum Research Group (CFRG) in
the IRTF. the IRTF.
Discussion Venues
This note is to be removed before publishing as an RFC.
Discussion of this document takes place on the Crypto Forum Research
Group mailing list (cfrg@ietf.org), which is archived at
https://mailarchive.ietf.org/arch/search/?email_list=cfrg.
Source for this draft and an issue tracker can be found at
https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This document is not an Internet Standards Track specification; it is
provisions of BCP 78 and BCP 79. published for informational purposes.
Internet-Drafts are working documents of the Internet Engineering This document is a product of the Internet Research Task Force
Task Force (IETF). Note that other groups may also distribute (IRTF). The IRTF publishes the results of Internet-related research
working documents as Internet-Drafts. The list of current Internet- and development activities. These results might not be suitable for
Drafts is at https://datatracker.ietf.org/drafts/current/. deployment. This RFC represents the consensus of the Crypto Forum
Research Group of the Internet Research Task Force (IRTF). Documents
approved for publication by the IRSG are not candidates for any level
of Internet Standard; see Section 2 of RFC 7841.
Internet-Drafts are draft documents valid for a maximum of six months Information about the current status of this document, any errata,
and may be updated, replaced, or obsoleted by other documents at any and how to provide feedback on it may be obtained at
time. It is inappropriate to use Internet-Drafts as reference https://www.rfc-editor.org/info/rfc9380.
material or to cite them other than as "work in progress."
This Internet-Draft will expire on 17 December 2022.
Copyright Notice Copyright Notice
Copyright (c) 2022 IETF Trust and the persons identified as the Copyright (c) 2023 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 (https://trustee.ietf.org/ Provisions Relating to IETF Documents
license-info) in effect on the date of publication of this document. (https://trustee.ietf.org/license-info) in effect on the date of
Please review these documents carefully, as they describe your rights publication of this document. Please review these documents
and restrictions with respect to this document. Code Components carefully, as they describe your rights and restrictions with respect
extracted from this document must include Revised BSD License text as to this document.
described in Section 4.e of the Trust Legal Provisions and are
provided without warranty as described in the Revised BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 5 1. Introduction
1.1. Requirements Notation . . . . . . . . . . . . . . . . . . 6 1.1. Requirements Notation
2. Background . . . . . . . . . . . . . . . . . . . . . . . . . 6 2. Background
2.1. Elliptic curves . . . . . . . . . . . . . . . . . . . . . 6 2.1. Elliptic Curves
2.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 8 2.2. Terminology
2.2.1. Mappings . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1. Mappings
2.2.2. Encodings . . . . . . . . . . . . . . . . . . . . . . 9 2.2.2. Encodings
2.2.3. Random oracle encodings . . . . . . . . . . . . . . . 9 2.2.3. Random Oracle Encodings
2.2.4. Serialization . . . . . . . . . . . . . . . . . . . . 10 2.2.4. Serialization
2.2.5. Domain separation . . . . . . . . . . . . . . . . . . 10 2.2.5. Domain Separation
3. Encoding byte strings to elliptic curves . . . . . . . . . . 11 3. Encoding Byte Strings to Elliptic Curves
3.1. Domain separation requirements . . . . . . . . . . . . . 13 3.1. Domain Separation Requirements
4. Utility functions . . . . . . . . . . . . . . . . . . . . . . 14 4. Utility Functions
4.1. The sgn0 function . . . . . . . . . . . . . . . . . . . . 16 4.1. The sgn0 Function
5. Hashing to a finite field . . . . . . . . . . . . . . . . . . 17 5. Hashing to a Finite Field
5.1. Efficiency considerations in extension fields . . . . . . 18 5.1. Efficiency Considerations in Extension Fields
5.2. hash_to_field implementation . . . . . . . . . . . . . . 19 5.2. hash_to_field Implementation
5.3. expand_message . . . . . . . . . . . . . . . . . . . . . 20 5.3. expand_message
5.3.1. expand_message_xmd . . . . . . . . . . . . . . . . . 20 5.3.1. expand_message_xmd
5.3.2. expand_message_xof . . . . . . . . . . . . . . . . . 22 5.3.2. expand_message_xof
5.3.3. Using DSTs longer than 255 bytes . . . . . . . . . . 23 5.3.3. Using DSTs Longer than 255 Bytes
5.3.4. Defining other expand_message variants . . . . . . . 24 5.3.4. Defining Other expand_message Variants
6. Deterministic mappings . . . . . . . . . . . . . . . . . . . 25 6. Deterministic Mappings
6.1. Choosing a mapping function . . . . . . . . . . . . . . . 25 6.1. Choosing a Mapping Function
6.2. Interface . . . . . . . . . . . . . . . . . . . . . . . . 25 6.2. Interface
6.3. Notation . . . . . . . . . . . . . . . . . . . . . . . . 26 6.3. Notation
6.4. Sign of the resulting point . . . . . . . . . . . . . . . 26 6.4. Sign of the Resulting Point
6.5. Exceptional cases . . . . . . . . . . . . . . . . . . . . 26 6.5. Exceptional Cases
6.6. Mappings for Weierstrass curves . . . . . . . . . . . . . 27 6.6. Mappings for Weierstrass Curves
6.6.1. Shallue-van de Woestijne method . . . . . . . . . . . 27 6.6.1. Shallue-van de Woestijne Method
6.6.2. Simplified Shallue-van de Woestijne-Ulas method . . . 28 6.6.2. Simplified Shallue-van de Woestijne-Ulas Method
6.6.3. Simplified SWU for AB == 0 . . . . . . . . . . . . . 29 6.6.3. Simplified SWU for AB == 0
6.7. Mappings for Montgomery curves . . . . . . . . . . . . . 31 6.7. Mappings for Montgomery Curves
6.7.1. Elligator 2 method . . . . . . . . . . . . . . . . . 31 6.7.1. Elligator 2 Method
6.8. Mappings for twisted Edwards curves . . . . . . . . . . . 32 6.8. Mappings for Twisted Edwards Curves
6.8.1. Rational maps from Montgomery to twisted Edwards 6.8.1. Rational Maps from Montgomery to Twisted Edwards Curves
curves . . . . . . . . . . . . . . . . . . . . . . . 32 6.8.2. Elligator 2 Method
6.8.2. Elligator 2 method . . . . . . . . . . . . . . . . . 33 7. Clearing the Cofactor
7. Clearing the cofactor . . . . . . . . . . . . . . . . . . . . 33 8. Suites for Hashing
8. Suites for hashing . . . . . . . . . . . . . . . . . . . . . 34 8.1. Implementing a Hash-to-Curve Suite
8.1. Implementing a hash-to-curve suite . . . . . . . . . . . 37 8.2. Suites for NIST P-256
8.2. Suites for NIST P-256 . . . . . . . . . . . . . . . . . . 37 8.3. Suites for NIST P-384
8.3. Suites for NIST P-384 . . . . . . . . . . . . . . . . . . 38 8.4. Suites for NIST P-521
8.4. Suites for NIST P-521 . . . . . . . . . . . . . . . . . . 39 8.5. Suites for curve25519 and edwards25519
8.5. Suites for curve25519 and edwards25519 . . . . . . . . . 40 8.6. Suites for curve448 and edwards448
8.6. Suites for curve448 and edwards448 . . . . . . . . . . . 41 8.7. Suites for secp256k1
8.7. Suites for secp256k1 . . . . . . . . . . . . . . . . . . 42 8.8. Suites for BLS12-381
8.8. Suites for BLS12-381 . . . . . . . . . . . . . . . . . . 43 8.8.1. BLS12-381 G1
8.8.1. BLS12-381 G1 . . . . . . . . . . . . . . . . . . . . 43 8.8.2. BLS12-381 G2
8.8.2. BLS12-381 G2 . . . . . . . . . . . . . . . . . . . . 44 8.9. Defining a New Hash-to-Curve Suite
8.9. Defining a new hash-to-curve suite . . . . . . . . . . . 45 8.10. Suite ID Naming Conventions
8.10. Suite ID naming conventions . . . . . . . . . . . . . . . 46 9. IANA Considerations
9. IANA considerations . . . . . . . . . . . . . . . . . . . . . 47 10. Security Considerations
10. Security considerations . . . . . . . . . . . . . . . . . . . 48 10.1. Properties of Encodings
10.1. Properties of encodings . . . . . . . . . . . . . . . . 48 10.2. Hashing Passwords
10.2. Hashing passwords . . . . . . . . . . . . . . . . . . . 49 10.3. Constant-Time Requirements
10.3. Constant-time requirements . . . . . . . . . . . . . . . 49 10.4. encode_to_curve: Output Distribution and
10.4. encode_to_curve: output distribution and Indifferentiability
indifferentiability . . . . . . . . . . . . . . . . . . 49 10.5. hash_to_field Security
10.5. hash_to_field security . . . . . . . . . . . . . . . . . 50 10.6. expand_message_xmd Security
10.6. expand_message_xmd security . . . . . . . . . . . . . . 51 10.7. Domain Separation for expand_message Variants
10.7. Domain separation for expand_message variants . . . . . 51 10.8. Target Security Levels
10.8. Target security levels . . . . . . . . . . . . . . . . . 55 11. References
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 55 11.1. Normative References
12. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 55 11.2. Informative References
13. References . . . . . . . . . . . . . . . . . . . . . . . . . 55 Appendix A. Related Work
13.1. Normative References . . . . . . . . . . . . . . . . . . 55 Appendix B. Hashing to ristretto255
13.2. Informative References . . . . . . . . . . . . . . . . . 56 Appendix C. Hashing to decaf448
Appendix A. Related work . . . . . . . . . . . . . . . . . . . . 65 Appendix D. Rational Maps
Appendix B. Hashing to ristretto255 . . . . . . . . . . . . . . 67 D.1. Generic Mapping from Montgomery to Twisted Edwards
Appendix C. Hashing to decaf448 . . . . . . . . . . . . . . . . 68 D.2. Mapping from Weierstrass to Montgomery
Appendix D. Rational maps . . . . . . . . . . . . . . . . . . . 69 Appendix E. Isogeny Maps for Suites
D.1. Generic Montgomery to twisted Edwards map . . . . . . . . 70 E.1. 3-Isogeny Map for secp256k1
D.2. Weierstrass to Montgomery map . . . . . . . . . . . . . . 72 E.2. 11-Isogeny Map for BLS12-381 G1
Appendix E. Isogeny maps for suites . . . . . . . . . . . . . . 72 E.3. 3-Isogeny Map for BLS12-381 G2
E.1. 3-isogeny map for secp256k1 . . . . . . . . . . . . . . . 73 Appendix F. Straight-Line Implementations of Deterministic
E.2. 11-isogeny map for BLS12-381 G1 . . . . . . . . . . . . . 74 Mappings
E.3. 3-isogeny map for BLS12-381 G2 . . . . . . . . . . . . . 78 F.1. Shallue-van de Woestijne Method
F.2. Simplified SWU Method
Appendix F. Straight-line implementations of deterministic F.2.1. sqrt_ratio Subroutine
mappings . . . . . . . . . . . . . . . . . . . . . . . . 80 F.3. Elligator 2 Method
F.1. Shallue-van de Woestijne method . . . . . . . . . . . . . 80 Appendix G. Curve-Specific Optimized Sample Code
F.2. Simplified SWU method . . . . . . . . . . . . . . . . . . 81 G.1. Interface and Projective Coordinate Systems
F.2.1. sqrt_ratio subroutines . . . . . . . . . . . . . . . 82 G.2. Elligator 2
F.3. Elligator 2 method . . . . . . . . . . . . . . . . . . . 86 G.2.1. curve25519 (q = 5 (mod 8), K = 1)
Appendix G. Curve-specific optimized sample code . . . . . . . . 87 G.2.2. edwards25519
G.1. Interface and projective coordinate systems . . . . . . . 87 G.2.3. curve448 (q = 3 (mod 4), K = 1)
G.2. Elligator 2 . . . . . . . . . . . . . . . . . . . . . . . 88 G.2.4. edwards448
G.2.1. curve25519 (q = 5 (mod 8), K = 1) . . . . . . . . . . 88 G.2.5. Montgomery Curves with q = 3 (mod 4)
G.2.2. edwards25519 . . . . . . . . . . . . . . . . . . . . 89 G.2.6. Montgomery Curves with q = 5 (mod 8)
G.2.3. curve448 (q = 3 (mod 4), K = 1) . . . . . . . . . . . 90 G.3. Cofactor Clearing for BLS12-381 G2
G.2.4. edwards448 . . . . . . . . . . . . . . . . . . . . . 91 Appendix H. Scripts for Parameter Generation
G.2.5. Montgomery curves with q = 3 (mod 4) . . . . . . . . 93 H.1. Finding Z for the Shallue-van de Woestijne Map
G.2.6. Montgomery curves with q = 5 (mod 8) . . . . . . . . 95 H.2. Finding Z for Simplified SWU
G.3. Cofactor clearing for BLS12-381 G2 . . . . . . . . . . . 96 H.3. Finding Z for Elligator 2
Appendix H. Scripts for parameter generation . . . . . . . . . . 98 Appendix I. sqrt and is_square Functions
H.1. Finding Z for the Shallue-van de Woestijne map . . . . . 98 I.1. sqrt for q = 3 (mod 4)
H.2. Finding Z for Simplified SWU . . . . . . . . . . . . . . 99 I.2. sqrt for q = 5 (mod 8)
H.3. Finding Z for Elligator 2 . . . . . . . . . . . . . . . . 100 I.3. sqrt for q = 9 (mod 16)
Appendix I. sqrt and is_square functions . . . . . . . . . . . . 100 I.4. Constant-Time Tonelli-Shanks Algorithm
I.1. sqrt for q = 3 (mod 4) . . . . . . . . . . . . . . . . . 101 I.5. is_square for F = GF(p^2)
I.2. sqrt for q = 5 (mod 8) . . . . . . . . . . . . . . . . . 101 Appendix J. Suite Test Vectors
I.3. sqrt for q = 9 (mod 16) . . . . . . . . . . . . . . . . . 101 J.1. NIST P-256
I.4. Constant-time Tonelli-Shanks algorithm . . . . . . . . . 102 J.1.1. P256_XMD:SHA-256_SSWU_RO_
I.5. is_square for F = GF(p^2) . . . . . . . . . . . . . . . . 103 J.1.2. P256_XMD:SHA-256_SSWU_NU_
Appendix J. Suite test vectors . . . . . . . . . . . . . . . . . 104 J.2. NIST P-384
J.1. NIST P-256 . . . . . . . . . . . . . . . . . . . . . . . 104 J.2.1. P384_XMD:SHA-384_SSWU_RO_
J.1.1. P256_XMD:SHA-256_SSWU_RO_ . . . . . . . . . . . . . . 104 J.2.2. P384_XMD:SHA-384_SSWU_NU_
J.1.2. P256_XMD:SHA-256_SSWU_NU_ . . . . . . . . . . . . . . 106 J.3. NIST P-521
J.2. NIST P-384 . . . . . . . . . . . . . . . . . . . . . . . 108 J.3.1. P521_XMD:SHA-512_SSWU_RO_
J.2.1. P384_XMD:SHA-384_SSWU_RO_ . . . . . . . . . . . . . . 108 J.3.2. P521_XMD:SHA-512_SSWU_NU_
J.2.2. P384_XMD:SHA-384_SSWU_NU_ . . . . . . . . . . . . . . 110 J.4. curve25519
J.3. NIST P-521 . . . . . . . . . . . . . . . . . . . . . . . 112 J.4.1. curve25519_XMD:SHA-512_ELL2_RO_
J.3.1. P521_XMD:SHA-512_SSWU_RO_ . . . . . . . . . . . . . . 112 J.4.2. curve25519_XMD:SHA-512_ELL2_NU_
J.3.2. P521_XMD:SHA-512_SSWU_NU_ . . . . . . . . . . . . . . 115 J.5. edwards25519
J.4. curve25519 . . . . . . . . . . . . . . . . . . . . . . . 117 J.5.1. edwards25519_XMD:SHA-512_ELL2_RO_
J.4.1. curve25519_XMD:SHA-512_ELL2_RO_ . . . . . . . . . . . 117 J.5.2. edwards25519_XMD:SHA-512_ELL2_NU_
J.4.2. curve25519_XMD:SHA-512_ELL2_NU_ . . . . . . . . . . . 119 J.6. curve448
J.5. edwards25519 . . . . . . . . . . . . . . . . . . . . . . 121 J.6.1. curve448_XOF:SHAKE256_ELL2_RO_
J.5.1. edwards25519_XMD:SHA-512_ELL2_RO_ . . . . . . . . . . 121 J.6.2. curve448_XOF:SHAKE256_ELL2_NU_
J.5.2. edwards25519_XMD:SHA-512_ELL2_NU_ . . . . . . . . . . 123 J.7. edwards448
J.6. curve448 . . . . . . . . . . . . . . . . . . . . . . . . 125 J.7.1. edwards448_XOF:SHAKE256_ELL2_RO_
J.6.1. curve448_XOF:SHAKE256_ELL2_RO_ . . . . . . . . . . . 125 J.7.2. edwards448_XOF:SHAKE256_ELL2_NU_
J.6.2. curve448_XOF:SHAKE256_ELL2_NU_ . . . . . . . . . . . 128 J.8. secp256k1
J.7. edwards448 . . . . . . . . . . . . . . . . . . . . . . . 130 J.8.1. secp256k1_XMD:SHA-256_SSWU_RO_
J.7.1. edwards448_XOF:SHAKE256_ELL2_RO_ . . . . . . . . . . 130 J.8.2. secp256k1_XMD:SHA-256_SSWU_NU_
J.7.2. edwards448_XOF:SHAKE256_ELL2_NU_ . . . . . . . . . . 133 J.9. BLS12-381 G1
J.9.1. BLS12381G1_XMD:SHA-256_SSWU_RO_
J.8. secp256k1 . . . . . . . . . . . . . . . . . . . . . . . . 135 J.9.2. BLS12381G1_XMD:SHA-256_SSWU_NU_
J.8.1. secp256k1_XMD:SHA-256_SSWU_RO_ . . . . . . . . . . . 135 J.10. BLS12-381 G2
J.8.2. secp256k1_XMD:SHA-256_SSWU_NU_ . . . . . . . . . . . 137 J.10.1. BLS12381G2_XMD:SHA-256_SSWU_RO_
J.9. BLS12-381 G1 . . . . . . . . . . . . . . . . . . . . . . 139 J.10.2. BLS12381G2_XMD:SHA-256_SSWU_NU_
J.9.1. BLS12381G1_XMD:SHA-256_SSWU_RO_ . . . . . . . . . . . 139 Appendix K. Expand Test Vectors
J.9.2. BLS12381G1_XMD:SHA-256_SSWU_NU_ . . . . . . . . . . . 141 K.1. expand_message_xmd(SHA-256)
J.10. BLS12-381 G2 . . . . . . . . . . . . . . . . . . . . . . 143 K.2. expand_message_xmd(SHA-256) (Long DST)
J.10.1. BLS12381G2_XMD:SHA-256_SSWU_RO_ . . . . . . . . . . 143 K.3. expand_message_xmd(SHA-512)
J.10.2. BLS12381G2_XMD:SHA-256_SSWU_NU_ . . . . . . . . . . 147 K.4. expand_message_xof(SHAKE128)
Appendix K. Expand test vectors . . . . . . . . . . . . . . . . 149 K.5. expand_message_xof(SHAKE128) (Long DST)
K.1. expand_message_xmd(SHA-256) . . . . . . . . . . . . . . . 150 K.6. expand_message_xof(SHAKE256)
K.2. expand_message_xmd(SHA-256) (long DST) . . . . . . . . . 154 Acknowledgements
K.3. expand_message_xmd(SHA-512) . . . . . . . . . . . . . . . 158 Contributors
K.4. expand_message_xof(SHAKE128) . . . . . . . . . . . . . . 163 Authors' Addresses
K.5. expand_message_xof(SHAKE128) (long DST) . . . . . . . . . 167
K.6. expand_message_xof(SHAKE256) . . . . . . . . . . . . . . 171
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 175
1. Introduction 1. Introduction
Many cryptographic protocols require a procedure that encodes an Many cryptographic protocols require a procedure that encodes an
arbitrary input, e.g., a password, to a point on an elliptic curve. arbitrary input, e.g., a password, to a point on an elliptic curve.
This procedure is known as hashing to an elliptic curve, where the This procedure is known as hashing to an elliptic curve, where the
hashing procedure provides collision resistance and does not reveal hashing procedure provides collision resistance and does not reveal
the discrete logarithm of the output point. Prominent examples of the discrete logarithm of the output point. Prominent examples of
cryptosystems that hash to elliptic curves include password- cryptosystems that hash to elliptic curves include password-
authenticated key exchanges [BM92] [J96] [BMP00] [p1363.2], Identity- authenticated key exchanges [BM92] [J96] [BMP00] [p1363.2], Identity-
Based Encryption [BF01], Boneh-Lynn-Shacham signatures [BLS01] Based Encryption [BF01], Boneh-Lynn-Shacham signatures [BLS01]
[I-D.irtf-cfrg-bls-signature], Verifiable Random Functions [MRV99] [BLS-SIG], Verifiable Random Functions [MRV99] [VRF], and Oblivious
[I-D.irtf-cfrg-vrf], and Oblivious Pseudorandom Functions [NR97] Pseudorandom Functions [NR97] [OPRFs].
[I-D.irtf-cfrg-voprf].
Unfortunately for implementors, the precise hash function that is Unfortunately for implementors, the precise hash function that is
suitable for a given protocol implemented using a given elliptic suitable for a given protocol implemented using a given elliptic
curve is often unclear from the protocol's description. Meanwhile, curve is often unclear from the protocol's description. Meanwhile,
an incorrect choice of hash function can have disastrous consequences an incorrect choice of hash function can have disastrous consequences
for security. for security.
This document aims to bridge this gap by providing a comprehensive This document aims to bridge this gap by providing a comprehensive
set of recommended algorithms for a range of curve types. Each set of recommended algorithms for a range of curve types. Each
algorithm conforms to a common interface: it takes as input an algorithm conforms to a common interface: it takes as input an
skipping to change at page 6, line 10 skipping to change at line 231
algorithm, describe the security rationale behind each algorithm, describe the security rationale behind each
recommendation, and give guidance for elliptic curves that are not recommendation, and give guidance for elliptic curves that are not
explicitly covered. We also present optimized implementations for explicitly covered. We also present optimized implementations for
internal functions used by these algorithms. internal functions used by these algorithms.
Readers wishing to quickly specify or implement a conforming hash Readers wishing to quickly specify or implement a conforming hash
function should consult Section 8, which lists recommended hash-to- function should consult Section 8, which lists recommended hash-to-
curve suites and describes both how to implement an existing suite curve suites and describes both how to implement an existing suite
and how to specify a new one. and how to specify a new one.
This document does not cover rejection sampling methods, sometimes This document does not specify probabilistic rejection sampling
referred to as "try-and-increment" or "hunt-and-peck," because the methods, sometimes referred to as "try-and-increment" or "hunt-and-
goal is to describe algorithms that can plausibly be computed in peck," because the goal is to specify algorithms that can plausibly
constant time. Use of these rejection methods is NOT RECOMMENDED, be computed in constant time. Use of these probabilistic rejection
because they have been a perennial cause of side-channel methods is NOT RECOMMENDED, because they have been a perennial cause
vulnerabilities. See Dragonblood [VR20] as one example of this of side-channel vulnerabilities. See Dragonblood [VR20] as one
problem in practice, and see Appendix A for a further description of example of this problem in practice, and see Appendix A for an
rejection sampling methods. informal description of rejection sampling methods and the timing
side-channels they introduce.
This document represents the consensus of the Crypto Forum Research This document represents the consensus of the Crypto Forum Research
Group (CFRG). Group (CFRG).
1.1. Requirements Notation 1.1. Requirements Notation
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in "OPTIONAL" in this document are to be interpreted as described in
BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here. capitals, as shown here.
2. Background 2. Background
2.1. Elliptic curves 2.1. Elliptic Curves
The following is a brief definition of elliptic curves, with an The following is a brief definition of elliptic curves, with an
emphasis on important parameters and their relation to hashing to emphasis on important parameters and their relation to hashing to
curves. For further reference on elliptic curves, consult curves. For further reference on elliptic curves, consult
[CFADLNV05] or [W08]. [CFADLNV05] or [W08].
Let F be the finite field GF(q) of prime characteristic p > 3. (This Let F be the finite field GF(q) of prime characteristic p > 3. (This
document does not consider elliptic curves over fields of document does not consider elliptic curves over fields of
characteristic 2 or 3.) In most cases F is a prime field, so q = p. characteristic 2 or 3.) In most cases, F is a prime field, so q = p.
Otherwise, F is an extension field, so q = p^m for an integer m > 1. Otherwise, F is an extension field, so q = p^m for an integer m > 1.
This document writes elements of extension fields in a primitive This document writes elements of extension fields in a primitive
element or polynomial basis, i.e., as a vector of m elements of GF(p) element or polynomial basis, i.e., as a vector of m elements of GF(p)
written in ascending order by degree. The entries of this vector are written in ascending order by degree. The entries of this vector are
indexed in ascending order starting from 1, i.e., x = (x_1, x_2, ..., indexed in ascending order starting from 1, i.e., x = (x_1, x_2, ...,
x_m). For example, if q = p^2 and the primitive element basis is (1, x_m). For example, if q = p^2 and the primitive element basis is (1,
I), then x = (a, b) corresponds to the element a + b * I, where x_1 = I), then x = (a, b) corresponds to the element a + b * I, where x_1 =
a and x_2 = b. (Note that all choices of basis are isomorphic, but a and x_2 = b. (Note that all choices of basis are isomorphic, but
certain choices may result in a more efficient implementation; this certain choices may result in a more efficient implementation; this
document does not make any particular assumptions about choice of document does not make any particular assumptions about choice of
skipping to change at page 7, line 4 skipping to change at line 275
This document writes elements of extension fields in a primitive This document writes elements of extension fields in a primitive
element or polynomial basis, i.e., as a vector of m elements of GF(p) element or polynomial basis, i.e., as a vector of m elements of GF(p)
written in ascending order by degree. The entries of this vector are written in ascending order by degree. The entries of this vector are
indexed in ascending order starting from 1, i.e., x = (x_1, x_2, ..., indexed in ascending order starting from 1, i.e., x = (x_1, x_2, ...,
x_m). For example, if q = p^2 and the primitive element basis is (1, x_m). For example, if q = p^2 and the primitive element basis is (1,
I), then x = (a, b) corresponds to the element a + b * I, where x_1 = I), then x = (a, b) corresponds to the element a + b * I, where x_1 =
a and x_2 = b. (Note that all choices of basis are isomorphic, but a and x_2 = b. (Note that all choices of basis are isomorphic, but
certain choices may result in a more efficient implementation; this certain choices may result in a more efficient implementation; this
document does not make any particular assumptions about choice of document does not make any particular assumptions about choice of
basis.) basis.)
An elliptic curve E is specified by an equation in two variables and An elliptic curve E is specified by an equation in two variables and
a finite field F. An elliptic curve equation takes one of several a finite field F. An elliptic curve equation takes one of several
standard forms, including (but not limited to) Weierstrass, standard forms, including (but not limited to) Weierstrass,
Montgomery, and Edwards. Montgomery, and Edwards.
The curve E induces an algebraic group of order n, meaning that the The curve E induces an algebraic group of order n, meaning that the
group has n distinct elements. (This document uses additive notation group has n distinct elements. (This document uses additive notation
for the elliptic curve group operation.) Elements of an elliptic for the elliptic curve group operation.) Elements of an elliptic
curve group are points with affine coordinates (x, y) satisfying the curve group are points with affine coordinates (x, y) satisfying the
curve equation, where x and y are elements of F. In addition, all curve equation, where x and y are elements of F. In addition, all
elliptic curve groups have a distinguished element, the identity elliptic curve groups have a distinguished element, the identity
point, which acts as the identity element for the group operation. point, which acts as the identity element for the group operation.
On certain curves (including Weierstrass and Montgomery curves), the On certain curves (including Weierstrass and Montgomery curves), the
identity point cannot be represented as an (x, y) coordinate pair. identity point cannot be represented as an (x, y) coordinate pair.
For security reasons, cryptographic uses of elliptic curves generally For security reasons, cryptographic applications of elliptic curves
require using a (sub)group of prime order. Let G be such a subgroup generally require using a (sub)group of prime order. Let G be such a
of the curve of prime order r, where n = h * r. In this equation, h subgroup of the curve of prime order r, where n = h * r. In this
is an integer called the cofactor. An algorithm that takes as input equation, h is an integer called the cofactor. An algorithm that
an arbitrary point on the curve E and produces as output a point in takes as input an arbitrary point on the curve E and produces as
the subgroup G of E is said to "clear the cofactor." Such algorithms output a point in the subgroup G of E is said to "clear the
are discussed in Section 7. cofactor." Such algorithms are discussed in Section 7.
Certain hash-to-curve algorithms restrict the form of the curve Certain hash-to-curve algorithms restrict the form of the curve
equation, the characteristic of the field, or the parameters of the equation, the characteristic of the field, or the parameters of the
curve. For each algorithm presented, this document lists the curve. For each algorithm presented, this document lists the
relevant restrictions. relevant restrictions.
The table below summarizes quantities relevant to hashing to curves: The table below summarizes quantities relevant to hashing to curves:
+========+=====================+=======================+ +========+=====================+=======================+
| Symbol | Meaning | Relevance | | Symbol | Meaning | Relevance |
+========+=====================+=======================+ +========+=====================+=======================+
| F,q,p | A finite field F of | For prime fields, q = | | F,q,p | A finite field F of | For prime fields, |
| | characteristic p | p; otherwise, q = p^m | | | characteristic p | q = p; otherwise, |
| | and #F = q = p^m. | and m>1. | | | and #F = q = p^m. | q = p^m and m>1. |
+--------+---------------------+-----------------------+ +--------+---------------------+-----------------------+
| E | Elliptic curve. | E is specified by an | | E | Elliptic curve. | E is specified by an |
| | | equation and a field | | | | equation and a field |
| | | F. | | | | F. |
+--------+---------------------+-----------------------+ +--------+---------------------+-----------------------+
| n | Number of points on | n = h * r, for h and | | n | Number of points on | n = h * r, for h and |
| | the elliptic curve | r defined below. | | | the elliptic curve | r defined below. |
| | E. | | | | E. | |
+--------+---------------------+-----------------------+ +--------+---------------------+-----------------------+
| G | A prime-order | Destination group to | | G | A prime-order | G is a destination |
| | subgroup of the | which byte strings | | | subgroup of the | group to which byte |
| | points on E. | are encoded. | | | points on E. | strings are encoded. |
+--------+---------------------+-----------------------+ +--------+---------------------+-----------------------+
| r | Order of G. | r is a prime factor | | r | Order of G. | r is a prime factor |
| | | of n (usually, the | | | | of n (usually, the |
| | | largest such factor). | | | | largest such factor). |
+--------+---------------------+-----------------------+ +--------+---------------------+-----------------------+
| h | Cofactor, h >= 1. | An integer satisfying | | h | Cofactor, h >= 1. | h is an integer |
| | | n = h * r. | | | | satisfying n = h * r. |
+--------+---------------------+-----------------------+ +--------+---------------------+-----------------------+
Table 1: Summary of symbols and their definitions. Table 1: Summary of Symbols and Their Definitions
2.2. Terminology 2.2. Terminology
In this section, we define important terms used throughout the In this section, we define important terms used throughout the
document. document.
2.2.1. Mappings 2.2.1. Mappings
A mapping is a deterministic function from an element of the field F A mapping is a deterministic function from an element of the field F
to a point on an elliptic curve E defined over F. to a point on an elliptic curve E defined over F.
In general, the set of all points that a mapping can produce over all In general, the set of all points that a mapping can produce over all
possible inputs may be only a subset of the points on an elliptic possible inputs may be only a subset of the points on an elliptic
curve (i.e., the mapping may not be surjective). In addition, a curve (i.e., the mapping may not be surjective). In addition, a
mapping may output the same point for two or more distinct inputs mapping may output the same point for two or more distinct inputs
(i.e., the mapping may not be injective). For example, consider a (i.e., the mapping may not be injective). For example, consider a
mapping from F to an elliptic curve having n points: if the number of mapping from F to an elliptic curve having n points: if the number of
elements of F is not equal to n, then this mapping cannot be elements of F is not equal to n, then this mapping cannot be
bijective (i.e., both injective and surjective) since the mapping is bijective (i.e., both injective and surjective), since the mapping is
defined to be deterministic. defined to be deterministic.
Mappings may also be invertible, meaning that there is an efficient Mappings may also be invertible, meaning that there is an efficient
algorithm that, for any point P output by the mapping, outputs an x algorithm that, for any point P output by the mapping, outputs an x
in F such that applying the mapping to x outputs P. Some of the in F such that applying the mapping to x outputs P. Some of the
mappings given in Section 6 are invertible, but this document does mappings given in Section 6 are invertible, but this document does
not discuss inversion algorithms. not discuss inversion algorithms.
2.2.2. Encodings 2.2.2. Encodings
skipping to change at page 9, line 31 skipping to change at line 381
deterministic mapping takes that element as input and outputs a point deterministic mapping takes that element as input and outputs a point
on an elliptic curve E defined over F. Since Hf takes arbitrary- on an elliptic curve E defined over F. Since Hf takes arbitrary-
length byte strings as inputs, it cannot be injective: the set of length byte strings as inputs, it cannot be injective: the set of
inputs is larger than the set of outputs, so there must be distinct inputs is larger than the set of outputs, so there must be distinct
inputs that give the same output (i.e., there must be collisions). inputs that give the same output (i.e., there must be collisions).
Thus, any encoding built from Hf is also not injective. Thus, any encoding built from Hf is also not injective.
Like mappings, encodings may be invertible, meaning that there is an Like mappings, encodings may be invertible, meaning that there is an
efficient algorithm that, for any point P output by the encoding, efficient algorithm that, for any point P output by the encoding,
outputs a string s such that applying the encoding to s outputs P. outputs a string s such that applying the encoding to s outputs P.
The instantiation of Hf used by all encodings specified in this However, the instantiation of Hf used by all encodings specified in
document (Section 5) is not invertible. Thus, the encodings are also this document (Section 5) is not invertible; thus, those encodings
not invertible. are also not invertible.
In some applications of hashing to elliptic curves, it is important In some applications of hashing to elliptic curves, it is important
that encodings do not leak information through side channels. [VR20] that encodings do not leak information through side channels. [VR20]
is one example of this type of leakage leading to a security is one example of this type of leakage leading to a security
vulnerability. See Section 10.3 for further discussion. vulnerability. See Section 10.3 for further discussion.
2.2.3. Random oracle encodings 2.2.3. Random Oracle Encodings
A random-oracle encoding satisfies a strong property: it can be A random-oracle encoding satisfies a strong property: it can be
proved indifferentiable from a random oracle [MRH04] under a suitable proved indifferentiable from a random oracle [MRH04] under a suitable
assumption. assumption.
Both constructions described in Section 3 are indifferentiable from Both constructions described in Section 3 are indifferentiable from
random oracles [MRH04] when instantiated following the guidelines in random oracles [MRH04] when instantiated following the guidelines in
this document. The constructions differ in their output this document. The constructions differ in their output
distributions: one gives a uniformly random point on the curve, the distributions: one gives a uniformly random point on the curve, the
other gives a point sampled from a nonuniform distribution. other gives a point sampled from a nonuniform distribution.
A random-oracle encoding with a uniform output distribution is A random-oracle encoding with a uniform output distribution is
suitable for use in many cryptographic protocols proven secure in the suitable for use in many cryptographic protocols proven secure in the
random oracle model. See Section 10.1 for further discussion. random-oracle model. See Section 10.1 for further discussion.
2.2.4. Serialization 2.2.4. Serialization
A procedure related to encoding is the conversion of an elliptic A procedure related to encoding is the conversion of an elliptic
curve point to a bit string. This is called serialization, and is curve point to a bit string. This is called serialization, and it is
typically used for compactly storing or transmitting points. The typically used for compactly storing or transmitting points. The
inverse operation, deserialization, converts a bit string to an inverse operation, deserialization, converts a bit string to an
elliptic curve point. For example, [SEC1] and [p1363a] give standard elliptic curve point. For example, [SEC1] and [p1363a] give standard
methods for serialization and deserialization. methods for serialization and deserialization.
Deserialization is different from encoding in that only certain Deserialization is different from encoding in that only certain
strings (namely, those output by the serialization procedure) can be strings (namely, those output by the serialization procedure) can be
deserialized. In contrast, this document is concerned with encodings deserialized. In contrast, this document is concerned with encodings
from arbitrary strings to elliptic curve points. This document does from arbitrary strings to elliptic curve points. This document does
not cover serialization or deserialization. not cover serialization or deserialization.
2.2.5. Domain separation 2.2.5. Domain Separation
Cryptographic protocols proven secure in the random oracle model are Cryptographic protocols proven secure in the random-oracle model are
often analyzed under the assumption that the random oracle only often analyzed under the assumption that the random oracle only
answers queries associated with that protocol (including queries made answers queries associated with that protocol (including queries made
by adversaries) [BR93]. In practice, this assumption does not hold by adversaries) [BR93]. In practice, this assumption does not hold
if two protocols use the same function to instantiate the random if two protocols use the same function to instantiate the random
oracle. Concretely, consider protocols P1 and P2 that query a random oracle. Concretely, consider protocols P1 and P2 that query a
oracle RO: if P1 and P2 both query RO on the same value x, the random-oracle RO: if P1 and P2 both query RO on the same value x, the
security analysis of one or both protocols may be invalidated. security analysis of one or both protocols may be invalidated.
A common way of addressing this issue is called domain separation, A common way of addressing this issue is called domain separation,
which allows a single random oracle to simulate multiple, independent which allows a single random oracle to simulate multiple, independent
oracles. This is effected by ensuring that each simulated oracle oracles. This is effected by ensuring that each simulated oracle
sees queries that are distinct from those seen by all other simulated sees queries that are distinct from those seen by all other simulated
oracles. For example, to simulate two oracles RO1 and RO2 given a oracles. For example, to simulate two oracles RO1 and RO2 given a
single oracle RO, one might define single oracle RO, one might define
RO1(x) := RO("RO1" || x) RO1(x) := RO("RO1" || x)
RO2(x) := RO("RO2" || x) RO2(x) := RO("RO2" || x)
where || is the concatenation operator. In this example, "RO1" and where || is the concatenation operator. In this example, "RO1" and
"RO2" are called domain separation tags; they ensure that queries to "RO2" are called domain separation tags (DSTs); they ensure that
RO1 and RO2 cannot result in identical queries to RO, meaning that it queries to RO1 and RO2 cannot result in identical queries to RO,
is safe to treat RO1 and RO2 as independent oracles. meaning that it is safe to treat RO1 and RO2 as independent oracles.
In general, domain separation requires defining a distinct injective In general, domain separation requires defining a distinct injective
encoding for each oracle being simulated. In the above example, encoding for each oracle being simulated. In the above example,
"RO1" and "RO2" have the same length and thus satisfy this "RO1" and "RO2" have the same length and thus satisfy this
requirement when used as prefixes. The algorithms specified in this requirement when used as prefixes. The algorithms specified in this
document take a different approach to ensuring injectivity; see document take a different approach to ensuring injectivity; see
Section 5.3 and Section 10.7 for more details. Sections 5.3 and 10.7 for more details.
3. Encoding byte strings to elliptic curves 3. Encoding Byte Strings to Elliptic Curves
This section presents a general framework and interface for encoding This section presents a general framework and interface for encoding
byte strings to points on an elliptic curve. The constructions in byte strings to points on an elliptic curve. The constructions in
this section rely on three basic functions: this section rely on three basic functions:
* The function hash_to_field hashes arbitrary-length byte strings to * The function hash_to_field hashes arbitrary-length byte strings to
a list of one or more elements of a finite field F; its a list of one or more elements of a finite field F; its
implementation is defined in Section 5. implementation is defined in Section 5.
hash_to_field(msg, count) hash_to_field(msg, count)
Inputs: Input:
- msg, a byte string containing the message to hash. - msg, a byte string containing the message to hash.
- count, the number of elements of F to output. - count, the number of elements of F to output.
Outputs: Output:
- (u_0, ..., u_(count - 1)), a list of field elements. - (u_0, ..., u_(count - 1)), a list of field elements.
Steps: defined in Section 5. Steps: defined in Section 5.
* The function map_to_curve calculates a point on the elliptic curve * The function map_to_curve calculates a point on the elliptic curve
E from an element of the finite field F over which E is defined. E from an element of the finite field F over which E is defined.
Section 6 describes mappings for a range of curve families. Section 6 describes mappings for a range of curve families.
map_to_curve(u) map_to_curve(u)
skipping to change at page 13, line 6 skipping to change at line 543
Steps: Steps:
1. u = hash_to_field(msg, 2) 1. u = hash_to_field(msg, 2)
2. Q0 = map_to_curve(u[0]) 2. Q0 = map_to_curve(u[0])
3. Q1 = map_to_curve(u[1]) 3. Q1 = map_to_curve(u[1])
4. R = Q0 + Q1 # Point addition 4. R = Q0 + Q1 # Point addition
5. P = clear_cofactor(R) 5. P = clear_cofactor(R)
6. return P 6. return P
Each hash-to-curve suite in Section 8 instantiates one of these Each hash-to-curve suite in Section 8 instantiates one of these
encoding functions for a specifc elliptic curve. encoding functions for a specific elliptic curve.
3.1. Domain separation requirements 3.1. Domain Separation Requirements
All uses of the encoding functions defined in this document MUST All uses of the encoding functions defined in this document MUST
include domain separation (Section 2.2.5) to avoid interfering with include domain separation (Section 2.2.5) to avoid interfering with
other uses of similar functionality. other uses of similar functionality.
Applications that instantiate multiple, independent instances of Applications that instantiate multiple, independent instances of
either hash_to_curve or encode_to_curve MUST enforce domain either hash_to_curve or encode_to_curve MUST enforce domain
separation between those instances. This requirement applies both in separation between those instances. This requirement applies in both
the case of multiple instances targeting the same curve and in the the case of multiple instances targeting the same curve and the case
case of multiple instances targeting different curves. (This is of multiple instances targeting different curves. (This is because
because the internal hash_to_field primitive (Section 5) requires the internal hash_to_field primitive (Section 5) requires domain
domain separation to guarantee independent outputs.) separation to guarantee independent outputs.)
Domain separation is enforced with a domain separation tag (DST), Domain separation is enforced with a domain separation tag (DST),
which is a byte string constructed according to the following which is a byte string constructed according to the following
requirements: requirements:
1. Tags MUST be supplied as the DST parameter to hash_to_field, as 1. Tags MUST be supplied as the DST parameter to hash_to_field, as
described in Section 5. described in Section 5.
2. Tags MUST have nonzero length. A minimum length of 16 bytes is 2. Tags MUST have nonzero length. A minimum length of 16 bytes is
RECOMMENDED to reduce the chance of collisions with other RECOMMENDED to reduce the chance of collisions with other
skipping to change at page 13, line 42 skipping to change at line 579
3. Tags SHOULD begin with a fixed identification string that is 3. Tags SHOULD begin with a fixed identification string that is
unique to the application. unique to the application.
4. Tags SHOULD include a version number. 4. Tags SHOULD include a version number.
5. For applications that define multiple ciphersuites, each 5. For applications that define multiple ciphersuites, each
ciphersuite's tag MUST be different. For this purpose, it is ciphersuite's tag MUST be different. For this purpose, it is
RECOMMENDED to include a ciphersuite identifier in each tag. RECOMMENDED to include a ciphersuite identifier in each tag.
6. For applications that use multiple encodings, either to the same 6. For applications that use multiple encodings, to either the same
curve or to different curves, each encoding MUST use a different curve or different curves, each encoding MUST use a different
tag. For this purpose, it is RECOMMENDED to include the tag. For this purpose, it is RECOMMENDED to include the
encoding's Suite ID (Section 8) in the domain separation tag. encoding's Suite ID (Section 8) in the domain separation tag.
For independent encodings based on the same suite, each tag For independent encodings based on the same suite, each tag
SHOULD also include a distinct identifier, e.g., "ENC1" and SHOULD also include a distinct identifier, e.g., "ENC1" and
"ENC2". "ENC2".
As an example, consider a fictional application named Quux that As an example, consider a fictional application named Quux that
defines several different ciphersuites, each for a different curve. defines several different ciphersuites, each for a different curve.
A reasonable choice of tag is "QUUX-V<xx>-CS<yy>-<suiteID>", where A reasonable choice of tag is "QUUX-V<xx>-CS<yy>-<suiteID>", where
<xx> and <yy> are two-digit numbers indicating the version and <xx> and <yy> are two-digit numbers indicating the version and
skipping to change at page 14, line 19 skipping to change at line 605
requires two independent random oracles to the same curve. requires two independent random oracles to the same curve.
Reasonable choices of tags for these oracles are "BAZ-V<xx>-CS<yy>- Reasonable choices of tags for these oracles are "BAZ-V<xx>-CS<yy>-
<suiteID>-ENC1" and "BAZ-V<xx>-CS<yy>-<suiteID>-ENC2", respectively, <suiteID>-ENC1" and "BAZ-V<xx>-CS<yy>-<suiteID>-ENC2", respectively,
where <xx>, <yy>, and <suiteID> are as described above. where <xx>, <yy>, and <suiteID> are as described above.
The example tags given above are assumed to be ASCII-encoded byte The example tags given above are assumed to be ASCII-encoded byte
strings without null termination, which is the RECOMMENDED format. strings without null termination, which is the RECOMMENDED format.
Other encodings can be used, but in all cases the encoding as a Other encodings can be used, but in all cases the encoding as a
sequence of bytes MUST be specified unambiguously. sequence of bytes MUST be specified unambiguously.
4. Utility functions 4. Utility Functions
Algorithms in this document use the utility functions described Algorithms in this document use the utility functions described
below, plus standard arithmetic operations (addition, multiplication, below, plus standard arithmetic operations (addition, multiplication,
modular reduction, etc.) and elliptic curve point operations (point modular reduction, etc.) and elliptic curve point operations (point
addition and scalar multiplication). addition and scalar multiplication).
For security, implementations of these functions SHOULD be constant For security, implementations of these functions SHOULD be constant
time: in brief, this means that execution time and memory access time: in brief, this means that execution time and memory access
patterns SHOULD NOT depend on the values of secret inputs, patterns SHOULD NOT depend on the values of secret inputs,
intermediate values, or outputs. For such constant-time intermediate values, or outputs. For such constant-time
implementations, all arithmetic, comparisons, and assignments MUST implementations, all arithmetic, comparisons, and assignments MUST
also be implemented in constant time. Section 10.3 briefly discusses also be implemented in constant time. Section 10.3 briefly discusses
constant-time security issues. constant-time security issues.
Guidance on implementing low-level operations (in constant time or Guidance on implementing low-level operations (in constant time or
otherwise) is beyond the scope of this document; readers should otherwise) is beyond the scope of this document; readers should
consult standard reference material [MOV96] [CFADLNV05]. consult standard reference material [MOV96] [CFADLNV05].
* CMOV(a, b, c): If c is False, CMOV returns a, otherwise it returns * CMOV(a, b, c): If c is False, CMOV returns a; otherwise, it
b. For constant-time implementations, this operation must run in returns b. For constant-time implementations, this operation must
time independent of the value of c. run in a time that is independent of the value of c.
* AND, OR, NOT, and XOR are standard bitwise logical operators. For * AND, OR, NOT, and XOR are standard bitwise logical operators. For
constant-time implementations, short-circuit operators MUST be constant-time implementations, short-circuit operators MUST be
avoided. avoided.
* is_square(x): This function returns True whenever the value x is a * is_square(x): This function returns True whenever the value x is a
square in the field F. By Euler's criterion, this function can be square in the field F. By Euler's criterion, this function can be
calculated in constant time as calculated in constant time as
is_square(x) := { True, if x^((q - 1) / 2) is 0 or 1 in F; is_square(x) := { True, if x^((q - 1) / 2) is 0 or 1 in F;
skipping to change at page 15, line 47 skipping to change at line 681
such methods is beyond the scope of this document. such methods is beyond the scope of this document.
* I2OSP and OS2IP: These functions are used to convert a byte string * I2OSP and OS2IP: These functions are used to convert a byte string
to and from a non-negative integer as described in [RFC8017]. to and from a non-negative integer as described in [RFC8017].
(Note that these functions operate on byte strings in big-endian (Note that these functions operate on byte strings in big-endian
byte order.) byte order.)
* a || b: denotes the concatenation of byte strings a and b. For * a || b: denotes the concatenation of byte strings a and b. For
example, "ABC" || "DEF" == "ABCDEF". example, "ABC" || "DEF" == "ABCDEF".
* substr(str, sbegin, slen): for a byte string str, this function * substr(str, sbegin, slen): For a byte string str, this function
returns the slen-byte substring starting at position sbegin; returns the slen-byte substring starting at position sbegin;
positions are zero indexed. For example, substr("ABCDEFG", 2, 3) positions are zero indexed. For example, substr("ABCDEFG", 2, 3)
== "CDE". == "CDE".
* len(str): for a byte string str, this function returns the length * len(str): For a byte string str, this function returns the length
of str in bytes. For example, len("ABC") == 3. of str in bytes. For example, len("ABC") == 3.
* strxor(str1, str2): for byte strings str1 and str2, strxor(str1, * strxor(str1, str2): For byte strings str1 and str2, strxor(str1,
str2) returns the bitwise XOR of the two strings. For example, str2) returns the bitwise XOR of the two strings. For example,
strxor("abc", "XYZ") == "9;9" (the strings in this example are strxor("abc", "XYZ") == "9;9" (the strings in this example are
ASCII literals, but strxor is defined for arbitrary byte strings). ASCII literals, but strxor is defined for arbitrary byte strings).
In this document, strxor is only applied to inputs of equal In this document, strxor is only applied to inputs of equal
length. length.
4.1. The sgn0 function 4.1. The sgn0 Function
This section defines a generic sgn0 implementation that applies to This section defines a generic sgn0 implementation that applies to
any field F = GF(p^m). It also gives simplified implementations for any field F = GF(p^m). It also gives simplified implementations for
the cases F = GF(p) and F = GF(p^2). the cases F = GF(p) and F = GF(p^2).
The definition of the sgn0 function for extension fields relies on The definition of the sgn0 function for extension fields relies on
the polynomial basis or vector representation of field elements, and the polynomial basis or vector representation of field elements, and
iterates over the entire vector representation of the input element. iterates over the entire vector representation of the input element.
As a result, sgn0 depends on the primitive polynomial used to define As a result, sgn0 depends on the primitive polynomial used to define
the polynomial basis; see Section 8 for more information about this the polynomial basis; see Section 8 for more information about this
skipping to change at page 17, line 27 skipping to change at line 754
Input: x, an element of GF(p^2). Input: x, an element of GF(p^2).
Output: 0 or 1. Output: 0 or 1.
Steps: Steps:
1. sign_0 = x_0 mod 2 1. sign_0 = x_0 mod 2
2. zero_0 = x_0 == 0 2. zero_0 = x_0 == 0
3. sign_1 = x_1 mod 2 3. sign_1 = x_1 mod 2
4. s = sign_0 OR (zero_0 AND sign_1) # Avoid short-circuit logic ops 4. s = sign_0 OR (zero_0 AND sign_1) # Avoid short-circuit logic ops
5. return s 5. return s
5. Hashing to a finite field 5. Hashing to a Finite Field
The hash_to_field function hashes a byte string msg of arbitrary The hash_to_field function hashes a byte string msg of arbitrary
length into one or more elements of a field F. This function works length into one or more elements of a field F. This function works
in two steps: it first hashes the input byte string to produce a in two steps: it first hashes the input byte string to produce a
uniformly random byte string, and then interprets this byte string as uniformly random byte string, and then interprets this byte string as
one or more elements of F. one or more elements of F.
For the first step, hash_to_field calls an auxiliary function For the first step, hash_to_field calls an auxiliary function
expand_message. This document defines two variants of expand_message. This document defines two variants of
expand_message: one appropriate for hash functions like SHA-2 expand_message: one appropriate for hash functions like SHA-2
[FIPS180-4] or SHA-3 [FIPS202], and another appropriate for [FIPS180-4] or SHA-3 [FIPS202], and another appropriate for
extendable-output functions such as SHAKE128 [FIPS202]. Security extendable-output functions such as SHAKE128 [FIPS202]. Security
considerations for each expand_message variant are discussed below considerations for each expand_message variant are discussed below
(Section 5.3.1, Section 5.3.2). (Sections 5.3.1 and 5.3.2).
Implementors MUST NOT use rejection sampling to generate a uniformly Implementors MUST NOT use rejection sampling to generate a uniformly
random element of F, to ensure that the hash_to_field function is random element of F, to ensure that the hash_to_field function is
amenable to constant-time implementation. The reason is that amenable to constant-time implementation. The reason is that
rejection sampling procedures are difficult to implement in constant rejection sampling procedures are difficult to implement in constant
time, and later well-meaning "optimizations" may silently render an time, and later well-meaning "optimizations" may silently render an
implementation non-constant-time. This means that any hash_to_field implementation non-constant-time. This means that any hash_to_field
function based on rejection sampling would be incompatible with function based on rejection sampling would be incompatible with
constant-time implementation. constant-time implementation.
skipping to change at page 18, line 33 skipping to change at line 807
targeting k-bit security. For each such integer, hash_to_field uses targeting k-bit security. For each such integer, hash_to_field uses
expand_message to obtain L uniform bytes, where expand_message to obtain L uniform bytes, where
L = ceil((ceil(log2(p)) + k) / 8) L = ceil((ceil(log2(p)) + k) / 8)
These uniform bytes are then interpreted as an integer via OS2IP. These uniform bytes are then interpreted as an integer via OS2IP.
For example, for a 255-bit prime p, and k = 128-bit security, L = For example, for a 255-bit prime p, and k = 128-bit security, L =
ceil((255 + 128) / 8) = 48 bytes. ceil((255 + 128) / 8) = 48 bytes.
Note that k is an upper bound on the security level for the Note that k is an upper bound on the security level for the
corresponding curve. See Section 10.8 for more details, and corresponding curve. See Section 10.8 for more details and
Section 8.9 for guidelines on choosing k for a given curve. Section 8.9 for guidelines on choosing k for a given curve.
5.1. Efficiency considerations in extension fields 5.1. Efficiency Considerations in Extension Fields
The hash_to_field function described in this section is inefficient The hash_to_field function described in this section is inefficient
for certain extension fields. Specifically, when hashing to an for certain extension fields. Specifically, when hashing to an
element of the extension field GF(p^m), hash_to_field requires element of the extension field GF(p^m), hash_to_field requires
expanding msg into m * L bytes (for L as defined above). For expanding msg into m * L bytes (for L as defined above). For
extension fields where log2(p) is significantly smaller than the extension fields where log2(p) is significantly smaller than the
security level k, this approach is inefficient: it requires security level k, this approach is inefficient: it requires
expand_message to output roughly m * log2(p) + m * k bits, whereas m expand_message to output roughly m * log2(p) + m * k bits, whereas m
* log2(p) + k bytes suffices to generate an element of GF(p^m) with * log2(p) + k bytes suffices to generate an element of GF(p^m) with
bias at most 2^-k. In such cases, applications MAY use an bias at most 2^-k. In such cases, applications MAY use an
alternative hash_to_field function, provided it meets the following alternative hash_to_field function, provided it meets the following
security requirements: security requirements:
* The function MUST output field element(s) that are uniformly * The function MUST output one or more field elements that are
random except with bias at most 2^-k. uniformly random except with bias at most 2^-k.
* The function MUST NOT use rejection sampling. * The function MUST NOT use rejection sampling.
* The function SHOULD be amenable to straight line implementations. * The function SHOULD be amenable to straight-line implementations.
For example, Pornin [P20] describes a method for hashing to For example, Pornin [P20] describes a method for hashing to
GF(9767^19) that meets these requirements while using fewer output GF(9767^19) that meets these requirements while using fewer output
bits from expand_message than hash_to_field would for that field. bits from expand_message than hash_to_field would for that field.
5.2. hash_to_field implementation 5.2. hash_to_field Implementation
The following procedure implements hash_to_field. The following procedure implements hash_to_field.
The expand_message parameter to this function MUST conform to the The expand_message parameter to this function MUST conform to the
requirements given in Section 5.3. Section 3.1 discusses the requirements given in Section 5.3. Section 3.1 discusses the
REQUIRED method for constructing DST, the domain separation tag. REQUIRED method for constructing DST, the domain separation tag.
Note that hash_to_field may fail (abort) if expand_message fails. Note that hash_to_field may fail (ABORT) if expand_message fails.
hash_to_field(msg, count) hash_to_field(msg, count)
Parameters: Parameters:
- DST, a domain separation tag (see Section 3.1). - DST, a domain separation tag (see Section 3.1).
- F, a finite field of characteristic p and order q = p^m. - F, a finite field of characteristic p and order q = p^m.
- p, the characteristic of F (see immediately above). - p, the characteristic of F (see immediately above).
- m, the extension degree of F, m >= 1 (see immediately above). - m, the extension degree of F, m >= 1 (see immediately above).
- L = ceil((ceil(log2(p)) + k) / 8), where k is the security - L = ceil((ceil(log2(p)) + k) / 8), where k is the security
parameter of the suite (e.g., k = 128). parameter of the suite (e.g., k = 128).
- expand_message, a function that expands a byte string and - expand_message, a function that expands a byte string and
domain separation tag into a uniformly random byte string domain separation tag into a uniformly random byte string
(see Section 5.3). (see Section 5.3).
Inputs: Input:
- msg, a byte string containing the message to hash. - msg, a byte string containing the message to hash.
- count, the number of elements of F to output. - count, the number of elements of F to output.
Outputs: Output:
- (u_0, ..., u_(count - 1)), a list of field elements. - (u_0, ..., u_(count - 1)), a list of field elements.
Steps: Steps:
1. len_in_bytes = count * m * L 1. len_in_bytes = count * m * L
2. uniform_bytes = expand_message(msg, DST, len_in_bytes) 2. uniform_bytes = expand_message(msg, DST, len_in_bytes)
3. for i in (0, ..., count - 1): 3. for i in (0, ..., count - 1):
4. for j in (0, ..., m - 1): 4. for j in (0, ..., m - 1):
5. elm_offset = L * (j + i * m) 5. elm_offset = L * (j + i * m)
6. tv = substr(uniform_bytes, elm_offset, L) 6. tv = substr(uniform_bytes, elm_offset, L)
7. e_j = OS2IP(tv) mod p 7. e_j = OS2IP(tv) mod p
skipping to change at page 20, line 23 skipping to change at line 893
3. len_in_bytes, the number of bytes to be generated. 3. len_in_bytes, the number of bytes to be generated.
This document defines the following two variants of expand_message: This document defines the following two variants of expand_message:
* expand_message_xmd (Section 5.3.1) is appropriate for use with a * expand_message_xmd (Section 5.3.1) is appropriate for use with a
wide range of hash functions, including SHA-2 [FIPS180-4], SHA-3 wide range of hash functions, including SHA-2 [FIPS180-4], SHA-3
[FIPS202], BLAKE2 [RFC7693], and others. [FIPS202], BLAKE2 [RFC7693], and others.
* expand_message_xof (Section 5.3.2) is appropriate for use with * expand_message_xof (Section 5.3.2) is appropriate for use with
extendable-output functions (XOFs) including functions in the extendable-output functions (XOFs), including functions in the
SHAKE [FIPS202] or BLAKE2X [BLAKE2X] families. SHAKE [FIPS202] or BLAKE2X [BLAKE2X] families.
These variants should suffice for the vast majority of use cases, but These variants should suffice for the vast majority of use cases, but
other variants are possible; Section 5.3.4 discusses requirements. other variants are possible; Section 5.3.4 discusses requirements.
5.3.1. expand_message_xmd 5.3.1. expand_message_xmd
The expand_message_xmd function produces a uniformly random byte The expand_message_xmd function produces a uniformly random byte
string using a cryptographic hash function H that outputs b bits. string using a cryptographic hash function H that outputs b bits.
For security, H MUST meet the following requirements: For security, H MUST meet the following requirements:
* The number of bits output by H MUST be b >= 2 * k, for k the * The number of bits output by H MUST be b >= 2 * k, where k is the
target security level in bits, and b MUST be divisible by 8. The target security level in bits, and b MUST be divisible by 8. The
first requirement ensures k-bit collision resistance; the second first requirement ensures k-bit collision resistance; the second
ensures uniformity of expand_message_xmd's output. ensures uniformity of expand_message_xmd's output.
* H MAY be a Merkle-Damgaard hash function like SHA-2. In this * H MAY be a Merkle-Damgaard hash function like SHA-2. In this
case, security holds when the underlying compression function is case, security holds when the underlying compression function is
modeled as a random oracle [CDMP05]. (See Section 10.6 for modeled as a random oracle [CDMP05]. (See Section 10.6 for
discussion.) discussion.)
* H MAY be a sponge-based hash function like SHA-3 or BLAKE2. In * H MAY be a sponge-based hash function like SHA-3 or BLAKE2. In
skipping to change at page 22, line 5 skipping to change at line 972
8. b_1 = H(b_0 || I2OSP(1, 1) || DST_prime) 8. b_1 = H(b_0 || I2OSP(1, 1) || DST_prime)
9. for i in (2, ..., ell): 9. for i in (2, ..., ell):
10. b_i = H(strxor(b_0, b_(i - 1)) || I2OSP(i, 1) || DST_prime) 10. b_i = H(strxor(b_0, b_(i - 1)) || I2OSP(i, 1) || DST_prime)
11. uniform_bytes = b_1 || ... || b_ell 11. uniform_bytes = b_1 || ... || b_ell
12. return substr(uniform_bytes, 0, len_in_bytes) 12. return substr(uniform_bytes, 0, len_in_bytes)
Note that the string Z_pad (step 6) is prefixed to msg before Note that the string Z_pad (step 6) is prefixed to msg before
computing b_0 (step 7). This is necessary for security when H is a computing b_0 (step 7). This is necessary for security when H is a
Merkle-Damgaard hash, e.g., SHA-2 (see Section 10.6). Hashing this Merkle-Damgaard hash, e.g., SHA-2 (see Section 10.6). Hashing this
additional data means that the cost of computing b_0 is higher than additional data means that the cost of computing b_0 is higher than
the cost of simply computing H(msg). In most settings this overhead the cost of simply computing H(msg). In most settings, this overhead
is negligible, because the cost of evaluating H is much less than the is negligible, because the cost of evaluating H is much less than the
other costs involved in hashing to a curve. other costs involved in hashing to a curve.
It is possible, however, to entirely avoid this overhead by taking It is possible, however, to entirely avoid this overhead by taking
advantage of the fact that Z_pad depends only on H, and not on the advantage of the fact that Z_pad depends only on H, and not on the
arguments to expand_message_xmd. To do so, first precompute and save arguments to expand_message_xmd. To do so, first precompute and save
the internal state of H after ingesting Z_pad. Then, when computing the internal state of H after ingesting Z_pad. Then, when computing
b_0, initialize H using the saved state. Further details are b_0, initialize H using the saved state. Further details are
implementation dependent, and beyond the scope of this document. implementation dependent and are beyond the scope of this document.
5.3.2. expand_message_xof 5.3.2. expand_message_xof
The expand_message_xof function produces a uniformly random byte The expand_message_xof function produces a uniformly random byte
string using an extendable-output function (XOF) H. For security, H string using an extendable-output function (XOF) H. For security, H
MUST meet the following criteria: MUST meet the following criteria:
* The collision resistance of H MUST be at least k bits. * The collision resistance of H MUST be at least k bits.
* H MUST be an XOF that has been proved indifferentiable from a * H MUST be an XOF that has been proved indifferentiable from a
random oracle under a reasonable cryptographic assumption. random oracle under a reasonable cryptographic assumption.
The SHAKE [FIPS202] XOF family is a typical and RECOMMENDED choice. The SHAKE XOF family [FIPS202] is a typical and RECOMMENDED choice.
As an example, for 128-bit security, SHAKE128 would be an appropriate As an example, for 128-bit security, SHAKE128 would be an appropriate
choice. choice.
The following procedure implements expand_message_xof. The following procedure implements expand_message_xof.
expand_message_xof(msg, DST, len_in_bytes) expand_message_xof(msg, DST, len_in_bytes)
Parameters: Parameters:
- H(m, d), an extendable-output function that processes - H(m, d), an extendable-output function that processes
input message m and returns d bytes. input message m and returns d bytes.
Input: Input:
- msg, a byte string. - msg, a byte string.
- DST, a byte string of at most 255 bytes. - DST, a byte string of at most 255 bytes.
See below for information on using longer DSTs. See below for information on using longer DSTs.
- len_in_bytes, the length of the requested output in bytes. - len_in_bytes, the length of the requested output in bytes.
Output: Output:
- uniform_bytes, a byte string. - uniform_bytes, a byte string.
Steps: Steps:
1. ABORT if len_in_bytes > 65535 or len(DST) > 255 1. ABORT if len_in_bytes > 65535 or len(DST) > 255
2. DST_prime = DST || I2OSP(len(DST), 1) 2. DST_prime = DST || I2OSP(len(DST), 1)
3. msg_prime = msg || I2OSP(len_in_bytes, 2) || DST_prime 3. msg_prime = msg || I2OSP(len_in_bytes, 2) || DST_prime
4. uniform_bytes = H(msg_prime, len_in_bytes) 4. uniform_bytes = H(msg_prime, len_in_bytes)
5. return uniform_bytes 5. return uniform_bytes
5.3.3. Using DSTs longer than 255 bytes 5.3.3. Using DSTs Longer than 255 Bytes
The expand_message variants defined in this section accept domain The expand_message variants defined in this section accept domain
separation tags of at most 255 bytes. If applications require a separation tags of at most 255 bytes. If applications require a
domain separation tag longer than 255 bytes, e.g., because of domain separation tag longer than 255 bytes, e.g., because of
requirements imposed by an invoking protocol, implementors MUST requirements imposed by an invoking protocol, implementors MUST
compute a short domain separation tag by hashing, as follows: compute a short domain separation tag by hashing, as follows:
* For expand_message_xmd using hash function H, DST is computed as * For expand_message_xmd using hash function H, DST is computed as
DST = H("H2C-OVERSIZE-DST-" || a_very_long_DST) DST = H("H2C-OVERSIZE-DST-" || a_very_long_DST)
* For expand_message_xof using extendable-output function H, DST is * For expand_message_xof using extendable-output function H, DST is
computed as computed as
DST = H("H2C-OVERSIZE-DST-" || a_very_long_DST, ceil(2 * k / 8)) DST = H("H2C-OVERSIZE-DST-" || a_very_long_DST, ceil(2 * k / 8))
Here, a_very_long_DST is the DST whose length is greater than 255 Here, a_very_long_DST is the DST whose length is greater than 255
bytes, "H2C-OVERSIZE-DST-" is a 17-byte ASCII string literal, and k bytes, "H2C-OVERSIZE-DST-" is a 17-byte ASCII string literal, and k
is the target security level in bits. is the target security level in bits.
5.3.4. Defining other expand_message variants 5.3.4. Defining Other expand_message Variants
When defining a new expand_message variant, the most important When defining a new expand_message variant, the most important
consideration is that hash_to_field models expand_message as a random consideration is that hash_to_field models expand_message as a random
oracle. Thus, implementors SHOULD prove indifferentiability from a oracle. Thus, implementors SHOULD prove indifferentiability from a
random oracle under an appropriate assumption about the underlying random oracle under an appropriate assumption about the underlying
cryptographic primitives; see Section 10.5 for more information. cryptographic primitives; see Section 10.5 for more information.
In addition, expand_message variants: In addition, expand_message variants:
* MUST give collision resistance commensurate with the security * MUST give collision resistance commensurate with the security
skipping to change at page 24, line 34 skipping to change at line 1072
* MUST give independent values for distinct (msg, DST, length) * MUST give independent values for distinct (msg, DST, length)
inputs. Meeting this requirement is subtle. As a simplified inputs. Meeting this requirement is subtle. As a simplified
example, hashing msg || DST does not work, because in this case example, hashing msg || DST does not work, because in this case
distinct (msg, DST) pairs whose concatenations are equal will distinct (msg, DST) pairs whose concatenations are equal will
return the same output (e.g., ("AB", "CDEF") and ("ABC", "DEF")). return the same output (e.g., ("AB", "CDEF") and ("ABC", "DEF")).
The variants defined in this document use a suffix-free encoding The variants defined in this document use a suffix-free encoding
of DST to avoid this issue. of DST to avoid this issue.
* MUST use the domain separation tag DST to ensure that invocations * MUST use the domain separation tag DST to ensure that invocations
of cryptographic primitives inside of expand_message are domain of cryptographic primitives inside of expand_message are domain-
separated from invocations outside of expand_message. For separated from invocations outside of expand_message. For
example, if the expand_message variant uses a hash function H, an example, if the expand_message variant uses a hash function H, an
encoding of DST MUST be added either as a prefix or a suffix of encoding of DST MUST be added either as a prefix or a suffix of
the input to each invocation of H. Adding DST as a suffix is the the input to each invocation of H. Adding DST as a suffix is the
RECOMMENDED approach. RECOMMENDED approach.
* SHOULD read msg exactly once, for efficiency when msg is long. * SHOULD read msg exactly once, for efficiency when msg is long.
In addition, each expand_message variant MUST specify a unique In addition, each expand_message variant MUST specify a unique
EXP_TAG that identifies that variant in a Suite ID. See Section 8.10 EXP_TAG that identifies that variant in a Suite ID. See Section 8.10
for more information. for more information.
6. Deterministic mappings 6. Deterministic Mappings
The mappings in this section are suitable for implementing either The mappings in this section are suitable for implementing either
nonuniform or uniform encodings using the constructions in Section 3. nonuniform or uniform encodings using the constructions in Section 3.
Certain mappings restrict the form of the curve or its parameters. Certain mappings restrict the form of the curve or its parameters.
For each mapping presented, this document lists the relevant For each mapping presented, this document lists the relevant
restrictions. restrictions.
Note that mappings in this section are not interchangeable: different Note that mappings in this section are not interchangeable: different
mappings will almost certainly output different points when evaluated mappings will almost certainly output different points when evaluated
on the same input. on the same input.
6.1. Choosing a mapping function 6.1. Choosing a Mapping Function
This section gives brief guidelines on choosing a mapping function This section gives brief guidelines on choosing a mapping function
for a given elliptic curve. Note that the suites given in Section 8 for a given elliptic curve. Note that the suites given in Section 8
are recommended mappings for the respective curves. are recommended mappings for the respective curves.
If the target elliptic curve is a Montgomery curve (Section 6.7), the If the target elliptic curve is a Montgomery curve (Section 6.7), the
Elligator 2 method (Section 6.7.1) is recommended. Similarly, if the Elligator 2 method (Section 6.7.1) is recommended. Similarly, if the
target elliptic curve is a twisted Edwards curve (Section 6.8), the target elliptic curve is a twisted Edwards curve (Section 6.8), the
twisted Edwards Elligator 2 method (Section 6.8.2) is recommended. twisted Edwards Elligator 2 method (Section 6.8.2) is recommended.
The remaining cases are Weierstrass curves. For curves supported by The remaining cases are Weierstrass curves. For curves supported by
the Simplified SWU method (Section 6.6.2), that mapping is the the Simplified Shallue-van de Woestijne-Ulas (SWU) method
recommended one. Otherwise, the Simplified SWU method for AB == 0 (Section 6.6.2), that mapping is the recommended one. Otherwise, the
(Section 6.6.3) is recommended if the goal is best performance, while Simplified SWU method for AB == 0 (Section 6.6.3) is recommended if
the Shallue-van de Woestijne method (Section 6.6.1) is recommended if the goal is best performance, while the Shallue-van de Woestijne
the goal is simplicity of implementation. (The reason for this method (Section 6.6.1) is recommended if the goal is simplicity of
distinction is that the Simplified SWU method for AB == 0 requires implementation. (The reason for this distinction is that the
implementing an isogeny map in addition to the mapping function, Simplified SWU method for AB == 0 requires implementing an isogeny
while the Shallue-van de Woestijne method does not.) map in addition to the mapping function, while the Shallue-van de
Woestijne method does not.)
The Shallue-van de Woestijne method (Section 6.6.1) works with any The Shallue-van de Woestijne method (Section 6.6.1) works with any
curve, and may be used in cases where a generic mapping is required. curve and may be used in cases where a generic mapping is required.
Note, however, that this mapping is almost always more Note, however, that this mapping is almost always more
computationally expensive than the curve-specific recommendations computationally expensive than the curve-specific recommendations
above. above.
6.2. Interface 6.2. Interface
The generic interface shared by all mappings in this section is as The generic interface shared by all mappings in this section is as
follows: follows:
(x, y) = map_to_curve(u) (x, y) = map_to_curve(u)
skipping to change at page 26, line 28 skipping to change at line 1155
produced by the hash_to_field function. produced by the hash_to_field function.
* (x, y), (s, t), (v, w): the affine coordinates of the point output * (x, y), (s, t), (v, w): the affine coordinates of the point output
by the mapping. Indexed variables (e.g., x1, y2, ...) are used by the mapping. Indexed variables (e.g., x1, y2, ...) are used
for candidate values. for candidate values.
* tv1, tv2, ...: reusable temporary variables. * tv1, tv2, ...: reusable temporary variables.
* c1, c2, ...: constant values, which can be computed in advance. * c1, c2, ...: constant values, which can be computed in advance.
6.4. Sign of the resulting point 6.4. Sign of the Resulting Point
In general, elliptic curves have equations of the form y^2 = g(x). In general, elliptic curves have equations of the form y^2 = g(x).
The mappings in this section first identify an x such that g(x) is The mappings in this section first identify an x such that g(x) is
square, then take a square root to find y. Since there are two square, then take a square root to find y. Since there are two
square roots when g(x) != 0, this may result in an ambiguity square roots when g(x) != 0, this may result in an ambiguity
regarding the sign of y. regarding the sign of y.
When necessary, the mappings in this section resolve this ambiguity When necessary, the mappings in this section resolve this ambiguity
by specifying the sign of the y-coordinate in terms of the input to by specifying the sign of the y-coordinate in terms of the input to
the mapping function. Two main reasons support this approach: first, the mapping function. Two main reasons support this approach: first,
this covers elliptic curves over any field in a uniform way, and this covers elliptic curves over any field in a uniform way, and
second, it gives implementors leeway in optimizing square-root second, it gives implementors leeway in optimizing square-root
implementations. implementations.
6.5. Exceptional cases 6.5. Exceptional Cases
Mappings may have exceptional cases, i.e., inputs u on which the Mappings may have exceptional cases, i.e., inputs u on which the
mapping is undefined. These cases must be handled carefully, mapping is undefined. These cases must be handled carefully,
especially for constant-time implementations. especially for constant-time implementations.
For each mapping in this section, we discuss the exceptional cases For each mapping in this section, we discuss the exceptional cases
and show how to handle them in constant time. Note that all and show how to handle them in constant time. Note that all
implementations SHOULD use inv0 (Section 4) to compute multiplicative implementations SHOULD use inv0 (Section 4) to compute multiplicative
inverses, to avoid exceptional cases that result from attempting to inverses, to avoid exceptional cases that result from attempting to
compute the inverse of 0. compute the inverse of 0.
6.6. Mappings for Weierstrass curves 6.6. Mappings for Weierstrass Curves
The mappings in this section apply to a target curve E defined by the The mappings in this section apply to a target curve E defined by the
equation equation
y^2 = g(x) = x^3 + A * x + B y^2 = g(x) = x^3 + A * x + B
where 4 * A^3 + 27 * B^2 != 0. where 4 * A^3 + 27 * B^2 != 0.
6.6.1. Shallue-van de Woestijne method 6.6.1. Shallue-van de Woestijne Method
Shallue and van de Woestijne [SW06] describe a mapping that applies Shallue and van de Woestijne [SW06] describe a mapping that applies
to essentially any elliptic curve. (Note, however, that this mapping to essentially any elliptic curve. (Note, however, that this mapping
is more expensive to evaluate than the other mappings in this is more expensive to evaluate than the other mappings in this
document.) document.)
The parameterization given below is for Weierstrass curves; its The parameterization given below is for Weierstrass curves; its
derivation is detailed in [W19]. This parameterization also works derivation is detailed in [W19]. This parameterization also works
for Montgomery (Section 6.7) and twisted Edwards (Section 6.8) curves for Montgomery curves (Section 6.7) and twisted Edwards curves
via the rational maps given in Appendix D: first evaluate the (Section 6.8) via the rational maps given in Appendix D: first,
Shallue-van de Woestijne mapping to an equivalent Weierstrass curve, evaluate the Shallue-van de Woestijne mapping to an equivalent
then map that point to the target Montgomery or twisted Edwards curve Weierstrass curve, then map that point to the target Montgomery or
using the corresponding rational map. twisted Edwards curve using the corresponding rational map.
Preconditions: A Weierstrass curve y^2 = x^3 + A * x + B. Preconditions: A Weierstrass curve y^2 = x^3 + A * x + B.
Constants: Constants:
* A and B, the parameter of the Weierstrass curve. * A and B, the parameter of the Weierstrass curve.
* Z, a non-zero element of F meeting the below criteria. * Z, a non-zero element of F meeting the below criteria.
Appendix H.1 gives a Sage [SAGE] script that outputs the Appendix H.1 gives a Sage script [SAGE] that outputs the
RECOMMENDED Z. RECOMMENDED Z.
1. g(Z) != 0 in F. 1. g(Z) != 0 in F.
2. -(3 * Z^2 + 4 * A) / (4 * g(Z)) != 0 in F. 2. -(3 * Z^2 + 4 * A) / (4 * g(Z)) != 0 in F.
3. -(3 * Z^2 + 4 * A) / (4 * g(Z)) is square in F. 3. -(3 * Z^2 + 4 * A) / (4 * g(Z)) is square in F.
4. At least one of g(Z) and g(-Z / 2) is square in F. 4. At least one of g(Z) and g(-Z / 2) is square in F.
skipping to change at page 28, line 35 skipping to change at line 1254
11. x3 = Z + tv6 * (tv2^2 * tv3)^2 11. x3 = Z + tv6 * (tv2^2 * tv3)^2
12. If is_square(g(x1)), set x = x1 and y = sqrt(g(x1)) 12. If is_square(g(x1)), set x = x1 and y = sqrt(g(x1))
13. Else If is_square(g(x2)), set x = x2 and y = sqrt(g(x2)) 13. Else If is_square(g(x2)), set x = x2 and y = sqrt(g(x2))
14. Else set x = x3 and y = sqrt(g(x3)) 14. Else set x = x3 and y = sqrt(g(x3))
15. If sgn0(u) != sgn0(y), set y = -y 15. If sgn0(u) != sgn0(y), set y = -y
16. return (x, y) 16. return (x, y)
Appendix F.1 gives an example straight-line implementation of this Appendix F.1 gives an example straight-line implementation of this
mapping. mapping.
6.6.2. Simplified Shallue-van de Woestijne-Ulas method 6.6.2. Simplified Shallue-van de Woestijne-Ulas Method
The function map_to_curve_simple_swu(u) implements a simplification The function map_to_curve_simple_swu(u) implements a simplification
of the Shallue-van de Woestijne-Ulas mapping [U07] described by Brier of the Shallue-van de Woestijne-Ulas mapping [U07] described by Brier
et al. [BCIMRT10], which they call the "simplified SWU" map. Wahby et al. [BCIMRT10], which they call the "simplified SWU" map. Wahby
and Boneh [WB19] generalize and optimize this mapping. and Boneh [WB19] generalize and optimize this mapping.
Preconditions: A Weierstrass curve y^2 = x^3 + A * x + B where A != 0 Preconditions: A Weierstrass curve y^2 = x^3 + A * x + B where A != 0
and B != 0. and B != 0.
Constants: Constants:
* A and B, the parameters of the Weierstrass curve. * A and B, the parameters of the Weierstrass curve.
* Z, an element of F meeting the below criteria. Appendix H.2 gives * Z, an element of F meeting the below criteria. Appendix H.2 gives
a Sage [SAGE] script that outputs the RECOMMENDED Z. The criteria a Sage script [SAGE] that outputs the RECOMMENDED Z. The criteria
are: are as follows:
1. Z is non-square in F, 1. Z is non-square in F,
2. Z != -1 in F, 2. Z != -1 in F,
3. the polynomial g(x) - Z is irreducible over F, and 3. the polynomial g(x) - Z is irreducible over F, and
4. g(B / (Z * A)) is square in F. 4. g(B / (Z * A)) is square in F.
Sign of y: Inputs u and -u give the same x-coordinate. Thus, we set Sign of y: Inputs u and -u give the same x-coordinate. Thus, we set
sgn0(y) == sgn0(u). sgn0(y) == sgn0(u).
Exceptions: The exceptional cases are values of u such that Z^2 * u^4 Exceptions: The exceptional cases are values of u such that Z^2 * u^4
+ Z * u^2 == 0. This includes u == 0, and may include other values + Z * u^2 == 0. This includes u == 0 and may include other values
depending on Z. Implementations must detect this case and set x1 = B that depend on Z. Implementations must detect this case and set x1 =
/ (Z * A), which guarantees that g(x1) is square by the condition on B / (Z * A), which guarantees that g(x1) is square by the condition
Z given above. on Z given above.
Operations: Operations:
1. tv1 = inv0(Z^2 * u^4 + Z * u^2) 1. tv1 = inv0(Z^2 * u^4 + Z * u^2)
2. x1 = (-B / A) * (1 + tv1) 2. x1 = (-B / A) * (1 + tv1)
3. If tv1 == 0, set x1 = B / (Z * A) 3. If tv1 == 0, set x1 = B / (Z * A)
4. gx1 = x1^3 + A * x1 + B 4. gx1 = x1^3 + A * x1 + B
5. x2 = Z * u^2 * x1 5. x2 = Z * u^2 * x1
6. gx2 = x2^3 + A * x2 + B 6. gx2 = x2^3 + A * x2 + B
7. If is_square(gx1), set x = x1 and y = sqrt(gx1) 7. If is_square(gx1), set x = x1 and y = sqrt(gx1)
8. Else set x = x2 and y = sqrt(gx2) 8. Else set x = x2 and y = sqrt(gx2)
9. If sgn0(u) != sgn0(y), set y = -y 9. If sgn0(u) != sgn0(y), set y = -y
10. return (x, y) 10. return (x, y)
Appendix F.2 gives a general and optimized straight-line Appendix F.2 gives a general and optimized straight-line
implementation of this mapping. For more information on optimizing implementation of this mapping. For more information on optimizing
this mapping, see [WB19] Section 4 or the example code found at this mapping, see Section 4 of [WB19] or the example code found at
[hash2curve-repo]. [hash2curve-repo].
6.6.3. Simplified SWU for AB == 0 6.6.3. Simplified SWU for AB == 0
Wahby and Boneh [WB19] show how to adapt the simplified SWU mapping Wahby and Boneh [WB19] show how to adapt the Simplified SWU mapping
to Weierstrass curves having A == 0 or B == 0, which the mapping of to Weierstrass curves having A == 0 or B == 0, which the mapping of
Section 6.6.2 does not support. (The case A == B == 0 is excluded Section 6.6.2 does not support. (The case A == B == 0 is excluded
because y^2 = x^3 is not an elliptic curve.) because y^2 = x^3 is not an elliptic curve.)
This method applies to curves like secp256k1 [SEC2] and to pairing- This method applies to curves like secp256k1 [SEC2] and to pairing-
friendly curves in the Barreto-Lynn-Scott [BLS03], Barreto-Naehrig friendly curves in the Barreto-Lynn-Scott family [BLS03], Barreto-
[BN05], and other families. Naehrig family [BN05], and other families.
This method requires finding another elliptic curve E' given by the This method requires finding another elliptic curve E' given by the
equation equation
y'^2 = g'(x') = x'^3 + A' * x' + B' y'^2 = g'(x') = x'^3 + A' * x' + B'
that is isogenous to E and has A' != 0 and B' != 0. (See [WB19], that is isogenous to E and has A' != 0 and B' != 0. (See [WB19],
Appendix A, for one way of finding E' using [SAGE].) This isogeny Appendix A, for one way of finding E' using [SAGE].) This isogeny
defines a map iso_map(x', y') given by a pair of rational functions. defines a map iso_map(x', y') given by a pair of rational functions.
iso_map takes as input a point on E' and produces as output a point iso_map takes as input a point on E' and produces as output a point
on E. on E.
Once E' and iso_map are identified, this mapping works as follows: on Once E' and iso_map are identified, this mapping works as follows: on
input u, first apply the simplified SWU mapping to get a point on E', input u, first apply the Simplified SWU mapping to get a point on E',
then apply the isogeny map to that point to get a point on E. then apply the isogeny map to that point to get a point on E.
Note that iso_map is a group homomorphism, meaning that point Note that iso_map is a group homomorphism, meaning that point
addition commutes with iso_map. Thus, when using this mapping in the addition commutes with iso_map. Thus, when using this mapping in the
hash_to_curve construction of Section 3, one can effect a small hash_to_curve construction discussed in Section 3, one can effect a
optimization by first mapping u0 and u1 to E', adding the resulting small optimization by first mapping u0 and u1 to E', adding the
points on E', and then applying iso_map to the sum. This gives the resulting points on E', and then applying iso_map to the sum. This
same result while requiring only one evaluation of iso_map. gives the same result while requiring only one evaluation of iso_map.
Preconditions: An elliptic curve E' with A' != 0 and B' != 0 that is Preconditions: An elliptic curve E' with A' != 0 and B' != 0 that is
isogenous to the target curve E with isogeny map iso_map from E' to isogenous to the target curve E with isogeny map iso_map from E' to
E. E.
Helper functions: Helper functions:
* map_to_curve_simple_swu is the mapping of Section 6.6.2 to E' * map_to_curve_simple_swu is the mapping of Section 6.6.2 to E'
* iso_map is the isogeny map from E' to E * iso_map is the isogeny map from E' to E
Sign of y: for this map, the sign is determined by Sign of y: For this map, the sign is determined by
map_to_curve_simple_swu. No further sign adjustments are necessary. map_to_curve_simple_swu. No further sign adjustments are necessary.
Exceptions: map_to_curve_simple_swu handles its exceptional cases. Exceptions: map_to_curve_simple_swu handles its exceptional cases.
Exceptional cases of iso_map are inputs that cause the denominator of Exceptional cases of iso_map are inputs that cause the denominator of
either rational function to evaluate to zero; such cases MUST return either rational function to evaluate to zero; such cases MUST return
the identity point on E. the identity point on E.
Operations: Operations:
1. (x', y') = map_to_curve_simple_swu(u) # (x', y') is on E' 1. (x', y') = map_to_curve_simple_swu(u) # (x', y') is on E'
2. (x, y) = iso_map(x', y') # (x, y) is on E 2. (x, y) = iso_map(x', y') # (x, y) is on E
3. return (x, y) 3. return (x, y)
See [hash2curve-repo] or [WB19] Section 4.3 for details on See [hash2curve-repo] or Section 4.3 of [WB19] for details on
implementing the isogeny map. implementing the isogeny map.
6.7. Mappings for Montgomery curves 6.7. Mappings for Montgomery Curves
The mapping defined in this section applies to a target curve M The mapping defined in this section applies to a target curve M
defined by the equation defined by the equation
K * t^2 = s^3 + J * s^2 + s K * t^2 = s^3 + J * s^2 + s
6.7.1. Elligator 2 method 6.7.1. Elligator 2 Method
Bernstein, Hamburg, Krasnova, and Lange give a mapping that applies Bernstein, Hamburg, Krasnova, and Lange give a mapping that applies
to any curve with a point of order 2 [BHKL13], which they call to any curve with a point of order 2 [BHKL13], which they call
Elligator 2. Elligator 2.
Preconditions: A Montgomery curve K * t^2 = s^3 + J * s^2 + s where J Preconditions: A Montgomery curve K * t^2 = s^3 + J * s^2 + s where
!= 0, K != 0, and (J^2 - 4) / K^2 is non-zero and non-square in F. J != 0, K != 0, and (J^2 - 4) / K^2 is non-zero and non-square in F.
Constants: Constants:
* J and K, the parameters of the elliptic curve. * J and K, the parameters of the elliptic curve.
* Z, a non-square element of F. Appendix H.3 gives a Sage [SAGE] * Z, a non-square element of F. Appendix H.3 gives a Sage script
script that outputs the RECOMMENDED Z. [SAGE] that outputs the RECOMMENDED Z.
Sign of t: this mapping fixes the sign of t as specified in [BHKL13]. Sign of t: This mapping fixes the sign of t as specified in [BHKL13].
No additional adjustment is required. No additional adjustment is required.
Exceptions: The exceptional case is Z * u^2 == -1, i.e., 1 + Z * u^2 Exceptions: The exceptional case is Z * u^2 == -1, i.e., 1 + Z * u^2
== 0. Implementations must detect this case and set x1 = -(J / K). == 0. Implementations must detect this case and set x1 = -(J / K).
Note that this can only happen when q = 3 (mod 4). Note that this can only happen when q = 3 (mod 4).
Operations: Operations:
1. x1 = -(J / K) * inv0(1 + Z * u^2) 1. x1 = -(J / K) * inv0(1 + Z * u^2)
2. If x1 == 0, set x1 = -(J / K) 2. If x1 == 0, set x1 = -(J / K)
skipping to change at page 32, line 5 skipping to change at line 1414
6. If is_square(gx1), set x = x1, y = sqrt(gx1) with sgn0(y) == 1. 6. If is_square(gx1), set x = x1, y = sqrt(gx1) with sgn0(y) == 1.
7. Else set x = x2, y = sqrt(gx2) with sgn0(y) == 0. 7. Else set x = x2, y = sqrt(gx2) with sgn0(y) == 0.
8. s = x * K 8. s = x * K
9. t = y * K 9. t = y * K
10. return (s, t) 10. return (s, t)
Appendix F.3 gives an example straight-line implementation of this Appendix F.3 gives an example straight-line implementation of this
mapping. Appendix G.2 gives optimized straight-line procedures that mapping. Appendix G.2 gives optimized straight-line procedures that
apply to specific classes of curves and base fields. apply to specific classes of curves and base fields.
6.8. Mappings for twisted Edwards curves 6.8. Mappings for Twisted Edwards Curves
Twisted Edwards curves (a class of curves that includes Edwards Twisted Edwards curves (a class of curves that includes Edwards
curves) are given by the equation curves) are given by the equation
a * v^2 + w^2 = 1 + d * v^2 * w^2 a * v^2 + w^2 = 1 + d * v^2 * w^2
with a != 0, d != 0, and a != d [BBJLP08]. with a != 0, d != 0, and a != d [BBJLP08].
These curves are closely related to Montgomery curves (Section 6.7): These curves are closely related to Montgomery curves (Section 6.7):
every twisted Edwards curve is birationally equivalent to a every twisted Edwards curve is birationally equivalent to a
Montgomery curve ([BBJLP08], Theorem 3.2). This equivalence yields Montgomery curve ([BBJLP08], Theorem 3.2). This equivalence yields
an efficient way of hashing to a twisted Edwards curve: first, hash an efficient way of hashing to a twisted Edwards curve: first, hash
to an equivalent Montgomery curve, then transform the result into a to an equivalent Montgomery curve, then transform the result into a
point on the twisted Edwards curve via a rational map. This method point on the twisted Edwards curve via a rational map. This method
of hashing to a twisted Edwards curve thus requires identifying a of hashing to a twisted Edwards curve thus requires identifying a
corresponding Montgomery curve and rational map. We describe how to corresponding Montgomery curve and rational map. We describe how to
identify such a curve and map immediately below. identify such a curve and map immediately below.
6.8.1. Rational maps from Montgomery to twisted Edwards curves 6.8.1. Rational Maps from Montgomery to Twisted Edwards Curves
There are two ways to select a Montgomery curve and rational map for There are two ways to select a Montgomery curve and rational map for
use when hashing to a given twisted Edwards curve. The selected use when hashing to a given twisted Edwards curve. The selected
Montgomery curve and rational map MUST be specified as part of the Montgomery curve and rational map MUST be specified as part of the
hash-to-curve suite for a given twisted Edwards curve; see Section 8. hash-to-curve suite for a given twisted Edwards curve; see Section 8.
1. When hashing to a standardized twisted Edwards curve for which a 1. When hashing to a standardized twisted Edwards curve for which a
corresponding Montgomery form and rational map are also corresponding Montgomery form and rational map are also
standardized, the standard Montgomery form and rational map standardized, the standard Montgomery form and rational map
SHOULD be used to ensure compatibility with existing software. SHOULD be used to ensure compatibility with existing software.
In certain cases, e.g., edwards25519 [RFC7748], the sign of the In certain cases, e.g., edwards25519 [RFC7748], the sign of the
rational map from the twisted Edwards curve to its corresponding rational map from the twisted Edwards curve to its corresponding
Montgomery curve is not given explicitly. In this case, the sign Montgomery curve is not given explicitly. In this case, the sign
MUST be fixed such that applying the rational map to the twisted MUST be fixed such that applying the rational map to the twisted
Edwards curve's base point yields the Montgomery curve's base Edwards curve's base point yields the Montgomery curve's base
point with correct sign. (For edwards25519, see [RFC7748] and point with correct sign. (For edwards25519, see [RFC7748] and
[EID4730].) [Err4730].)
When defining new twisted Edwards curves, a Montgomery equivalent When defining new twisted Edwards curves, a Montgomery equivalent
and rational map SHOULD also be specified, and the sign of the and rational map SHOULD also be specified, and the sign of the
rational map SHOULD be stated explicitly. rational map SHOULD be stated explicitly.
2. When hashing to a twisted Edwards curve that does not have a 2. When hashing to a twisted Edwards curve that does not have a
standardized Montgomery form or rational map, the map given in standardized Montgomery form or rational map, the map given in
Appendix D SHOULD be used. Appendix D SHOULD be used.
6.8.2. Elligator 2 method 6.8.2. Elligator 2 Method
Preconditions: A twisted Edwards curve E and an equivalent Montgomery Preconditions: A twisted Edwards curve E and an equivalent Montgomery
curve M meeting the requirements in Section 6.8.1. curve M meeting the requirements in Section 6.8.1.
Helper functions: Helper functions:
* map_to_curve_elligator2 is the mapping of Section 6.7.1 to the * map_to_curve_elligator2 is the mapping of Section 6.7.1 to the
curve M. curve M.
* rational_map is a function that takes a point (s, t) on M and * rational_map is a function that takes a point (s, t) on M and
returns a point (v, w) on E, as defined in Section 6.8.1. returns a point (v, w) on E. This rational map should be chosen
as defined in Section 6.8.1.
Sign of t (and v): for this map, the sign is determined by Sign of t (and v): For this map, the sign is determined by
map_to_curve_elligator2. No further sign adjustments are required. map_to_curve_elligator2. No further sign adjustments are required.
Exceptions: The exceptions for the Elligator 2 mapping are as given Exceptions: The exceptions for the Elligator 2 mapping are as given
in Section 6.7.1. The exceptions for the rational map are as given in Section 6.7.1. The exceptions for the rational map are as given
in Section 6.8.1. No other exceptions are possible. in Section 6.8.1. No other exceptions are possible.
The following procedure implements the Elligator 2 mapping for a The following procedure implements the Elligator 2 mapping for a
twisted Edwards curve. (Note that the output point is denoted (v, w) twisted Edwards curve. (Note that the output point is denoted (v, w)
because it is a point on the target twisted Edwards curve.) because it is a point on the target twisted Edwards curve.)
map_to_curve_elligator2_edwards(u) map_to_curve_elligator2_edwards(u)
Input: u, an element of F. Input: u, an element of F.
Output: (v, w), a point on E. Output: (v, w), a point on E.
1. (s, t) = map_to_curve_elligator2(u) # (s, t) is on M 1. (s, t) = map_to_curve_elligator2(u) # (s, t) is on M
2. (v, w) = rational_map(s, t) # (v, w) is on E 2. (v, w) = rational_map(s, t) # (v, w) is on E
3. return (v, w) 3. return (v, w)
7. Clearing the cofactor 7. Clearing the Cofactor
The mappings of Section 6 always output a point on the elliptic The mappings of Section 6 always output a point on the elliptic
curve, i.e., a point in a group of order h * r (Section 2.1). curve, i.e., a point in a group of order h * r (Section 2.1).
Obtaining a point in G may require a final operation commonly called Obtaining a point in G may require a final operation commonly called
"clearing the cofactor," which takes as input any point on the curve "clearing the cofactor," which takes as input any point on the curve
and produces as output a point in the prime-order (sub)group G and produces as output a point in the prime-order (sub)group G
(Section 2.1). (Section 2.1).
The cofactor can always be cleared via scalar multiplication by h. The cofactor can always be cleared via scalar multiplication by h.
For elliptic curves where h = 1, i.e., the curves with a prime number For elliptic curves where h = 1, i.e., the curves with a prime number
of points, no operation is required. This applies, for example, to of points, no operation is required. This applies, for example, to
the NIST curves P-256, P-384, and P-521 [FIPS186-4]. the NIST curves P-256, P-384, and P-521 [FIPS186-4].
In some cases, it is possible to clear the cofactor via a faster In some cases, it is possible to clear the cofactor via a faster
method than scalar multiplication by h. These methods are equivalent method than scalar multiplication by h. These methods are equivalent
to (but usually faster than) multiplication by some scalar h_eff to (but usually faster than) multiplication by some scalar h_eff
whose value is determined by the method and the curve. Examples of whose value is determined by the method and the curve. Examples of
fast cofactor clearing methods include the following: fast cofactor clearing methods include the following:
* For certain pairing-friendly curves having subgroup G2 over an * For certain pairing-friendly curves having subgroup G2 over an
extension field, Scott et al. [SBCDK09] describe a method for extension field, Scott et al. [SBCDK09] describe a method for fast
fast cofactor clearing that exploits an efficiently-computable cofactor clearing that exploits an efficiently computable
endomorphism. Fuentes-Castaneda et al. [FKR11] propose an endomorphism. Fuentes-Castaneda et al. [FKR11] propose an
alternative method that is sometimes more efficient. Budroni and alternative method that is sometimes more efficient. Budroni and
Pintore [BP17] give concrete instantiations of these methods for Pintore [BP17] give concrete instantiations of these methods for
Barreto-Lynn-Scott pairing-friendly curves [BLS03]. This method Barreto-Lynn-Scott pairing-friendly curves [BLS03]. This method
is described for the specific case of BLS12-381 in Appendix G.3. is described for the specific case of BLS12-381 in Appendix G.3.
* Wahby and Boneh ([WB19], Section 5) describe a trick due to Scott * Wahby and Boneh ([WB19], Section 5) describe a trick due to Scott
for fast cofactor clearing on any elliptic curve for which the for fast cofactor clearing on any elliptic curve for which the
prime factorization of h and the structure of the elliptic curve prime factorization of h and the structure of the elliptic curve
group meet certain conditions. group meet certain conditions.
skipping to change at page 34, line 38 skipping to change at line 1542
clear_cofactor(P) := h_eff * P clear_cofactor(P) := h_eff * P
where * represents scalar multiplication. When a curve does not where * represents scalar multiplication. When a curve does not
support a fast cofactor clearing method, h_eff = h and the cofactor support a fast cofactor clearing method, h_eff = h and the cofactor
MUST be cleared via scalar multiplication. MUST be cleared via scalar multiplication.
When a curve admits a fast cofactor clearing method, clear_cofactor When a curve admits a fast cofactor clearing method, clear_cofactor
MAY be evaluated either via that method or via scalar multiplication MAY be evaluated either via that method or via scalar multiplication
by the equivalent h_eff; these two methods give the same result. by the equivalent h_eff; these two methods give the same result.
Note that in this case scalar multiplication by the cofactor h does Note that in this case scalar multiplication by the cofactor h does
not generally give the same result as the fast method, and MUST NOT not generally give the same result as the fast method and MUST NOT be
be used. used.
8. Suites for hashing 8. Suites for Hashing
This section lists recommended suites for hashing to standard This section lists recommended suites for hashing to standard
elliptic curves. elliptic curves.
A hash-to-curve suite fully specifies the procedure for hashing byte A hash-to-curve suite fully specifies the procedure for hashing byte
strings to points on a specific elliptic curve group. Section 8.1 strings to points on a specific elliptic curve group. Section 8.1
describes how to implement a suite. Applications that require describes how to implement a suite. Applications that require
hashing to an elliptic curve should use either an existing suite or a hashing to an elliptic curve should use either an existing suite or a
new suite specified as described in Section 8.9. new suite specified as described in Section 8.9.
All applications using a hash-to-curve suite MUST choose a domain All applications using a hash-to-curve suite MUST choose a domain
separation tag (DST) in accordance with the guidelines in separation tag (DST) in accordance with the guidelines in
Section 3.1. In addition, applications whose security requires a Section 3.1. In addition, applications whose security requires a
random oracle that returns uniformly random points on the target random oracle that returns uniformly random points on the target
curve MUST use a suite whose encoding type is hash_to_curve; see curve MUST use a suite whose encoding type is hash_to_curve; see
Section 3 and immediately below for more information. Section 3 and immediately below for more information.
A hash-to-curve suite comprises the following parameters: A hash-to-curve suite comprises the following parameters:
* Suite ID, a short name used to refer to a given suite. * Suite ID, a short name used to refer to a given suite.
Section 8.10 discusses the naming conventions for suite IDs. Section 8.10 discusses the naming conventions for Suite IDs.
* encoding type, either uniform (hash_to_curve) or nonuniform * encoding type, either uniform (hash_to_curve) or nonuniform
(encode_to_curve). See Section 3 for definitions of these (encode_to_curve). See Section 3 for definitions of these
encoding types. encoding types.
* E, the target elliptic curve over a field F. * E, the target elliptic curve over a field F.
* p, the characteristic of the field F. * p, the characteristic of the field F.
* m, the extension degree of the field F. If m > 1, the suite MUST * m, the extension degree of the field F. If m > 1, the suite MUST
skipping to change at page 36, line 5 skipping to change at line 1597
the underlying hash function). the underlying hash function).
* f, a mapping function from Section 6. * f, a mapping function from Section 6.
* h_eff, the scalar parameter for clear_cofactor (Section 7). * h_eff, the scalar parameter for clear_cofactor (Section 7).
In addition to the above parameters, the mapping f may require In addition to the above parameters, the mapping f may require
additional parameters Z, M, rational_map, E', or iso_map. When additional parameters Z, M, rational_map, E', or iso_map. When
applicable, these MUST be specified. applicable, these MUST be specified.
The below table lists suites RECOMMENDED for some elliptic curves. The table below lists suites RECOMMENDED for some elliptic curves.
The corresponding parameters are given in the following subsections. The corresponding parameters are given in the following subsections.
Applications instantiating cryptographic protocols whose security Applications instantiating cryptographic protocols whose security
analysis relies on a random oracle that outputs points with a uniform analysis relies on a random oracle that outputs points with a uniform
distribution MUST NOT use a nonuniform encoding. Moreover, distribution MUST NOT use a nonuniform encoding. Moreover,
applications that use a nonuniform encoding SHOULD carefully analyze applications that use a nonuniform encoding SHOULD carefully analyze
the security implications of nonuniformity. When the required the security implications of nonuniformity. When the required
encoding is not clear, applications SHOULD use a uniform encoding for encoding is not clear, applications SHOULD use a uniform encoding for
security. security.
+==============+===================================+=========+ +==============+===================================+=========+
| E | Suites | Section | | E | Suites | Section |
+==============+===================================+=========+ +==============+===================================+=========+
| NIST P-256 | P256_XMD:SHA-256_SSWU_RO_ | Section | | NIST P-256 | P256_XMD:SHA-256_SSWU_RO_ | 8.2 |
| | P256_XMD:SHA-256_SSWU_NU_ | 8.2 | | | P256_XMD:SHA-256_SSWU_NU_ | |
+--------------+-----------------------------------+---------+ +--------------+-----------------------------------+---------+
| NIST P-384 | P384_XMD:SHA-384_SSWU_RO_ | Section | | NIST P-384 | P384_XMD:SHA-384_SSWU_RO_ | 8.3 |
| | P384_XMD:SHA-384_SSWU_NU_ | 8.3 | | | P384_XMD:SHA-384_SSWU_NU_ | |
+--------------+-----------------------------------+---------+ +--------------+-----------------------------------+---------+
| NIST P-521 | P521_XMD:SHA-512_SSWU_RO_ | Section | | NIST P-521 | P521_XMD:SHA-512_SSWU_RO_ | 8.4 |
| | P521_XMD:SHA-512_SSWU_NU_ | 8.4 | | | P521_XMD:SHA-512_SSWU_NU_ | |
+--------------+-----------------------------------+---------+ +--------------+-----------------------------------+---------+
| curve25519 | curve25519_XMD:SHA-512_ELL2_RO_ | Section | | curve25519 | curve25519_XMD:SHA-512_ELL2_RO_ | 8.5 |
| | curve25519_XMD:SHA-512_ELL2_NU_ | 8.5 | | | curve25519_XMD:SHA-512_ELL2_NU_ | |
+--------------+-----------------------------------+---------+ +--------------+-----------------------------------+---------+
| edwards25519 | edwards25519_XMD:SHA-512_ELL2_RO_ | Section | | edwards25519 | edwards25519_XMD:SHA-512_ELL2_RO_ | 8.5 |
| | edwards25519_XMD:SHA-512_ELL2_NU_ | 8.5 | | | edwards25519_XMD:SHA-512_ELL2_NU_ | |
+--------------+-----------------------------------+---------+ +--------------+-----------------------------------+---------+
| curve448 | curve448_XOF:SHAKE256_ELL2_RO_ | Section | | curve448 | curve448_XOF:SHAKE256_ELL2_RO_ | 8.6 |
| | curve448_XOF:SHAKE256_ELL2_NU_ | 8.6 | | | curve448_XOF:SHAKE256_ELL2_NU_ | |
+--------------+-----------------------------------+---------+ +--------------+-----------------------------------+---------+
| edwards448 | edwards448_XOF:SHAKE256_ELL2_RO_ | Section | | edwards448 | edwards448_XOF:SHAKE256_ELL2_RO_ | 8.6 |
| | edwards448_XOF:SHAKE256_ELL2_NU_ | 8.6 | | | edwards448_XOF:SHAKE256_ELL2_NU_ | |
+--------------+-----------------------------------+---------+ +--------------+-----------------------------------+---------+
| secp256k1 | secp256k1_XMD:SHA-256_SSWU_RO_ | Section | | secp256k1 | secp256k1_XMD:SHA-256_SSWU_RO_ | 8.7 |
| | secp256k1_XMD:SHA-256_SSWU_NU_ | 8.7 | | | secp256k1_XMD:SHA-256_SSWU_NU_ | |
+--------------+-----------------------------------+---------+ +--------------+-----------------------------------+---------+
| BLS12-381 G1 | BLS12381G1_XMD:SHA-256_SSWU_RO_ | Section | | BLS12-381 G1 | BLS12381G1_XMD:SHA-256_SSWU_RO_ | 8.8 |
| | BLS12381G1_XMD:SHA-256_SSWU_NU_ | 8.8 | | | BLS12381G1_XMD:SHA-256_SSWU_NU_ | |
+--------------+-----------------------------------+---------+ +--------------+-----------------------------------+---------+
| BLS12-381 G2 | BLS12381G2_XMD:SHA-256_SSWU_RO_ | Section | | BLS12-381 G2 | BLS12381G2_XMD:SHA-256_SSWU_RO_ | 8.8 |
| | BLS12381G2_XMD:SHA-256_SSWU_NU_ | 8.8 | | | BLS12381G2_XMD:SHA-256_SSWU_NU_ | |
+--------------+-----------------------------------+---------+ +--------------+-----------------------------------+---------+
Table 2: Suites for hashing to elliptic curves. Table 2: Suites for hashing to elliptic curves.
8.1. Implementing a hash-to-curve suite 8.1. Implementing a Hash-to-Curve Suite
A hash-to-curve suite requires the following functions. Note that A hash-to-curve suite requires the following functions. Note that
some of these require utility functions from Section 4. some of these require utility functions from Section 4.
1. Base field arithmetic operations for the target elliptic curve, 1. Base field arithmetic operations for the target elliptic curve,
e.g., addition, multiplication, and square root. e.g., addition, multiplication, and square root.
2. Elliptic curve point operations for the target curve, e.g., point 2. Elliptic curve point operations for the target curve, e.g., point
addition and scalar multiplication. addition and scalar multiplication.
skipping to change at page 40, line 9 skipping to change at line 1793
P521_XMD:SHA-512_SSWU_NU_ is identical to P521_XMD:SHA-512_SSWU_RO_, P521_XMD:SHA-512_SSWU_NU_ is identical to P521_XMD:SHA-512_SSWU_RO_,
except that the encoding type is encode_to_curve (Section 3). except that the encoding type is encode_to_curve (Section 3).
An optimized example implementation of the Simplified SWU mapping to An optimized example implementation of the Simplified SWU mapping to
P-521 is given in Appendix F.2. P-521 is given in Appendix F.2.
8.5. Suites for curve25519 and edwards25519 8.5. Suites for curve25519 and edwards25519
This section defines ciphersuites for curve25519 and edwards25519 This section defines ciphersuites for curve25519 and edwards25519
[RFC7748]. Note that these ciphersuites MUST NOT be used when [RFC7748]. Note that these ciphersuites MUST NOT be used when
hashing to ristretto255 [I-D.irtf-cfrg-ristretto255-decaf448]. See hashing to ristretto255 [ristretto255-decaf448]. See Appendix B for
Appendix B for information on how to hash to that group. information on how to hash to that group.
curve25519_XMD:SHA-512_ELL2_RO_ is defined as follows: curve25519_XMD:SHA-512_ELL2_RO_ is defined as follows:
* encoding type: hash_to_curve (Section 3) * encoding type: hash_to_curve (Section 3)
* E: K * t^2 = s^3 + J * s^2 + s, where * E: K * t^2 = s^3 + J * s^2 + s, where
- J = 486662 - J = 486662
- K = 1 - K = 1
skipping to change at page 40, line 52 skipping to change at line 1836
* E: a * v^2 + w^2 = 1 + d * v^2 * w^2, where * E: a * v^2 + w^2 = 1 + d * v^2 * w^2, where
- a = -1 - a = -1
- d = 0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca1 - d = 0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca1
35978a3 35978a3
* f: Twisted Edwards Elligator 2 method (Section 6.8.2) * f: Twisted Edwards Elligator 2 method (Section 6.8.2)
* M: curve25519 defined in [RFC7748], Section 4.1 * M: curve25519, defined in [RFC7748], Section 4.1
* rational_map: the birational map defined in [RFC7748], Section 4.1
* rational_map: the birational maps defined in [RFC7748],
Section 4.1
curve25519_XMD:SHA-512_ELL2_NU_ is identical to curve25519_XMD:SHA- curve25519_XMD:SHA-512_ELL2_NU_ is identical to curve25519_XMD:SHA-
512_ELL2_RO_, except that the encoding type is encode_to_curve 512_ELL2_RO_, except that the encoding type is encode_to_curve
(Section 3). (Section 3).
edwards25519_XMD:SHA-512_ELL2_NU_ is identical to edwards25519_XMD:SHA-512_ELL2_NU_ is identical to
edwards25519_XMD:SHA-512_ELL2_RO_, except that the encoding type is edwards25519_XMD:SHA-512_ELL2_RO_, except that the encoding type is
encode_to_curve (Section 3). encode_to_curve (Section 3).
Optimized example implementations of the above mappings are given in Optimized example implementations of the above mappings are given in
Appendix G.2.1 and Appendix G.2.2. Appendix G.2.1 and Appendix G.2.2.
8.6. Suites for curve448 and edwards448 8.6. Suites for curve448 and edwards448
This section defines ciphersuites for curve448 and edwards448 This section defines ciphersuites for curve448 and edwards448
[RFC7748]. Note that these ciphersuites MUST NOT be used when [RFC7748]. Note that these ciphersuites MUST NOT be used when
hashing to decaf448 [I-D.irtf-cfrg-ristretto255-decaf448]. See hashing to decaf448 [ristretto255-decaf448]. See Appendix C for
Appendix C for information on how to hash to that group. information on how to hash to that group.
curve448_XOF:SHAKE256_ELL2_RO_ is defined as follows: curve448_XOF:SHAKE256_ELL2_RO_ is defined as follows:
* encoding type: hash_to_curve (Section 3) * encoding type: hash_to_curve (Section 3)
* E: K * t^2 = s^3 + J * s^2 + s, where * E: K * t^2 = s^3 + J * s^2 + s, where
- J = 156326 - J = 156326
- K = 1 - K = 1
skipping to change at page 43, line 29 skipping to change at line 1961
secp256k1_XMD:SHA-256_SSWU_NU_ is identical to secp256k1_XMD:SHA- secp256k1_XMD:SHA-256_SSWU_NU_ is identical to secp256k1_XMD:SHA-
256_SSWU_RO_, except that the encoding type is encode_to_curve 256_SSWU_RO_, except that the encoding type is encode_to_curve
(Section 3). (Section 3).
An optimized example implementation of the Simplified SWU mapping to An optimized example implementation of the Simplified SWU mapping to
the curve E' isogenous to secp256k1 is given in Appendix F.2. the curve E' isogenous to secp256k1 is given in Appendix F.2.
8.8. Suites for BLS12-381 8.8. Suites for BLS12-381
This section defines ciphersuites for groups G1 and G2 of the This section defines ciphersuites for groups G1 and G2 of the
BLS12-381 elliptic curve [BLS12-381]. The curve parameters in this BLS12-381 elliptic curve [BLS12-381].
section match the ones listed in
[I-D.irtf-cfrg-pairing-friendly-curves], Appendix C.
8.8.1. BLS12-381 G1 8.8.1. BLS12-381 G1
BLS12381G1_XMD:SHA-256_SSWU_RO_ is defined as follows: BLS12381G1_XMD:SHA-256_SSWU_RO_ is defined as follows:
* encoding type: hash_to_curve (Section 3) * encoding type: hash_to_curve (Section 3)
* E: y^2 = x^3 + 4 * E: y^2 = x^3 + 4
* p: 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f * p: 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f
skipping to change at page 44, line 28 skipping to change at line 2006
* iso_map: the 11-isogeny map from E' to E given in Appendix E.2 * iso_map: the 11-isogeny map from E' to E given in Appendix E.2
* h_eff: 0xd201000000010001 * h_eff: 0xd201000000010001
BLS12381G1_XMD:SHA-256_SSWU_NU_ is identical to BLS12381G1_XMD:SHA- BLS12381G1_XMD:SHA-256_SSWU_NU_ is identical to BLS12381G1_XMD:SHA-
256_SSWU_RO_, except that the encoding type is encode_to_curve 256_SSWU_RO_, except that the encoding type is encode_to_curve
(Section 3). (Section 3).
Note that the h_eff values for these suites are chosen for Note that the h_eff values for these suites are chosen for
compatibility with the fast cofactor clearing method described by compatibility with the fast cofactor clearing method described by
Scott ([WB19] Section 5). Scott ([WB19], Section 5).
An optimized example implementation of the Simplified SWU mapping to An optimized example implementation of the Simplified SWU mapping to
the curve E' isogenous to BLS12-381 G1 is given in Appendix F.2. the curve E' isogenous to BLS12-381 G1 is given in Appendix F.2.
8.8.2. BLS12-381 G2 8.8.2. BLS12-381 G2
BLS12381G2_XMD:SHA-256_SSWU_RO_ is defined as follows: BLS12381G2_XMD:SHA-256_SSWU_RO_ is defined as follows:
* encoding type: hash_to_curve (Section 3) * encoding type: hash_to_curve (Section 3)
skipping to change at page 45, line 32 skipping to change at line 2058
* h_eff: 0xbc69f08f2ee75b3584c6a0ea91b352888e2a8e9145ad7689986ff0315 * h_eff: 0xbc69f08f2ee75b3584c6a0ea91b352888e2a8e9145ad7689986ff0315
08ffe1329c2f178731db956d82bf015d1212b02ec0ec69d7477c1ae954cbc06689 08ffe1329c2f178731db956d82bf015d1212b02ec0ec69d7477c1ae954cbc06689
f6a359894c0adebbf6b4e8020005aaa95551 f6a359894c0adebbf6b4e8020005aaa95551
BLS12381G2_XMD:SHA-256_SSWU_NU_ is identical to BLS12381G2_XMD:SHA- BLS12381G2_XMD:SHA-256_SSWU_NU_ is identical to BLS12381G2_XMD:SHA-
256_SSWU_RO_, except that the encoding type is encode_to_curve 256_SSWU_RO_, except that the encoding type is encode_to_curve
(Section 3). (Section 3).
Note that the h_eff values for these suites are chosen for Note that the h_eff values for these suites are chosen for
compatibility with the fast cofactor clearing method described by compatibility with the fast cofactor clearing method described by
Budroni and Pintore ([BP17], Section 4.1), and summarized in Budroni and Pintore ([BP17], Section 4.1) and are summarized in
Appendix G.3. Appendix G.3.
An optimized example implementation of the Simplified SWU mapping to An optimized example implementation of the Simplified SWU mapping to
the curve E' isogenous to BLS12-381 G2 is given in Appendix F.2. the curve E' isogenous to BLS12-381 G2 is given in Appendix F.2.
8.9. Defining a new hash-to-curve suite 8.9. Defining a New Hash-to-Curve Suite
For elliptic curves not listed elsewhere in Section 8, a new hash-to- For elliptic curves not listed elsewhere in Section 8, a new hash-to-
curve suite can be defined by: curve suite can be defined by the following:
1. E, F, p, and m are determined by the elliptic curve and its base 1. E, F, p, and m are determined by the elliptic curve and its base
field. field.
2. k is an upper bound on the target security level of the suite 2. k is an upper bound on the target security level of the suite
(Section 10.8). A reasonable choice of k is ceil(log2(r) / 2), (Section 10.8). A reasonable choice of k is ceil(log2(r) / 2),
where r is the order of the subgroup G of the curve E where r is the order of the subgroup G of the curve E
(Section 2.1). (Section 2.1).
3. Choose encoding type, either hash_to_curve or encode_to_curve 3. Choose encoding type, either hash_to_curve or encode_to_curve
skipping to change at page 46, line 22 skipping to change at line 2094
6. Choose a mapping following the guidelines in Section 6.1, and 6. Choose a mapping following the guidelines in Section 6.1, and
select any required parameters for that mapping. select any required parameters for that mapping.
7. Choose h_eff to be either the cofactor of E or, if a fast 7. Choose h_eff to be either the cofactor of E or, if a fast
cofactor clearing method is to be used, a value appropriate to cofactor clearing method is to be used, a value appropriate to
that method as discussed in Section 7. that method as discussed in Section 7.
8. Construct a Suite ID following the guidelines in Section 8.10. 8. Construct a Suite ID following the guidelines in Section 8.10.
8.10. Suite ID naming conventions 8.10. Suite ID Naming Conventions
Suite IDs MUST be constructed as follows: Suite IDs MUST be constructed as follows:
CURVE_ID || "_" || HASH_ID || "_" || MAP_ID || "_" || ENC_VAR || "_" CURVE_ID || "_" || HASH_ID || "_" || MAP_ID || "_" || ENC_VAR || "_"
The fields CURVE_ID, HASH_ID, MAP_ID, and ENC_VAR are ASCII-encoded The fields CURVE_ID, HASH_ID, MAP_ID, and ENC_VAR are ASCII-encoded
strings of at most 64 characters each. Fields MUST contain only strings of at most 64 characters each. Fields MUST contain only
ASCII characters between 0x21 and 0x7E (inclusive) except that ASCII characters between 0x21 and 0x7E (inclusive), except that
underscore (i.e., 0x5f) is not allowed. underscore (i.e., 0x5F) is not allowed.
As indicated above, each field (including the last) is followed by an As indicated above, each field (including the last) is followed by an
underscore ("_", ASCII 0x5f). This helps to ensure that Suite IDs underscore ("_", ASCII 0x5F). This helps to ensure that Suite IDs
are prefix free. Suite IDs MUST include the final underscore and are prefix free. Suite IDs MUST include the final underscore and
MUST NOT include any characters after the final underscore. MUST NOT include any characters after the final underscore.
Suite ID fields MUST be chosen as follows: Suite ID fields MUST be chosen as follows:
* CURVE_ID: a human-readable representation of the target elliptic * CURVE_ID: a human-readable representation of the target elliptic
curve. curve.
* HASH_ID: a human-readable representation of the expand_message * HASH_ID: a human-readable representation of the expand_message
function and any underlying hash primitives used in hash_to_field function and any underlying hash primitives used in hash_to_field
skipping to change at page 47, line 24 skipping to change at line 2144
is "XMD:SHA3-256". is "XMD:SHA3-256".
Suites that use an alternative hash_to_field function that meets Suites that use an alternative hash_to_field function that meets
the requirements in Section 5.1 MUST indicate this by appending a the requirements in Section 5.1 MUST indicate this by appending a
tag identifying that function to the HASH_ID field, separated by a tag identifying that function to the HASH_ID field, separated by a
colon (":", ASCII 0x3A). colon (":", ASCII 0x3A).
* MAP_ID: a human-readable representation of the map_to_curve * MAP_ID: a human-readable representation of the map_to_curve
function as defined in Section 6. These are defined as follows: function as defined in Section 6. These are defined as follows:
- "SVDW" for or Shallue and van de Woestijne (Section 6.6.1). - "SVDW" for Shallue and van de Woestijne (Section 6.6.1).
- "SSWU" for Simplified SWU (Section 6.6.2, Section 6.6.3). - "SSWU" for Simplified SWU (Sections 6.6.2 and 6.6.3).
- "ELL2" for Elligator 2 (Section 6.7.1, Section 6.8.2). - "ELL2" for Elligator 2 (Sections 6.7.1 and 6.8.2).
* ENC_VAR: a string indicating the encoding type and other * ENC_VAR: a string indicating the encoding type and other
information. The first two characters of this string indicate information. The first two characters of this string indicate
whether the suite represents a hash_to_curve or an encode_to_curve whether the suite represents a hash_to_curve or an encode_to_curve
operation (Section 3), as follows: operation (Section 3), as follows:
- If ENC_VAR begins with "RO", the suite uses hash_to_curve. - If ENC_VAR begins with "RO", the suite uses hash_to_curve.
- If ENC_VAR begins with "NU", the suite uses encode_to_curve. - If ENC_VAR begins with "NU", the suite uses encode_to_curve.
- ENC_VAR MUST NOT begin with any other string. - ENC_VAR MUST NOT begin with any other string.
ENC_VAR MAY also be used to encode other information used to ENC_VAR MAY also be used to encode other information used to
identify variants, for example, a version number. The RECOMMENDED identify variants, for example, a version number. The RECOMMENDED
way to do so is to add one or more subfields separated by colons. way to do so is to add one or more subfields separated by colons.
For example, "RO:V02" is an appropriate ENC_VAR value for the For example, "RO:V02" is an appropriate ENC_VAR value for the
second version of a uniform encoding suite, while second version of a uniform encoding suite, while
"RO:V02:FOO01:BAR17" might be used to indicate a variant of that "RO:V02:FOO01:BAR17" might be used to indicate a variant of that
suite. suite.
9. IANA considerations 9. IANA Considerations
This document has no IANA actions. This document has no IANA actions.
10. Security considerations 10. Security Considerations
This section contains additional security considerations about the This section contains additional security considerations about the
hash-to-curve mechanisms described in this document. hash-to-curve mechanisms described in this document.
10.1. Properties of encodings 10.1. Properties of Encodings
Each encoding type (Section 3) accepts an arbitrary byte string and Each encoding type (Section 3) accepts an arbitrary byte string and
maps it to a point on the curve sampled from a distribution that maps it to a point on the curve sampled from a distribution that
depends on the encoding type. It is important to note that using a depends on the encoding type. It is important to note that using a
nonuniform encoding or directly evaluating one of the mappings of nonuniform encoding or directly evaluating one of the mappings of
Section 6 produces an output that is easily distinguished from a Section 6 produces an output that is easily distinguished from a
uniformly random point. Applications that use a nonuniform encoding uniformly random point. Applications that use a nonuniform encoding
SHOULD carefully analyze the security implications of nonuniformity. SHOULD carefully analyze the security implications of nonuniformity.
When the required encoding is not clear, applications SHOULD use a When the required encoding is not clear, applications SHOULD use a
uniform encoding. uniform encoding.
skipping to change at page 48, line 36 skipping to change at line 2204
is computationally infeasible to find an input to either encoding is computationally infeasible to find an input to either encoding
function whose corresponding output is the identity element. (Both function whose corresponding output is the identity element. (Both
of these properties hold when the encoding functions are instantiated of these properties hold when the encoding functions are instantiated
with a hash_to_field function that follows all guidelines in with a hash_to_field function that follows all guidelines in
Section 5.) Protocols that use these encoding functions SHOULD NOT Section 5.) Protocols that use these encoding functions SHOULD NOT
add a special case to detect and "fix" the identity element. add a special case to detect and "fix" the identity element.
When the hash_to_curve function (Section 3) is instantiated with a When the hash_to_curve function (Section 3) is instantiated with a
hash_to_field function that is indifferentiable from a random oracle hash_to_field function that is indifferentiable from a random oracle
(Section 5), the resulting function is indifferentiable from a random (Section 5), the resulting function is indifferentiable from a random
oracle ([MRH04], [BCIMRT10], [FFSTV13], [LBB19], [H20]). In many oracle ([MRH04] [BCIMRT10] [FFSTV13] [LBB19] [H20]). In many cases,
cases such a function can be safely used in cryptographic protocols such a function can be safely used in cryptographic protocols whose
whose security analysis assumes a random oracle that outputs security analysis assumes a random oracle that outputs uniformly
uniformly random points on an elliptic curve. As Ristenpart et al. random points on an elliptic curve. As Ristenpart et al. discuss in
discuss in [RSS11], however, not all security proofs that rely on [RSS11], however, not all security proofs that rely on random oracles
random oracles continue to hold when those oracles are replaced by continue to hold when those oracles are replaced by indifferentiable
indifferentiable functionalities. This limitation should be functionalities. This limitation should be considered when analyzing
considered when analyzing the security of protocols relying on the the security of protocols relying on the hash_to_curve function.
hash_to_curve function.
10.2. Hashing passwords 10.2. Hashing Passwords
When hashing passwords using any function described in this document, When hashing passwords using any function described in this document,
an adversary who learns the output of the hash function (or an adversary who learns the output of the hash function (or
potentially any intermediate value, e.g., the output of potentially any intermediate value, e.g., the output of
hash_to_field) may be able to carry out a dictionary attack. To hash_to_field) may be able to carry out a dictionary attack. To
mitigate such attacks, it is recommended to first execute a more mitigate such attacks, it is recommended to first execute a more
costly key derivation function (e.g., PBKDF2 [RFC2898], scrypt costly key derivation function (e.g., PBKDF2 [RFC8018], scrypt
[RFC7914], or Argon2 [I-D.irtf-cfrg-argon2]) on the password, then [RFC7914], or Argon2 [RFC9106]) on the password, then hash the output
hash the output of that function to the target elliptic curve. For of that function to the target elliptic curve. For collision
collision resistance, the hash underlying the key derivation function resistance, the hash underlying the key derivation function should be
should be chosen according to the guidelines listed in Section 5.3.1. chosen according to the guidelines listed in Section 5.3.1.
10.3. Constant-time requirements 10.3. Constant-Time Requirements
Constant-time implementations of all functions in this document are Constant-time implementations of all functions in this document are
STRONGLY RECOMMENDED for all uses, to avoid leaking information via STRONGLY RECOMMENDED for all uses, to avoid leaking information via
side channels. It is especially important to use a constant-time side channels. It is especially important to use a constant-time
implementation when inputs to an encoding are secret values; in such implementation when inputs to an encoding are secret values; in such
cases, constant-time implementations are REQUIRED for security cases, constant-time implementations are REQUIRED for security
against timing attacks (e.g., [VR20]). When constant-time against timing attacks (e.g., [VR20]). When constant-time
implementations are required, all basic operations and utility implementations are required, all basic operations and utility
functions must be implemented in constant time, as discussed in functions must be implemented in constant time, as discussed in
Section 4. In some applications (e.g., embedded systems), leakage Section 4. In some applications (e.g., embedded systems), leakage
through other side channels (e.g., power or electromagnetic side through other side channels (e.g., power or electromagnetic side
channels) may be pertinent. Defending against such leakage is channels) may be pertinent. Defending against such leakage is
outside the scope of this document, because the nature of the leakage outside the scope of this document, because the nature of the leakage
and the appropriate defense depend on the application. and the appropriate defense depend on the application.
10.4. encode_to_curve: output distribution and indifferentiability 10.4. encode_to_curve: Output Distribution and Indifferentiability
The encode_to_curve function (Section 3) returns points sampled from The encode_to_curve function (Section 3) returns points sampled from
a distribution that is statistically far from uniform. This a distribution that is statistically far from uniform. This
distribution is bounded roughly as follows: first, it includes at distribution is bounded roughly as follows: first, it includes at
least one eighth of the points in G, and second, the probability of least one eighth of the points in G, and second, the probability of
points in the distribution varies by at most a factor of four. These points in the distribution varies by at most a factor of four. These
bounds hold when encode_to_curve is instantiated with any of the bounds hold when encode_to_curve is instantiated with any of the
map_to_curve functions in Section 6. map_to_curve functions in Section 6.
The bounds above are derived from several works in the literature. The bounds above are derived from several works in the literature.
Specifically: Specifically:
* Shallue and van de Woestijne [SW06] and Fouque and Tibouchi [FT12] * Shallue and van de Woestijne [SW06] and Fouque and Tibouchi [FT12]
derive bounds on the Shallue-van de Woestijne mapping derive bounds on the Shallue-van de Woestijne mapping
(Section 6.6.1). (Section 6.6.1).
* Fouque and Tibouchi [FT10] and Tibouchi [T14] derive bounds for * Fouque and Tibouchi [FT10] and Tibouchi [T14] derive bounds for
the Simplified SWU mapping (Section 6.6.2, Section 6.6.3). the Simplified SWU mapping (Sections 6.6.2 and 6.6.3).
* Bernstein et al. [BHKL13] derive bounds for the Elligator 2 * Bernstein et al. [BHKL13] derive bounds for the Elligator 2
mapping (Section 6.7.1, Section 6.8.2). mapping (Sections 6.7.1 and 6.8.2).
Indifferentiability of encode_to_curve follows from an argument Indifferentiability of encode_to_curve follows from an argument
similar to the one given by Brier et al. [BCIMRT10]; we briefly similar to the one given by Brier et al. [BCIMRT10]; we briefly
sketch. Consider an ideal random oracle Hc() that samples from the sketch this argument as follows. Consider an ideal random oracle
distribution induced by the map_to_curve function called by Hc() that samples from the distribution induced by the map_to_curve
encode_to_curve, and assume for simplicity that the target elliptic function called by encode_to_curve, and assume for simplicity that
curve has cofactor 1 (a similar argument applies for non-unity the target elliptic curve has cofactor 1 (a similar argument applies
cofactors). Indifferentiability holds just if it is possible to for non-unity cofactors). Indifferentiability holds just if it is
efficiently simulate the "inner" random oracle in encode_to_curve, possible to efficiently simulate the "inner" random oracle in
namely, hash_to_field. The simulator works as follows: on a fresh encode_to_curve, namely, hash_to_field. The simulator works as
query msg, the simulator queries Hc(msg) and receives a point P in follows: on a fresh query msg, the simulator queries Hc(msg) and
the image of map_to_curve (if msg is the same as a prior query, the receives a point P in the image of map_to_curve (if msg is the same
simulator just returns the value it gave in response to that query). as a prior query, the simulator just returns the value it gave in
The simulator then computes the possible preimages of P under response to that query). The simulator then computes the possible
map_to_curve, i.e., elements u of F such that map_to_curve(u) == P preimages of P under map_to_curve, i.e., elements u of F such that
(Tibouchi [T14] shows that this can be done efficiently for the map_to_curve(u) == P (Tibouchi [T14] shows that this can be done
Shallue-van de Woestijne and Simplified SWU maps, and Bernstein et efficiently for the Shallue-van de Woestijne and Simplified SWU maps,
al. show the same for Elligator 2). The simulator selects one such and Bernstein et al. show the same for Elligator 2). The simulator
preimage at random and returns this value as the simulated output of selects one such preimage at random and returns this value as the
the "inner" random oracle. By hypothesis, Hc() samples from the simulated output of the "inner" random oracle. By hypothesis, Hc()
distribution induced by map_to_curve on a uniformly random input samples from the distribution induced by map_to_curve on a uniformly
element of F, so this value is uniformly random and induces the random input element of F, so this value is uniformly random and
correct point P when passed through map_to_curve. induces the correct point P when passed through map_to_curve.
10.5. hash_to_field security 10.5. hash_to_field Security
The hash_to_field function defined in Section 5 is indifferentiable The hash_to_field function, defined in Section 5, is indifferentiable
from a random oracle [MRH04] when expand_message (Section 5.3) is from a random oracle [MRH04] when expand_message (Section 5.3) is
modeled as a random oracle. By composability of indifferentiability modeled as a random oracle. Since indifferentiability proofs are
proofs, this also holds when expand_message is proved composable, this also holds when expand_message is proved
indifferentiable from a random oracle relative to an underlying indifferentiable from a random oracle relative to an underlying
primitive that is modeled as a random oracle. When following the primitive that is modeled as a random oracle. When following the
guidelines in Section 5.3, both variants of expand_message defined in guidelines in Section 5.3, both variants of expand_message defined in
that section meet this requirement (see also Section 10.6). that section meet this requirement (see also Section 10.6).
We very briefly sketch the indifferentiability argument for We very briefly sketch the indifferentiability argument for
hash_to_field. Notice that each integer mod p that hash_to_field hash_to_field. Notice that each integer mod p that hash_to_field
returns (i.e., each element of the vector representation of F) is a returns (i.e., each element of the vector representation of F) is a
member of an equivalence class of roughly 2^k integers of length member of an equivalence class of roughly 2^k integers of length
log2(p) + k bits, all of which are equal modulo p. For each integer log2(p) + k bits, all of which are equal modulo p. For each integer
mod p that hash_to_field returns, the simulator samples one member of mod p that hash_to_field returns, the simulator samples one member of
this equivalence class at random and outputs the byte string returned this equivalence class at random and outputs the byte string returned
by I2OSP. (Notice that this is essentially the inverse of the by I2OSP. (Notice that this is essentially the inverse of the
hash_to_field procedure.) hash_to_field procedure.)
10.6. expand_message_xmd security 10.6. expand_message_xmd Security
The expand_message_xmd function defined in Section 5.3.1 is The expand_message_xmd function, defined in Section 5.3.1, is
indifferentiable from a random oracle [MRH04] when one of the indifferentiable from a random oracle [MRH04] when one of the
following holds: following holds:
1. H is indifferentiable from a random oracle, 1. H is indifferentiable from a random oracle,
2. H is a sponge-based hash function whose inner function is modeled 2. H is a sponge-based hash function whose inner function is modeled
as a random transformation or random permutation [BDPV08], or as a random transformation or random permutation [BDPV08], or
3. H is a Merkle-Damgaard hash function whose compression function 3. H is a Merkle-Damgaard hash function whose compression function
is modeled as a random oracle [CDMP05]. is modeled as a random oracle [CDMP05].
For cases (1) and (2), the indifferentiability of expand_message_xmd For cases (1) and (2), the indifferentiability of expand_message_xmd
follows directly from the indifferentiability of H. follows directly from the indifferentiability of H.
For case (3), i.e., for H a Merkle-Damgaard hash function, For case (3), i.e., where H is a Merkle-Damgaard hash function,
indifferentiability follows from [CDMP05], Theorem 3.5. In indifferentiability follows from [CDMP05], Theorem 5. In particular,
particular, expand_message_xmd computes b_0 by prefixing the message expand_message_xmd computes b_0 by prefixing the message with one
with one block of 0-bytes plus auxiliary information (length, block of zeros plus auxiliary information (length, counter, and DST).
counter, and DST). Then, each of the output blocks b_i, i >= 1 in Then, each of the output blocks b_i, i >= 1 in expand_message_xmd is
expand_message_xmd is the result of invoking H on a unique, prefix- the result of invoking H on a unique, prefix-free encoding of b_0.
free encoding of b_0. This is true, first, because the length of the This is true, first because the length of the input to all such
input to all such invocations is equal and fixed by the choice of H invocations is equal and fixed by the choice of H and DST, and second
and DST, and second, because each such input has a unique suffix because each such input has a unique suffix (because of the inclusion
(because of the inclusion of the counter byte I2OSP(i, 1)). of the counter byte I2OSP(i, 1)).
The essential difference between the construction of [CDMP05] and The essential difference between the construction discussed in
expand_message_xmd is that the latter hashes a counter appended to [CDMP05] and expand_message_xmd is that the latter hashes a counter
strxor(b_0, b_(i - 1)) (step 10) rather than to b_0. This approach appended to strxor(b_0, b_(i - 1)) ({#hashtofield-expand-xmd}, step
increases the Hamming distance between inputs to different 10) rather than to b_0. This approach increases the Hamming distance
invocations of H, which reduces the likelihood that nonidealities in between inputs to different invocations of H, which reduces the
H affect the distribution of the b_i values. likelihood that nonidealities in H affect the distribution of the b_i
values.
We note that expand_message_xmd can be used to instantiate a general- We note that expand_message_xmd can be used to instantiate a general-
purpose indifferentiable functionality with variable-length output purpose indifferentiable functionality with variable-length output
based on any hash function meeting one of the above criteria. based on any hash function meeting one of the above criteria.
Applications that use expand_message_xmd outside of hash_to_field Applications that use expand_message_xmd outside of hash_to_field
should ensure domain separation by picking a distinct value for DST. should ensure domain separation by picking a distinct value for DST.
10.7. Domain separation for expand_message variants 10.7. Domain Separation for expand_message Variants
As discussed in Section 2.2.5, the purpose of domain separation is to As discussed in Section 2.2.5, the purpose of domain separation is to
ensure that security analyses of cryptographic protocols that query ensure that security analyses of cryptographic protocols that query
multiple independent random oracles remain valid even if all of these multiple independent random oracles remain valid even if all of these
random oracles are instantiated based on one underlying function H. random oracles are instantiated based on one underlying function H.
The expand_message variants in this document (Section 5.3) ensure The expand_message variants in this document (Section 5.3) ensure
domain separation by appending a suffix-free-encoded domain domain separation by appending a suffix-free-encoded domain
separation tag DST_prime to all strings hashed by H, an underlying separation tag DST_prime to all strings hashed by H, an underlying
hash or extendable-output function. (Other expand_message variants hash or extendable-output function. (Other expand_message variants
that follow the guidelines in Section 5.3.4 are expected to behave that follow the guidelines in Section 5.3.4 are expected to behave
similarly, but these should be analyzed on a case-by-case basis.) similarly, but these should be analyzed on a case-by-case basis.)
For security, applications that use the same function H outside of For security, applications that use the same function H outside of
expand_message should enforce domain separation between those uses of expand_message should enforce domain separation between those uses of
H and expand_message, and should separate all of these from uses of H H and expand_message, and they should separate all of these from uses
in other applications. of H in other applications.
This section suggests four methods for enforcing domain separation This section suggests four methods for enforcing domain separation
from expand_message variants, explains how each method achieves from expand_message variants, explains how each method achieves
domain separation, and lists the situations in which each is domain separation, and lists the situations in which each is
appropriate. These methods share a high-level structure: the appropriate. These methods share a high-level structure: the
application designer fixes a tag DST_ext distinct from DST_prime and application designer fixes a tag DST_ext distinct from DST_prime and
augments calls to H with DST_ext. Each method augments calls to H augments calls to H with DST_ext. Each method augments calls to H
differently, and each may impose additional requirements on DST_ext. differently, and each may impose additional requirements on DST_ext.
These methods can be used to instantiate multiple domain separated These methods can be used to instantiate multiple domain-separated
functions (e.g., H1 and H2) by selecting distinct DST_ext values for functions (e.g., H1 and H2) by selecting distinct DST_ext values for
each (e.g., DST_ext1, DST_ext2). each (e.g., DST_ext1, DST_ext2).
1. (Suffix-only domain separation.) This method is useful when 1. (Suffix-only domain separation.) This method is useful when
domain separating invocations of H from expand_message_xmd or domain-separating invocations of H from expand_message_xmd or
expand_message_xof. It is not appropriate for domain separating expand_message_xof. It is not appropriate for domain-separating
expand_message from HMAC-H [RFC2104]; for that purpose, see expand_message from HMAC-H [RFC2104]; for that purpose, see
method 4. method 4.
To instantiate a suffix-only domain separated function Hso, To instantiate a suffix-only domain-separated function Hso,
compute compute
Hso(msg) = H(msg || DST_ext) Hso(msg) = H(msg || DST_ext)
DST_ext should be suffix-free encoded (e.g., by appending one DST_ext should be suffix-free encoded (e.g., by appending one
byte encoding the length of DST_ext) to make it infeasible to byte encoding the length of DST_ext) to make it infeasible to
find distinct (msg, DST_ext) pairs that hash to the same value. find distinct (msg, DST_ext) pairs that hash to the same value.
This method ensures domain separation because all distinct This method ensures domain separation because all distinct
invocations of H have distinct suffixes, since DST_ext is invocations of H have distinct suffixes, since DST_ext is
distinct from DST_prime. distinct from DST_prime.
2. (Prefix-suffix domain separation.) This method can be used in 2. (Prefix-suffix domain separation.) This method can be used in
the same cases as the suffix-only method. the same cases as the suffix-only method.
To instantiate a prefix-suffix domain separated function Hps, To instantiate a prefix-suffix domain-separated function Hps,
compute compute
Hps(msg) = H(DST_ext || msg || I2OSP(0, 1)) Hps(msg) = H(DST_ext || msg || I2OSP(0, 1))
DST_ext should be prefix-free encoded (e.g., by adding a one-byte DST_ext should be prefix-free encoded (e.g., by adding a one-byte
prefix that encodes the length of DST_ext) to make it infeasible prefix that encodes the length of DST_ext) to make it infeasible
to find distinct (msg, DST_ext) pairs that hash to the same to find distinct (msg, DST_ext) pairs that hash to the same
value. value.
This method ensures domain separation because appending the byte This method ensures domain separation because appending the byte
I2OSP(0, 1) ensures that inputs to H inside Hps are distinct from I2OSP(0, 1) ensures that inputs to H inside Hps are distinct from
those inside expand_message. Specifically, the final byte of those inside expand_message. Specifically, the final byte of
DST_prime encodes the length of DST, which is required to be DST_prime encodes the length of DST, which is required to be
nonzero (Section 3.1, requirement 2), and DST_prime is always nonzero (Section 3.1, requirement 2), and DST_prime is always
appended to invocations of H inside expand_message. appended to invocations of H inside expand_message.
3. (Prefix-only domain separation.) This method is only useful for 3. (Prefix-only domain separation.) This method is only useful for
domain separating invocations of H from expand_message_xmd. It domain-separating invocations of H from expand_message_xmd. It
does not give domain separation for expand_message_xof or HMAC-H. does not give domain separation for expand_message_xof or HMAC-H.
To instantiate a prefix-only domain separated function Hpo, To instantiate a prefix-only domain-separated function Hpo,
compute compute
Hpo(msg) = H(DST_ext || msg) Hpo(msg) = H(DST_ext || msg)
In order for this method to give domain separation, DST_ext In order for this method to give domain separation, DST_ext
should be at least b bits long, where b is the number of bits should be at least b bits long, where b is the number of bits
output by the hash function H. In addition, at least one of the output by the hash function H. In addition, at least one of the
first b bits must be nonzero. Finally, DST_ext should be prefix- first b bits must be nonzero. Finally, DST_ext should be prefix-
free encoded (e.g., by adding a one-byte prefix that encodes the free encoded (e.g., by adding a one-byte prefix that encodes the
length of DST_ext) to make it infeasible to find distinct (msg, length of DST_ext) to make it infeasible to find distinct (msg,
skipping to change at page 53, line 47 skipping to change at line 2448
DST_ext contains at least one nonzero bit among its first b bits, DST_ext contains at least one nonzero bit among its first b bits,
it is guaranteed to be distinct from the value Z_pad it is guaranteed to be distinct from the value Z_pad
(Section 5.3.1, step 4), which ensures that all inputs to H are (Section 5.3.1, step 4), which ensures that all inputs to H are
distinct from the input used to generate b_0 in distinct from the input used to generate b_0 in
expand_message_xmd. Second, since DST_ext is at least b bits expand_message_xmd. Second, since DST_ext is at least b bits
long, it is almost certainly distinct from the values b_0 and long, it is almost certainly distinct from the values b_0 and
strxor(b_0, b_(i - 1)), and therefore all inputs to H are strxor(b_0, b_(i - 1)), and therefore all inputs to H are
distinct from the inputs used to generate b_i, i >= 1, with high distinct from the inputs used to generate b_i, i >= 1, with high
probability. probability.
4. (XMD-HMAC domain separation.) This method is useful for domain 4. (XMD-HMAC domain separation.) This method is useful for domain-
separating invocations of H inside HMAC-H (i.e., HMAC [RFC2104] separating invocations of H inside HMAC-H (i.e., HMAC [RFC2104]
instantiated with hash function H) from expand_message_xmd. It instantiated with hash function H) from expand_message_xmd. It
also applies to HKDF-H [RFC5869], as discussed below. also applies to HKDF-H (i.e., HKDF [RFC5869] instantiated with
hash function H), as discussed below.
Specifically, this method applies when HMAC-H is used with a non- Specifically, this method applies when HMAC-H is used with a non-
secret key to instantiate a random oracle based on a hash secret key to instantiate a random oracle based on a hash
function H (note that expand_message_xmd can also be used for function H (note that expand_message_xmd can also be used for
this purpose; see Section 10.6). When using HMAC-H with a high- this purpose; see Section 10.6). When using HMAC-H with a high-
entropy secret key, domain separation is not necessary; see entropy secret key, domain separation is not necessary; see
discussion below. discussion below.
To choose a non-secret HMAC key DST_key that ensures domain To choose a non-secret HMAC key DST_key that ensures domain
separation from expand_message_xmd, compute separation from expand_message_xmd, compute
skipping to change at page 54, line 42 skipping to change at line 2491
fixing a high-entropy secret key, domain separation from fixing a high-entropy secret key, domain separation from
expand_message_xmd is not necessary. This is because, similarly expand_message_xmd is not necessary. This is because, similarly
to the case above, all inputs to H inside HMAC-H using this to the case above, all inputs to H inside HMAC-H using this
secret key almost certainly have distinct prefixes from all secret key almost certainly have distinct prefixes from all
inputs to H inside expand_message_xmd. inputs to H inside expand_message_xmd.
Finally, this method can be used with HKDF-H [RFC5869] by fixing Finally, this method can be used with HKDF-H [RFC5869] by fixing
the salt input to HKDF-Extract to DST_key, computed as above. the salt input to HKDF-Extract to DST_key, computed as above.
This ensures domain separation for HKDF-Extract by the same This ensures domain separation for HKDF-Extract by the same
argument as for HMAC-H using DST_key. Moreover, assuming that argument as for HMAC-H using DST_key. Moreover, assuming that
the IKM input to HKDF-Extract has sufficiently high entropy (say, the input keying material (IKM) supplied to HKDF-Extract has
commensurate with the security parameter), the HKDF-Expand step sufficiently high entropy (say, commensurate with the security
is domain separated by the same argument as for HMAC-H with a parameter), the HKDF-Expand step is domain-separated by the same
high-entropy secret key (since PRK is exactly that). argument as for HMAC-H with a high-entropy secret key (since a
pseudorandom key is exactly that).
10.8. Target security levels 10.8. Target Security Levels
Each ciphersuite specifies a target security level (in bits) for the Each ciphersuite specifies a target security level (in bits) for the
underlying curve. This parameter ensures the corresponding underlying curve. This parameter ensures the corresponding
hash_to_field instantiation is conservative and correct. We stress hash_to_field instantiation is conservative and correct. We stress
that this parameter is only an upper bound on the security level of that this parameter is only an upper bound on the security level of
the curve, and is neither a guarantee nor endorsement of its the curve and is neither a guarantee nor endorsement of its
suitability for a given application. Mathematical and cryptographic suitability for a given application. Mathematical and cryptographic
advancements may reduce the effective security level for any curve. advancements may reduce the effective security level for any curve.
11. Acknowledgements 11. References
The authors would like to thank Adam Langley for his detailed writeup
of Elligator 2 with Curve25519 [L13]; Dan Boneh, Christopher Patton,
Benjamin Lipp, and Leonid Reyzin for educational discussions; and
David Benjamin, Daniel Bourdrez, Frank Denis, Sean Devlin, Justin
Drake, Bjoern Haase, Mike Hamburg, Dan Harkins, Daira Hopwood, Thomas
Icart, Andy Polyakov, Thomas Pornin, Mamy Ratsimbazafy, Michael
Scott, Filippo Valsorda, and Mathy Vanhoef for helpful reviews and
feedback.
12. Contributors
* Sharon Goldberg, Boston University (goldbe@cs.bu.edu)
* Ela Lee, Royal Holloway, University of London
(Ela.Lee.2010@live.rhul.ac.uk)
* Michele Orru (michele.orru@ens.fr)
13. References
13.1. Normative References 11.1. Normative References
[EID4730] Langley, A., "RFC 7748, Errata ID 4730", July 2016, [Err4730] RFC Errata, "Erratum ID 4730", RFC 7748, July 2016,
<https://www.rfc-editor.org/errata/eid4730>. <https://www.rfc-editor.org/errata/eid4730>.
[I-D.irtf-cfrg-pairing-friendly-curves]
Sakemi, Y., Kobayashi, T., Saito, T., and R. S. Wahby,
"Pairing-Friendly Curves", Work in Progress, Internet-
Draft, draft-irtf-cfrg-pairing-friendly-curves-10, 30 July
2021, <https://datatracker.ietf.org/doc/html/draft-irtf-
cfrg-pairing-friendly-curves-10>.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<https://doi.org/10.17487/RFC2119>. <https://www.rfc-editor.org/info/rfc2119>.
[RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves
for Security", RFC 7748, DOI 10.17487/RFC7748, January for Security", RFC 7748, DOI 10.17487/RFC7748, January
2016, <https://doi.org/10.17487/RFC7748>. 2016, <https://www.rfc-editor.org/info/rfc7748>.
[RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch,
"PKCS #1: RSA Cryptography Specifications Version 2.2", "PKCS #1: RSA Cryptography Specifications Version 2.2",
RFC 8017, DOI 10.17487/RFC8017, November 2016, RFC 8017, DOI 10.17487/RFC8017, November 2016,
<https://doi.org/10.17487/RFC8017>. <https://www.rfc-editor.org/info/rfc8017>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://doi.org/10.17487/RFC8174>. May 2017, <https://www.rfc-editor.org/info/rfc8174>.
13.2. Informative References 11.2. Informative References
[AFQTZ14] Aranha, D.F., Fouque, P.A., Qian, C., Tibouchi, M., and [AFQTZ14] Aranha, D. F., Fouque, P.-A., Qian, C., Tibouchi, M., and
J.C. Zapalowicz, "Binary Elligator squared", J. C. Zapalowicz, "Binary Elligator Squared", In Selected
DOI 10.1007/978-3-319-13051-4_2, pages 20-37, In Selected Areas in Cryptography - SAC 2014, pages 20-37,
Areas in Cryptography - SAC 2014, 2014, DOI 10.1007/978-3-319-13051-4_2, November 2014,
<https://doi.org/10.1007/978-3-319-13051-4_2>. <https://doi.org/10.1007/978-3-319-13051-4_2>.
[AR13] Adj, G. and F. Rodriguez-Henriquez, "Square Root [AR13] Adj, G. and F. Rodríguez-Henríquez, "Square Root
Computation over Even Extension Fields", Computation over Even Extension Fields", In IEEE
DOI 10.1109/TC.2013.145, pages 2829-2841, In IEEE Transactions on Computers. vol 63 issue 11, pages
Transactions on Computers. vol 63 issue 11, November 2014, 2829-2841, DOI 10.1109/TC.2013.145, November 2014,
<https://doi.org/10.1109/TC.2013.145>. <https://doi.org/10.1109/TC.2013.145>.
[BBJLP08] Bernstein, D.J., Birkner, P., Joye, M., Lange, T., and C. [BBJLP08] Bernstein, D. J., Birkner, P., Joye, M., Lange, T., and C.
Peters, "Twisted Edwards curves", Peters, "Twisted Edwards Curves", In AFRICACRYPT 2008,
DOI 10.1007/978-3-540-68164-9_26, pages 389-405, pages 389-405, DOI 10.1007/978-3-540-68164-9_26, June
In AFRICACRYPT 2008, 2008, 2008, <https://doi.org/10.1007/978-3-540-68164-9_26>.
<https://doi.org/10.1007/978-3-540-68164-9_26>.
[BCIMRT10] Brier, E., Coron, J-S., Icart, T., Madore, D., Randriam, [BCIMRT10] Brier, E., Coron, J.-S., Icart, T., Madore, D., Randriam,
H., and M. Tibouchi, "Efficient Indifferentiable Hashing H., and M. Tibouchi, "Efficient Indifferentiable Hashing
into Ordinary Elliptic Curves", into Ordinary Elliptic Curves", In Advances in Cryptology
DOI 10.1007/978-3-642-14623-7_13, pages 237-254, - CRYPTO 2010, pages 237-254,
In Advances in Cryptology - CRYPTO 2010, 2010, DOI 10.1007/978-3-642-14623-7_13, August 2010,
<https://doi.org/10.1007/978-3-642-14623-7_13>. <https://doi.org/10.1007/978-3-642-14623-7_13>.
[BDPV08] Bertoni,, G., Daemen, J., Peeters, M., and G. Van Assche, [BDPV08] Bertoni, G., Daemen, J., Peeters, M., and G. Van Assche,
"On the Indifferentiability of the Sponge Construction", "On the Indifferentiability of the Sponge Construction",
DOI 10.1007/978-3-540-78967-3_11, pages 181-197, In Advances in Cryptology - EUROCRYPT 2008, pages 181-197,
In Advances in Cryptology - EUROCRYPT 2008, 2008, DOI 10.1007/978-3-540-78967-3_11, April 2008,
<https://doi.org/10.1007/978-3-540-78967-3_11>. <https://doi.org/10.1007/978-3-540-78967-3_11>.
[BF01] Boneh, D. and M. Franklin, "Identity-based encryption from [BF01] Boneh, D. and M. Franklin, "Identity-Based Encryption from
the Weil pairing", DOI 10.1007/3-540-44647-8_13, the Weil Pairing", In Advances in Cryptology - CRYPTO
pages 213-229, In Advances in Cryptology - CRYPTO 2001, 2001, pages 213-229, DOI 10.1007/3-540-44647-8_13, August
August 2001, <https://doi.org/10.1007/3-540-44647-8_13>. 2001, <https://doi.org/10.1007/3-540-44647-8_13>.
[BHKL13] Bernstein, D.J., Hamburg, M., Krasnova, A., and T. Lange, [BHKL13] Bernstein, D. J., Hamburg, M., Krasnova, A., and T. Lange,
"Elligator: elliptic-curve points indistinguishable from "Elligator: elliptic-curve points indistinguishable from
uniform random strings", DOI 10.1145/2508859.2516734, uniform random strings", In Proceedings of the 2013 ACM
pages 967-980, In Proceedings of the 2013 ACM SIGSAC SIGSAC Conference on Computer and Communications Security,
Conference on Computer and Communications Security, pages 967-980, DOI 10.1145/2508859.2516734, November 2013,
November 2013, <https://doi.org/10.1145/2508859.2516734>. <https://doi.org/10.1145/2508859.2516734>.
[BLAKE2X] Aumasson, J-P., Neves, S., Wilcox-O'Hearn, Z., and C. [BLAKE2X] Aumasson, J.-P., Neves, S., Wilcox-O'Hearn, Z., and C.
Winnerlein, "BLAKE2X", December 2016, Winnerlein, "BLAKE2X", December 2016,
<https://blake2.net/blake2x.pdf>. <https://blake2.net/blake2x.pdf>.
[BLMP19] Bernstein, D.J., Lange, T., Martindale, C., and L. Panny, [BLMP19] Bernstein, D. J., Lange, T., Martindale, C., and L. Panny,
"Quantum circuits for the CSIDH: optimizing quantum "Quantum Circuits for the CSIDH: Optimizing Quantum
evaluation of isogenies", DOI 10.1007/978-3-030-17656-3, Evaluation of Isogenies", In Advances in Cryptology -
In Advances in Cryptology - EUROCRYPT 2019, 2019, EUROCRYPT 2019, pages 409-441,
<https://doi.org/10.1007/978-3-030-17656-3>. DOI 10.1007/978-3-030-17656-3, May 2019,
<https://doi.org/10.1007/978-3-030-17656-3_15>.
[BLS01] Boneh, D., Lynn, B., and H. Shacham, "Short signatures [BLS-SIG] Boneh, D., Gorbunov, S., Wahby, R. S., Wee, H., Wood, C.
from the Weil pairing", DOI 10.1007/s00145-004-0314-9, A., and Z. Zhang, "BLS Signatures", Work in Progress,
pages 297-319, In Journal of Cryptology, vol 17, July Internet-Draft, draft-irtf-cfrg-bls-signature-05, 16 June
2004, <https://doi.org/10.1007/s00145-004-0314-9>. 2022, <https://datatracker.ietf.org/doc/html/draft-irtf-
cfrg-bls-signature-05>.
[BLS03] Barreto, P., Lynn, B., and M. Scott, "Constructing [BLS01] Boneh, D., Lynn, B., and H. Shacham, "Short Signatures
Elliptic Curves with Prescribed Embedding Degrees", from the Weil Pairing", In Journal of Cryptology, vol 17,
DOI 10.1007/3-540-36413-7_19, pages 257-267, In Security pages 297-319, DOI 10.1007/s00145-004-0314-9, July 2004,
in Communication Networks, 2003, <https://doi.org/10.1007/s00145-004-0314-9>.
[BLS03] Barreto, P. S. L. M., Lynn, B., and M. Scott,
"Constructing Elliptic Curves with Prescribed Embedding
Degrees", In Security in Communication Networks, pages
257-267, DOI 10.1007/3-540-36413-7_19, September 2002,
<https://doi.org/10.1007/3-540-36413-7_19>. <https://doi.org/10.1007/3-540-36413-7_19>.
[BLS12-381] [BLS12-381]
Bowe, S., "BLS12-381: New zk-SNARK Elliptic Curve Bowe, S., "BLS12-381: New zk-SNARK Elliptic Curve
Construction", March 2017, Construction", March 2017,
<https://electriccoin.co/blog/new-snark-curve/>. <https://electriccoin.co/blog/new-snark-curve/>.
[BM92] Bellovin, S.M. and M. Merritt, "Encrypted key exchange: [BM92] Bellovin, S. M. and M. Merritt, "Encrypted key exchange:
Password-based protocols secure against dictionary password-based protocols secure against dictionary
attacks", DOI 10.1109/RISP.1992.213269, pages 72-84, attacks", In IEEE Symposium on Security and Privacy -
In IEEE Symposium on Security and Privacy - Oakland 1992, Oakland 1992, pages 72-84, DOI 10.1109/RISP.1992.213269,
1992, <https://doi.org/10.1109/RISP.1992.213269>. May 1992, <https://doi.org/10.1109/RISP.1992.213269>.
[BMP00] Boyko, V., MacKenzie, P.D., and S. Patel, "Provably secure [BMP00] Boyko, V., MacKenzie, P., and S. Patel, "Provably Secure
password-authenticated key exchange using Diffie-Hellman", Password-Authenticated Key Exchange Using Diffie-Hellman",
DOI 10.1007/3-540-45539-6_12, pages 156-171, In Advances In Advances in Cryptology - EUROCRYPT 2000, pages 156-171,
in Cryptology - EUROCRYPT 2000, May 2000, DOI 10.1007/3-540-45539-6_12, May 2000,
<https://doi.org/10.1007/3-540-45539-6_12>. <https://doi.org/10.1007/3-540-45539-6_12>.
[BN05] Barreto, P. and M. Naehrig, "Pairing-Friendly Elliptic [BN05] Barreto, P. S. L. M. and M. Naehrig, "Pairing-Friendly
Curves of Prime Order", DOI 10.1007/11693383_22, Elliptic Curves of Prime Order", In Selected Areas in
pages 319-331, In Selected Areas in Cryptography 2005, Cryptography 2005, pages 319-331, DOI 10.1007/11693383_22,
2006, <https://doi.org/10.1007/11693383_22>. 2006, <https://doi.org/10.1007/11693383_22>.
[BP17] Budroni, A. and F. Pintore, "Efficient hash maps to G2 on [BP17] Budroni, A. and F. Pintore, "Efficient hash maps to
BLS curves", ePrint 2017/419, May 2017, \mathbb{G}_2 on BLS curves", Cryptology ePrint Archive,
Paper 2017/419, May 2017,
<https://eprint.iacr.org/2017/419>. <https://eprint.iacr.org/2017/419>.
[BR93] Bellare, M. and P. Rogaway, "Random oracles are practical: [BR93] Bellare, M. and P. Rogaway, "Random oracles are practical:
a paradigm for designing efficient protocols", a paradigm for designing efficient protocols", In
DOI 10.1145/168588.168596, pages 62-73, In Proceedings of Proceedings of the 1993 ACM Conference on Computer and
the 1993 ACM Conference on Computer and Communications Communications Security, pages 62-73,
Security, December 1993, DOI 10.1145/168588.168596, December 1993,
<https://doi.org/10.1145/168588.168596>. <https://doi.org/10.1145/168588.168596>.
[C93] Cohen, H., "A Course in Computational Algebraic Number [C93] Cohen, H., "A Course in Computational Algebraic Number
Theory", ISBN 9783642081422, publisher Springer-Verlag, Theory", Springer-Verlag, ISBN 9783642081422,
1993, <https://doi.org/10.1007/978-3-662-02945-9>. DOI 10.1007/978-3-662-02945-9, 1993,
<https://doi.org/10.1007/978-3-662-02945-9>.
[CDMP05] Coron, J-S., Dodis, Y., Malinaud, C., and P. Puniya, [CDMP05] Coron, J.-S., Dodis, Y., Malinaud, C., and P. Puniya,
"Merkle-Damgaard Revisited: How to Construct a Hash "Merkle-Damgård Revisited: How to Construct a Hash
Function", DOI 10.1007/11535218_26, pages 430-448, Function", In Advances in Cryptology -- CRYPTO 2005, pages
In Advances in Cryptology - CRYPTO 2005, 2005, 430-448, DOI 10.1007/11535218_26, August 2005,
<https://doi.org/10.1007/11535218_26>. <https://doi.org/10.1007/11535218_26>.
[CFADLNV05] [CFADLNV05]
Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T.,
Nguyen, K., and F. Vercauteren, "Handbook of Elliptic and Nguyen, K., and F. Vercauteren, "Handbook of Elliptic and
Hyperelliptic Curve Cryptography", ISBN 9781584885184, Hyperelliptic Curve Cryptography", Chapman and Hall / CRC,
publisher Chapman and Hall / CRC, 2005, ISBN 9781584885184, 2005,
<https://www.crcpress.com/9781584885184>. <https://www.crcpress.com/9781584885184>.
[CK11] Couveignes, J. and J. Kammerer, "The geometry of flex [CK11] Couveignes, J.-M. and J.-G. Kammerer, "The geometry of
tangents to a cubic curve and its parameterizations", flex tangents to a cubic curve and its parameterizations",
DOI 10.1016/j.jsc.2011.11.003, pages 266-281, In Journal In Journal of Symbolic Computation, vol 47 issue 3, pages
of Symbolic Computation, vol 47 issue 3, 2012, 266-281, DOI 10.1016/j.jsc.2011.11.003, March 2012,
<https://doi.org/10.1016/j.jsc.2011.11.003>. <https://doi.org/10.1016/j.jsc.2011.11.003>.
[F11] Farashahi, R.R., "Hashing into Hessian curves", [F11] Farashahi, R. R., "Hashing into Hessian Curves", In
DOI 10.1007/978-3-642-21969-6_17, pages 278-289, AFRICACRYPT 2011, pages 278-289,
In AFRICACRYPT 2011, 2011, DOI 10.1007/978-3-642-21969-6_17, July 2011,
<https://doi.org/10.1007/978-3-642-21969-6_17>. <https://doi.org/10.1007/978-3-642-21969-6_17>.
[FFSTV13] Farashahi, R.R., Fouque, P.A., Shparlinski, I.E., [FFSTV13] Farashahi, R. R., Fouque, P.-A., Shparlinski, I. E.,
Tibouchi, M., and J.F. Voloch, "Indifferentiable Tibouchi, M., and J. F. Voloch, "Indifferentiable
deterministic hashing to elliptic and hyperelliptic deterministic hashing to elliptic and hyperelliptic
curves", DOI 10.1090/S0025-5718-2012-02606-8, curves", In Mathematics of Computation. vol 82, pages
pages 491-512, In Math. Comp. vol 82, 2013, 491-512, DOI 10.1090/S0025-5718-2012-02606-8, 2013,
<https://doi.org/10.1090/S0025-5718-2012-02606-8>. <https://doi.org/10.1090/S0025-5718-2012-02606-8>.
[FIPS180-4] [FIPS180-4]
National Institute of Standards and Technology (NIST), National Institute of Standards and Technology (NIST),
"Secure Hash Standard (SHS)", August 2015, "Secure Hash Standard (SHS)", FIPS 180-4,
DOI 10.6028/NIST.FIPS.180-4, August 2015,
<https://nvlpubs.nist.gov/nistpubs/FIPS/ <https://nvlpubs.nist.gov/nistpubs/FIPS/
NIST.FIPS.180-4.pdf>. NIST.FIPS.180-4.pdf>.
[FIPS186-4] [FIPS186-4]
National Institute of Standards and Technology (NIST), National Institute of Standards and Technology (NIST),
"FIPS Publication 186-4: Digital Signature Standard", July "Digital Signature Standard (DSS)", FIPS 186-4,
2013, <https://nvlpubs.nist.gov/nistpubs/FIPS/ DOI 10.6028/NIST.FIPS.186-4, July 2013,
<https://nvlpubs.nist.gov/nistpubs/FIPS/
NIST.FIPS.186-4.pdf>. NIST.FIPS.186-4.pdf>.
[FIPS202] National Institute of Standards and Technology (NIST), [FIPS202] National Institute of Standards and Technology (NIST),
"SHA-3 Standard: Permutation-Based Hash and Extendable- "SHA-3 Standard: Permutation-Based Hash and Extendable-
Output Functions", August 2015, Output Functions", FIPS 202, DOI 10.6028/NIST.FIPS.202,
<https://nvlpubs.nist.gov/nistpubs/FIPS/ August 2015, <https://nvlpubs.nist.gov/nistpubs/FIPS/
NIST.FIPS.202.pdf>. NIST.FIPS.202.pdf>.
[FJT13] Fouque, P-A., Joux, A., and M. Tibouchi, "Injective [FJT13] Fouque, P.-A., Joux, A., and M. Tibouchi, "Injective
encodings to elliptic curves", Encodings to Elliptic Curves", In ACISP 2013, pages
DOI 10.1007/978-3-642-39059-3_14, pages 203-218, In ACISP 203-218, DOI 10.1007/978-3-642-39059-3_14, 2013,
2013, 2013,
<https://doi.org/10.1007/978-3-642-39059-3_14>. <https://doi.org/10.1007/978-3-642-39059-3_14>.
[FKR11] Fuentes-Castaneda, L., Knapp, E., and F. Rodriguez- [FKR11] Fuentes-Castañeda, L., Knapp, E., and F. Rodriguez-
Henriquez, "Fast Hashing to G2 on Pairing-Friendly Henriquez, "Faster Hashing to G2", In Selected Areas in
Curves", DOI 10.1007/978-3-642-28496-0_25, pages 412-430, Cryptography, pages 412-430,
In Selected Areas in Cryptography, 2011, DOI 10.1007/978-3-642-28496-0_25, August 2011,
<https://doi.org/10.1007/978-3-642-28496-0_25>. <https://doi.org/10.1007/978-3-642-28496-0_25>.
[FSV09] Farashahi, R.R., Shparlinski, I.E., and J.F. Voloch, "On [FSV09] Farashahi, R. R., Shparlinski, I. E., and J. F. Voloch,
hashing into elliptic curves", DOI 10.1515/JMC.2009.022, "On hashing into elliptic curves", In Journal of
pages 353-360, In Journal of Mathematical Cryptology, vol Mathematical Cryptology, vol 3 no 4, pages 353-360,
3 no 4, 2009, <https://doi.org/10.1515/JMC.2009.022>. DOI 10.1515/JMC.2009.022, March 2009,
<https://doi.org/10.1515/JMC.2009.022>.
[FT10] Fouque, P-A. and M. Tibouchi, "Estimating the size of the [FT10] Fouque, P.-A. and M. Tibouchi, "Estimating the Size of the
image of deterministic hash functions to elliptic Image of Deterministic Hash Functions to Elliptic Curves",
curves.", DOI 10.1007/978-3-642-14712-8_5, pages 81-91, In Progress in Cryptology - LATINCRYPT 2010, pages 81-91,
In Progress in Cryptology - LATINCRYPT 2010, 2010, DOI 10.1007/978-3-642-14712-8_5, August 2010,
<https://doi.org/10.1007/978-3-642-14712-8_5>. <https://doi.org/10.1007/978-3-642-14712-8_5>.
[FT12] Fouque, P-A. and M. Tibouchi, "Indifferentiable Hashing to [FT12] Fouque, P.-A. and M. Tibouchi, "Indifferentiable Hashing
Barreto-Naehrig Curves", DOI 10.1007/978-3-642-33481-8_1, to Barreto--Naehrig Curves", In Progress in Cryptology -
pages 1-7, In Progress in Cryptology - LATINCRYPT 2012, LATINCRYPT 2012, pages 1-17,
2012, <https://doi.org/10.1007/978-3-642-33481-8_1>. DOI 10.1007/978-3-642-33481-8_1, 2012,
<https://doi.org/10.1007/978-3-642-33481-8_1>.
[H20] Hamburg, M., "Indifferentiable hashing from Elligator 2", [H20] Hamburg, M., "Indifferentiable hashing from Elligator 2",
2020, <https://eprint.iacr.org/2020/1513>. Cryptology ePrint Archive, Paper 2020/1513, 2020,
<https://eprint.iacr.org/2020/1513>.
[hash2curve-repo] [hash2curve-repo]
"Hashing to Elliptic Curves - GitHub repository", 2019, "Hashing to Elliptic Curves", commit 664b135, June 2022,
<https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve>. <https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve>.
[I-D.irtf-cfrg-argon2] [Icart09] Icart, T., "How to Hash into Elliptic Curves", In Advances
Biryukov, A., Dinu, D., Khovratovich, D., and S. in Cryptology - CRYPTO 2009, pages 303-316,
Josefsson, "Argon2 Memory-Hard Function for Password DOI 10.1007/978-3-642-03356-8_18, August 2009,
Hashing and Proof-of-Work Applications", Work in Progress,
Internet-Draft, draft-irtf-cfrg-argon2-13, 11 March 2021,
<https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-
argon2-13>.
[I-D.irtf-cfrg-bls-signature]
Boneh, D., Gorbunov, S., Wahby, R. S., Wee, H., and Z.
Zhang, "BLS Signatures", Work in Progress, Internet-Draft,
draft-irtf-cfrg-bls-signature-04, 10 September 2020,
<https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-
bls-signature-04>.
[I-D.irtf-cfrg-ristretto255-decaf448]
Valence, H. D., Grigg, J., Hamburg, M., Lovecruft, I.,
Tankersley, G., and F. Valsorda, "The ristretto255 and
decaf448 Groups", Work in Progress, Internet-Draft, draft-
irtf-cfrg-ristretto255-decaf448-03, 25 February 2022,
<https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-
ristretto255-decaf448-03>.
[I-D.irtf-cfrg-voprf]
Davidson, A., Faz-Hernandez, A., Sullivan, N., and C. A.
Wood, "Oblivious Pseudorandom Functions (OPRFs) using
Prime-Order Groups", Work in Progress, Internet-Draft,
draft-irtf-cfrg-voprf-09, 8 February 2022,
<https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-
voprf-09>.
[I-D.irtf-cfrg-vrf]
Goldberg, S., Reyzin, L., Papadopoulos, D., and J. Vcelak,
"Verifiable Random Functions (VRFs)", Work in Progress,
Internet-Draft, draft-irtf-cfrg-vrf-12, 26 May 2022,
<https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-
vrf-12>.
[Icart09] Icart, T., "How to Hash into Elliptic Curves",
DOI 10.1007/978-3-642-03356-8_18, pages 303-316,
In Advances in Cryptology - CRYPTO 2009, 2009,
<https://doi.org/10.1007/978-3-642-03356-8_18>. <https://doi.org/10.1007/978-3-642-03356-8_18>.
[J96] Jablon, D.P., "Strong password-only authenticated key [J96] Jablon, D. P., "Strong password-only authenticated key
exchange", DOI 10.1145/242896.242897, pages 5-26, exchange", In SIGCOMM Computer Communication Review, vol
In SIGCOMM Computer Communication Review, vol 26 issue 5, 26 issue 5, pages 5-26, DOI 10.1145/242896.242897, October
1996, <https://doi.org/10.1145/242896.242897>. 1996, <https://doi.org/10.1145/242896.242897>.
[jubjub-fq] [jubjub-fq]
"zkcrypto/jubjub - fq.rs", 2019, "zkcrypto/jubjub - fq.rs", 2019,
<https://github.com/zkcrypto/jubjub/blob/master/src/ <https://github.com/zkcrypto/jubjub/pull/18>.
fq.rs>.
[KLR10] Kammerer, J., Lercier, R., and G. Renault, "Encoding [KLR10] Kammerer, J.-G., Lercier, R., and G. Renault, "Encoding
points on hyperelliptic curves over finite fields in Points on Hyperelliptic Curves over Finite Fields in
deterministic polynomial time", Deterministic Polynomial Time", In Pairing-Based
DOI 10.1007/978-3-642-17455-1_18, pages 278-297, Cryptography - Pairing 2010, pages 278-297,
In PAIRING 2010, 2010, DOI 10.1007/978-3-642-17455-1_18, 2010,
<https://doi.org/10.1007/978-3-642-17455-1_18>. <https://doi.org/10.1007/978-3-642-17455-1_18>.
[L13] Langley, A., "Implementing Elligator for Curve25519", [L13] Langley, A., "Implementing Elligator for Curve25519",
2013, <https://www.imperialviolet.org/2013/12/25/ December 2013, <https://www.imperialviolet.org/2013/12/25/
elligator.html>. elligator.html>.
[LBB19] Lipp, B., Blanchet, B., and K. Bhargavan, "A Mechanised [LBB19] Lipp, B., Blanchet, B., and K. Bhargavan, "A Mechanised
Proof of the WireGuard Virtual Private Network Protocol", Cryptographic Proof of the WireGuard Virtual Private
In INRIA Research Report No. 9269, April 2019, Network Protocol", In INRIA Research Report 9269, April
<https://hal.inria.fr/hal-02100345/>. 2019, <https://hal.inria.fr/hal-02100345/>.
[MOV96] Menezes, A.J., van Oorschot, P.C., and S.A. Vanstone, [MOV96] Menezes, A. J., van Oorschot, P. C., and S. A. Vanstone,
"Handbook of Applied Cryptography", ISBN 9780849385230, "Handbook of Applied Cryptography", CRC Press,
publisher CRC Press, 1996, ISBN 9780849385230, October 1996,
<http://cacr.uwaterloo.ca/hac/>. <http://cacr.uwaterloo.ca/hac/>.
[MRH04] Maurer, U., Renner, R., and C. Holenstein, [MRH04] Maurer, U., Renner, R., and C. Holenstein,
"Indifferentiability, impossibility results on reductions, "Indifferentiability, Impossibility Results on Reductions,
and applications to the random oracle methodology", and Applications to the Random Oracle Methodology", In TCC
DOI 10.1007/978-3-540-24638-1_2, pages 21-39, In TCC 2004: 2004: Theory of Cryptography, pages 21-39,
Theory of Cryptography, February 2004, DOI 10.1007/978-3-540-24638-1_2, February 2004,
<https://doi.org/10.1007/978-3-540-24638-1_2>. <https://doi.org/10.1007/978-3-540-24638-1_2>.
[MRV99] Micali, S., Rabin, M., and S. Vadhan, "Verifiable Random [MRV99] Micali, S., Rabin, M., and S. Vadhan, "Verifiable random
Functions", DOI 10.1109/SFFCS.1999.814584, In Symposium on functions", 40th Annual Symposium on Foundations of
the Foundations of Computer Science, October 1999, Computer Science (Cat. No.99CB37039), pages 120-130,
DOI 10.1109/SFFCS.1999.814584, October 1999,
<https://doi.org/10.1109/SFFCS.1999.814584>. <https://doi.org/10.1109/SFFCS.1999.814584>.
[MT98] Matsumoto, M. and T. Nishimura, "Mersenne twister: A [MT98] Matsumoto, M. and T. Nishimura, "Mersenne twister: A
623-dimensionally equidistributed uniform pseudo-random 623-dimensionally equidistributed uniform pseudo-random
number generator", DOI 10.1145/272991.272995, pages 3-30, number generator", In ACM Transactions on Modeling and
In ACM Transactions on Modeling and Computer Simulation Computer Simulation (TOMACS), vol 8 issue 1, pages 3-30,
(TOMACS), Volume 8, Issue 1, January 1998, DOI 10.1145/272991.272995, January 1998,
<https://doi.org/10.1145/272991.272995>. <https://doi.org/10.1145/272991.272995>.
[NR97] Naor, M. and O. Reingold, "Number-theoretic constructions [NR97] Naor, M. and O. Reingold, "Number-theoretic constructions
of efficient pseudo-random functions", of efficient pseudo-random functions", In Proceedings 38th
DOI 10.1109/SFCS.1997.646134, In Symposium on the Annual Symposium on Foundations of Computer Science, pages
Foundations of Computer Science, October 1997, 458-467, DOI 10.1109/SFCS.1997.646134, October 1997,
<https://doi.org/10.1109/SFCS.1997.646134>. <https://doi.org/10.1109/SFCS.1997.646134>.
[p1363.2] IEEE Computer Society, "IEEE Standard Specification for [OPRFs] Davidson, A., Faz-Hernandez, A., Sullivan, N., and C. A.
Password-Based Public-Key Cryptography Techniques", Wood, "Oblivious Pseudorandom Functions (OPRFs) using
Prime-Order Groups", Work in Progress, Internet-Draft,
draft-irtf-cfrg-voprf-21, 21 February 2023,
<https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-
voprf-21>.
[p1363.2] IEEE, "IEEE Standard Specification for Password-Based
Public-Key Cryptography Techniques", IEEE 1363.2-2008,
September 2008, September 2008,
<https://standards.ieee.org/standard/1363_2-2008.html>. <https://standards.ieee.org/standard/1363_2-2008.html>.
[p1363a] IEEE Computer Society, "IEEE Standard Specifications for [p1363a] IEEE, "IEEE Standard Specifications for Public-Key
Public-Key Cryptography---Amendment 1: Additional Cryptography - Amendment 1: Additional Techniques", IEEE
Techniques", March 2004, 1363a-2004, March 2004,
<https://standards.ieee.org/standard/1363a-2004.html>. <https://standards.ieee.org/standard/1363a-2004.html>.
[P20] Pornin, T., "Efficient Elliptic Curve Operations On [P20] Pornin, T., "Efficient Elliptic Curve Operations On
Microcontrollers With Finite Field Extensions", 2020, Microcontrollers With Finite Field Extensions", Cryptology
ePrint Archive, Paper 2020/009, 2020,
<https://eprint.iacr.org/2020/009>. <https://eprint.iacr.org/2020/009>.
[RCB16] Renes, J., Costello, C., and L. Batina, "Complete addition [RCB16] Renes, J., Costello, C., and L. Batina, "Complete Addition
formulas for prime order elliptic curves", Formulas for Prime Order Elliptic Curves", In Advances in
DOI 10.1007/978-3-662-49890-3_16, pages 403-428, Cryptology - EUROCRYPT 2016, pages 403-428,
In Advances in Cryptology - EUROCRYPT 2016, May 2016, DOI 10.1007/978-3-662-49890-3_16, April 2016,
<https://doi.org/10.1007/978-3-662-49890-3_16>. <https://doi.org/10.1007/978-3-662-49890-3_16>.
[RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed-
Hashing for Message Authentication", RFC 2104, Hashing for Message Authentication", RFC 2104,
DOI 10.17487/RFC2104, February 1997, DOI 10.17487/RFC2104, February 1997,
<https://doi.org/10.17487/RFC2104>. <https://www.rfc-editor.org/info/rfc2104>.
[RFC2898] Kaliski, B., "PKCS #5: Password-Based Cryptography
Specification Version 2.0", RFC 2898,
DOI 10.17487/RFC2898, September 2000,
<https://doi.org/10.17487/RFC2898>.
[RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand
Key Derivation Function (HKDF)", RFC 5869, Key Derivation Function (HKDF)", RFC 5869,
DOI 10.17487/RFC5869, May 2010, DOI 10.17487/RFC5869, May 2010,
<https://doi.org/10.17487/RFC5869>. <https://www.rfc-editor.org/info/rfc5869>.
[RFC7693] Saarinen, M-J., Ed. and J-P. Aumasson, "The BLAKE2 [RFC7693] Saarinen, M., Ed. and J. Aumasson, "The BLAKE2
Cryptographic Hash and Message Authentication Code (MAC)", Cryptographic Hash and Message Authentication Code (MAC)",
RFC 7693, DOI 10.17487/RFC7693, November 2015, RFC 7693, DOI 10.17487/RFC7693, November 2015,
<https://doi.org/10.17487/RFC7693>. <https://www.rfc-editor.org/info/rfc7693>.
[RFC7914] Percival, C. and S. Josefsson, "The scrypt Password-Based [RFC7914] Percival, C. and S. Josefsson, "The scrypt Password-Based
Key Derivation Function", RFC 7914, DOI 10.17487/RFC7914, Key Derivation Function", RFC 7914, DOI 10.17487/RFC7914,
August 2016, <https://doi.org/10.17487/RFC7914>. August 2016, <https://www.rfc-editor.org/info/rfc7914>.
[RFC8018] Moriarty, K., Ed., Kaliski, B., and A. Rusch, "PKCS #5:
Password-Based Cryptography Specification Version 2.1",
RFC 8018, DOI 10.17487/RFC8018, January 2017,
<https://www.rfc-editor.org/info/rfc8018>.
[RFC9106] Biryukov, A., Dinu, D., Khovratovich, D., and S.
Josefsson, "Argon2 Memory-Hard Function for Password
Hashing and Proof-of-Work Applications", RFC 9106,
DOI 10.17487/RFC9106, September 2021,
<https://www.rfc-editor.org/info/rfc9106>.
[ristretto255-decaf448]
de Valence, H., Grigg, J., Hamburg, M., Lovecruft, I.,
Tankersley, G., and F. Valsorda, "The ristretto255 and
decaf448 Groups", Work in Progress, Internet-Draft, draft-
irtf-cfrg-ristretto255-decaf448-07, 3 April 2023,
<https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-
ristretto255-decaf448-07>.
[RSS11] Ristenpart, T., Shacham, H., and T. Shrimpton, "Careful [RSS11] Ristenpart, T., Shacham, H., and T. Shrimpton, "Careful
with Composition: Limitations of the Indifferentiability with Composition: Limitations of the Indifferentiability
Framework", DOI 10.1007/978-3-642-20465-4_27, Framework", In Advances in Cryptology - EUROCRYPT 2011,
pages 487-506, In Advances in Cryptology - EUROCRYPT 2011, pages 487–506, DOI 10.1007/978-3-642-20465-4_27, May 2011,
May 2011, <https://doi.org/10.1007/978-3-642-20465-4_27>. <https://doi.org/10.1007/978-3-642-20465-4_27>.
[S05] Skalba, M., "Points on elliptic curves over finite [S05] Skałba, M., "Points on elliptic curves over finite
fields", DOI 10.4064/aa117-3-7, pages 293-301, In Acta fields", In Acta Arithmetica, vol 117 no 3, pages 293-301,
Arithmetica, vol 117 no 3, 2005, DOI 10.4064/aa117-3-7, 2005,
<https://doi.org/10.4064/aa117-3-7>. <https://doi.org/10.4064/aa117-3-7>.
[S85] Schoof, R., "Elliptic Curves Over Finite Fields and the [S85] Schoof, R., "Elliptic curves over finite fields and the
Computation of Square Roots mod p", computation of square roots mod p", In Mathematics of
DOI 10.1090/S0025-5718-1985-0777280-6, pages 483-494, Computation, vol 44 issue 170, pages 483-494,
In Mathematics of Computation vol 44 issue 170, April DOI 10.1090/S0025-5718-1985-0777280-6, April 1985,
1985, <https://doi.org/10.1090/S0025-5718-1985-0777280-6>. <https://doi.org/10.1090/S0025-5718-1985-0777280-6>.
[SAGE] The Sage Developers, "SageMath, the Sage Mathematics [SAGE] The Sage Developers, "SageMath, the Sage Mathematics
Software System", 2019, <https://www.sagemath.org>. Software System", <https://www.sagemath.org>.
[SBCDK09] Scott, M., Benger, N., Charlemagne, M., Dominguez Perez, [SBCDK09] Scott, M., Benger, N., Charlemagne, M., Dominguez Perez,
L.J., and E.J. Kachisa, "Fast Hashing to G2 on Pairing- L. J., and E. J. Kachisa, "Fast Hashing to G2 on Pairing-
Friendly Curves", DOI 10.1007/978-3-642-03298-1_8, Friendly Curves", In Pairing-Based Cryptography - Pairing
pages 102-113, In Pairing-Based Cryptography - Pairing 2009, pages 102-113, DOI 10.1007/978-3-642-03298-1_8,
2009, 2009, <https://doi.org/10.1007/978-3-642-03298-1_8>. August 2009,
<https://doi.org/10.1007/978-3-642-03298-1_8>.
[SEC1] Standards for Efficient Cryptography Group (SECG), "SEC 1: [SEC1] Standards for Efficient Cryptography Group (SECG), "SEC 1:
Elliptic Curve Cryptography", May 2009, Elliptic Curve Cryptography", May 2009,
<http://www.secg.org/sec1-v2.pdf>. <http://www.secg.org/sec1-v2.pdf>.
[SEC2] Standards for Efficient Cryptography Group (SECG), "SEC 2: [SEC2] Standards for Efficient Cryptography Group (SECG), "SEC 2:
Recommended Elliptic Curve Domain Parameters", January Recommended Elliptic Curve Domain Parameters", January
2010, <http://www.secg.org/sec2-v2.pdf>. 2010, <http://www.secg.org/sec2-v2.pdf>.
[SS04] Schinzel, A. and M. Skalba, "On equations y^2 = x^n + k in [SS04] Schinzel, A. and M. Skałba, "On equations y^2 = x^n + k in
a finite field.", DOI 10.4064/ba52-3-1, pages 223-226, a finite field", In Bulletin Polish Academy of Sciences.
In Bulletin Polish Acad. Sci. Math. vol 52, no 3, 2004, Mathematics, vol 52 no 3, pages 223-226,
DOI 10.4064/ba52-3-1, 2004,
<https://doi.org/10.4064/ba52-3-1>. <https://doi.org/10.4064/ba52-3-1>.
[SW06] Shallue, A. and C. van de Woestijne, "Construction of [SW06] Shallue, A. and C. E. van de Woestijne, "Construction of
rational points on elliptic curves over finite fields", Rational Points on Elliptic Curves over Finite Fields", In
DOI 10.1007/11792086_36, pages 510-524, In Algorithmic Algorithmic Number Theory - ANTS 2006, pages 510-524,
Number Theory. ANTS 2006., 2006, DOI 10.1007/11792086_36, July 2006,
<https://doi.org/10.1007/11792086_36>. <https://doi.org/10.1007/11792086_36>.
[T14] Tibouchi, M., "Elligator squared: Uniform points on [T14] Tibouchi, M., "Elligator Squared: Uniform Points on
elliptic curves of prime order as uniform random strings", Elliptic Curves of Prime Order as Uniform Random Strings",
DOI 10.1007/978-3-662-45472-5_10, pages 139-156,
In Financial Cryptography and Data Security - FC 2014, In Financial Cryptography and Data Security - FC 2014,
pages 139-156, DOI 10.1007/978-3-662-45472-5_10, November
2014, <https://doi.org/10.1007/978-3-662-45472-5_10>. 2014, <https://doi.org/10.1007/978-3-662-45472-5_10>.
[TK17] Tibouchi, M. and T. Kim, "Improved elliptic curve hashing [TK17] Tibouchi, M. and T. Kim, "Improved elliptic curve hashing
and point representation", DOI 10.1007/s10623-016-0288-2, and point representation", In Designs, Codes, and
pages 161-177, In Designs, Codes, and Cryptography, vol Cryptography, vol 82, pages 161-177,
82, 2017, <https://doi.org/10.1007/s10623-016-0288-2>. DOI 10.1007/s10623-016-0288-2, January 2017,
<https://doi.org/10.1007/s10623-016-0288-2>.
[U07] Ulas, M., "Rational points on certain hyperelliptic curves [U07] Ulas, M., "Rational Points on Certain Hyperelliptic Curves
over finite fields", DOI 10.4064/ba55-2-1, pages 97-104, over Finite Fields", In Bulletin Polish Academy of
In Bulletin Polish Acad. Sci. Math. vol 55, no 2, 2007, Science. Mathematics, vol 55 no 2, pages 97-104,
DOI 10.4064/ba55-2-1, July 2007,
<https://doi.org/10.4064/ba55-2-1>. <https://doi.org/10.4064/ba55-2-1>.
[VR20] Vanhoef, M. and E. Ronen, "Dragonblood: Analyzing the [VR20] Vanhoef, M. and E. Ronen, "Dragonblood: Analyzing the
Dragonfly Handshake of WPA3 and EAP-pwd", In IEEE Dragonfly Handshake of WPA3 and EAP-pwd", In IEEE
Symposium on Security & Privacy (SP), 2020, Symposium on Security & Privacy (SP), May 2020,
<https://eprint.iacr.org/2019/383>. <https://eprint.iacr.org/2019/383>.
[W08] Washington, L.C., "Elliptic curves: Number theory and [VRF] Goldberg, S., Reyzin, L., Papadopoulos, D., and J. Včelák,
cryptography", ISBN 9781420071467, publisher Chapman and "Verifiable Random Functions (VRFs)", Work in Progress,
Hall / CRC, edition 2nd, 2008, Internet-Draft, draft-irtf-cfrg-vrf-15, 9 August 2022,
<https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-
vrf-15>.
[W08] Washington, L. C., "Elliptic Curves: Number Theory and
Cryptography, Second Edition", Chapman and Hall / CRC,
ISBN 9781420071467, April 2008,
<https://www.crcpress.com/9781420071467>. <https://www.crcpress.com/9781420071467>.
[W19] Wahby, R.S., "An explicit, generic parameterization for [W19] Wahby, R. S., "An explicit, generic parameterization for
the Shallue--van de Woestijne map", 2019, the Shallue--van de Woestijne map", commit e2a625f, March
<https://github.com/cfrg/draft-irtf-cfrg-hash-to- 2020, <https://github.com/cfrg/draft-irtf-cfrg-hash-to-
curve/raw/master/doc/svdw_params.pdf>. curve/blob/draft-irtf-cfrg-hash-to-curve-14/doc/
svdw_params.pdf>.
[WB19] Wahby, R.S. and D. Boneh, "Fast and simple constant-time [WB19] Wahby, R. S. and D. Boneh, "Fast and simple constant-time
hashing to the BLS12-381 elliptic curve", hashing to the BLS12-381 elliptic curve", In IACR
DOI 10.13154/tches.v2019.i4.154-179, ePrint 2019/403, Transactions on Cryptographic Hardware and Embedded
issue 4, volume 2019, In IACR Trans. CHES, August 2019, Systems, vol 2019 issue 4, Cryptology ePrint Archive,
<https://eprint.iacr.org/2019/403>. Paper 2019/403, DOI 10.13154/tches.v2019.i4.154-179,
August 2019, <https://eprint.iacr.org/2019/403>.
Appendix A. Related work Appendix A. Related Work
The problem of mapping arbitrary bit strings to elliptic curve points The problem of mapping arbitrary bit strings to elliptic curve points
has been the subject of both practical and theoretical research. has been the subject of both practical and theoretical research.
This section briefly describes the background and research results This section briefly describes the background and research results
that underly the recommendations in this document. This section is that underlie the recommendations in this document. This section is
provided for informational purposes only. provided for informational purposes only.
A naive but generally insecure method of mapping a string msg to a A naive but generally insecure method of mapping a string msg to a
point on an elliptic curve E having n points is to first fix a point point on an elliptic curve E having n points is to first fix a point
P that generates the elliptic curve group, and a hash function Hn P that generates the elliptic curve group, and a hash function Hn
from bit strings to integers less than n; then compute Hn(msg) * P, from bit strings to integers less than n; then compute Hn(msg) * P,
where the * operator represents scalar multiplication. The reason where the * operator represents scalar multiplication. The reason
this approach is insecure is that the resulting point has a known this approach is insecure is that the resulting point has a known
discrete log relationship to P. Thus, except in cases where this discrete log relationship to P. Thus, except in cases where this
method is specified by the protocol, it must not be used; doing so method is specified by the protocol, it must not be used; doing so
risks catastrophic security failures. risks catastrophic security failures.
Boneh et al. [BLS01] describe an encoding method they call Boneh et al. [BLS01] describe an encoding method they call
MapToGroup, which works roughly as follows: first, use the input MapToGroup, which works roughly as follows: first, use the input
string to initialize a pseudorandom number generator, then use the string to initialize a pseudorandom number generator, then use the
generator to produce a value x in F. If x is the x-coordinate of a generator to produce a value x in F. If x is the x-coordinate of a
point on the elliptic curve, output that point. Otherwise, generate point on the elliptic curve, output that point. Otherwise, generate
a new value x in F and try again. Since a random value x in F has a new value x in F and try again. Since a random value x in F has
probability about 1/2 of corresponding to a point on the curve, the probability about 1/2 of corresponding to a point on the curve, the
expected number of tries is just two. However, the running time of expected number of tries is just two. However, the running time of
this method, which is generally referred to as a probabilistic try- this method, which is generally referred to as a probabilistic try-
and-increment algorithm, depends on the input string. As such, it is and-increment algorithm, depends on the input string. As such, it is
not safe to use in protocols sensitive to timing side channels, as not safe to use in protocols sensitive to timing side channels, as
skipping to change at page 66, line 16 skipping to change at line 2994
elliptic curve points deterministically, for a restricted class of elliptic curve points deterministically, for a restricted class of
curves and a very small number of points. Skalba [S05] generalizes curves and a very small number of points. Skalba [S05] generalizes
this construction to more curves and more points on those curves. this construction to more curves and more points on those curves.
Shallue and van de Woestijne [SW06] further generalize and simplify Shallue and van de Woestijne [SW06] further generalize and simplify
Skalba's construction, yielding concretely efficient maps to a Skalba's construction, yielding concretely efficient maps to a
constant fraction of the points on almost any curve. Fouque and constant fraction of the points on almost any curve. Fouque and
Tibouchi [FT12] give a parameterization of this mapping for Barreto- Tibouchi [FT12] give a parameterization of this mapping for Barreto-
Naehrig pairing-friendly curves [BN05]. Naehrig pairing-friendly curves [BN05].
Ulas [U07] describes a simpler version of the Shallue-van de Ulas [U07] describes a simpler version of the Shallue-van de
Woestijne map, and Brier et al. [BCIMRT10] give a further Woestijne map, and Brier et al. [BCIMRT10] give a further
simplification, which the authors call the "simplified SWU" map. simplification, which the authors call the "Simplified SWU" map.
That simplified map applies only to fields of characteristic p = 3 That simplified map applies only to fields of characteristic p = 3
(mod 4); Wahby and Boneh [WB19] generalize to fields of any (mod 4); Wahby and Boneh [WB19] generalize to fields of any
characteristic, and give further optimizations. characteristic and give further optimizations.
Boneh and Franklin give a deterministic algorithm mapping to certain Boneh and Franklin give a deterministic algorithm mapping to certain
supersingular curves over fields of characteristic p = 2 (mod 3) supersingular curves over fields of characteristic p = 2 (mod 3)
[BF01]. Icart gives another deterministic algorithm which maps to [BF01]. Icart gives another deterministic algorithm that maps to any
any curve over a field of characteristic p = 2 (mod 3) [Icart09]. curve over a field of characteristic p = 2 (mod 3) [Icart09].
Several extensions and generalizations follow this work, including Several extensions and generalizations follow this work, including
[FSV09], [FT10], [KLR10], [F11], and [CK11]. [FSV09], [FT10], [KLR10], [F11], and [CK11].
Following the work of Farashahi [F11], Fouque et al. [FJT13] Following the work of Farashahi [F11], Fouque et al. [FJT13] describe
describe a mapping to curves over fields of characteristic p = 3 (mod a mapping to curves over fields of characteristic p = 3 (mod 4)
4) having a number of points divisible by 4. Bernstein et al. having a number of points divisible by 4. Bernstein et al. [BHKL13]
[BHKL13] optimize this mapping and describe a related mapping that optimize this mapping and describe a related mapping that they call
they call "Elligator 2," which applies to any curve over a field of "Elligator 2," which applies to any curve over a field of odd
odd characteristic having a point of order 2. This includes characteristic having a point of order 2. This includes Curve25519
Curve25519 and Curve448, both of which are CFRG-recommended curves and Curve448, both of which are CFRG-recommended curves [RFC7748].
[RFC7748]. Bernstein et al. [BLMP19] extend the Elligator 2 map to Bernstein et al. [BLMP19] extend the Elligator 2 map to a class of
a class of supersingular curves over fields of characteristic p = 3 supersingular curves over fields of characteristic p = 3 (mod 4).
(mod 4).
An important caveat regarding all of the above deterministic mapping An important caveat regarding all of the above deterministic mapping
functions is that none of them map to the entire curve, but rather to functions is that none of them map to the entire curve, but rather to
some fraction of the points. This means that they cannot be used some fraction of the points. This means that they cannot be used
directly to construct a random oracle that outputs points on the directly to construct a random oracle that outputs points on the
curve. curve.
Brier et al. [BCIMRT10] give two solutions to this problem. The Brier et al. [BCIMRT10] give two solutions to this problem. The
first, which Brier et al. prove applies to Icart's method, computes first, which Brier et al. prove applies to Icart's method, computes
f(H0(msg)) + f(H1(msg)) for two distinct hash functions H0 and H1 f(H0(msg)) + f(H1(msg)) for two distinct hash functions H0 and H1
from bit strings to F and a mapping f from F to the elliptic curve E. from bit strings to F and a mapping f from F to the elliptic curve E.
The second, which applies to essentially all deterministic mappings The second, which applies to essentially all deterministic mappings
but is more costly, computes f(H0(msg)) + H2(msg) * P, for P a but is more costly, computes f(H0(msg)) + H2(msg) * P, where P is a
generator of the elliptic curve group and H2 a hash from bit strings generator of the elliptic curve group, H2 is a hash from bit strings
to integers modulo r, the order of the elliptic curve group. to integers modulo r, and r is the order of the elliptic curve group.
Farashahi et al. [FFSTV13] improve the analysis of the first method,
Farashahi et al. [FFSTV13] improve the analysis of the first method,
showing that it applies to essentially all deterministic mappings. showing that it applies to essentially all deterministic mappings.
Tibouchi and Kim [TK17] further refine the analysis and describe Tibouchi and Kim [TK17] further refine the analysis and describe
additional optimizations. additional optimizations.
Complementary to the problem of mapping from bit strings to elliptic Complementary to the problem of mapping from bit strings to elliptic
curve points, Bernstein et al. [BHKL13] study the problem of mapping curve points, Bernstein et al. [BHKL13] study the problem of mapping
from elliptic curve points to uniformly random bit strings, giving from elliptic curve points to uniformly random bit strings, giving
solutions for a class of curves including Montgomery and twisted solutions for a class of curves that includes Montgomery and twisted
Edwards curves. Tibouchi [T14] and Aranha et al. [AFQTZ14] Edwards curves. Tibouchi [T14] and Aranha et al. [AFQTZ14]
generalize these results. This document does not deal with this generalize these results. This document does not deal with this
complementary problem. complementary problem.
Appendix B. Hashing to ristretto255 Appendix B. Hashing to ristretto255
ristretto255 [I-D.irtf-cfrg-ristretto255-decaf448] provides a prime- ristretto255 [ristretto255-decaf448] provides a prime-order group
order group based on Curve25519 [RFC7748]. This section describes based on curve25519 [RFC7748]. This section describes
hash_to_ristretto255, which implements a random-oracle encoding to hash_to_ristretto255, which implements a random-oracle encoding to
this group that has a uniform output distribution (Section 2.2.3) and this group that has a uniform output distribution (Section 2.2.3) and
the same security properties and interface as the hash_to_curve the same security properties and interface as the hash_to_curve
function (Section 3). function (Section 3).
The ristretto255 API defines a one-way map The ristretto255 API defines a one-way map ([ristretto255-decaf448],
([I-D.irtf-cfrg-ristretto255-decaf448], Section 4.3.4); this section Section 4.3.4); this section refers to that map as ristretto255_map.
refers to that map as ristretto255_map.
The hash_to_ristretto255 function MUST be instantiated with an The hash_to_ristretto255 function MUST be instantiated with an
expand_message function that conforms to the requirements given in expand_message function that conforms to the requirements given in
Section 5.3. In addition, it MUST use a domain separation tag Section 5.3. In addition, it MUST use a domain separation tag
constructed as described in Section 3.1, and all domain separation constructed as described in Section 3.1, and all domain separation
recommendations given in Section 10.7 apply when implementing recommendations given in Section 10.7 apply when implementing
protocols that use hash_to_ristretto255. protocols that use hash_to_ristretto255.
hash_to_ristretto255(msg) hash_to_ristretto255(msg)
skipping to change at page 68, line 42 skipping to change at line 3101
* ENC_VAR: "RO" * ENC_VAR: "RO"
For example, if expand_message is expand_message_xmd using SHA-512, For example, if expand_message is expand_message_xmd using SHA-512,
the REQUIRED identifier is: the REQUIRED identifier is:
ristretto255_XMD:SHA-512_R255MAP_RO_ ristretto255_XMD:SHA-512_R255MAP_RO_
Appendix C. Hashing to decaf448 Appendix C. Hashing to decaf448
Similar to ristretto255, decaf448 Similar to ristretto255, decaf448 [ristretto255-decaf448] provides a
[I-D.irtf-cfrg-ristretto255-decaf448] provides a prime-order group prime-order group based on curve448 [RFC7748]. This section
based on Curve448 [RFC7748]. This section describes describes hash_to_decaf448, which implements a random-oracle encoding
hash_to_decaf448, which implements a random-oracle encoding to this to this group that has a uniform output distribution (Section 2.2.3)
group that has a uniform output distribution (Section 2.2.3) and the and the same security properties and interface as the hash_to_curve
same security properties and interface as the hash_to_curve function function (Section 3).
(Section 3).
The decaf448 API defines a one-way map The decaf448 API defines a one-way map ([ristretto255-decaf448],
([I-D.irtf-cfrg-ristretto255-decaf448], Section 5.3.4); this section Section 5.3.4); this section refers to that map as decaf448_map.
refers to that map as decaf448_map.
The hash_to_decaf448 function MUST be instantiated with an The hash_to_decaf448 function MUST be instantiated with an
expand_message function that conforms to the requirements given in expand_message function that conforms to the requirements given in
Section 5.3. In addition, it MUST use a domain separation tag Section 5.3. In addition, it MUST use a domain separation tag
constructed as described in Section 3.1, and all domain separation constructed as described in Section 3.1, and all domain separation
recommendations given in Section 10.7 apply when implementing recommendations given in Section 10.7 apply when implementing
protocols that use hash_to_decaf448. protocols that use hash_to_decaf448.
hash_to_decaf448(msg) hash_to_decaf448(msg)
skipping to change at page 69, line 47 skipping to change at line 3153
* MAP_ID: "D448MAP" * MAP_ID: "D448MAP"
* ENC_VAR: "RO" * ENC_VAR: "RO"
For example, if expand_message is expand_message_xof using SHAKE256, For example, if expand_message is expand_message_xof using SHAKE256,
the REQUIRED identifier is: the REQUIRED identifier is:
decaf448_XOF:SHAKE256_D448MAP_RO_ decaf448_XOF:SHAKE256_D448MAP_RO_
Appendix D. Rational maps Appendix D. Rational Maps
This section gives rational maps that can be used when hashing to This section gives rational maps that can be used when hashing to
twisted Edwards or Montgomery curves. twisted Edwards or Montgomery curves.
Given a twisted Edwards curve, Appendix D.1 shows how to derive a Given a twisted Edwards curve, Appendix D.1 shows how to derive a
corresponding Montgomery curve and how to map from that curve to the corresponding Montgomery curve and how to map from that curve to the
twisted Edwards curve. This mapping may be used when hashing to twisted Edwards curve. This mapping may be used when hashing to
twisted Edwards curves as described in Section 6.8. twisted Edwards curves as described in Section 6.8.
Given a Montgomery curve, Appendix D.2 shows how to derive a Given a Montgomery curve, Appendix D.2 shows how to derive a
corresponding Weierstrass curve and how to map from that curve to the corresponding Weierstrass curve and how to map from that curve to the
Montgomery curve. This mapping can be used to hash to Montgomery or Montgomery curve. This mapping can be used to hash to Montgomery or
twisted Edwards curves via the Shallue-van de Woestijne twisted Edwards curves via the Shallue-van de Woestijne method
(Section 6.6.1) or Simplified SWU (Section 6.6.2) method, as follows: (Section 6.6.1) or Simplified SWU method (Section 6.6.2), as follows:
* For Montgomery curves, first map to the Weierstrass curve, then * For Montgomery curves, first map to the Weierstrass curve, then
convert to Montgomery coordinates via the mapping. convert to Montgomery coordinates via the mapping.
* For twisted Edwards curves, compose the Weierstrass to Montgomery * For twisted Edwards curves, compose the mapping from Weierstrass
mapping with the Montgomery to twisted Edwards mapping to Montgomery with the mapping from Montgomery to twisted Edwards
(Appendix D.1) to obtain a Weierstrass curve and a mapping to the (Appendix D.1) to obtain a Weierstrass curve and a mapping to the
target twisted Edwards curve. Map to this Weierstrass curve, then target twisted Edwards curve. Map to this Weierstrass curve, then
convert to Edwards coordinates via the mapping. convert to Edwards coordinates via the mapping.
D.1. Generic Montgomery to twisted Edwards map D.1. Generic Mapping from Montgomery to Twisted Edwards
This section gives a generic birational map between twisted Edwards This section gives a generic birational map between twisted Edwards
and Montgomery curves. and Montgomery curves.
The map in this section is a simplified version of the map given in The map in this section is a simplified version of the map given in
[BBJLP08], Theorem 3.2. Specifically, this section's map handles [BBJLP08], Theorem 3.2. Specifically, this section's map handles
exceptional cases in a simplified way that is geared towards hashing exceptional cases in a simplified way that is geared towards hashing
to a twisted Edwards curve's prime-order subgroup. to a twisted Edwards curve's prime-order subgroup.
The twisted Edwards curve The twisted Edwards curve
skipping to change at page 72, line 4 skipping to change at line 3251
* a = (J + 2) / K * a = (J + 2) / K
* d = (J - 2) / K * d = (J - 2) / K
The rational map from the point (v, w) on the twisted Edwards curve The rational map from the point (v, w) on the twisted Edwards curve
to the point (s, t) on the Montgomery curve is given by to the point (s, t) on the Montgomery curve is given by
* s = (1 + w) / (1 - w) * s = (1 + w) / (1 - w)
* t = (1 + w) / (v * (1 - w)) * t = (1 + w) / (v * (1 - w))
The mapping is undefined when v == 0 or w == 1. When the goal is to The mapping is undefined when v == 0 or w == 1. When the goal is to
map into the prime-order subgroup of the Montgomery curve, it map into the prime-order subgroup of the Montgomery curve, it
suffices to return the identity point on the Montgomery curve in the suffices to return the identity point on the Montgomery curve in the
exceptional cases. exceptional cases.
D.2. Weierstrass to Montgomery map D.2. Mapping from Weierstrass to Montgomery
The rational map from the point (s, t) on the Montgomery curve The rational map from the point (s, t) on the Montgomery curve
K * t^2 = s^3 + J * s^2 + s K * t^2 = s^3 + J * s^2 + s
to the point (x, y) on the equivalent Weierstrass curve to the point (x, y) on the equivalent Weierstrass curve
y^2 = x^3 + A * x + B y^2 = x^3 + A * x + B
is given by: is given by
* A = (3 - J^2) / (3 * K^2) * A = (3 - J^2) / (3 * K^2)
* B = (2 * J^3 - 9 * J) / (27 * K^3) * B = (2 * J^3 - 9 * J) / (27 * K^3)
* x = (3 * s + J) / (3 * K) * x = (3 * s + J) / (3 * K)
* y = t / K * y = t / K
The inverse map, from the point (x, y) to the point (s, t), is given The inverse map, from the point (x, y) to the point (s, t), is given
by by
* s = (3 * K * x - J) / 3 * s = (3 * K * x - J) / 3
* t = y * K * t = y * K
This mapping can be used to apply the Shallue-van de Woestijne This mapping can be used to apply the Shallue-van de Woestijne method
(Section 6.6.1) or Simplified SWU (Section 6.6.2) method to (Section 6.6.1) or Simplified SWU method (Section 6.6.2) to
Montgomery curves. Montgomery curves.
Appendix E. Isogeny maps for suites Appendix E. Isogeny Maps for Suites
This section specifies the isogeny maps for the secp256k1 and This section specifies the isogeny maps for the secp256k1 and
BLS12-381 suites listed in Section 8. BLS12-381 suites listed in Section 8.
These maps are given in terms of affine coordinates. Wahby and Boneh These maps are given in terms of affine coordinates. Wahby and Boneh
([WB19], Section 4.3) show how to evaluate these maps in a projective ([WB19], Section 4.3) show how to evaluate these maps in a projective
coordinate system (Appendix G.1), which avoids modular inversions. coordinate system (Appendix G.1), which avoids modular inversions.
Refer to the draft repository [hash2curve-repo] for a Sage [SAGE] Refer to [hash2curve-repo] for a Sage [SAGE] script that constructs
script that constructs these isogenies. these isogenies.
E.1. 3-isogeny map for secp256k1 E.1. 3-Isogeny Map for secp256k1
This section specifies the isogeny map for the secp256k1 suite listed This section specifies the isogeny map for the secp256k1 suite listed
in Section 8.7. in Section 8.7.
The 3-isogeny map from (x', y') on E' to (x, y) on E is given by the The 3-isogeny map from (x', y') on E' to (x, y) on E is given by the
following rational functions: following rational functions:
* x = x_num / x_den, where * x = x_num / x_den, where
- x_num = k_(1,3) * x'^3 + k_(1,2) * x'^2 + k_(1,1) * x' + - x_num = k_(1,3) * x'^3 + k_(1,2) * x'^2 + k_(1,1) * x' +
skipping to change at page 73, line 29 skipping to change at line 3324
* y = y' * y_num / y_den, where * y = y' * y_num / y_den, where
- y_num = k_(3,3) * x'^3 + k_(3,2) * x'^2 + k_(3,1) * x' + - y_num = k_(3,3) * x'^3 + k_(3,2) * x'^2 + k_(3,1) * x' +
k_(3,0) k_(3,0)
- y_den = x'^3 + k_(4,2) * x'^2 + k_(4,1) * x' + k_(4,0) - y_den = x'^3 + k_(4,2) * x'^2 + k_(4,1) * x' + k_(4,0)
The constants used to compute x_num are as follows: The constants used to compute x_num are as follows:
* k_(1,0) = * k_(1,0) =0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38
0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa8c7 daaaaa8c7
* k_(1,1) = * k_(1,1) =
0x7d3d4c80bc321d5b9f315cea7fd44c5d595d2fc0bf63b92dfff1044f17c6581 0x7d3d4c80bc321d5b9f315cea7fd44c5d595d2fc0bf63b92dfff1044f17c6581
* k_(1,2) = * k_(1,2) =
0x534c328d23f234e6e2a413deca25caece4506144037c40314ecbd0b53d9dd262 0x534c328d23f234e6e2a413deca25caece4506144037c40314ecbd0b53d9dd262
* k_(1,3) = * k_(1,3) =
0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa88c 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa88c
skipping to change at page 74, line 25 skipping to change at line 3369
* k_(4,0) = * k_(4,0) =
0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffff93b 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffff93b
* k_(4,1) = * k_(4,1) =
0x7a06534bb8bdb49fd5e9e6632722c2989467c1bfc8e8d978dfb425d2685c2573 0x7a06534bb8bdb49fd5e9e6632722c2989467c1bfc8e8d978dfb425d2685c2573
* k_(4,2) = * k_(4,2) =
0x6484aa716545ca2cf3a70c3fa8fe337e0a3d21162f0d6299a7bf8192bfd2a76f 0x6484aa716545ca2cf3a70c3fa8fe337e0a3d21162f0d6299a7bf8192bfd2a76f
E.2. 11-isogeny map for BLS12-381 G1 E.2. 11-Isogeny Map for BLS12-381 G1
The 11-isogeny map from (x', y') on E' to (x, y) on E is given by the The 11-isogeny map from (x', y') on E' to (x, y) on E is given by the
following rational functions: following rational functions:
* x = x_num / x_den, where * x = x_num / x_den, where
- x_num = k_(1,11) * x'^11 + k_(1,10) * x'^10 + k_(1,9) * x'^9 + - x_num = k_(1,11) * x'^11 + k_(1,10) * x'^10 + k_(1,9) * x'^9 +
... + k_(1,0) ... + k_(1,0)
- x_den = x'^10 + k_(2,9) * x'^9 + k_(2,8) * x'^8 + ... + k_(2,0) - x_den = x'^10 + k_(2,9) * x'^9 + k_(2,8) * x'^8 + ... + k_(2,0)
skipping to change at page 78, line 23 skipping to change at line 3556
* k_(4,12) = 0xad6b9514c767fe3c3613144b45f1496543346d98adf02267d5cee * k_(4,12) = 0xad6b9514c767fe3c3613144b45f1496543346d98adf02267d5cee
f9a00d9b8693000763e3b90ac11e99b138573345cc f9a00d9b8693000763e3b90ac11e99b138573345cc
* k_(4,13) = 0x2660400eb2e4f3b628bdd0d53cd76f2bf565b94e72927c1cb748d * k_(4,13) = 0x2660400eb2e4f3b628bdd0d53cd76f2bf565b94e72927c1cb748d
f27942480e420517bd8714cc80d1fadc1326ed06f7 f27942480e420517bd8714cc80d1fadc1326ed06f7
* k_(4,14) = 0xe0fa1d816ddc03e6b24255e0d7819c171c40f65e273b853324efc * k_(4,14) = 0xe0fa1d816ddc03e6b24255e0d7819c171c40f65e273b853324efc
d6356caa205ca2f570f13497804415473a1d634b8f d6356caa205ca2f570f13497804415473a1d634b8f
E.3. 3-isogeny map for BLS12-381 G2 E.3. 3-Isogeny Map for BLS12-381 G2
The 3-isogeny map from (x', y') on E' to (x, y) on E is given by the The 3-isogeny map from (x', y') on E' to (x, y) on E is given by the
following rational functions: following rational functions:
* x = x_num / x_den, where * x = x_num / x_den, where
- x_num = k_(1,3) * x'^3 + k_(1,2) * x'^2 + k_(1,1) * x' + - x_num = k_(1,3) * x'^3 + k_(1,2) * x'^2 + k_(1,1) * x' +
k_(1,0) k_(1,0)
- x_den = x'^2 + k_(2,1) * x' + k_(2,0) - x_den = x'^2 + k_(2,1) * x' + k_(2,0)
skipping to change at page 80, line 5 skipping to change at line 3632
a0f6b0f6241eabfffeb153ffffb9feffffffffa8fb + 0x1a0111ea397fe69a4b1 a0f6b0f6241eabfffeb153ffffb9feffffffffa8fb + 0x1a0111ea397fe69a4b1
ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9fef ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9fef
fffffffa8fb * I fffffffa8fb * I
* k_(4,1) = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2 * k_(4,1) = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2
a0f6b0f6241eabfffeb153ffffb9feffffffffa9d3 * I a0f6b0f6241eabfffeb153ffffb9feffffffffa9d3 * I
* k_(4,2) = 0x12 + 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512b * k_(4,2) = 0x12 + 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512b
f6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaa99 * I f6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaa99 * I
Appendix F. Straight-line implementations of deterministic mappings Appendix F. Straight-Line Implementations of Deterministic Mappings
This section gives straight-line implementations of the mappings of This section gives straight-line implementations of the mappings of
Section 6. These implementations are generic, i.e., they are defined Section 6. These implementations are generic, i.e., they are defined
for any curve and field. Appendix G gives further implementations for any curve and field. Appendix G gives further implementations
that are optimized for specific classes of curves and fields. that are optimized for specific classes of curves and fields.
F.1. Shallue-van de Woestijne method F.1. Shallue-van de Woestijne Method
This section gives a straight-line implementation of the Shallue and This section gives a straight-line implementation of the Shallue-van
van de Woestijne method for any Weierstrass curve of the form given de Woestijne method for any Weierstrass curve of the form given in
in Section 6.6. See Section 6.6.1 for information on the constants Section 6.6. See Section 6.6.1 for information on the constants used
used in this mapping. in this mapping.
Note that the constant c3 below MUST be chosen such that sgn0(c3) = Note that the constant c3 below MUST be chosen such that sgn0(c3) =
0. In other words, if the square-root computation returns a value cx 0. In other words, if the square-root computation returns a value cx
such that sgn0(cx) = 1, set c3 = -cx; otherwise, set c3 = cx. such that sgn0(cx) = 1, set c3 = -cx; otherwise, set c3 = cx.
map_to_curve_svdw(u) map_to_curve_svdw(u)
Input: u, an element of F. Input: u, an element of F.
Output: (x, y), a point on E. Output: (x, y), a point on E.
skipping to change at page 81, line 23 skipping to change at line 3699
28. x = CMOV(x, x2, e2) # x = x2 if gx2 is square and gx1 is not 28. x = CMOV(x, x2, e2) # x = x2 if gx2 is square and gx1 is not
29. gx = x^2 29. gx = x^2
30. gx = gx + A 30. gx = gx + A
31. gx = gx * x 31. gx = gx * x
32. gx = gx + B 32. gx = gx + B
33. y = sqrt(gx) 33. y = sqrt(gx)
34. e3 = sgn0(u) == sgn0(y) 34. e3 = sgn0(u) == sgn0(y)
35. y = CMOV(-y, y, e3) # Select correct sign of y 35. y = CMOV(-y, y, e3) # Select correct sign of y
36. return (x, y) 36. return (x, y)
F.2. Simplified SWU method F.2. Simplified SWU Method
This section gives a straight-line implementation of the simplified This section gives a straight-line implementation of the Simplified
SWU method for any Weierstrass curve of the form given in SWU method for any Weierstrass curve of the form given in
Section 6.6. See Section 6.6.2 for information on the constants used Section 6.6. See Section 6.6.2 for information on the constants used
in this mapping. in this mapping.
This optimized, straight-line procedure applies to any base field. This optimized, straight-line procedure applies to any base field.
The sqrt_ratio subroutine is defined in Appendix F.2.1. The sqrt_ratio subroutine is defined in Appendix F.2.1.
map_to_curve_simple_swu(u) map_to_curve_simple_swu(u)
Input: u, an element of F. Input: u, an element of F.
skipping to change at page 82, line 38 skipping to change at line 3742
18. (is_gx1_square, y1) = sqrt_ratio(tv2, tv6) 18. (is_gx1_square, y1) = sqrt_ratio(tv2, tv6)
19. y = tv1 * u 19. y = tv1 * u
20. y = y * y1 20. y = y * y1
21. x = CMOV(x, tv3, is_gx1_square) 21. x = CMOV(x, tv3, is_gx1_square)
22. y = CMOV(y, y1, is_gx1_square) 22. y = CMOV(y, y1, is_gx1_square)
23. e1 = sgn0(u) == sgn0(y) 23. e1 = sgn0(u) == sgn0(y)
24. y = CMOV(-y, y, e1) 24. y = CMOV(-y, y, e1)
25. x = x / tv4 25. x = x / tv4
26. return (x, y) 26. return (x, y)
F.2.1. sqrt_ratio subroutines F.2.1. sqrt_ratio Subroutine
This section defines three variants of the sqrt_ratio subroutine used This section defines three variants of the sqrt_ratio subroutine used
by the above procedure. The first variant can be used with any by the above procedure. The first variant can be used with any
field; the others are optimized versions for specific fields. field; the others are optimized versions for specific fields.
The routines given in this section depend on the constant Z from the The routines given in this section depend on the constant Z from the
simplified SWU map. For correctness, sqrt_ratio and Simplified SWU map. For correctness, sqrt_ratio and
map_to_curve_simple_swu MUST use the same value for Z. map_to_curve_simple_swu MUST use the same value for Z.
F.2.1.1. sqrt_ratio for any field F.2.1.1. sqrt_ratio for Any Field
sqrt_ratio(u, v) sqrt_ratio(u, v)
Parameters: Parameters:
- F, a finite field of characteristic p and order q = p^m. - F, a finite field of characteristic p and order q = p^m.
- Z, the constant from the simplified SWU map. - Z, the constant from the Simplified SWU map.
Input: u and v, elements of F, where v != 0. Input: u and v, elements of F, where v != 0.
Output: (b, y), where Output: (b, y), where
b = True and y = sqrt(u / v) if (u / v) is square in F, and b = True and y = sqrt(u / v) if (u / v) is square in F, and
b = False and y = sqrt(Z * (u / v)) otherwise. b = False and y = sqrt(Z * (u / v)) otherwise.
Constants: Constants:
1. c1, the largest integer such that 2^c1 divides q - 1. 1. c1, the largest integer such that 2^c1 divides q - 1.
2. c2 = (q - 1) / (2^c1) # Integer arithmetic 2. c2 = (q - 1) / (2^c1) # Integer arithmetic
3. c3 = (c2 - 1) / 2 # Integer arithmetic 3. c3 = (c2 - 1) / 2 # Integer arithmetic
skipping to change at page 84, line 5 skipping to change at line 3803
19. tv5 = 2^tv5 19. tv5 = 2^tv5
20. tv5 = tv4^tv5 20. tv5 = tv4^tv5
21. e1 = tv5 == 1 21. e1 = tv5 == 1
22. tv2 = tv3 * tv1 22. tv2 = tv3 * tv1
23. tv1 = tv1 * tv1 23. tv1 = tv1 * tv1
24. tv5 = tv4 * tv1 24. tv5 = tv4 * tv1
25. tv3 = CMOV(tv2, tv3, e1) 25. tv3 = CMOV(tv2, tv3, e1)
26. tv4 = CMOV(tv5, tv4, e1) 26. tv4 = CMOV(tv5, tv4, e1)
27. return (isQR, tv3) 27. return (isQR, tv3)
F.2.1.2. optimized sqrt_ratio for q = 3 mod 4 F.2.1.2. Optimized sqrt_ratio for q = 3 mod 4
sqrt_ratio_3mod4(u, v) sqrt_ratio_3mod4(u, v)
Parameters: Parameters:
- F, a finite field of characteristic p and order q = p^m, - F, a finite field of characteristic p and order q = p^m,
where q = 3 mod 4. where q = 3 mod 4.
- Z, the constant from the simplified SWU map. - Z, the constant from the Simplified SWU map.
Input: u and v, elements of F, where v != 0. Input: u and v, elements of F, where v != 0.
Output: (b, y), where Output: (b, y), where
b = True and y = sqrt(u / v) if (u / v) is square in F, and b = True and y = sqrt(u / v) if (u / v) is square in F, and
b = False and y = sqrt(Z * (u / v)) otherwise. b = False and y = sqrt(Z * (u / v)) otherwise.
Constants: Constants:
1. c1 = (q - 3) / 4 # Integer arithmetic 1. c1 = (q - 3) / 4 # Integer arithmetic
2. c2 = sqrt(-Z) 2. c2 = sqrt(-Z)
skipping to change at page 84, line 36 skipping to change at line 3834
3. tv1 = tv1 * tv2 3. tv1 = tv1 * tv2
4. y1 = tv1^c1 4. y1 = tv1^c1
5. y1 = y1 * tv2 5. y1 = y1 * tv2
6. y2 = y1 * c2 6. y2 = y1 * c2
7. tv3 = y1^2 7. tv3 = y1^2
8. tv3 = tv3 * v 8. tv3 = tv3 * v
9. isQR = tv3 == u 9. isQR = tv3 == u
10. y = CMOV(y2, y1, isQR) 10. y = CMOV(y2, y1, isQR)
11. return (isQR, y) 11. return (isQR, y)
F.2.1.3. optimized sqrt_ratio for q = 5 mod 8 F.2.1.3. Optimized sqrt_ratio for q = 5 mod 8
sqrt_ratio_5mod8(u, v) sqrt_ratio_5mod8(u, v)
Parameters: Parameters:
- F, a finite field of characteristic p and order q = p^m, - F, a finite field of characteristic p and order q = p^m,
where q = 5 mod 8. where q = 5 mod 8.
- Z, the constant from the simplified SWU map. - Z, the constant from the Simplified SWU map.
Input: u and v, elements of F, where v != 0. Input: u and v, elements of F, where v != 0.
Output: (b, y), where Output: (b, y), where
b = True and y = sqrt(u / v) if (u / v) is square in F, and b = True and y = sqrt(u / v) if (u / v) is square in F, and
b = False and y = sqrt(Z * (u / v)) otherwise. b = False and y = sqrt(Z * (u / v)) otherwise.
Constants: Constants:
1. c1 = (q - 5) / 8 1. c1 = (q - 5) / 8
2. c2 = sqrt(-1) 2. c2 = sqrt(-1)
3. c3 = sqrt(Z / c2) 3. c3 = sqrt(Z / c2)
skipping to change at page 86, line 5 skipping to change at line 3879
16. y2 = y1 * c3 16. y2 = y1 * c3
17. tv1 = y2 * c2 17. tv1 = y2 * c2
18. tv2 = tv1^2 18. tv2 = tv1^2
19. tv2 = tv2 * v 19. tv2 = tv2 * v
20. tv3 = Z * u 20. tv3 = Z * u
21. e2 = tv2 == tv3 21. e2 = tv2 == tv3
22. y2 = CMOV(y2, tv1, e2) 22. y2 = CMOV(y2, tv1, e2)
23. y = CMOV(y2, y1, isQR) 23. y = CMOV(y2, y1, isQR)
24. return (isQR, y) 24. return (isQR, y)
F.3. Elligator 2 method F.3. Elligator 2 Method
This section gives a straight-line implementation of the Elligator 2 This section gives a straight-line implementation of the Elligator 2
method for any Montgomery curve of the form given in Section 6.7. method for any Montgomery curve of the form given in Section 6.7.
See Section 6.7.1 for information on the constants used in this See Section 6.7.1 for information on the constants used in this
mapping. mapping.
Appendix G.2 gives optimized straight-line procedures that apply to Appendix G.2 gives optimized straight-line procedures that apply to
specific classes of curves and base fields, including curve25519 and specific classes of curves and base fields, including curve25519 and
curve448 [RFC7748]. curve448 [RFC7748].
skipping to change at page 87, line 5 skipping to change at line 3923
14. e2 = is_square(gx1) # If is_square(gx1) 14. e2 = is_square(gx1) # If is_square(gx1)
15. x = CMOV(x2, x1, e2) # then x = x1, else x = x2 15. x = CMOV(x2, x1, e2) # then x = x1, else x = x2
16. y2 = CMOV(gx2, gx1, e2) # then y2 = gx1, else y2 = gx2 16. y2 = CMOV(gx2, gx1, e2) # then y2 = gx1, else y2 = gx2
17. y = sqrt(y2) 17. y = sqrt(y2)
18. e3 = sgn0(y) == 1 18. e3 = sgn0(y) == 1
19. y = CMOV(y, -y, e2 XOR e3) # fix sign of y 19. y = CMOV(y, -y, e2 XOR e3) # fix sign of y
20. s = x * K 20. s = x * K
21. t = y * K 21. t = y * K
22. return (s, t) 22. return (s, t)
Appendix G. Curve-specific optimized sample code Appendix G. Curve-Specific Optimized Sample Code
This section gives sample implementations optimized for some of the This section gives sample implementations optimized for some of the
elliptic curves listed in Section 8. Sample Sage [SAGE] code for elliptic curves listed in Section 8. Sample Sage code [SAGE] for
each algorithm can also be found in the draft repository each algorithm can also be found in [hash2curve-repo].
[hash2curve-repo].
G.1. Interface and projective coordinate systems G.1. Interface and Projective Coordinate Systems
The sample code in this section uses a different interface than the The sample code in this section uses a different interface than the
mappings of Section 6. Specifically, each mapping function in this mappings of Section 6. Specifically, each mapping function in this
section has the following signature: section has the following signature:
(xn, xd, yn, yd) = map_to_curve(u) (xn, xd, yn, yd) = map_to_curve(u)
The resulting affine point (x, y) is given by (xn / xd, yn / yd). The resulting affine point (x, y) is given by (xn / xd, yn / yd).
The reason for this modified interface is that it enables further The reason for this modified interface is that it enables further
optimizations when working with points in a projective coordinate optimizations when working with points in a projective coordinate
system. This is desirable, for example, when the resulting point system. This is desirable, for example, when the resulting point
will be immediately multiplied by a scalar, since most scalar will be immediately multiplied by a scalar, since most scalar
multiplication algorithms operate on projective points. multiplication algorithms operate on projective points.
Projective coordinates are also useful when implementing random Projective coordinates are also useful when implementing random-
oracle encodings (Section 3). One reason is that, in general, point oracle encodings (Section 3). One reason is that, in general, point
addition is faster using projective coordinates. Another reason is addition is faster using projective coordinates. Another reason is
that, for Weierstrass curves, projective coordinates allow using that, for Weierstrass curves, projective coordinates allow using
complete addition formulas [RCB16]. This is especially convenient complete addition formulas [RCB16]. This is especially convenient
when implementing a constant-time encoding, because it eliminates the when implementing a constant-time encoding, because it eliminates the
need for a special case when Q0 == Q1, which incomplete addition need for a special case when Q0 == Q1, which incomplete addition
formulas usually do not handle. formulas usually do not handle.
The following are two commonly used projective coordinate systems and The following are two commonly used projective coordinate systems and
the corresponding conversions: the corresponding conversions:
skipping to change at page 89, line 27 skipping to change at line 4041
39. return (xn, xd, y, 1) 39. return (xn, xd, y, 1)
G.2.2. edwards25519 G.2.2. edwards25519
The following is a straight-line implementation of Elligator 2 for The following is a straight-line implementation of Elligator 2 for
edwards25519 [RFC7748] as specified in Section 8.5. The subroutine edwards25519 [RFC7748] as specified in Section 8.5. The subroutine
map_to_curve_elligator2_curve25519 is defined in Appendix G.2.1. map_to_curve_elligator2_curve25519 is defined in Appendix G.2.1.
Note that the sign of the constant c1 below is chosen as specified in Note that the sign of the constant c1 below is chosen as specified in
Section 6.8.1, i.e., applying the rational map to the edwards25519 Section 6.8.1, i.e., applying the rational map to the edwards25519
base point yields the curve25519 base point (see erratum [EID4730]). base point yields the curve25519 base point (see erratum [Err4730]).
map_to_curve_elligator2_edwards25519(u) map_to_curve_elligator2_edwards25519(u)
Input: u, an element of F. Input: u, an element of F.
Output: (xn, xd, yn, yd) such that (xn / xd, yn / yd) is a Output: (xn, xd, yn, yd) such that (xn / xd, yn / yd) is a
point on edwards25519. point on edwards25519.
Constants: Constants:
1. c1 = sqrt(-486664) # sgn0(c1) MUST equal 0 1. c1 = sqrt(-486664) # sgn0(c1) MUST equal 0
skipping to change at page 93, line 5 skipping to change at line 4165
30. tv4 = tv4 * yd2 30. tv4 = tv4 * yd2
31. yEd = yEd + tv4 31. yEd = yEd + tv4
32. tv1 = xEd * yEd 32. tv1 = xEd * yEd
33. e = tv1 == 0 33. e = tv1 == 0
34. xEn = CMOV(xEn, 0, e) 34. xEn = CMOV(xEn, 0, e)
35. xEd = CMOV(xEd, 1, e) 35. xEd = CMOV(xEd, 1, e)
36. yEn = CMOV(yEn, 1, e) 36. yEn = CMOV(yEn, 1, e)
37. yEd = CMOV(yEd, 1, e) 37. yEd = CMOV(yEd, 1, e)
38. return (xEn, xEd, yEn, yEd) 38. return (xEn, xEd, yEn, yEd)
G.2.5. Montgomery curves with q = 3 (mod 4) G.2.5. Montgomery Curves with q = 3 (mod 4)
The following is a straight-line implementation of Elligator 2 that The following is a straight-line implementation of Elligator 2 that
applies to any Montgomery curve defined over GF(q) where q = 3 (mod applies to any Montgomery curve defined over GF(q) where q = 3 (mod
4). 4).
For curves where K = 1, the implementation given in Appendix G.2.3 For curves where K = 1, the implementation given in Appendix G.2.3
gives identical results with slightly reduced cost. gives identical results with slightly reduced cost.
map_to_curve_elligator2_3mod4(u) map_to_curve_elligator2_3mod4(u)
skipping to change at page 95, line 5 skipping to change at line 4219
25. tv2 = tv2 * gxd 25. tv2 = tv2 * gxd
26. e2 = tv2 == gx1 26. e2 = tv2 == gx1
27. xn = CMOV(x2n, x1n, e2) # If e2, x = x1, else x = x2 27. xn = CMOV(x2n, x1n, e2) # If e2, x = x1, else x = x2
28. xn = xn * K 28. xn = xn * K
29. y = CMOV(y2, y1, e2) # If e2, y = y1, else y = y2 29. y = CMOV(y2, y1, e2) # If e2, y = y1, else y = y2
30. e3 = sgn0(y) == 1 # Fix sign of y 30. e3 = sgn0(y) == 1 # Fix sign of y
31. y = CMOV(y, -y, e2 XOR e3) 31. y = CMOV(y, -y, e2 XOR e3)
32. y = y * K 32. y = y * K
33. return (xn, xd, y, 1) 33. return (xn, xd, y, 1)
G.2.6. Montgomery curves with q = 5 (mod 8) G.2.6. Montgomery Curves with q = 5 (mod 8)
The following is a straight-line implementation of Elligator 2 that The following is a straight-line implementation of Elligator 2 that
applies to any Montgomery curve defined over GF(q) where q = 5 (mod applies to any Montgomery curve defined over GF(q) where q = 5 (mod
8). 8).
For curves where K = 1, the implementation given in Appendix G.2.1 For curves where K = 1, the implementation given in Appendix G.2.1
gives identical results with slightly reduced cost. gives identical results with slightly reduced cost.
map_to_curve_elligator2_5mod8(u) map_to_curve_elligator2_5mod8(u)
skipping to change at page 96, line 25 skipping to change at line 4288
37. tv2 = tv2 * gxd 37. tv2 = tv2 * gxd
38. e3 = tv2 == gx1 38. e3 = tv2 == gx1
39. xn = CMOV(x2n, x1n, e3) # If e3, x = x1, else x = x2 39. xn = CMOV(x2n, x1n, e3) # If e3, x = x1, else x = x2
40. xn = xn * K 40. xn = xn * K
41. y = CMOV(y2, y1, e3) # If e3, y = y1, else y = y2 41. y = CMOV(y2, y1, e3) # If e3, y = y1, else y = y2
42. e4 = sgn0(y) == 1 # Fix sign of y 42. e4 = sgn0(y) == 1 # Fix sign of y
43. y = CMOV(y, -y, e3 XOR e4) 43. y = CMOV(y, -y, e3 XOR e4)
44. y = y * K 44. y = y * K
45. return (xn, xd, y, 1) 45. return (xn, xd, y, 1)
G.3. Cofactor clearing for BLS12-381 G2 G.3. Cofactor Clearing for BLS12-381 G2
The curve BLS12-381, whose parameters are defined in Section 8.8.2, The curve BLS12-381, whose parameters are defined in Section 8.8.2,
admits an efficiently-computable endomorphism psi that can be used to admits an efficiently computable endomorphism, psi, that can be used
speed up cofactor clearing for G2 [SBCDK09] [FKR11] [BP17] (see also to speed up cofactor clearing for G2 [SBCDK09] [FKR11] [BP17] (see
Section 7). This section implements the endomorphism psi and a fast also Section 7). This section implements the endomorphism psi and a
cofactor clearing method described by Budroni and Pintore [BP17]. fast cofactor clearing method described by Budroni and Pintore
[BP17].
The functions in this section operate on points whose coordinates are The functions in this section operate on points whose coordinates are
represented as ratios, i.e., (xn, xd, yn, yd) corresponds to the represented as ratios, i.e., (xn, xd, yn, yd) corresponds to the
point (xn / xd, yn / yd); see Appendix G.1 for further discussion of point (xn / xd, yn / yd); see Appendix G.1 for further discussion of
projective coordinates. When points are represented in affine projective coordinates. When points are represented in affine
coordinates, one can simply ignore the denominators (xd == 1 and yd coordinates, one can simply ignore the denominators (xd == 1 and
== 1). yd == 1).
The following function computes the Frobenius endomorphism for an The following function computes the Frobenius endomorphism for an
element of F = GF(p^2) with basis (1, I), where I^2 + 1 == 0 in F. element of F = GF(p^2) with basis (1, I), where I^2 + 1 == 0 in F.
(This is the base field of the elliptic curve E defined in (This is the base field of the elliptic curve E defined in
Section 8.8.2.) Section 8.8.2.)
frobenius(x) frobenius(x)
Input: x, an element of GF(p^2). Input: x, an element of GF(p^2).
Output: a, an element of GF(p^2). Output: a, an element of GF(p^2).
Notation: x = x0 + I * x1, where x0 and x1 are elements of GF(p). Notation: x = x0 + I * x1, where x0 and x1 are elements of GF(p).
Steps: Steps:
1. a = x0 - I * x1 1. a = x0 - I * x1
2. return a 2. return a
skipping to change at page 98, line 35 skipping to change at line 4385
3. t3 = 2 * P 3. t3 = 2 * P
4. t3 = psi2(t3) 4. t3 = psi2(t3)
5. t3 = t3 - t2 5. t3 = t3 - t2
6. t2 = t1 + t2 6. t2 = t1 + t2
7. t2 = c1 * t2 7. t2 = c1 * t2
8. t3 = t3 + t2 8. t3 = t3 + t2
9. t3 = t3 - t1 9. t3 = t3 - t1
10. Q = t3 - P 10. Q = t3 - P
11. return Q 11. return Q
Appendix H. Scripts for parameter generation Appendix H. Scripts for Parameter Generation
This section gives Sage [SAGE] scripts used to generate parameters This section gives Sage scripts [SAGE] used to generate parameters
for the mappings of Section 6. for the mappings of Section 6.
H.1. Finding Z for the Shallue-van de Woestijne map H.1. Finding Z for the Shallue-van de Woestijne Map
The below function outputs an appropriate Z for the Shallue and van The below function outputs an appropriate Z for the Shallue-van de
de Woestijne map (Section 6.6.1). Woestijne map (Section 6.6.1).
# Arguments: # Arguments:
# - F, a field object, e.g., F = GF(2^521 - 1) # - F, a field object, e.g., F = GF(2^521 - 1)
# - A and B, the coefficients of the curve y^2 = x^3 + A * x + B # - A and B, the coefficients of the curve y^2 = x^3 + A * x + B
def find_z_svdw(F, A, B, init_ctr=1): def find_z_svdw(F, A, B, init_ctr=1):
g = lambda x: F(x)^3 + F(A) * F(x) + F(B) g = lambda x: F(x)^3 + F(A) * F(x) + F(B)
h = lambda Z: -(F(3) * Z^2 + F(4) * A) / (F(4) * g(Z)) h = lambda Z: -(F(3) * Z^2 + F(4) * A) / (F(4) * g(Z))
# NOTE: if init_ctr=1 fails to find Z, try setting it to F.gen() # NOTE: if init_ctr=1 fails to find Z, try setting it to F.gen()
ctr = init_ctr ctr = init_ctr
while True: while True:
skipping to change at page 100, line 45 skipping to change at line 4468
def find_z_ell2(F): def find_z_ell2(F):
ctr = F.gen() ctr = F.gen()
while True: while True:
for Z_cand in (F(ctr), F(-ctr)): for Z_cand in (F(ctr), F(-ctr)):
# Z must be a non-square in F. # Z must be a non-square in F.
if is_square(Z_cand): if is_square(Z_cand):
continue continue
return Z_cand return Z_cand
ctr += 1 ctr += 1
Appendix I. sqrt and is_square functions Appendix I. sqrt and is_square Functions
This section defines special-purpose sqrt functions for the three This section defines special-purpose sqrt functions for the three
most common cases, q = 3 (mod 4), q = 5 (mod 8), and q = 9 (mod 16), most common cases, q = 3 (mod 4), q = 5 (mod 8), and q = 9 (mod 16),
plus a generic constant-time algorithm that works for any prime plus a generic constant-time algorithm that works for any prime
modulus. modulus.
In addition, it gives an optimized is_square method for GF(p^2). In addition, it gives an optimized is_square method for GF(p^2).
I.1. sqrt for q = 3 (mod 4) I.1. sqrt for q = 3 (mod 4)
skipping to change at page 102, line 31 skipping to change at line 4543
3. tv3 = c2 * tv1 3. tv3 = c2 * tv1
4. tv4 = c3 * tv1 4. tv4 = c3 * tv1
5. e1 = (tv2^2) == x 5. e1 = (tv2^2) == x
6. e2 = (tv3^2) == x 6. e2 = (tv3^2) == x
7. tv1 = CMOV(tv1, tv2, e1) # Select tv2 if (tv2^2) == x 7. tv1 = CMOV(tv1, tv2, e1) # Select tv2 if (tv2^2) == x
8. tv2 = CMOV(tv4, tv3, e2) # Select tv3 if (tv3^2) == x 8. tv2 = CMOV(tv4, tv3, e2) # Select tv3 if (tv3^2) == x
9. e3 = (tv2^2) == x 9. e3 = (tv2^2) == x
10. z = CMOV(tv1, tv2, e3) # Select the sqrt from tv1 and tv2 10. z = CMOV(tv1, tv2, e3) # Select the sqrt from tv1 and tv2
11. return z 11. return z
I.4. Constant-time Tonelli-Shanks algorithm I.4. Constant-Time Tonelli-Shanks Algorithm
This algorithm is a constant-time version of the classic Tonelli- This algorithm is a constant-time version of the classic Tonelli-
Shanks algorithm ([C93], Algorithm 1.5.1) due to Sean Bowe, Jack Shanks algorithm ([C93], Algorithm 1.5.1) due to Sean Bowe, Jack
Grigg, and Eirik Ogilvie-Wigley [jubjub-fq], adapted and optimized by Grigg, and Eirik Ogilvie-Wigley [jubjub-fq], adapted and optimized by
Michael Scott. Michael Scott.
This algorithm applies to GF(p) for any p. Note, however, that the This algorithm applies to GF(p) for any p. Note, however, that the
special-purpose algorithms given in the prior sections are faster, special-purpose algorithms given in the prior sections are faster,
when they apply. when they apply.
skipping to change at page 103, line 46 skipping to change at line 4595
16. b = t 16. b = t
17. return z 17. return z
I.5. is_square for F = GF(p^2) I.5. is_square for F = GF(p^2)
The following is_square method applies to any field F = GF(p^2) with The following is_square method applies to any field F = GF(p^2) with
basis (1, I) represented as described in Section 2.1, i.e., an basis (1, I) represented as described in Section 2.1, i.e., an
element x = (x_1, x_2) = x_1 + x_2 * I. element x = (x_1, x_2) = x_1 + x_2 * I.
Other optimizations of this type are possible in other extension Other optimizations of this type are possible in other extension
fields; see, e.g., [AR13] for more information. fields; see, for example, [AR13] for more information.
is_square(x) is_square(x)
Parameters: Parameters:
- F, an extension field of characteristic p and order q = p^2 - F, an extension field of characteristic p and order q = p^2
with basis (1, I). with basis (1, I).
Input: x, an element of F. Input: x, an element of F.
Output: True if x is square in F, and False otherwise. Output: True if x is square in F, and False otherwise.
skipping to change at page 104, line 26 skipping to change at line 4618
Procedure: Procedure:
1. tv1 = x_1^2 1. tv1 = x_1^2
2. tv2 = I * x_2 2. tv2 = I * x_2
3. tv2 = tv2^2 3. tv2 = tv2^2
4. tv1 = tv1 - tv2 4. tv1 = tv1 - tv2
5. tv1 = tv1^c1 5. tv1 = tv1^c1
6. e1 = tv1 != -1 # Note: -1 in F 6. e1 = tv1 != -1 # Note: -1 in F
7. return e1 7. return e1
Appendix J. Suite test vectors Appendix J. Suite Test Vectors
This section gives test vectors for each suite defined in Section 8. This section gives test vectors for each suite defined in Section 8.
The test vectors in this section were generated using code that is The test vectors in this section were generated using code that is
available from [hash2curve-repo]. available from [hash2curve-repo].
Each test vector in this section lists values computed by the Each test vector in this section lists values computed by the
appropriate encoding function, with variable names defined as in appropriate encoding function, with variable names defined as in
Section 3. For example, for a suite whose encoding type is random Section 3. For example, for a suite whose encoding type is random
oracle, the test vector gives the value for msg, u, Q0, Q1, and the oracle, the test vector gives the value for msg, u, Q0, Q1, and the
output point P. output point P.
skipping to change at page 149, line 41 skipping to change at line 6795
9363bdccf0a1fc0029bad07d65b15ccfe6dd25e20d 9363bdccf0a1fc0029bad07d65b15ccfe6dd25e20d
Q.x = 19592c812d5a50c5601062faba14c7d670711745311c879de1235a Q.x = 19592c812d5a50c5601062faba14c7d670711745311c879de1235a
0a11c75aab61327bf2d1725db07ec4d6996a682886 0a11c75aab61327bf2d1725db07ec4d6996a682886
+ I * 0eef4fa41ddc17ed47baf447a2c498548f3c72a02381313d13bef9 + I * 0eef4fa41ddc17ed47baf447a2c498548f3c72a02381313d13bef9
16e240b61ce125539090d62d9fbb14a900bf1b8e90 16e240b61ce125539090d62d9fbb14a900bf1b8e90
Q.y = 1260d6e0987eae96af9ebe551e08de22b37791d53f4db9e0d59da7 Q.y = 1260d6e0987eae96af9ebe551e08de22b37791d53f4db9e0d59da7
36e66699735793e853e26362531fe4adf99c1883e3 36e66699735793e853e26362531fe4adf99c1883e3
+ I * 0dbace5df0a4ac4ac2f45d8fdf8aee45484576fdd6efc4f98ab9b9 + I * 0dbace5df0a4ac4ac2f45d8fdf8aee45484576fdd6efc4f98ab9b9
f4112309e628255e183022d98ea5ed6e47ca00306c f4112309e628255e183022d98ea5ed6e47ca00306c
Appendix K. Expand test vectors Appendix K. Expand Test Vectors
This section gives test vectors for expand_message variants specified This section gives test vectors for expand_message variants specified
in Section 5.3. The test vectors in this section were generated in Section 5.3. The test vectors in this section were generated
using code that is available from [hash2curve-repo]. using code that is available from [hash2curve-repo].
Each test vector in this section lists the expand_message name, hash Each test vector in this section lists the expand_message name, hash
function, and DST, along with a series of tuples of the function function, and DST, along with a series of tuples of the function
inputs (msg and len_in_bytes), output (uniform_bytes), and inputs (msg and len_in_bytes), output (uniform_bytes), and
intermediate values (dst_prime and msg_prime). DST and msg are intermediate values (dst_prime and msg_prime). DST and msg are
represented as ASCII strings. Intermediate and output values are represented as ASCII strings. Intermediate and output values are
skipping to change at page 154, line 26 skipping to change at line 7016
616161616161616161616161616161616161616161616161616161 616161616161616161616161616161616161616161616161616161
616161616161616161616161616161008000515555582d5630312d 616161616161616161616161616161008000515555582d5630312d
435330322d776974682d657870616e6465722d5348413235362d31 435330322d776974682d657870616e6465722d5348413235362d31
323826 323826
uniform_bytes = 546aff5444b5b79aa6148bd81728704c32decb73a3ba76e9 uniform_bytes = 546aff5444b5b79aa6148bd81728704c32decb73a3ba76e9
e75885cad9def1d06d6792f8a7d12794e90efed817d96920d72889 e75885cad9def1d06d6792f8a7d12794e90efed817d96920d72889
6a4510864370c207f99bd4a608ea121700ef01ed879745ee3e4cee 6a4510864370c207f99bd4a608ea121700ef01ed879745ee3e4cee
f777eda6d9e5e38b90c86ea6fb0b36504ba4a45d22e86f6db5dd43 f777eda6d9e5e38b90c86ea6fb0b36504ba4a45d22e86f6db5dd43
d98a294bebb9125d5b794e9d2a81181066eb954966a487 d98a294bebb9125d5b794e9d2a81181066eb954966a487
K.2. expand_message_xmd(SHA-256) (long DST) K.2. expand_message_xmd(SHA-256) (Long DST)
name = expand_message_xmd name = expand_message_xmd
DST = QUUX-V01-CS02-with-expander-SHA256-128-long-DST-111111 DST = QUUX-V01-CS02-with-expander-SHA256-128-long-DST-111111
111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111 1111111111111111111111111111111111111111
hash = SHA256 hash = SHA256
k = 128 k = 128
skipping to change at page 167, line 26 skipping to change at line 7640
616161616161616161616161616161616161616161616161616161 616161616161616161616161616161616161616161616161616161
616161616161616161616161616161616161616161616161616161 616161616161616161616161616161616161616161616161616161
61616161610080515555582d5630312d435330322d776974682d65 61616161610080515555582d5630312d435330322d776974682d65
7870616e6465722d5348414b4531323824 7870616e6465722d5348414b4531323824
uniform_bytes = 9d763a5ce58f65c91531b4100c7266d479a5d9777ba76169 uniform_bytes = 9d763a5ce58f65c91531b4100c7266d479a5d9777ba76169
3d052acd37d149e7ac91c796a10b919cd74a591a1e38719fb91b72 3d052acd37d149e7ac91c796a10b919cd74a591a1e38719fb91b72
03e2af31eac3bff7ead2c195af7d88b8bc0a8adf3d1e90ab9bed6d 03e2af31eac3bff7ead2c195af7d88b8bc0a8adf3d1e90ab9bed6d
dc2b7f655dd86c730bdeaea884e73741097142c92f0e3fc1811b69 dc2b7f655dd86c730bdeaea884e73741097142c92f0e3fc1811b69
9ba593c7fbd81da288a29d423df831652e3a01a9374999 9ba593c7fbd81da288a29d423df831652e3a01a9374999
K.5. expand_message_xof(SHAKE128) (long DST) K.5. expand_message_xof(SHAKE128) (Long DST)
name = expand_message_xof name = expand_message_xof
DST = QUUX-V01-CS02-with-expander-SHAKE128-long-DST-11111111 DST = QUUX-V01-CS02-with-expander-SHAKE128-long-DST-11111111
111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111 1111111111111111111111111111111111111111
hash = SHAKE128 hash = SHAKE128
k = 128 k = 128
skipping to change at page 175, line 12 skipping to change at line 8010
616161616161616161616161616161616161616161616161616161 616161616161616161616161616161616161616161616161616161
616161616161616161616161616161616161616161616161616161 616161616161616161616161616161616161616161616161616161
61616161610080515555582d5630312d435330322d776974682d65 61616161610080515555582d5630312d435330322d776974682d65
7870616e6465722d5348414b4532353624 7870616e6465722d5348414b4532353624
uniform_bytes = 09afc76d51c2cccbc129c2315df66c2be7295a231203b8ab uniform_bytes = 09afc76d51c2cccbc129c2315df66c2be7295a231203b8ab
2dd7f95c2772c68e500bc72e20c602abc9964663b7a03a389be128 2dd7f95c2772c68e500bc72e20c602abc9964663b7a03a389be128
c56971ce81001a0b875e7fd17822db9d69792ddf6a23a151bf4700 c56971ce81001a0b875e7fd17822db9d69792ddf6a23a151bf4700
79c518279aef3e75611f8f828994a9988f4a8a256ddb8bae161e65 79c518279aef3e75611f8f828994a9988f4a8a256ddb8bae161e65
8d5a2a09bcfe839c6396dc06ee5c8ff3c22d3b1f9deb7e 8d5a2a09bcfe839c6396dc06ee5c8ff3c22d3b1f9deb7e
Acknowledgements
The authors would like to thank Adam Langley for his detailed writeup
of Elligator 2 with Curve25519 [L13]; Dan Boneh, Benjamin Lipp,
Christopher Patton, and Leonid Reyzin for educational discussions;
and David Benjamin, Daniel Bourdrez, Frank Denis, Sean Devlin, Justin
Drake, Bjoern Haase, Mike Hamburg, Dan Harkins, Daira Hopwood, Thomas
Icart, Andy Polyakov, Thomas Pornin, Mamy Ratsimbazafy, Michael
Scott, Filippo Valsorda, and Mathy Vanhoef for helpful reviews and
feedback.
Contributors
Sharon Goldberg
Boston University
Email: goldbe@cs.bu.edu
Ela Lee
Royal Holloway, University of London
Email: Ela.Lee.2010@live.rhul.ac.uk
Michele Orru
Email: michele.orru@ens.fr)
Authors' Addresses Authors' Addresses
Armando Faz-Hernandez Armando Faz-Hernandez
Cloudflare, Inc. Cloudflare, Inc.
101 Townsend St 101 Townsend St
San Francisco, San Francisco, CA 94107
United States of America United States of America
Email: armfazh@cloudflare.com Email: armfazh@cloudflare.com
Sam Scott Sam Scott
Cornell Tech Oso Security, Inc.
2 West Loop Rd 335 Madison Ave
New York, New York 10044, New York, NY 10017
United States of America United States of America
Email: sam.scott@cornell.edu Email: sam.scott89@gmail.com
Nick Sullivan Nick Sullivan
Cloudflare, Inc. Cloudflare, Inc.
101 Townsend St 101 Townsend St
San Francisco, San Francisco, CA 94107
United States of America United States of America
Email: nick@cloudflare.com Email: nicholas.sullivan@gmail.com
Riad S. Wahby Riad S. Wahby
Stanford University Stanford University
Email: rsw@cs.stanford.edu Email: rsw@cs.stanford.edu
Christopher A. Wood Christopher A. Wood
Cloudflare, Inc. Cloudflare, Inc.
101 Townsend St 101 Townsend St
San Francisco, San Francisco, CA 94107
United States of America United States of America
Email: caw@heapingbits.net Email: caw@heapingbits.net
 End of changes. 311 change blocks. 
844 lines changed or deleted 840 lines changed or added

This html diff was produced by rfcdiff 1.48.