Skip to main content

Hashing to Elliptic Curves
draft-irtf-cfrg-hash-to-curve-00

The information below is for an old version of the document.
Document Type
This is an older version of an Internet-Draft that was ultimately published as RFC 9380.
Authors Nick Sullivan , Christopher A. Wood
Last updated 2018-04-08 (Latest revision 2018-03-23)
Replaces draft-sullivan-cfrg-hash-to-curve
RFC stream Internet Research Task Force (IRTF)
Formats
IETF conflict review conflict-review-irtf-cfrg-hash-to-curve, conflict-review-irtf-cfrg-hash-to-curve, conflict-review-irtf-cfrg-hash-to-curve, conflict-review-irtf-cfrg-hash-to-curve, conflict-review-irtf-cfrg-hash-to-curve, conflict-review-irtf-cfrg-hash-to-curve
Additional resources Mailing list discussion
Stream IRTF state Active RG Document
Consensus boilerplate Unknown
Document shepherd (None)
IESG IESG state Became RFC 9380 (Informational)
Telechat date (None)
Responsible AD (None)
Send notices to (None)
draft-irtf-cfrg-hash-to-curve-00
Network Working Group                                        N. Sullivan
Internet-Draft                                                Cloudflare
Intended status: Informational                                   C. Wood
Expires: September 24, 2018                                   Apple Inc.
                                                          March 23, 2018

                       Hashing to Elliptic Curves
                    draft-irtf-cfrg-hash-to-curve-00

Abstract

   This document specifies a number of algorithms that may be used to
   hash arbitrary strings to Elliptic Curves.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on September 24, 2018.

Copyright Notice

   Copyright (c) 2018 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (https://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Sullivan & Wood        Expires September 24, 2018               [Page 1]
Internet-Draft                hash-to-curve                   March 2018

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
     1.1.  Requirements  . . . . . . . . . . . . . . . . . . . . . .   3
   2.  Algorithm Recommendations . . . . . . . . . . . . . . . . . .   3
   3.  Generic Interface . . . . . . . . . . . . . . . . . . . . . .   4
     3.1.  Utility Functions . . . . . . . . . . . . . . . . . . . .   4
   4.  Hashing Variants  . . . . . . . . . . . . . . . . . . . . . .   5
     4.1.  Icart Method  . . . . . . . . . . . . . . . . . . . . . .   5
     4.2.  Shallue-Woestijne-Ulas Method . . . . . . . . . . . . . .   6
     4.3.  Simplified SWU Method . . . . . . . . . . . . . . . . . .   6
     4.4.  Elligator2 Method . . . . . . . . . . . . . . . . . . . .   8
   5.  Curve Transformations . . . . . . . . . . . . . . . . . . . .  10
   6.  Cost Comparison . . . . . . . . . . . . . . . . . . . . . . .  10
   7.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  11
   8.  Security Considerations . . . . . . . . . . . . . . . . . . .  11
   9.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .  11
   10. Contributors  . . . . . . . . . . . . . . . . . . . . . . . .  11
   11. Normative References  . . . . . . . . . . . . . . . . . . . .  11
   Appendix A.  Try-and-Increment Method . . . . . . . . . . . . . .  13
   Appendix B.  Sample Code  . . . . . . . . . . . . . . . . . . . .  13
     B.1.  Icart Method  . . . . . . . . . . . . . . . . . . . . . .  13
     B.2.  Shallue-Woestijne-Ulas Method . . . . . . . . . . . . . .  14
     B.3.  Simplified SWU Method . . . . . . . . . . . . . . . . . .  15
     B.4.  Elligator2 Method . . . . . . . . . . . . . . . . . . . .  16
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  17

1.  Introduction

   Many cryptographic protocols require a procedure which maps arbitrary
   input, e.g., passwords, to points on an elliptic curve (EC).
   Prominent examples include Simple Password Exponential Key Exchange
   [Jablon96], Password Authenticated Key Exchange [BMP00], and Boneh-
   Lynn-Shacham signatures [BLS01].

   Let E be an elliptic curve over base field GF(p).  In practice,
   efficient (polynomial-time) functions that hash arbitrary input to E
   can be constructed by composing a cryptographically secure hash
   function F1 : {0,1}^* ->GF(p) and an injection F2 : GF(p) -> E, i.e.,
   Hash(m) = F2(F1(m)).  Probabilistic constructions of Hash, e.g., the
   MapToGroup function described by Boneh et al.  [BLS01].  Their
   algorithm fails with probability 2^I, where I is a tunable parameter
   that one can control.  Another variant, dubbed the "Try and
   Increment" approach, was described by Boneh et al.  [BLS01].  This
   function works by hashing input m using a standard hash function,
   e.g., SHA256, and then checking to see if the resulting point E(m,
   f(m)), for curve function f, belongs on E.  This algorithm is
   expected to find a valid curve point after approximately two

Sullivan & Wood        Expires September 24, 2018               [Page 2]
Internet-Draft                hash-to-curve                   March 2018

   attempts, i.e., when ctr=1, on average.  (See Appendix Appendix A for
   a more detailed description of this algorithm.)  Since the running
   time of the algorithm depends on m, this algorithm is NOT safe for
   cases sensitive to timing side channel attacks.  Deterministic
   algorithms are needed in such cases where failures are undesirable.
   Shallue and Woestijne [SWU] first introduced a deterministic
   algorithm that maps elements in F_{q} to an EC 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].

   This document specifies several algorithms for deterministically
   hashing onto a curve with varying properties: Icart, SWU, Simplified
   SWU, and Elligator2.  Each algorithm conforms to a common interface,
   i.e., it maps an element from a base field F to a curve E.  For each
   variant, we describe the requirements for F and E to make it work.
   Sample code for each variant is presented in the appendix.  Unless
   otherwise stated, all elliptic curve points are assumed to be
   represented as affine coordinates, i.e., (x, y) points on a curve.

