< draft-irtf-cfrg-hash-to-curve-03.txt | draft-irtf-cfrg-hash-to-curve-04.txt > | |||
---|---|---|---|---|

Network Working Group S. Scott | Network Working Group A. Faz-Hernandez | |||

Internet-Draft Cornell Tech | Internet-Draft Cloudflare | |||

Intended status: Informational N. Sullivan | Intended status: Informational S. Scott | |||

Expires: September 12, 2019 Cloudflare | Expires: January 9, 2020 Cornell Tech | |||

N. Sullivan | ||||

Cloudflare | ||||

R. Wahby | ||||

Stanford University | ||||

C. Wood | C. Wood | |||

Apple Inc. | Apple Inc. | |||

March 11, 2019 | July 08, 2019 | |||

Hashing to Elliptic Curves | Hashing to Elliptic Curves | |||

draft-irtf-cfrg-hash-to-curve-03 | draft-irtf-cfrg-hash-to-curve-04 | |||

Abstract | Abstract | |||

This document specifies a number of algorithms that may be used to | This document specifies a number of algorithms that may be used to | |||

encode or hash an arbitrary string to a point on an Elliptic Curve. | encode or hash an arbitrary string to a point on an elliptic curve. | |||

Status of This Memo | Status of This Memo | |||

This Internet-Draft is submitted in full conformance with the | This Internet-Draft is submitted in full conformance with the | |||

provisions of BCP 78 and BCP 79. | provisions of BCP 78 and BCP 79. | |||

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

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

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

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

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

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

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

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

This Internet-Draft will expire on September 12, 2019. | This Internet-Draft will expire on January 9, 2020. | |||

Copyright Notice | Copyright Notice | |||

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

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

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

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

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

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

carefully, as they describe your rights and restrictions with respect | carefully, as they describe your rights and restrictions with respect | |||

to this document. Code Components extracted from this document must | to this document. Code Components extracted from this document must | |||

include Simplified BSD License text as described in Section 4.e of | include Simplified BSD License text as described in Section 4.e of | |||

the Trust Legal Provisions and are provided without warranty as | the Trust Legal Provisions and are provided without warranty as | |||

described in the Simplified BSD License. | described in the Simplified BSD License. | |||

Table of Contents | Table of Contents | |||

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 | 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 | |||

1.1. Requirements . . . . . . . . . . . . . . . . . . . . . . 3 | 1.1. Requirements . . . . . . . . . . . . . . . . . . . . . . 4 | |||

2. Background . . . . . . . . . . . . . . . . . . . . . . . . . 3 | 2. Background . . . . . . . . . . . . . . . . . . . . . . . . . 4 | |||

2.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 5 | 2.1. Elliptic curves . . . . . . . . . . . . . . . . . . . . . 4 | |||

2.1.1. Encoding . . . . . . . . . . . . . . . . . . . . . . 5 | 2.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 5 | |||

2.1.2. Serialization . . . . . . . . . . . . . . . . . . . . 5 | 2.2.1. Mappings . . . . . . . . . . . . . . . . . . . . . . 5 | |||

2.1.3. Random Oracle . . . . . . . . . . . . . . . . . . . . 6 | 2.2.2. Encodings . . . . . . . . . . . . . . . . . . . . . . 6 | |||

3. Algorithm Recommendations . . . . . . . . . . . . . . . . . . 6 | 2.2.3. Random oracle encodings . . . . . . . . . . . . . . . 6 | |||

4. Utility Functions . . . . . . . . . . . . . . . . . . . . . . 7 | 2.2.4. Serialization . . . . . . . . . . . . . . . . . . . . 7 | |||

5. Deterministic Encodings . . . . . . . . . . . . . . . . . . . 8 | 2.2.5. Domain separation . . . . . . . . . . . . . . . . . . 7 | |||

5.1. Interface . . . . . . . . . . . . . . . . . . . . . . . . 8 | 3. Roadmap . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 | |||

5.2. Notation . . . . . . . . . . . . . . . . . . . . . . . . 8 | 3.1. Domain separation requirements . . . . . . . . . . . . . 9 | |||

5.3. Encodings for Weierstrass curves . . . . . . . . . . . . 9 | 4. Utility Functions . . . . . . . . . . . . . . . . . . . . . . 10 | |||

5.3.1. Icart Method . . . . . . . . . . . . . . . . . . . . 9 | 5. Hashing to a Finite Field . . . . . . . . . . . . . . . . . . 13 | |||

5.3.2. Shallue-Woestijne-Ulas Method . . . . . . . . . . . . 10 | 5.1. Security considerations . . . . . . . . . . . . . . . . . 13 | |||

5.3.3. Simplified SWU Method . . . . . . . . . . . . . . . . 13 | 5.2. Performance considerations . . . . . . . . . . . . . . . 14 | |||

5.3.4. Boneh-Franklin Method . . . . . . . . . . . . . . . . 14 | 5.3. Implementation . . . . . . . . . . . . . . . . . . . . . 15 | |||

5.3.5. Fouque-Tibouchi Method . . . . . . . . . . . . . . . 16 | 6. Deterministic Mappings . . . . . . . . . . . . . . . . . . . 16 | |||

5.4. Encodings for Montgomery curves . . . . . . . . . . . . . 19 | 6.1. Interface . . . . . . . . . . . . . . . . . . . . . . . . 16 | |||

5.4.1. Elligator2 Method . . . . . . . . . . . . . . . . . . 19 | 6.2. Notation . . . . . . . . . . . . . . . . . . . . . . . . 16 | |||

6. Random Oracles . . . . . . . . . . . . . . . . . . . . . . . 22 | 6.3. Sign of the resulting point . . . . . . . . . . . . . . . 16 | |||

6.1. Interface . . . . . . . . . . . . . . . . . . . . . . . . 22 | 6.4. Exceptional cases . . . . . . . . . . . . . . . . . . . . 17 | |||

7. Curve Transformations . . . . . . . . . . . . . . . . . . . . 22 | 6.5. Mappings for Weierstrass curves . . . . . . . . . . . . . 17 | |||

8. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . 22 | 6.5.1. Icart Method . . . . . . . . . . . . . . . . . . . . 17 | |||

9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 | 6.5.2. Simplified Shallue-van de Woestijne-Ulas Method . . . 18 | |||

10. Security Considerations . . . . . . . . . . . . . . . . . . . 25 | 6.6. Mappings for Montgomery curves . . . . . . . . . . . . . 20 | |||

11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 25 | 6.6.1. Elligator 2 Method . . . . . . . . . . . . . . . . . 21 | |||

12. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 25 | 6.7. Mappings for Twisted Edwards curves . . . . . . . . . . . 23 | |||

13. Normative References . . . . . . . . . . . . . . . . . . . . 25 | 6.7.1. Rational maps from Montgomery to twisted Edwards | |||

Appendix A. Related Work . . . . . . . . . . . . . . . . . . . . 28 | curves . . . . . . . . . . . . . . . . . . . . . . . 23 | |||

A.1. Probabilistic Encoding . . . . . . . . . . . . . . . . . 28 | 6.7.2. Elligator 2 Method . . . . . . . . . . . . . . . . . 25 | |||

A.2. Naive Encoding . . . . . . . . . . . . . . . . . . . . . 29 | 6.8. Mappings for Supersingular curves . . . . . . . . . . . . 25 | |||

A.3. Deterministic Encoding . . . . . . . . . . . . . . . . . 29 | 6.8.1. Boneh-Franklin Method . . . . . . . . . . . . . . . . 25 | |||

A.4. Supersingular Curves . . . . . . . . . . . . . . . . . . 30 | 6.8.2. Elligator 2, A == 0 Method . . . . . . . . . . . . . 26 | |||

A.5. Twisted Variants . . . . . . . . . . . . . . . . . . . . 30 | 6.9. Mappings for Pairing-Friendly curves . . . . . . . . . . 27 | |||

Appendix B. Try-and-Increment Method . . . . . . . . . . . . . . 30 | 6.9.1. Shallue-van de Woestijne Method . . . . . . . . . . . 27 | |||

Appendix C. Sample Code . . . . . . . . . . . . . . . . . . . . 31 | 6.9.2. Simplified SWU for Pairing-Friendly Curves . . . . . 30 | |||

C.1. Icart Method . . . . . . . . . . . . . . . . . . . . . . 31 | 7. Clearing the cofactor . . . . . . . . . . . . . . . . . . . . 31 | |||

C.2. Shallue-Woestijne-Ulas Method . . . . . . . . . . . . . . 32 | 8. Suites for Hashing . . . . . . . . . . . . . . . . . . . . . 32 | |||

C.3. Simplified SWU Method . . . . . . . . . . . . . . . . . . 34 | 8.1. Suites for NIST P-256 . . . . . . . . . . . . . . . . . . 33 | |||

C.4. Boneh-Franklin Method . . . . . . . . . . . . . . . . . . 34 | 8.2. Suites for NIST P-384 . . . . . . . . . . . . . . . . . . 34 | |||

C.5. Fouque-Tibouchi Method . . . . . . . . . . . . . . . . . 35 | 8.3. Suites for NIST P-521 . . . . . . . . . . . . . . . . . . 34 | |||

C.6. Elligator2 Method . . . . . . . . . . . . . . . . . . . . 36 | 8.4. Suites for curve25519 and edwards25519 . . . . . . . . . 35 | |||

C.7. hash2base . . . . . . . . . . . . . . . . . . . . . . . . 37 | 8.5. Suites for curve448 and edwards448 . . . . . . . . . . . 36 | |||

C.7.1. Considerations . . . . . . . . . . . . . . . . . . . 38 | 8.6. Suites for SECP256K1 . . . . . . . . . . . . . . . . . . 37 | |||

Appendix D. Test Vectors . . . . . . . . . . . . . . . . . . . . 39 | 8.7. Suites for BLS12-381 . . . . . . . . . . . . . . . . . . 37 | |||

D.1. Elligator2 to Curve25519 . . . . . . . . . . . . . . . . 39 | 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 39 | |||

D.2. Icart to P-384 . . . . . . . . . . . . . . . . . . . . . 41 | 10. Security Considerations . . . . . . . . . . . . . . . . . . . 39 | |||

D.3. SWU to P-256 . . . . . . . . . . . . . . . . . . . . . . 44 | 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 39 | |||

D.4. Simple SWU to P-256 . . . . . . . . . . . . . . . . . . . 48 | 12. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 39 | |||

D.5. Boneh-Franklin to P-503 . . . . . . . . . . . . . . . . . 52 | 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 39 | |||

D.6. Fouque-Tibouchi to BN256 . . . . . . . . . . . . . . . . 56 | 13.1. Normative References . . . . . . . . . . . . . . . . . . 40 | |||

D.7. Sample hash2base . . . . . . . . . . . . . . . . . . . . 60 | 13.2. Informative References . . . . . . . . . . . . . . . . . 40 | |||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 61 | Appendix A. Related Work . . . . . . . . . . . . . . . . . . . . 45 | |||

Appendix B. Rational maps from twisted Edwards to Weierstrass | ||||

and Montgomery curves . . . . . . . . . . . . . . . 47 | ||||

Appendix C. Isogenous curves and corresponding maps for | ||||

BLS12-381 . . . . . . . . . . . . . . . . . . . . . 48 | ||||

C.1. 11-isogeny map for G1 . . . . . . . . . . . . . . . . . . 48 | ||||

C.2. 3-isogeny map for G2 . . . . . . . . . . . . . . . . . . 52 | ||||

Appendix D. Sample Code . . . . . . . . . . . . . . . . . . . . 53 | ||||

D.1. Interface and projective coordinate systems . . . . . . . 53 | ||||

D.2. P-256 (Simplified SWU) . . . . . . . . . . . . . . . . . 54 | ||||

D.3. curve25519 (Elligator 2) . . . . . . . . . . . . . . . . 56 | ||||

D.4. edwards25519 (Elligator 2) . . . . . . . . . . . . . . . 57 | ||||

D.5. curve448 (Elligator 2) . . . . . . . . . . . . . . . . . 57 | ||||

D.6. edwards448 (Elligator 2) . . . . . . . . . . . . . . . . 58 | ||||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 59 | ||||

1. Introduction | 1. Introduction | |||

Many cryptographic protocols require a procedure which maps arbitrary | Many cryptographic protocols require a procedure that encodes an | |||

input, e.g., passwords, to points on an elliptic curve (EC). | arbitrary input, e.g., a password, to a point on an elliptic curve. | |||

Prominent examples include Simple Password Exponential Key Exchange | This procedure is known as hashing to an elliptic curve. Prominent | |||

[Jablon96], Password Authenticated Key Exchange [BMP00], Identity- | examples of cryptosystems that hash to elliptic curves include Simple | |||

Based Encryption [BF01] and Boneh-Lynn-Shacham signatures [BLS01]. | Password Exponential Key Exchange [J96], Password Authenticated Key | |||

Exchange [BMP00], Identity-Based Encryption [BF01] and Boneh-Lynn- | ||||

Unfortunately for implementors, the precise mapping which is suitable | Shacham signatures [BLS01]. | |||

for a given scheme is not necessarily included in the description of | ||||

the protocol. Compounding this problem is the need to pick a | ||||

suitable curve for the specific protocol. | ||||

This document aims to address this lapse by providing a thorough set | Unfortunately for implementors, the precise hash function that is | |||

of recommendations across a range of implementations, and curve | suitable for a given scheme is not necessarily included in the | |||

types. We provide implementation and performance details for each | description of the protocol. Compounding this problem is the need to | |||

mechanism, along with references to the security rationale behind | pick a suitable curve for the specific protocol. | |||

each recommendation and guidance for applications not yet covered. | ||||

Each algorithm conforms to a common interface, i.e., it maps a | This document aims to bridge this gap by providing a thorough set of | |||

bitstring {0, 1}^* to a point on an elliptic curve E. For each | recommended algorithms for a range of curve types. Each algorithm | |||

variant, we describe the requirements for E to make it work. Sample | conforms to a common interface: it takes as input an arbitrary-length | |||

code for each variant is presented in the appendix. Unless otherwise | bit string and produces as output a point on an elliptic curve. We | |||

stated, all elliptic curve points are assumed to be represented as | provide implementation details for each algorithm, describe the | |||

affine coordinates, i.e., (x, y) points on a curve. | security rationale behind each recommendation, and give guidance for | |||

elliptic curves that are not explicitly covered. | ||||

1.1. Requirements | 1.1. Requirements | |||

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", | The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", | |||

"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this | "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this | |||

document are to be interpreted as described in [RFC2119]. | document are to be interpreted as described in [RFC2119]. | |||

2. Background | 2. Background | |||

Here we give a brief definition of elliptic curves, with an emphasis | 2.1. Elliptic curves | |||

on defining important parameters and their relation to encoding. | ||||

Let F be the finite field GF(p^k). We say that F is a field of | The following is a brief definition of elliptic curves, with an | |||

characteristic p. For most applications, F is a prime field, in | emphasis on important parameters and their relation to hashing to | |||

which case k=1 and we will simply write GF(p). | curves. For further reference on elliptic curves, consult | |||

[CFADLNV05] or [W08]. | ||||

Elliptic curves can be represented by equations of different standard | Let F be the finite field GF(q) of prime characteristic p. In most | |||

forms, including, but not limited to: Weierstrass, Montgomery, and | cases F is a prime field, so q = p. Otherwise, F is a field | |||

Edwards. Each of these variants correspond to a different category | extension, so q = p^m for an integer m > 1. This document assumes | |||

of curve equation. For example, the short Weierstrass equation is | that elements of field extensions are written in a primitive element | |||

"y^2 = x^3 + Ax + B". Certain encoding functions may have | or polynomial basis, i.e., as of m elements of GF(p) written in | |||

requirements on the curve form, the characteristic of the field, and | ascending order by degree. For example, if q = p^2 and the primitive | |||

the parameters, such as A and B in the previous example. | element basis is {1, i}, then the vector (a, b) corresponds to the | |||

element a + b * i. | ||||

An elliptic curve E is specified by its equation, and a finite field | An elliptic curve E is specified by an equation in two variables and | |||

F. The curve E forms a group, whose elements correspond to those who | a finite field F. An elliptic curve equation takes one of several | |||

satisfy the curve equation, with values taken from the field F. As a | standard forms, including (but not limited to) Weierstrass, | |||

group, E has order n, which is the number of points on the curve. | Montgomery, and Edwards. | |||

For security reasons, it is a strong requirement that all | ||||

cryptographic operations take place in a prime order group. However, | The curve E induces an algebraic group whose elements are those | |||

not all elliptic curves generate groups of prime order. In those | points with coordinates (x, y) satisfying the curve equation, and | |||

cases, it is allowed to work with elliptic curves of order n = qh, | where x and y are elements of F. This group has order n, meaning | |||

where q is a large prime, and h is a short number known as the | that there are n distinct points. This document uses additive | |||

cofactor. Thus, we may wish an encoding that returns points on the | notation for the elliptic curve group operation. | |||

subgroup of order q. Multiplying a point P on E by the cofactor h | ||||

guarantees that hP is a point in the subgroup of order q. | For security reasons, groups of prime order MUST be used. Elliptic | |||

curves induce subgroups of prime order. Let G be a subgroup of the | ||||

curve of prime order r, where n = h * r. In this equation, h is an | ||||

integer called the cofactor. An algorithm that takes as input an | ||||

arbitrary point on the curve E and produces as output a point in the | ||||

subgroup G of E is said to "clear the cofactor." Such algorithms are | ||||

discussed in Section 7. | ||||

Certain hash-to-curve algorithms restrict the form of the curve | ||||

equation, the characteristic of the field, and/or the parameters of | ||||

the curve. For each algorithm presented, this document lists the | ||||

relevant restrictions. | ||||

Summary of quantities: | Summary of quantities: | |||

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

| Symbol | Meaning | Relevance | | | Symbol | Meaning | Relevance | | |||

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

| p | Order of finite | Curve points need to be represented | | | F,q,p | Finite field F of | For prime fields, q = p; | | |||

| | field, F = GF(p) | in terms of p. For prime power | | | | characteristic p and #F = | otherwise, q = p^m and m>1. | | |||

| | | extension fields, we write F = | | | | q = p^m. | | | |||

| | | GF(p^k). | | | | | | | |||

| | | | | | E | Elliptic curve. | E is specified by an | | |||

| n | Number of curve | For map to E, needs to produce n | | | | | equation and a field F. | | |||

| | points, #E(F) = n | elements. | | | | | | | |||

| | | | | | n | Number of points on the | n = h * r, for h and r | | |||

| q | Order of the | If n is not prime, may need mapping | | | | elliptic curve E. | defined below. | | |||

| | largest prime | to q. | | | | | | | |||

| | subgroup of E, n | | | | G | A subgroup of the elliptic | Destination group to which | | |||

| | = qh | | | | | curve. | bit strings are encoded. | | |||

| | | | | | | | | | |||

| h | Cofactor | For mapping to subgroup, need to | | | r | Order of G. | This number MUST be prime. | | |||

| | | multiply by cofactor. | | | | | | | |||

+--------+-------------------+--------------------------------------+ | | h | Cofactor, h >= 1. | An integer satisfying n = h | | |||

| | | * r. | | ||||

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

2.1. Terminology | 2.2. Terminology | |||

In the following, we categorize the terminology for mapping | In this section, we define important terms used in the rest of this | |||

bitstrings to points on elliptic curves. | document. | |||

2.1.1. Encoding | 2.2.1. Mappings | |||

In practice, the input of a given cryptographic algorithm will be a | A mapping is a deterministic function from an element of the field F | |||

bitstring of arbitrary length, denoted {0, 1}^*. Hence, a concern for | to a point on an elliptic curve E defined over F. | |||

virtually all protocols involving elliptic curves is how to convert | ||||

this input into a curve point. The general term "encoding" refers to | ||||

the process of producing an elliptic curve point given as input a | ||||

bitstring. In some protocols, the original message may also be | ||||

recovered through a decoding procedure. An encoding may be | ||||

deterministic or probabilistic, although the latter is problematic in | ||||

potentially leaking plaintext information as a side-channel. | ||||

Suppose as the input to the encoding function we wish to use a fixed- | In general, the set of all points that a mapping can produce over all | |||

length bitstring of length L. Comparing sizes of the sets, 2^L and | possible inputs may be only a subset of the points on an elliptic | |||

n, an encoding function cannot be both deterministic and bijective. | curve (i.e., the mapping may not be surjective). In addition, a | |||

We can instead use an injective encoding from {0, 1}^L to E, with "L | mapping may output the same point for two or more distinct inputs | |||

< log2(n)- 1", which is a bijection over a subset of points in E. | (i.e., the mapping may not be injective). For example, consider a | |||

This ensures that encoded plaintext messages can be recovered. | 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 | ||||

bijective (i.e., both injective and surjective) since it is defined | ||||

to be deterministic. | ||||

In practice, encodings are commonly injective and invertible. | Mappings may also be invertible, meaning that there is an efficient | |||

Injective encodings map inputs to a subset of points on the curve. | algorithm that, for any point P output by the mapping, outputs an x | |||

Invertible encodings allow computation of input bitstrings given a | in F such that applying the mapping to x outputs P. Some of the | |||

point on the curve. | mappings given in Section 6 are invertible, but this document does | |||

not discuss inversion algorithms. | ||||

2.1.2. Serialization | 2.2.2. Encodings | |||

A related issue is the conversion of an elliptic curve point to a | Encodings are closely related to mappings. Like a mapping, an | |||

bitstring. We refer to this process as "serialization", since it is | encoding is a function that outputs a point on an elliptic curve. In | |||

typically used for compactly storing and transporting points, or for | contrast to a mapping, however, the input to an encoding is an | |||

producing canonicalized outputs. Since a deserialization algorithm | arbitrary bit string. Encodings can be deterministic or | |||

can often be used as a type of encoding algorithm, we also briefly | probabilistic. Deterministic encodings are preferred for security, | |||

document properties of these functions. | because probabilistic ones can leak information through side | |||

channels. | ||||

A straightforward serialization algorithm maps a point (x, y) on E to | This document constructs deterministic encodings by composing a hash | |||

a bitstring of length 2*log(p), given that x, y are both elements in | function H with a deterministic mapping. In particular, H takes as | |||

GF(p). However, since there are only n points in E (with n | input an arbitrary bit string and outputs an element of F. The | |||

approximately equal to p), it is possible to serialize to a bitstring | deterministic mapping takes that element as input and outputs a point | |||

of length log(n). For example, one common method is to store the | on an elliptic curve E defined over F. Since the hash function H | |||

x-coordinate and a single bit to determine whether the point is (x, | takes arbitrary bit strings as inputs, it cannot be injective: the | |||

y) or (x, -y), thus requiring log(p)+1 bits. This method reduces | set of inputs is larger than the set of outputs, so there must be | |||

storage, but adds computation, since the deserialization process must | distinct inputs that give the same output (i.e., there must be | |||

recover the y coordinate. | collisions). Thus, any encoding built from H is also not injective. | |||

2.1.3. Random Oracle | Like mappings, encodings may be invertible, meaning that there is an | |||

efficient algorithm that, for any point P output by the encoding, | ||||

outputs a bit string s such that applying the encoding to s outputs | ||||

P. The hash function used by all encodings specified in this | ||||

document (Section 5) is not invertible; thus, the encodings are also | ||||

not invertible. | ||||

It is often the case that the output of the encoding function | 2.2.3. Random oracle encodings | |||

Section 2.1.1 should be (a) distributed uniformly at random on the | ||||

elliptic curve and (b) non-invertible. That is, there is no | ||||

discernible relation existing between outputs that can be computed | ||||

based on the inputs. Moreover, given such an encoding function F | ||||

from bitstrings to points on the curve, as well as a single point y, | ||||

it is computationally intractable to produce an input x that maps to | ||||

a y via F. In practice, these requirement stem from needing a random | ||||

oracle which outputs elliptic curve points: one way to construct this | ||||

is by first taking a regular random oracle, operating entirely on | ||||

bitstrings, and applying a suitable encoding function to the output. | ||||

This motivates the term "hashing to the curve", since cryptographic | Two different types of encodings are possible: nonuniform encodings, | |||

hash functions are typically modeled as random oracles. However, | whose output distribution is not uniformly random, and random oracle | |||

this still leaves open the question of what constitutes a suitable | encodings, whose output distribution is indistinguishable from | |||

encoding method, which is a primary concern of this document. | uniformly random. Some protocols require a random oracle for | |||

security, while others can be securely instantiated with a nonuniform | ||||

encoding. When the required encoding is not clear, applications | ||||

SHOULD use a random oracle. | ||||

A random oracle onto an elliptic curve can also be instantiated using | Care is required when constructing a random oracle from a mapping | |||

direct constructions, however these tend to rely on many group | function. A simple but insecure approach is to use the output of a | |||

operations and are less efficient than hash and encode methods. | cryptographically secure hash function H as the input to the mapping. | |||

Because in general the mapping is not surjective, the output of this | ||||

construction is distinguishable from uniformly random, i.e., it does | ||||

not behave like a random oracle. | ||||

3. Algorithm Recommendations | Brier et al. [BCIMRT10] describe two generic constructions whose | |||

outputs are indistinguishable from a random oracle. Farashahi et al. | ||||

[FFSTV13] and Tibouchi and Kim [TK17] refine the analysis of one of | ||||

these constructions. That construction is described in Section 3. | ||||

In practice, two types of mappings are common: (1) Injective | 2.2.4. Serialization | |||

encodings, as can be used to construct a PRF as F(k, m) = k*H(m), and | ||||

(2) Random Oracles, as required by PAKEs [BMP00], BLS [BLS01], and | ||||

IBE [BF01]. (Some applications, such as IBE, have additional | ||||

requirements, such as a Supersingular, pairing-friendly curve.) | ||||

The following table lists recommended algorithms for different curves | A procedure related to encoding is the conversion of an elliptic | |||

and mappings. To select a suitable algorithm, choose the mapping | curve point to a bit string. This is called serialization, and is | |||

associated with the target curve. For example, Elligator2 is the | typically used for compactly storing or transmitting points. For | |||

recommended injective encoding function for Curve25519, whereas | example, [SECG1] gives a standard method for serializing points. The | |||

Simple SWU is the recommended injective encoding for P-256. | reverse operation, deserialization, converts a bit string to an | |||

Similarly, the FFSTV Random Oracle construction described in | elliptic curve point. | |||

Section 6 composed with Elligator2 should be used for Random Oracle | ||||

mappings to Curve25519. When the required mapping is not clear, | ||||

applications SHOULD use a Random Oracle. | ||||

+------------+-------------------------+----------------------------+ | Deserialization is different from encoding in that only certain | |||

| Curve | Inj. Encoding | Random Oracle | | strings (namely, those output by the serialization procedure) can be | |||

+------------+-------------------------+----------------------------+ | deserialized. In contrast, this document is concerned with encodings | |||

| P-256 | Simple SWU Section | FFSTV(SWU) Section 6 | | from arbitrary bit strings to elliptic curve points. This document | |||

| | 5.3.3 | | | does not cover serialization or deserialization. | |||

| | | | | ||||

| P-384 | Icart Section 5.3.1 | FFSTV(Icart) Section 6 | | 2.2.5. Domain separation | |||

| | | | | ||||

| Curve25519 | Elligator2 Section | FFSTV(Elligator2) Section | | Cryptographic protocols that use random oracles are often analyzed | |||

| | 5.4.1 | 6 | | under the assumption that random oracles answer only queries | |||

| | | | | generated by that protocol. In practice, this assumption does not | |||

| Curve448 | Elligator2 Section | FFSTV(Elligator2) Section | | hold if two protocols query the same random oracle. Concretely, | |||

| | 5.4.1 | 6 | | consider protocols P1 and P2 that query random oracle R: if P1 and P2 | |||

