Merge pull request #4357

8501b8df crypto_ops_builder: link to EdDSA/Ed25519 draft RFC (moneromooo-monero)

1 files changed, 3 insertions, 1401 deletions

diff --git a/src/crypto/crypto_ops_builder/ietf.txt b/src/crypto/crypto_ops_builder/ietf.txt
index 0736f71ec..609f5e75a 100644
--- a/src/crypto/crypto_ops_builder/ietf.txt
+++ b/src/crypto/crypto_ops_builder/ietf.txt
@@ -1,1402 +1,4 @@
-                                                                        
+https://tools.ietf.org/id/draft-josefsson-eddsa-ed25519-02.txt
 
-[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]               
-                                                                        
-Versions: 00 01 02                                                      
-                                                                        
-Network Working Group                                       S. Josefsson
-Internet-Draft                                                    SJD AB
-Intended status: Informational                                N. Moeller
-Expires: August 26, 2015
-                                                       February 22, 2015
-
-
-                           EdDSA and Ed25519
-
-                    draft-josefsson-eddsa-ed25519-02
-
-
-Abstract
-
-   The elliptic curve signature scheme EdDSA and one instance of it
-   called Ed25519 is described.  An example implementation and test
-   vectors are provided.
-
-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 http://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 August 26, 2015.
-
-Copyright Notice
-
-   Copyright (c) 2015 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
-   (http://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.
-
-
-
-
-Josefsson & Moeller      Expires August 26, 2015                [Page 1]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-Table of Contents
-
-   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
-   2.  Notation  . . . . . . . . . . . . . . . . . . . . . . . . . .   3
-   3.  Background  . . . . . . . . . . . . . . . . . . . . . . . . .   3
-   4.  EdDSA . . . . . . . . . . . . . . . . . . . . . . . . . . . .   4
-     4.1.  Encoding  . . . . . . . . . . . . . . . . . . . . . . . .   4
-     4.2.  Keys  . . . . . . . . . . . . . . . . . . . . . . . . . .   5
-     4.3.  Sign  . . . . . . . . . . . . . . . . . . . . . . . . . .   5
-     4.4.  Verify  . . . . . . . . . . . . . . . . . . . . . . . . .   5
-   5.  Ed25519 . . . . . . . . . . . . . . . . . . . . . . . . . . .   5
-     5.1.  Modular arithmetic  . . . . . . . . . . . . . . . . . . .   6
-     5.2.  Encoding  . . . . . . . . . . . . . . . . . . . . . . . .   6
-     5.3.  Decoding  . . . . . . . . . . . . . . . . . . . . . . . .   6
-     5.4.  Point addition  . . . . . . . . . . . . . . . . . . . . .   7
-     5.5.  Key Generation  . . . . . . . . . . . . . . . . . . . . .   8
-     5.6.  Sign  . . . . . . . . . . . . . . . . . . . . . . . . . .   8
-     5.7.  Verify  . . . . . . . . . . . . . . . . . . . . . . . . .   9
-     5.8.  Python illustration . . . . . . . . . . . . . . . . . . .   9
-   6.  Test Vectors for Ed25519  . . . . . . . . . . . . . . . . . .  14
-   7.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .  17
-   8.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  18
-   9.  Security Considerations . . . . . . . . . . . . . . . . . . .  18
-     9.1.  Side-channel leaks  . . . . . . . . . . . . . . . . . . .  18
-   10. References  . . . . . . . . . . . . . . . . . . . . . . . . .  18
-     10.1.  Normative References . . . . . . . . . . . . . . . . . .  18
-     10.2.  Informative References . . . . . . . . . . . . . . . . .  18
-   Appendix A.  Ed25519 Python Library . . . . . . . . . . . . . . .  19
-   Appendix B.  Library driver . . . . . . . . . . . . . . . . . . .  23
-   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  24
-
-1.  Introduction
-
-
-   The Edwards-curve Digital Signature Algorithm (EdDSA) is a variant of
-   Schnorr's signature system with Twisted Edwards curves.  EdDSA needs
-   to be instantiated with certain parameters and this document describe
-   Ed25519 - an instantiation of EdDSA in a curve over GF(2^255-19).  To
-   facilitate adoption in the Internet community of Ed25519, this
-   document describe the signature scheme in an implementation-oriented
-   way, and we provide sample code and test vectors.
-
-   The advantages with EdDSA and Ed25519 include:
-
-   1.  High-performance on a variety of platforms.
-
-   2.  Does not require the use of a unique random number for each
-       signature.
-
-
-
-
-Josefsson & Moeller      Expires August 26, 2015                [Page 2]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-   3.  More resilient to side-channel attacks.
-
-   4.  Small public keys (32 bytes) and signatures (64 bytes).
-
-   5.  The formulas are "strongly unified", i.e., they are valid for all
-       points on the curve, with no exceptions.  This obviates the need
-       for EdDSA to perform expensive point validation on untrusted
-       public values.
-
-   6.  Collision resilience, meaning that hash-function collisions do
-       not break this system.
-
-   For further background, see the original EdDSA paper [EDDSA].
-
-2.  Notation
-
-
-   The following notation is used throughout the document:
-
-   GF(p) finite field with p elements
-
-   x^y x multiplied by itself y times
-
-   B generator of the group or subgroup of interest
-
-   n B B added to itself n times.
-
-   h_i the i'th bit of h
-
-   a || b (bit-)string a concatenated with (bit-)string b
-
-3.  Background
-
-
-   EdDSA is defined using an elliptic curve over GF(p) of the form
-
-   -x^2 + y^2 = 1 + d x^2 y^2
-
-   In general, p could be a prime power, but it is usually chosen as a
-   prime number.  It is required that p = 1 modulo 4 (which implies that
-   -1 is a square modulo p) and that d is a non-square modulo p.  For
-   Ed25519, the curve used is equivalent to Curve25519 [CURVE25519],
-   under a change of coordinates, which means that the difficulty of the
-   discrete logarithm problem is the same as for Curve25519.
-
-   Points on this curve form a group under addition, (x3, y3) = (x1, y1)
-   + (x2, y2), with the formulas
-
-
-
-
-
-
-Josefsson & Moeller      Expires August 26, 2015                [Page 3]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-           x1 y2 + x2 y1              y1 y2 + x1 x2
-   x3 = -------------------,  y3 = -------------------
-         1 + d x1 x2 y1 y2          1 - d x1 x2 y1 y2
-
-   The neutral element in the group is (0, 1).
-
-   Unlike manyy other curves used for cryptographic applications, these
-   formulas are "strongly unified": they are valid for all points on the
-   curve, with no exceptions.  In particular, the denominators are non-
-   zero for all input points.
-
-   There are more efficient formulas, which are still strongly unified,
-   which use homogeneous coordinates to avoid the expensive modulo p
-   inversions.  See [Faster-ECC] and [Edwards-revisited].
-
-4.  EdDSA
-
-
-   EdDSA is a digital signature system with several parameters.  The
-   generic EdDSA digital signature system is normally not implemented
-   directly, but instead a particular instance of EdDSA (like Ed25519)
-   is implemented.  A precise explanation of the generic EdDSA is thus
-   not particulary useful for implementers, but for background and
-   completeness, a succint description of the generic EdDSA algorithm is
-   given here.
-
-   EdDSA has seven parameters:
-
-   1.  an integer b >= 10.
-
-   2.  a cryptographic hash function H producing 2b-bit outputs.
-
-   3.  a prime power p congruent to 1 modulo 4.
-
-   4.  a (b-1)-bit encoding of elements of the finite field GF(p).
-
-   5.  a non-square element d of GF(p)
-
-   6.  an element B != (0,1) of the set E = { (x,y) is a member of GF(p)
-       x GF(p) such that -x^2 + y^2 = 1 + dx^2y^2 }.
-
-   7.  a prime q, of size b-3 bits, such that qB = (0, 1), i.e., q is
-       the order of B or a multiple thereof.
-
-4.1.  Encoding
-
-
-   An element (x,y) of E is encoded as a b-bit string called ENC(x,y)
-   which is the (b-1)-bit encoding of y concatenated with one bit that
-   is 1 if x is negative and 0 if x is not negative.  Negative elements
-
-
-
-Josefsson & Moeller      Expires August 26, 2015                [Page 4]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-   of GF(q) are those x which the (b-1)-bit encoding of x is
-   lexicographically larger than the (b-1)-bit encoding of -x.
-
-4.2.  Keys
-
-
-   An EdDSA secret key is a b-bit string k.  Let the hash H(k) = (h_0,
-   h_1, ..., h_(2b-1)) determine an integer a which is 2^(b-2) plus the
-   sum of m = 2^i * h_i for all i equal or larger than 3 and equal to or
-   less than b-3 such that m is a member of the set { 2^(b-2), 2^(b-2) +
-   8, ..., 2^(b-1) - 8 }.  The EdDSA public key is ENC(A) = ENC(aB).
-   The bits h_b, ..., h_(2b-1) is used below during signing.
-
-4.3.  Sign
-
-
-   The signature of a message M under a secret key k is the 2b-bit
-   string ENC(R) || ENC'(S), where ENC'(S) is defined as the b-bit
-   little-endian encoding of S.  R and S are derived as follows.  First
-   define r = H(h_b, ... h_(2b-1)), M) interpreting 2b-bit strings in
-   little-endian form as integers in {0, 1, ..., 2^(2b)-1}.  Let R=rB
-   and S=(r+H(ENC(R) || ENC(A) || M)a) mod l.
-
-4.4.  Verify
-
-
-   To verify a signature ENC(R) || ENC'(S) on a message M under a public
-   key ENC(A), proceed as follows.  Parse the inputs so that A and R is
-   an element of E, and S is a member of the set {0, 1, ..., l-1 }.
-   Compute H' = H(ENC(R) || ENC(A) || M) and check the group equation
-   8SB = 8R + 8H'A in E.  Verification is rejected if parsing fails or
-   the group equation does not hold.
-
-5.  Ed25519
-
-
-   Theoretically, Ed25519 is EdDSA instantiated with b=256, H being
-   SHA-512 [RFC4634], p is the prime 2^255-19, the 255-bit encoding of
-   GF(2^255-19) being the little-endian encoding of {0, 1, ...,
-   2^255-20}, q is the prime 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed,
-   d = -121665/121666 which is a member of GF(p), and B is the unique
-   point (x, 4/5) in E for which x is "positive", which with the
-   encoding used simply means that the least significant bit of x is 0.
-   The curve p, prime q, d and B follows from [I-D.irtf-cfrg-curves].
-
-   Written out explicitly, B is the point (15112221349535400772501151409
-   588531511454012693041857206046113283949847762202, 4631683569492647816
-   9428394003475163141307993866256225615783033603165251855960).
-
-
-
-
-
-
-
-Josefsson & Moeller      Expires August 26, 2015                [Page 5]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-5.1.  Modular arithmetic
-
-
-   For advise on how to implement arithmetic modulo p = 2^255 - 1
-   efficiently and securely, see Curve25519 [CURVE25519].  For inversion
-   modulo p, it is recommended to use the identity x^-1 = x^(p-2) (mod
-   p).
-
-   For point decoding or "decompression", square roots modulo p are
-   needed.  They can be computed using the Tonelli-Shanks algorithm, or
-   the special case for p = 5 (mod 8).  To find a square root of a,
-   first compute the candidate root x = a^((p+3)/8) (mod p).  Then there
-   are three cases:
-
-      x^2 = a (mod p).  Then x is a square root.
-
-      x^2 = -a (mod p).  Then 2^((p-1)/4) x is a square root.
-
-      a is not a square modulo p.
-
-5.2.  Encoding
-
-
-   All values are coded as octet strings, and integers are coded using
-   little endian convention.  I.e., a 32-octet string h h[0],...h[31]
-   represents the integer h[0] + 2^8 h[1] + ... + 2^248 h[31].
-
-   A curve point (x,y), with coordiantes in the range 0 <= x,y < p, is
-   coded as follows.  First encode the y-coordinate as a little-endian
-   string of 32 octets.  The most significant bit of the final octet is
-   always zero.  To form the encoding of the point, copy the least
-   significant bit of the x-coordinate to the most significant bit of
-   the final octet.
-
-5.3.  Decoding
-
-
-   Decoding a point, given as a 32-octet string, is a little more
-   complicated.
-
-   1.  First interpret the string as an integer in little-endian
-       representation.  Bit 255 of this number is the least significant
-       bit of the x-coordinate, and denote this value x_0.  The
-       y-coordinate is recovered simply by clearing this bit.  If the
-       resulting value is >= p, decoding fails.
-
-   2.  To recover the x coordinate, the curve equation implies x^2 =
-       (y^2 - 1) / (d y^2 + 1) (mod p).  Since d is a non-square and -1
-       is a square, the numerator, (d y^2 + 1), is always invertible
-       modulo p.  Let u = y^2 - 1 and v = d y^2 + 1.  To compute the
-       square root of (u/v), the first step is to compute the candidate
-
-
-
-Josefsson & Moeller      Expires August 26, 2015                [Page 6]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-       root x = (u/v)^((p+3)/8).  This can be done using the following
-       trick, to use a single modular powering for both the inversion of
-       v and the square root:
-
-                      (p+3)/8      3        (p-5)/8
-             x = (u/v)        = u v  (u v^7)         (mod p)
-
-   3.  Again, there are three cases:
-
-       1.  If v x^2 = u (mod p), x is a square root.
-
-       2.  If v x^2 = -u (mod p), set x <-- x 2^((p-1)/4), which is a
-           square root.
-
-       3.  Otherwise, no square root exists modulo p, and decoding
-           fails.
-
-   4.  Finally, use the x_0 bit to select the right square root.  If x =
-       0, and x_0 = 1, decoding fails.  Otherwise, if x_0 != x mod 2,
-       set x <-- p - x.  Return the decoded point (x,y).
-
-5.4.  Point addition
-
-
-   For point addition, the following method is recommended.  A point
-   (x,y) is represented in extended homogeneous coordinates (X, Y, Z,
-   T), with x = X/Z, y = Y/Z, x y = T/Z.
-
-   The following formulas for adding two points, (x3,y3) =
-   (x1,y1)+(x2,y2) are described in [Edwards-revisited], section 3.1.
-   They are strongly unified, i.e., they work for any pair of valid
-   input points.
-
-           A = (Y1-X1)*(Y2-X2)
-           B = (Y1+X1)*(Y2+X2)
-           C = T1*2*d*T2
-           D = Z1*2*Z2
-           E = B-A
-           F = D-C
-           G = D+C
-           H = B+A
-           X3 = E*F
-           Y3 = G*H
-           T3 = E*H
-           Z3 = F*G
-
-
-
-
-
-
-
-Josefsson & Moeller      Expires August 26, 2015                [Page 7]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-5.5.  Key Generation
-
-
-   The secret is 32 octets (256 bits, corresponding to b) of
-   cryptographically-secure random data.  See [RFC4086] for a discussion
-   about randomness.
-
-   The 32-byte public key is generated by the following steps.
-
-   1.  Hash the 32-byte secret using SHA-512, storing the digest in a
-       64-octet large buffer, denoted h.  Only the lower 32 bytes are
-       used for generating the public key.
-
-   2.  Prune the buffer.  In C terminology:
-
-             h[0] &= ~0x07;
-             h[31] &= 0x7F;
-             h[31] |= 0x40;
-
-   3.  Interpret the buffer as the little-endian integer, forming a
-       secret scalar a.  Perform a known-base-point scalar
-       multiplication a B.
-
-   4.  The public key A is the encoding of the point aB.  First encode
-       the y coordinate (in the range 0 <= y < p) as a little-endian
-       string of 32 octets.  The most significant bit of the final octet
-       is always zero.  To form the encoding of the point aB, copy the
-       least significant bit of the x coordinate to the most significant
-       bit of the final octet.  The result is the public key.
-
-5.6.  Sign
-
-
-   The imputs to the signing procedure is the secret key, a 32-octet
-   string, and a message M of arbitrary size.
-
-   1.  Hash the secret key, 32-octets, using SHA-512.  Let h denote the
-       resulting digest.  Construct the secret scalar a from the first
-       half of the digest, and the corresponding public key A, as
-       described in the previous section.  Let prefix denote the second
-       half of the hash digest, h[32],...,h[63].
-
-   2.  Compute SHA-512(prefix || M), where M is the message to be
-       signed.  Interpret the 64-octet digest as a little-endian integer
-       r.
-
-   3.  Compute the point rB.  For efficiency, do this by first reducing
-       r modulo q, the group order of B.  Let the string R be the
-       encoding of this point.
-
-
-
-
-Josefsson & Moeller      Expires August 26, 2015                [Page 8]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-   4.  Compute SHA512(R || A || M), and interpret the 64-octet digest as
-       a little-endian integer k.
-
-   5.  Compute s = (r + k a) mod q.  For efficiency, again reduce k
-       modulo q first.
-
-   6.  Form the signature of the concatenation of R (32 octets) and the
-       little-endian encoding of s (32 octets, three most significant
-       bits of the final octets always zero).
-
-5.7.  Verify
-
-
-   1.  To verify a signature on a message M, first split the signature
-       into two 32-octet halves.  Decode the first half as a point R,
-       and the second half as an integer s, in the range 0 <= s < q.  If
-       the decoding fails, the signature is invalid.
-
-   2.  Compute SHA512(R || A || M), and interpret the 64-octet digest as
-       a little-endian integer k.
-
-   3.  Check the group equation 8s B = 8 R + 8k A.  It's sufficient, but
-       not required, to instead check s B = R + k A.
-
-5.8.  Python illustration
-
-
-   The rest of this section describes how Ed25519 can be implemented in
-   Python (version 3.2 or later) for illustration.  See appendix A for
-   the complete implementation and appendix B for a test-driver to run
-   it through some test vectors.
-
-   First some preliminaries that will be needed.
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Josefsson & Moeller      Expires August 26, 2015                [Page 9]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-   import hashlib
-
-   def sha512(s):
-       return hashlib.sha512(s).digest()
-
-   # Base field Z_p
-   p = 2**255 - 19
-
-   def modp_inv(x):
-       return pow(x, p-2, p)
-
-   # Curve constant
-   d = -121665 * modp_inv(121666) % p
-
-   # Group order
-   q = 2**252 + 27742317777372353535851937790883648493
-
-   def sha512_modq(s):
-       return int.from_bytes(sha512(s), "little") % q
-
-   Then follows functions to perform point operations.
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Josefsson & Moeller      Expires August 26, 2015               [Page 10]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-# Points are represented as tuples (X, Y, Z, T) of extended coordinates,
-# with x = X/Z, y = Y/Z, x*y = T/Z
-
-def point_add(P, Q):
-    A = (P[1]-P[0])*(Q[1]-Q[0]) % p
-    B = (P[1]+P[0])*(Q[1]+Q[0]) % p
-    C = 2 * P[3] * Q[3] * d % p
-    D = 2 * P[2] * Q[2] % p
-    E = B-A
-    F = D-C
-    G = D+C
-    H = B+A
-    return (E*F, G*H, F*G, E*H)
-
-# Computes Q = s * Q
-def point_mul(s, P):
-    Q = (0, 1, 1, 0)  # Neutral element
-    while s > 0:
-        # Is there any bit-set predicate?
-        if s & 1:
-            Q = point_add(Q, P)
-        P = point_add(P, P)
-        s >>= 1
-    return Q
-
-def point_equal(P, Q):
-    # x1 / z1 == x2 / z2  <==>  x1 * z2 == x2 * z1
-    if (P[0] * Q[2] - Q[0] * P[2]) % p != 0:
-        return False
-    if (P[1] * Q[2] - Q[1] * P[2]) % p != 0:
-        return False
-    return True
-
-   Now follows functions for point compression.
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Josefsson & Moeller      Expires August 26, 2015               [Page 11]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-# Square root of -1
-modp_sqrt_m1 = pow(2, (p-1) // 4, p)
-
-# Compute corresponding x coordinate, with low bit corresponding to sign,
-# or return None on failure
-def recover_x(y, sign):
-    x2 = (y*y-1) * modp_inv(d*y*y+1)
-    if x2 == 0:
-        if sign:
-            return None
-        else:
-            return 0
-
-    # Compute square root of x2
-    x = pow(x2, (p+3) // 8, p)
-    if (x*x - x2) % p != 0:
-        x = x * modp_sqrt_m1 % p
-    if (x*x - x2) % p != 0:
-        return None
-
-    if (x & 1) != sign:
-        x = p - x
-    return x
-
-# Base point
-g_y = 4 * modp_inv(5) % p
-g_x = recover_x(g_y, 0)
-G = (g_x, g_y, 1, g_x * g_y % p)
-
-def point_compress(P):
-    zinv = modp_inv(P[2])
-    x = P[0] * zinv % p
-    y = P[1] * zinv % p
-    return int.to_bytes(y | ((x & 1) << 255), 32, "little")
-
-def point_decompress(s):
-    if len(s) != 32:
-        raise Exception("Invalid input length for decompression")
-    y = int.from_bytes(s, "little")
-    sign = y >> 255
-    y &= (1 << 255) - 1
-
-    x = recover_x(y, sign)
-    if x is None:
-        return None
-    else:
-        return (x, y, 1, x*y % p)
-
-
-
-
-Josefsson & Moeller      Expires August 26, 2015               [Page 12]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-   These are functions for manipulating the secret.
-
-   def secret_expand(secret):
-       if len(secret) != 32:
-           raise Exception("Bad size of private key")
-       h = sha512(secret)
-       a = int.from_bytes(h[:32], "little")
-       a &= (1 << 254) - 8
-       a |= (1 << 254)
-       return (a, h[32:])
-
-   def secret_to_public(secret):
-       (a, dummy) = secret_expand(secret)
-       return point_compress(point_mul(a, G))
-
-   The signature function works as below.
-
-   def sign(secret, msg):
-       a, prefix = secret_expand(secret)
-       A = point_compress(point_mul(a, G))
-       r = sha512_modq(prefix + msg)
-       R = point_mul(r, G)
-       Rs = point_compress(R)
-       h = sha512_modq(Rs + A + msg)
-       s = (r + h * a) % q
-       return Rs + int.to_bytes(s, 32, "little")
-
-   And finally the verification function.
-
-   def verify(public, msg, signature):
-       if len(public) != 32:
-           raise Exception("Bad public-key length")
-       if len(signature) != 64:
-           Exception("Bad signature length")
-       A = point_decompress(public)
-       if not A:
-           return False
-       Rs = signature[:32]
-       R = point_decompress(Rs)
-       if not R:
-           return False
-       s = int.from_bytes(signature[32:], "little")
-       h = sha512_modq(Rs + public + msg)
-       sB = point_mul(s, G)
-       hA = point_mul(h, A)
-       return point_equal(sB, point_add(R, hA))
-
-
-
-
-
-Josefsson & Moeller      Expires August 26, 2015               [Page 13]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-6.  Test Vectors for Ed25519
-
-
-   Below is a sequence of octets with test vectors for the the Ed25519
-   signature algorithm.  The octets are hex encoded and whitespace is
-   inserted for readability.  Private keys are 64 bytes, public keys 32
-   bytes, message of arbitrary length, and signatures are 64 bytes.  The
-   test vectors are taken from [ED25519-TEST-VECTORS] (but we removed
-   the public key as a suffix of the secret key, and removed the message
-   from the signature) and [ED25519-LIBGCRYPT-TEST-VECTORS].
-
-   -----TEST 1
-   SECRET KEY:
-   9d61b19deffd5a60ba844af492ec2cc4
-   4449c5697b326919703bac031cae7f60
-
-   PUBLIC KEY:
-   d75a980182b10ab7d54bfed3c964073a
-   0ee172f3daa62325af021a68f707511a
-
-   MESSAGE (length 0 bytes):
-
-   SIGNATURE:
-   e5564300c360ac729086e2cc806e828a
-   84877f1eb8e5d974d873e06522490155
-   5fb8821590a33bacc61e39701cf9b46b
-   d25bf5f0595bbe24655141438e7a100b
-
-   -----TEST 2
-   SECRET KEY:
-   4ccd089b28ff96da9db6c346ec114e0f
-   5b8a319f35aba624da8cf6ed4fb8a6fb
-
-   PUBLIC KEY:
-   3d4017c3e843895a92b70aa74d1b7ebc
-   9c982ccf2ec4968cc0cd55f12af4660c
-
-   MESSAGE (length 1 byte):
-   72
-
-   SIGNATURE:
-   92a009a9f0d4cab8720e820b5f642540
-   a2b27b5416503f8fb3762223ebdb69da
-   085ac1e43e15996e458f3613d0f11d8c
-   387b2eaeb4302aeeb00d291612bb0c00
-
-   -----TEST 3
-   SECRET KEY:
-   c5aa8df43f9f837bedb7442f31dcb7b1
-
-
-
-Josefsson & Moeller      Expires August 26, 2015               [Page 14]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-   66d38535076f094b85ce3a2e0b4458f7
-
-   PUBLIC KEY:
-   fc51cd8e6218a1a38da47ed00230f058
-   0816ed13ba3303ac5deb911548908025
-
-   MESSAGE (length 2 bytes):
-   af82
-
-   SIGNATURE:
-   6291d657deec24024827e69c3abe01a3
-   0ce548a284743a445e3680d7db5ac3ac
-   18ff9b538d16f290ae67f760984dc659
-   4a7c15e9716ed28dc027beceea1ec40a
-
-   -----TEST 1024
-   SECRET KEY:
-   f5e5767cf153319517630f226876b86c
-   8160cc583bc013744c6bf255f5cc0ee5
-
-   PUBLIC KEY:
-   278117fc144c72340f67d0f2316e8386
-   ceffbf2b2428c9c51fef7c597f1d426e
-
-   MESSAGE:
-   08b8b2b733424243760fe426a4b54908
-   632110a66c2f6591eabd3345e3e4eb98
-   fa6e264bf09efe12ee50f8f54e9f77b1
-   e355f6c50544e23fb1433ddf73be84d8
-   79de7c0046dc4996d9e773f4bc9efe57
-   38829adb26c81b37c93a1b270b20329d
-   658675fc6ea534e0810a4432826bf58c
-   941efb65d57a338bbd2e26640f89ffbc
-   1a858efcb8550ee3a5e1998bd177e93a
-   7363c344fe6b199ee5d02e82d522c4fe
-   ba15452f80288a821a579116ec6dad2b
-   3b310da903401aa62100ab5d1a36553e
-   06203b33890cc9b832f79ef80560ccb9
-   a39ce767967ed628c6ad573cb116dbef
-   efd75499da96bd68a8a97b928a8bbc10
-   3b6621fcde2beca1231d206be6cd9ec7
-   aff6f6c94fcd7204ed3455c68c83f4a4
-   1da4af2b74ef5c53f1d8ac70bdcb7ed1
-   85ce81bd84359d44254d95629e9855a9
-   4a7c1958d1f8ada5d0532ed8a5aa3fb2
-   d17ba70eb6248e594e1a2297acbbb39d
-   502f1a8c6eb6f1ce22b3de1a1f40cc24
-   554119a831a9aad6079cad88425de6bd
-
-
-
-Josefsson & Moeller      Expires August 26, 2015               [Page 15]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-   e1a9187ebb6092cf67bf2b13fd65f270
-   88d78b7e883c8759d2c4f5c65adb7553
-   878ad575f9fad878e80a0c9ba63bcbcc
-   2732e69485bbc9c90bfbd62481d9089b
-   eccf80cfe2df16a2cf65bd92dd597b07
-   07e0917af48bbb75fed413d238f5555a
-   7a569d80c3414a8d0859dc65a46128ba
-   b27af87a71314f318c782b23ebfe808b
-   82b0ce26401d2e22f04d83d1255dc51a
-   ddd3b75a2b1ae0784504df543af8969b
-   e3ea7082ff7fc9888c144da2af58429e
-   c96031dbcad3dad9af0dcbaaaf268cb8
-   fcffead94f3c7ca495e056a9b47acdb7
-   51fb73e666c6c655ade8297297d07ad1
-   ba5e43f1bca32301651339e22904cc8c
-   42f58c30c04aafdb038dda0847dd988d
-   cda6f3bfd15c4b4c4525004aa06eeff8
-   ca61783aacec57fb3d1f92b0fe2fd1a8
-   5f6724517b65e614ad6808d6f6ee34df
-   f7310fdc82aebfd904b01e1dc54b2927
-   094b2db68d6f903b68401adebf5a7e08
-   d78ff4ef5d63653a65040cf9bfd4aca7
-   984a74d37145986780fc0b16ac451649
-   de6188a7dbdf191f64b5fc5e2ab47b57
-   f7f7276cd419c17a3ca8e1b939ae49e4
-   88acba6b965610b5480109c8b17b80e1
-   b7b750dfc7598d5d5011fd2dcc5600a3
-   2ef5b52a1ecc820e308aa342721aac09
-   43bf6686b64b2579376504ccc493d97e
-   6aed3fb0f9cd71a43dd497f01f17c0e2
-   cb3797aa2a2f256656168e6c496afc5f
-   b93246f6b1116398a346f1a641f3b041
-   e989f7914f90cc2c7fff357876e506b5
-   0d334ba77c225bc307ba537152f3f161
-   0e4eafe595f6d9d90d11faa933a15ef1
-   369546868a7f3a45a96768d40fd9d034
-   12c091c6315cf4fde7cb68606937380d
-   b2eaaa707b4c4185c32eddcdd306705e
-   4dc1ffc872eeee475a64dfac86aba41c
-   0618983f8741c5ef68d3a101e8a3b8ca
-   c60c905c15fc910840b94c00a0b9d0
-
-   SIGNATURE:
-   0aab4c900501b3e24d7cdf4663326a3a
-   87df5e4843b2cbdb67cbf6e460fec350
-   aa5371b1508f9f4528ecea23c436d94b
-   5e8fcd4f681e30a6ac00a9704a188a03
-
-
-
-
-Josefsson & Moeller      Expires August 26, 2015               [Page 16]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-   -----TEST 1A
-   -----An additional test with the data from test 1 but using an
-   -----uncompressed public key.
-   SECRET KEY:
-   9d61b19deffd5a60ba844af492ec2cc4
-   4449c5697b326919703bac031cae7f60
-
-   PUBLIC KEY:
-   0455d0e09a2b9d34292297e08d60d0f6
-   20c513d47253187c24b12786bd777645
-   ce1a5107f7681a02af2523a6daf372e1
-   0e3a0764c9d3fe4bd5b70ab18201985a
-   d7
-
-   MSG (length 0 bytes):
-
-   SIGNATURE:
-   e5564300c360ac729086e2cc806e828a
-   84877f1eb8e5d974d873e06522490155
-   5fb8821590a33bacc61e39701cf9b46b
-   d25bf5f0595bbe24655141438e7a100b
-
-   -----TEST 1B
-   -----An additional test with the data from test 1 but using an
-   -----compressed prefix.
-   SECRET KEY:
-   9d61b19deffd5a60ba844af492ec2cc4
-   4449c5697b326919703bac031cae7f60
-
-   PUBLIC KEY:
-   40d75a980182b10ab7d54bfed3c96407
-   3a0ee172f3daa62325af021a68f70751
-   1a
-
-   MESSAGE (length 0 bytes):
-
-   SIGNATURE:
-   e5564300c360ac729086e2cc806e828a
-   84877f1eb8e5d974d873e06522490155
-   5fb8821590a33bacc61e39701cf9b46b
-   d25bf5f0595bbe24655141438e7a100b
-   -----
-
-7.  Acknowledgements
-
-
-   Feedback on this document was received from Werner Koch and Damien
-   Miller.
-
-
-
-
-Josefsson & Moeller      Expires August 26, 2015               [Page 17]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-8.  IANA Considerations
-
-
-   None.
-
-9.  Security Considerations
-
-
-9.1.  Side-channel leaks
-
-
-   For implementations performing signatures, secrecy of the key is
-   fundamental.  It is possible to protect against some side-channel
-   attacks by ensuring that the implementation executes exactly the same
-   sequence of instructions and performs exactly the same memory
-   accesses, for any value of the secret key.
-
-   To make an implementation side-channel silent in this way, the modulo
-   p arithmetic must not use any data-dependent branches, e.g., related
-   to carry propagation.  Side channel-silent point addition is
-   straight-forward, thanks to the unified formulas.
-
-   Scalar multiplication, multiplying a point by an integer, needs some
-   additional effort to implement in a side-channel silent manner.  One
-   simple approach is to implement a side-channel silent conditional
-   assignment, and use together with the binary algorithm to examine one
-   bit of the integer at a time.
-
-   Note that the example implementation in this document does not
-   attempt to be side-channel silent.
-
-10.  References
-
-
-10.1.  Normative References
-
-
-   [RFC4634]  Eastlake, D. and T. Hansen, "US Secure Hash Algorithms
-              (SHA and HMAC-SHA)", RFC 4634, July 2006.
-
-   [I-D.irtf-cfrg-curves]
-              Langley, A., Salz, R., and S. Turner, "Elliptic Curves for
-              Security", draft-irtf-cfrg-curves-01 (work in progress),
-              January 2015.
-
-10.2.  Informative References
-
-
-   [RFC4086]  Eastlake, D., Schiller, J., and S. Crocker, "Randomness
-              Requirements for Security", BCP 106, RFC 4086, June 2005.
-
-
-
-
-
-
-
-Josefsson & Moeller      Expires August 26, 2015               [Page 18]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-   [EDDSA]    Bernstein, D., Duif, N., Lange, T., Schwabe, P., and B.
-              Yang, "High-speed high-security signatures", WWW
-              http://ed25519.cr.yp.to/ed25519-20110926.pdf, September
-              2011.
-
-   [Faster-ECC]
-              Bernstein, D. and T. Lange, "Faster addition and doubling
-              on elliptic curves", WWW http://eprint.iacr.org/2007/286,
-              July 2007.
-
-   [Edwards-revisited]
-              Hisil, H., Wong, K., Carter, G., and E. Dawson, "Twisted
-              Edwards Curves Revisited", WWW
-              http://eprint.iacr.org/2008/522, December 2008.
-
-   [CURVE25519]
-              Bernstein, D., "Curve25519: new Diffie-Hellman speed
-              records", WWW http://cr.yp.to/ecdh.html, February 2006.
-
-   [ED25519-TEST-VECTORS]
-              Bernstein, D., Duif, N., Lange, T., Schwabe, P., and B.
-              Yang, "Ed25519 test vectors", WWW
-              http://ed25519.cr.yp.to/python/sign.input, July 2011.
-
-   [ED25519-LIBGCRYPT-TEST-VECTORS]
-              Koch, W., "Ed25519 Libgcrypt test vectors", WWW
-              http://git.gnupg.org/cgi-
-              bin/gitweb.cgi?p=libgcrypt.git;a=blob;f=tests/t-ed25519.in
-              p;h=e13566f826321eece65e02c593bc7d885b3dbe23;hb=refs/
-              heads/master, July 2014.
-
-Appendix A.  Ed25519 Python Library
-
-
-   Below is an example implementation of Ed25519 written in Python,
-   version 3.2 or higher is required.
-
-# Loosely based on the public domain code at
-# http://ed25519.cr.yp.to/software.html
-#
-# Needs python-3.2
-
-import hashlib
-
-
-def sha512(s):
-    return hashlib.sha512(s).digest()
-
-# Base field Z_p
-
-
-
-Josefsson & Moeller      Expires August 26, 2015               [Page 19]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-p = 2**255 - 19
-
-
-def modp_inv(x):
-    return pow(x, p-2, p)
-
-# Curve constant
-d = -121665 * modp_inv(121666) % p
-
-# Group order
-q = 2**252 + 27742317777372353535851937790883648493
-
-
-def sha512_modq(s):
-    return int.from_bytes(sha512(s), "little") % q
-
-# Points are represented as tuples (X, Y, Z, T) of extended coordinates,
-# with x = X/Z, y = Y/Z, x*y = T/Z
-
-
-def point_add(P, Q):
-    A = (P[1]-P[0])*(Q[1]-Q[0]) % p
-    B = (P[1]+P[0])*(Q[1]+Q[0]) % p
-    C = 2 * P[3] * Q[3] * d % p
-    D = 2 * P[2] * Q[2] % p
-    E = B-A
-    F = D-C
-    G = D+C
-    H = B+A
-    return (E*F, G*H, F*G, E*H)
-
-
-# Computes Q = s * Q
-def point_mul(s, P):
-    Q = (0, 1, 1, 0)  # Neutral element
-    while s > 0:
-        # Is there any bit-set predicate?
-        if s & 1:
-            Q = point_add(Q, P)
-        P = point_add(P, P)
-        s >>= 1
-    return Q
-
-
-def point_equal(P, Q):
-    # x1 / z1 == x2 / z2  <==>  x1 * z2 == x2 * z1
-    if (P[0] * Q[2] - Q[0] * P[2]) % p != 0:
-        return False
-
-
-
-Josefsson & Moeller      Expires August 26, 2015               [Page 20]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-    if (P[1] * Q[2] - Q[1] * P[2]) % p != 0:
-        return False
-    return True
-
-# Square root of -1
-modp_sqrt_m1 = pow(2, (p-1) // 4, p)
-
-
-# Compute corresponding x coordinate, with low bit corresponding to sign,
-# or return None on failure
-def recover_x(y, sign):
-    x2 = (y*y-1) * modp_inv(d*y*y+1)
-    if x2 == 0:
-        if sign:
-            return None
-        else:
-            return 0
-
-    # Compute square root of x2
-    x = pow(x2, (p+3) // 8, p)
-    if (x*x - x2) % p != 0:
-        x = x * modp_sqrt_m1 % p
-    if (x*x - x2) % p != 0:
-        return None
-
-    if (x & 1) != sign:
-        x = p - x
-    return x
-
-# Base point
-g_y = 4 * modp_inv(5) % p
-g_x = recover_x(g_y, 0)
-G = (g_x, g_y, 1, g_x * g_y % p)
-
-
-def point_compress(P):
-    zinv = modp_inv(P[2])
-    x = P[0] * zinv % p
-    y = P[1] * zinv % p
-    return int.to_bytes(y | ((x & 1) << 255), 32, "little")
-
-
-def point_decompress(s):
-    if len(s) != 32:
-        raise Exception("Invalid input length for decompression")
-    y = int.from_bytes(s, "little")
-    sign = y >> 255
-    y &= (1 << 255) - 1
-
-
-
-Josefsson & Moeller      Expires August 26, 2015               [Page 21]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-    x = recover_x(y, sign)
-    if x is None:
-        return None
-    else:
-        return (x, y, 1, x*y % p)
-
-
-def secret_expand(secret):
-    if len(secret) != 32:
-        raise Exception("Bad size of private key")
-    h = sha512(secret)
-    a = int.from_bytes(h[:32], "little")
-    a &= (1 << 254) - 8
-    a |= (1 << 254)
-    return (a, h[32:])
-
-
-def secret_to_public(secret):
-    (a, dummy) = secret_expand(secret)
-    return point_compress(point_mul(a, G))
-
-
-def sign(secret, msg):
-    a, prefix = secret_expand(secret)
-    A = point_compress(point_mul(a, G))
-    r = sha512_modq(prefix + msg)
-    R = point_mul(r, G)
-    Rs = point_compress(R)
-    h = sha512_modq(Rs + A + msg)
-    s = (r + h * a) % q
-    return Rs + int.to_bytes(s, 32, "little")
-
-
-def verify(public, msg, signature):
-    if len(public) != 32:
-        raise Exception("Bad public-key length")
-    if len(signature) != 64:
-        Exception("Bad signature length")
-    A = point_decompress(public)
-    if not A:
-        return False
-    Rs = signature[:32]
-    R = point_decompress(Rs)
-    if not R:
-        return False
-    s = int.from_bytes(signature[32:], "little")
-    h = sha512_modq(Rs + public + msg)
-    sB = point_mul(s, G)
-
-
-
-Josefsson & Moeller      Expires August 26, 2015               [Page 22]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-    hA = point_mul(h, A)
-    return point_equal(sB, point_add(R, hA))
-
-Appendix B.  Library driver
-
-
-   Below is a command-line tool that uses the library above to perform
-   computations, for interactive use or for self-checking.
-
-   import sys
-   import binascii
-
-   from ed25519 import *
-
-   def point_valid(P):
-       zinv = modp_inv(P[2])
-       x = P[0] * zinv % p
-       y = P[1] * zinv % p
-       assert (x*y - P[3]*zinv) % p == 0
-       return (-x*x + y*y - 1 - d*x*x*y*y) % p == 0
-
-   assert point_valid(G)
-   Z = (0, 1, 1, 0)
-   assert point_valid(Z)
-
-   assert point_equal(Z, point_add(Z, Z))
-   assert point_equal(G, point_add(Z, G))
-   assert point_equal(Z, point_mul(0, G))
-   assert point_equal(G, point_mul(1, G))
-   assert point_equal(point_add(G, G), point_mul(2, G))
-   for i in range(0, 100):
-       assert point_valid(point_mul(i, G))
-   assert point_equal(Z, point_mul(q, G))
-
-   def munge_string(s, pos, change):
-       return (s[:pos] +
-               int.to_bytes(s[pos] ^ change, 1, "little") +
-               s[pos+1:])
-
-   # Read a file in the format of
-   # http://ed25519.cr.yp.to/python/sign.input
-   lineno = 0
-   while True:
-       line = sys.stdin.readline()
-       if not line:
-           break
-       lineno = lineno + 1
-       print(lineno)
-       fields = line.split(":")
-
-
-
-Josefsson & Moeller      Expires August 26, 2015               [Page 23]
-
- 
-Internet-Draft               EdDSA & Ed25519               February 2015
-
-
-       secret = (binascii.unhexlify(fields[0]))[:32]
-       public = binascii.unhexlify(fields[1])
-       msg = binascii.unhexlify(fields[2])
-       signature = binascii.unhexlify(fields[3])[:64]
-
-       assert public == secret_to_public(secret)
-       assert signature == sign(secret, msg)
-       assert verify(public, msg, signature)
-       if len(msg) == 0:
-           bad_msg = b"x"
-       else:
-           bad_msg = munge_string(msg, len(msg) // 3, 4)
-       assert not verify(public, bad_msg, signature)
-       bad_signature = munge_string(signature, 20, 8)
-       assert not verify(public, msg, bad_signature)
-       bad_signature = munge_string(signature, 40, 16)
-       assert not verify(public, msg, bad_signature)
-
-Authors' Addresses
-
-   Simon Josefsson
-   SJD AB
-
-   Email: simon@josefsson.org
-   URI:   http://josefsson.org/
-
-
-   Niels Moeller
-
-   Email: nisse@lysator.liu.se
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Josefsson & Moeller      Expires August 26, 2015               [Page 24]
-
-
-
-Html markup produced by rfcmarkup 1.113, available from https://tools.ietf.org/tools/rfcmarkup/  
+Note: This draft is now superseded by https://datatracker.ietf.org/doc/rfc8032/
+(review of the differences is left as an exercise for the reader)