1.1.  Requirements

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].

2.  Algorithm Recommendations

   The following table lists recommended algorithms to use for specific
   curves.

                  +------------+------------------------+
                  | Curve      | Algorithm              |
                  +------------+------------------------+
                  | P-256      | SWU Section 4.3        |
                  |            |                        |
                  | P-384      | Icart Section 4.1      |
                  |            |                        |
                  | Curve25519 | Elligator2 Section 4.4 |
                  |            |                        |
                  | Curve448   | Elligator2 Section 4.4 |
                  +------------+------------------------+

Sullivan & Wood        Expires September 24, 2018               [Page 3]
Internet-Draft                hash-to-curve                   March 2018

   The SWU variant from Section Section 4.2 applies to any curve.  As
   such, this algorithm SHOULD be used if no other better alternative is
   known.  More efficient variants and their curve requirements are
   shown in the table below.  These MAY be used if the target curve
   meets the listed criteria.

   +--------------------+----------------------------------------------+
   | Algorithm          | Requirement                                  |
   +--------------------+----------------------------------------------+
   | Icart Section 4.1  | p = 2 mod 3                                  |
   |                    |                                              |
   | SWU Section 4.2    | None                                         |
   |                    |                                              |
   | Simplified SWU     | p = 3 mod 4                                  |
   | Section 4.3        |                                              |
   |                    |                                              |
   | Elligator2 Section | p is large and there is a point of order two |
   | 4.4                | and j-invariant != 1728                      |
   +--------------------+----------------------------------------------+

3.  Generic Interface

   The generic interface for hashing to elliptic curves is as follows:

   hash_to_curve(alpha)

   where alpha is a message to hash onto a curve.

3.1.  Utility Functions

   Algorithms in this document make use of utility functions described
   below.

   o  HashToBase(x): H(x)[0:log2(p) + 1], i.e., hash-truncate-reduce,
      where H is a cryptographic hash function, such as SHA256, and p is
      the prime order of base field Fp.

   o  CMOV(a, b, c): If c = 1, return a, else return b.

   Note: We assume that HashToBase maps its input to the base field
   uniformly.  In practice, there may be inherent biases in p, e.g., p =
   2^k - 1 will have non-negligible bias in higher bits.

   ((TODO: expand on this problem))