+------------+-------------------------+----------------------------+ | both query R on the same value x, the security analysis of one or | |||

both protocols may be invalidated. | ||||

A common approach to addressing this issue is called domain | ||||

separation, which allows a single random oracle to simulate multiple, | ||||

independent oracles. This is effected by ensuring that each | ||||

simulated oracle sees queries that are distinct from those seen by | ||||

all other simulated oracles. For example, to simulate two oracles R1 | ||||

and R2 given a single oracle R, one might define | ||||

R1(x) := R("R1" || x) | ||||

R2(x) := R("R2" || x) | ||||

In this example, "R1" and "R2" are called domain separation tags; | ||||

they ensure that queries to R1 and R2 cannot result in identical | ||||

queries to R. Thus, it is safe to treat R1 and R2 as independent | ||||

oracles. | ||||

3. Roadmap | ||||

This section presents a general framework for encoding bit strings to | ||||

points on an elliptic curve. To construct these encodings, we rely | ||||

on three basic functions: | ||||

o The function hash_to_base, {0, 1}^* x {0, 1, 2} -> F, hashes | ||||

arbitrary-length bit strings to elements of a finite field; its | ||||

implementation is defined in Section 5. | ||||

o The function map_to_curve, F -> E, calculates a point on the | ||||

elliptic curve E from an element of the finite field F over which | ||||

E is defined. Section 6 describes mappings for a range of curve | ||||

families. | ||||

o The function clear_cofactor, E -> G, sends any point on the curve | ||||

E to the subgroup G of E. Section 7 describes methods to perform | ||||

this operation. | ||||

We describe two high-level encoding functions (Section 2.2.2). | ||||

Although these functions have the same interface, the distributions | ||||

of their outputs are different. | ||||

o Nonuniform encoding (encode_to_curve). This function encodes bit | ||||

strings to points in G. The distribution of the output is not | ||||

uniformly random in G. | ||||

encode_to_curve(alpha) | ||||

Input: alpha, an arbitrary-length bit string. | ||||

Output: P, a point in G. | ||||

Steps: | ||||

1. u = hash_to_base(alpha, 2) | ||||

2. Q = map_to_curve(u) | ||||

3. P = clear_cofactor(Q) | ||||

4. return P | ||||

o Random oracle encoding (hash_to_curve). This function encodes bit | ||||

strings to points in G. The distribution of the output is | ||||

indistinguishable from uniformly random in G provided that | ||||

map_to_curve is "well distributed" ([FFSTV13], Def. 1). All of | ||||

the map_to_curve functions defined in Section 6 meet this | ||||

requirement. | ||||

hash_to_curve(alpha) | ||||

Input: alpha, an arbitrary-length bit string. | ||||

Output: P, a point in G. | ||||

Steps: | ||||

1. u0 = hash_to_base(alpha, 0) | ||||

2. u1 = hash_to_base(alpha, 1) | ||||

3. Q0 = map_to_curve(u0) | ||||

4. Q1 = map_to_curve(u1) | ||||

5. R = Q0 + Q1 // point addition | ||||

6. P = clear_cofactor(R) | ||||

7. return P | ||||

Instances of these functions are given in Section 8, which defines a | ||||

list of suites that specify a full set of parameters matching | ||||

elliptic curves and algorithms. | ||||

3.1. Domain separation requirements | ||||

When invoking hash_to_curve from a higher-level protocol, | ||||

implementors MUST use domain separation (Section 2.2.5) to avoid | ||||

interfering with other protocols that also use the hash_to_curve | ||||

functionality. Protocols that use encode_to_curve SHOULD use domain | ||||

separation if possible, though it is not required in this case. | ||||

Protocols that instantiate multiple, independent random oracles based | ||||

on hash_to_curve MUST enforce domain separation between those | ||||

oracles. This requirement applies both in the case of multiple | ||||

oracles to the same curve and in the case of multiple oracles to | ||||

different curves. This is because the hash_to_base primitive | ||||

(Section 5) requires domain separation to guarantee independent | ||||

outputs. | ||||

Care is required when choosing a domain separation tag. Implementors | ||||

SHOULD observe the following guidelines: | ||||

1. Tags should be prepended to the value being hashed, as in the | ||||

example in Section 2.2.5. | ||||

2. Tags should have fixed length, or should be encoded in a way that | ||||

makes the length of a given tag unambiguous. If a variable- | ||||

length tag is used, it should be prefixed with a fixed-length | ||||

field that encodes the length of the tag. | ||||

3. Tags should begin with a fixed protocol identification string. | ||||

Ideally, this identification string should be unique to the | ||||

protocol. | ||||

4. Tags should include a protocol version number. | ||||

5. For protocols that support multiple ciphersuites, tags should | ||||

include a ciphersuite identifier. | ||||

As an example, consider a fictional key exchange protocol named Quux. | ||||

A reasonable choice of tag is "QUUX-V<xx>-CS<yy>", where <xx> and | ||||

<yy> are two-digit numbers indicating the version and ciphersuite, | ||||

respectively. Alternatively, if a variable-length ciphersuite string | ||||

must be used, a reasonable choice of tag is "QUUX-V<xx>- | ||||

L<zz>-<csid>", where <csid> is the ciphersuite string, and <xx> and | ||||

<zz> are two-digit numbers indicating the version and the length of | ||||

the ciphersuite string, respectively. | ||||

As another example, consider a fictional protocol named Baz that | ||||

requires two independent random oracles, where one oracle outputs | ||||

points on the curve E1 and the other outputs points on the curve E2. | ||||

To ensure that these two random oracles are independent, each one | ||||

must be called with a distinct domain separation tag. Reasonable | ||||

choices of tags for the E1 and E2 oracles are "BAZ-V<xx>-CS<yy>-E1" | ||||

and "BAZ-V<xx>-CS<yy>-E2", respectively, where <xx> and <yy> are as | ||||

defined above. | ||||

4. Utility Functions | 4. Utility Functions | |||

Algorithms in this document make use of utility functions described | Algorithms in this document make use of utility functions described | |||

below. | below. | |||

o hash2base(x). This method is parametrized by p and H, where p is | For security reasons, all field operations, comparisons, and | |||

the prime order of the base field Fp, and H is a cryptographic | assignments MUST be implemented in constant time (i.e., execution | |||

hash function which outputs at least floor(log2(p)) + 1 bits. The | time MUST NOT depend on the values of the inputs), and without | |||

function first hashes x, converts the result to an integer, and | branching. Guidance on implementing these low-level operations in | |||

reduces modulo p to give an element of Fp. We provide a more | constant time is beyond the scope of this document. | |||

detailed algorithm in Appendix C.7. | ||||

o CMOV(a, b, c): If c = 1, return a, else return b. | o CMOV(a, b, c): If c is False, CMOV returns a, otherwise it returns | |||

b. To prevent against timing attacks, this operation must run in | ||||

constant time, without revealing the value of c. Commonly, | ||||

implementations assume that the selector c is 1 for True or 0 for | ||||

False. In this case, given a bit string C, the desired selector c | ||||

can be computed by OR-ing all bits of C together. The resulting | ||||

selector will be either 0 if all bits of C are zero, or 1 if at | ||||

least one bit of C is 1. | ||||

Common software implementations of constant-time selects assume c | o is_square(x): This function returns True whenever the value x is a | |||

= 1 or c = 0. CMOV may be implemented by computing the desired | square in the field F. Due to Euler's criterion, this function | |||

selector (0 or 1) by ORing all bits of c together. The end result | can be calculated in constant time as | |||

will be either 0 if all bits of c are zero, or 1 if at least one | ||||

bit of c is 1. | ||||

