< draft-irtf-cfrg-hash-to-curve-02.txt   draft-irtf-cfrg-hash-to-curve-03.txt >
Network Working Group S. Scott Network Working Group S. Scott
Internet-Draft Cornell Tech Internet-Draft Cornell Tech
Intended status: Informational N. Sullivan Intended status: Informational N. Sullivan
Expires: April 25, 2019 Cloudflare Expires: September 12, 2019 Cloudflare
C. Wood C. Wood
Apple Inc. Apple Inc.
October 22, 2018 March 11, 2019
Hashing to Elliptic Curves Hashing to Elliptic Curves
draft-irtf-cfrg-hash-to-curve-02 draft-irtf-cfrg-hash-to-curve-03
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 http://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 April 25, 2019. This Internet-Draft will expire on September 12, 2019.
Copyright Notice Copyright Notice
Copyright (c) 2018 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
(http://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 . . . . . . . . . . . . . . . . . . . . . . 3
2. Background . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Background . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 2.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1. Encoding . . . . . . . . . . . . . . . . . . . . . . 4 2.1.1. Encoding . . . . . . . . . . . . . . . . . . . . . . 5
2.1.2. Serialization . . . . . . . . . . . . . . . . . . . . 5 2.1.2. Serialization . . . . . . . . . . . . . . . . . . . . 5
2.1.3. Random Oracle . . . . . . . . . . . . . . . . . . . . 5 2.1.3. Random Oracle . . . . . . . . . . . . . . . . . . . . 6
3. Algorithm Recommendations . . . . . . . . . . . . . . . . . . 6 3. Algorithm Recommendations . . . . . . . . . . . . . . . . . . 6
4. Utility Functions . . . . . . . . . . . . . . . . . . . . . . 6 4. Utility Functions . . . . . . . . . . . . . . . . . . . . . . 7
5. Deterministic Encodings . . . . . . . . . . . . . . . . . . . 7 5. Deterministic Encodings . . . . . . . . . . . . . . . . . . . 8
5.1. Interface . . . . . . . . . . . . . . . . . . . . . . . . 7 5.1. Interface . . . . . . . . . . . . . . . . . . . . . . . . 8
5.2. Encoding Variants . . . . . . . . . . . . . . . . . . . . 7 5.2. Notation . . . . . . . . . . . . . . . . . . . . . . . . 8
5.2.1. Icart Method . . . . . . . . . . . . . . . . . . . . 7 5.3. Encodings for Weierstrass curves . . . . . . . . . . . . 9
5.2.2. Shallue-Woestijne-Ulas Method . . . . . . . . . . . . 9 5.3.1. Icart Method . . . . . . . . . . . . . . . . . . . . 9
5.2.3. Simplified SWU Method . . . . . . . . . . . . . . . . 11 5.3.2. Shallue-Woestijne-Ulas Method . . . . . . . . . . . . 10
5.2.4. Elligator2 Method . . . . . . . . . . . . . . . . . . 12 5.3.3. Simplified SWU Method . . . . . . . . . . . . . . . . 13
5.3. Cost Comparison . . . . . . . . . . . . . . . . . . . . . 14 5.3.4. Boneh-Franklin Method . . . . . . . . . . . . . . . . 14
6. Random Oracles . . . . . . . . . . . . . . . . . . . . . . . 14 5.3.5. Fouque-Tibouchi Method . . . . . . . . . . . . . . . 16
6.1. Interface . . . . . . . . . . . . . . . . . . . . . . . . 14 5.4. Encodings for Montgomery curves . . . . . . . . . . . . . 19
6.2. General Construction (FFSTV13) . . . . . . . . . . . . . 14 5.4.1. Elligator2 Method . . . . . . . . . . . . . . . . . . 19
7. Curve Transformations . . . . . . . . . . . . . . . . . . . . 15 6. Random Oracles . . . . . . . . . . . . . . . . . . . . . . . 22
8. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . 15 6.1. Interface . . . . . . . . . . . . . . . . . . . . . . . . 22
9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 7. Curve Transformations . . . . . . . . . . . . . . . . . . . . 22
10. Security Considerations . . . . . . . . . . . . . . . . . . . 17 8. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . 22
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 17 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24
12. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 17 10. Security Considerations . . . . . . . . . . . . . . . . . . . 25
13. Normative References . . . . . . . . . . . . . . . . . . . . 17 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 25
Appendix A. Related Work . . . . . . . . . . . . . . . . . . . . 19 12. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 25
A.1. Probabilistic Encoding . . . . . . . . . . . . . . . . . 20 13. Normative References . . . . . . . . . . . . . . . . . . . . 25
A.2. Naive Encoding . . . . . . . . . . . . . . . . . . . . . 20 Appendix A. Related Work . . . . . . . . . . . . . . . . . . . . 28
A.3. Deterministic Encoding . . . . . . . . . . . . . . . . . 21 A.1. Probabilistic Encoding . . . . . . . . . . . . . . . . . 28
A.4. Supersingular Curves . . . . . . . . . . . . . . . . . . 21 A.2. Naive Encoding . . . . . . . . . . . . . . . . . . . . . 29
A.5. Twisted Variants . . . . . . . . . . . . . . . . . . . . 21 A.3. Deterministic Encoding . . . . . . . . . . . . . . . . . 29
Appendix B. Try-and-Increment Method . . . . . . . . . . . . . . 22 A.4. Supersingular Curves . . . . . . . . . . . . . . . . . . 30
Appendix C. Sample Code . . . . . . . . . . . . . . . . . . . . 22 A.5. Twisted Variants . . . . . . . . . . . . . . . . . . . . 30
C.1. Icart Method . . . . . . . . . . . . . . . . . . . . . . 22 Appendix B. Try-and-Increment Method . . . . . . . . . . . . . . 30
C.2. Shallue-Woestijne-Ulas Method . . . . . . . . . . . . . . 23 Appendix C. Sample Code . . . . . . . . . . . . . . . . . . . . 31
C.3. Simplified SWU Method . . . . . . . . . . . . . . . . . . 25 C.1. Icart Method . . . . . . . . . . . . . . . . . . . . . . 31
C.4. Elligator2 Method . . . . . . . . . . . . . . . . . . . . 25 C.2. Shallue-Woestijne-Ulas Method . . . . . . . . . . . . . . 32
C.5. HashToBase . . . . . . . . . . . . . . . . . . . . . . . 26 C.3. Simplified SWU Method . . . . . . . . . . . . . . . . . . 34
C.5.1. Considerations . . . . . . . . . . . . . . . . . . . 27 C.4. Boneh-Franklin Method . . . . . . . . . . . . . . . . . . 34
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 28 C.5. Fouque-Tibouchi Method . . . . . . . . . . . . . . . . . 35
C.6. Elligator2 Method . . . . . . . . . . . . . . . . . . . . 36
C.7. hash2base . . . . . . . . . . . . . . . . . . . . . . . . 37
C.7.1. Considerations . . . . . . . . . . . . . . . . . . . 38
Appendix D. Test Vectors . . . . . . . . . . . . . . . . . . . . 39
D.1. Elligator2 to Curve25519 . . . . . . . . . . . . . . . . 39
D.2. Icart to P-384 . . . . . . . . . . . . . . . . . . . . . 41
D.3. SWU to P-256 . . . . . . . . . . . . . . . . . . . . . . 44
D.4. Simple SWU to P-256 . . . . . . . . . . . . . . . . . . . 48
D.5. Boneh-Franklin to P-503 . . . . . . . . . . . . . . . . . 52
D.6. Fouque-Tibouchi to BN256 . . . . . . . . . . . . . . . . 56
D.7. Sample hash2base . . . . . . . . . . . . . . . . . . . . 60
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 61
1. Introduction 1. Introduction
Many cryptographic protocols require a procedure which maps arbitrary Many cryptographic protocols require a procedure which maps arbitrary
input, e.g., passwords, to points on an elliptic curve (EC). input, e.g., passwords, to points on an elliptic curve (EC).
Prominent examples include Simple Password Exponential Key Exchange Prominent examples include Simple Password Exponential Key Exchange
[Jablon96], Password Authenticated Key Exchange [BMP00], Identity- [Jablon96], Password Authenticated Key Exchange [BMP00], Identity-
Based Encryption [BF01] and Boneh-Lynn-Shacham signatures [BLS01]. Based Encryption [BF01] and Boneh-Lynn-Shacham signatures [BLS01].
Unfortunately for implementors, the precise mapping which is suitable Unfortunately for implementors, the precise mapping which is suitable
skipping to change at page 5, line 15 skipping to change at page 5, line 29
deterministic or probabilistic, although the latter is problematic in deterministic or probabilistic, although the latter is problematic in
potentially leaking plaintext information as a side-channel. potentially leaking plaintext information as a side-channel.
Suppose as the input to the encoding function we wish to use a fixed- Suppose as the input to the encoding function we wish to use a fixed-
length bitstring of length L. Comparing sizes of the sets, 2^L and length bitstring of length L. Comparing sizes of the sets, 2^L and
n, an encoding function cannot be both deterministic and bijective. n, an encoding function cannot be both deterministic and bijective.
We can instead use an injective encoding from {0, 1}^L to E, with "L We can instead use an injective encoding from {0, 1}^L to E, with "L
< log2(n)- 1", which is a bijection over a subset of points in E. < log2(n)- 1", which is a bijection over a subset of points in E.
This ensures that encoded plaintext messages can be recovered. This ensures that encoded plaintext messages can be recovered.
In practice, encodings are commonly injective and invertible.
Injective encodings map inputs to a subset of points on the curve.
Invertible encodings allow computation of input bitstrings given a
point on the curve.
2.1.2. Serialization 2.1.2. Serialization
A related issue is the conversion of an elliptic curve point to a A related issue is the conversion of an elliptic curve point to a
bitstring. We refer to this process as "serialization", since it is bitstring. We refer to this process as "serialization", since it is
typically used for compactly storing and transporting points, or for typically used for compactly storing and transporting points, or for
producing canonicalized outputs. Since a deserialization algorithm producing canonicalized outputs. Since a deserialization algorithm
can often be used as a type of encoding algorithm, we also briefly can often be used as a type of encoding algorithm, we also briefly
document properties of these functions. document properties of these functions.
A straightforward serialization algorithm maps a point (x, y) on E to A straightforward serialization algorithm maps a point (x, y) on E to
skipping to change at page 5, line 37 skipping to change at page 6, line 8
approximately equal to p), it is possible to serialize to a bitstring approximately equal to p), it is possible to serialize to a bitstring
of length log(n). For example, one common method is to store the of length log(n). For example, one common method is to store the
x-coordinate and a single bit to determine whether the point is (x, x-coordinate and a single bit to determine whether the point is (x,
y) or (x, -y), thus requiring log(p)+1 bits. This method reduces y) or (x, -y), thus requiring log(p)+1 bits. This method reduces
storage, but adds computation, since the deserialization process must storage, but adds computation, since the deserialization process must
recover the y coordinate. recover the y coordinate.
2.1.3. Random Oracle 2.1.3. Random Oracle
It is often the case that the output of the encoding function It is often the case that the output of the encoding function
Section 2.1.1 should be distributed uniformly at random on the Section 2.1.1 should be (a) distributed uniformly at random on the
elliptic curve. That is, there is no discernible relation existing elliptic curve and (b) non-invertible. That is, there is no
between outputs that can be computed based on the inputs. In discernible relation existing between outputs that can be computed
practice, this requirement stems from needing a random oracle which based on the inputs. Moreover, given such an encoding function F
outputs elliptic curve points: one way to construct this is by first from bitstrings to points on the curve, as well as a single point y,
taking a regular random oracle, operating entirely on bitstrings, and it is computationally intractable to produce an input x that maps to
applying a suitable encoding function to the output. 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 This motivates the term "hashing to the curve", since cryptographic
hash functions are typically modeled as random oracles. However, hash functions are typically modeled as random oracles. However,
this still leaves open the question of what constitutes a suitable this still leaves open the question of what constitutes a suitable
encoding method, which is a primary concern of this document. encoding method, which is a primary concern of this document.
A random oracle onto an elliptic curve can also be instantiated using A random oracle onto an elliptic curve can also be instantiated using
direct constructions, however these tend to rely on many group direct constructions, however these tend to rely on many group
operations and are less efficient than hash and encode methods. operations and are less efficient than hash and encode methods.
3. Algorithm Recommendations 3. Algorithm Recommendations
The following table lists algorithms recommended by use-case: In practice, two types of mappings are common: (1) Injective
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
| Application | Requirement | Additional Details | IBE [BF01]. (Some applications, such as IBE, have additional
+----------------+-----------------+--------------------------------+ requirements, such as a Supersingular, pairing-friendly curve.)
| SPEKE | Naive | H(x)*G |
| [Jablon96] | | |
| | | |
| PAKE [BMP00] | Random Oracle | - |
| | | |
| BLS [BLS01] | Random Oracle | - |
| | | |
| IBE [BF01] | Random Oracle | Supersingular, pairing- |
| | | friendly curve |
| | | |
| PRF | Injective | F(k, m) = k*H(m) |
| | encoding | |
+----------------+-----------------+--------------------------------+
To find the suitable algorithm, lookup the requirement from above, The following table lists recommended algorithms for different curves
with the chosen curve in the below: and mappings. To select a suitable algorithm, choose the mapping
associated with the target curve. For example, Elligator2 is the
recommended injective encoding function for Curve25519, whereas
Simple SWU is the recommended injective encoding for P-256.
Similarly, the FFSTV Random Oracle construction described in
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.
+------------+--------------------------+---------------+ +------------+-------------------------+----------------------------+
| Curve | Inj. Encoding | Random Oracle | | Curve | Inj. Encoding | Random Oracle |
+------------+--------------------------+---------------+ +------------+-------------------------+----------------------------+
| P-256 | Simple SWU Section 5.2.3 | FFSTV(SWU) | | P-256 | Simple SWU Section | FFSTV(SWU) Section 6 |
| | | | | | 5.3.3 | |
| P-384 | Icart Section 5.2.1 | FFSTV(Icart) | | | | |
| | | | | P-384 | Icart Section 5.3.1 | FFSTV(Icart) Section 6 |
| Curve25519 | Elligator2 Section 5.2.4 | ... | | | | |
| | | | | Curve25519 | Elligator2 Section | FFSTV(Elligator2) Section |
| Curve448 | Elligator2 Section 5.2.4 | ... | | | 5.4.1 | 6 |
+------------+--------------------------+---------------+ | | | |
| Curve448 | Elligator2 Section | FFSTV(Elligator2) Section |
| | 5.4.1 | 6 |
+------------+-------------------------+----------------------------+
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 HashToBase(x, i). This method is parametrized by p and H, where p o hash2base(x). This method is parametrized by p and H, where p is
is the prime order of the base field Fp, and H is a cryptographic the prime order of the base field Fp, and H is a cryptographic
hash function which outputs at least floor(log2(p)) + 2 bits. The hash function which outputs at least floor(log2(p)) + 1 bits. The
function first hashes x, converts the result to an integer, and function first hashes x, converts the result to an integer, and
reduces modulo p to give an element of Fp. reduces modulo p to give an element of Fp. We provide a more
detailed algorithm in Appendix C.7.
We provide a more detailed algorithm in Appendix C.5. The value
of i is used to separate inputs when used multiple times in one
algorithm (see Section 6.2 for example). When i is omitted, we
set it to 0.
o CMOV(a, b, c): If c = 1, return a, else return b. o CMOV(a, b, c): If c = 1, return a, else return b.
Common software implementations of constant-time selects assume c Common software implementations of constant-time selects assume c
= 1 or c = 0. CMOV may be implemented by computing the desired = 1 or c = 0. CMOV may be implemented by computing the desired
selector (0 or 1) by ORing all bits of c together. The end result selector (0 or 1) by ORing all bits of c together. The end result
will be either 0 if all bits of c are zero, or 1 if at least one will be either 0 if all bits of c are zero, or 1 if at least one
bit of c is 1. bit of c is 1.
o CTEQ(a, b): Returns a == b. Inputs a and b must be the same o CTEQ(a, b): Returns a == b. Inputs a and b must be the same
skipping to change at page 7, line 32 skipping to change at page 8, line 5
constant time. constant time.
o Legendre(x, p): x^((p-1)/2). The Legendre symbol computes whether o Legendre(x, p): x^((p-1)/2). The Legendre symbol computes whether
the value x is a "quadratic residue" modulo p, and takes values 1, the value x is a "quadratic residue" modulo p, and takes values 1,
-1, 0, for when x is a residue, non-residue, or zero, -1, 0, for when x is a residue, non-residue, or zero,
respectively. Due to Euler's criterion, this can be computed in respectively. Due to Euler's criterion, this can be computed in
constant time, with respect to a fixed p, using the equation constant time, with respect to a fixed p, using the equation
x^((p-1)/2). For clarity, we will generally prefer using the x^((p-1)/2). For clarity, we will generally prefer using the
formula directly, and annotate the usage with this definition. formula directly, and annotate the usage with this definition.
o sqrt(x, p): Computing square roots should be done in constant time
where possible.
When p = 3 (mod 4), the square root can be computed as "sqrt(x, p)
:= x^(p+1)/4". This applies to P256, P384, and Curve448.
When p = 5 (mod 8), the square root can be computed by the
following algorithm, in which "sqrt(-1)" is a field element and
can be precomputed. This applies to Curve25519.
sqrt(x, p) :=
x^(p+3)/8 if x^(p+3)/4 == x
sqrt(-1) * x^(p+3)/8 otherwise
The above two conditions hold for most practically used curves, due
to the simplicity of the square root function. For others, a
suitable constant-time Tonelli-Shanks variant should be used as in
[Schoof85].
5. Deterministic Encodings 5. Deterministic Encodings
5.1. Interface 5.1. Interface
The generic interface for deterministic encoding functions to The generic interface for deterministic encoding functions to
elliptic curves is as follows: elliptic curves is as follows:
map2curve(alpha) map2curve(alpha)
where alpha is a message to encode on a curve. where alpha is a message to encode on a curve.
5.2. Encoding Variants 5.2. Notation
5.2.1. Icart Method As a rough style guide for the following, we use (x, y) to be the
output coordinates of the encoding method. Indexed values are used
when the algorithm will choose between candidate values. For
example, the SWU algorithm computes three candidates (x1, y1), (x2,
y2), (x3, y3), from which the final (x, y) output is chosen via
constant time comparison operations.
The following map2curve_icart(alpha) implements the Icart method from We use u, v to denote the values in Fp output from hash2base, and use
[Icart09]. This algorithm works for any curve over F_{p^n}, where as initial values in the encoding.
p^n = 2 mod 3 (or p = 2 mod 3 and for odd n), including:
o P384 We use t1, t2, ..., as reusable temporary variables. For notable
o Curve1174 variables, we will use a distinct name, for ease of debugging
purposes when correlating with test vectors.
o Curve448 The code presented here corresponds to the example Sage [SAGE] code
found at [github-repo]. Which is additionally used to generate
intermediate test vectors. The Sage code is also checked against the
hacspec implementation.
Unsupported curves include: P224, P256, P521, and Curve25519 since, Note that each encoding requires that certain preconditions must hold
for each, p = 1 mod 3. in order to be applied.
Mathematically, given input alpha, and A and B from E, the Icart 5.3. Encodings for Weierstrass curves
method works as follows:
u = HashToBase(alpha) The following encodings apply to elliptic curves defined as E: y^2 =
x^3+Ax+B, where 4A^3+27B^2 &#8800; 0.
5.3.1. Icart Method
The map2curve_icart(alpha) implements the Icart encoding method from
[Icart09].
*Preconditions*
A Weierstrass curve over F_{p^n}, where p>3 and p^n = 2 mod 3 (or p =
2 mod 3 and for odd n).
*Examples*
o P-384
*Algorithm*: map2curve_icart
Input:
o alpha: an octet string to be hashed.
o A, B : the constants from the Weierstrass curve.
Output:
o (x,y), a point in E.
Operations:
u = hash2base(alpha)
v = ((3A - u^4) / 6u) v = ((3A - u^4) / 6u)
x = (v^2 - B - (u^6 / 27))^(1/3) + (u^2 / 3) x = (v^2 - B - (u^6 / 27))^(1/3) + (u^2 / 3)
y = ux + v y = ux + v
Output (x, y)
The following procedure implements this algorithm in a straight-line *Implementation*
fashion. It requires knowledge of A and B, the constants from the The following procedure implements Icart's algorithm in a straight-
curve Weierstrass form. It outputs a point with affine coordinates. line fashion.
map2curve_icart(alpha) map2curve_icart(alpha)
Input: Input:
alpha - value to be hashed, an octet string alpha - value to be hashed, an octet string
Output: Output:
(x, y) - a point in E (x, y) - a point in E
Precomputations:
1. c1 = (2 * p) - 1
2. c1 = c1 / 3 // c1 = (2p-1)/3 as integer
3 c2 = 3^(-1) // c2 = 1/3 (mod p)
4. c3 = c2^3 // c3 = 1/27 (mod p)
Steps: Steps:
1. u = HashToBase(alpha) // {0,1}^* -> Fp 1. u = hash2base(alpha) // {0,1}^* -> Fp
2. u2 = u^2 (mod p) // u^2 2. u2 = u^2 // u^2
3. t2 = u2^2 (mod p) // u^4 3. u4 = u2^2 // u^4
4. v1 = 3 * A (mod p) // 3A in Fp 4. v = 3 * A // 3A in Fp
5. v1 = v1 - t2 (mod p) // 3A - u^4 5. v = v - u4 // 3A - u^4
6. t1 = 6 * u (mod p) // 6u 6. t1 = 6 * u // 6u
7. t3 = t1 ^ (-1) (mod p) // modular inverse 7. t1 = t1^(-1) // modular inverse
8. v = v1 * t3 (mod p) // (3A - u^4)/(6u) 8. v = v * t1 // (3A - u^4)/(6u)
9. x = v^2 (mod p) // v^2 9. x1 = v^2 // v^2
10. x = x - B (mod p) // v^2 - B 10. x1 = x - B // v^2 - B
11. t1 = 27 ^ (-1) (mod p) // 1/27 11. u6 = u4 * c3 // u^4 / 27
12. t1 = t1 * u2 (mod p) // u^4 / 27 12. u6 = u6 * u2 // u^6 / 27
13. t1 = t1 * t2 (mod p) // u^6 / 27 13. x1 = x1 - u6 // v^2 - B - u^6/27
14. x = x - t1 (mod p) // v^2 - B - u^6/27 14. x1 = x^c1 // (v^2 - B - u^6/27) ^ (1/3)
15. t1 = (2 * p) - 1 // 2p - 1 in ZZ 15. t1 = u2 * c2 // u^2 / 3
16. t1 = t1 / 3 // (2p - 1)/3 in ZZ 16. x = x + t1 // (v^2 - B - u^6/27) ^ (1/3) + (u^2 / 3)
17. x = x^t1 (mod p) // (v^2 - B - u^6/27) ^ (1/3) 17. y = u * x // ux
18. t2 = u2 / 3 (mod p) // u^2 / 3 18. y = y + v // ux + v
19. x = x + t2 (mod p) // (v^2 - B - u^6/27) ^ (1/3) + (u^2 / 3) 19. Output (x, y)
20. y = u * x (mod p) // ux
21. y = y + v (mod p) // ux + v
22. Output (x, y)
5.2.2. Shallue-Woestijne-Ulas Method 5.3.2. Shallue-Woestijne-Ulas Method
The Shallue-Woestijne-Ulas (SWU) method, originated in part by The map2curve_swu(alpha) implements the Shallue-Woestijne-Ulas (SWU)
Shallue and Woestijne [SW06] and later simplified and extended by method by Ulas [SWU07], which is based on Shallue and Woestijne
Ulas [SWU07], deterministically encodes an arbitrary string to a [SW06] method.
point on a curve. This algorithm works for any curve over F_{p^n}.
Given curve equation g(x) = x^3 + Ax + B, this algorithm works as
follows:
1. t = HashToBase(alpha, 0) *Preconditions*
2. u = HashToBase(alpha, 1)
3. X1 = u This algorithm works for any Weierstrass curve over F_{p^n} such that
4. X2 = (-B / A)(1 + 1 / (t^4 * g(u)^2 + t^2 * g(u))) A&#8800;0 and B&#8800;0.
5. X3 = t^3 * g(u)^2 * g(X2)
6. If g(X1) is square, output (X1, sqrt(g(X1))) *Examples*
7. If g(X2) is square, output (X2, sqrt(g(X2)))
8. Output (X3(t, u), sqrt(g(X3))) o P-256
o P-384
o P-521
*Algorithm*: map2curve_swu
Input:
o alpha: an octet string to be hashed.
o A, B : the constants from the Weierstrass curve.
Output:
o (x,y), a point in E.
Operations:
1. u = hash2base(alpha || 0x00)
2. v = hash2base(alpha || 0x01)
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: The algorithm relies on the following equality:
t^3 * g(u)^2 * g(X2(t, u)) = g(X1(t, u)) * g(X2(t, u)) * g(X3(t, u)) u^3 * g(v)^2 * g(x2) = g(x1) * g(x2) * g(x3)
The algorithm computes three candidate points, constructed such that The algorithm computes three candidate points, constructed such that
at least one of them lies on the curve. at least one of them lies on the curve.
The following procedure implements this algorithm. It outputs a *Implementation*
point with affine coordinates. It requires knowledge of A and B, the
constants from the curve Weierstrass form.
map2curve_swu(alpha) The following procedure implements SWU's algorithm in a straight-line
fashion.
map2curve_swu(alpha)
Input:
alpha - value to be hashed, an octet string
Output:
(x, y) - a point in E
Precomputations:
1. c1 = -B / A mod p // Field arithmetic
2. c2 = (p - 1)/2 // Integer arithmetic
Steps:
1. u = hash2base(alpha || 0x00) // {0,1}^* -> Fp
2. v = hash2base(alpha || 0x01) // {0,1}^* -> Fp
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
Shallue-Woestijne-Ulas algorithm given by Brier et al. [SimpleSWU].
*Preconditions*
This algorithm works for any Weierstrass curve over F_{p^n} such that
A&#8800;0, B&#8800;0, and p=3 mod 4.
*Examples*
o P-256
o P-384
o P-521
*Algorithm*: map2curve_simple_swu
Input: Input:
alpha - value to be hashed, an octet string o alpha: an octet string to be hashed.
o A, B : the constants from the Weierstrass curve.
Output: Output:
(x, y) - a point in E o (x,y), a point in E.
Steps: Operations:
1. t = HashToBase(alpha, 0) // {0,1}^* -> Fp 1. Define g(x) = x^3 + Ax + B
2. u = HashToBase(alpha, 1) // {0,1}^* -> Fp 2. u = hash2base(alpha)
3. t2 = t^2 3. x1 = -B/A * (1 + (1 / (u^4 - u^2)))
4. t4 = t2^2 4. x2 = -u^2 * x1
5. gu = u^3 5. If g(x1) is square, output (x1, sqrt(g(x1)))
6. gu = gu + (A * u) 6. Output (x2, sqrt(g(x2)))
7. gu = gu + B // gu = g(u)
8. x1 = u // x1 = X1(t, u) = u
9. x2 = B * -1
10. x2 = x2 / A
11. gx1 = x1^3
12. gx1 = gx1 + (A * x1)
13. gx1 = gx1 + B // gx1 = g(X1(t, u))
14. d1 = gu^2
15. d1 = d1 * t4
16. d2 = t2 * gu
17. d3 = d1 + d2
18. d3 = d3^(-1)
19. n1 = 1 + d3
20. x2 = x2 * n1 // x2 = X2(t, u)
21. gx2 = x2^3
22. gx2 = gx2 + (A * x2)
23. gx2 = gx2 + B // gx2 = g(X2(t, u))
24. x3 = t2 * gu
25. x3 = x3 * x2 // x3 = X3(t, u)
26. gx3 = x3^3
27. gx3 = gx3 + (A * x3)
28. gx3 = gx3 + B // gx3 = g(X3(t, u))
29. l1 = gx1^((p - 1) / 2)
30. l2 = gx2^((p - 1) / 2)
31. s1 = gx1^(1/2)
32. s2 = gx2^(1/2)
33. s3 = gx3^(1/2)
34. if l1 == 1:
35. Output (x1, s1)
36. if l2 == 1:
37. Output (x2, s2)
38. Output (x3, s3)
5.2.3. Simplified SWU Method *Implementation*
The following map2curve_simple_swu(alpha) implements the simplified The following procedure implements the Simple SWU's algorithm in a
Shallue-Woestijne-Ulas algorithm from [SimpleSWU]. This algorithm straight-line fashion.
works for any curve over F_{p^n}, where p = 3 mod 4, including:
o P256 map2curve_simple_swu(alpha)
o ... Input:
Given curve equation g(x) = x^3 + Ax + B, this algorithm works as alpha - value to be encoded, an octet string
follows:
1. t = HashToBase(alpha) Output:
2. alpha = (-B / A) * (1 + (1 / (t^4 + t^2)))
3. beta = -t^2 * alpha
4. If g(alpha) is square, output (alpha, sqrt(g(alpha)))
5. Output (beta, sqrt(g(beta)))
The following procedure implements this algorithm. It outputs a (x, y) - a point in E
point with affine coordinates. It requires knowledge of A and B, the
constants from the curve Weierstrass form.
map2curve_simple_swu(alpha) Precomputations:
1. c1 = -B / A mod p // Field arithmetic
2. c2 = (p - 1)/2 // Integer arithmetic
Steps:
1. u = hash2base(alpha) // {0,1}^* -> Fp
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 map2curve_bf(alpha) implements the Boneh-Franklin method [BF01]
which covers the case of supersingular curves "E: y^2=x^3+B". This
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*
This algorithm works for any Weierstrass curve over "F_q" such that
"A=0" and "q=2 mod 3".
*Examples*
o "y^2 = x^3 + 1"
*Algorithm*: map2curve_bf
Input: Input:
alpha - value to be encoded, an octet string o "alpha": an octet string to be hashed.
o "B": the constant from the Weierstrass curve.
Output: Output:
(x, y) - a point in E o "(x, y)": a point in E.
Operations:
1. u = hash2base(alpha)
2. x = (u^2 - B)^((2 * q - 1) / 3)
3. Output (x, u)
*Implementation*
The following procedure implements the Boneh-Franklin's algorithm in
a straight-line fashion.
map2curve_bf(alpha)
Input:
alpha: an octet string to be hashed.
B : the constant from the Weierstrass curve.
Output:
(x, y): a point in E
Precomputations:
1. c = (2 * q - 1) / 3 // Integer arithmetic
Steps: Steps:
1. t = HashToBase(alpha) 1. u = hash2base(alpha) // {0,1}^* -> F_q
2. alpha = t^2 (mod p) 2. t0 = u^2 // t0 = u^2
3. alpha = alpha * -1 (mod p) 3. t1 = t0 - B // t1 = u^2 - B
4. right = alpha^2 + alpha (mod p) 4. x = t1^c // x = (u^2 - B)^((2 * q - 1) / 3)
5. right = right^(-1) (mod p) 5. Output (x, u)
6. right = right + 1 (mod p)
7. left = B * -1 (mod p)
8. left = left / A (mod p)
9. x2 = left * right (mod p)
10. x3 = alpha * x2 (mod p)
11. h2 = x2 ^ 3 (mod p)
12. i2 = x2 * A (mod p)
13. i2 = i2 + B (mod p)
14. h2 = h2 + i2 (mod p)
15. h3 = x3 ^ 3 (mod p)
16. i3 = x3 * A (mod p)
17. i3 = i3 + B (mod p)
18. h3 = h3 + i3 (mod p)
19. y1 = h2 ^ ((p + 1) / 4) (mod p)
20. y2 = h3 ^ ((p + 1) / 4) (mod p)
21. e = CTEQ(y1 ^ 2, h2) // Constant-time equality
22. x = CMOV(x2, x3, e) // If e = 1, choose x2, else choose x3
23. y = CMOV(y1, y2, e) // If e = 1, choose y1, else choose y2
24. Output (x, y)
5.2.4. Elligator2 Method 5.3.5. Fouque-Tibouchi Method
The following map2curve_elligator2(alpha) implements the Elligator2 The map2curve_ft(alpha) implements the Fouque-Tibouchi's method
method from [Elligator2]. This algorithm works for any curve with a [FT12] (Sec. 3, Def. 2) which covers the case of pairing-friendly
point of order 2 and j-invariant != 1728. Given curve equation y^2 = curves "E : y^2 = x^3 + B". Note that for pairing curves the
x(x^2 + Ax + B), i.e., a Montgomery form with (0,0), a point of order destination group is usually a subgroup of the curve, hence, a scalar
2, this algorithm works as shown below. (Note that any curve with a multiplication by the cofactor will be required to send the point to
point of order 2 is isomorphic to this representation.) the desired subgroup.
1. r = HashToBase(alpha)
2. Let u be a non-square value in Fp *Preconditions*
3. v = -A/(1+ur^ 2)
4. e = Legendre(v^3+Av^2+Bv) This algorithm works for any Weierstrass curve over "F_q" such that
5.1. If r != 0, then "q=7 mod 12", "A=0", and "1+B" is a non-zero square in the field.
This covers the case "q=1 mod 3" not handled by Boneh-Franklin's
method.
*Examples*
o SECP256K1 curve [SEC2]
o BN curves [BN05]
o KSS curves [KSS08]
o BLS curves [BLS01]
*Algorithm*: map2curve_ft
Input:
o "alpha": an octet string to be hashed.
o "B": the constant from the Weierstrass curve.
o "s": a constant equal to sqrt(-3) in the field.
Output:
o (x, y): a point in E.
Operations:
1. t = hash2base(alpha)
2. w = (s * t)/(1 + B + t^2)
3. x1 = ((-1 + s) / 2) - t * w
4. x2 = -1 - x1
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*
The following procedure implements the Fouque-Tibouchi's algorithm in
a straight-line fashion.
map2curve_ft(alpha)
Input:
alpha: an octet string to be encoded
B : the constant of the curve
Output:
(x, y): - a point in E
Precomputations:
1. c1 = sqrt(-3) // Field arithmetic
2. c2 = (-1 + c1) / 2 // Field arithmetic
Steps:
1. t = hash2base(alpha) // {0,1}^* -> Fp
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
+ B))" when "u=0".
5.4. Encodings for Montgomery curves
A Montgomery curve is given by the following equation E:
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 map2curve_elligator2(alpha) implements the Elligator2 method from
[Elligator2].
*Preconditions*
Any curve of the form y^2=x^3+Ax^2+Bx, which covers all Montgomery
curves such that A &#8800; 0 and B=1 (i.e. j-invariant != 1728).
*Examples*
o Curve25519
o Curve448
*Algorithm*: map2curve_elligator2
Input:
o alpha: an octet string to be hashed.
o A,B=1: the constants of the Montgomery curve.
o N : a constant non-square in the field.
Output:
o (x,y), a point in E.
Operations:
1. Define g(x) = x(x^2 + Ax + B)
2. u = hash2base(alpha)
3. v = -A/(1 + N*u^2)
4. e = Legendre(g(v))
5.1. If u != 0, then
5.2. x = ev - (1 - e)A/2 5.2. x = ev - (1 - e)A/2
5.3. y = -e*sqrt(x^3+Ax^2+x) 5.3. y = -e*sqrt(g(x))
5.4. Else, x=0 and y=0 5.4. Else, x=0 and y=0
6. Output (x,y) 6. Output (x,y)
Here, e is the Legendre symbol defined as in Section 4. Here, e is the Legendre symbol defined as in Section 4.
The following procedure implements this algorithm. *Implementation*
The following procedure implements elligator2 algorithm in a
straight-line fashion.
map2curve_elligator2(alpha) map2curve_elligator2(alpha)
Input: Input:
alpha - value to be encoded, an octet string alpha - value to be encoded, an octet string
A,B=1 - the constants of the Montgomery curve.
u - fixed non-square value in Fp. N - a constant non-square value in Fp.
Output: Output:
(x, y) - a point in E (x, y) - a point in E
Steps: Precomputations:
1. r = HashToBase(alpha)
2. r = r^2 (mod p)
3. nu = r * u (mod p)
4. r = nu
5. r = r + 1 (mod p)
6. r = r^(-1) (mod p)
7. v = A * r (mod p)
8. v = v * -1 (mod p) // -A / (1 + ur^2)
9. v2 = v^2 (mod p)
10. v3 = v * v2 (mod p)
11. e = v3 + v (mod p)
12. v2 = v2 * A (mod p)
13. e = v2 + e (mod p)
14. e = e^((p - 1) / 2) // = Legendre(e)
15. nv = v * -1 (mod p)
16. v = CMOV(v, nv, e) // If e = 1, choose v, else choose nv
17. v2 = CMOV(0, A, e) // If e = 1, choose 0, else choose A
18. x = v - v2 (mod p)
19. y = -e*sqrt(x^3+Ax^2+Bx)
19. Output (x, y)
Elligator2 can be simplified with projective coordinates.
((TODO: write this variant)) 1. c1 = (p - 1)/2 // Integer arithmetic
2. c2 = A / 2 (mod p) // Field arithmetic
5.3. Cost Comparison Steps:
The following table summarizes the cost of each map2curve variant. 1. u = hash2base(alpha)
We express this cost in terms of additions (A), multiplications (M), 2. t1 = u^2
squares (SQ), and square roots (SR). 3. t1 = N * t1
4. t1 = 1 + t1
5. t1 = t1^(-1)
6. v = A * t1
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)
((TODO: finish this section)) Elligator2 can be simplified with projective coordinates.
+----------------------+-------------------+ ((TODO: write this variant))
| Algorithm | Cost (Operations) |
+----------------------+-------------------+
| map2curve_icart | TODO |
| | |
| map2curve_swu | TODO |
| | |
| map2curve_simple_swu | TODO |
| | |
| map2curve_elligator2 | TODO |
+----------------------+-------------------+
6. Random Oracles 6. Random Oracles
6.1. Interface Some applications require a Random Oracle (RO) of points, which can
be constructed from deterministic encoding functions. Farashahi et
The generic interface for deterministic encoding functions to al. [FFSTV13] showed a generic mapping construction that is
elliptic curves is as follows: indistinguishable from a random oracle. In particular, let "f :
{0,1}^* -> E(F)" be a deterministic encoding function, and let "H0"
hash2curve(alpha) 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
where alpha is a message to encode on a curve. hash2curveRO(alpha) = f(H0(alpha)) + f(H1(alpha))
6.2. General Construction (FFSTV13) where alpha is an octet string to be encoded as a point on a curve.
When applications need a Random Oracle (RO), they can be constructed 6.1. Interface
from deterministic encoding functions. In particular, let F :
{0,1}^* -> E be a deterministic encoding function onto curve E, and
let H0 and H1 be two hash functions modeled as random oracles that
map input messages to the base field of E, i.e., Z_q. Farashahi et
al. [FFSTV13] showed that the following mapping is indistinguishable
from a RO:
hash2curve(alpha) = F(H0(alpha)) + F(H1(alpha)) Using the deterministic encodings from Section 5, the
This construction works for the Icart, SWU, and Simplfied SWU "hash2curveRO(alpha)" mapping can be instantiated as
encodings.
Here, H0 and H1 are constructed as follows: hash2curveRO(alpha) = hash2curve(alpha || 0x02) + hash2curve(alpha || 0x03)
H0(alpha) = HashToBase(alpha, 2) where the addition operation is performed as a point addition.
H1(alpha) = HashToBase(alpha, 3)
7. Curve Transformations 7. Curve Transformations
Every elliptic curve can be converted to an equivalent curve in short Every elliptic curve can be converted to an equivalent curve in short
Weierstrass form ([BL07] Theorem 2.1), making SWU a generic algorithm Weierstrass form ([BL07] Theorem 2.1), making SWU a generic algorithm
that can be used for all curves. Curves in either Edwards or Twisted that can be used for all curves. Curves in either Edwards or Twisted
Edwards form can be transformed into equivalent curves in Montgomery Edwards form can be transformed into equivalent curves in Montgomery
form [BL17] for use with Elligator2. [RFC7748] describes how to form [BL17] for use with Elligator2. [RFC7748] describes how to
convert between points on Curve25519 and Ed25519, and between convert between points on Curve25519 and Ed25519, and between
Curve448 and its Edwards equivalent, Goldilocks. Curve448 and its Edwards equivalent, Goldilocks.
8. Ciphersuites 8. Ciphersuites
To provide concrete recommendations for algorithms we define a hash- To provide concrete recommendations for algorithms we define a hash-
to-curve "ciphersuite" as a four-tuple containing: to-curve "ciphersuite" as a four-tuple containing:
o Destination Group (e.g. P256 or Curve25519) o Destination Group (e.g. P256 or Curve25519)
o HashToBase algorithm o hash2base algorithm
o HashToCurve algorithm (e.g. SSWU, Icart) o HashToCurve algorithm (e.g. SSWU, Icart)
o (Optional) Transformation (e.g. FFSTV, cofactor clearing) o (Optional) Transformation (e.g. FFSTV, cofactor clearing)
A ciphersuite defines an algorithm that takes an arbitrary octet A ciphersuite defines an algorithm that takes an arbitrary octet
string and returns an element of the Destination Group defined in the string and returns an element of the Destination Group defined in the
ciphersuite by applying HashToCurve and Transformation (if defined). ciphersuite by applying HashToCurve and Transformation (if defined).
This document describes the following set of ciphersuites: * H2C- This document describes the following set of ciphersuites:
P256-SHA256-SSWU- * H2C-P384-SHA512-Icart- * H2C-
Curve25519-SHA512-Elligator2-Clear * H2C-
Curve448-SHA512-Elligator2-Clear * H2C-
Curve25519-SHA512-Elligator2-FFSTV * H2C-
Curve448-SHA512-Elligator2-FFSTV
H2C-P256-SHA256-SWU- is defined as follows: o H2C-P256-SHA256-SSWU-
o H2C-P384-SHA512-Icart-
o H2C-SECP256K1-SHA512-FT-
o H2C-BN256-SHA512-FT-
o H2C-Curve25519-SHA512-Elligator2-Clear
o H2C-Curve448-SHA512-Elligator2-Clear
o H2C-Curve25519-SHA512-Elligator2-FFSTV
o H2C-Curve448-SHA512-Elligator2-FFSTV
H2C-P256-SHA256-SSWU- is defined as follows:
o The destination group is the set of points on the NIST P-256 o The destination group is the set of points on the NIST P-256
elliptic curve, with curve parameters as specified in [DSS] elliptic curve, with curve parameters as specified in [DSS]
(Section D.1.2.3) and [RFC5114] (Section 2.6). (Section D.1.2.3) and [RFC5114] (Section 2.6).
o HashToBase is defined as {#hashtobase} with the hash function o hash2base is defined as {#hashtobase} with the hash function
defined as SHA-256 as specified in [RFC6234], and p set to the defined as SHA-256 as specified in [RFC6234], and p set to the
prime field used in P-256 (2^256 - 2^224 + 2^192 + 2^96 - 1). prime field used in P-256 (2^256 - 2^224 + 2^192 + 2^96 - 1).
o HashToCurve is defined to be {#sswu} with A and B taken from the o HashToCurve is defined to be {#sswu} with A and B taken from the
definition of P-256 (A=-3, B=4105836372515214212932612978004726840 definition of P-256 (A=-3, B=4105836372515214212932612978004726840
9114441015993725554835256314039467401291). 9114441015993725554835256314039467401291).
H2C-P384-SHA512-Icart- is defined as follows: H2C-P384-SHA512-Icart- is defined as follows:
o The destination group is the set of points on the NIST P-384 o The destination group is the set of points on the NIST P-384
elliptic curve, with curve parameters as specified in [DSS] elliptic curve, with curve parameters as specified in [DSS]
(Section D.1.2.4) and [RFC5114] (Section 2.7). (Section D.1.2.4) and [RFC5114] (Section 2.7).
o HashToBase is defined as {#hashtobase} with the hash function o hash2base is defined as {#hashtobase} with the hash function
defined as SHA-512 as specified in [RFC6234], and p set to the defined as SHA-512 as specified in [RFC6234], and p set to the
prime field used in P-384 (2^384 - 2^128 - 2^96 + 2^32 - 1). prime field used in P-384 (2^384 - 2^128 - 2^96 + 2^32 - 1).
o HashToCurve is defined to be {#icart} with A and B taken from the o HashToCurve is defined to be {#icart} with A and B taken from the
definition of P-384 (A=-3, B=2758019355995970587784901184038904809 definition of P-384 (A=-3, B=2758019355995970587784901184038904809
305690585636156852142870730198868924130986086513626076488374510776 305690585636156852142870730198868924130986086513626076488374510776
5439761230575). 5439761230575).
H2C-Curve25519-SHA512-Elligator2-Clear is defined as follows: H2C-Curve25519-SHA512-Elligator2-Clear is defined as follows:
o The destination group is the points on Curve25519, with curve o The destination group is the points on Curve25519, with curve
parameters as specified in [RFC7748] (Section 4.1). parameters as specified in [RFC7748] (Section 4.1).
o HashToBase is defined as {#hashtobase} with the hash function o hash2base is defined as {#hashtobase} with the hash function
defined as SHA-512 as specified in [RFC6234], and p set to the defined as SHA-512 as specified in [RFC6234], and p set to the
prime field used in Curve25519 (2^255 - 19). prime field used in Curve25519 (2^255 - 19).
o HashToCurve is defined to be {#elligator2} with the curve function o HashToCurve is defined to be {#elligator2} with the curve function
defined to be the Montgomery form of Curve25519 (y^2 = x^3 + defined to be the Montgomery form of Curve25519 (y^2 = x^3 +
486662x^2 + x) and u = 2. 486662x^2 + x) and N = 2.
o The final output is multiplied by the cofactor of Curve25519, 8. o The final output is multiplied by the cofactor of Curve25519, 8.
H2C-Curve448-SHA512-Elligator2-Clear is defined as follows: H2C-Curve448-SHA512-Elligator2-Clear is defined as follows:
o The destination group is the points on Curve448, with curve o The destination group is the points on Curve448, with curve
parameters as specified in [RFC7748] (Section 4.1). parameters as specified in [RFC7748] (Section 4.1).
o HashToBase is defined as {#hashtobase} with the hash function o hash2base is defined as {#hashtobase} with the hash function
defined as SHA-512 as specified in [RFC6234], and p set to the defined as SHA-512 as specified in [RFC6234], and p set to the
prime field used in Curve448 (2^448 - 2^224 - 1). prime field used in Curve448 (2^448 - 2^224 - 1).
o HashToCurve is defined to be {#elligator2} with the curve function o HashToCurve is defined to be {#elligator2} with the curve function
defined to be the Montgomery form of Curve448 (y^2 = x^3 + defined to be the Montgomery form of Curve448 (y^2 = x^3 +
156326x^2 + x) and u = -1. 156326x^2 + x) and N = -1.
o The final output is multiplied by the cofactor of Curve448, 4. o The final output is multiplied by the cofactor of Curve448, 4.
H2C-Curve25519-SHA512-Elligator2-FFSTV is defined as in H2C- H2C-Curve25519-SHA512-Elligator2-FFSTV is defined as in H2C-
Curve25519-SHA-512-Elligator2-Clear except HashToCurve is defined to Curve25519-SHA-512-Elligator2-Clear except HashToCurve is defined to
be {#ffstv} where F is {#elligator2}. be {#ffstv} where F is {#elligator2}.
H2C-Curve448-SHA512-Elligator2-FFSTV is defined as in H2C-Curve448- H2C-Curve448-SHA512-Elligator2-FFSTV is defined as in H2C-Curve448-
SHA-512-Elligator2-Clear except HashToCurve is defined to be {#ffstv} SHA-512-Elligator2-Clear except HashToCurve is defined to be {#ffstv}
where F is {#elligator2}. where F is {#elligator2}.
skipping to change at page 17, line 41 skipping to change at page 25, line 23
11. Acknowledgements 11. Acknowledgements
The authors would like to thank Adam Langley for this detailed The authors would like to thank Adam Langley for this detailed
writeup up Elligator2 with Curve25519 [ElligatorAGL]. We also thank writeup up Elligator2 with Curve25519 [ElligatorAGL]. We also thank
Sean Devlin and Thomas Icart for feedback on earlier versions of this Sean Devlin and Thomas Icart for feedback on earlier versions of this
document. document.
12. Contributors 12. Contributors
o Armando Faz
Cloudflare
armfazh@cloudflare.com
o Sharon Goldberg o Sharon Goldberg
Boston University Boston University
goldbe@cs.bu.edu goldbe@cs.bu.edu
o Ela Lee
Royal Holloway, University of London
Ela.Lee.2010@live.rhul.ac.uk
13. Normative References 13. Normative References
[BF01] "Identity-based encryption from the Weil pairing", n.d.. [BF01] Boneh, D. and M. Franklin, "Identity-based encryption from
the Weil pairing", Advances in Cryptology -- CRYPTO 2001,
pages 213-229 , n.d.,
<https://doi.org/10.1007/3-540-44647-8_13>.
[BL07] "Faster addition and doubling on elliptic curves", n.d., [BL07] "Faster addition and doubling on elliptic curves", n.d.,
<https://eprint.iacr.org/2007/286.pdf>. <https://eprint.iacr.org/2007/286.pdf>.
[BL17] "Montgomery curves and the Montgomery ladder", n.d., [BL17] "Montgomery curves and the Montgomery ladder", n.d.,
<https://eprint.iacr.org/2017/293.pdf>. <https://eprint.iacr.org/2017/293.pdf>.
[BLS01] "Short signatures from the Weil pairing", n.d., [BLS01] Dan Boneh, ., Ben Lynn, ., and . Hovav Shacham, "Short
<https://iacr.org/archive/asiacrypt2001/22480516.pdf>. signatures from the Weil pairing", Journal of Cryptology,
v17, pages 297-319 , n.d.,
<https://doi.org/10.1007/s00145-004-0314-9>.
[BMP00] "Provably secure password-authenticated key exchange using [BMP00] Victor Boyko, ., MacKenzie, Philip., and . Sarvar Patel,
"Provably secure password-authenticated key exchange using
diffie-hellman", n.d.. diffie-hellman", n.d..
[BN05] Barreto, P. and M. Naehrig, "Pairing-Friendly Elliptic
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. [DSS] National Institute of Standards and Technology, U.S.
Department of Commerce, "Digital Signature Standard, Department of Commerce, "Digital Signature Standard,
version 4", NIST FIPS PUB 186-4, 2013. version 4", NIST FIPS PUB 186-4, 2013.
[ECOPRF] "EC-OPRF - Oblivious Pseudorandom Functions using Elliptic [ECOPRF] "EC-OPRF - Oblivious Pseudorandom Functions using Elliptic
Curves", n.d.. Curves", n.d..
[Elligator2] [Elligator2]
"Elligator -- Elliptic-curve points indistinguishable from "Elligator -- Elliptic-curve points indistinguishable from
uniform random strings", n.d., <https://dl.acm.org/ uniform random strings", n.d.,
ft_gateway.cfm?id=2516734&type=pdf>. <https://dl.acm.org/ft_gateway.cfm?id=2516734&type=pdf>.
[ElligatorAGL] [ElligatorAGL]
"Implementing Elligator for Curve25519", n.d., "Implementing Elligator for Curve25519", n.d.,
<https://www.imperialviolet.org/2013/12/25/ <https://www.imperialviolet.org/2013/12/25/
elligator.html>. elligator.html>.
[FFSTV13] "Indifferentiable deterministic hashing to elliptic and [FFSTV13] "Indifferentiable deterministic hashing to elliptic and
hyperelliptic curves", n.d.. hyperelliptic curves", n.d..
[FIPS-186-4] [FIPS-186-4]
"Digital Signature Standard (DSS), FIPS PUB 186-4, July "Digital Signature Standard (DSS), FIPS PUB 186-4, July
2013", n.d., 2013", n.d.,
<https://csrc.nist.gov/publications/detail/fips/186/4/ <https://csrc.nist.gov/publications/detail/fips/186/4/
final>. final>.
[hacspec] "hacspec", n.d., <https://github.com/HACS-workshop/ [FT12] Pierre-Alain Fouque, . and . Mehdi Tibouchi,
hacspec>. "Indifferentiable Hashing to Barreto-Naehrig Curves",
LATINCRYPT 2012, pages 1-17. , n.d.,
<https://doi.org/10.1007/978-3-642-33481-8_1>.
[Icart09] "How to Hash into Elliptic Curves", n.d., [github-repo]
"draft-irtf-cfrg-hash-to-curve | github.com", n.d.,
<https://github.com/chris-wood/
draft-irtf-cfrg-hash-to-curve/>.
[hacspec] "hacspec", n.d.,
<https://github.com/HACS-workshop/hacspec>.
[Icart09] Icart, T., "How to Hash into Elliptic Curves", n.d.,
<https://eprint.iacr.org/2009/226.pdf>. <https://eprint.iacr.org/2009/226.pdf>.
[Jablon96] [Jablon96]
"Strong password-only authenticated key exchange", n.d.. "Strong password-only authenticated key exchange", n.d..
[KSS08] Kachisa, E., Schaefer, E., and M. Scott, "Constructing
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 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, <https://www.rfc- DOI 10.17487/RFC2119, March 1997,
editor.org/info/rfc2119>. <https://www.rfc-editor.org/info/rfc2119>.
[RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman [RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman
Groups for Use with IETF Standards", RFC 5114, Groups for Use with IETF Standards", RFC 5114,
DOI 10.17487/RFC5114, January 2008, <https://www.rfc- DOI 10.17487/RFC5114, January 2008,
editor.org/info/rfc5114>. <https://www.rfc-editor.org/info/rfc5114>.
[RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand
Key Derivation Function (HKDF)", RFC 5869, Key Derivation Function (HKDF)", RFC 5869,
DOI 10.17487/RFC5869, May 2010, <https://www.rfc- DOI 10.17487/RFC5869, May 2010,
editor.org/info/rfc5869>. <https://www.rfc-editor.org/info/rfc5869>.
[RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms [RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms
(SHA and SHA-based HMAC and HKDF)", RFC 6234, (SHA and SHA-based HMAC and HKDF)", RFC 6234,
DOI 10.17487/RFC6234, May 2011, <https://www.rfc- DOI 10.17487/RFC6234, May 2011,
editor.org/info/rfc6234>. <https://www.rfc-editor.org/info/rfc6234>.
[RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves
for Security", RFC 7748, DOI 10.17487/RFC7748, January for Security", RFC 7748, DOI 10.17487/RFC7748, January
2016, <https://www.rfc-editor.org/info/rfc7748>. 2016, <https://www.rfc-editor.org/info/rfc7748>.
[RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch,
"PKCS #1: RSA Cryptography Specifications Version 2.2", "PKCS #1: RSA Cryptography Specifications Version 2.2",
RFC 8017, DOI 10.17487/RFC8017, November 2016, RFC 8017, DOI 10.17487/RFC8017, November 2016,
<https://www.rfc-editor.org/info/rfc8017>. <https://www.rfc-editor.org/info/rfc8017>.
[RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital
Signature Algorithm (EdDSA)", RFC 8032, Signature Algorithm (EdDSA)", RFC 8032,
DOI 10.17487/RFC8032, January 2017, <https://www.rfc- DOI 10.17487/RFC8032, January 2017,
editor.org/info/rfc8032>. <https://www.rfc-editor.org/info/rfc8032>.
[SECG1] "SEC 1 -- Elliptic Curve Cryptography", n.d., [SAGE] "SageMath, the Sage Mathematics Software System", n.d.,
<https://www.sagemath.org>.
[Schoof85]
"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
2: Recommended Elliptic Curve Domain Parameters", n.d.,
<http://www.secg.org/sec2-v2.pdf>.
[SECG1] Standards for Efficient Cryptography Group (SECG), ., "SEC
1: Elliptic Curve Cryptography", n.d.,
<http://www.secg.org/sec1-v2.pdf>. <http://www.secg.org/sec1-v2.pdf>.
[SimpleSWU] [SimpleSWU]
"Efficient Indifferentiable Hashing into Ordinary Elliptic "Efficient Indifferentiable Hashing into Ordinary Elliptic
Curves", n.d.. Curves", n.d., <https://eprint.iacr.org/2009/340.pdf>.
[SW06] "Construction of rational points on elliptic curves over [SW06] "Construction of rational points on elliptic curves over
finite fields", n.d.. finite fields", n.d..
[SWU07] "Rational points on certain hyperelliptic curves over [SWU07] "Rational points on certain hyperelliptic curves over
finite fields", n.d., <https://arxiv.org/pdf/0706.1448>. finite fields", n.d., <https://arxiv.org/pdf/0706.1448>.
Appendix A. Related Work Appendix A. Related Work
In this chapter, we give a background to some common methods to In this chapter, we give a background to some common methods to
skipping to change at page 22, line 11 skipping to change at page 30, line 41
Montgomery curves. In this case, there is no need for an encoding 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 function, since the output of F in GF(p) is sufficient to define a
point on one of E or E^d. point on one of E or E^d.
Appendix B. Try-and-Increment Method Appendix B. Try-and-Increment Method
In cases where constant time execution is not required, the so-called In cases where constant time execution is not required, the so-called
try-and-increment method may be appropriate. As discussion in try-and-increment method may be appropriate. As discussion in
Section 1, this variant works by hashing input m using a standard 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 hash function ("Hash"), e.g., SHA256, and then checking to see if the
resulting point E(m, f(m)), for curve function f, belongs on E. This resulting point (m, f(m)), for curve function f, belongs on E. This
is detailed below. is detailed below.
1. ctr = 0 1. ctr = 0
2. h = "INVALID" 2. h = "INVALID"
3. While h is "INVALID" or h is EC point at infinity: 3. While h is "INVALID" or h is EC point at infinity:
4.1 CTR = I2OSP(ctr, 4) 4.1 CTR = I2OSP(ctr, 4)
4.2 ctr = ctr + 1 4.2 ctr = ctr + 1
4.3 attempted_hash = Hash(m || CTR) 4.3 attempted_hash = Hash(m || CTR)
4.4 h = RS2ECP(attempted_hash) 4.4 h = RS2ECP(attempted_hash)
4.5 If h is not "INVALID" and cofactor > 1, set h = h * cofactor 4.5 If h is not "INVALID" and cofactor > 1, set h = h * cofactor
skipping to change at page 25, line 38 skipping to change at page 34, line 38
exp = fmul(fadd(to_felem(prime), to_felem(-1)), finv(to_felem(2))) exp = fmul(fadd(to_felem(prime), to_felem(-1)), finv(to_felem(2)))
e = fexp(h2, exp) e = fexp(h2, exp)
exp = to_felem((prime + 1) // 4) exp = to_felem((prime + 1) // 4)
if e == 1: if e == 1:
return (x2, fexp(f_p256(x2), exp)) return (x2, fexp(f_p256(x2), exp))
else: else:
return (x3, fexp(f_p256(x3), exp)) return (x3, fexp(f_p256(x3), exp))
C.4. Elligator2 Method C.4. Boneh-Franklin Method
The following hacspec program implements map2curve_bf(alpha) for a
supersingular curve "y^2=x^3+1" over "GF(p)" and "p = (2^250)(3^159)-
1".
from hacspec.speclib import *
prime = 2**250*3**159-1
a503 = to_felem(0)
b503 = to_felem(1)
@typechecked
def map2p503(u:felem_t) -> affine_t:
t0 = fsqr(u)
t1 = fsub(t0,b503)
x = fexp(t1, (2 * prime - 1) // 3)
return (x, u)
C.5. Fouque-Tibouchi Method
The following hacspec program implements map2curve_ft(alpha) for a BN
curve "BN256 : y^2=x^3+1" over "GF(p(t))", where "p(x) = 36x^4 +
36x^3 + 24x^2 + 6x + 1", and "t = -(2^62 + 2^55 + 1)".
from hacspec.speclib import *
t = -(2**62 + 2**55 + 1)
p = lambda x: 36*x**4 + 36*x**3 + 24*x**2 + 6*x + 1
prime = p(t)
aBN256 = to_felem(0)
bBN256 = to_felem(1)
@typechecked
def map2BN256(u:felem_t) -> affine_t:
ZERO = to_felem(0)
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)))
flegendre = lambda x: fexp(u, (prime - 1) // 2)
w = finv(fadd(fadd(fsqr(u),B),ONE))
w = fmul(fmul(w,SQRT_MINUS3),u)
e = flegendre(u)
x1 = fsub(ONE_SQRT3_DIV2,fmul(u,w))
fx1 = fcurve(x1)
s1 = flegendre(fx1)
if s1 == 1:
y1 = fmul(fsqrt(fx1),e)
return (x1,y1)
x2 = fsub(ZERO,fadd(ONE,x1))
fx2 = fcurve(x2)
s2 = flegendre(fx2)
if s2 == 1:
y2 = fmul(fsqrt(fx2),e)
return (x2,y2)
x3 = fadd(finv(fsqr(w)),ONE)
fx3 = fcurve(x3)
y3 = fmul(fsqrt(fx3),e)
return (x3,y3)
C.6. Elligator2 Method
The following hacspec program implements map2curve_elligator2(alpha) The following hacspec program implements map2curve_elligator2(alpha)
for Curve25519. for Curve25519.
from curve25519 import * from curve25519 import *
from hacspec.speclib import * from hacspec.speclib import *
a25519 = to_felem(486662) a25519 = to_felem(486662)
b25519 = to_felem(1) b25519 = to_felem(1)
u25519 = to_felem(2) u25519 = to_felem(2)
skipping to change at page 26, line 29 skipping to change at page 37, line 29
power = nat((p25519 - 1) // 2) power = nat((p25519 - 1) // 2)
e = fexp(f_25519(d), power) e = fexp(f_25519(d), power)
x = 0 x = 0
if e != 1: if e != 1:
x = fsub(to_felem(-d), to_felem(a25519)) x = fsub(to_felem(-d), to_felem(a25519))
else: else:
x = d x = d
return x return x
C.5. HashToBase C.7. hash2base
The following procedure implements HashToBase. The following procedure implements hash2base.
HashToBase(x, i) hash2base(x)
Parameters: Parameters:
H - cryptographic hash function to use H - cryptographic hash function to use
hbits - number of bits output by H hbits - number of bits output by H
p - order of the base field Fp p - order of the base field Fp
label - context label for domain separation label - context label for domain separation
Preconditions: Preconditions:
floor(log2(p)) + 1 >= hbits floor(log2(p)) + 1 >= hbits
Input: Input:
x - value to be hashed, an octet string x - an octet string to be hashed
i - hash call index, a non-negative integer
Output: Output:
y - a value in the field Fp y - a value in the field Fp
Steps: Steps:
1. t1 = H("h2c" || label || I2OSP(i, 4) || x) 1. t1 = H("h2c" || label || I2OSP(len(x), 4) || x)
2. t2 = OS2IP(t1) 2. t2 = OS2IP(t1)
3. y = t2 (mod p) 3. y = t2 mod p
4. Output y 4. Output y
where I2OSP, OS2IP [RFC8017] are used to convert an octet string to where I2OSP, OS2IP [RFC8017] are used to convert an octet string to
and from a non-negative integer, and a || b denotes concatenation of and from a non-negative integer, and a || b denotes concatenation of
a and b. a and b.
C.5.1. Considerations C.7.1. Considerations
Performance: HashToBase requires hashing the entire input x. In some Performance: hash2base requires hashing the entire input x. In some
algorithms/ciphersuite combinations, HashToBase is called multiple algorithms/ciphersuite combinations, hash2base is called multiple
times. For large inputs, implementers can therefore consider hashing times. For large inputs, implementers can therefore consider hashing
x before calling HashToBase. I.e. HashToBase(H'(x)). x before calling hash2base. I.e. hash2base(H'(x)).
Most algorithms assume that HashToBase maps its input to the base Most algorithms assume that hash2base maps its input to the base
field uniformly. In practice, there will be inherent biases. For field uniformly. In practice, there will be inherent biases. For
example, taking H as SHA256, over the finite field used by Curve25519 example, taking H as SHA256, over the finite field used by Curve25519
we have p = 2^255 - 19, and thus when reducing from 255 bits, the we have p = 2^255 - 19, and thus when reducing from 255 bits, the
values of 0 .. 19 will be twice as likely to occur. This is a values of 0 .. 19 will be twice as likely to occur. This is a
standard problem in generating uniformly distributed integers from a standard problem in generating uniformly distributed integers from a
bitstring. In this example, the resulting bias is negligible, but bitstring. In this example, the resulting bias is negligible, but
for others this bias can be significant. for others this bias can be significant.
To address this, our HashToBase algorithm greedily takes as many bits To address this, our hash2base algorithm greedily takes as many bits
as possible before reducing mod p, in order to smooth out this bias. as possible before reducing mod p, in order to smooth out this bias.
This is preferable to an iterated procedure, such as rejection This is preferable to an iterated procedure, such as rejection
sampling, since this can be hard to reliably implement in constant sampling, since this can be hard to reliably implement in constant
time. time.
The running time of each map2curve function is dominated by the cost
of finite field inversion. Assuming T_i(F) is the time of inversion
in field F, a rough bound on the running time of each map2curve
function is O(T_i(F)) for the associated field.
Appendix D. Test Vectors
This section contains test vectors, generated from reference Sage
code, for each map2curve variant and the hash2base function described
in Appendix C.7.
D.1. Elligator2 to Curve25519
Input:
alpha =
Intermediate values:
u = 140876c725e59a161990918755b3eff6a9d5e75d69ea20f9a4ebcf
94e69ff013
v = 6a262de4dba3a094ceb2d307fd985a018f55d1c7dafa3416423b46
2c8aaff893
gv = 5dc09f578dca7bfffeac3ec4ad2792c9822cd1d881839e823d26cd
338f6ddc3e
Output:
x = 15d9d21b245c5f6b314d2cf80267a5fe70aa2e382505cbe9bdc4b9
d375489a54
y = 1f132cbbfbb17d3f80eba862a6fb437650775de0b86624f5a40d3e
17739a07ff
Input:
alpha = 00
Intermediate values:
u = 10a97c83decb52945a72fe18511ac9741234de3fb62fa0fec399df
5f390a6a21
v = 6ff5b9893b26c0c8b68adb3d653b335a8e810b4abbdbc13348e828
f74814f4c4
gv = 2d1599d36275c36cabf334c07c62934e940c3248a9d275041f3724
819d7e8b22
Output:
x = 6ff5b9893b26c0c8b68adb3d653b335a8e810b4abbdbc13348e828
f74814f4c4
y = 55345d1e10a5fc1c56434494c47dcfa9c7983c07fcb908f7a38717
ba869a2469
Input:
alpha = ff
Intermediate values:
u = 59c48eefc872abc09321ca7231ecd6c754c65244a86e6315e9e230
716ed674d3
v = 20392de0e96030c4a37cd6f650a86c6bc390bcec21919d9c544f35
f2a2534b2b
gv = 0951a0c55b92e231494695cb775a0653a23f41635e11f97168e231
095dd5c30c
Output:
x = 5fc6d21f169fcf3b5c832909af5793943c6f4313de6e6263abb0ca
0d5da547bc
y = 2b6bf1b3322717ed5640d04659757c8db6615c0dee954fbd695e8a
c9d97e24d1
Input:
alpha = ff0011223344112233441122334411223344556677885566778855
66778855667788
Intermediate values:
u = 380619de15c80fe3668bac96be51b0fd17129f6cf084a250cfaa76
7ff92b6cba
v = 2f3d9063e573c522d8f20c752f15b114f810b53d880154e2f30cde
fdf82bbe26
gv = 4ce282b7cfdca2db63cec91a08b947f10fcf03bc69bafcd1c60b7d
dfc305baaf
Output:
x = 2f3d9063e573c522d8f20c752f15b114f810b53d880154e2f30cde
fdf82bbe26
y = 5e43ab6a0590c11547b910d06d37c96e4cc3fc91adf8a54494d74b
12de6ae45d
D.2. Icart to P-384
Input:
alpha =
Intermediate values:
u = 287d7ef77451ecd3c1c0428092a70b5ed870ca22681c81ac52037d
a7e22a3657d3538fa5ce30488b8e5fb95eb58dda86
u4 = 56aee47e1e72dbae15bd0d5a8462d0228a5db9093268639e1cd015
4aa3e63d81eea72c2d5fa4998f7ca971bb50b44df6
v = eaa16e82d5a88ebb9ff1866640c34693d4de32fdca72921ed2fe4d
cfce3b163dea8ec9e528f7e3b5ca3e27cba5c97db9
x1 = cbc52f2bf7f194a47fd88e3fa4f68fc41cddeea8c47f79c225ad80
455c4db0e5db47209754764929327edf339c19203b
u6 = 5af8bcb067c1fc0bf3c7115481f3bd78afd70e035a9d067060c6e2
164620d477e3247a55e514d0a790a7ddf58e7482fa
x1 = 871a993757d3aa90b7261aa76fc1d74b8b4dcfbc8505f1170e3707
1ab59c9c3a88caa9d6331730503d2b4f94a592b147
Output:
x = b4e57fc7f87adbdc52ab843635313cdf5fb356550b6fbde5741f6b
51b12b33a104bfe2c68bef24139332c7e213f145d5
y = bd3980b713d51ac0f719b6cc045e2168717b74157f6fd0e36d4501
3e2b5c7e0d70dacbb2fb826ad12d3f8a0dc5dc801f
Input:
alpha = 00
Intermediate values:
u = 5584733e5ee080c9dbfa4a91c5c8da5552cce17c74fae9d28380e6
623493df985a7827f02538929373de483477b23521
u4 = 3f8451733c017a3e5acd8a310f5594ae539c74b009fc75aecda7f1
abd42b3a47b1bd8b2b29eb3dd01db0a1bf67f5c15e
v = a20ff29b0a3d0067cb8a53e132753a46f598aa568efe00f9e286a5
e4300c9010f58e3ed97b4b7b356347048f122ca2b8
x1 = d8fcadbc05829f3d7d12493f8720514e2f125751f0dcf91ba8ee5d
4e3456528c1e155cc93ac525562d9c3fcb3e49d3e3
u6 = 35340edd3abbe78fe33fd955e9126d67c6352db6ecbcbcf3abbaa5
30ffa37724d3a51d9d046057d0fa76278f916fa10c
x1 = 382b470b52fbe5de86ed48a824ae3827a738b8cada54c9473d1eee
18b548b8f12389dcea7c47893e18aafad06ab8ff52
Output:
x = a15fe3979721e717f173c54d38882c011be02499d26a070a3bed82
5fcac5a251a1297a9593254a50f8aa243c6191976a
y = 641d1cb53087208240a935769ca1b99c3a97a492526e5b3cfae8c2
0bebde9345c4dd549e2d01d5417918ce039451f4d7
Input:
alpha = ff
Intermediate values:
u = d25e7c84dcdf5b32e8ff5ae510026628d7427b2341c9d885f753a9
72b21e3c82881ab0a2845ec645dd9d6fd4f3c74cb3
u4 = 60cbd41d32d7588ff3634655bd5e5ef6ab9077b7629bb648669cf8
bef00c87b3c7c59bed55d6db75a59fc988ee84db41
v = f3e63b1b10195a28833f391d480df124be3c1cbbaa0c7b5b0252db
405ba97a10d19a6afd134f1c829fd8fba36a3ea5a5
x1 = 9d4c43b595deb99138eb0f7688695abe8a7145d4b8f1f911b8384b
0205c873cfcb6a6092e71b887e0a56e8633987fa7e
u6 = bb44318a26c920aa39270421eb8ff73aac89637d01e6b32697fbd2
c6097d3143fbe8e192372a25be723a0008bcf64326
x1 = aa283d625fdb4d127611e359d6bd6a2d1e63f036a2d9d1373c11d9
1a557ffe24ec208f0408763c524112147fd78fd15e
Output:
x = 26536b1be6480de4e8d3232e17312085d2fc5b4ad18aae3edfe1f6
2c192ebcbed4711aba15be7af83ef691e09aded56c
y = 7533cf819fa713699f4919f79fc0f01c9b632f2e08a5ae34de7d9e
1069b18b256924b9acb7db85c707fb40ef893e4b9e
Input:
alpha = ff0011223344112233441122334411223344556677885566778855
66778855667788
Intermediate values:
u = e1a5025e8e9b6776263767613cd90b685a46fe462c914aaf7dab3b
2ac7b7f6479e6de0790858fae8471beda1d93117c2
u4 = be47baa8671fb710a0cf58c85d95ea9cef2a7d6a6d859f3dbc52be
fde3ad898851a83e166b87eeb7870ce1d3427a56b5
v = 24ed8cb050c045f6401a6221b85c37d482197f54a7340303449c13
52717394450495f4bfa8c0bc12181496db59113671
x1 = a1e180da2f619774632fccb74133963606ffaec0545dcdf225e180
3f04d7bd9fb612bf57145004905142a35a5d1b47f0
u6 = e806b407afd7874ad4ded43a46bc002e0dda1a39a5754cf09dfcb9
9cfc8d19750a4a7e825e06ac256166b91ee3f5e28d
x1 = 41d5d81708d776d643b75fd29658c14fddaf009d8f47a9ec18b9d3
bee961f1544dd7339e6115bffbe638a17658cea94a
Output:
x = 810096c7dec85367fa04f706c2e456334325202b9fcbc34970d9fd
f545c507debc328246489e3c9a8d576b97e6e104d8
y = ddde061cec66efc0cfcdabdc0241fdb00ab2ad28bf8e00dc0d45f8
845c00b6e5c803b133c8deb31b4922d83649c4c249
D.3. SWU to P-256
Input:
alpha =
Intermediate values:
u = d8e1655d6562677a74be47c33ce9edcbefd5596653650e5758c8aa
ab65a99db3
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:
x = 7764572395df002912b7cbb93c9c287f325b57afa1e7e82618ba57
9b796e6ad1
y = 574e9564a28b9104b9dfb104a976f5f6a07c5c5b69e901e596df26
e4f571e369
Input:
alpha = 00
Intermediate values:
u = c4188ee0e554dae7aea559d04d45982d6b184eff86c4a910a43247
44d6fb3c62
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:
x = 331a4d8dead257f3d36e239e9cfaeaaf6804354a5897da421db73a
795c3f9af7
y = 6c6fa249077e13be24cf2cfab67dfcc8407a299e69c817785b8b9a
23eecfe734
Input:
alpha = ff
Intermediate values:
u = 777b56233c4bdb9fe7de8b046189d39e0b2c2add660221e7c4a2d4
58c3034df2
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:
x = 51a60aedc0ade7769bd04a4a3241130e00c7adaa9a1f76f1e115f1
d082902b02
y = 4115534ea22d3b46a9c541a25e72b3f37a2ac7635a6bebb16ff504
c3170fb69a
Input:
alpha = ff0011223344112233441122334411223344556677885566778855
66778855667788
Intermediate values:
u = 87541ffa2efec46a38875330f66a6a53b99edce4e407e06cd0ccaf
39f8208aa6
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:
x = 39150bdb341015403c27154093cd0382d61d27dafe1dbe70836832
23bc3e1b2a
y = 71b6dea4bc8dcae3dab695b69f25a7dbdc4e00f4926407bad89a80
ab12655340
D.4. Simple SWU to P-256
Input:
alpha =
Intermediate values:
u = 650354c1367c575b44d039f35a05f2201b3b3d2a93bf4ad6e5535b
bb5838c24e
n1 = 88d14bad9d79058c1427aa778892529b513234976ce84015c795f3
b3c1860963
x1 = c55836cadcb8cdfd9b9e345c88aa0af67db2d32e6e527de7a5b7a8
59a3f6a2d3
gx1 = 9104bf247de931541fedfd4a483ced90fd3ac32f4bbbb0de021a21
f770fcc7ae
x2 = 0243b55837314f184ed8eca38b733945ec124ffd079850de608c9d
175aed9d29
gx2 = 0f522f68139c6a8ff028c5c24536069441c3eae8a68d49939b2019
0a87e2f170
y2 = 29b59b5c656bfd740b3ea8efad626a01f072eb384f2db56903f67f
e4fbb6ff82
Output:
x = 0243b55837314f184ed8eca38b733945ec124ffd079850de608c9d
175aed9d29
y = 29b59b5c656bfd740b3ea8efad626a01f072eb384f2db56903f67f
e4fbb6ff82
Input:
alpha = 00
Intermediate values:
u = 54acd0c1b3527a157432500fc3403b6f8a0aa0103d6966b783614a
8e41c9c5b1
n1 = bb27567ea0729adc2b7af65a85b7f599559b107ce0d2495c4d26d8
a1ce842372
x1 = 6ae899e0232f040f8a82934f462e1ccedac76ad8549ae581f17c82
1a5944244f
gx1 = 8a78bbf9c2156533fa0d9d37533752508a061b90108675ad705009
7adabff9cb
x2 = 498c0e2faee29adf4e6aed9120eb8c69cd3bb7206bcd47a746fb5e
d4ed5529a5
gx2 = 63adfce3aaa4d56b70cc3e8e7475154b5963855e275ffc26858cbf
2456ea5f52
y1 = 3b81976ce93e79d2ba13394a6b5deb34602d6829f4625d987fc98c
a79d5d5c98
Output:
x = 6ae899e0232f040f8a82934f462e1ccedac76ad8549ae581f17c82
1a5944244f
y = 3b81976ce93e79d2ba13394a6b5deb34602d6829f4625d987fc98c
a79d5d5c98
Input:
alpha = ff
Intermediate values:
u = 86855e4bc3905ae04f6b284820856db6809633c5046ed92816a4e9
976e994818
n1 = 5ec1cf436c1a2e84b53674bcf2470a0aeeda9550c474b06da4bda8
3bda56f2e3
x1 = 04e73147d10de271f7d77a9a3d6dd761d5b892ab39224b9dab93a2
50139b124a
gx1 = 9d26bdc1b5afe7ccf9a7963a099e3c0b98070525b7ed08e8f32f44
aef918b15f
x2 = 28566b4d673bf59f00d42771968bd69b1a54e8b557857ba231cbdd
feb18b38b5
gx2 = 3b7edb432f00509ed44a4e6a2cbdbc69321215097953dac5bab8a9
01a1d0d998
y2 = 6644bab658f2915f2129791db0eb29eaeb34036db1bced721b161e
06caaef008
Output:
x = 28566b4d673bf59f00d42771968bd69b1a54e8b557857ba231cbdd
feb18b38b5
y = 6644bab658f2915f2129791db0eb29eaeb34036db1bced721b161e
06caaef008
Input:
alpha = ff0011223344112233441122334411223344556677885566778855
66778855667788
Intermediate values:
u = 34a8fc904e2d40dabb826b914917a6feea97ec3c0828f41c8716b2
6f8f4b7aaf
n1 = 3b14efe9953378860e667b9051f9e412811e71b489ad8b72a8856f
e57a5473d9
x1 = 8ac342ff43931be5b1a9de4f602994853fa9ec943eacc5e39760df
73fb4d9799
gx1 = b45e916f6478943e1baf89e559c38f95457f2cadc1aaa8d54b0cac
9507ebc6ba
x2 = f9e15f7507632859104da82a28882021608b2c41f2fce3b1a82e43
2841284ec7
gx2 = 1940c3ff4cd98e41cdc5e863eb355168b5d794af03ca374244c7ac
94c5e2f7b0
y2 = 180369d261ec6086346e6b2d36990a3aaa803558f1398b6816c3c6
18d41ff73e
Output:
x = f9e15f7507632859104da82a28882021608b2c41f2fce3b1a82e43
2841284ec7
y = 180369d261ec6086346e6b2d36990a3aaa803558f1398b6816c3c6
18d41ff73e
D.5. Boneh-Franklin to P-503
The P-503 curve is a supersingular curve defined as "y^2=x^3+1" over
"GF(p)", where "p = 2^250*3^159-1".
Input:
alpha =
Intermediate values:
u = 198008fe3da9ee741c2ff07b9d4732df88a3cb98e8227b2cf49d55
57aec1e61d1d29f460c6e4572b2baa21d2444d64d59cdcd2c0dfa2
0144dfab7e92a83e00
t0 = 1f6bb1854a1ff7db82b43c235727d998fe28889152ec4efa533994
fc6d0e77cd9f3ddb8c46226de8e5de75f705370944b809fe0ca092
8587addb9c54ae1a05
t1 = 1f6bb1854a1ff7db82b43c235727d998fe28889152ec4efa533994
fc6d0e77cd9f3ddb8c46226de8e5de75f705370944b809fe0ca092
8587addb9c54ae1a04
x = 04671bff33e7f9f7905848cd4c0fc652bd22200eedf29ef8e13ccb
5536e4aa11db4366d2f346070d63c994bf0a4b1a4e555d6b3d021a
eba340b641ada82054
Output:
x = 04671bff33e7f9f7905848cd4c0fc652bd22200eedf29ef8e13ccb
5536e4aa11db4366d2f346070d63c994bf0a4b1a4e555d6b3d021a
eba340b641ada82054
y = 198008fe3da9ee741c2ff07b9d4732df88a3cb98e8227b2cf49d55
57aec1e61d1d29f460c6e4572b2baa21d2444d64d59cdcd2c0dfa2
0144dfab7e92a83e00
Input:
alpha = 00
Intermediate values:
u = 30e30a56d82cdca830f08d729ce909fc1ffec68df49ba75f9a1af7
2ca242e92742f34b474a299bb452c6a71b69bdc9ee2403eaac7c84
120a160737d667e29e
t0 = 0a64d9f288a0881bb6addebc0db89f146b282b05570efa3419f5d3
2f11ec7bb449a1da8b33817642f01db039f838ad0bd459ec03e76d
8eec3a1e79d6c63f79
t1 = 0a64d9f288a0881bb6addebc0db89f146b282b05570efa3419f5d3
2f11ec7bb449a1da8b33817642f01db039f838ad0bd459ec03e76d
8eec3a1e79d6c63f78
x = 0970ff4bb9237704cc30f5b0d80a9d97001064ab4cdb98de74f8d7
283b922726406393c07ad01de0499e46ebc0ed1cd116112cf8965f
b8f918205adb13d3da
Output:
x = 0970ff4bb9237704cc30f5b0d80a9d97001064ab4cdb98de74f8d7
283b922726406393c07ad01de0499e46ebc0ed1cd116112cf8965f
b8f918205adb13d3da
y = 30e30a56d82cdca830f08d729ce909fc1ffec68df49ba75f9a1af7
2ca242e92742f34b474a299bb452c6a71b69bdc9ee2403eaac7c84
120a160737d667e29e
Input:
alpha = ff
Intermediate values:
u = 3808ae24b17af9147bd16077e3e83aff5c579784c8a1443d90e5ff
e2451bfabacba73ee8b8f652b991290f5c64b34b1a4c9a498e21d4
3d000dae7f8860200a
t0 = 2282d37dce4761dad69d1fe012c8580ba4e23158a0621fb3f51813
10e7275e95573c89a8f0cda7ad98ca9e0a9e04ef94a1a79685d069
6ac6ad423a0de96b7d
t1 = 2282d37dce4761dad69d1fe012c8580ba4e23158a0621fb3f51813
10e7275e95573c89a8f0cda7ad98ca9e0a9e04ef94a1a79685d069
6ac6ad423a0de96b7c
x = 173dc6d853d9024f367e24a283768e11ce559473e788f3c0ed0281
6b48403fc6e100d4935b3f6197799bfbd4fbd94b3656596252f12b
27fa46602c76ae1370
Output:
x = 173dc6d853d9024f367e24a283768e11ce559473e788f3c0ed0281
6b48403fc6e100d4935b3f6197799bfbd4fbd94b3656596252f12b
27fa46602c76ae1370
y = 3808ae24b17af9147bd16077e3e83aff5c579784c8a1443d90e5ff
e2451bfabacba73ee8b8f652b991290f5c64b34b1a4c9a498e21d4
3d000dae7f8860200a
Input:
alpha = ff0011223344112233441122334411223344556677885566778855
66778855667788
Intermediate values:
u = 3ebdfccb07ddc61d9f81be2b9f5a7a8733581f1a8d531d78229d7b
0be50f30887f085ef393422ef96e06ff1df4b608b05c53320a9012
09b8df48b68ab338ec
t0 = 27958e69b08a9fd2d1765ce3e8dbaf8645c28e5ce033b9d0a7875c
e7e73d6583e62ff3a06a2b55de1cb8c26819d0cd4aed2dc7cb65fa
d5eb3c149db9e8381b
t1 = 27958e69b08a9fd2d1765ce3e8dbaf8645c28e5ce033b9d0a7875c
e7e73d6583e62ff3a06a2b55de1cb8c26819d0cd4aed2dc7cb65fa
d5eb3c149db9e8381a
x = 3fe94cd4d2be061834d1a5020ca181562fdb7e9787f71965ca55cd
dbf069b68ddd5e2b05a5696a061723093914e69b0540402baa0db3
fddc517df4211daea1
Output:
x = 3fe94cd4d2be061834d1a5020ca181562fdb7e9787f71965ca55cd
dbf069b68ddd5e2b05a5696a061723093914e69b0540402baa0db3
fddc517df4211daea1
y = 3ebdfccb07ddc61d9f81be2b9f5a7a8733581f1a8d531d78229d7b
0be50f30887f085ef393422ef96e06ff1df4b608b05c53320a9012
09b8df48b68ab338ec
D.6. Fouque-Tibouchi to BN256
An instance of a BN curve is defined as "BN256: y^2=x^3+1" over
"GF(p(t))" such that
t = -(2^62 + 2^55 + 1).
p = 0x2523648240000001ba344d80000000086121000000000013a700000000000013
Input:
alpha =
Intermediate values:
u = 1f6f2aceae3d9323ea64e9be00566f863cc1583385eaff6b01aed7
a762b11122
t0 = 1e9c884ab8d2015985a3e3d2764798b183ff5982b0fd9034f27456
0f19d06ed0
x1 = 0843eb0f5ed559e940a453f257b2a2e297895ecc2375a070168117
b5127ec2ae
x2 = 1cdf7972e12aa618798ff98da84d5d25c997a133dc8a5fa3907ee8
4aed813d64
x3 = 042f756fe42e2ed4c58990da3b2567a7b16252c0e17b2da55b8f68
be71ebd432
e = 2523648240000001ba344d80000000086121000000000013a70000
0000000012
fx1 = 0a8442855e93541a104052273e2bba930338d392d71f70efe83c77
ae95471a4e
y1 = 135a017a32abc542796e55d0b68840546c3b2498963773635e27c2
5aa3737199
Output:
x = 0843eb0f5ed559e940a453f257b2a2e297895ecc2375a070168117
b5127ec2ae
y = 135a017a32abc542796e55d0b68840546c3b2498963773635e27c2
5aa3737199
Input:
alpha = 00
Intermediate values:
u = 053c7251b0e5e5c9acde43c6abd44ffeb13109f61ec27ba0a8191f
1165435065
t0 = 0377baf027b80854661187280a98ae1320d7fd8cb0a65fd7077270
6c38cb71d8
x1 = 0f5173cd2eb8d4352497a9cb56ebf40b623d9dabb7dcc3f626b1f3
89e49b9356
x2 = 15d1f0b511472bcc959ca3b4a9140bfcfee3625448233c1d804e0c
761b646cbc
x3 = 100fb33cea2b98b99ca5a279e1b4e5b0cf6927ded3cb729a822483
809e486dc7
e = 2523648240000001ba344d80000000086121000000000013a70000
0000000012
fx1 = 044c88525cbf81408b9bac1c83bdc49e3f31ec5a7b68495b5d03e5
18448a7f09
y1 = 18e4bd91f687e110fb5f57411fccf34b4b1d16d3d978a75d988c38
d338522d7c
Output:
x = 0f5173cd2eb8d4352497a9cb56ebf40b623d9dabb7dcc3f626b1f3
89e49b9356
y = 18e4bd91f687e110fb5f57411fccf34b4b1d16d3d978a75d988c38
d338522d7c
Input:
alpha = ff
Intermediate values:
u = 077033c69096f00eb76446a64be88c7ae5f1921b977381a6f2e9a8
336191e783
t0 = 1716fb7790dd8e2e5a3ef94d63ca31682dd8b92ce13b93e0977943
bf4c364c72
x1 = 187ca1d0f0dec664467d49b4a4a661602faac5453fbd4ad9e3f15d
a35627459e
x2 = 0ca6c2b14f21399d73b703cb5b599ea831763abac042b539c30ea2
5ca9d8ba74
x3 = 0f694914de2533b1fbab6495b1de12cde6965bba0b505b527c1cb0
69a5fdfd03
e = 000000000000000000000000000000000000000000000000000000
0000000001
fx1 = 067a294268373f0123d95357d7d46c730277e67e68daf3a2c605bf
035f680a7b
y1 = 0de5f5d8ecfc19580a882c53c08b47791edf4499965df86263c525
afd4fe0769
Output:
x = 187ca1d0f0dec664467d49b4a4a661602faac5453fbd4ad9e3f15d
a35627459e
y = 0de5f5d8ecfc19580a882c53c08b47791edf4499965df86263c525
afd4fe0769
Input:
alpha = ff0011223344112233441122334411223344556677885566778855
66778855667788
Intermediate values:
u = 1dd9ec37d5abeed0f289daddd685d45a395a90f2730a9adead62bf
1ae2fe958b
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:
x = 09c1ba4259e59a54221b5761cf9438a60e6cd644996e7c8a11be96
88718e0261
y = 190e8d47070240ff3c78a03d07123334e67b207fe555c31d0900fe
71ab33035e
D.7. Sample hash2base
hash2base("H2C-Curve25519-SHA256-Elligator-Clear", 1234)
= 1e10b542835e7b227c727bd0a7b2790f39ca1e09fc8538b3c70ef736cb1c298f
hash2base("H2C-P256-SHA512-SWU-", 1234)
= 4fabef095423c97566bd28b70ee70fb4dd95acfeec076862f4e40981a6c9dd85
hash2base("H2C-P256-SHA512-SSWU-", 1234)
= d6f685079d692e24ae13ab154684ae46c5311b78a704c6e11b2f44f4db4c6e47
Authors' Addresses Authors' Addresses
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
 End of changes. 110 change blocks. 
361 lines changed or deleted 1514 lines changed or added

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