Sullivan & Wood        Expires September 24, 2018               [Page 4]
Internet-Draft                hash-to-curve                   March 2018

4.  Hashing Variants

4.1.  Icart Method

   The following hash_to_curve_icart(alpha) implements the Icart method
   from [Icart09].  This algorithm works for any curve over F_{p^n},
   where p^n = 2 mod 3 (or p = 2 mod 3 and for odd n), including:

   o  P384

   o  Curve1174

   o  Curve448

   Unsupported curves include: P224, P256, P521, and Curve25519 since,
   for each, p = 1 mod 3.

   Mathematically, given input alpha, and A and B from E, the Icart
   method works as follows:

   u = HashToBase(alpha)
   x = (v^2 - b - (u^6 / 27))^(1/3) + (u^2 / 3)
   y = ux + v

   where v = ((3A - u^4) / 6u).

   The following procedure implements this algorithm in a straight-line
   fashion.  It requires knowledge of A and B, the constants from the
   curve Weierstrass form.  It outputs a point with affine coordinates.

Sullivan & Wood        Expires September 24, 2018               [Page 5]
Internet-Draft                hash-to-curve                   March 2018

  hash_to_curve_icart(alpha)

  Input:

    alpha - value to be hashed, an octet string

  Output:

    (x, y) - a point in E

  Steps:

  1.   u = HashToBase(alpha)   // {0,1}^* -> Fp
  2.  u2 = u^2 (mod p)         // u^2
  3.  t2 = u2^2 (mod p)        // u^4
  4.  v1 = 3 * A (mod p)       // 3A
  5.  v1 = v1 - t2 (mod p)     // 3A - u^4
  6.  t1 = 6 * u (mod p)       // 6u
  7.  t3 = t1 ^ (-1) (mod p)   // modular inverse
  8.   v = v1 * t3 (mod p)     // (3A - u^4)/(6u)
  9.   x = v^2 (mod p)         // v^2
  10.  x = x - B (mod p)       // v^2 - b
  11. t1 = 27 ^ (-1) (mod p)   // 1/27
  12. t1 = t1 * u2 (mod p)     // u^4 / 27
  13. t1 = t1 * t2 (mod p)     // u^6 / 27
  14.  x = x - t1 (mod p)      // v^2 - b - u^6/27
  15. t1 = (2 * p) - 1 (mod p) // 2p - 1
  16. t1 = t1 / 3 (mod p)      // (2p - 1)/3
  17.  x = x^t1 (mod p)        // (v^2 - b - u^6/27) ^ (1/3)
  18. t2 = u2 / 3 (mod p)      // u^2 / 3
  19.  x = x + t2 (mod p)      // (v^2 - b - u^6/27) ^ (1/3) + (u^2 / 3)
  20.  y = u * x (mod p)       // ux
  21.  y = y + v (mod p)       // ux + v
  22. Output (x, y)

4.2.  Shallue-Woestijne-Ulas Method

   ((TODO: write this section))

4.3.  Simplified SWU Method

   The following hash_to_curve_simple_swu(alpha) implements the
   simplfied Shallue-Woestijne-Ulas algorithm from [SimpleSWU].  This
   algorithm works for any curve over F_{p^n}, where p = 3 mod 4,
   including:

   o  P256

Sullivan & Wood        Expires September 24, 2018               [Page 6]
Internet-Draft                hash-to-curve                   March 2018

   o  ...

   Given curve equation g(x) = x^3 + Ax + B, this algorithm works as
   follows:

   1. t = HashToBase(alpha)
   2. alpha = (-b / a) * (1 + (1 / (t^4 + t^2)))
   3. beta = -t^2 * alpha
   4. z = t^3 * g(alpha)
   5. Output (-g * alpha) * (g * beta)

   The following procedure implements this algorithm.  It outputs a
   point with affine coordinates.

Sullivan & Wood        Expires September 24, 2018               [Page 7]
Internet-Draft                hash-to-curve                   March 2018

   hash_to_curve_simple_swu(alpha)

   Input:

     alpha - value to be hashed, an octet string

   Output:

     (x, y) - a point in E

   Steps:

   1.     t = HashToBase(alpha)
   2. alpha = t^2 (mod p)
   3. alpha = alpha * -1 (mod p)
   4. right = alpha^2 + alpha (mod p)
   5. right = right^(-1) (mod p)
   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 = (y1 ^ 2 == h2)
   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)