o CTEQ(a, b): Returns a == b. Inputs a and b must be the same | is_square(x) := { True, if x^((q - 1) / 2) is 0 or 1 in F; | |||

length (as bytestrings) and the comparison must be implemented in | { False, otherwise. | |||

constant time. | ||||

o Legendre(x, p): x^((p-1)/2). The Legendre symbol computes whether | o sqrt(x): The sqrt operation is a multi-valued function, i.e. there | |||

the value x is a "quadratic residue" modulo p, and takes values 1, | exist two roots of x in the field F whenever x is square. To | |||

-1, 0, for when x is a residue, non-residue, or zero, | maintain compatibility across implementations while allowing | |||

respectively. Due to Euler's criterion, this can be computed in | implementors leeway for optimizations, this document does not | |||

constant time, with respect to a fixed p, using the equation | require sqrt() to return a particular value. Instead, as | |||

x^((p-1)/2). For clarity, we will generally prefer using the | explained in Section 6.3, any higher-level function that computes | |||

formula directly, and annotate the usage with this definition. | square roots also specifies how to determine the sign of the | |||

result. | ||||

o sqrt(x, p): Computing square roots should be done in constant time | The preferred way of computing square roots is to fix a | |||

where possible. | deterministic algorithm particular to F. We give algorithms for | |||

the three most common cases immediately below; other cases are | ||||

analogous. | ||||

When p = 3 (mod 4), the square root can be computed as "sqrt(x, p) | Note that Case 3 below applies to GF(p^2) when p = 3 mod 8. | |||

:= x^(p+1)/4". This applies to P256, P384, and Curve448. | [AR13] and [S85] describe methods that work for other field | |||

extensions. Regardless of the method chosen, the sqrt function | ||||

MUST be performed in constant time. | ||||

When p = 5 (mod 8), the square root can be computed by the | s = sqrt(x) | |||

following algorithm, in which "sqrt(-1)" is a field element and | ||||

can be precomputed. This applies to Curve25519. | ||||

sqrt(x, p) := | Parameters: | |||

x^(p+3)/8 if x^(p+3)/4 == x | - F, a finite field of characteristic p and order q = p^m, m >= 1. | |||

sqrt(-1) * x^(p+3)/8 otherwise | ||||

The above two conditions hold for most practically used curves, due | Input: x, an element of F. | |||

to the simplicity of the square root function. For others, a | Output: s, an element of F such that (s^2) == x. | |||

suitable constant-time Tonelli-Shanks variant should be used as in | ||||

[Schoof85]. | ||||

5. Deterministic Encodings | ====== | |||

5.1. Interface | Case 1: q = 3 (mod 4) | |||

The generic interface for deterministic encoding functions to | Constants: | |||

elliptic curves is as follows: | 1. c1 = (q + 1) / 4 // Integer arithmetic | |||

map2curve(alpha) | Procedure: | |||

1. return x^c1 | ||||

where alpha is a message to encode on a curve. | ====== | |||

5.2. Notation | Case 2: q = 5 (mod 8) | |||

As a rough style guide for the following, we use (x, y) to be the | Constants: | |||

output coordinates of the encoding method. Indexed values are used | 1. c1 = sqrt(-1) in F, i.e., (c1^2) == -1 in F | |||

when the algorithm will choose between candidate values. For | 2. c2 = (q + 3) / 8 // Integer arithmetic | |||

example, the SWU algorithm computes three candidates (x1, y1), (x2, | Procedure: | |||

y2), (x3, y3), from which the final (x, y) output is chosen via | 1. t1 = x^c2 | |||

constant time comparison operations. | 2. e = (t1^2) == x | |||

3. s = CMOV(t1 * c1, t1, e) | ||||

3. return s | ||||

We use u, v to denote the values in Fp output from hash2base, and use | ====== | |||

as initial values in the encoding. | ||||

We use t1, t2, ..., as reusable temporary variables. For notable | Case 3: q = 9 (mod 16) | |||

variables, we will use a distinct name, for ease of debugging | ||||

purposes when correlating with test vectors. | ||||

The code presented here corresponds to the example Sage [SAGE] code | Constants: | |||

found at [github-repo]. Which is additionally used to generate | 1. c1 = sqrt(-1) in F, i.e., (c1^2) == -1 in F | |||

intermediate test vectors. The Sage code is also checked against the | 2. c2 = sqrt(c1) in F, i.e., (c2^2) == c1 in F | |||

hacspec implementation. | 3. c3 = sqrt(-c1) in F, i.e., (c3^2) == -c1 in F | |||

4. c4 = (q + 7) / 16 // Integer arithmetic | ||||

Note that each encoding requires that certain preconditions must hold | Procedure: | |||

in order to be applied. | 1. t1 = x^c4 | |||

2. t2 = c1 * t1 | ||||

3. t3 = c2 * t1 | ||||

4. t4 = c3 * t1 | ||||

5. e1 = (t2^2) == x | ||||

6. e2 = (t3^2) == x | ||||

7. t1 = CMOV(t1, t2, e1) // select t2 if (t2^2) == x | ||||

8. t2 = CMOV(t4, t3, e2) // select t3 if (t3^2) == x | ||||

9. e3 = (t2^2) == x | ||||

10. s = CMOV(t1, t2, e3) // select the sqrt from t1 and t2 | ||||

11. return s | ||||

5.3. Encodings for Weierstrass curves | o sgn0(x): This function returns either +1 or -1 indicating the | |||

"sign" of x, where sgn0(x) == -1 just when x is lexically greater | ||||

than -x. Thus, this function considers 0 to be positive. The | ||||

following procedure implements sgn0(x) in constant time. See | ||||

Section 2.1 for a discussion of representing x as a vector. | ||||

The following encodings apply to elliptic curves defined as E: y^2 = | sgn0(x) | |||

x^3+Ax+B, where 4A^3+27B^2 ≠ 0. | ||||

5.3.1. Icart Method | Parameters: | |||

- F, a finite field of characteristic p and order q = p^m, m >= 1. | ||||

The map2curve_icart(alpha) implements the Icart encoding method from | Input: x, an element of F. | |||

[Icart09]. | Output: -1 or 1 (an integer). | |||

*Preconditions* | Notation: x_i is the i^th element of the vector representation of x. | |||

A Weierstrass curve over F_{p^n}, where p>3 and p^n = 2 mod 3 (or p = | Steps: | |||

2 mod 3 and for odd n). | 1. sign = 0 | |||

2. for i in (m, m - 1, ..., 1): | ||||

3. sign_i = CMOV(1, -1, x_i > ((p - 1) / 2)) | ||||

4. sign_i = CMOV(sign_i, 0, x_i == 0) | ||||

5. sign = CMOV(sign, sign_i, sign == 0) | ||||

6. return CMOV(sign, 1, sign == 0) // regard x == 0 as positive | ||||

*Examples* | o abs(x): The absolute value of x is defined in terms of sgn0 in the | |||

natural way, namely, abs(x) := sgn0(x) * x. | ||||

o P-384 | o inv0(x): This function returns the multiplicative inverse of x in | |||

F, extended to all of F by fixing inv0(0) == 0. To implement inv0 | ||||

in constant time, compute inv0(x) := x^(q - 2). Notice on input | ||||

0, the output is 0 as required. | ||||

*Algorithm*: map2curve_icart | o I2OSP and OS2IP: These functions are used to convert an octet | |||

string to and from a non-negative integer as described in | ||||

[RFC8017]. | ||||

Input: | o a || b: denotes the concatenation of bit strings a and b. | |||

o alpha: an octet string to be hashed. | 5. Hashing to a Finite Field | |||

o A, B : the constants from the Weierstrass curve. | The hash_to_base function hashes a string msg of any length into an | |||

element of a field F. This function is parametrized by the field F | ||||

(Section 2.1) and by H, a cryptographic hash function that outputs b | ||||

bits. | ||||

Output: | 5.1. Security considerations | |||

o (x,y), a point in E. | For security, hash_to_base should be collision resistant and its | |||

output distribution should be uniform over F. To this end, | ||||

hash_to_base requires a cryptographic hash function H which satisfies | ||||

the following properties: | ||||

Operations: | 1. The number of bits output by H should be b >= 2 * k for | |||

sufficient collision resistance, where k is the target security | ||||

level in bits. (This is needed for a birthday bound of | ||||

approximately 2^(-k).) | ||||

u = hash2base(alpha) | 2. H is modeled as a random oracle, so its output must be | |||

v = ((3A - u^4) / 6u) | indistinguishable from a uniformly random bit string. | |||

x = (v^2 - B - (u^6 / 27))^(1/3) + (u^2 / 3) | ||||

y = ux + v | ||||

Output (x, y) | ||||

*Implementation* | For example, for 128-bit security, b >= 256 bits; in this case, | |||

The following procedure implements Icart's algorithm in a straight- | SHA256 would be an appropriate choice for H. | |||

line fashion. | ||||

map2curve_icart(alpha) | Ensuring that the hash_to_base output is a uniform random element of | |||

F requires care, even when H outputs a uniformly random string. For | ||||

example, if H is SHA256 and F is a field of characteristic p = 2^255 | ||||

- 19, then the result of reducing H(msg) (a 256-bit integer) modulo p | ||||

is slightly more likely to be in [0, 38] than if the value were | ||||

selected uniformly at random. In this example the bias is | ||||

negligible, but in general it can be significant. | ||||

Input: | To control bias, the input msg should be hashed to an integer | |||

comprising at least ceil(log2(p)) + k bits; reducing this integer | ||||

modulo p gives bias at most 2^-k, which is a safe choice for a | ||||

cryptosystem with k-bit security. To obtain such an integer, HKDF | ||||

[RFC5869] is used to expand the input msg to a L-byte string, where L | ||||

= ceil((ceil(log2(p)) + k) / 8); this string is then interpreted as | ||||

an integer via OS2IP [RFC8017]. For example, for p a 255-bit prime | ||||

and k = 128-bit security, L = ceil((255 + 128) / 8) = 48 bytes. | ||||

alpha - value to be hashed, an octet string | Section 3.1 discusses requirements for domain separation and | |||

recommendations for choosing domain separation tags. The | ||||

hash_to_curve function takes such a tag as a parameter, DST; this is | ||||

the recommended way of applying domain separation. As an | ||||

alternative, implementations MAY instead prepend a domain separation | ||||

tag to the input msg; in this case, DST SHOULD be the empty string. | ||||

Output: | Section 5.3 details the hash_to_base procedure. | |||

(x, y) - a point in E | Note that implementors SHOULD NOT use rejection sampling to generate | |||

a uniformly random element of F. The reason is that these procedures | ||||

are difficult to implement in constant time, and later well-meaning | ||||

"optimizations" may silently render an implementation non-constant- | ||||

time. | ||||

Precomputations: | 5.2. Performance considerations | |||

1. c1 = (2 * p) - 1 | The hash_to_base function uses HKDF-Extract to combine the input msg | |||

2. c1 = c1 / 3 // c1 = (2p-1)/3 as integer | and domain separation tag DST into a short digest, which is then | |||

3 c2 = 3^(-1) // c2 = 1/3 (mod p) | passed to HKDF-Expand [RFC5869]. For short messages, this entails at | |||

4. c3 = c2^3 // c3 = 1/27 (mod p) | most two extra invocations of H, which is a negligible overhead in | |||

the context of hashing to elliptic curves. | ||||

Steps: | A related issue is that the random oracle construction described in | |||

Section 3 requires evaluating two independent hash functions H0 and | ||||

H1 on msg. A standard way to instantiate independent hashes is to | ||||

append a counter to the value being hashed, e.g., H(msg || 0) and | ||||

H(msg || 1). If msg is long, however, this is either inefficient | ||||

(because it entails hashing msg twice) or requires non-black-box use | ||||

of H (e.g., partial evaluation). | ||||

1. u = hash2base(alpha) // {0,1}^* -> Fp | To sidestep both of these issues, hash_to_base takes a second | |||

2. u2 = u^2 // u^2 | argument, ctr, which it passes to HKDF-Expand. This means that two | |||

3. u4 = u2^2 // u^4 | invocations of hash_to_base on the same msg with different ctr values | |||

4. v = 3 * A // 3A in Fp | both start with identical invocations of HKDF-Extract. This is an | |||

5. v = v - u4 // 3A - u^4 | improvement because it allows sharing one evaluation of HKDF-Extract | |||

6. t1 = 6 * u // 6u | among multiple invocations of hash_to_base, i.e., by factoring out | |||

7. t1 = t1^(-1) // modular inverse | the common computation. | |||

8. v = v * t1 // (3A - u^4)/(6u) | ||||

9. x1 = v^2 // v^2 | ||||

10. x1 = x - B // v^2 - B | ||||

11. u6 = u4 * c3 // u^4 / 27 | ||||

12. u6 = u6 * u2 // u^6 / 27 | ||||

13. x1 = x1 - u6 // v^2 - B - u^6/27 | ||||

14. x1 = x^c1 // (v^2 - B - u^6/27) ^ (1/3) | ||||

15. t1 = u2 * c2 // u^2 / 3 | ||||

16. x = x + t1 // (v^2 - B - u^6/27) ^ (1/3) + (u^2 / 3) | ||||

17. y = u * x // ux | ||||

18. y = y + v // ux + v | ||||

19. Output (x, y) | ||||

5.3.2. Shallue-Woestijne-Ulas Method | 5.3. Implementation | |||

The map2curve_swu(alpha) implements the Shallue-Woestijne-Ulas (SWU) | The following procedure implements hash_to_base. | |||

method by Ulas [SWU07], which is based on Shallue and Woestijne | ||||

[SW06] method. | ||||

*Preconditions* | hash_to_base(msg, ctr) | |||

This algorithm works for any Weierstrass curve over F_{p^n} such that | Parameters: | |||

A≠0 and B≠0. | - DST, a domain separation tag (see discussion above). | |||

- H, a cryptographic hash function. | ||||

- F, a finite field of characteristic p and order q = p^m. | ||||

- L = ceil((ceil(log2(p)) + k) / 8), where k is the security | ||||

parameter of the cryptosystem (e.g., k = 128). | ||||

- HKDF-Extract and HKDF-Expand are as defined in RFC5869, | ||||

instantiated with the hash function H. | ||||

*Examples* | Inputs: | |||

- msg is the message to hash. | ||||

- ctr is 0, 1, or 2. | ||||

This is used to efficiently create independent | ||||

instances of hash_to_base (see discussion above). | ||||

o P-256 | Output: | |||

- u, an element in F. | ||||

o P-384 | Steps: | |||

1. m' = HKDF-Extract(DST, msg) | ||||

2. for i in (1, ..., m): | ||||

3. info = "H2C" || I2OSP(ctr, 1) || I2OSP(i, 1) | ||||

4. t = HKDF-Expand(m', info, L) | ||||

5. e_i = OS2IP(t) mod p | ||||

6. return u = (e_1, ..., e_m) | ||||

o P-521 | 6. Deterministic Mappings | |||

*Algorithm*: map2curve_swu | The mappings in this section are suitable for constructing either | |||

nonuniform or random oracle encodings using the constructions of | ||||

Section 3. | ||||

Input: | 6.1. Interface | |||

o alpha: an octet string to be hashed. | The generic interface shared by all mappings in this section is as | |||

follows: | ||||

o A, B : the constants from the Weierstrass curve. | (x, y) = map_to_curve(u) | |||

Output: | The input u and outputs x and y are elements of the field F. The | |||

coordinates (x, y) specify a point on an elliptic curve defined over | ||||

F. Note that the point (x, y) is not a uniformly random point. If | ||||

uniformity is required for security, the random oracle construction | ||||

of Section 3 MUST be used instead. | ||||

o (x,y), a point in E. | 6.2. Notation | |||

Operations: | As a rough style guide the following convention is used: | |||

1. u = hash2base(alpha || 0x00) | o All arithmetic operations are performed over a field F, unless | |||

2. v = hash2base(alpha || 0x01) | explicitly stated otherwise. | |||

3. x1 = v | ||||

4. x2 = (-B / A)(1 + 1 / (u^4 * g(v)^2 + u^2 * g(v))) | ||||

5. x3 = u^2 * g(v)^2 * g(x2) | ||||

6. If g(x1) is square, output (x1, sqrt(g(x1))) | ||||

7. If g(x2) is square, output (x2, sqrt(g(x2))) | ||||

8. Output (x3, sqrt(g(x3))) | ||||

The algorithm relies on the following equality: | o u: the input to the mapping function. This is an element of F | |||

produced by the hash_to_base function. | ||||

u^3 * g(v)^2 * g(x2) = g(x1) * g(x2) * g(x3) | o (x, y): are the affine coordinates of the point output by the | |||

mapping. Indexed values are used when the algorithm calculates | ||||

some candidate values. | ||||

The algorithm computes three candidate points, constructed such that | o t1, t2, ...: are reusable temporary variables. For notable | |||

at least one of them lies on the curve. | variables, distinct names are used easing the debugging process | |||

when correlating with test vectors. | ||||

*Implementation* | o c1, c2, ...: are constant values, which can be computed in | |||

advance. | ||||

The following procedure implements SWU's algorithm in a straight-line | 6.3. Sign of the resulting point | |||

fashion. | ||||

map2curve_swu(alpha) | In general, elliptic curves have equations of the form y^2 = g(x). | |||

Most of 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 roots when g(x) != 0, this results in an ambiguity | ||||

regarding the sign of y. | ||||

Input: | To resolve this ambiguity, the mappings in this section specify the | |||

sign of the y-coordinate in terms of the input to the mapping | ||||

function. Two main reasons support this approach. First, this | ||||

covers elliptic curves over any field in a uniform way, and second, | ||||

it gives implementors leeway to optimize their square-root | ||||

implementations. | ||||

alpha - value to be hashed, an octet string | 6.4. Exceptional cases | |||

Output: | Mappings may have have exceptional cases, i.e., inputs u on which the | |||

mapping is undefined. These cases must be handled carefully, | ||||

especially for constant-time implementations. | ||||

(x, y) - a point in E | For each mapping in this section, we discuss the exceptional cases | |||

and show how to handle them in constant time. Note that all | ||||

implementations SHOULD use inv0 (Section 4) to compute multiplicative | ||||

inverses, to avoid exceptional cases that result from attempting to | ||||

compute the inverse of 0. | ||||

Precomputations: | 6.5. Mappings for Weierstrass curves | |||

1. c1 = -B / A mod p // Field arithmetic | The following mappings apply to elliptic curves defined by the | |||

2. c2 = (p - 1)/2 // Integer arithmetic | equation E: y^2 = g(x) = x^3 + A * x + B, where 4 * A^3 + 27 * B^2 != | |||

0. | ||||

Steps: | 6.5.1. Icart Method | |||

1. u = hash2base(alpha || 0x00) // {0,1}^* -> Fp | The function map_to_curve_icart(u) implements the Icart method from | |||

2. v = hash2base(alpha || 0x01) // {0,1}^* -> Fp | [Icart09]. | |||

3. x1 = v // x1 = v | ||||

4. gv = v^3 | ||||

5. gv = gv + (A * v) | ||||

6. gv = gv + B // gv = g(v) | ||||

7. gx1 = gv // gx1 = g(x1) | ||||

8. u2 = u^2 | ||||

9. t1 = u2 * gv // t1 = u^2 * g(v) | ||||

10. t2 = t1^2 | ||||

11. t2 = t2 + t1 | ||||

12. t2 = t2^(-1) // t2 = 1/(u^4*g(v)^2 + u^2*g(v)) | ||||

13. n1 = 1 + t2 | ||||

14. x2 = c1 * n1 // x2 = -B/A * (1 + 1/(t1^2 + t1)) | ||||

15. gx2 = x2^3 | ||||

16. t2 = A * x2 | ||||

17. gx2 = gx2 + t2 | ||||

18. gx2 = gx2 + B // gx2 = g(x2) | ||||

19. x3 = x2 * t1 // x3 = x2 * u^2 * g(v) | ||||

20. gx3 = x3^3 | ||||

21. gx3 = gx3 + (A * x3) | ||||

22. gx3 = gx3 + B // gx3 = g(X3(t, u)) | ||||

23. l1 = gx1^c2 // Legendre(gx1) | ||||

24. l2 = gx2^c2 // Legendre(gx2) | ||||

25. x = CMOV(x2, x3, l2) // If l2 = 1, choose x2, else choose x3 | ||||

26. x = CMOV(x1, x, l1) // If l1 = 1, choose x1, else choose x | ||||

27. gx = CMOV(gx2, gx3, l2) // If l2 = 1, choose gx2, else choose gx3 | ||||

28. gx = CMOV(gx1, gx, l1) // If l1 = 1, choose gx1, else choose gx | ||||

29. y = sqrt(gx) | ||||

30. Output (x, y) | ||||

5.3.3. Simplified SWU Method | ||||

The map2curve_simple_swu(alpha) implements a simplified version of | Preconditions: An elliptic curve over F, such that p > 3 and q = p^m | |||

Shallue-Woestijne-Ulas algorithm given by Brier et al. [SimpleSWU]. | = 2 (mod 3), or p = 2 (mod 3) and odd m. | |||

*Preconditions* | Constants: A and B, the parameters of the Weierstrass curve. | |||

This algorithm works for any Weierstrass curve over F_{p^n} such that | Sign of y: this mapping does not compute a square root, so there is | |||

A≠0, B≠0, and p=3 mod 4. | no ambiguity regarding the sign of y. | |||

*Examples* | Exceptions: The only exceptional case is u == 0. Implementations | |||

MUST detect this case by testing whether u == 0 and setting u = 1 if | ||||

so. | ||||

o P-256 | Operations: | |||

o P-384 | 1. If u == 0, set u = 1 | |||

2. v = (3 * A - u^4) / (6 * u) | ||||

3. w = (2 * p - 1) / 3 // Integer arithmetic | ||||

4. x = (v^2 - B - (u^6 / 27))^w + (u^2 / 3) | ||||

5. y = u * x + v | ||||

6. return (x, y) | ||||

o P-521 | 6.5.1.1. Implementation | |||

*Algorithm*: map2curve_simple_swu | The following procedure implements Icart's algorithm in a straight- | |||

line fashion. | ||||

Input: | map_to_curve_icart(u) | |||

Input: u, an element of F. | ||||

Output: (x, y), a point on E. | ||||

o alpha: an octet string to be hashed. | Constants: | |||

1. c1 = (2 * p - 1) / 3 // Integer arithmetic | ||||

2. c2 = 1 / 3 | ||||

3. c3 = c2^3 | ||||

4. c4 = 3 * A | ||||

o A, B : the constants from the Weierstrass curve. | Steps: | |||

1. e = u == 0 | ||||

2. u = CMOV(u, 1, e) // handle exceptional case u == 0 | ||||

3. u2 = u^2 // u^2 | ||||

4. u4 = u2^2 // u^4 | ||||

5. v = c4 - u4 // 3 * A - u^4 | ||||

6. t1 = 6 * u // 6 * u | ||||

7. t1 = inv0(t1) // 1 / (6 * u) | ||||

8. v = v * t1 // v = (3 * A - u^4) / (6 * u) | ||||

9. x = v^2 // v^2 | ||||

10. x = x - B // v^2 - B | ||||

11. u6 = u4 * c3 // u^4 / 27 | ||||

12. u6 = u6 * u2 // u^6 / 27 | ||||

13. x = x - u6 // v^2 - B - u^6 / 27 | ||||

14. x = x^c1 // (v^2 - B - u^6 / 27)^(1 / 3) | ||||

15. t1 = u2 * c2 // u^2 / 3 | ||||

16. x = x + t1 // x = (v^2 - B - u^6 / 27)^(1 / 3) + (u^2 / 3) | ||||

17. y = u * x // u * x | ||||

18. y = y + v // y = u * x + v | ||||

19. return (x, y) | ||||

Output: | 6.5.2. Simplified Shallue-van de Woestijne-Ulas Method | |||

o (x,y), a point in E. | The function map_to_curve_simple_swu(u) implements a simplification | |||

of the Shallue-van de Woestijne-Ulas mapping [U07] described by Brier | ||||

et al. [BCIMRT10], which they call the "simplified SWU" map. Wahby | ||||

and Boneh [WB19] generalize this mapping to curves over fields of odd | ||||

characteristic p > 3. | ||||

Operations: | Preconditions: A Weierstrass curve over F such that A != 0 and B != | |||

0. | ||||

1. Define g(x) = x^3 + Ax + B | Constants: | |||

2. u = hash2base(alpha) | ||||

3. x1 = -B/A * (1 + (1 / (u^4 - u^2))) | ||||

4. x2 = -u^2 * x1 | ||||

5. If g(x1) is square, output (x1, sqrt(g(x1))) | ||||

6. Output (x2, sqrt(g(x2))) | ||||

*Implementation* | o A and B, the parameters of the Weierstrass curve. | |||

The following procedure implements the Simple SWU's algorithm in a | o Z, the unique element of F meeting all of the following criteria: | |||

straight-line fashion. | ||||

map2curve_simple_swu(alpha) | 1. Z is non-square in F, | |||

Input: | 2. g(B / (Z * A)) is square in F, | |||

alpha - value to be encoded, an octet string | 3. there is no other Z' meeting criteria (1) and (2) for which | |||

abs(Z') < abs(Z) (Section 4), and | ||||

Output: | 4. if Z and -Z both meet the above criteria, Z is the element | |||

such that sgn0(Z) == 1. | ||||

(x, y) - a point in E | Sign of y: Inputs u and -u give the same x-coordinate. Thus, we set | |||

sgn0(y) == sgn0(u). | ||||

Precomputations: | 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 | ||||

depending on Z. Implementations must detect this case and set x1 = B | ||||

/ (Z * A), which guarantees that g(x1) is square by the condition on | ||||

Z given above. | ||||

1. c1 = -B / A mod p // Field arithmetic | Operations: | |||

2. c2 = (p - 1)/2 // Integer arithmetic | ||||

1. t1 = inv0(Z^2 * u^4 + Z * u^2) | ||||

2. x1 = (-B / A) * (1 + t1) | ||||

3. If t1 == 0, set x1 = B / (Z * A) | ||||

4. gx1 = x1^3 + A * x1 + B | ||||

5. x2 = Z * u^2 * x1 | ||||

6. gx2 = x2^3 + A * x2 + B | ||||

7. If is_square(gx1), set x = x1 and y = sqrt(gx1) | ||||

8. Else set x = x2 and y = sqrt(gx2) | ||||

9. If sgn0(u) != sgn0(y), set y = -y | ||||

10. return (x, y) | ||||

6.5.2.1. Implementation | ||||

The following procedure implements the simplified SWU mapping in a | ||||

straight-line fashion. Appendix D gives an optimized straight-line | ||||

procedure for P-256 [FIPS186-4]. For discussion of how to generalize | ||||

to q = 1 (mod 4), see [WB19] (Section 4) or the example code found at | ||||

[hash2curve-repo]. | ||||

map_to_curve_simple_swu(u) | ||||

Input: u, an element of F. | ||||

Output: (x, y), a point on E. | ||||

Constants: | ||||

1. c1 = -B / A | ||||

2. c2 = -1 / Z | ||||

Steps: | Steps: | |||

1. t1 = Z * u^2 | ||||

2. t2 = t1^2 | ||||

3. x1 = t1 + t2 | ||||

4. x1 = inv0(x1) | ||||

5. e1 = x1 == 0 | ||||

6. x1 = x1 + 1 | ||||

7. x1 = CMOV(x1, c2, e1) // if (t1 + t2) == 0, set x1 = -1 / Z | ||||

8. x1 = x1 * c1 // x1 = (-B / A) * (1 + (1 / (Z^2 * u^4 + Z * u^2))) | ||||

9. gx1 = x1^2 | ||||

10. gx1 = gx1 + A | ||||

11. gx1 = gx1 * x1 | ||||

12. gx1 = gx1 + B // gx1 = g(x1) = x1^3 + A * x1 + B | ||||

13. x2 = t1 * x1 // x2 = Z * u^2 * x1 | ||||

14. t2 = t1 * t2 | ||||

15. gx2 = gx1 * t2 // gx2 = (Z * u^2)^3 * gx1 | ||||

16. e2 = is_square(gx1) | ||||

17. x = CMOV(x2, x1, e2) // If is_square(gx1), x = x1, else x = x2 | ||||

18. y2 = CMOV(gx2, gx1, e2) // If is_square(gx1), y2 = gx1, else y2 = gx2 | ||||

19. y = sqrt(y2) | ||||

20. e3 = sgn0(u) == sgn0(y) // fix sign of y | ||||

21. y = CMOV(-y, y, e3) | ||||

22. return (x, y) | ||||

1. u = hash2base(alpha) // {0,1}^* -> Fp | 6.6. Mappings for Montgomery curves | |||

2. u2 = u^2 | ||||

3. u2 = -u2 // u2 = -u^2 | ||||

4. u4 = u2^2 | ||||

5. t1 = u4 + u2 | ||||

6. t1 = t1^(-1) | ||||

7. n1 = 1 + t2 // n1 = 1 + (1 / (u^4 - u^2)) | ||||

8. x1 = c1 * n1 // x1 = -B/A * (1 + (1 / (u^4 - u^2))) | ||||

9. gx1 = x1 ^ 3 | ||||

10. t1 = A * x1 | ||||

11. gx1 = gx1 + t1 | ||||

12. gx1 = gx1 + B // gx1 = x1^3 + Ax1 + B = g(x1) | ||||

13. x2 = u2 * x1 // x2 = -u^2 * x1 | ||||

14. gx2 = x2^3 | ||||

15. t1 = A * x2 | ||||

16. gx2 = gx2 + 12 | ||||

17. gx2 = gx2 + B // gx2 = x2^3 + Ax2 + B = g(x2) | ||||

18. e = gx1^c2 | ||||

19. x = CMOV(x1, x2, l1) // If l1 = 1, choose x1, else choose x2 | ||||

20. gx = CMOV(gx1, gx2, l1) // If l1 = 1, choose gx1, else choose gx2 | ||||

21. y = sqrt(gx) | ||||

22. Output (x, y) | ||||

5.3.4. Boneh-Franklin Method | The mapping defined in Section 6.6.1 implements Elligator 2 [BHKL13] | |||

for curves defined by the Weierstrass equation y^2 = x^3 + A * x^2 + | ||||

B * x, where A * B * (A^2 - 4 * B) != 0 and A^2 - 4 * B is non-square | ||||

in F. | ||||

The map2curve_bf(alpha) implements the Boneh-Franklin method [BF01] | Such a Weierstrass curve is related to the Montgomery curve B' * y'^2 | |||

which covers the case of supersingular curves "E: y^2=x^3+B". This | = x'^3 + A' * x'^2 + x' by the following change of variables: | |||

method does not guarantee that the resulting a point be in a specific | ||||

subgroup of the curve. To do that, a scalar multiplication by a | ||||

cofactor is required. | ||||

*Preconditions* | o A = A' / B' | |||

This algorithm works for any Weierstrass curve over "F_q" such that | o B = 1 / B'^2 | |||

"A=0" and "q=2 mod 3". | ||||

*Examples* | o x = x' / B' | |||

o "y^2 = x^3 + 1" | o y = y' / B' | |||

*Algorithm*: map2curve_bf | The Elligator 2 mapping given below returns a point (x, y) on the | |||

Weierstrass curve defined above. This point can be converted to a | ||||

point (x', y') on the original Montgomery curve by computing | ||||

Input: | o x' = B' * x | |||

o "alpha": an octet string to be hashed. | o y' = B' * y | |||

o "B": the constant from the Weierstrass curve. | Note that when B and B' are equal to 1, the above two curve equations | |||

are identical and no conversion is necessary. This is the case, for | ||||

example, for Curve25519 and Curve448 [RFC7748]. | ||||

Output: | 6.6.1. Elligator 2 Method | |||

o "(x, y)": a point in E. | Preconditions: A Weierstrass curve y^2 = x^3 + A * x^2 + B * x where | |||

A != 0, B != 0, and A^2 - 4 * B is non-zero and non-square in F. | ||||

Constants: | ||||

o A and B, the parameters of the elliptic curve. | ||||

o Z, the unique element of F meeting all of the following criteria: | ||||

1. Z is non-square in F, | ||||

2. there is no other non-square Z' for which abs(Z') < abs(Z) | ||||

(Section 4), and | ||||

3. if Z and -Z both met the above criteria, Z is the element such | ||||

that sgn0(Z) == 1. | ||||

Sign of y: Inputs u and -u give the same x-coordinate. Thus, we set | ||||

sgn0(y) == sgn0(u). | ||||

Exceptions: The exceptional case is Z * u^2 == -1, i.e., 1 + Z * u^2 | ||||

== 0. Implementations must detect this case and set x1 = -A. Note | ||||

that this can only happen when q = 3 (mod 4). | ||||

Operations: | Operations: | |||

1. u = hash2base(alpha) | 1. x1 = -A * inv0(1 + Z * u^2) | |||

2. x = (u^2 - B)^((2 * q - 1) / 3) | 2. If x1 == 0, set x1 = -A. | |||

3. Output (x, u) | 3. gx1 = x1^3 + A * x1^2 + B * x1 | |||

4. x2 = -x1 - A | ||||

5. gx2 = x2^3 + A * x2^2 + B * x2 | ||||

6. If is_square(gx1), set x = x1 and y = sqrt(gx1) | ||||

7. Else if is_square(gx2), set x = x2 and y = sqrt(gx2) | ||||

8. If sgn0(u) != sgn0(y), set y = -y | ||||

9. return (x, y) | ||||

*Implementation* | 6.6.1.1. Implementation | |||

The following procedure implements the Boneh-Franklin's algorithm in | The following procedure implements Elligator 2 in a straight-line | |||

a straight-line fashion. | fashion. Appendix D gives optimized straight-line procedures for | |||

curve25519 and curve448 [RFC7748]. | ||||

map2curve_bf(alpha) | map_to_curve_elligator2(u) | |||

Input: u, an element of F. | ||||

Output: (x, y), a point on E. | ||||

Input: | Steps: | |||

1. t1 = u^2 | ||||

2. t1 = Z * t1 // Z * u^2 | ||||

3. x1 = t1 + 1 | ||||

4. x1 = inv0(x1) | ||||

5. e1 = x1 == 0 | ||||

6. x1 = CMOV(x1, 1, e1) // if x1 == 0, set x1 = 1 | ||||

7. x1 = -A * x1 // x1 = -A / (1 + Z * u^2) | ||||

8. gx1 = x1 + A | ||||

9. gx1 = gx1 * x1 | ||||

10. gx1 = gx1 + B | ||||

11. gx1 = gx1 * x1 // gx1 = x1^3 + A * x1^2 + B * x1 | ||||

12. x2 = -x1 - A | ||||

13. gx2 = t1 * gx1 | ||||

14. e2 = is_square(gx1) | ||||

15. x = CMOV(x2, x1, e2) // If is_square(gx1), x = x1, else x = x2 | ||||

16. y2 = CMOV(gx2, gx1, e2) // If is_square(gx1), y2 = gx1, else y2 = gx2 | ||||

17. y = sqrt(y2) | ||||

18. e3 = sgn0(u) == sgn0(y) // fix sign of y | ||||

19. y = CMOV(-y, y, e3) | ||||

20. return (x, y) | ||||

6.7. Mappings for Twisted Edwards curves | ||||

alpha: an octet string to be hashed. | Twisted Edwards curves (a class of curves that includes Edwards | |||

B : the constant from the Weierstrass curve. | curves) are closely related to Montgomery curves (Section 6.6): every | |||

twisted Edwards curve is birationally equivalent to a Montgomery | ||||

curve ([BBJLP08], Theorem 3.2). This equivalence yields an efficient | ||||

way of hashing to a twisted Edwards curve: first, hash to the | ||||

equivalent Montgomery curve, then transform the result into a point | ||||

on the twisted Edwards curve via a rational map. This method of | ||||

hashing to a twisted Edwards curve thus requires identifying a | ||||

corresponding Montgomery curve and rational map. We describe how to | ||||

identify such a curve and map immediately below. | ||||

Output: | 6.7.1. Rational maps from Montgomery to twisted Edwards curves | |||

(x, y): a point in E | There are two ways to identify the correct Montgomery curve and | |||

rational map for use when hashing to a given twisted Edwards curve. | ||||

Precomputations: | When hashing to a standardized twisted Edwards curve for which a | |||

corresponding Montgomery form and rational map are also standardized, | ||||

the standard Montgomery form and rational map MUST be used to ensure | ||||

compatibility with existing software. Two such standardized curves | ||||

are the edwards25519 and edwards448 curves, which correspond to the | ||||

Montgomery curves curve25519 and curve448, respectively. For both of | ||||

these curves, [RFC7748] lists both the Montgomery and twisted Edwards | ||||

forms and gives the corresponding rational maps. | ||||

1. c = (2 * q - 1) / 3 // Integer arithmetic | The rational map for edwards25519 ([RFC7748], Section 4.1) uses the | |||

constant sqrt_neg_486664 = sqrt(-486664) mod 2^255 - 19. To ensure | ||||

compatibility, this constant MUST be chosen such that | ||||

sgn0(sqrt_neg_486664) == 1. Analogous ambiguities in other | ||||

standardized rational maps MUST be resolved in the same way: for any | ||||

constant k whose sign is ambiguous, k MUST be chosen such that | ||||

sgn0(k) == 1. | ||||

Steps: | The 4-isogeny map from curve448 to edwards448 ([RFC7748], | |||

Section 4.2) is unambiguous with respect to sign. | ||||

1. u = hash2base(alpha) // {0,1}^* -> F_q | When defining new twisted Edwards curves, a Montgomery equivalent and | |||

2. t0 = u^2 // t0 = u^2 | rational map SHOULD be specified, and the sign of the rational map | |||

3. t1 = t0 - B // t1 = u^2 - B | SHOULD be stated unambiguously. | |||

4. x = t1^c // x = (u^2 - B)^((2 * q - 1) / 3) | ||||

5. Output (x, u) | ||||

5.3.5. Fouque-Tibouchi Method | When hashing to a twisted Edwards curve that does not have a | |||

standardized Montgomery form or rational map, the following procedure | ||||

MUST be used to derive them. For a twisted Edwards curve given by a | ||||

* x^2 + y^2 = 1 + d * x^2 * y^2, first compute A and B, the | ||||

parameters of the equivalent curve given by y'^2 = x'^3 + A * x'^2 + | ||||

B * x', as follows: | ||||

The map2curve_ft(alpha) implements the Fouque-Tibouchi's method | o A = (a + d) / 2 | |||

[FT12] (Sec. 3, Def. 2) which covers the case of pairing-friendly | ||||

curves "E : y^2 = x^3 + B". Note that for pairing curves the | ||||

destination group is usually a subgroup of the curve, hence, a scalar | ||||

multiplication by the cofactor will be required to send the point to | ||||

the desired subgroup. | ||||

*Preconditions* | o B = (a - d)^2 / 16 | |||

This algorithm works for any Weierstrass curve over "F_q" such that | Note that the above curve is given in the Weierstrass form required | |||

"q=7 mod 12", "A=0", and "1+B" is a non-zero square in the field. | by the Elligator 2 mapping of Section 6.6.1. The rational map from | |||

This covers the case "q=1 mod 3" not handled by Boneh-Franklin's | the point (x', y') on this Weierstrass curve to the point (x, y) on | |||

method. | the twisted Edwards curve is given by | |||

*Examples* | o x = x' / y' | |||

o SECP256K1 curve [SEC2] | o y = (B' * x' - 1) / (B' * x' + 1), where B' = 1 / sqrt(B) = 4 / (a | |||

- d) | ||||

o BN curves [BN05] | For completeness, we give the inverse map in Appendix B. Note that | |||

the inverse map is not used when hashing to a twisted Edwards curve. | ||||

o KSS curves [KSS08] | Rational maps may be undefined, for example, when the denominator of | |||

one of the rational functions is zero. For example, in the map | ||||

described above, the exceptional cases are y' == 0 or B' * x' == -1. | ||||

Implementations MUST detect exceptional cases and return the value | ||||

(x, y) = (0, 1), which is a valid point on all twisted Edwards curves | ||||

given by the equation above. | ||||

o BLS curves [BLS01] | The following straight-line implementation of the above rational map | |||

*Algorithm*: map2curve_ft | handles the exceptional cases. Implementations of other rational | |||

maps (e.g., the ones give in [RFC7748]) are analogous. | ||||

Input: | rational_map(x', y') | |||

Input: (x', y'), a point on the curve y'^2 = x'^3 + A * x'^2 + B * x'. | ||||

Output: (x, y), a point on the equivalent twisted Edwards curve. | ||||

o "alpha": an octet string to be hashed. | 1. t1 = y' * B' | |||

2. t2 = x' + 1 | ||||

3. t3 = t1 * t2 | ||||

4. t3 = inv0(t3) | ||||

5. x = t2 * t3 | ||||

6. x = x * x' | ||||

7. y = x' - 1 | ||||

8. y = y * t3 | ||||

9. y = y * t1 | ||||

10. e = y == 0 | ||||

11. y = CMOV(y, 1, e) | ||||

12. return (x, y) | ||||

o "B": the constant from the Weierstrass curve. | 6.7.2. Elligator 2 Method | |||

o "s": a constant equal to sqrt(-3) in the field. | Preconditions: A twisted Edwards curve E and an equivalent curve M | |||

meeting the requirements in Section 6.7.1. | ||||

Output: | Helper functions: | |||

o (x, y): a point in E. | o map_to_curve_elligator2 is the mapping of Section 6.6.1 to the | |||

curve M. | ||||

o rational_map is a function that takes a point (x', y') on M and | ||||

returns a point (x, y) on E, as defined in Section 6.7.1. | ||||

Sign of y: for this map, the sign is determined by | ||||

map_to_curve_elligator2. No further sign adjustments are required. | ||||

Exceptions: The exceptions for the Elligator 2 mapping are as given | ||||

in Section 6.6.1. The exceptions for the rational map are as given | ||||

in Section 6.7.1. No other exceptions are possible. | ||||

The following procedure implements the Elligator 2 mapping for a | ||||

twisted Edwards curve. | ||||

map_to_curve_elligator2_edwards(u) | ||||

Input: u, an element of F. | ||||

Output: (x, y), a point on E. | ||||

1. (x', y') = map_to_curve_elligator2(u) // (x', y') is on M | ||||

2. (x, y) = rational_map(x', y') // (x, y) is on E | ||||

3. return (x, y) | ||||

6.8. Mappings for Supersingular curves | ||||

6.8.1. Boneh-Franklin Method | ||||

The function map_to_curve_bf(u) implements the Boneh-Franklin method | ||||

[BF01] which covers the supersingular curves defined by y^2 = x^3 + B | ||||

over a field F such that q = 2 (mod 3). | ||||

Preconditions: A supersingular curve over F such that q = 2 (mod 3). | ||||

Constants: B, the parameter of the supersingular curve. | ||||

Sign of y: determined by sign of u. No adjustments are necessary. | ||||

Exceptions: none. | ||||

Operations: | Operations: | |||

1. t = hash2base(alpha) | 1. w = (2 * q - 1) / 3 // Integer arithmetic | |||

2. w = (s * t)/(1 + B + t^2) | 2. x = (u^2 - B)^w | |||

3. x1 = ((-1 + s) / 2) - t * w | 3. y = u | |||

4. x2 = -1 - x1 | 4. return (x, y) | |||

5. x3 = 1 + (1 / w^2) | ||||

6. e = Legendre(t) | ||||

7. If x1^3 + B is square, output (x1, e * sqrt(x1^3 + B) ) | ||||

8. If x2^3 + B is square, output (x2, e * sqrt(x2^3 + B) ) | ||||

9. Output (x3, e * sqrt(x3^3 + B)) | ||||

*Implementation* | 6.8.1.1. Implementation | |||

The following procedure implements the Fouque-Tibouchi's algorithm in | The following procedure implements the Boneh-Franklin's algorithm in | |||

a straight-line fashion. | a straight-line fashion. | |||

map2curve_ft(alpha) | map_to_curve_bf(u) | |||

Input: u, an element of F. | ||||

Output: (x, y), a point on E. | ||||

Input: | Constants: | |||

1. c1 = (2 * q - 1) / 3 // Integer arithmetic | ||||

alpha: an octet string to be encoded | Steps: | |||

B : the constant of the curve | 1. t1 = u^2 | |||

2. t1 = t1 - B | ||||

3. x = t1^c1 // x = (u^2 - B)^((2 * q - 1) / 3) | ||||

4. y = u | ||||

5. return (x, y) | ||||

Output: | 6.8.2. Elligator 2, A == 0 Method | |||

(x, y): - a point in E | The function map_to_curve_ell2A0(u) implements an adaptation of | |||

Elligator 2 [BLMP19] targeting curves given by y^2 = x^3 + B * x over | ||||

F such that q = 3 (mod 4). | ||||

Precomputations: | Preconditions: An elliptic curve over F such that q = 3 (mod 4). | |||

1. c1 = sqrt(-3) // Field arithmetic | Constants: B, the parameter of the elliptic curve. | |||

2. c2 = (-1 + c1) / 2 // Field arithmetic | ||||

Steps: | Sign of y: Inputs u and -u give the same x-coordinate. Thus, we set | |||

sgn0(y) == sgn0(u). | ||||

1. t = hash2base(alpha) // {0,1}^* -> Fp | Exceptions: none. | |||

2. k = t^2 // t^2 | ||||

3. k = k + B + 1 // t^2 + B + 1 | ||||

4. k = 1 / k // 1 / (t^2 + B + 1) | ||||

5. k = k * t // t / (t^2 + B + 1) | ||||

6. k = k * c1 // sqrt(-3) * t / (t^2 + B + 1) | ||||

7. x1 = c2 - t * k // (-1 + sqrt(-3)) / 2 - sqrt(-3) * t^2 / (t^2 + B + 1) | ||||

8. x2 = -1 - x1 | ||||

9. r = k^2 | ||||

10. r = 1 / r | ||||

11. x3 = 1 + r | ||||

12. fx1 = x1^3 + B | ||||

12. fx2 = x2^3 + B | ||||

12. s1 = Legendre(fx1) | ||||

13. s2 = Legendre(fx2) | ||||

14. x = x3 | ||||

15. x = CMOV(x2 ,x, s2 > 0) // if s2=1, then x is set to x2 | ||||

16. x = CMOV(x1, x, s1 > 0) // if s1=1, then x is set to x1 | ||||

17. y = x^3 + B | ||||

18. t2 = Legendre(t) | ||||

19. y = t2 * sqrt(y) // TODO: determine which root to choose | ||||

20. Output (x, y) | ||||

Additionally, "map2curve_ft(alpha)" can return the point "(c2, sqrt(1 | Operations: | |||

+ B))" when "u=0". | ||||

5.4. Encodings for Montgomery curves | 1. x1 = u | |||

2. gx1 = x1^3 + B * x1 | ||||

3. x2 = -x1 | ||||

4. gx2 = -gx1 | ||||

5. If gx1 is square, x = x1 and y = sqrt(gx1) | ||||

6. Else x = x2 and y = sqrt(gx2) | ||||

7. If sgn0(u) != sgn0(y), set y = -y. | ||||

8. return (x, y) | ||||

A Montgomery curve is given by the following equation E: | 6.8.2.1. Implementation | |||

By^2=x^3+Ax^2+x, where B(A^2 - 4) ≠ 0. Note that any curve | ||||

with a point of order 2 is isomorphic to this representation. Also | ||||

notice that E cannot have a prime order group, hence, a scalar | ||||

multiplication by the cofactor is required to obtain a point in the | ||||

main subgroup. | ||||

5.4.1. Elligator2 Method | The following procedure implements the Elligator 2 mapping for | |||

supersingular curves in a straight-line fashion. | ||||

The map2curve_elligator2(alpha) implements the Elligator2 method from | map_to_curve_ell2A0(u) | |||

[Elligator2]. | Input: u, an element of F. | |||

Output: (x, y), a point on E. | ||||

*Preconditions* | Constants: | |||

1. c1 = (p + 1) / 4 // Integer arithmetic | ||||

