diff options
Diffstat (limited to 'src/crypto/crypto_ops_builder/ietf.txt')
| -rw-r--r-- | src/crypto/crypto_ops_builder/ietf.txt | 1402 |
1 files changed, 1402 insertions, 0 deletions
diff --git a/src/crypto/crypto_ops_builder/ietf.txt b/src/crypto/crypto_ops_builder/ietf.txt new file mode 100644 index 000000000..0736f71ec --- /dev/null +++ b/src/crypto/crypto_ops_builder/ietf.txt @@ -0,0 +1,1402 @@ + + +[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/ |