4.4.  Elligator2 Method

   The following hash_to_curve_elligator2(alpha) implements the
   Elligator2 method from [Elligator2].  This algorithm works for any
   curve with a point of order 2 and j-invariant != 1728.  Given curve
   equation f(x) = y^2 = x(x^2 + Ax + B), i.e., a Montgomery form with
   the point of order 2 at (0,0), this algorithm works as shown below.
   (Note that any curve with a point of order 2 is isomorphic to this
   representation.)

Sullivan & Wood        Expires September 24, 2018               [Page 8]
Internet-Draft                hash-to-curve                   March 2018

   1. r = HashToBase(alpha)
   2. If f(-A/(1+ur^2)) is square, then output f(-A/(1+ur^2))^(1/2)
   3. Else, output f(-Aur^2/(1+ur^2))^(1/2)

   Another way to express this algorithm is as follows:

   1. r = HashToBase(alpha)
   2. d = -A / (1 + ur^2)
   3. e = f(d)^((p-1)/2)
   4. u = ed - (1 - e)A/u

   Here, e is the Legendre symbol of y = (d^3 + Ad^2 + d), which will be
   1 if y is a quadratic residue (square) mod p, and -1 otherwise.
   (Note that raising y to ((p -1) / 2) is a common way to compute the
   Legendre symbol.)

   The following procedure implements this algorithm.

Sullivan & Wood        Expires September 24, 2018               [Page 9]
Internet-Draft                hash-to-curve                   March 2018

   hash_to_curve_elligator2(alpha)

   Input:

     alpha - value to be hashed, an octet string

     u - fixed non-square value in Fp.
     f() - Curve function

   Output:

     (x, y) - a point in E

   Steps:

   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 symbol
   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.  u = v - v2 (mod p)
   19. Output (u, f(u))

   Elligator2 can be simplified with projective coordinates.

   ((TODO: write this variant))

5.  Curve Transformations

   ((TODO: write this section))

6.  Cost Comparison

   The following table summarizes the cost of each hash_to_curve
   variant.  We express this cost in terms of additions (A),
   multiplications (M), squares (SQ), and square roots (SR).

Sullivan & Wood        Expires September 24, 2018              [Page 10]
Internet-Draft                hash-to-curve                   March 2018

   ((TODO: finish this section))

             +--------------------------+-------------------+
             | Algorithm                | Cost (Operations) |
             +--------------------------+-------------------+
             | hash_to_curve_icart      | TODO              |
             |                          |                   |
             | hash_to_curve_swu        | TODO              |
             |                          |                   |
             | hash_to_curve_simple_swu | TODO              |
             |                          |                   |
             | hash_to_curve_elligator2 | TODO              |
             +--------------------------+-------------------+

7.  IANA Considerations

   This document has no IANA actions.

8.  Security Considerations

   Each hash function variant accepts arbitrary input and maps it to a
   pseudorandom point on the curve.  Points are close to
   indistinguishable from randomly chosen elements on the curve.  Some
   variants variants are not 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.

9.  Acknowledgements

   The authors would like to thank Adam Langley for this detailed
   writeup up Elligator2 with Curve25519 [ElligatorAGL].  We also thank
   Sean Devlin and Thomas Icart for feedback on earlier versions of this
   document.

10.  Contributors

   o  Sharon Goldberg
      Boston University
      goldbe@cs.bu.edu

11.  Normative References

   [BLS01]    "Short signatures from the Weil pairing", n.d.,
              <https://iacr.org/archive/asiacrypt2001/22480516.pdf>.

   [BMP00]    "Provably secure password-authenticated key exchange using
              diffie-hellman", n.d..

