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 &#8800; 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&#8800;0 and B&#8800;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&#8800;0, B&#8800;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) &#8800; 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 &#8800; 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 &#8746; 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.45. The latest version is available from http://tools.ietf.org/tools/rfcdiff/