Any curve of the form y^2=x^3+Ax^2+Bx, which covers all Montgomery | Steps: | |||

curves such that A ≠ 0 and B=1 (i.e. j-invariant != 1728). | 1. x1 = u | |||

2. x2 = -x1 | ||||

3. gx1 = x1^2 | ||||

4. gx1 = gx1 + B | ||||

5. gx1 = gx1 * x1 // gx1 = x1^3 + B * x1 | ||||

6. y = gx1^c1 // this is either sqrt(gx1) or sqrt(gx2) | ||||

7. e1 = (y^2) == gx1 | ||||

8. x = CMOV(x2, x1, e1) | ||||

9. e2 = sgn0(u) == sgn0(y) | ||||

10. y = CMOV(-y, y, e2) | ||||

11. return (x, y) | ||||

*Examples* | 6.9. Mappings for Pairing-Friendly curves | |||

o Curve25519 | 6.9.1. Shallue-van de Woestijne Method | |||

o Curve448 | Shallue and van de Woestijne [SW06] describe a mapping that applies | |||

to essentially any elliptic curve. Fouque and Tibouchi [FT12] give a | ||||

concrete set of parameters for this mapping geared toward Barreto- | ||||

Naehrig pairing-friendly curves [BN05], i.e., curves y^2 = x^3 + B | ||||

over fields of characteristic q = 1 (mod 3). Wahby and Boneh [WB19] | ||||

suggest a small generalization of the Fouque-Tibouchi parameters that | ||||

results in a uniform method for handling exceptional cases. | ||||

*Algorithm*: map2curve_elligator2 | The Shallue-van de Woestijne mapping method covers curves not handled | |||

by other methods, e.g., SECP256K1 [SEC2]. It also covers pairing- | ||||

friendly curves in the BN [BN05], KSS [KSS08], and BLS [BLS03] | ||||

families. (Note, however, that the mapping described in | ||||

Section 6.9.2 is faster, when it applies.) | ||||

Input: | Preconditions: An elliptic curve y^2 = g(x) = x^3 + B over F such | |||

that q = 1 (mod 3) and B != 0. | ||||

o alpha: an octet string to be hashed. | Constants: | |||

o A,B=1: the constants of the Montgomery curve. | o B, the parameter of the Weierstrass curve. | |||

o N : a constant non-square in the field. | o Z, the unique element of F meeting all of the following criteria: | |||

Output: | 1. g((sqrt(-3 * Z^2) - Z) / 2) is square in F, | |||

o (x,y), a point in E. | 2. there is no other Z' meeting criterion (1) for which abs(Z') < | |||

abs(Z) (Section 4), and | ||||

3. if Z and -Z both meet the above criteria, Z is the element | ||||

such that sgn0(Z) == 1. | ||||

Sign of y: Inputs u and -u give the same x-coordinate. Thus, we set | ||||

sgn0(y) == sgn0(u). | ||||

Exceptions: The exceptional cases for u occur when u^2 * (u^2 + g(Z)) | ||||

== 0. The restriction on Z given above ensures that implementations | ||||

that use inv0 to invert this product are exception free. | ||||

Operations: | Operations: | |||

1. Define g(x) = x(x^2 + Ax + B) | 1. t1 = u^2 + g(Z) | |||

2. u = hash2base(alpha) | 2. t2 = inv0(u^2 * t1) | |||

3. v = -A/(1 + N*u^2) | 3. t3 = u^4 * t2 * sqrt(-3 * Z^2) | |||

4. e = Legendre(g(v)) | 4. x1 = ((sqrt(-3 * Z^2) - Z) / 2) - t3 | |||

5.1. If u != 0, then | 5. x2 = t3 - ((sqrt(-3 * Z^2) + Z) / 2) | |||

5.2. x = ev - (1 - e)A/2 | 6. x3 = Z - (t1^3 * t2 / (3 * Z^2)) | |||

5.3. y = -e*sqrt(g(x)) | 7. If is_square(g(x1)), set x = x1 and y = sqrt(g(x1)) | |||

5.4. Else, x=0 and y=0 | 8. Else If is_square(g(x2)), set x = x2 and y = sqrt(g(x2)) | |||

6. Output (x,y) | 9. Else set x = x3 and y = sqrt(g(x3)) | |||

10. If sgn0(u) != sgn0(y), set y = -y | ||||

11. return (x, y) | ||||

Here, e is the Legendre symbol defined as in Section 4. | 6.9.1.1. Implementation | |||

*Implementation* | The following procedure implements the Shallue and van de Woestijne | |||

method in a straight-line fashion. | ||||

The following procedure implements elligator2 algorithm in a | map_to_curve_svdw(u) | |||

straight-line fashion. | Input: u, an element of F. | |||

Output: (x, y), a point on E. | ||||

map2curve_elligator2(alpha) | Constants: | |||

1. c1 = g(Z) | ||||

2. c2 = sqrt(-3 * Z^2) | ||||

3. c3 = (sqrt(-3 * Z^2) - Z) / 2 | ||||

4. c4 = (sqrt(-3 * Z^2) + Z) / 2 | ||||

5. c5 = 1 / (3 * Z^2) | ||||

Input: | Steps: | |||

1. t1 = u^2 | ||||

2. t2 = t1 + c1 // t2 = u^2 + g(Z) | ||||

3. t3 = t1 * t2 | ||||

4. t4 = inv0(t3) // t4 = 1 / (u^2 * (u^2 + g(Z))) | ||||

5. t3 = t1^2 | ||||

6. t3 = t3 * t4 | ||||

7. t3 = t3 * c2 // t3 = u^2 * sqrt(-3 * Z^2) / (u^2 + g(Z)) | ||||

8. x1 = c3 - t3 | ||||

9. gx1 = x1^2 | ||||

10. gx1 = gx1 * x1 | ||||

11. gx1 = gx1 + B // gx1 = x1^3 + B | ||||

12. e1 = is_square(gx1) | ||||

13. x2 = t3 - c4 | ||||

14. gx2 = x2^2 | ||||

15. gx2 = gx2 * x2 | ||||

16. gx2 = gx2 + B // gx2 = x2^3 + B | ||||

17. e2 = is_square(gx2) | ||||

18. e3 = e1 OR e2 // logical OR | ||||

19. x3 = t2^2 | ||||

20. x3 = x3 * t2 | ||||

21. x3 = x3 * t4 | ||||

22. x3 = x3 * c5 | ||||

23. x3 = Z - x3 // Z - (u^2 + g(Z))^2 / (3 Z^2 u^2) | ||||

24. gx3 = x3^2 | ||||

25. gx3 = gx3 * x3 | ||||

26. gx3 = gx3 + B // gx3 = x3^3 + B | ||||

27. x = CMOV(x2, x1, e1) // select x1 if gx1 is square | ||||

28. gx = CMOV(gx2, gx1, e1) | ||||

29. x = CMOV(x3, x, e3) // select x3 if gx1 and gx2 are not square | ||||

30. gx = CMOV(gx3, gx, e3) | ||||

31. y = sqrt(gx) | ||||

32. e4 = sgn0(u) == sgn0(y) | ||||

33. y = CMOV(-y, y, e4) // select correct sign of y | ||||

34. return (x, y) | ||||

alpha - value to be encoded, an octet string | 6.9.2. Simplified SWU for Pairing-Friendly Curves | |||

A,B=1 - the constants of the Montgomery curve. | ||||

N - a constant non-square value in Fp. | ||||

Output: | Wahby and Boneh [WB19] show how to adapt the simplified SWU mapping | |||

to certain Weierstrass curves having either A = 0 or B = 0, one of | ||||

which is almost always true for pairing-friendly curves. Note that | ||||

neither case is supported by the mapping of Section 6.5.2. | ||||

(x, y) - a point in E | This method requires finding another elliptic curve | |||

Precomputations: | E': y^2 = g'(x) = x^3 + A' * x + B' | |||

1. c1 = (p - 1)/2 // Integer arithmetic | that is isogenous to E and has A' != 0 and B' != 0. (One might do | |||

2. c2 = A / 2 (mod p) // Field arithmetic | this, for example, using [SAGE]; details are beyond the scope of this | |||

document.) This isogeny defines a map iso_map(x', y') that takes as | ||||

input a point on E' and produces as output a point on E. | ||||

Steps: | 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', | ||||

then apply the isogeny map to that point to get a point on E. | ||||

1. u = hash2base(alpha) | Note that iso_map is a group homomorphism, meaning that point | |||

2. t1 = u^2 | addition commutes with iso_map. Thus, when using this mapping in the | |||

3. t1 = N * t1 | hash_to_curve construction of Section 3, one can effect a small | |||

4. t1 = 1 + t1 | optimization by first mapping u0 and u1 to E', adding the resulting | |||

5. t1 = t1^(-1) | points on E', and then applying iso_map to the sum. This gives the | |||

6. v = A * t1 | same result while requiring only one evaluation of iso_map. | |||

7. v = -v // v = -A / (1 + N * u^2) | ||||

8. gv = v + A | ||||

9. gv = gv * v | ||||

0. gv = gv + B | ||||

11. gv = gv * v // gv = v^3 + Av^2 + Bv | ||||

12. e = gv^c1 // Legendre(gv) | ||||

13. x = e*v | ||||

14. ne = -e | ||||

15. t1 = 1 + ne | ||||

16. t1 = t1 * c2 | ||||

17. x = x - t1 // x = ev - (1 - e)*A/2 | ||||

18. y = x + A | ||||

19. y = y * x | ||||

20. y = y + B | ||||

21. y = y * x | ||||

22. y = sqrt(y) | ||||

23. y = y * ne // y = -e * sqrt(x^3 + Ax^2 + Bx) | ||||

24. x = CMOV(0, x, 1-u) | ||||

25. y = CMOV(0, y, 1-u) | ||||

26. Output (x, y) | ||||

Elligator2 can be simplified with projective coordinates. | Preconditions: An elliptic curve E' with A' != 0 and B' != 0 that is | |||

isogenous to the target curve E with isogeny map iso_map(x, y) from | ||||

E' to E. | ||||

((TODO: write this variant)) | Helper functions: | |||

6. Random Oracles | o map_to_curve_simple_swu is the mapping of Section 6.5.2 to E' | |||

Some applications require a Random Oracle (RO) of points, which can | o iso_map is the isogeny map from E' to E | |||

be constructed from deterministic encoding functions. Farashahi et | ||||

al. [FFSTV13] showed a generic mapping construction that is | ||||

indistinguishable from a random oracle. In particular, let "f : | ||||

{0,1}^* -> E(F)" be a deterministic encoding function, and let "H0" | ||||

and "H1" be two hash functions modeled as random oracles that map bit | ||||

strings to elements in the field "F", i.e., "H0,H1 : {0,1}* -> F". | ||||

Then, the "hash2curveRO(alpha)" mapping is defined as | ||||

hash2curveRO(alpha) = f(H0(alpha)) + f(H1(alpha)) | Sign of y: for this map, the sign is determined by | |||

map_to_curve_elligator2. No further sign adjustments are necessary. | ||||

where alpha is an octet string to be encoded as a point on a curve. | Exceptions: map_to_curve_simple_swu handles its exceptional cases. | |||

Exceptional cases of iso_map should return the identity point on E. | ||||

6.1. Interface | Operations: | |||

Using the deterministic encodings from Section 5, the | 1. (x', y') = map_to_curve_simple_swu(u) // (x', y') is on E' | |||

"hash2curveRO(alpha)" mapping can be instantiated as | 2. (x, y) = iso_map(x', y') // (x, y) is on E | |||

3. return (x, y) | ||||

We do not repeat the sample implementation of Section 6.5.2 here. | ||||

See [hash2curve-repo] or [WB19] for details on implementing the | ||||

isogeny map. | ||||

hash2curveRO(alpha) = hash2curve(alpha || 0x02) + hash2curve(alpha || 0x03) | 7. Clearing the cofactor | |||

where the addition operation is performed as a point addition. | 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). | ||||

Obtaining a point in G may require a final operation commonly called | ||||

"clearing the cofactor," which takes as input any point on the curve. | ||||

7. Curve Transformations | 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 | ||||

of points, no operation is required. This applies, for example, to | ||||

the NIST curves P-256, P-384, and P-521 [FIPS186-4]. | ||||

Every elliptic curve can be converted to an equivalent curve in short | In some cases, it is possible to clear the cofactor via a faster | |||

Weierstrass form ([BL07] Theorem 2.1), making SWU a generic algorithm | method than scalar multiplication by h. These methods are equivalent | |||

that can be used for all curves. Curves in either Edwards or Twisted | to (but usually faster than) multiplication by some scalar h_eff | |||

Edwards form can be transformed into equivalent curves in Montgomery | whose value is determined by the method and the curve. Examples of | |||

form [BL17] for use with Elligator2. [RFC7748] describes how to | fast cofactor clearing methods include the following: | |||

convert between points on Curve25519 and Ed25519, and between | ||||

Curve448 and its Edwards equivalent, Goldilocks. | ||||

8. Ciphersuites | o For certain pairing-friendly curves having subgroup G2 over an | |||

extension field, Scott et al. [SBCDBK09] describe a method for | ||||

fast cofactor clearing that exploits an efficiently-computable | ||||

endomorphism. Fuentes-Castaneda et al. [FKR11] propose an | ||||

alternative method that is sometimes more efficient. Budroni and | ||||

Pintore [BP18] give concrete instantiations of these methods for | ||||

Barreto-Lynn-Scott pairing-friendly curves [BLS03]. | ||||

To provide concrete recommendations for algorithms we define a hash- | o Wahby and Boneh ([WB19], Section 5) describe a trick due to Scott | |||

to-curve "ciphersuite" as a four-tuple containing: | for fast cofactor clearing on any elliptic curve for which the | |||

prime factorization of h and the structure of the elliptic curve | ||||

group meet certain conditions. | ||||

o Destination Group (e.g. P256 or Curve25519) | The clear_cofactor function is parameterized by a scalar h_eff. | |||

Specifically, | ||||

o hash2base algorithm | clear_cofactor(P) := h_eff * P | |||

o HashToCurve algorithm (e.g. SSWU, Icart) | where * represents scalar multiplication. When a curve does not | |||

support a fast cofactor clearing method, h_eff = h and the cofactor | ||||

MUST be cleared via scalar multiplication. | ||||

o (Optional) Transformation (e.g. FFSTV, cofactor clearing) | When a curve admits a fast cofactor clearing method, clear_cofactor | |||

A ciphersuite defines an algorithm that takes an arbitrary octet | MAY be evaluated either via that method or via scalar multiplication | |||

string and returns an element of the Destination Group defined in the | by the equivalent h_eff; these two methods give the same result. | |||

ciphersuite by applying HashToCurve and Transformation (if defined). | Note that in this case scalar multiplication by the cofactor h does | |||

not generally give the same result as the fast method, and SHOULD NOT | ||||

be used. | ||||

This document describes the following set of ciphersuites: | 8. Suites for Hashing | |||

o H2C-P256-SHA256-SSWU- | This section lists recommended suites for hashing to standard | |||

elliptic curves. | ||||

o H2C-P384-SHA512-Icart- | A suite fully specifies the procedure for hashing bit strings to | |||

points on a specific elliptic curve group. Each suite comprises the | ||||

following parameters: | ||||

o H2C-SECP256K1-SHA512-FT- | o Suite ID, a short name used to refer to a given suite. | |||

o H2C-BN256-SHA512-FT- | o E, the target elliptic curve over a field F. | |||

o H2C-Curve25519-SHA512-Elligator2-Clear | o p, the characteristic of the field F. | |||

o H2C-Curve448-SHA512-Elligator2-Clear | o m, the extension degree of the field F. | |||

o H2C-Curve25519-SHA512-Elligator2-FFSTV | o H, the hash function used by hash_to_base (Section 5). | |||

o H2C-Curve448-SHA512-Elligator2-FFSTV | o W, the number of evaluations of H in hash_to_base. | |||

H2C-P256-SHA256-SSWU- is defined as follows: | o f, a mapping function from Section 6. | |||

o The destination group is the set of points on the NIST P-256 | o h_eff, the scalar parameter for clear_cofactor (Section 7). | |||

elliptic curve, with curve parameters as specified in [DSS] | ||||

(Section D.1.2.3) and [RFC5114] (Section 2.6). | ||||