Sullivan & Wood        Expires September 24, 2018              [Page 11]
Internet-Draft                hash-to-curve                   March 2018

   [ECOPRF]   "EC-OPRF - Oblivious Pseudorandom Functions using Elliptic
              Curves", n.d..

   [Elligator2]
              "Elligator -- Elliptic-curve points indistinguishable from
              uniform random strings", n.d.,
              <https://dl.acm.org/ft_gateway.cfm?id=2516734&type=pdf>.

   [ElligatorAGL]
              "Implementing Elligator for Curve25519", n.d.,
              <https://www.imperialviolet.org/2013/12/25/
              elligator.html>.

   [Icart09]  "How to Hash into Elliptic Curves", n.d.,
              <https://eprint.iacr.org/2009/226.pdf>.

   [Jablon96]
              "Strong password-only authenticated key exchange", n.d..

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://www.rfc-editor.org/info/rfc2119>.

   [RFC7748]  Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves
              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,
              "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
              Signature Algorithm (EdDSA)", RFC 8032,
              DOI 10.17487/RFC8032, January 2017,
              <https://www.rfc-editor.org/info/rfc8032>.

   [SECG1]    "SEC 1 -- Elliptic Curve Cryptography", n.d.,
              <http://www.secg.org/sec1-v2.pdf>.

   [SimpleSWU]
              "Efficient Indifferentiable Hashing into Ordinary Elliptic
              Curves", n.d..

   [SWU]      "Rational points on certain hyperelliptic curves over
              finite fields", n.d., <https://arxiv.org/pdf/0706.1448>.

Sullivan & Wood        Expires September 24, 2018              [Page 12]
Internet-Draft                hash-to-curve                   March 2018

Appendix A.  Try-and-Increment Method

   In cases where constant time execution is not required, the so-called
   try-and-increment method may be appropriate.  As discussion in
   Section 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 E(m, f(m)), for curve function f, belongs
   on E.  This is detailed below.

   1. ctr = 0
   3. h = "INVALID"
   4. While h is "INVALID" or h is EC point at infinity:
      A.  CTR = I2OSP(ctr, 4)
      B.  ctr = ctr + 1
      C.  attempted_hash = Hash(m || CTR)
      D.  h = RS2ECP(attempted_hash)
      E.  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
   string as defined in Section 4.1 of [RFC8017], and RS2ECP is a
   function that converts of a random 2n-octet string to an EC point as
   specified in Section 5.1.3 of [RFC8032].

Appendix B.  Sample Code

B.1.  Icart Method

   The following Sage program implements hash_to_curve_icart(alpha) for
   P-384.

p = 394020061963944792122790401001436138050797392704654466679482934042 \
45721771496870329047266088258938001861606973112319
F = GF(p)
A = p - 3
B = 0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875a \
c656398d8a2ed19d2a85c8edd3ec2aef
q = 394020061963944792122790401001436138050797392704654466679469052796 \
27659399113263569398956308152294913554433653942643
E = EllipticCurve([F(A), F(B)])
g = E(0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a \
385502f25dbf55296c3a545e3872760ab7, \
    0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c0 \
0a60b1ce1d7e819d7a431d7c90ea0e5f)
E.set_order(q)

def icart(u):
  u = F(u)

Sullivan & Wood        Expires September 24, 2018              [Page 13]
Internet-Draft                hash-to-curve                   March 2018

  v = (3*A - u^4)//(6*u)
  x = (v^2 - B - u^6/27)^((2*p-1)//3) + u^2/3
  y = u*x + v
  return E(x, y)

def icart_straight(u):
    u = F(u)
    u2 = u ^ 2
    t2 = u2 ^ 2
    assert t2 == u^4

    v1 = 3 * A
    v1 = v1 - t2
    t1 = 6 * u
    t3 = t1 ^ (-1)
    v = v1 * t3
    assert v == (3 * A - u^4) // (6 * u)

    x = v ^ 2
    x = x - B
    assert x == (v^2 - B)

    t1 = F(27) ^ (-1)
    t1 = t1 * u2
    t1 = t1 * t2
    assert t1 == ((u^6) / 27)

    x = x - t1
    t1 = (2 * p) - 1
    t1 = t1 / 3
    assert t1 == ((2*p) - 1) / 3

    x = x ^ t1

    t2 = u2 / 3
    x = x + t2
    y = u * x
    y = y + v
    return E(x, y)

B.2.  Shallue-Woestijne-Ulas Method

   ((TODO: write this section))

Sullivan & Wood        Expires September 24, 2018              [Page 14]
Internet-Draft                hash-to-curve                   March 2018

B.3.  Simplified SWU Method

   The following Sage program implements hash_to_curve_swu(alpha) for
   P-256.

p = 115792089210356248762697446949407573530086143415290314195533631308 \
867097853951
F = GF(p)
A = F(p - 3)
B = F(ZZ("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2 \
604b", 16))
E = EllipticCurve([A, B])

def simple_swu(alpha):
    t = F(alpha)

    alpha = -(t^2)
    frac = (1 / (alpha^2 + alpha))
    x2 = (-B / A) * (1 + frac)

    x3 = alpha * x2
    h2 = x2^3 + A * x2 + B
    h3 = x3^3 + A * x3 + B

    if is_square(h2):
        return E(x2, h2^((p + 1) // 4))
    else:
        return E(x3, h3^((p + 1) // 4))

def simple_swu_straight(alpha):
    t = F(alpha)

    alpha = t^2
    alpha = alpha * -1

    right = alpha^2 + alpha
    right = right^(-1)
    right = right + 1

    left = B * -1
    left = left / A

    x2 = left * right
    x3 = alpha * x2

    h2 = x2 ^ 3
    i2 = x2 * A
    i2 = i2 + B

Sullivan & Wood        Expires September 24, 2018              [Page 15]
Internet-Draft                hash-to-curve                   March 2018

    h2 = h2 + i2

    h3 = x3 ^ 3
    i3 = x3 * A
    i3 = i3 + B
    h3 = h3 + i3

    y1 = h2^((p + 1) // 4)
    y2 = h3^((p + 1) // 4)

    # Is it square?
    e = y1^2 == h2

    x = x2
    if e != 1:
        x = x3

    y = y1
    if e != 1:
        y = y2

    return E(x, y)

B.4.  Elligator2 Method

   The following Sage program implements hash_to_curve_elligator2(alpha)
   for Curve25519.

   p = 2**255 - 19
   F = GF(p)
   A = 486662
   B = 1
   E = EllipticCurve(F, [0, A, 0, 1, 0])

   def curve25519(x):
       return x^3 + (A * x^2) + x

   def elligator2(alpha):

       r = F(alpha)

       # u is a fixed nonsquare value, eg -1 if p==3 mod 4.
       u = F(2) # F(2)
       assert(not u.is_square())

       # If f(-A/(1+ur^2)) is square, return its square root.
       # Else, return the square root of f(-Aur^2/(1+ur^2)).
       x = -A / (1 + (u * r^2))

Sullivan & Wood        Expires September 24, 2018              [Page 16]
Internet-Draft                hash-to-curve                   March 2018

       y = curve25519(x)
       if y.is_square(): # is this point square?
           y = y.square_root()
       else:
           x = (-A * u * r^2) / (1 + (u * r^2))
           y = curve25519(x).square_root()

       return (x, curve25519(x))

   def elligator2_straight(alpha):
       r = F(alpha)

       r = r^2
       r = r * 2
       r = r + 1
       r = r^(-1)
       v = A * r
       v = v * -1 # d

       v2 = v^2
       v3 = v * v2
       e = v3 + v
       v2 = v2 * A
       e = v2 + e

       # Legendre symbol
       e = e^((p - 1) / 2)

       nv = v * -1
       if e != 1:
           v = nv

       v2 = 0
       if e != 1:
           v2 = A

       u = v - v2

       return (u, curve25519(u))

Authors' Addresses

Sullivan & Wood        Expires September 24, 2018              [Page 17]
Internet-Draft                hash-to-curve                   March 2018

   Nick Sullivan
   Cloudflare
   101 Townsend St
   San Francisco
   United States of America

   Email: nick@cloudflare.com

   Christopher A. Wood
   Apple Inc.
   One Apple Park Way
   Cupertino, California 95014
   United States of America

   Email: cawood@apple.com

Sullivan & Wood        Expires September 24, 2018              [Page 18]