o hash2base is defined as {#hashtobase} with the hash function | In addition to the above parameters, the mapping f may require | |||

defined as SHA-256 as specified in [RFC6234], and p set to the | additional parameters Z, M, rational_map, E', and/or iso_map. These | |||

prime field used in P-256 (2^256 - 2^224 + 2^192 + 2^96 - 1). | are specified when applicable. | |||

o HashToCurve is defined to be {#sswu} with A and B taken from the | Suites whose ID includes "-RO" use the hash_to_curve procedure of | |||

definition of P-256 (A=-3, B=4105836372515214212932612978004726840 | Section 3; suites whose ID includes "-NU" use the encode_to_curve | |||

9114441015993725554835256314039467401291). | procedure from that section. Applications whose security requires a | |||

random oracle MUST use a "-RO" suite. | ||||

H2C-P384-SHA512-Icart- is defined as follows: | When standardizing a new elliptic curve, corresponding hash-to-curve | |||

suites SHOULD be specified. | ||||

o The destination group is the set of points on the NIST P-384 | The below table lists the curves for which suites are defined and the | |||

elliptic curve, with curve parameters as specified in [DSS] | subsection that gives the corresponding parameters. | |||

(Section D.1.2.4) and [RFC5114] (Section 2.7). | ||||

o hash2base is defined as {#hashtobase} with the hash function | +---------------------------+-------------+ | |||

defined as SHA-512 as specified in [RFC6234], and p set to the | | E | Section | | |||

prime field used in P-384 (2^384 - 2^128 - 2^96 + 2^32 - 1). | +---------------------------+-------------+ | |||

| NIST P-256 | Section 8.1 | | ||||

| | | | ||||

| NIST P-384 | Section 8.2 | | ||||

| | | | ||||

| NIST P-521 | Section 8.3 | | ||||

| | | | ||||

| curve25519 / edwards25519 | Section 8.4 | | ||||

| | | | ||||

| curve448 / edwards448 | Section 8.5 | | ||||

| | | | ||||

| SECP256k1 | Section 8.6 | | ||||

| | | | ||||

| BLS12-381 | Section 8.7 | | ||||

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

o HashToCurve is defined to be {#icart} with A and B taken from the | 8.1. Suites for NIST P-256 | |||

definition of P-384 (A=-3, B=2758019355995970587784901184038904809 | ||||

305690585636156852142870730198868924130986086513626076488374510776 | ||||

5439761230575). | ||||

H2C-Curve25519-SHA512-Elligator2-Clear is defined as follows: | The suites P256-SHA256-SSWU-RO and P256-SHA256-SSWU-NU are defined | |||

for the NIST P-256 elliptic curve [FIPS186-4]. These suites share | ||||

the following parameters: | ||||

o The destination group is the points on Curve25519, with curve | o E: y^2 = x^3 + A * x + B, where | |||

parameters as specified in [RFC7748] (Section 4.1). | ||||

o hash2base is defined as {#hashtobase} with the hash function | * A = -3 | |||

defined as SHA-512 as specified in [RFC6234], and p set to the | ||||

prime field used in Curve25519 (2^255 - 19). | ||||

o HashToCurve is defined to be {#elligator2} with the curve function | * B = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e2 | |||

defined to be the Montgomery form of Curve25519 (y^2 = x^3 + | 7d2604b | |||

486662x^2 + x) and N = 2. | ||||

o The final output is multiplied by the cofactor of Curve25519, 8. | o p: 2^256 - 2^224 + 2^192 + 2^96 - 1 | |||

H2C-Curve448-SHA512-Elligator2-Clear is defined as follows: | o m: 1 | |||

o The destination group is the points on Curve448, with curve | o H: SHA-256 | |||

parameters as specified in [RFC7748] (Section 4.1). | ||||

o hash2base is defined as {#hashtobase} with the hash function | o W: 2 | |||

defined as SHA-512 as specified in [RFC6234], and p set to the | ||||

prime field used in Curve448 (2^448 - 2^224 - 1). | ||||

o HashToCurve is defined to be {#elligator2} with the curve function | o f: Simplified SWU method, Section 6.5.2 | |||

defined to be the Montgomery form of Curve448 (y^2 = x^3 + | ||||

156326x^2 + x) and N = -1. | ||||

o The final output is multiplied by the cofactor of Curve448, 4. | o Z: -2 | |||

H2C-Curve25519-SHA512-Elligator2-FFSTV is defined as in H2C- | o h_eff: 1 | |||

Curve25519-SHA-512-Elligator2-Clear except HashToCurve is defined to | ||||

be {#ffstv} where F is {#elligator2}. | ||||

H2C-Curve448-SHA512-Elligator2-FFSTV is defined as in H2C-Curve448- | 8.2. Suites for NIST P-384 | |||

SHA-512-Elligator2-Clear except HashToCurve is defined to be {#ffstv} | ||||

where F is {#elligator2}. | ||||

9. IANA Considerations | The suites P384-SHA512-ICART-RO and P384-SHA512-ICART-NU are defined | |||

for the NIST P-384 elliptic curve [FIPS186-4]. These suites share | ||||

the following parameters: | ||||

This document has no IANA actions. | o E: y^2 = x^3 + A * x + B, where | |||

10. Security Considerations | * A = -3 | |||

Each encoding function variant accepts arbitrary input and maps it to | * B = 0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5 | |||

a pseudorandom point on the curve. Points are close to | 013875ac656398d8a2ed19d2a85c8edd3ec2aef | |||

indistinguishable from randomly chosen elements on the curve. Not | ||||

all encoding functions are full-domain hashes. Elligator2, for | ||||

example, only maps strings to "about half of all curve points," | ||||

whereas Icart's method only covers about 5/8 of the points. | ||||

11. Acknowledgements | o p: 2^384 - 2^128 - 2^96 + 2^32 - 1 | |||

The authors would like to thank Adam Langley for this detailed | o m: 1 | |||

writeup up Elligator2 with Curve25519 [ElligatorAGL]. We also thank | ||||

Sean Devlin and Thomas Icart for feedback on earlier versions of this | ||||

document. | ||||

12. Contributors | o H: SHA-512 | |||

o Armando Faz | o W: 2 | |||

Cloudflare | ||||

armfazh@cloudflare.com | ||||

o Sharon Goldberg | o f: Icart's method, Section 6.5.1 | |||

Boston University | ||||

goldbe@cs.bu.edu | ||||

o Ela Lee | o h_eff: 1 | |||

Royal Holloway, University of London | ||||

Ela.Lee.2010@live.rhul.ac.uk | ||||

13. Normative References | 8.3. Suites for NIST P-521 | |||

[BF01] Boneh, D. and M. Franklin, "Identity-based encryption from | The suites P521-SHA512-SSWU-RO and P521-SHA512-SSWU-NU are defined | |||

the Weil pairing", Advances in Cryptology -- CRYPTO 2001, | for the NIST P-384 elliptic curve [FIPS186-4]. These suites share | |||

pages 213-229 , n.d., | the following parameters: | |||

<https://doi.org/10.1007/3-540-44647-8_13>. | ||||

[BL07] "Faster addition and doubling on elliptic curves", n.d., | o E: y^2 = x^3 + A * x + B, where | |||

<https://eprint.iacr.org/2007/286.pdf>. | ||||

[BL17] "Montgomery curves and the Montgomery ladder", n.d., | * A = -3 | |||

<https://eprint.iacr.org/2017/293.pdf>. | ||||

[BLS01] Dan Boneh, ., Ben Lynn, ., and . Hovav Shacham, "Short | * B = 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b4899 | |||

signatures from the Weil pairing", Journal of Cryptology, | 18ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451f | |||

v17, pages 297-319 , n.d., | d46b503f00 | |||

<https://doi.org/10.1007/s00145-004-0314-9>. | ||||

[BMP00] Victor Boyko, ., MacKenzie, Philip., and . Sarvar Patel, | o p: 2^521 - 1 | |||

"Provably secure password-authenticated key exchange using | ||||

diffie-hellman", n.d.. | ||||

[BN05] Barreto, P. and M. Naehrig, "Pairing-Friendly Elliptic | o m: 1 | |||

Curves of Prime Order", Selected Areas in Cryptography | ||||

2005, pages 319-331. , n.d., | ||||

<https://doi.org/10.1007/11693383_22>. | ||||

[DSS] National Institute of Standards and Technology, U.S. | o H: SHA-512 | |||

Department of Commerce, "Digital Signature Standard, | ||||

version 4", NIST FIPS PUB 186-4, 2013. | ||||

[ECOPRF] "EC-OPRF - Oblivious Pseudorandom Functions using Elliptic | o W: 2 | |||

Curves", n.d.. | ||||

[Elligator2] | o f: Simplified SWU method, Section 6.5.2 | |||

"Elligator -- Elliptic-curve points indistinguishable from | o Z: -2 | |||

uniform random strings", n.d., | ||||

<https://dl.acm.org/ft_gateway.cfm?id=2516734&type=pdf>. | ||||

[ElligatorAGL] | o h_eff: 1 | |||

"Implementing Elligator for Curve25519", n.d., | ||||

<https://www.imperialviolet.org/2013/12/25/ | ||||

elligator.html>. | ||||

[FFSTV13] "Indifferentiable deterministic hashing to elliptic and | An optimized example implementation of the above mapping is given in | |||

hyperelliptic curves", n.d.. | Appendix D.2. | |||

[FIPS-186-4] | 8.4. Suites for curve25519 and edwards25519 | |||

"Digital Signature Standard (DSS), FIPS PUB 186-4, July | ||||

2013", n.d., | ||||

<https://csrc.nist.gov/publications/detail/fips/186/4/ | ||||

final>. | ||||

[FT12] Pierre-Alain Fouque, . and . Mehdi Tibouchi, | This section defines ciphersuites for curve25519 and edwards25519 | |||

"Indifferentiable Hashing to Barreto-Naehrig Curves", | [RFC7748]. | |||

LATINCRYPT 2012, pages 1-17. , n.d., | ||||

<https://doi.org/10.1007/978-3-642-33481-8_1>. | ||||

[github-repo] | The suites curve25519-SHA256-ELL2-RO and curve25519-SHA256-ELL2-NU | |||

"draft-irtf-cfrg-hash-to-curve | github.com", n.d., | share the following parameters, in addition to the common parameters | |||

<https://github.com/chris-wood/ | below. | |||

draft-irtf-cfrg-hash-to-curve/>. | ||||

[hacspec] "hacspec", n.d., | o E: B * y^2 = x^3 + A * x^2 + x, where | |||

<https://github.com/HACS-workshop/hacspec>. | ||||

[Icart09] Icart, T., "How to Hash into Elliptic Curves", n.d., | * A = 486662 | |||

<https://eprint.iacr.org/2009/226.pdf>. | ||||

[Jablon96] | * B = 1 | |||

"Strong password-only authenticated key exchange", n.d.. | ||||

[KSS08] Kachisa, E., Schaefer, E., and M. Scott, "Constructing | o f: Elligator 2 method, Section 6.6.1 | |||

Brezing-Weng Pairing-Friendly Elliptic Curves Using | ||||

Elements in the Cyclotomic Field", Pairing-Based | ||||

Cryptography - Pairing 2008, pages 126-135 , n.d., | ||||

<https://doi.org/10.1007/978-3-540-85538-5_9>. | ||||

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate | The suites edwards25519-SHA256-EDELL2-RO and | |||

Requirement Levels", BCP 14, RFC 2119, | edwards25519-SHA256-EDELL2-NU share the following parameters, in | |||

DOI 10.17487/RFC2119, March 1997, | addition to the common parameters below. | |||

<https://www.rfc-editor.org/info/rfc2119>. | ||||

[RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman | o E: a * x^2 + y^2 = 1 + d * x^2 * y^2, where | |||

Groups for Use with IETF Standards", RFC 5114, | ||||

DOI 10.17487/RFC5114, January 2008, | ||||

<https://www.rfc-editor.org/info/rfc5114>. | ||||

[RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand | * a = -1 | |||

Key Derivation Function (HKDF)", RFC 5869, | ||||

DOI 10.17487/RFC5869, May 2010, | ||||

<https://www.rfc-editor.org/info/rfc5869>. | ||||

[RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms | * d = 0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca1 | |||

(SHA and SHA-based HMAC and HKDF)", RFC 6234, | 35978a3 | |||

DOI 10.17487/RFC6234, May 2011, | ||||

<https://www.rfc-editor.org/info/rfc6234>. | ||||

[RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves | o f: Twisted Edwards Elligator 2 method, Section 6.7.2 | |||

for Security", RFC 7748, DOI 10.17487/RFC7748, January | ||||

2016, <https://www.rfc-editor.org/info/rfc7748>. | ||||

[RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, | o M: curve25519 defined in [RFC7748], Section 4.1 | |||

"PKCS #1: RSA Cryptography Specifications Version 2.2", | ||||

RFC 8017, DOI 10.17487/RFC8017, November 2016, | ||||

<https://www.rfc-editor.org/info/rfc8017>. | ||||

[RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital | o rational_map: the birational map defined in [RFC7748], Section 4.1 | |||

Signature Algorithm (EdDSA)", RFC 8032, | ||||

DOI 10.17487/RFC8032, January 2017, | ||||

<https://www.rfc-editor.org/info/rfc8032>. | ||||

[SAGE] "SageMath, the Sage Mathematics Software System", n.d., | The common parameters for all of the above suites are: | |||

<https://www.sagemath.org>. | ||||

[Schoof85] | o p: 2^255 - 19 | |||

"Elliptic Curves Over Finite Fields and the Computation of | ||||

Square Roots mod p", n.d., <https://www.ams.org/journals/ | ||||

mcom/1985-44-170/S0025-5718-1985-0777280-6/ | ||||

S0025-5718-1985-0777280-6.pdf>. | ||||

[SEC2] Standards for Efficient Cryptography Group (SECG), ., "SEC | o m: 1 | |||

2: Recommended Elliptic Curve Domain Parameters", n.d., | ||||

<http://www.secg.org/sec2-v2.pdf>. | ||||

[SECG1] Standards for Efficient Cryptography Group (SECG), ., "SEC | o H: SHA-256 | |||

1: Elliptic Curve Cryptography", n.d., | o W: 2 | |||

<http://www.secg.org/sec1-v2.pdf>. | ||||

[SimpleSWU] | o Z: 2 | |||

"Efficient Indifferentiable Hashing into Ordinary Elliptic | ||||

Curves", n.d., <https://eprint.iacr.org/2009/340.pdf>. | ||||

[SW06] "Construction of rational points on elliptic curves over | o h_eff: 8 | |||

finite fields", n.d.. | ||||

[SWU07] "Rational points on certain hyperelliptic curves over | Optimized example implementations of the above mappings are given in | |||

finite fields", n.d., <https://arxiv.org/pdf/0706.1448>. | Appendix D.3 and Appendix D.4. | |||

Appendix A. Related Work | 8.5. Suites for curve448 and edwards448 | |||

In this chapter, we give a background to some common methods to | This section defines ciphersuites for curve448 and edwards448 | |||

encode or hash to the curve, motivated by the similar exposition in | [RFC7748]. | |||

[Icart09]. Understanding of this material is not required in order | ||||

to choose a suitable encoding function - we defer this to Section 3 - | ||||

the background covered here can work as a template for analyzing | ||||

encoding functions not found in this document, and as a guide for | ||||

further research into the topics covered. | ||||

A.1. Probabilistic Encoding | The suites curve448-SHA512-ELL2-RO and curve448-SHA512-ELL2-NU share | |||

the following parameters, in addition to the common parameters below. | ||||

As mentioned in Section 2, as a rule of thumb, for every x in GF(p), | o E: B * y^2 = x^3 + A * x^2 + x, where | |||

there is approximately a 1/2 chance that there exist a corresponding | ||||

y value such that (x, y) is on the curve E. | ||||

This motivates the construction of the MapToGroup method described by | * A = 156326 | |||

Boneh et al. [BLS01]. For an input message m, a counter i, and a | ||||

standard hash function H : {0, 1}^* -> GF(p) x {0, 1}, one computes | ||||

(x, b) = H(i || m), where i || m denotes concatenation of the two | ||||

values. Next, test to see whether there exists a corresponding y | ||||

value such that (x, y) is on the curve, returning (x, y) if | ||||

successful, where b determines whether to take +/- y. If there does | ||||

not exist such a y, then increment i and repeat. A maximum counter | ||||

value is set to I, and since each iteration succeeds with probability | ||||

approximately 1/2, this process fails with probability 2^-I. (See | ||||

Appendix B for a more detailed description of this algorithm.) | ||||

Although MapToGroup describes a method to hash to the curve, it can | * B = 1 | |||

also be adapted to a simple encoding mechanism. For a bitstring of | ||||

length strictly less than log2(p), one can make use of the spare bits | ||||

in order to encode the counter value. Allocating more space for the | ||||

counter increases the expansion, but reduces the failure probability. | ||||

Since the running time of the MapToGroup algorithm depends on m, this | o f: Elligator 2 method, Section 6.6.1 | |||

algorithm is NOT safe for cases sensitive to timing side channel | ||||

attacks. Deterministic algorithms are needed in such cases where | ||||

failures are undesirable. | ||||

A.2. Naive Encoding | The suites edwards448-SHA512-EDELL2-RO and | |||

edwards448-SHA512-EDELL2-NU share the following parameters, in | ||||

addition to the common parameters below. | ||||

A naive solution includes computing H(m)*G as map2curve(m), where H | o E: a * x^2 + y^2 = 1 + d * x^2 * y^2, where | |||

is a standard hash function H : {0, 1}^* -> GF(p), and G is a | ||||

generator of the curve. Although efficient, this solution is | ||||

unsuitable for constructing a random oracle onto E, since the | ||||

discrete logarithm with respect to G is known. For example, given y1 | ||||

= map2curve(m1) and y2 = map2curve(m2) for any m1 and m2, it must be | ||||

true that y2 = H(m2) / H(m1) * map2curve(m1). This relationship | ||||

would not hold (with overwhelming probability) for truly random | ||||

values y1 and y2. This causes catastrophic failure in many cases. | ||||

However, one exception is found in SPEKE [Jablon96], which constructs | ||||

a base for a Diffie-Hellman key exchange by hashing the password to a | ||||

curve point. Notably the use of a hash function is purely for | ||||

encoding an arbitrary length string to a curve point, and does not | ||||

need to be a random oracle. | ||||

A.3. Deterministic Encoding | * a = 1 | |||

Shallue, Woestijne, and Ulas [SW06] first introduced a deterministic | * d = -39081 | |||

algorithm that maps elements in F_{q} to a curve in time O(log^4 q), | ||||

where q = p^n for some prime p, and time O(log^3 q) when q = 3 mod 4. | ||||

Icart introduced yet another deterministic algorithm which maps F_{q} | ||||

to any EC where q = 2 mod 3 in time O(log^3 q) [Icart09]. Elligator | ||||

(2) [Elligator2] is yet another deterministic algorithm for any odd- | ||||

characteristic EC that has a point of order 2. Elligator2 can be | ||||

applied to Curve25519 and Curve448, which are both CFRG-recommended | ||||

curves [RFC7748]. | ||||

However, an important caveat to all of the above deterministic | o f: Twisted Edwards Elligator 2 method, Section 6.7.2 | |||

encoding functions, is that none of them map injectively to the | ||||

entire curve, but rather some fraction of the points. This makes | ||||

them unable to use to directly construct a random oracle on the | ||||

curve. | ||||

Brier et al. [SimpleSWU] proposed a couple of solutions to this | o M: curve448, defined in [RFC7748], Section 4.2 | |||

problem, The first applies solely to Icart's method described above, | ||||

by computing F(H0(m)) + F(H1(m)) for two distinct hash functions H0, | ||||

H1. The second uses a generator G, and computes F(H0(m)) + H1(m)*G. | ||||

Later, Farashahi et al. [FFSTV13] showed the generality of the | ||||

F(H0(m)) + F(H1(m)) method, as well as the applicability to | ||||

hyperelliptic curves (not covered here). | ||||

A.4. Supersingular Curves | o rational_map: the 4-isogeny map defined in [RFC7748], Section 4.2 | |||

For supersingular curves, for every y in GF(p) (with p>3), there | The common parameters for all of the above suites are: | |||

exists a value x such that (x, y) is on the curve E. Hence we can | ||||

construct a bijection F : GF(p) -> E (ignoring the point at | ||||

infinity). This is the case for [BF01], but is not common. | ||||

A.5. Twisted Variants | o p: 2^448 - 2^224 - 1 | |||

We can also consider curves which have twisted variants, E^d. For | o m: 1 | |||

such curves, for any x in GF(p), there exists y in GF(p) such that | ||||

(x, y) is either a point on E or E^d. Hence one can construct a | ||||

bijection F : GF(p) x {0,1} -> E ∪ E^d, where the extra bit is | ||||

needed to choose the sign of the point. This can be particularly | ||||

useful for constructions which only need the x-coordinate of the | ||||

point. For example, x-only scalar multiplication can be computed on | ||||

Montgomery curves. In this case, there is no need for an encoding | ||||

function, since the output of F in GF(p) is sufficient to define a | ||||

point on one of E or E^d. | ||||

Appendix B. Try-and-Increment Method | o H: SHA-512 | |||

o W: 2 | ||||

In cases where constant time execution is not required, the so-called | o Z: -1 | |||

try-and-increment method may be appropriate. As discussion in | ||||

Section 1, this variant works by hashing input m using a standard | ||||

hash function ("Hash"), e.g., SHA256, and then checking to see if the | ||||

resulting point (m, f(m)), for curve function f, belongs on E. This | ||||

is detailed below. | ||||

1. ctr = 0 | o h_eff: 4 | |||

2. h = "INVALID" | ||||

3. While h is "INVALID" or h is EC point at infinity: | ||||

4.1 CTR = I2OSP(ctr, 4) | ||||

4.2 ctr = ctr + 1 | ||||

4.3 attempted_hash = Hash(m || CTR) | ||||

4.4 h = RS2ECP(attempted_hash) | ||||

4.5 If h is not "INVALID" and cofactor > 1, set h = h * cofactor | ||||

5. Output h | ||||

I2OSP is a function that converts a nonnegative integer to octet | Optimized example implementations of the above mappings are given in | |||

string as defined in Section 4.1 of [RFC8017], and RS2ECP(h) = | Appendix D.5 and Appendix D.6. | |||

OS2ECP(0x02 || h), where OS2ECP is specified in Section 2.3.4 of | ||||

[SECG1], which converts an input string into an EC point. | ||||

Appendix C. Sample Code | 8.6. Suites for SECP256K1 | |||

This section contains reference implementations for each map2curve | The suites SECP256K1-SHA256-SVDW-RO and SECP256K1-SHA256-SVDW-NU are | |||

variant built using [hacspec]. | defined for the SECP256K1 elliptic curve [SEC2]. These suites share | |||

the following parameters: | ||||

C.1. Icart Method | o E: y^2 = x^3 + 7 | |||

The following hacspec program implements map2curve_icart(alpha) for | o p: 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 | |||

P-384. | ||||

from hacspec.speclib import * | o m: 1 | |||

prime = 2**384 - 2**128 - 2**96 + 2**32 - 1 | o H: SHA-256 | |||

felem_t = refine(nat, lambda x: x < prime) | o W: 2 | |||

affine_t = tuple2(felem_t, felem_t) | ||||

@typechecked | o f: Shallue-van de Woestijne method, Section 6.9.1 | |||

def to_felem(x: nat_t) -> felem_t: | ||||

return felem_t(nat(x % prime)) | ||||

@typechecked | o Z: 1 | |||

def fadd(x: felem_t, y: felem_t) -> felem_t: | ||||

return to_felem(x + y) | ||||

@typechecked | o h_eff: 1 | |||

def fsub(x: felem_t, y: felem_t) -> felem_t: | ||||

return to_felem(x - y) | ||||

@typechecked | 8.7. Suites for BLS12-381 | |||

def fmul(x: felem_t, y: felem_t) -> felem_t: | ||||

return to_felem(x * y) | ||||

@typechecked | This section defines ciphersuites for groups G1 and G2 of the | |||

def fsqr(x: felem_t) -> felem_t: | BLS12-381 elliptic curve [draft-yonezawa-pfc-01]. | |||

return to_felem(x * x) | ||||

@typechecked | The suites BLS12381G1-SHA256-SSWU-RO and BLS12381G1-SHA256-SSWU-NU | |||

def fexp(x: felem_t, n: nat_t) -> felem_t: | share the following parameters, in addition to the common parameters | |||

return to_felem(pow(x, n, prime)) | below. | |||

@typechecked | o E: y^2 = x^3 + 4 | |||

def finv(x: felem_t) -> felem_t: | ||||

return to_felem(pow(x, prime-2, prime)) | ||||

a384 = to_felem(prime - 3) | o m: 1 | |||

b384 = to_felem(27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575) | ||||

@typechecked | o Z: -1 | |||

def map2p384(u:felem_t) -> affine_t: | ||||

v = fmul(fsub(fmul(to_felem(3), a384), fexp(u, 4)), finv(fmul(to_felem(6), u))) | ||||

u2 = fmul(fexp(u, 6), finv(to_felem(27))) | ||||

x = fsub(fsqr(v), b384) | ||||

x = fsub(x, u2) | ||||

x = fexp(x, (2 * prime - 1) // 3) | ||||

x = fadd(x, fmul(fsqr(u), finv(to_felem(3)))) | ||||

y = fadd(fmul(u, x), v) | ||||

return (x, y) | ||||

C.2. Shallue-Woestijne-Ulas Method | o E': y'^2 = x'^3 + A * x' + B, where | |||

* A = 0x144698a3b8e9433d693a02c96d4982b0ea985383ee66a8d8e8981aefd | ||||

881ac98936f8da0e0f97f5cf428082d584c1d | ||||

The following hacspec program implements map2curve_swu(alpha) for | * B = 0x12e2908d11688030018b12e8753eee3b2016c1f0f24f4070a0b9c14fc | |||

P-256. | ef35ef55a23215a316ceaa5d1cc48e98e172be0 | |||

from p256 import * | o iso_map: the 11-isogeny map from E' to E given in Appendix C.1 | |||

from hacspec.speclib import * | ||||

a256 = to_felem(prime - 3) | o h_eff: 0xd201000000010001 | |||

b256 = to_felem(41058363725152142129326129780047268409114441015993725554835256314039467401291) | ||||

@typechecked | The suites BLS12381G2-SHA256-SSWU-RO and BLS12381G2-SHA256-SSWU-NU | |||

def f_p256(x:felem_t) -> felem_t: | share the following parameters, in addition to the common parameters | |||

return fadd(fexp(x, 3), fadd(fmul(to_felem(a256), x), to_felem(b256))) | below. | |||

@typechecked | o F: GF(p^m), where | |||

def x1(t:felem_t, u:felem_t) -> felem_t: | ||||

return u | ||||

@typechecked | * p: defined below | |||

def x2(t:felem_t, u:felem_t) -> felem_t: | ||||

coefficient = fmul(to_felem(-b256), finv(to_felem(a256))) | ||||

t2 = fsqr(t) | ||||

t4 = fsqr(t2) | ||||

gu = f_p256(u) | ||||

gu2 = fsqr(gu) | ||||

denom = fadd(fmul(t4, gu2), fmul(t2, gu)) | ||||

return fmul(coefficient, fadd(to_felem(1), finv(denom))) | ||||

@typechecked | * m: 2 | |||

def x3(t:felem_t, u:felem_t) -> felem_t: | ||||

return fmul(fsqr(t), fmul(f_p256(u), x2(t, u))) | ||||

@typechecked | * (1, i) is the basis for F, where i^2 + 1 == 0 in F | |||

def map2p256(t:felem_t) -> felem_t: | ||||

u = fadd(t, to_felem(1)) | ||||

x1v = x1(t, u) | ||||

x2v = x2(t, u) | ||||

x3v = x3(t, u) | ||||

exp = to_felem((prime - 1) // 2) | o E: y^2 = x^3 + 4 * (1 + i) | |||

e1 = fexp(f_p256(x1v), exp) | ||||

e2 = fexp(f_p256(x2v), exp) | ||||

if e1 == 1: | o Z: 1 + i | |||

return x1v | ||||

elif e2 == 1: | ||||

return x2v | ||||

else: | ||||

return x3v | ||||

C.3. Simplified SWU Method | o E': y'^2 = x'^3 + A * x' + B, where | |||

The following hacspec program implements map2curve_simple_swu(alpha) | * A = 240 * i | |||

for P-256. | ||||

from p256 import * | * B = 1012 * (1 + i) | |||

from hacspec.speclib import * | ||||

a256 = to_felem(prime - 3) | o iso_map: the isogeny map from E' to E given in Appendix C.2 | |||

b256 = to_felem(41058363725152142129326129780047268409114441015993725554835256314039467401291) | ||||

def f_p256(x:felem_t) -> felem_t: | o h_eff: 0xbc69f08f2ee75b3584c6a0ea91b352888e2a8e9145ad7689986ff0315 | |||

return fadd(fexp(x, 3), fadd(fmul(to_felem(a256), x), to_felem(b256))) | 08ffe1329c2f178731db956d82bf015d1212b02ec0ec69d7477c1ae954cbc06689 | |||

f6a359894c0adebbf6b4e8020005aaa95551 | ||||

def map2p256(t:felem_t) -> affine_t: | The common parameters for the above suites are: | |||

alpha = to_felem(-(fsqr(t))) | ||||

frac = finv((fadd(fsqr(alpha), alpha))) | ||||

coefficient = fmul(to_felem(-b256), finv(to_felem(a256))) | ||||

x2 = fmul(coefficient, fadd(to_felem(1), frac)) | ||||

x3 = fmul(alpha, x2) | o p: 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f | |||

h2 = fadd(fexp(x2, 3), fadd(fmul(a256, x2), b256)) | 6241eabfffeb153ffffb9feffffffffaaab | |||

h3 = fadd(fexp(x3, 3), fadd(fmul(a256, x3), b256)) | ||||

exp = fmul(fadd(to_felem(prime), to_felem(-1)), finv(to_felem(2))) | o H: SHA-256 | |||

e = fexp(h2, exp) | ||||

exp = to_felem((prime + 1) // 4) | o W: 2 | |||

if e == 1: | ||||

return (x2, fexp(f_p256(x2), exp)) | ||||

else: | ||||

return (x3, fexp(f_p256(x3), exp)) | ||||

C.4. Boneh-Franklin Method | o f: Simplified SWU for pairing-friendly curves, Section 6.9.2 | |||

Note that the h_eff parameters for all of the above suites are chosen | ||||

for compatibility with the fast cofactor clearing methods described | ||||

by Scott for G1 ([WB19] Section 5) and by Budroni and Pintore for G2 | ||||

([BP18], Section 4.1). | ||||

The following hacspec program implements map2curve_bf(alpha) for a | 9. IANA Considerations | |||

supersingular curve "y^2=x^3+1" over "GF(p)" and "p = (2^250)(3^159)- | ||||

1". | ||||

from hacspec.speclib import * | This document has no IANA actions. | |||

prime = 2**250*3**159-1 | 10. Security Considerations | |||

a503 = to_felem(0) | When constant-time implementations are required, all basic operations | |||

b503 = to_felem(1) | and utility functions must be implemented in constant time, as | |||

discussed in Section 4. | ||||

@typechecked | Each encoding function accepts arbitrary input and maps it to a | |||

def map2p503(u:felem_t) -> affine_t: | pseudorandom point on the curve. Directly evaluating the mappings of | |||

t0 = fsqr(u) | Section 6 produces an output that is distinguishable from random. | |||

t1 = fsub(t0,b503) | Section 3 shows how to use these mappings to construct a function | |||

x = fexp(t1, (2 * prime - 1) // 3) | approximating a random oracle. | |||

return (x, u) | ||||

C.5. Fouque-Tibouchi Method | Section 3.1 describes considerations related to domain separation for | |||

random oracle encodings. | ||||

The following hacspec program implements map2curve_ft(alpha) for a BN | Section 5 describes considerations for uniformly hashing to field | |||

curve "BN256 : y^2=x^3+1" over "GF(p(t))", where "p(x) = 36x^4 + | elements. | |||

36x^3 + 24x^2 + 6x + 1", and "t = -(2^62 + 2^55 + 1)". | ||||

from hacspec.speclib import * | 11. Acknowledgements | |||

t = -(2**62 + 2**55 + 1) | The authors would like to thank Adam Langley for his detailed writeup | |||

p = lambda x: 36*x**4 + 36*x**3 + 24*x**2 + 6*x + 1 | up Elligator 2 with Curve25519 [L13]. We also thank Sean Devlin and | |||

prime = p(t) | Thomas Icart for feedback on earlier versions of this document. | |||

aBN256 = to_felem(0) | 12. Contributors | |||

bBN256 = to_felem(1) | ||||

@typechecked | o Sharon Goldberg | |||

def map2BN256(u:felem_t) -> affine_t: | Boston University | |||

ZERO = to_felem(0) | goldbe@cs.bu.edu | |||

ONE = to_felem(1) | ||||

SQRT_MINUS3 = fsqrt(to_felem(-3)) | ||||

ONE_SQRT3_DIV2 = fmul(finv(to_felem(2)),fsub(SQRT_MINUS3,ONE)) | ||||

fcurve = lambda x: fadd(fexp(x, 3), fadd(fmul(to_felem(aBN256), x), to_felem(bBN256))) | o Ela Lee | |||

flegendre = lambda x: fexp(u, (prime - 1) // 2) | Royal Holloway, University of London | |||

Ela.Lee.2010@live.rhul.ac.uk | ||||

w = finv(fadd(fadd(fsqr(u),B),ONE)) | 13. References | |||

w = fmul(fmul(w,SQRT_MINUS3),u) | 13.1. Normative References | |||

e = flegendre(u) | ||||

x1 = fsub(ONE_SQRT3_DIV2,fmul(u,w)) | [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate | |||

fx1 = fcurve(x1) | Requirement Levels", BCP 14, RFC 2119, | |||

s1 = flegendre(fx1) | DOI 10.17487/RFC2119, March 1997, | |||

if s1 == 1: | <https://www.rfc-editor.org/info/rfc2119>. | |||

y1 = fmul(fsqrt(fx1),e) | ||||

return (x1,y1) | ||||

x2 = fsub(ZERO,fadd(ONE,x1)) | [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand | |||

fx2 = fcurve(x2) | Key Derivation Function (HKDF)", RFC 5869, | |||

s2 = flegendre(fx2) | DOI 10.17487/RFC5869, May 2010, | |||

if s2 == 1: | <https://www.rfc-editor.org/info/rfc5869>. | |||

y2 = fmul(fsqrt(fx2),e) | ||||

return (x2,y2) | ||||

x3 = fadd(finv(fsqr(w)),ONE) | [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves | |||

fx3 = fcurve(x3) | for Security", RFC 7748, DOI 10.17487/RFC7748, January | |||

y3 = fmul(fsqrt(fx3),e) | 2016, <https://www.rfc-editor.org/info/rfc7748>. | |||

return (x3,y3) | ||||

C.6. Elligator2 Method | [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, | |||

"PKCS #1: RSA Cryptography Specifications Version 2.2", | ||||

RFC 8017, DOI 10.17487/RFC8017, November 2016, | ||||

<https://www.rfc-editor.org/info/rfc8017>. | ||||

The following hacspec program implements map2curve_elligator2(alpha) | 13.2. Informative References | |||

for Curve25519. | ||||

from curve25519 import * | [AFQTZ14] Aranha, D., Fouque, P., Qian, C., Tibouchi, M., and J. | |||

from hacspec.speclib import * | Zapalowicz, "Binary Elligator squared", In Selected Areas | |||

in Cryptography - SAC 2014, pages 20-37, | ||||

DOI 10.1007/978-3-319-13051-4_2, 2014, | ||||

<https://doi.org/10.1007/978-3-319-13051-4_2>. | ||||

a25519 = to_felem(486662) | [AR13] Adj, G. and F. Rodriguez-Henriquez, "Square Root | |||

b25519 = to_felem(1) | Computation over Even Extension Fields", In IEEE | |||

u25519 = to_felem(2) | Transactions on Computers. vol 63 issue 11, | |||

pages 2829-2841, DOI 10.1109/TC.2013.145, November 2014, | ||||

<https://doi.org/10.1109/TC.2013.145>. | ||||

@typechecked | [BBJLP08] Bernstein, D., Birkner, P., Joye, M., Lange, T., and C. | |||

def f_25519(x:felem_t) -> felem_t: | Peters, "Twisted Edwards curves", In AFRICACRYPT 2008, | |||

return fadd(fmul(x, fsqr(x)), fadd(fmul(a25519, fsqr(x)), x)) | pages 389-405, DOI 10.1007/978-3-540-68164-9_26, 2008, | |||

<https://doi.org/10.1007/978-3-540-68164-9_26>. | ||||

@typechecked | [BCIMRT10] | |||

def map2curve25519(r:felem_t) -> felem_t: | Brier, E., Coron, J., Icart, T., Madore, D., Randriam, H., | |||

d = fsub(to_felem(p25519), fmul(a25519, finv(fadd(to_felem(1), fmul(u25519, fsqr(r)))))) | and M. Tibouchi, "Efficient Indifferentiable Hashing into | |||

power = nat((p25519 - 1) // 2) | Ordinary Elliptic Curves", In Advances in Cryptology - | |||

e = fexp(f_25519(d), power) | CRYPTO 2010, pages 237-254, | |||

x = 0 | DOI 10.1007/978-3-642-14623-7_13, 2010, | |||

if e != 1: | <https://doi.org/10.1007/978-3-642-14623-7_13>. | |||

x = fsub(to_felem(-d), to_felem(a25519)) | ||||

else: | ||||

x = d | ||||

return x | [BF01] Boneh, D. and M. Franklin, "Identity-based encryption from | |||

the Weil pairing", In Advances in Cryptology - CRYPTO | ||||

2001, pages 213-229, DOI 10.1007/3-540-44647-8_13, August | ||||

2001, <https://doi.org/10.1007/3-540-44647-8_13>. | ||||

C.7. hash2base | [BHKL13] Bernstein, D., Hamburg, M., Krasnova, A., and T. Lange, | |||

"Elligator: elliptic-curve points indistinguishable from | ||||

uniform random strings", In Proceedings of the 2013 ACM | ||||

SIGSAC conference on computer and communications | ||||

security., pages 967-980, DOI 10.1145/2508859.2516734, | ||||

November 2013, <https://doi.org/10.1145/2508859.2516734>. | ||||

The following procedure implements hash2base. | [BLMP19] Bernstein, D., Lange, T., Martindale, C., and L. Panny, | |||

"Quantum circuits for the CSIDH: optimizing quantum | ||||

evaluation of isogenies", In Advances in Cryptology - | ||||

EUROCRYPT 2019, DOI 10.1007/978-3-030-17656-3, 2019, | ||||

<https://doi.org/10.1007/978-3-030-17656-3>. | ||||

hash2base(x) | [BLS01] Boneh, D., Lynn, B., and H. Shacham, "Short signatures | |||

from the Weil pairing", In Journal of Cryptology, vol 17, | ||||

pages 297-319, DOI 10.1007/s00145-004-0314-9, July 2004, | ||||

<https://doi.org/10.1007/s00145-004-0314-9>. | ||||

Parameters: | [BLS03] Barreto, P., 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, 2003, | ||||

<https://doi.org/10.1007/3-540-36413-7_19>. | ||||

H - cryptographic hash function to use | [BMP00] Boyko, V., MacKenzie, P., and S. Patel, "Provably secure | |||

hbits - number of bits output by H | password-authenticated key exchange using Diffie-Hellman", | |||

p - order of the base field Fp | In Advances in Cryptology - EUROCRYPT 2000, pages 156-171, | |||

label - context label for domain separation | DOI 10.1007/3-540-45539-6_12, May 2000, | |||

<https://doi.org/10.1007/3-540-45539-6_12>. | ||||

Preconditions: | [BN05] Barreto, P. and M. Naehrig, "Pairing-Friendly Elliptic | |||

Curves of Prime Order", In Selected Areas in Cryptography | ||||

2005, pages 319-331, DOI 10.1007/11693383_22, 2006, | ||||

<https://doi.org/10.1007/11693383_22>. | ||||

floor(log2(p)) + 1 >= hbits | [BP18] Budroni, A. and F. Pintore, "Hashing to G2 on BLS pairing- | |||

friendly curves", In ACM Communications in Computer | ||||

Algebra, pages 63-66, DOI 10.1145/3313880.3313884, | ||||

September 2018, <https://doi.org/10.1145/3313880.3313884>. | ||||

Input: | [CFADLNV05] | |||

Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., | ||||

Nguyen, K., and F. Vercauteren, "Handbook of Elliptic and | ||||

Hyperelliptic Curve Cryptography", publisher Chapman and | ||||

Hall / CRC, ISBN 9781584885184, 2005, | ||||

<https://www.crcpress.com/9781584885184>. | ||||

x - an octet string to be hashed | [CK11] Couveignes, J. and J. Kammerer, "The geometry of flex | |||

tangents to a cubic curve and its parameterizations", | ||||

In Journal of Symbolic Computation, vol 47 issue 3, | ||||

pages 266-281, DOI 10.1016/j.jsc.2011.11.003, 2012, | ||||

<https://doi.org/10.1016/j.jsc.2011.11.003>. | ||||

Output: | [draft-yonezawa-pfc-01] | |||

Yonezawa, S., Chikara, S., Kobayashi, T., and T. Saito, | ||||

"Pairing-friendly Curves", March 2019, | ||||

<https://datatracker.ietf.org/doc/ | ||||

draft-yonezawa-pairing-friendly-curves/>. | ||||

y - a value in the field Fp | [F11] Farashahi, R., "Hashing into Hessian curves", | |||

In AFRICACRYPT 2011, pages 278-289, | ||||

DOI 10.1007/978-3-642-21969-6_17, 2011, | ||||

<https://doi.org/10.1007/978-3-642-21969-6_17>. | ||||

Steps: | [FFSTV13] Farashahi, R., Fouque, P., Shparlinski, I., Tibouch, M., | |||

and J. Voloch, "Indifferentiable deterministic hashing to | ||||

elliptic and hyperelliptic curves", In Math. Comp. vol 82, | ||||

pages 491-512, DOI 10.1090/S0025-5718-2012-02606-8, 2013, | ||||

<https://doi.org/10.1090/S0025-5718-2012-02606-8>. | ||||

1. t1 = H("h2c" || label || I2OSP(len(x), 4) || x) | [FIPS186-4] | |||

2. t2 = OS2IP(t1) | National Institute of Standards and Technology (NIST), | |||

3. y = t2 mod p | "FIPS Publication 186-4: Digital Signature Standard", July | |||

4. Output y | 2013, <https://nvlpubs.nist.gov/nistpubs/FIPS/ | |||

NIST.FIPS.186-4.pdf>. | ||||

where I2OSP, OS2IP [RFC8017] are used to convert an octet string to | [FJT13] Fouque, P., Joux, A., and M. Tibouchi, "Injective | |||

and from a non-negative integer, and a || b denotes concatenation of | encodings to elliptic curves", In ACISP 2013, | |||

a and b. | pages 203-218, DOI 10.1007/978-3-642-39059-3_14, 2013, | |||

<https://doi.org/10.1007/978-3-642-39059-3_14>. | ||||

C.7.1. Considerations | [FKR11] Fuentes-Castaneda, L., Knapp, E., and F. Rodriguez- | |||

Henriquez, "Fast Hashing to G2 on Pairing-Friendly | ||||

Curves", In Selected Areas in Cryptography, pages 412-430, | ||||

DOI 10.1007/978-3-642-28496-0_25, 2011, | ||||

<https://doi.org/10.1007/978-3-642-28496-0_25>. | ||||

Performance: hash2base requires hashing the entire input x. In some | [FSV09] Farashahi, R., Shparlinski, I., and J. Voloch, "On hashing | |||

algorithms/ciphersuite combinations, hash2base is called multiple | into elliptic curves", In Journal of Mathematical | |||

times. For large inputs, implementers can therefore consider hashing | Cryptology, vol 3 no 4, pages 353-360, | |||

x before calling hash2base. I.e. hash2base(H'(x)). | DOI 10.1515/JMC.2009.022, 2009, | |||

<https://doi.org/10.1515/JMC.2009.022>. | ||||

Most algorithms assume that hash2base maps its input to the base | [FT10] Fouque, P. and M. Tibouchi, "Estimating the size of the | |||

field uniformly. In practice, there will be inherent biases. For | image of deterministic hash functions to elliptic | |||

example, taking H as SHA256, over the finite field used by Curve25519 | curves.", In Progress in Cryptology - LATINCRYPT 2010, | |||

we have p = 2^255 - 19, and thus when reducing from 255 bits, the | pages 81-91, DOI 10.1007/978-3-642-14712-8_5, 2010, | |||

values of 0 .. 19 will be twice as likely to occur. This is a | <https://doi.org/10.1007/978-3-642-14712-8_5>. | |||

standard problem in generating uniformly distributed integers from a | ||||

bitstring. In this example, the resulting bias is negligible, but | ||||

for others this bias can be significant. | ||||

To address this, our hash2base algorithm greedily takes as many bits | [FT12] Fouque, P. and M. Tibouchi, "Indifferentiable Hashing to | |||

as possible before reducing mod p, in order to smooth out this bias. | Barreto-Naehrig Curves", In Progress in Cryptology - | |||

This is preferable to an iterated procedure, such as rejection | LATINCRYPT 2012, pages 1-7, | |||

sampling, since this can be hard to reliably implement in constant | DOI 10.1007/978-3-642-33481-8_1, 2012, | |||

time. | <https://doi.org/10.1007/978-3-642-33481-8_1>. | |||

The running time of each map2curve function is dominated by the cost | [hash2curve-repo] | |||

of finite field inversion. Assuming T_i(F) is the time of inversion | "Hashing to Elliptic Curves - GitHub repository", 2019, | |||

in field F, a rough bound on the running time of each map2curve | <https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve>. | |||

function is O(T_i(F)) for the associated field. | ||||

Appendix D. Test Vectors | [Icart09] Icart, T., "How to Hash into Elliptic Curves", In Advances | |||

in Cryptology - CRYPTO 2009, pages 303-316, | ||||

DOI 10.1007/978-3-642-03356-8_18, 2009, | ||||

<https://doi.org/10.1007/978-3-642-03356-8_18>. | ||||

This section contains test vectors, generated from reference Sage | [J96] Jablon, D., "Strong password-only authenticated key | |||

code, for each map2curve variant and the hash2base function described | exchange", In SIGCOMM Computer Communication Review, vol | |||

in Appendix C.7. | 26 issue 5, pages 5-26, DOI 10.1145/242896.242897, 1996, | |||

<https://doi.org/10.1145/242896.242897>. | ||||

D.1. Elligator2 to Curve25519 | [KLR10] Kammerer, J., Lercier, R., and G. Renault, "Encoding | |||

points on hyperelliptic curves over finite fields in | ||||

deterministic polynomial time", In PAIRING 2010, | ||||

pages 278-297, DOI 10.1007/978-3-642-17455-1_18, 2010, | ||||

<https://doi.org/10.1007/978-3-642-17455-1_18>. | ||||

Input: | [KSS08] Kachisa, E., Schaefer, E., and M. Scott, "Constructing | |||

Brezing-Weng Pairing-Friendly Elliptic Curves Using | ||||

Elements in the Cyclotomic Field", In Pairing-Based | ||||

Cryptography - Pairing 2008, pages 126-135, | ||||

DOI 10.1007/978-3-540-85538-5_9, 2008, | ||||

<https://doi.org/10.1007/978-3-540-85538-5_9>. | ||||

alpha = | [L13] Langley, A., "Implementing Elligator for Curve25519", | |||

2013, <https://www.imperialviolet.org/2013/12/25/ | ||||

elligator.html>. | ||||

Intermediate values: | [S05] Skalba, M., "Points on elliptic curves over finite | |||

fields", In Acta Arithmetica, vol 117 no 3, pages 293-301, | ||||

DOI 10.4064/aa117-3-7, 2005, | ||||

<https://doi.org/10.4064/aa117-3-7>. | ||||

u = 140876c725e59a161990918755b3eff6a9d5e75d69ea20f9a4ebcf | [S85] Schoof, R., "Elliptic Curves Over Finite Fields and the | |||

94e69ff013 | Computation of Square Roots mod p", In Mathematics of | |||

v = 6a262de4dba3a094ceb2d307fd985a018f55d1c7dafa3416423b46 | Computation vol 44 issue 170, pages 483-494, | |||

2c8aaff893 | DOI 10.1090/S0025-5718-1985-0777280-6, April 1985, | |||

gv = 5dc09f578dca7bfffeac3ec4ad2792c9822cd1d881839e823d26cd | <https://doi.org/10.1090/S0025-5718-1985-0777280-6>. | |||

338f6ddc3e | ||||

Output: | [SAGE] The Sage Developers, "SageMath, the Sage Mathematics | |||

Software System", 2019, <https://www.sagemath.org>. | ||||

x = 15d9d21b245c5f6b314d2cf80267a5fe70aa2e382505cbe9bdc4b9 | [SBCDBK09] | |||

d375489a54 | Scott, M., Benger, N., Charlemagne, M., Dominguez Perez, | |||

y = 1f132cbbfbb17d3f80eba862a6fb437650775de0b86624f5a40d3e | L., Benger, N., and E. Kachisa, "Fast Hashing to G2 on | |||

17739a07ff | Pairing-Friendly Curves", In Pairing-Based Cryptography - | |||

Pairing 2009, pages 102-113, | ||||

DOI 10.1007/978-3-642-03298-1_8, 2009, | ||||

<https://doi.org/10.1007/978-3-642-03298-1_8>. | ||||

Input: | [SEC2] Standards for Efficient Cryptography Group (SECG), "SEC 2: | |||

Recommended Elliptic Curve Domain Parameters", January | ||||

2010, <http://www.secg.org/sec2-v2.pdf>. | ||||

alpha = 00 | [SECG1] Standards for Efficient Cryptography Group (SECG), "SEC 1: | |||

Elliptic Curve Cryptography", May 2009, | ||||

<http://www.secg.org/sec1-v2.pdf>. | ||||

Intermediate values: | [SS04] Schinzel, A. and M. Skalba, "On equations y^2 = x^n + k in | |||

a finite field.", In Bulletin Polish Acad. Sci. Math. vol | ||||

52, no 3, pages 223-226, DOI 10.4064/ba52-3-1, 2004, | ||||

<https://doi.org/10.4064/ba52-3-1>. | ||||

u = 10a97c83decb52945a72fe18511ac9741234de3fb62fa0fec399df | [SW06] Shallue, A. and C. van de Woestijne, "Construction of | |||

5f390a6a21 | rational points on elliptic curves over finite fields", | |||

v = 6ff5b9893b26c0c8b68adb3d653b335a8e810b4abbdbc13348e828 | In Algorithmic Number Theory. ANTS 2006., pages 510-524, | |||

f74814f4c4 | DOI 10.1007/11792086_36, 2006, | |||

gv = 2d1599d36275c36cabf334c07c62934e940c3248a9d275041f3724 | <https://doi.org/10.1007/11792086_36>. | |||

819d7e8b22 | ||||

Output: | [T14] Tibouchi, M., "Elligator squared: Uniform points on | |||

elliptic curves of prime order as uniform random strings", | ||||

In Financial Cryptography and Data Security - FC 2014, | ||||

pages 139-156, DOI 10.1007/978-3-662-45472-5_10, 2014, | ||||

<https://doi.org/10.1007/978-3-662-45472-5_10>. | ||||

x = 6ff5b9893b26c0c8b68adb3d653b335a8e810b4abbdbc13348e828 | [TK17] Tibouchi, M. and T. Kim, "Improved elliptic curve hashing | |||

f74814f4c4 | and point representation", In Designs, Codes, and | |||

y = 55345d1e10a5fc1c56434494c47dcfa9c7983c07fcb908f7a38717 | Cryptography, vol 82, pages 161-177, | |||

ba869a2469 | DOI 10.1007/s10623-016-0288-2, 2017, | |||

<https://doi.org/10.1007/s10623-016-0288-2>. | ||||

Input: | [U07] Ulas, M., "Rational points on certain hyperelliptic curves | |||

over finite fields", In Bulletin Polish Acad. Sci. Math. | ||||

vol 55, no 2, pages 97-104, DOI 10.4064/ba55-2-1, 2007, | ||||

<https://doi.org/10.4064/ba55-2-1>. | ||||

alpha = ff | [W08] Washington, L., "Elliptic curves: Number theory and | |||

cryptography", edition 2nd, publisher Chapman and Hall / | ||||

CRC, ISBN 9781420071467, 2008, | ||||

<https://www.crcpress.com/9781420071467>. | ||||

Intermediate values: | [WB19] Wahby, R. and D. Boneh, "Fast and simple constant-time | |||

hashing to the BLS12-381 elliptic curve", Technical | ||||

report ePrint 2019/403, 2019, | ||||

<https://eprint.iacr.org/2019/403>. | ||||

u = 59c48eefc872abc09321ca7231ecd6c754c65244a86e6315e9e230 | Appendix A. Related Work | |||

716ed674d3 | ||||

v = 20392de0e96030c4a37cd6f650a86c6bc390bcec21919d9c544f35 | ||||

f2a2534b2b | ||||

gv = 0951a0c55b92e231494695cb775a0653a23f41635e11f97168e231 | ||||

095dd5c30c | ||||

Output: | The problem of mapping arbitrary bit strings to elliptic curve points | |||

has been the subject of both practical and theoretical research. | ||||

This section briefly describes the background and research results | ||||

that underly the recommendations in this document. This section is | ||||

provided for informational purposes only. | ||||

x = 5fc6d21f169fcf3b5c832909af5793943c6f4313de6e6263abb0ca | A naive but generally insecure method of mapping a string alpha to a | |||

0d5da547bc | point on an elliptic curve E having n points is to first fix a point | |||

y = 2b6bf1b3322717ed5640d04659757c8db6615c0dee954fbd695e8a | P that generates the elliptic curve group, and a hash function Hn | |||

c9d97e24d1 | from bit strings to integers less than n; then compute Hn(alpha) * P, | |||

where the * operator represents scalar multiplication. The reason | ||||

this approach is insecure is that the resulting point has a known | ||||

discrete log relationship to P. Thus, except in cases where this | ||||

method is specified by the protocol, it must not be used; doing so | ||||

risks catastrophic security failures. | ||||

Input: | Boneh et al. [BLS01] describe an encoding method they call | |||

MapToGroup, which works roughly as follows: first, use the input | ||||

string to initialize a pseudorandom number generator, then use the | ||||

generator to produce a pseudorandom value x in F. If x is the | ||||

x-coordinate of a point on the elliptic curve, output that point. | ||||

Otherwise, generate a new pseudorandom 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 expected number of tries | ||||

is just two. However, the running time of this method depends on the | ||||

input string, which means that it is not safe to use in protocols | ||||

sensitive to timing side channels. | ||||

alpha = ff0011223344112233441122334411223344556677885566778855 | Schinzel and Skalba [SS04] introduce the first method of constructing | |||

66778855667788 | elliptic curve points deterministically, for a restricted class of | |||

curves and a very small number of points. Skalba [S05] generalizes | ||||

this construction to more curves and more points on those curves. | ||||

Shallue and van de Woestijne [SW06] further generalize and simplify | ||||

Skalba's construction, yielding concretely efficient maps to a | ||||

constant fraction of the points on almost any curve. Ulas [U07] | ||||

describes a simpler version of this map, and Brier et al. [BCIMRT10] | ||||

give a further simplification, which the authors call the "simplified | ||||

SWU" map. The simplified map applies only to fields of | ||||

characteristic p = 3 mod 4; Wahby and Boneh [WB19] generalize to | ||||

fields of any characteristic. | ||||

Intermediate values: | Icart gives another deterministic algorithm which maps to any curve | |||

over a field of characteristic p = 2 mod 3 [Icart09]. Several | ||||

extensions and generalizations follow this work, including [FSV09], | ||||

[FT10], [KLR10], [F11], and [CK11]. | ||||

u = 380619de15c80fe3668bac96be51b0fd17129f6cf084a250cfaa76 | Following the work of Farashahi [F11], Fouque et al. [FJT13] | |||

7ff92b6cba | describe a mapping to curves of characteristic p = 3 mod 4 having a | |||

v = 2f3d9063e573c522d8f20c752f15b114f810b53d880154e2f30cde | number of points divisible by 4. Bernstein et al. [BHKL13] optimize | |||

fdf82bbe26 | this mapping and describe a related mapping that they call "Elligator | |||

gv = 4ce282b7cfdca2db63cec91a08b947f10fcf03bc69bafcd1c60b7d | 2," which applies to any curve over a field of odd characteristic | |||

dfc305baaf | having a point of order 2. This includes Curve25519 and Curve448, | |||

both of which are CFRG-recommended curves [RFC7748]. | ||||

Output: | An important caveat regarding all of the above deterministic mapping | |||

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

directly to construct a random oracle that outputs points on the | ||||

curve. | ||||

x = 2f3d9063e573c522d8f20c752f15b114f810b53d880154e2f30cde | Brier et al. [BCIMRT10] give two solutions to this problem. The | |||

fdf82bbe26 | first, which Brier et al. prove applies to Icart's method, computes | |||

y = 5e43ab6a0590c11547b910d06d37c96e4cc3fc91adf8a54494d74b | f(H0(msg)) + f(H1(msg)) for two distinct hash functions H0 and H1 | |||

12de6ae45d | 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 | ||||

but is more costly, computes f(H0(msg)) + H2(msg) * P, for P a | ||||

generator of the elliptic curve group and H2 a hash from bit strings | ||||

to integers modulo n, the order of the elliptic curve group. | ||||

Farashahi et al. [FFSTV13] improve the analysis of the first method, | ||||

showing that it applies to essentially all deterministic mappings. | ||||

Tibouchi and Kim [TK17] further refine the analysis and describe | ||||

additional optimizations. | ||||

D.2. Icart to P-384 | Complementary to the problem of mapping from bit strings to elliptic | |||

curve points, Bernstein et al. [BHKL13] study the problem of mapping | ||||

from elliptic curve points to uniformly random bit strings, giving | ||||

solutions for a class of curves including Montgomery and twisted | ||||

Edwards curves. Tibouchi [T14] and Aranha et al. [AFQTZ14] | ||||

generalize these results. This document does not deal with this | ||||

complementary problem. | ||||

Input: | Appendix B. Rational maps from twisted Edwards to Weierstrass and | |||

Montgomery curves | ||||

alpha = | The inverse of the rational map specified in Section 6.7.1, i.e., the | |||

map from the point (x', y') on the Weierstrass curve y'^2 = x'^3 + A | ||||

* x'^2 + B * x' to the point (x, y) on the twisted Edwards curve a * | ||||

x^2 + y^2 = 1 + d * x^2 * y^2 is given by: | ||||

Intermediate values: | o x' = (1 + y) / (B' * (1 - y)) | |||

u = 287d7ef77451ecd3c1c0428092a70b5ed870ca22681c81ac52037d | o y' = (1 + y) / (B' * x * (1 - y)) | |||

a7e22a3657d3538fa5ce30488b8e5fb95eb58dda86 | ||||

u4 = 56aee47e1e72dbae15bd0d5a8462d0228a5db9093268639e1cd015 | ||||

4aa3e63d81eea72c2d5fa4998f7ca971bb50b44df6 | ||||

v = eaa16e82d5a88ebb9ff1866640c34693d4de32fdca72921ed2fe4d | ||||

cfce3b163dea8ec9e528f7e3b5ca3e27cba5c97db9 | ||||

x1 = cbc52f2bf7f194a47fd88e3fa4f68fc41cddeea8c47f79c225ad80 | ||||

455c4db0e5db47209754764929327edf339c19203b | ||||

u6 = 5af8bcb067c1fc0bf3c7115481f3bd78afd70e035a9d067060c6e2 | ||||

164620d477e3247a55e514d0a790a7ddf58e7482fa | ||||

x1 = 871a993757d3aa90b7261aa76fc1d74b8b4dcfbc8505f1170e3707 | ||||

1ab59c9c3a88caa9d6331730503d2b4f94a592b147 | ||||

Output: | where | |||

x = b4e57fc7f87adbdc52ab843635313cdf5fb356550b6fbde5741f6b | o A = (a + d) / 2 | |||

51b12b33a104bfe2c68bef24139332c7e213f145d5 | ||||

y = bd3980b713d51ac0f719b6cc045e2168717b74157f6fd0e36d4501 | ||||

3e2b5c7e0d70dacbb2fb826ad12d3f8a0dc5dc801f | ||||

Input: | o B = (a - d)^2 / 16 | |||

alpha = 00 | o B' = 1 / sqrt(B) = 4 / (a - d) | |||

Intermediate values: | This map is undefined when y == 1 or x == 0. In this case, return | |||

the point (0, 0). | ||||

u = 5584733e5ee080c9dbfa4a91c5c8da5552cce17c74fae9d28380e6 | It may also be useful to map to a Montgomery curve of the form B' * | |||

623493df985a7827f02538929373de483477b23521 | y''^2 = x''^3 + A' * x''^2 + x''. This curve is equivalent to the | |||

u4 = 3f8451733c017a3e5acd8a310f5594ae539c74b009fc75aecda7f1 | twisted Edwards curve above via the following rational map | |||

abd42b3a47b1bd8b2b29eb3dd01db0a1bf67f5c15e | ([BBJLP08], Theorem 3.2): | |||

v = a20ff29b0a3d0067cb8a53e132753a46f598aa568efe00f9e286a5 | ||||

e4300c9010f58e3ed97b4b7b356347048f122ca2b8 | ||||

x1 = d8fcadbc05829f3d7d12493f8720514e2f125751f0dcf91ba8ee5d | ||||

4e3456528c1e155cc93ac525562d9c3fcb3e49d3e3 | ||||

u6 = 35340edd3abbe78fe33fd955e9126d67c6352db6ecbcbcf3abbaa5 | ||||

30ffa37724d3a51d9d046057d0fa76278f916fa10c | ||||

x1 = 382b470b52fbe5de86ed48a824ae3827a738b8cada54c9473d1eee | ||||

18b548b8f12389dcea7c47893e18aafad06ab8ff52 | ||||

Output: | o A' = 2 * (a + d) / (a - d) | |||

x = a15fe3979721e717f173c54d38882c011be02499d26a070a3bed82 | o B' = 4 / (a - d) | |||

5fcac5a251a1297a9593254a50f8aa243c6191976a | ||||

y = 641d1cb53087208240a935769ca1b99c3a97a492526e5b3cfae8c2 | ||||

0bebde9345c4dd549e2d01d5417918ce039451f4d7 | ||||

Input: | o x'' = (1 + y) / (1 - y) | |||

alpha = ff | o y'' = (1 + y) / (x * (1 - y)) | |||

Intermediate values: | Appendix C. Isogenous curves and corresponding maps for BLS12-381 | |||

u = d25e7c84dcdf5b32e8ff5ae510026628d7427b2341c9d885f753a9 | This section specifies the isogeny maps for the BLS12-381 suites | |||

72b21e3c82881ab0a2845ec645dd9d6fd4f3c74cb3 | listed in Section 8.7. | |||

u4 = 60cbd41d32d7588ff3634655bd5e5ef6ab9077b7629bb648669cf8 | ||||

bef00c87b3c7c59bed55d6db75a59fc988ee84db41 | ||||

v = f3e63b1b10195a28833f391d480df124be3c1cbbaa0c7b5b0252db | ||||

405ba97a10d19a6afd134f1c829fd8fba36a3ea5a5 | ||||

x1 = 9d4c43b595deb99138eb0f7688695abe8a7145d4b8f1f911b8384b | ||||

0205c873cfcb6a6092e71b887e0a56e8633987fa7e | ||||

u6 = bb44318a26c920aa39270421eb8ff73aac89637d01e6b32697fbd2 | ||||

c6097d3143fbe8e192372a25be723a0008bcf64326 | ||||

x1 = aa283d625fdb4d127611e359d6bd6a2d1e63f036a2d9d1373c11d9 | ||||

1a557ffe24ec208f0408763c524112147fd78fd15e | ||||

Output: | C.1. 11-isogeny map for G1 | |||

x = 26536b1be6480de4e8d3232e17312085d2fc5b4ad18aae3edfe1f6 | The 11-isogeny map from E' to E is given by the following rational | |||

2c192ebcbed4711aba15be7af83ef691e09aded56c | functions: | |||

y = 7533cf819fa713699f4919f79fc0f01c9b632f2e08a5ae34de7d9e | ||||

1069b18b256924b9acb7db85c707fb40ef893e4b9e | ||||

Input: | o x = x_num / x_den, where | |||

alpha = ff0011223344112233441122334411223344556677885566778855 | * x_num = k_(1,11) * x'^11 + k_(1,10) * x'^10 + ... + k_(1,0) | |||

66778855667788 | ||||

Intermediate values: | * x_den = x'^10 + k_(2,9) * x'^9 + ... + k_(2,0) | |||

u = e1a5025e8e9b6776263767613cd90b685a46fe462c914aaf7dab3b | o y = y' * y_num / y_den, where | |||

2ac7b7f6479e6de0790858fae8471beda1d93117c2 | ||||

u4 = be47baa8671fb710a0cf58c85d95ea9cef2a7d6a6d859f3dbc52be | ||||

fde3ad898851a83e166b87eeb7870ce1d3427a56b5 | ||||

v = 24ed8cb050c045f6401a6221b85c37d482197f54a7340303449c13 | ||||

52717394450495f4bfa8c0bc12181496db59113671 | ||||

x1 = a1e180da2f619774632fccb74133963606ffaec0545dcdf225e180 | ||||

3f04d7bd9fb612bf57145004905142a35a5d1b47f0 | ||||

u6 = e806b407afd7874ad4ded43a46bc002e0dda1a39a5754cf09dfcb9 | ||||

9cfc8d19750a4a7e825e06ac256166b91ee3f5e28d | ||||

x1 = 41d5d81708d776d643b75fd29658c14fddaf009d8f47a9ec18b9d3 | ||||

bee961f1544dd7339e6115bffbe638a17658cea94a | ||||

Output: | * y_num = k_(3,15) * x'^15 + k_(3,14) * x'^14 + ... + k_(3,0) | |||

x = 810096c7dec85367fa04f706c2e456334325202b9fcbc34970d9fd | * y_den = x'^15 + k_(4,14) * x'^14 + ... + k_(4,0) | |||

f545c507debc328246489e3c9a8d576b97e6e104d8 | ||||

y = ddde061cec66efc0cfcdabdc0241fdb00ab2ad28bf8e00dc0d45f8 | ||||

845c00b6e5c803b133c8deb31b4922d83649c4c249 | ||||

D.3. SWU to P-256 | The constants used to compute x_num are as follows: | |||

Input: | ||||

alpha = | o k_(1,0) = 0x11a05f2b1e833340b809101dd99815856b303e88a2d7005ff2627b | |||

56cdb4e2c85610c2d5f2e62d6eaeac1662734649b7 | ||||

Intermediate values: | o k_(1,1) = 0x17294ed3e943ab2f0588bab22147a81c7c17e75b2f6a8417f565e3 | |||

3c70d1e86b4838f2a6f318c356e834eef1b3cb83bb | ||||

u = d8e1655d6562677a74be47c33ce9edcbefd5596653650e5758c8aa | o k_(1,2) = 0xd54005db97678ec1d1048c5d10a9a1bce032473295983e56878e50 | |||

ab65a99db3 | 1ec68e25c958c3e3d2a09729fe0179f9dac9edcb0 | |||

v = 7764572395df002912b7cbb93c9c287f325b57afa1e7e82618ba57 | ||||

9b796e6ad1 | ||||

x1 = 7764572395df002912b7cbb93c9c287f325b57afa1e7e82618ba57 | ||||

9b796e6ad1 | ||||

gv = 0d8af0935d993caaefca7ef912e06415cbe7e00a93cca295237c66 | ||||

7f0cc2f941 | ||||

gx1 = 0d8af0935d993caaefca7ef912e06415cbe7e00a93cca295237c66 | ||||

7f0cc2f941 | ||||

n1 = ef66b409fa309a99e4dd4a1922711dea3899259d4a5947b3a0e3fe | ||||

34efdfc0cf | ||||

x2 = 2848af84de537f96c3629d93a78b37413a8b07c72248be8eac61fa | ||||

a058cedf96 | ||||

gx2 = 3aeb1a6a81f78b9176847f84ab7987f361cb486846d4dbf3e45af2 | ||||

d9354fb36a | ||||

x3 = 4331afd86e99e4fc7a3e5f0ca7b8a62c3c9f0146dac5f75b6990fe | ||||

60b8293e8e | ||||

gx3 = 1d78aa2bd9ff7c11c53807622c4d476ed67ab3c93206225ae437f0 | ||||

86ebaa2982 | ||||

y1 = 574e9564a28b9104b9dfb104a976f5f6a07c5c5b69e901e596df26 | ||||

e4f571e369 | ||||

Output: | o k_(1,3) = 0x1778e7166fcc6db74e0609d307e55412d7f5e4656a8dbf25f1b332 | |||

89f1b330835336e25ce3107193c5b388641d9b6861 | ||||

x = 7764572395df002912b7cbb93c9c287f325b57afa1e7e82618ba57 | o k_(1,4) = 0xe99726a3199f4436642b4b3e4118e5499db995a1257fb3f086eeb6 | |||

9b796e6ad1 | 5982fac18985a286f301e77c451154ce9ac8895d9 | |||

y = 574e9564a28b9104b9dfb104a976f5f6a07c5c5b69e901e596df26 | ||||

e4f571e369 | ||||

Input: | o k_(1,5) = 0x1630c3250d7313ff01d1201bf7a74ab5db3cb17dd952799b9ed3ab | |||

9097e68f90a0870d2dcae73d19cd13c1c66f652983 | ||||

alpha = 00 | o k_(1,6) = 0xd6ed6553fe44d296a3726c38ae652bfb11586264f0f8ce19008e21 | |||

8f9c86b2a8da25128c1052ecaddd7f225a139ed84 | ||||

Intermediate values: | o k_(1,7) = 0x17b81e7701abdbe2e8743884d1117e53356de5ab275b4db1a682c6 | |||

2ef0f2753339b7c8f8c8f475af9ccb5618e3f0c88e | ||||

u = c4188ee0e554dae7aea559d04d45982d6b184eff86c4a910a43247 | o k_(1,8) = 0x80d3cf1f9a78fc47b90b33563be990dc43b756ce79f5574a2c596c | |||

44d6fb3c62 | 928c5d1de4fa295f296b74e956d71986a8497e317 | |||

v = 0e82c0c07eb17c24c84f4a83fdd6195c23f76d455ba7a8d5bc3f62 | ||||

0cee20caf9 | ||||

x1 = 0e82c0c07eb17c24c84f4a83fdd6195c23f76d455ba7a8d5bc3f62 | ||||

0cee20caf9 | ||||

gv = 4914f49c40cb5c561bfeded5762d4bbf652e236f890ae752ea1046 | ||||

0be2939c3a | ||||

gx1 = 4914f49c40cb5c561bfeded5762d4bbf652e236f890ae752ea1046 | ||||

0be2939c3a | ||||

n1 = ae5000e861347ff29e3368597174b1a0a04b9b08019f59936aa65f | ||||

7e3176cf03 | ||||

x2 = 331a4d8dead257f3d36e239e9cfaeaaf6804354a5897da421db73a | ||||

795c3f9af7 | ||||

gx2 = b3dda8702e046be4e2bd42e2c9f09fddbc98a3fe04bd91ca8a1904 | ||||

5684be9d81 | ||||

x3 = 1133498ac9e96b683271586be695ca43a946aa320eb32e79662476 | ||||

6ac7d1cc60 | ||||

gx3 = 7cd39b42a3b487dc6c2782a5aebd123502b9fecc849be21766c8a0 | ||||

0ca16c318f | ||||

y2 = 6c6fa249077e13be24cf2cfab67dfcc8407a299e69c817785b8b9a | ||||

23eecfe734 | ||||

Output: | o k_(1,9) = 0x169b1f8e1bcfa7c42e0c37515d138f22dd2ecb803a0c5c99676314 | |||

baf4bb1b7fa3190b2edc0327797f241067be390c9e | ||||

x = 331a4d8dead257f3d36e239e9cfaeaaf6804354a5897da421db73a | o k_(1,10) = 0x10321da079ce07e272d8ec09d2565b0dfa7dccdde6787f96d50af | |||

795c3f9af7 | 36003b14866f69b771f8c285decca67df3f1605fb7b | |||

y = 6c6fa249077e13be24cf2cfab67dfcc8407a299e69c817785b8b9a | ||||

23eecfe734 | ||||

Input: | o k_(1,11) = 0x6e08c248e260e70bd1e962381edee3d31d79d7e22c837bc23c0bf | |||

1bc24c6b68c24b1b80b64d391fa9c8ba2e8ba2d229 | ||||

alpha = ff | The constants used to compute x_den are as follows: | |||

Intermediate values: | o k_(2,0) = 0x8ca8d548cff19ae18b2e62f4bd3fa6f01d5ef4ba35b48ba9c95886 | |||

17fc8ac62b558d681be343df8993cf9fa40d21b1c | ||||

u = 777b56233c4bdb9fe7de8b046189d39e0b2c2add660221e7c4a2d4 | o k_(2,1) = 0x12561a5deb559c4348b4711298e536367041e8ca0cf0800c0126c2 | |||

58c3034df2 | 588c48bf5713daa8846cb026e9e5c8276ec82b3bff | |||

v = 51a60aedc0ade7769bd04a4a3241130e00c7adaa9a1f76f1e115f1 | ||||

d082902b02 | ||||

x1 = 51a60aedc0ade7769bd04a4a3241130e00c7adaa9a1f76f1e115f1 | ||||

d082902b02 | ||||

gv = f7ba284fd26c0cb7b678f71caecbd9bf88890ddba48b596927c70b | ||||

f805ef5eba | ||||

gx1 = f7ba284fd26c0cb7b678f71caecbd9bf88890ddba48b596927c70b | ||||

f805ef5eba | ||||

n1 = a437e699818d87069a6e4d5298f26f19fd301835eb33b0a3936e3b | ||||

bd1507d680 | ||||

x2 = 7236d245e18dfd43dd756a2d048c6e491bb9ebfc2caa627e315d49 | ||||

b1e02957fc | ||||

gx2 = 9d6ebf27637ca38ee894e5052b989021b7d76fa2b01053ce054295 | ||||

54a205c047 | ||||

x3 = 90553fadf8a170464497621e7f2ffcc35d17af4107b79dab6d2a12 | ||||

6ea692c9db | ||||

gx3 = d7d141749e2e8e4b2253d4ef22e3ba7c7970e604e03b59277aed10 | ||||

32f02c1a11 | ||||

y1 = 4115534ea22d3b46a9c541a25e72b3f37a2ac7635a6bebb16ff504 | ||||

c3170fb69a | ||||

Output: | o k_(2,2) = 0xb2962fe57a3225e8137e629bff2991f6f89416f5a718cd1fca64e0 | |||

0b11aceacd6a3d0967c94fedcfcc239ba5cb83e19 | ||||

x = 51a60aedc0ade7769bd04a4a3241130e00c7adaa9a1f76f1e115f1 | o k_(2,3) = 0x3425581a58ae2fec83aafef7c40eb545b08243f16b1655154cca8a | |||

d082902b02 | bc28d6fd04976d5243eecf5c4130de8938dc62cd8 | |||

y = 4115534ea22d3b46a9c541a25e72b3f37a2ac7635a6bebb16ff504 | ||||

c3170fb69a | ||||

Input: | o k_(2,4) = 0x13a8e162022914a80a6f1d5f43e7a07dffdfc759a12062bb8d6b44 | |||

e833b306da9bd29ba81f35781d539d395b3532a21e | ||||

alpha = ff0011223344112233441122334411223344556677885566778855 | o k_(2,5) = 0xe7355f8e4e667b955390f7f0506c6e9395735e9ce9cad4d0a43bce | |||

66778855667788 | f24b8982f7400d24bc4228f11c02df9a29f6304a5 | |||

Intermediate values: | o k_(2,6) = 0x772caacf16936190f3e0c63e0596721570f5799af53a1894e2e073 | |||

062aede9cea73b3538f0de06cec2574496ee84a3a | ||||

u = 87541ffa2efec46a38875330f66a6a53b99edce4e407e06cd0ccaf | o k_(2,7) = 0x14a7ac2a9d64a8b230b3f5b074cf01996e7f63c21bca68a81996e1 | |||

39f8208aa6 | cdf9822c580fa5b9489d11e2d311f7d99bbdcc5a5e | |||

v = 3dbb1902335f823df0d4fe0797456bfee25d0a2016ae6e357197c4 | ||||

122bf7e310 | ||||

x1 = 3dbb1902335f823df0d4fe0797456bfee25d0a2016ae6e357197c4 | ||||

122bf7e310 | ||||

gv = 2704056d76b889ce788ab5cc68fd932f3d7cb125d0dbe0afba9dd7 | ||||

655d0651ed | ||||

gx1 = 2704056d76b889ce788ab5cc68fd932f3d7cb125d0dbe0afba9dd7 | ||||

655d0651ed | ||||

n1 = 43b52359e2739c205b2e4c8a0b3cd6842feb2ed131ec37fc0788eb | ||||

264dc1999b | ||||

x2 = 39150bdb341015403c27154093cd0382d61d27dafe1dbe70836832 | ||||

23bc3e1b2a | ||||

gx2 = 0985d428671b570b3c94dbaa2c4f160095db00a3d79b738ce488ca | ||||

8b45971d03 | ||||

x3 = 30cf2e681176c3e50b36842e3ee7623ba0577f6a1a0572448ab5ba | ||||

4bcf9c3d71 | ||||

gx3 = ea7c1f13e2ab39240d1d74e884f0878d21020fd73b7f4f84c7d9ad | ||||

72d0d09ae0 | ||||

y2 = 71b6dea4bc8dcae3dab695b69f25a7dbdc4e00f4926407bad89a80 | ||||

ab12655340 | ||||

Output: | o k_(2,8) = 0xa10ecf6ada54f825e920b3dafc7a3cce07f8d1d7161366b74100da | |||

67f39883503826692abba43704776ec3a79a1d641 | ||||

x = 39150bdb341015403c27154093cd0382d61d27dafe1dbe70836832 | o k_(2,9) = 0x95fc13ab9e92ad4476d6e3eb3a56680f682b4ee96f7d03776df533 | |||

23bc3e1b2a | 978f31c1593174e4b4b7865002d6384d168ecdd0a | |||

y = 71b6dea4bc8dcae3dab695b69f25a7dbdc4e00f4926407bad89a80 | ||||

ab12655340 | ||||

D.4. Simple SWU to P-256 | The constants used to compute y_num are as follows: | |||

Input: | ||||

alpha = | o k_(3,0) = 0x90d97c81ba24ee0259d1f094980dcfa11ad138e48a869522b52af6 | |||

c956543d3cd0c7aee9b3ba3c2be9845719707bb33 | ||||

Intermediate values: | o k_(3,1) = 0x134996a104ee5811d51036d776fb46831223e96c254f383d0f9063 | |||

43eb67ad34d6c56711962fa8bfe097e75a2e41c696 | ||||

u = 650354c1367c575b44d039f35a05f2201b3b3d2a93bf4ad6e5535b | o k_(3,2) = 0xcc786baa966e66f4a384c86a3b49942552e2d658a31ce2c344be4b | |||

bb5838c24e | 91400da7d26d521628b00523b8dfe240c72de1f6 | |||

n1 = 88d14bad9d79058c1427aa778892529b513234976ce84015c795f3 | ||||

b3c1860963 | ||||

x1 = c55836cadcb8cdfd9b9e345c88aa0af67db2d32e6e527de7a5b7a8 | ||||

59a3f6a2d3 | ||||

gx1 = 9104bf247de931541fedfd4a483ced90fd3ac32f4bbbb0de021a21 | ||||

f770fcc7ae | ||||

x2 = 0243b55837314f184ed8eca38b733945ec124ffd079850de608c9d | ||||

175aed9d29 | ||||

gx2 = 0f522f68139c6a8ff028c5c24536069441c3eae8a68d49939b2019 | ||||

0a87e2f170 | ||||

y2 = 29b59b5c656bfd740b3ea8efad626a01f072eb384f2db56903f67f | ||||

e4fbb6ff82 | ||||

Output: | o k_(3,3) = 0x1f86376e8981c217898751ad8746757d42aa7b90eeb791c09e4a3e | |||

c03251cf9de405aba9ec61deca6355c77b0e5f4cb | ||||

x = 0243b55837314f184ed8eca38b733945ec124ffd079850de608c9d | o k_(3,4) = 0x8cc03fdefe0ff135caf4fe2a21529c4195536fbe3ce50b879833fd | |||

175aed9d29 | 221351adc2ee7f8dc099040a841b6daecf2e8fedb | |||

y = 29b59b5c656bfd740b3ea8efad626a01f072eb384f2db56903f67f | ||||

e4fbb6ff82 | ||||

Input: | o k_(3,5) = 0x16603fca40634b6a2211e11db8f0a6a074a7d0d4afadb7bd76505c | |||

3d3ad5544e203f6326c95a807299b23ab13633a5f0 | ||||

alpha = 00 | o k_(3,6) = 0x4ab0b9bcfac1bbcb2c977d027796b3ce75bb8ca2be184cb5231413 | |||

c4d634f3747a87ac2460f415ec961f8855fe9d6f2 | ||||

Intermediate values: | o k_(3,7) = 0x987c8d5333ab86fde9926bd2ca6c674170a05bfe3bdd81ffd038da | |||

6c26c842642f64550fedfe935a15e4ca31870fb29 | ||||

u = 54acd0c1b3527a157432500fc3403b6f8a0aa0103d6966b783614a | o k_(3,8) = 0x9fc4018bd96684be88c9e221e4da1bb8f3abd16679dc26c1e8b6e6 | |||

8e41c9c5b1 | a1f20cabe69d65201c78607a360370e577bdba587 | |||

n1 = bb27567ea0729adc2b7af65a85b7f599559b107ce0d2495c4d26d8 | ||||

a1ce842372 | ||||

x1 = 6ae899e0232f040f8a82934f462e1ccedac76ad8549ae581f17c82 | ||||

1a5944244f | ||||

gx1 = 8a78bbf9c2156533fa0d9d37533752508a061b90108675ad705009 | ||||

7adabff9cb | ||||

x2 = 498c0e2faee29adf4e6aed9120eb8c69cd3bb7206bcd47a746fb5e | ||||

d4ed5529a5 | ||||

gx2 = 63adfce3aaa4d56b70cc3e8e7475154b5963855e275ffc26858cbf | ||||

2456ea5f52 | ||||

y1 = 3b81976ce93e79d2ba13394a6b5deb34602d6829f4625d987fc98c | ||||

a79d5d5c98 | ||||

Output: | o k_(3,9) = 0xe1bba7a1186bdb5223abde7ada14a23c42a0ca7915af6fe06985e7 | |||

ed1e4d43b9b3f7055dd4eba6f2bafaaebca731c30 | ||||

x = 6ae899e0232f040f8a82934f462e1ccedac76ad8549ae581f17c82 | o k_(3,10) = 0x19713e47937cd1be0dfd0b8f1d43fb93cd2fcbcb6caf493fd1183 | |||

1a5944244f | e416389e61031bf3a5cce3fbafce813711ad011c132 | |||

y = 3b81976ce93e79d2ba13394a6b5deb34602d6829f4625d987fc98c | ||||

a79d5d5c98 | ||||

Input: | o k_(3,11) = 0x18b46a908f36f6deb918c143fed2edcc523559b8aaf0c2462e6bf | |||

e7f911f643249d9cdf41b44d606ce07c8a4d0074d8e | ||||

alpha = ff | o k_(3,12) = 0xb182cac101b9399d155096004f53f447aa7b12a3426b08ec02710 | |||

e807b4633f06c851c1919211f20d4c04f00b971ef8 | ||||

Intermediate values: | o k_(3,13) = 0x245a394ad1eca9b72fc00ae7be315dc757b3b080d4c158013e663 | |||

2d3c40659cc6cf90ad1c232a6442d9d3f5db980133 | ||||

u = 86855e4bc3905ae04f6b284820856db6809633c5046ed92816a4e9 | o k_(3,14) = 0x5c129645e44cf1102a159f748c4a3fc5e673d81d7e86568d9ab0f | |||

976e994818 | 5d396a7ce46ba1049b6579afb7866b1e715475224b | |||

n1 = 5ec1cf436c1a2e84b53674bcf2470a0aeeda9550c474b06da4bda8 | ||||

3bda56f2e3 | ||||

x1 = 04e73147d10de271f7d77a9a3d6dd761d5b892ab39224b9dab93a2 | ||||

50139b124a | ||||

gx1 = 9d26bdc1b5afe7ccf9a7963a099e3c0b98070525b7ed08e8f32f44 | ||||

aef918b15f | ||||

x2 = 28566b4d673bf59f00d42771968bd69b1a54e8b557857ba231cbdd | ||||

feb18b38b5 | ||||

gx2 = 3b7edb432f00509ed44a4e6a2cbdbc69321215097953dac5bab8a9 | ||||

01a1d0d998 | ||||

y2 = 6644bab658f2915f2129791db0eb29eaeb34036db1bced721b161e | ||||

06caaef008 | ||||

Output: | o k_(3,15) = 0x15e6be4e990f03ce4ea50b3b42df2eb5cb181d8f84965a3957add | |||

4fa95af01b2b665027efec01c7704b456be69c8b604 | ||||

x = 28566b4d673bf59f00d42771968bd69b1a54e8b557857ba231cbdd | The constants used to compute y_den are as follows: | |||

feb18b38b5 | ||||

y = 6644bab658f2915f2129791db0eb29eaeb34036db1bced721b161e | ||||

06caaef008 | ||||

Input: | o k_(4,0) = 0x16112c4c3a9c98b252181140fad0eae9601a6de578980be6eec323 | |||

2b5be72e7a07f3688ef60c206d01479253b03663c1 | ||||

alpha = ff0011223344112233441122334411223344556677885566778855 | o k_(4,1) = 0x1962d75c2381201e1a0cbd6c43c348b885c84ff731c4d59ca4a103 | |||

66778855667788 | 56f453e01f78a4260763529e3532f6102c2e49a03d | |||

Intermediate values: | o k_(4,2) = 0x58df3306640da276faaae7d6e8eb15778c4855551ae7f310c35a5d | |||

d279cd2eca6757cd636f96f891e2538b53dbf67f2 | ||||

u = 34a8fc904e2d40dabb826b914917a6feea97ec3c0828f41c8716b2 | o k_(4,3) = 0x16b7d288798e5395f20d23bf89edb4d1d115c5dbddbcd30e123da4 | |||

6f8f4b7aaf | 89e726af41727364f2c28297ada8d26d98445f5416 | |||

n1 = 3b14efe9953378860e667b9051f9e412811e71b489ad8b72a8856f | ||||

e57a5473d9 | ||||

x1 = 8ac342ff43931be5b1a9de4f602994853fa9ec943eacc5e39760df | ||||

73fb4d9799 | ||||

gx1 = b45e916f6478943e1baf89e559c38f95457f2cadc1aaa8d54b0cac | ||||

9507ebc6ba | ||||

x2 = f9e15f7507632859104da82a28882021608b2c41f2fce3b1a82e43 | ||||

2841284ec7 | ||||

gx2 = 1940c3ff4cd98e41cdc5e863eb355168b5d794af03ca374244c7ac | ||||

94c5e2f7b0 | ||||

y2 = 180369d261ec6086346e6b2d36990a3aaa803558f1398b6816c3c6 | ||||

18d41ff73e | ||||

Output: | o k_(4,4) = 0xbe0e079545f43e4b00cc912f8228ddcc6d19c9f0f69bbb0542eda0 | |||

fc9dec916a20b15dc0fd2ededda39142311a5001d | ||||

x = f9e15f7507632859104da82a28882021608b2c41f2fce3b1a82e43 | o k_(4,5) = 0x8d9e5297186db2d9fb266eaac783182b70152c65550d881c5ecd87 | |||

2841284ec7 | b6f0f5a6449f38db9dfa9cce202c6477faaf9b7ac | |||

y = 180369d261ec6086346e6b2d36990a3aaa803558f1398b6816c3c6 | ||||

18d41ff73e | ||||

D.5. Boneh-Franklin to P-503 | o k_(4,6) = 0x166007c08a99db2fc3ba8734ace9824b5eecfdfa8d0cf8ef5dd365 | |||

bc400a0051d5fa9c01a58b1fb93d1a1399126a775c | ||||

The P-503 curve is a supersingular curve defined as "y^2=x^3+1" over | o k_(4,7) = 0x16a3ef08be3ea7ea03bcddfabba6ff6ee5a4375efa1f4fd7feb34f | |||

"GF(p)", where "p = 2^250*3^159-1". | d206357132b920f5b00801dee460ee415a15812ed9 | |||

Input: | o k_(4,8) = 0x1866c8ed336c61231a1be54fd1d74cc4f9fb0ce4c6af5920abc575 | |||

0c4bf39b4852cfe2f7bb9248836b233d9d55535d4a | ||||

alpha = | o k_(4,9) = 0x167a55cda70a6e1cea820597d94a84903216f763e13d87bb530859 | |||

2e7ea7d4fbc7385ea3d529b35e346ef48bb8913f55 | ||||

Intermediate values: | o k_(4,10) = 0x4d2f259eea405bd48f010a01ad2911d9c6dd039bb61a6290e591b | |||

36e636a5c871a5c29f4f83060400f8b49cba8f6aa8 | ||||

u = 198008fe3da9ee741c2ff07b9d4732df88a3cb98e8227b2cf49d55 | o k_(4,11) = 0xaccbb67481d033ff5852c1e48c50c477f94ff8aefce42d28c0f9a | |||

57aec1e61d1d29f460c6e4572b2baa21d2444d64d59cdcd2c0dfa2 | 88cea7913516f968986f7ebbea9684b529e2561092 | |||

0144dfab7e92a83e00 | ||||

t0 = 1f6bb1854a1ff7db82b43c235727d998fe28889152ec4efa533994 | ||||

fc6d0e77cd9f3ddb8c46226de8e5de75f705370944b809fe0ca092 | ||||

8587addb9c54ae1a05 | ||||

t1 = 1f6bb1854a1ff7db82b43c235727d998fe28889152ec4efa533994 | ||||

fc6d0e77cd9f3ddb8c46226de8e5de75f705370944b809fe0ca092 | ||||

8587addb9c54ae1a04 | ||||

x = 04671bff33e7f9f7905848cd4c0fc652bd22200eedf29ef8e13ccb | ||||

5536e4aa11db4366d2f346070d63c994bf0a4b1a4e555d6b3d021a | ||||

eba340b641ada82054 | ||||

Output: | o k_(4,12) = 0xad6b9514c767fe3c3613144b45f1496543346d98adf02267d5cee | |||

f9a00d9b8693000763e3b90ac11e99b138573345cc | ||||

x = 04671bff33e7f9f7905848cd4c0fc652bd22200eedf29ef8e13ccb | o k_(4,13) = 0x2660400eb2e4f3b628bdd0d53cd76f2bf565b94e72927c1cb748d | |||

5536e4aa11db4366d2f346070d63c994bf0a4b1a4e555d6b3d021a | f27942480e420517bd8714cc80d1fadc1326ed06f7 | |||

eba340b641ada82054 | ||||

y = 198008fe3da9ee741c2ff07b9d4732df88a3cb98e8227b2cf49d55 | ||||

57aec1e61d1d29f460c6e4572b2baa21d2444d64d59cdcd2c0dfa2 | ||||

0144dfab7e92a83e00 | ||||

Input: | o k_(4,14) = 0xe0fa1d816ddc03e6b24255e0d7819c171c40f65e273b853324efc | |||

d6356caa205ca2f570f13497804415473a1d634b8f | ||||

alpha = 00 | C.2. 3-isogeny map for G2 | |||

Intermediate values: | The 3-isogeny map from E' to E is given by the following rational | |||

functions: | ||||

u = 30e30a56d82cdca830f08d729ce909fc1ffec68df49ba75f9a1af7 | o x = x_num / x_den, where | |||

2ca242e92742f34b474a299bb452c6a71b69bdc9ee2403eaac7c84 | ||||

120a160737d667e29e | ||||

t0 = 0a64d9f288a0881bb6addebc0db89f146b282b05570efa3419f5d3 | ||||

2f11ec7bb449a1da8b33817642f01db039f838ad0bd459ec03e76d | ||||

8eec3a1e79d6c63f79 | ||||

t1 = 0a64d9f288a0881bb6addebc0db89f146b282b05570efa3419f5d3 | ||||

2f11ec7bb449a1da8b33817642f01db039f838ad0bd459ec03e76d | ||||

8eec3a1e79d6c63f78 | ||||

x = 0970ff4bb9237704cc30f5b0d80a9d97001064ab4cdb98de74f8d7 | ||||

283b922726406393c07ad01de0499e46ebc0ed1cd116112cf8965f | ||||

b8f918205adb13d3da | ||||

Output: | * x_num = k_(1,3) * x'^3 + k_(1,2) * x'^2 + ... + k_(1,0) | |||

x = 0970ff4bb9237704cc30f5b0d80a9d97001064ab4cdb98de74f8d7 | * x_den = x'^2 + k_(2,1) * x' + k_(2,0) | |||

283b922726406393c07ad01de0499e46ebc0ed1cd116112cf8965f | ||||

b8f918205adb13d3da | ||||

y = 30e30a56d82cdca830f08d729ce909fc1ffec68df49ba75f9a1af7 | ||||

2ca242e92742f34b474a299bb452c6a71b69bdc9ee2403eaac7c84 | ||||

120a160737d667e29e | ||||

Input: | o y = y' * y_num / y_den, where | |||

alpha = ff | * y_num = k_(3,3) * x'^3 + k_(3,2) * x'^2 + ... + k_(3,0) | |||

Intermediate values: | * y_den = x'^3 + k_(4,2) * x'^2 + ... + k_(4,0) | |||

u = 3808ae24b17af9147bd16077e3e83aff5c579784c8a1443d90e5ff | The constants used to compute x_num are as follows: | |||

e2451bfabacba73ee8b8f652b991290f5c64b34b1a4c9a498e21d4 | ||||

3d000dae7f8860200a | ||||

t0 = 2282d37dce4761dad69d1fe012c8580ba4e23158a0621fb3f51813 | ||||

10e7275e95573c89a8f0cda7ad98ca9e0a9e04ef94a1a79685d069 | ||||

6ac6ad423a0de96b7d | ||||

t1 = 2282d37dce4761dad69d1fe012c8580ba4e23158a0621fb3f51813 | ||||

10e7275e95573c89a8f0cda7ad98ca9e0a9e04ef94a1a79685d069 | ||||

6ac6ad423a0de96b7c | ||||

x = 173dc6d853d9024f367e24a283768e11ce559473e788f3c0ed0281 | ||||

6b48403fc6e100d4935b3f6197799bfbd4fbd94b3656596252f12b | ||||

27fa46602c76ae1370 | ||||

Output: | o k_(1,0) = 0x5c759507e8e333ebb5b7a9a47d7ed8532c52d39fd3a042a88b5842 | |||

3c50ae15d5c2638e343d9c71c6238aaaaaaaa97d6 + 0x5c759507e8e333ebb5b7 | ||||

a9a47d7ed8532c52d39fd3a042a88b58423c50ae15d5c2638e343d9c71c6238aaa | ||||

aaaaa97d6 * i | ||||

x = 173dc6d853d9024f367e24a283768e11ce559473e788f3c0ed0281 | o k_(1,1) = 0x11560bf17baa99bc32126fced787c88f984f87adf7ae0c7f9a208c | |||

6b48403fc6e100d4935b3f6197799bfbd4fbd94b3656596252f12b | 6b4f20a4181472aaa9cb8d555526a9ffffffffc71a * i | |||

27fa46602c76ae1370 | ||||

y = 3808ae24b17af9147bd16077e3e83aff5c579784c8a1443d90e5ff | ||||

e2451bfabacba73ee8b8f652b991290f5c64b34b1a4c9a498e21d4 | ||||

3d000dae7f8860200a | ||||

Input: | o k_(1,2) = 0x11560bf17baa99bc32126fced787c88f984f87adf7ae0c7f9a208c | |||

6b4f20a4181472aaa9cb8d555526a9ffffffffc71e + 0x8ab05f8bdd54cde1909 | ||||

37e76bc3e447cc27c3d6fbd7063fcd104635a790520c0a395554e5c6aaaa9354ff | ||||

ffffffe38d * i | ||||

alpha = ff0011223344112233441122334411223344556677885566778855 | o k_(1,3) = 0x171d6541fa38ccfaed6dea691f5fb614cb14b4e7f4e810aa22d610 | |||

66778855667788 | 8f142b85757098e38d0f671c7188e2aaaaaaaa5ed1 | |||

Intermediate values: | The constants used to compute x_den are as follows: | |||

u = 3ebdfccb07ddc61d9f81be2b9f5a7a8733581f1a8d531d78229d7b | o k_(2,0) = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2 | |||

0be50f30887f085ef393422ef96e06ff1df4b608b05c53320a9012 | a0f6b0f6241eabfffeb153ffffb9feffffffffaa63 * i | |||

09b8df48b68ab338ec | ||||

t0 = 27958e69b08a9fd2d1765ce3e8dbaf8645c28e5ce033b9d0a7875c | ||||

e7e73d6583e62ff3a06a2b55de1cb8c26819d0cd4aed2dc7cb65fa | ||||

d5eb3c149db9e8381b | ||||

t1 = 27958e69b08a9fd2d1765ce3e8dbaf8645c28e5ce033b9d0a7875c | ||||

e7e73d6583e62ff3a06a2b55de1cb8c26819d0cd4aed2dc7cb65fa | ||||

d5eb3c149db9e8381a | ||||

x = 3fe94cd4d2be061834d1a5020ca181562fdb7e9787f71965ca55cd | ||||

dbf069b68ddd5e2b05a5696a061723093914e69b0540402baa0db3 | ||||

fddc517df4211daea1 | ||||

Output: | o k_(2,1) = 0xc + 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf | |||

6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaa9f * i | ||||

x = 3fe94cd4d2be061834d1a5020ca181562fdb7e9787f71965ca55cd | The constants used to compute y_num are as follows: | |||

dbf069b68ddd5e2b05a5696a061723093914e69b0540402baa0db3 | ||||

fddc517df4211daea1 | ||||

y = 3ebdfccb07ddc61d9f81be2b9f5a7a8733581f1a8d531d78229d7b | ||||

0be50f30887f085ef393422ef96e06ff1df4b608b05c53320a9012 | ||||

09b8df48b68ab338ec | ||||

D.6. Fouque-Tibouchi to BN256 | o k_(3,0) = 0x1530477c7ab4113b59a4c18b076d11930f7da5d4a07f649bf54439 | |||

d87d27e500fc8c25ebf8c92f6812cfc71c71c6d706 + 0x1530477c7ab4113b59a | ||||

4c18b076d11930f7da5d4a07f649bf54439d87d27e500fc8c25ebf8c92f6812cfc | ||||

71c71c6d706 * i | ||||

An instance of a BN curve is defined as "BN256: y^2=x^3+1" over | o k_(3,1) = 0x5c759507e8e333ebb5b7a9a47d7ed8532c52d39fd3a042a88b5842 | |||

"GF(p(t))" such that | 3c50ae15d5c2638e343d9c71c6238aaaaaaaa97be * i | |||

t = -(2^62 + 2^55 + 1). | o k_(3,2) = 0x11560bf17baa99bc32126fced787c88f984f87adf7ae0c7f9a208c | |||

p = 0x2523648240000001ba344d80000000086121000000000013a700000000000013 | 6b4f20a4181472aaa9cb8d555526a9ffffffffc71c + 0x8ab05f8bdd54cde1909 | |||

Input: | 37e76bc3e447cc27c3d6fbd7063fcd104635a790520c0a395554e5c6aaaa9354ff | |||

ffffffe38f * i | ||||

alpha = | o k_(3,3) = 0x124c9ad43b6cf79bfbf7043de3811ad0761b0f37a1e26286b0e977 | |||

c69aa274524e79097a56dc4bd9e1b371c71c718b10 | ||||

Intermediate values: | The constants used to compute y_den are as follows: | |||

u = 1f6f2aceae3d9323ea64e9be00566f863cc1583385eaff6b01aed7 | o k_(4,0) = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2 | |||

a762b11122 | a0f6b0f6241eabfffeb153ffffb9feffffffffa8fb + 0x1a0111ea397fe69a4b1 | |||

t0 = 1e9c884ab8d2015985a3e3d2764798b183ff5982b0fd9034f27456 | ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9fef | |||

0f19d06ed0 | fffffffa8fb * i | |||

x1 = 0843eb0f5ed559e940a453f257b2a2e297895ecc2375a070168117 | ||||

b5127ec2ae | ||||

x2 = 1cdf7972e12aa618798ff98da84d5d25c997a133dc8a5fa3907ee8 | ||||

4aed813d64 | ||||

x3 = 042f756fe42e2ed4c58990da3b2567a7b16252c0e17b2da55b8f68 | ||||

be71ebd432 | ||||

e = 2523648240000001ba344d80000000086121000000000013a70000 | ||||

0000000012 | ||||

fx1 = 0a8442855e93541a104052273e2bba930338d392d71f70efe83c77 | ||||

ae95471a4e | ||||

y1 = 135a017a32abc542796e55d0b68840546c3b2498963773635e27c2 | ||||

5aa3737199 | ||||

Output: | o k_(4,1) = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2 | |||

a0f6b0f6241eabfffeb153ffffb9feffffffffa9d3 * i | ||||

x = 0843eb0f5ed559e940a453f257b2a2e297895ecc2375a070168117 | o k_(4,2) = 0x12 + 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512b | |||

b5127ec2ae | f6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaa99 * i | |||

y = 135a017a32abc542796e55d0b68840546c3b2498963773635e27c2 | ||||

5aa3737199 | ||||

Input: | Appendix D. Sample Code | |||

alpha = 00 | This section gives sample implementations optimized for some of the | |||

elliptic curves listed in Section 8. A future version of this | ||||

document will include all listed curves, plus accompanying test | ||||

vectors. Sample Sage [SAGE] code for each algorithm can also be | ||||

found in the draft repository [hash2curve-repo]. | ||||

Intermediate values: | D.1. Interface and projective coordinate systems | |||

u = 053c7251b0e5e5c9acde43c6abd44ffeb13109f61ec27ba0a8191f | The sample code in this section uses a different interface than the | |||

1165435065 | mappings of Section 6. Specifically, each mapping function in this | |||

t0 = 0377baf027b80854661187280a98ae1320d7fd8cb0a65fd7077270 | section has the following signature: | |||

6c38cb71d8 | ||||

x1 = 0f5173cd2eb8d4352497a9cb56ebf40b623d9dabb7dcc3f626b1f3 | ||||

89e49b9356 | ||||

x2 = 15d1f0b511472bcc959ca3b4a9140bfcfee3625448233c1d804e0c | ||||

761b646cbc | ||||

x3 = 100fb33cea2b98b99ca5a279e1b4e5b0cf6927ded3cb729a822483 | ||||

809e486dc7 | ||||

e = 2523648240000001ba344d80000000086121000000000013a70000 | ||||

0000000012 | ||||

fx1 = 044c88525cbf81408b9bac1c83bdc49e3f31ec5a7b68495b5d03e5 | ||||

18448a7f09 | ||||

y1 = 18e4bd91f687e110fb5f57411fccf34b4b1d16d3d978a75d988c38 | ||||

d338522d7c | ||||

Output: | (xn, xd, yn, nd) = map_to_curve(u) | |||

x = 0f5173cd2eb8d4352497a9cb56ebf40b623d9dabb7dcc3f626b1f3 | The resulting point (x, y) is given by (xn / xd, yn / yd). | |||

89e49b9356 | ||||

y = 18e4bd91f687e110fb5f57411fccf34b4b1d16d3d978a75d988c38 | ||||

d338522d7c | ||||

Input: | The reason for this modified interface is that it enables further | |||

optimizations when working with points in a projective coordinate | ||||

system. This is desirable, for example, when the resulting point | ||||

will be immediately multiplied by a scalar, since most scalar | ||||

multiplication algorithms operate on projective points. | ||||

alpha = ff | The following are two commonly used projective coordinate systems and | |||

the corresponding conversions: | ||||

Intermediate values: | o A point (X, Y, Z) in homogeneous projective coordinates | |||

corresponds to the affine point (x, y) = (X / Z, Y / Z); the | ||||

inverse conversion is given by (X, Y, Z) = (x, y, 1). To convert | ||||

(xn, xd, yn, yd) to homogeneous projective coordinates, compute | ||||

(X, Y, Z) = (xn * yd, yn * xd, xd * yd). | ||||

u = 077033c69096f00eb76446a64be88c7ae5f1921b977381a6f2e9a8 | o A point (X', Y', Z') in Jacobian projective coordinates | |||

336191e783 | corresponds to the affine point (x, y) = (X' / Z'^2, Y' / Z'^3); | |||

t0 = 1716fb7790dd8e2e5a3ef94d63ca31682dd8b92ce13b93e0977943 | the inverse conversion is given by (X', Y', Z') = (x, y, 1). To | |||

bf4c364c72 | convert (xn, xd, yn, yd) to Jacobian projective coordinates, | |||

x1 = 187ca1d0f0dec664467d49b4a4a661602faac5453fbd4ad9e3f15d | compute (X', Y', Z') = (xn * xd * yd^2, yn * yd^2 * xd^3, xd * | |||

a35627459e | yd). | |||

x2 = 0ca6c2b14f21399d73b703cb5b599ea831763abac042b539c30ea2 | ||||

5ca9d8ba74 | ||||

x3 = 0f694914de2533b1fbab6495b1de12cde6965bba0b505b527c1cb0 | ||||

69a5fdfd03 | ||||

e = 000000000000000000000000000000000000000000000000000000 | ||||

0000000001 | ||||

fx1 = 067a294268373f0123d95357d7d46c730277e67e68daf3a2c605bf | ||||

035f680a7b | ||||

y1 = 0de5f5d8ecfc19580a882c53c08b47791edf4499965df86263c525 | ||||

afd4fe0769 | ||||

Output: | D.2. P-256 (Simplified SWU) | |||

x = 187ca1d0f0dec664467d49b4a4a661602faac5453fbd4ad9e3f15d | The following is a straight-line implementation of the Simplified SWU | |||

a35627459e | mapping for P-256 [FIPS186-4] as specified in Section 8.1. | |||

y = 0de5f5d8ecfc19580a882c53c08b47791edf4499965df86263c525 | ||||

afd4fe0769 | ||||

Input: | map_to_curve_simple_swu_p256(u) | |||

Input: u, an element of F. | ||||

Output: (xn, xd, yn, yd) such that (xn / xd, yn / yd) is a | ||||

point on P-256. | ||||

alpha = ff0011223344112233441122334411223344556677885566778855 | Constants: | |||

66778855667788 | 1. B = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b | |||

2. c1 = B / 3 | ||||

3. c2 = (p - 3) / 4 // Integer arithmetic | ||||

4. c3 = sqrt(8) | ||||

Intermediate values: | Steps: | |||

1. t1 = u^2 | ||||

2. t3 = -2 * t1 | ||||

3. t2 = t3^2 | ||||

4. xd = t2 + t3 | ||||

5. x1n = xd + 1 | ||||

6. x1n = x1n * B | ||||

7. xd = xd * 3 | ||||

8. e1 = xd == 0 | ||||

9. xd = CMOV(xd, 6, e1) // If xd == 0, set xd = Z * A == 6 | ||||

10. t2 = xd^2 | ||||

11. gxd = t2 * xd // gxd == xd^3 | ||||

12. t2 = -3 * t2 | ||||

13. gx1 = x1n^2 | ||||

14. gx1 = gx1 + t2 // x1n^2 + A * xd^2 | ||||

15. gx1 = gx1 * x1n // x1n^3 + A * x1n * xd^2 | ||||

16. t2 = B * gxd | ||||

17. gx1 = gx1 + t2 // x1n^3 + A * x1n * xd^2 + B * xd^3 | ||||

18. t4 = gxd^2 | ||||

19. t2 = gx1 * gxd | ||||

20. t4 = t4 * t2 // gx1 * gxd^3 | ||||

21. y1 = t4^c2 // (gx1 * gxd^3)^((p - 3) / 4) | ||||

22. y1 = y1 * t2 // gx1 * gxd * (gx1 * gxd^3)^((p - 3) / 4) | ||||

23. x2n = t3 * x1n // x2 = x2n / xd = -2 * u^2 * x1n / xd | ||||

24. y2 = y1 * c3 | ||||

25. y2 = y2 * t1 | ||||

26. y2 = y2 * u | ||||

27. t2 = y1^2 | ||||

28. t2 = t2 * gxd | ||||

29. e2 = t2 == gx1 | ||||

30. xn = CMOV(x2n, x1n, e2) // If e2, x = x1, else x = x2 | ||||

31. y = CMOV(y2, y1, e2) // If e2, y = y1, else y = y2 | ||||

32. e3 = sgn0(u) == sgn0(y) // fix sign of y | ||||

33. y = CMOV(-y, y, e3) | ||||

34. return (xn, xd, y, 1) | ||||

D.3. curve25519 (Elligator 2) | ||||

u = 1dd9ec37d5abeed0f289daddd685d45a395a90f2730a9adead62bf | The following is a straight-line implementation of Elligator 2 for | |||

1ae2fe958b | curve25519 [RFC7748] as specified in Section 8.4. | |||

t0 = 23d0adbb23709a3732948019e038c13f498b33812149fe503b68da | ||||

76831a7aca | ||||

x1 = 00e2d073931bc2f38a069df42afbfc9e6f04155e52cf6211be3d40 | ||||

f4f4a3dc70 | ||||

x2 = 2440940eace43d0e302daf8bd5040369f21ceaa1ad309e01e8c2bf | ||||

0b0b5c23a2 | ||||

x3 = 09c1ba4259e59a54221b5761cf9438a60e6cd644996e7c8a11be96 | ||||

88718e0261 | ||||

e = 2523648240000001ba344d80000000086121000000000013a70000 | ||||

0000000012 | ||||

fx1 = 080e2aef1644070acf09d6563db6805684572eb33f457d9d75ed5c | ||||

f96e35c9c5 | ||||

fx2 = 0c2937174e6a4a89c1574ed4fa96d83a64fb09670c49a8b492321a | ||||

edac6617f6 | ||||

fx3 = 118bcb595ca0eac3ae6e56595267670caf75d34386dadc99284bf8 | ||||

4ae4ff4804 | ||||

y3 = 190e8d47070240ff3c78a03d07123334e67b207fe555c31d0900fe | ||||

71ab33035e | ||||

Output: | map_to_curve_elligator2_curve25519(u) | |||

Input: u, an element of F. | ||||

Output: (xn, xd, yn, yd) such that (xn / xd, yn / yd) is a | ||||

point on curve25519. | ||||

x = 09c1ba4259e59a54221b5761cf9438a60e6cd644996e7c8a11be96 | Constants: | |||

88718e0261 | 1. c1 = (p + 3) / 8 // Integer arithmetic | |||

y = 190e8d47070240ff3c78a03d07123334e67b207fe555c31d0900fe | 2. c2 = 2^c1 | |||

71ab33035e | 3. c3 = sqrt(-1) | |||

4. c4 = (p - 5) / 8 // Integer arithmetic | ||||

D.7. Sample hash2base | Steps: | |||

1. t1 = u^2 | ||||

2. t1 = 2 * t1 | ||||

3. xd = t1 + 1 // nonzero: -1 is square mod p, xd is not | ||||

4. x1n = -486662 // x1 = x1n / xd = -486662 / (1 + 2 * u^2) | ||||

5. t2 = xd^2 | ||||

6. gxd = t2 * xd // gxd = xd^3 | ||||

7. gx1 = 486662 * xd // 486662 * xd | ||||

8. gx1 = gx1 + x1n // x1n + 486662 * xd | ||||

9. gx1 = gx1 * x1n // x1n^2 + 486662 * x1n * xd | ||||

10. gx1 = gx1 + t2 // x1n^2 + 486662 * x1n * xd + xd^2 | ||||

11. gx1 = gx1 * x1n // x1n^3 + 486662 * x1n^2 * xd + x1n * xd^2 | ||||

12. t3 = gxd^2 | ||||

13. t2 = t3^2 // gxd^4 | ||||

14. t3 = t3 * gxd // gxd^3 | ||||

15. t3 = t3 * gx1 // gx1 * gxd^3 | ||||

16. t2 = t2 * t3 // gx1 * gxd^7 | ||||

17. y11 = t2^c4 // (gx1 * gxd^7)^((p - 5) / 8) | ||||

18. y11 = y11 * t3 // gx1 * gxd^3 * (gx1 * gxd^7)^((p - 5) / 8) | ||||

19. y12 = y11 * c3 | ||||

20. t2 = y11^2 | ||||

21. t2 = t2 * gxd | ||||

22. e1 = t2 == gx1 | ||||

23. y1 = CMOV(y12, y11, e1) // If g(x1) is square, this is its sqrt | ||||

24. x2n = x1n * t1 // x2 = x2n / xd = 2 * u^2 * x1n / xd | ||||

25. y21 = y11 * u | ||||

26. y21 = y21 * c2 | ||||

27. y22 = y21 * c3 | ||||

28. gx2 = gx1 * t1 // g(x2) = gx2 / gxd = 2 * u^2 * g(x1) | ||||

29. t2 = y21^2 | ||||

30. t2 = t2 * gxd | ||||

31. e2 = t2 == gx2 | ||||

32. y2 = CMOV(y22, y21, e2) // If g(x2) is square, this is its sqrt | ||||

33. t2 = y1^2 | ||||

34. t2 = t2 * gxd | ||||

35. e3 = t2 == gx1 | ||||

36. xn = CMOV(x2n, x1n, e3) // if e3, x = x1, else x = x2 | ||||

37. y = CMOV(y2, y1, e3) // if e3, y = y1, else y = y2 | ||||

38. e4 = sgn0(u) == sgn0(y) // fix sign of y | ||||

39. y = CMOV(-y, y, e4) | ||||

40. return (xn, xd, y, 1) | ||||

hash2base("H2C-Curve25519-SHA256-Elligator-Clear", 1234) | D.4. edwards25519 (Elligator 2) | |||

= 1e10b542835e7b227c727bd0a7b2790f39ca1e09fc8538b3c70ef736cb1c298f | ||||

hash2base("H2C-P256-SHA512-SWU-", 1234) | The following is a straight-line implementation of Elligator 2 for | |||

= 4fabef095423c97566bd28b70ee70fb4dd95acfeec076862f4e40981a6c9dd85 | edwards25519 [RFC7748] as specified in Section 8.4. The subroutine | |||

map_to_curve_elligator2_curve25519 is defined in Appendix D.3. | ||||

hash2base("H2C-P256-SHA512-SSWU-", 1234) | map_to_curve_elligator2_edwards25519(u) | |||

= d6f685079d692e24ae13ab154684ae46c5311b78a704c6e11b2f44f4db4c6e47 | Input: u, an element of F. | |||

Output: (xn, xd, yn, yd) such that (xn / xd, yn / yd) is a | ||||

point on edwards25519. | ||||

Constants: | ||||

1. c1 = sqrt(-486664) // sign MUST be chosen such that sgn0(c1) == 1 | ||||

Steps: | ||||

1. (xMn, xMd, yMn, yMd) = map_to_curve_elligator2_curve25519(u) | ||||

2. xn = xMn * yMd | ||||

3. xn = xn * c1 | ||||

4. xd = xMd * yMn // xn / xd = c1 * xM / yM | ||||

5. yn = xMn - xMd | ||||

6. yd = xMn + xMd // (n / d - 1) / (n / d + 1) = (n - d) / (n + d) | ||||

7. return (xn, xd, yn, yd) | ||||

D.5. curve448 (Elligator 2) | ||||

The following is a straight-line implementation of Elligator 2 for | ||||

curve448 [RFC7748] as specified in Section 8.5. | ||||

map_to_curve_elligator2_curve448(u) | ||||

Input: u, an element of F. | ||||

Output: (xn, xd, yn, yd) such that (xn / xd, yn / yd) is a | ||||

point on curve448. | ||||

Constants: | ||||

1. c1 = (p - 3) / 4 // Integer arithmetic | ||||

Steps: | ||||

1. t1 = u^2 | ||||

2. xd = 1 - t1 | ||||

3. e1 = xd == 0 | ||||

4. xd = CMOV(xd, 1, e1) // If xd == 0, set xd = 1 | ||||

5. x1n = CMOV(-156326, 1, e1) // If xd == 0, x1n = 1, else x1n = -A | ||||

6. t2 = xd^2 | ||||

7. gxd = t2 * xd // gxd = xd^3 | ||||

8. gx1 = 156326 * xd // 156326 * xd | ||||

9. gx1 = gx1 + x1n // x1n + 156326 * xd | ||||

10. gx1 = gx1 * x1n // x1n^2 + 156326 * x1n * xd | ||||

11. gx1 = gx1 + t2 // x1n^2 + 156326 * x1n * xd + xd^2 | ||||

12. gx1 = gx1 * x1n // x1n^3 + 156326 * x1n^2 * xd + x1n * xd^2 | ||||

13. t3 = gxd^2 | ||||

14. t2 = gx1 * gxd // gx1 * gxd | ||||

15. t3 = t3 * t2 // gx1 * gxd^3 | ||||

16. y1 = t3^c1 // (gx1 * gxd^3)^((p - 3) / 4) | ||||

17. y1 = y1 * t2 // gx1 * gxd * (gx1 * gxd^3)^((p - 3) / 4) | ||||

18. x2n = -t1 * x1n // x2 = x2n / xd = -1 * u^2 * x1n / xd | ||||

19. y2 = y1 * u | ||||

20. t2 = y1^2 | ||||

21. t2 = t2 * gxd | ||||

22. e2 = t2 == gx1 | ||||

23. xn = CMOV(x2n, x1n, e2) // If e2, x = x1, else x = x2 | ||||

24. y = CMOV(y2, y1, e2) // If e2, y = y1, else y = y2 | ||||

25. e3 = sgn0(u) == sgn0(y) // fix sign of y | ||||

26. y = CMOV(-y, y, e3) | ||||

27. return (xn, xd, y, 1) | ||||

D.6. edwards448 (Elligator 2) | ||||

The following is a straight-line implementation of Elligator 2 for | ||||

edwards448 [RFC7748] as specified in Section 8.5. The subroutine | ||||

map_to_curve_elligator2_curve448 is defined in Appendix D.5. | ||||

map_to_curve_elligator2_edwards448(u) | ||||

Input: u, an element of F. | ||||

Output: (xn, xd, yn, yd) such that (xn / xd, yn / yd) is a | ||||

point on edwards448. | ||||

Steps: | ||||

1. (xn, xd, yn, yd) = map_to_curve_elligator2_curve448(u) | ||||

2. xn2 = xn^2 | ||||

3. xd2 = xd^2 | ||||

4. xd4 = xd2^2 | ||||

5. yn2 = yn^2 | ||||

6. yd2 = yd^2 | ||||

7. xEn = xn2 - xd2 | ||||

8. t2 = xEn - xd2 | ||||

9. xEn = xEn * xd2 | ||||

10. xEn = xEn * yd | ||||

11. xEn = xEn * yn | ||||

12. xEn = xEn * 4 | ||||

13. t2 = t2 * xn2 | ||||

14. t2 = t2 * yd2 | ||||

15. t3 = 4 * yn2 | ||||

16. t1 = t3 + yd2 | ||||

17. t1 = t1 * xd4 | ||||

18. xEd = t1 + t2 | ||||

19. t2 = t2 * xn | ||||

20. t4 = xn * xd4 | ||||

21. yEn = t3 - yd2 | ||||

22. yEn = yEn * t4 | ||||

23. yEn = yEn - t2 | ||||

24. t1 = xn2 + xd2 | ||||

25. t1 = t1 * xd2 | ||||

26. t1 = t1 * xd | ||||

27. t1 = t1 * yn2 | ||||

28. t1 = -2 * t1 | ||||

29. yEd = t2 + t1 | ||||

30. t4 = t4 * yd2 | ||||

31. yEd = yEd + t4 | ||||

32. return (xEn, xEd, yEn, yEd) | ||||

Authors' Addresses | Authors' Addresses | |||

Armando Faz-Hernandez | ||||

Cloudflare | ||||

101 Townsend St | ||||

San Francisco | ||||

United States of America | ||||

Email: armfazh@cloudflare.com | ||||

Sam Scott | Sam Scott | |||

Cornell Tech | Cornell Tech | |||

2 West Loop Rd | 2 West Loop Rd | |||

New York, New York 10044 | New York, New York 10044 | |||

United States of America | United States of America | |||

Email: sam.scott@cornell.edu | Email: sam.scott@cornell.edu | |||

Nick Sullivan | Nick Sullivan | |||

Cloudflare | Cloudflare | |||

101 Townsend St | 101 Townsend St | |||

San Francisco | San Francisco | |||

United States of America | United States of America | |||

Email: nick@cloudflare.com | Email: nick@cloudflare.com | |||

Riad S. Wahby | ||||

Stanford University | ||||

Email: rsw@cs.stanford.edu | ||||

Christopher A. Wood | Christopher A. Wood | |||

Apple Inc. | Apple Inc. | |||

One Apple Park Way | One Apple Park Way | |||

Cupertino, California 95014 | Cupertino, California 95014 | |||

United States of America | United States of America | |||

Email: cawood@apple.com | Email: cawood@apple.com | |||

End of changes. 563 change blocks. | ||||

1747 lines changed or deleted | | 2103 lines changed or added | ||

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