7Internet Research Task Force (IRTF) S. Josefsson
8Request for Comments: 8032 SJD AB
9Category: Informational I. Liusvaara
10ISSN: 2070-1721 Independent
14 Edwards-Curve Digital Signature Algorithm (EdDSA)
18 This document describes elliptic curve signature scheme Edwards-curve
19 Digital Signature Algorithm (EdDSA). The algorithm is instantiated
20 with recommended parameters for the edwards25519 and edwards448
21 curves. An example implementation and test vectors are provided.
25 This document is not an Internet Standards Track specification; it is
26 published for informational purposes.
28 This document is a product of the Internet Research Task Force
29 (IRTF). The IRTF publishes the results of Internet-related research
30 and development activities. These results might not be suitable for
31 deployment. This RFC represents the consensus of the Crypto Forum
32 Research Group of the Internet Research Task Force (IRTF). Documents
33 approved for publication by the IRSG are not a candidate for any
34 level of Internet Standard; see Section 2 of RFC 7841.
36 Information about the current status of this document, any errata,
37 and how to provide feedback on it may be obtained at
38 http://www.rfc-editor.org/info/rfc8032.
42 Copyright (c) 2017 IETF Trust and the persons identified as the
43 document authors. All rights reserved.
45 This document is subject to BCP 78 and the IETF Trust's Legal
46 Provisions Relating to IETF Documents
47 (http://trustee.ietf.org/license-info) in effect on the date of
48 publication of this document. Please review these documents
49 carefully, as they describe your rights and restrictions with respect
58Josefsson & Liusvaara Informational [Page 1]
60RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
65 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
66 2. Notation and Conventions . . . . . . . . . . . . . . . . . . 4
67 3. EdDSA Algorithm . . . . . . . . . . . . . . . . . . . . . . . 5
68 3.1. Encoding . . . . . . . . . . . . . . . . . . . . . . . . 7
69 3.2. Keys . . . . . . . . . . . . . . . . . . . . . . . . . . 7
70 3.3. Sign . . . . . . . . . . . . . . . . . . . . . . . . . . 8
71 3.4. Verify . . . . . . . . . . . . . . . . . . . . . . . . . 8
72 4. PureEdDSA, HashEdDSA, and Naming . . . . . . . . . . . . . . 8
73 5. EdDSA Instances . . . . . . . . . . . . . . . . . . . . . . . 9
74 5.1. Ed25519ph, Ed25519ctx, and Ed25519 . . . . . . . . . . . 9
75 5.1.1. Modular Arithmetic . . . . . . . . . . . . . . . . . 10
76 5.1.2. Encoding . . . . . . . . . . . . . . . . . . . . . . 10
77 5.1.3. Decoding . . . . . . . . . . . . . . . . . . . . . . 11
78 5.1.4. Point Addition . . . . . . . . . . . . . . . . . . . 11
79 5.1.5. Key Generation . . . . . . . . . . . . . . . . . . . 13
80 5.1.6. Sign . . . . . . . . . . . . . . . . . . . . . . . . 13
81 5.1.7. Verify . . . . . . . . . . . . . . . . . . . . . . . 14
82 5.2. Ed448ph and Ed448 . . . . . . . . . . . . . . . . . . . . 15
83 5.2.1. Modular Arithmetic . . . . . . . . . . . . . . . . . 16
84 5.2.2. Encoding . . . . . . . . . . . . . . . . . . . . . . 16
85 5.2.3. Decoding . . . . . . . . . . . . . . . . . . . . . . 16
86 5.2.4. Point Addition . . . . . . . . . . . . . . . . . . . 17
87 5.2.5. Key Generation . . . . . . . . . . . . . . . . . . . 18
88 5.2.6. Sign . . . . . . . . . . . . . . . . . . . . . . . . 19
89 5.2.7. Verify . . . . . . . . . . . . . . . . . . . . . . . 19
90 6. Ed25519 Python Illustration . . . . . . . . . . . . . . . . . 20
91 7. Test Vectors . . . . . . . . . . . . . . . . . . . . . . . . 23
92 7.1. Test Vectors for Ed25519 . . . . . . . . . . . . . . . . 24
93 7.2. Test Vectors for Ed25519ctx . . . . . . . . . . . . . . . 27
94 7.3. Test Vectors for Ed25519ph . . . . . . . . . . . . . . . 30
95 7.4. Test Vectors for Ed448 . . . . . . . . . . . . . . . . . 30
96 7.5. Test Vectors for Ed448ph . . . . . . . . . . . . . . . . 38
97 8. Security Considerations . . . . . . . . . . . . . . . . . . . 40
98 8.1. Side-Channel Leaks . . . . . . . . . . . . . . . . . . . 40
99 8.2. Randomness Considerations . . . . . . . . . . . . . . . . 40
100 8.3. Use of Contexts . . . . . . . . . . . . . . . . . . . . . 41
101 8.4. Signature Malleability . . . . . . . . . . . . . . . . . 41
102 8.5. Choice of Signature Primitive . . . . . . . . . . . . . . 41
103 8.6. Mixing Different Prehashes . . . . . . . . . . . . . . . 42
104 8.7. Signing Large Amounts of Data at Once . . . . . . . . . . 42
105 8.8. Multiplication by Cofactor in Verification . . . . . . . 43
106 8.9. Use of SHAKE256 as a Hash Function . . . . . . . . . . . 43
107 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 43
108 9.1. Normative References . . . . . . . . . . . . . . . . . . 43
109 9.2. Informative References . . . . . . . . . . . . . . . . . 44
114Josefsson & Liusvaara Informational [Page 2]
116RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
119 Appendix A. Ed25519/Ed448 Python Library . . . . . . . . . . . . 46
120 Appendix B. Library Driver . . . . . . . . . . . . . . . . . . . 58
121 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 60
122 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 60
126 The Edwards-curve Digital Signature Algorithm (EdDSA) is a variant of
127 Schnorr's signature system with (possibly twisted) Edwards curves.
128 EdDSA needs to be instantiated with certain parameters, and this
129 document describes some recommended variants.
131 To facilitate adoption of EdDSA in the Internet community, this
132 document describes the signature scheme in an implementation-oriented
133 way and provides sample code and test vectors.
135 The advantages with EdDSA are as follows:
137 1. EdDSA provides high performance on a variety of platforms;
139 2. The use of a unique random number for each signature is not
142 3. It is more resilient to side-channel attacks;
144 4. EdDSA uses small public keys (32 or 57 bytes) and signatures (64
145 or 114 bytes) for Ed25519 and Ed448, respectively;
147 5. The formulas are "complete", i.e., they are valid for all points
148 on the curve, with no exceptions. This obviates the need for
149 EdDSA to perform expensive point validation on untrusted public
152 6. EdDSA provides collision resilience, meaning that hash-function
153 collisions do not break this system (only holds for PureEdDSA).
155 The original EdDSA paper [EDDSA] and the generalized version
156 described in "EdDSA for more curves" [EDDSA2] provide further
157 background. RFC 7748 [RFC7748] discusses specific curves, including
158 Curve25519 [CURVE25519] and Ed448-Goldilocks [ED448].
160 Ed25519 is intended to operate at around the 128-bit security level
161 and Ed448 at around the 224-bit security level. A sufficiently large
162 quantum computer would be able to break both. Reasonable projections
163 of the abilities of classical computers conclude that Ed25519 is
164 perfectly safe. Ed448 is provided for those applications with
165 relaxed performance requirements and where there is a desire to hedge
166 against analytical attacks on elliptic curves.
170Josefsson & Liusvaara Informational [Page 3]
172RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
1752. Notation and Conventions
177 The following notation is used throughout the document:
179 p Denotes the prime number defining the underlying field
181 GF(p) Finite field with p elements
183 x^y x multiplied by itself y times
185 B Generator of the group or subgroup of interest
187 [n]X X added to itself n times
189 h[i] The i'th octet of octet string
191 h_i The i'th bit of h
193 a || b (bit-)string a concatenated with (bit-)string b
195 a <= b a is less than or equal to b
197 a >= b a is greater than or equal to b
201 i*j Multiplication of i and j
203 i-j Subtraction of j from i
205 i/j Division of i by j
207 i x j Cartesian product of i and j
209 (u,v) Elliptic curve point with x-coordinate u and
212 SHAKE256(x, y) The y first octets of SHAKE256 [FIPS202] output for
215 OCTET(x) The octet with value x
217 OLEN(x) The number of octets in string x
226Josefsson & Liusvaara Informational [Page 4]
228RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
231 dom2(x, y) The blank octet string when signing or verifying
232 Ed25519. Otherwise, the octet string: "SigEd25519 no
233 Ed25519 collisions" || octet(x) || octet(OLEN(y)) ||
234 y, where x is in range 0-255 and y is an octet string
235 of at most 255 octets. "SigEd25519 no Ed25519
236 collisions" is in ASCII (32 octets).
238 dom4(x, y) The octet string "SigEd448" || octet(x) ||
239 octet(OLEN(y)) || y, where x is in range 0-255 and y
240 is an octet string of at most 255 octets. "SigEd448"
241 is in ASCII (8 octets).
243 Parentheses (i.e., '(' and ')') are used to group expressions, in
244 order to avoid having the description depend on a binding order
247 Bit strings are converted to octet strings by taking bits from left
248 to right, packing those from the least significant bit of each octet
249 to the most significant bit, and moving to the next octet when each
250 octet fills up. The conversion from octet string to bit string is
251 the reverse of this process; for example, the 16-bit bit string
253 b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15
255 is converted into two octets x0 and x1 (in this order) as
257 x0 = b7*128+b6*64+b5*32+b4*16+b3*8+b2*4+b1*2+b0
258 x1 = b15*128+b14*64+b13*32+b12*16+b11*8+b10*4+b9*2+b8
260 Little-endian encoding into bits places bits from left to right and
261 from least significant to most significant. If combined with
262 bit-string-to-octet-string conversion defined above, this results in
263 little-endian encoding into octets (if length is not a multiple of 8,
264 the most significant bits of the last octet remain unused).
266 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
267 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
268 document are to be interpreted as described in [RFC2119].
272 EdDSA is a digital signature system with 11 parameters.
274 The generic EdDSA digital signature system with its 11 input
275 parameters is not intended to be implemented directly. Choosing
276 parameters is critical for secure and efficient operation. Instead,
277 you would implement a particular parameter choice for EdDSA (such as
282Josefsson & Liusvaara Informational [Page 5]
284RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
287 Ed25519 or Ed448), sometimes slightly generalized to achieve code
288 reuse to cover Ed25519 and Ed448.
290 Therefore, a precise explanation of the generic EdDSA is thus not
291 particularly useful for implementers. For background and
292 completeness, a succinct description of the generic EdDSA algorithm
295 The definition of some parameters, such as n and c, may help to
296 explain some steps of the algorithm that are not intuitive.
298 This description closely follows [EDDSA2].
300 EdDSA has 11 parameters:
302 1. An odd prime power p. EdDSA uses an elliptic curve over the
305 2. An integer b with 2^(b-1) > p. EdDSA public keys have exactly b
306 bits, and EdDSA signatures have exactly 2*b bits. b is
307 recommended to be a multiple of 8, so public key and signature
308 lengths are an integral number of octets.
310 3. A (b-1)-bit encoding of elements of the finite field GF(p).
312 4. A cryptographic hash function H producing 2*b-bit output.
313 Conservative hash functions (i.e., hash functions where it is
314 infeasible to create collisions) are recommended and do not have
315 much impact on the total cost of EdDSA.
317 5. An integer c that is 2 or 3. Secret EdDSA scalars are multiples
318 of 2^c. The integer c is the base-2 logarithm of the so-called
321 6. An integer n with c <= n < b. Secret EdDSA scalars have exactly
322 n + 1 bits, with the top bit (the 2^n position) always set and
323 the bottom c bits always cleared.
325 7. A non-square element d of GF(p). The usual recommendation is to
326 take it as the value nearest to zero that gives an acceptable
329 8. A non-zero square element a of GF(p). The usual recommendation
330 for best performance is a = -1 if p mod 4 = 1, and a = 1 if
333 9. An element B != (0,1) of the set E = { (x,y) is a member of
334 GF(p) x GF(p) such that a * x^2 + y^2 = 1 + d * x^2 * y^2 }.
338Josefsson & Liusvaara Informational [Page 6]
340RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
343 10. An odd prime L such that [L]B = 0 and 2^c * L = #E. The number
344 #E (the number of points on the curve) is part of the standard
345 data provided for an elliptic curve E, or it can be computed as
348 11. A "prehash" function PH. PureEdDSA means EdDSA where PH is the
349 identity function, i.e., PH(M) = M. HashEdDSA means EdDSA where
350 PH generates a short output, no matter how long the message is;
351 for example, PH(M) = SHA-512(M).
353 Points on the curve form a group under addition, (x3, y3) = (x1, y1)
354 + (x2, y2), with the formulas
356 x1 * y2 + x2 * y1 y1 * y2 - a * x1 * x2
357 x3 = --------------------------, y3 = ---------------------------
358 1 + d * x1 * x2 * y1 * y2 1 - d * x1 * x2 * y1 * y2
360 The neutral element in the group is (0,1).
362 Unlike many other curves used for cryptographic applications, these
363 formulas are "complete"; they are valid for all points on the curve,
364 with no exceptions. In particular, the denominators are non-zero for
367 There are more efficient formulas, which are still complete, that use
368 homogeneous coordinates to avoid the expensive modulo p inversions.
369 See [Faster-ECC] and [Edwards-revisited].
373 An integer 0 < S < L - 1 is encoded in little-endian form as a b-bit
376 An element (x,y) of E is encoded as a b-bit string called ENC(x,y),
377 which is the (b-1)-bit encoding of y concatenated with one bit that
378 is 1 if x is negative and 0 if x is not negative.
380 The encoding of GF(p) is used to define "negative" elements of GF(p):
381 specifically, x is negative if the (b-1)-bit encoding of x is
382 lexicographically larger than the (b-1)-bit encoding of -x.
386 An EdDSA private key is a b-bit string k. Let the hash H(k) =
387 (h_0, h_1, ..., h_(2b-1)) determine an integer s, which is 2^n plus
388 the sum of m = 2^i * h_i for all integer i, c <= i < n. Let s
389 determine the multiple A = [s]B. The EdDSA public key is ENC(A).
390 The bits h_b, ..., h_(2b-1) are used below during signing.
394Josefsson & Liusvaara Informational [Page 7]
396RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
401 The EdDSA signature of a message M under a private key k is defined
402 as the PureEdDSA signature of PH(M). In other words, EdDSA simply
403 uses PureEdDSA to sign PH(M).
405 The PureEdDSA signature of a message M under a private key k is the
406 2*b-bit string ENC(R) || ENC(S). R and S are derived as follows.
407 First define r = H(h_b || ... || h_(2b-1) || M) interpreting 2*b-bit
408 strings in little-endian form as integers in {0, 1, ..., 2^(2*b) -
409 1}. Let R = [r]B and S = (r + H(ENC(R) || ENC(A) || PH(M)) * s) mod
410 L. The s used here is from the previous section.
414 To verify a PureEdDSA signature ENC(R) || ENC(S) on a message M under
415 a public key ENC(A), proceed as follows. Parse the inputs so that A
416 and R are elements of E, and S is a member of the set {0, 1, ...,
417 L-1}. Compute h = H(ENC(R) || ENC(A) || M), and check the group
418 equation [2^c * S] B = 2^c * R + [2^c * h] A in E. The signature is
419 rejected if parsing fails (including S being out of range) or if the
420 group equation does not hold.
422 EdDSA verification for a message M is defined as PureEdDSA
423 verification for PH(M).
4254. PureEdDSA, HashEdDSA, and Naming
428 function. This may be the identity function, resulting in an
429 algorithm called PureEdDSA, or a collision-resistant hash function
430 such as SHA-512, resulting in an algorithm called HashEdDSA.
432 Choosing which variant to use depends on which property is deemed to
433 be more important between 1) collision resilience and 2) a single-
434 pass interface for creating signatures. The collision resilience
435 property means EdDSA is secure even if it is feasible to compute
436 collisions for the hash function. The single-pass interface property
437 means that only one pass over the input message is required to create
438 a signature. PureEdDSA requires two passes over the input. Many
439 existing APIs, protocols, and environments assume digital signature
440 algorithms only need one pass over the input and may have API or
441 bandwidth concerns supporting anything else.
443 Note that single-pass verification is not possible with most uses of
444 signatures, no matter which signature algorithm is chosen. This is
445 because most of the time, one can't process the message until the
446 signature is validated, which needs a pass on the entire message.
450Josefsson & Liusvaara Informational [Page 8]
452RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
455 This document specifies parameters resulting in the HashEdDSA
456 variants Ed25519ph and Ed448ph and the PureEdDSA variants Ed25519 and
461 This section instantiates the general EdDSA algorithm for the
462 edwards25519 and edwards448 curves, each for the PureEdDSA and
463 HashEdDSA variants (plus a contextualized extension of the Ed25519
464 scheme). Thus, five different parameter sets are described.
4665.1. Ed25519ph, Ed25519ctx, and Ed25519
468 Ed25519 is EdDSA instantiated with:
470 +-----------+-------------------------------------------------------+
471 | Parameter | Value |
472 +-----------+-------------------------------------------------------+
473 | p | p of edwards25519 in [RFC7748] (i.e., 2^255 - 19) |
475 | encoding | 255-bit little-endian encoding of {0, 1, ..., p-1} |
477 | H(x) | SHA-512(dom2(phflag,context)||x) [RFC6234] |
478 | c | base 2 logarithm of cofactor of edwards25519 in |
479 | | [RFC7748] (i.e., 3) |
481 | d | d of edwards25519 in [RFC7748] (i.e., -121665/121666 |
482 | | = 370957059346694393431380835087545651895421138798432 |
483 | | 19016388785533085940283555) |
485 | B | (X(P),Y(P)) of edwards25519 in [RFC7748] (i.e., (1511 |
486 | | 22213495354007725011514095885315114540126930418572060 |
487 | | 46113283949847762202, 4631683569492647816942839400347 |
488 | | 5163141307993866256225615783033603165251855960)) |
489 | L | order of edwards25519 in [RFC7748] (i.e., |
490 | | 2^252+27742317777372353535851937790883648493). |
491 | PH(x) | x (i.e., the identity function) |
492 +-----------+-------------------------------------------------------+
494 Table 1: Parameters of Ed25519
496 For Ed25519, dom2(f,c) is the empty string. The phflag value is
497 irrelevant. The context (if present at all) MUST be empty. This
498 causes the scheme to be one and the same with the Ed25519 scheme
501 For Ed25519ctx, phflag=0. The context input SHOULD NOT be empty.
506Josefsson & Liusvaara Informational [Page 9]
508RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
511 For Ed25519ph, phflag=1 and PH is SHA512 instead. That is, the input
512 is hashed using SHA-512 before signing with Ed25519.
514 Value of context is set by the signer and verifier (maximum of 255
515 octets; the default is empty string, except for Ed25519, which can't
516 have context) and has to match octet by octet for verification to be
519 The curve used is equivalent to Curve25519 [CURVE25519], under a
520 change of coordinates, which means that the difficulty of the
521 discrete logarithm problem is the same as for Curve25519.
5235.1.1. Modular Arithmetic
525 For advice on how to implement arithmetic modulo p = 2^255 - 19
526 efficiently and securely, see Curve25519 [CURVE25519]. For inversion
527 modulo p, it is recommended to use the identity x^-1 = x^(p-2) (mod
528 p). Inverting zero should never happen, as it would require invalid
529 input, which would have been detected before, or would be a
532 For point decoding or "decompression", square roots modulo p are
533 needed. They can be computed using the Tonelli-Shanks algorithm or
534 the special case for p = 5 (mod 8). To find a square root of a,
535 first compute the candidate root x = a^((p+3)/8) (mod p). Then there
538 x^2 = a (mod p). Then x is a square root.
540 x^2 = -a (mod p). Then 2^((p-1)/4) * x is a square root.
542 a is not a square modulo p.
546 All values are coded as octet strings, and integers are coded using
547 little-endian convention, i.e., a 32-octet string h h[0],...h[31]
548 represents the integer h[0] + 2^8 * h[1] + ... + 2^248 * h[31].
550 A curve point (x,y), with coordinates in the range 0 <= x,y < p, is
551 coded as follows. First, encode the y-coordinate as a little-endian
552 string of 32 octets. The most significant bit of the final octet is
553 always zero. To form the encoding of the point, copy the least
554 significant bit of the x-coordinate to the most significant bit of
562Josefsson & Liusvaara Informational [Page 10]
564RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
569 Decoding a point, given as a 32-octet string, is a little more
572 1. First, interpret the string as an integer in little-endian
573 representation. Bit 255 of this number is the least significant
574 bit of the x-coordinate and denote this value x_0. The
575 y-coordinate is recovered simply by clearing this bit. If the
576 resulting value is >= p, decoding fails.
578 2. To recover the x-coordinate, the curve equation implies
579 x^2 = (y^2 - 1) / (d y^2 + 1) (mod p). The denominator is always
580 non-zero mod p. Let u = y^2 - 1 and v = d y^2 + 1. To compute
581 the square root of (u/v), the first step is to compute the
582 candidate root x = (u/v)^((p+3)/8). This can be done with the
583 following trick, using a single modular powering for both the
584 inversion of v and the square root:
587 x = (u/v) = u v (u v^7) (mod p)
589 3. Again, there are three cases:
591 1. If v x^2 = u (mod p), x is a square root.
593 2. If v x^2 = -u (mod p), set x <-- x * 2^((p-1)/4), which is a
596 3. Otherwise, no square root exists for modulo p, and decoding
599 4. Finally, use the x_0 bit to select the right square root. If
600 x = 0, and x_0 = 1, decoding fails. Otherwise, if x_0 != x mod
601 2, set x <-- p - x. Return the decoded point (x,y).
605 For point addition, the following method is recommended. A point
606 (x,y) is represented in extended homogeneous coordinates (X, Y, Z,
607 T), with x = X/Z, y = Y/Z, x * y = T/Z.
609 The neutral point is (0,1), or equivalently in extended homogeneous
610 coordinates (0, Z, Z, 0) for any non-zero Z.
618Josefsson & Liusvaara Informational [Page 11]
620RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
623 The following formulas for adding two points, (x3,y3) =
624 (x1,y1)+(x2,y2), on twisted Edwards curves with a=-1, square a, and
625 non-square d are described in Section 3.1 of [Edwards-revisited] and
626 in [EFD-TWISTED-ADD]. They are complete, i.e., they work for any
627 pair of valid input points.
642 For point doubling, (x3,y3) = (x1,y1)+(x1,y1), one could just
643 substitute equal points in the above (because of completeness, such
644 substitution is valid) and observe that four multiplications turn
645 into squares. However, using the formulas described in Section 3.2
646 of [Edwards-revisited] and in [EFD-TWISTED-DBL] saves a few smaller
674Josefsson & Liusvaara Informational [Page 12]
676RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
681 The private key is 32 octets (256 bits, corresponding to b) of
682 cryptographically secure random data. See [RFC4086] for a discussion
685 The 32-byte public key is generated by the following steps.
687 1. Hash the 32-byte private key using SHA-512, storing the digest in
688 a 64-octet large buffer, denoted h. Only the lower 32 bytes are
689 used for generating the public key.
691 2. Prune the buffer: The lowest three bits of the first octet are
692 cleared, the highest bit of the last octet is cleared, and the
693 second highest bit of the last octet is set.
695 3. Interpret the buffer as the little-endian integer, forming a
696 secret scalar s. Perform a fixed-base scalar multiplication
699 4. The public key A is the encoding of the point [s]B. First,
700 encode the y-coordinate (in the range 0 <= y < p) as a little-
701 endian string of 32 octets. The most significant bit of the
702 final octet is always zero. To form the encoding of the point
703 [s]B, copy the least significant bit of the x coordinate to the
704 most significant bit of the final octet. The result is the
709 The inputs to the signing procedure is the private key, a 32-octet
710 string, and a message M of arbitrary size. For Ed25519ctx and
711 Ed25519ph, there is additionally a context C of at most 255 octets
712 and a flag F, 0 for Ed25519ctx and 1 for Ed25519ph.
714 1. Hash the private key, 32 octets, using SHA-512. Let h denote the
715 resulting digest. Construct the secret scalar s from the first
716 half of the digest, and the corresponding public key A, as
717 described in the previous section. Let prefix denote the second
718 half of the hash digest, h[32],...,h[63].
720 2. Compute SHA-512(dom2(F, C) || prefix || PH(M)), where M is the
721 message to be signed. Interpret the 64-octet digest as a little-
724 3. Compute the point [r]B. For efficiency, do this by first
725 reducing r modulo L, the group order of B. Let the string R be
726 the encoding of this point.
730Josefsson & Liusvaara Informational [Page 13]
732RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
735 4. Compute SHA512(dom2(F, C) || R || A || PH(M)), and interpret the
736 64-octet digest as a little-endian integer k.
738 5. Compute S = (r + k * s) mod L. For efficiency, again reduce k
741 6. Form the signature of the concatenation of R (32 octets) and the
742 little-endian encoding of S (32 octets; the three most
743 significant bits of the final octet are always zero).
747 1. To verify a signature on a message M using public key A, with F
748 being 0 for Ed25519ctx, 1 for Ed25519ph, and if Ed25519ctx or
749 Ed25519ph is being used, C being the context, first split the
750 signature into two 32-octet halves. Decode the first half as a
751 point R, and the second half as an integer S, in the range
752 0 <= s < L. Decode the public key A as point A'. If any of the
753 decodings fail (including S being out of range), the signature is
756 2. Compute SHA512(dom2(F, C) || R || A || PH(M)), and interpret the
757 64-octet digest as a little-endian integer k.
759 3. Check the group equation [8][S]B = [8]R + [8][k]A'. It's
760 sufficient, but not required, to instead check [S]B = R + [k]A'.
786Josefsson & Liusvaara Informational [Page 14]
788RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
7915.2. Ed448ph and Ed448
793 Ed448 is EdDSA instantiated with:
795 +-----------+-------------------------------------------------------+
796 | Parameter | Value |
797 +-----------+-------------------------------------------------------+
798 | p | p of edwards448 in [RFC7748] (i.e., 2^448 - 2^224 - |
801 | encoding | 455-bit little-endian encoding of {0, 1, ..., p-1} |
803 | H(x) | SHAKE256(dom4(phflag,context)||x, 114) |
805 | c | base 2 logarithm of cofactor of edwards448 in |
806 | | [RFC7748] (i.e., 2) |
808 | d | d of edwards448 in [RFC7748] (i.e., -39081) |
810 | B | (X(P),Y(P)) of edwards448 in [RFC7748] (i.e., (224580 |
811 | | 04029592430018760433409989603624678964163256413424612 |
812 | | 54616869504154674060329090291928693579532825780320751 |
813 | | 46446173674602635247710, 2988192100784814926760179304 |
814 | | 43930673437544040154080242095928241372331506189835876 |
815 | | 00353687865541878473398230323350346250053154506283266 |
817 | L | order of edwards448 in [RFC7748] (i.e., 2^446 - 13818 |
818 | | 06680989511535200738674851542688033669247488217860989 |
820 | PH(x) | x (i.e., the identity function) |
821 +-----------+-------------------------------------------------------+
823 Table 2: Parameters of Ed448
825 Ed448ph is the same but with PH being SHAKE256(x, 64) and phflag
826 being 1, i.e., the input is hashed before signing with Ed448 with a
827 hash constant modified.
829 Value of context is set by signer and verifier (maximum of 255
830 octets; the default is empty string) and has to match octet by octet
831 for verification to be successful.
833 The curve is equivalent to Ed448-Goldilocks under change of the
834 basepoint, which preserves difficulty of the discrete logarithm.
842Josefsson & Liusvaara Informational [Page 15]
844RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
8475.2.1. Modular Arithmetic
849 For advice on how to implement arithmetic modulo p = 2^448 - 2^224 -
850 1 efficiently and securely, see [ED448]. For inversion modulo p, it
851 is recommended to use the identity x^-1 = x^(p-2) (mod p). Inverting
852 zero should never happen, as it would require invalid input, which
853 would have been detected before, or would be a calculation error.
855 For point decoding or "decompression", square roots modulo p are
856 needed. They can be computed by first computing candidate root
857 x = a ^ (p+1)/4 (mod p) and then checking if x^2 = a. If it is, then
858 x is the square root of a; if it isn't, then a does not have a square
863 All values are coded as octet strings, and integers are coded using
864 little-endian convention, i.e., a 57-octet string h h[0],...h[56]
865 represents the integer h[0] + 2^8 * h[1] + ... + 2^448 * h[56].
867 A curve point (x,y), with coordinates in the range 0 <= x,y < p, is
868 coded as follows. First, encode the y-coordinate as a little-endian
869 string of 57 octets. The final octet is always zero. To form the
870 encoding of the point, copy the least significant bit of the
871 x-coordinate to the most significant bit of the final octet.
875 Decoding a point, given as a 57-octet string, is a little more
878 1. First, interpret the string as an integer in little-endian
879 representation. Bit 455 of this number is the least significant
880 bit of the x-coordinate, and denote this value x_0. The
881 y-coordinate is recovered simply by clearing this bit. If the
882 resulting value is >= p, decoding fails.
884 2. To recover the x-coordinate, the curve equation implies
885 x^2 = (y^2 - 1) / (d y^2 - 1) (mod p). The denominator is always
886 non-zero mod p. Let u = y^2 - 1 and v = d y^2 - 1. To compute
887 the square root of (u/v), the first step is to compute the
888 candidate root x = (u/v)^((p+1)/4). This can be done using the
889 following trick, to use a single modular powering for both the
890 inversion of v and the square root:
893 x = (u/v) = u v (u^5 v^3) (mod p)
898Josefsson & Liusvaara Informational [Page 16]
900RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
903 3. If v * x^2 = u, the recovered x-coordinate is x. Otherwise, no
904 square root exists, and the decoding fails.
906 4. Finally, use the x_0 bit to select the right square root. If
907 x = 0, and x_0 = 1, decoding fails. Otherwise, if x_0 != x mod
908 2, set x <-- p - x. Return the decoded point (x,y).
912 For point addition, the following method is recommended. A point
913 (x,y) is represented in projective coordinates (X, Y, Z), with
916 The neutral point is (0,1), or equivalently in projective coordinates
917 (0, Z, Z) for any non-zero Z.
919 The following formulas for adding two points, (x3,y3) =
920 (x1,y1)+(x2,y2) on untwisted Edwards curve (i.e., a=1) with non-
921 square d, are described in Section 4 of [Faster-ECC] and in
922 [EFD-ADD]. They are complete, i.e., they work for any pair of valid
954Josefsson & Liusvaara Informational [Page 17]
956RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
959 Again, similar to the other curve, doubling formulas can be obtained
960 by substituting equal points, turning four multiplications into
961 squares. However, this is not even nearly optimal; the following
962 formulas described in Section 4 of [Faster-ECC] and in [EFD-DBL] save
963 multiple multiplications.
977 The private key is 57 octets (456 bits, corresponding to b) of
978 cryptographically secure random data. See [RFC4086] for a discussion
981 The 57-byte public key is generated by the following steps:
983 1. Hash the 57-byte private key using SHAKE256(x, 114), storing the
984 digest in a 114-octet large buffer, denoted h. Only the lower 57
985 bytes are used for generating the public key.
987 2. Prune the buffer: The two least significant bits of the first
988 octet are cleared, all eight bits the last octet are cleared, and
989 the highest bit of the second to last octet is set.
991 3. Interpret the buffer as the little-endian integer, forming a
992 secret scalar s. Perform a known-base-point scalar
995 4. The public key A is the encoding of the point [s]B. First encode
996 the y-coordinate (in the range 0 <= y < p) as a little-endian
997 string of 57 octets. The most significant bit of the final octet
998 is always zero. To form the encoding of the point [s]B, copy the
999 least significant bit of the x coordinate to the most significant
1000 bit of the final octet. The result is the public key.
1010Josefsson & Liusvaara Informational [Page 18]
1012RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
1017 The inputs to the signing procedure is the private key, a 57-octet
1018 string, a flag F, which is 0 for Ed448, 1 for Ed448ph, context C of
1019 at most 255 octets, and a message M of arbitrary size.
1021 1. Hash the private key, 57 octets, using SHAKE256(x, 114). Let h
1022 denote the resulting digest. Construct the secret scalar s from
1023 the first half of the digest, and the corresponding public key A,
1024 as described in the previous section. Let prefix denote the
1025 second half of the hash digest, h[57],...,h[113].
1027 2. Compute SHAKE256(dom4(F, C) || prefix || PH(M), 114), where M is
1028 the message to be signed, F is 1 for Ed448ph, 0 for Ed448, and C
1029 is the context to use. Interpret the 114-octet digest as a
1030 little-endian integer r.
1032 3. Compute the point [r]B. For efficiency, do this by first
1033 reducing r modulo L, the group order of B. Let the string R be
1034 the encoding of this point.
1036 4. Compute SHAKE256(dom4(F, C) || R || A || PH(M), 114), and
1037 interpret the 114-octet digest as a little-endian integer k.
1039 5. Compute S = (r + k * s) mod L. For efficiency, again reduce k
1042 6. Form the signature of the concatenation of R (57 octets) and the
1043 little-endian encoding of S (57 octets; the ten most significant
1044 bits of the final octets are always zero).
1048 1. To verify a signature on a message M using context C and public
1049 key A, with F being 0 for Ed448 and 1 for Ed448ph, first split
1050 the signature into two 57-octet halves. Decode the first half as
1051 a point R, and the second half as an integer S, in the range 0 <=
1052 s < L. Decode the public key A as point A'. If any of the
1053 decodings fail (including S being out of range), the signature is
1056 2. Compute SHAKE256(dom4(F, C) || R || A || PH(M), 114), and
1057 interpret the 114-octet digest as a little-endian integer k.
1059 3. Check the group equation [4][S]B = [4]R + [4][k]A'. It's
1060 sufficient, but not required, to instead check [S]B = R + [k]A'.
1066Josefsson & Liusvaara Informational [Page 19]
1068RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
10716. Ed25519 Python Illustration
1073 The rest of this section describes how Ed25519 can be implemented in
1074 Python (version 3.2 or later) for illustration. See Appendix A for
1075 the complete implementation and Appendix B for a test-driver to run
1076 it through some test vectors.
1078 Note that this code is not intended for production as it is not
1079 proven to be correct for all inputs, nor does it protect against
1080 side-channel attacks. The purpose is to illustrate the algorithm to
1081 help implementers with their own implementation.
1083## First, some preliminaries that will be needed.
1088 return hashlib.sha512(s).digest()
1094 return pow(x, p-2, p)
1097d = -121665 * modp_inv(121666) % p
1100q = 2**252 + 27742317777372353535851937790883648493
1103 return int.from_bytes(sha512(s), "little") % q
1105## Then follows functions to perform point operations.
1107# Points are represented as tuples (X, Y, Z, T) of extended
1108# coordinates, with x = X/Z, y = Y/Z, x*y = T/Z
1111 A, B = (P[1]-P[0]) * (Q[1]-Q[0]) % p, (P[1]+P[0]) * (Q[1]+Q[0]) % p;
1112 C, D = 2 * P[3] * Q[3] * d % p, 2 * P[2] * Q[2] % p;
1113 E, F, G, H = B-A, D-C, D+C, B+A;
1114 return (E*F, G*H, F*G, E*H);
1122Josefsson & Liusvaara Informational [Page 20]
1124RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
1129 Q = (0, 1, 1, 0) # Neutral element
1137def point_equal(P, Q):
1138 # x1 / z1 == x2 / z2 <==> x1 * z2 == x2 * z1
1139 if (P[0] * Q[2] - Q[0] * P[2]) % p != 0:
1141 if (P[1] * Q[2] - Q[1] * P[2]) % p != 0:
1145## Now follows functions for point compression.
1148modp_sqrt_m1 = pow(2, (p-1) // 4, p)
1150# Compute corresponding x-coordinate, with low bit corresponding to
1151# sign, or return None on failure
1152def recover_x(y, sign):
1155 x2 = (y*y-1) * modp_inv(d*y*y+1)
1162 # Compute square root of x2
1163 x = pow(x2, (p+3) // 8, p)
1164 if (x*x - x2) % p != 0:
1165 x = x * modp_sqrt_m1 % p
1166 if (x*x - x2) % p != 0:
1178Josefsson & Liusvaara Informational [Page 21]
1180RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
1184g_y = 4 * modp_inv(5) % p
1185g_x = recover_x(g_y, 0)
1186G = (g_x, g_y, 1, g_x * g_y % p)
1188def point_compress(P):
1189 zinv = modp_inv(P[2])
1192 return int.to_bytes(y | ((x & 1) << 255), 32, "little")
1194def point_decompress(s):
1196 raise Exception("Invalid input length for decompression")
1197 y = int.from_bytes(s, "little")
1201 x = recover_x(y, sign)
1205 return (x, y, 1, x*y % p)
1207## These are functions for manipulating the private key.
1209def secret_expand(secret):
1210 if len(secret) != 32:
1211 raise Exception("Bad size of private key")
1213 a = int.from_bytes(h[:32], "little")
1218def secret_to_public(secret):
1219 (a, dummy) = secret_expand(secret)
1220 return point_compress(point_mul(a, G))
1234Josefsson & Liusvaara Informational [Page 22]
1236RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
1239## The signature function works as below.
1241def sign(secret, msg):
1242 a, prefix = secret_expand(secret)
1243 A = point_compress(point_mul(a, G))
1244 r = sha512_modq(prefix + msg)
1246 Rs = point_compress(R)
1247 h = sha512_modq(Rs + A + msg)
1249 return Rs + int.to_bytes(s, 32, "little")
1251## And finally the verification function.
1253def verify(public, msg, signature):
1254 if len(public) != 32:
1255 raise Exception("Bad public key length")
1256 if len(signature) != 64:
1257 Exception("Bad signature length")
1258 A = point_decompress(public)
1262 R = point_decompress(Rs)
1265 s = int.from_bytes(signature[32:], "little")
1266 if s >= q: return False
1267 h = sha512_modq(Rs + public + msg)
1268 sB = point_mul(s, G)
1269 hA = point_mul(h, A)
1270 return point_equal(sB, point_add(R, hA))
1274 This section contains test vectors for Ed25519ph, Ed25519ctx,
1275 Ed448ph, Ed25519, and Ed448.
1277 Each section contains a sequence of test vectors. The octets are hex
1278 encoded, and whitespace is inserted for readability. Ed25519,
1279 Ed25519ctx, and Ed25519ph private and public keys are 32 octets;
1280 signatures are 64 octets. Ed448 and Ed448ph private and public keys
1281 are 57 octets; signatures are 114 octets. Messages are of arbitrary
1282 length. If the context is non-empty, it is given as 1-255 octets.
1290Josefsson & Liusvaara Informational [Page 23]
1292RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
12957.1. Test Vectors for Ed25519
1297 These test vectors are taken from [ED25519-TEST-VECTORS] (but we
1298 removed the public key as a suffix of the private key and removed the
1299 message from the signature) and [ED25519-LIBGCRYPT-TEST-VECTORS].
1307 9d61b19deffd5a60ba844af492ec2cc4
1308 4449c5697b326919703bac031cae7f60
1311 d75a980182b10ab7d54bfed3c964073a
1312 0ee172f3daa62325af021a68f707511a
1314 MESSAGE (length 0 bytes):
1317 e5564300c360ac729086e2cc806e828a
1318 84877f1eb8e5d974d873e06522490155
1319 5fb8821590a33bacc61e39701cf9b46b
1320 d25bf5f0595bbe24655141438e7a100b
1328 4ccd089b28ff96da9db6c346ec114e0f
1329 5b8a319f35aba624da8cf6ed4fb8a6fb
1332 3d4017c3e843895a92b70aa74d1b7ebc
1333 9c982ccf2ec4968cc0cd55f12af4660c
1335 MESSAGE (length 1 byte):
1339 92a009a9f0d4cab8720e820b5f642540
1340 a2b27b5416503f8fb3762223ebdb69da
1341 085ac1e43e15996e458f3613d0f11d8c
1342 387b2eaeb4302aeeb00d291612bb0c00
1346Josefsson & Liusvaara Informational [Page 24]
1348RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
1357 c5aa8df43f9f837bedb7442f31dcb7b1
1358 66d38535076f094b85ce3a2e0b4458f7
1361 fc51cd8e6218a1a38da47ed00230f058
1362 0816ed13ba3303ac5deb911548908025
1364 MESSAGE (length 2 bytes):
1368 6291d657deec24024827e69c3abe01a3
1369 0ce548a284743a445e3680d7db5ac3ac
1370 18ff9b538d16f290ae67f760984dc659
1371 4a7c15e9716ed28dc027beceea1ec40a
1379 f5e5767cf153319517630f226876b86c
1380 8160cc583bc013744c6bf255f5cc0ee5
1383 278117fc144c72340f67d0f2316e8386
1384 ceffbf2b2428c9c51fef7c597f1d426e
1386 MESSAGE (length 1023 bytes):
1387 08b8b2b733424243760fe426a4b54908
1388 632110a66c2f6591eabd3345e3e4eb98
1389 fa6e264bf09efe12ee50f8f54e9f77b1
1390 e355f6c50544e23fb1433ddf73be84d8
1391 79de7c0046dc4996d9e773f4bc9efe57
1392 38829adb26c81b37c93a1b270b20329d
1393 658675fc6ea534e0810a4432826bf58c
1394 941efb65d57a338bbd2e26640f89ffbc
1395 1a858efcb8550ee3a5e1998bd177e93a
1396 7363c344fe6b199ee5d02e82d522c4fe
1397 ba15452f80288a821a579116ec6dad2b
1398 3b310da903401aa62100ab5d1a36553e
1402Josefsson & Liusvaara Informational [Page 25]
1404RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
1407 06203b33890cc9b832f79ef80560ccb9
1408 a39ce767967ed628c6ad573cb116dbef
1409 efd75499da96bd68a8a97b928a8bbc10
1410 3b6621fcde2beca1231d206be6cd9ec7
1411 aff6f6c94fcd7204ed3455c68c83f4a4
1412 1da4af2b74ef5c53f1d8ac70bdcb7ed1
1413 85ce81bd84359d44254d95629e9855a9
1414 4a7c1958d1f8ada5d0532ed8a5aa3fb2
1415 d17ba70eb6248e594e1a2297acbbb39d
1416 502f1a8c6eb6f1ce22b3de1a1f40cc24
1417 554119a831a9aad6079cad88425de6bd
1418 e1a9187ebb6092cf67bf2b13fd65f270
1419 88d78b7e883c8759d2c4f5c65adb7553
1420 878ad575f9fad878e80a0c9ba63bcbcc
1421 2732e69485bbc9c90bfbd62481d9089b
1422 eccf80cfe2df16a2cf65bd92dd597b07
1423 07e0917af48bbb75fed413d238f5555a
1424 7a569d80c3414a8d0859dc65a46128ba
1425 b27af87a71314f318c782b23ebfe808b
1426 82b0ce26401d2e22f04d83d1255dc51a
1427 ddd3b75a2b1ae0784504df543af8969b
1428 e3ea7082ff7fc9888c144da2af58429e
1429 c96031dbcad3dad9af0dcbaaaf268cb8
1430 fcffead94f3c7ca495e056a9b47acdb7
1431 51fb73e666c6c655ade8297297d07ad1
1432 ba5e43f1bca32301651339e22904cc8c
1433 42f58c30c04aafdb038dda0847dd988d
1434 cda6f3bfd15c4b4c4525004aa06eeff8
1435 ca61783aacec57fb3d1f92b0fe2fd1a8
1436 5f6724517b65e614ad6808d6f6ee34df
1437 f7310fdc82aebfd904b01e1dc54b2927
1438 094b2db68d6f903b68401adebf5a7e08
1439 d78ff4ef5d63653a65040cf9bfd4aca7
1440 984a74d37145986780fc0b16ac451649
1441 de6188a7dbdf191f64b5fc5e2ab47b57
1442 f7f7276cd419c17a3ca8e1b939ae49e4
1443 88acba6b965610b5480109c8b17b80e1
1444 b7b750dfc7598d5d5011fd2dcc5600a3
1445 2ef5b52a1ecc820e308aa342721aac09
1446 43bf6686b64b2579376504ccc493d97e
1447 6aed3fb0f9cd71a43dd497f01f17c0e2
1448 cb3797aa2a2f256656168e6c496afc5f
1449 b93246f6b1116398a346f1a641f3b041
1450 e989f7914f90cc2c7fff357876e506b5
1451 0d334ba77c225bc307ba537152f3f161
1452 0e4eafe595f6d9d90d11faa933a15ef1
1453 369546868a7f3a45a96768d40fd9d034
1454 12c091c6315cf4fde7cb68606937380d
1458Josefsson & Liusvaara Informational [Page 26]
1460RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
1463 b2eaaa707b4c4185c32eddcdd306705e
1464 4dc1ffc872eeee475a64dfac86aba41c
1465 0618983f8741c5ef68d3a101e8a3b8ca
1466 c60c905c15fc910840b94c00a0b9d0
1469 0aab4c900501b3e24d7cdf4663326a3a
1470 87df5e4843b2cbdb67cbf6e460fec350
1471 aa5371b1508f9f4528ecea23c436d94b
1472 5e8fcd4f681e30a6ac00a9704a188a03
1480 833fe62409237b9d62ec77587520911e
1481 9a759cec1d19755b7da901b96dca3d42
1484 ec172b93ad5e563bf4932c70e1245034
1485 c35467ef2efd4d64ebf819683467e2bf
1487 MESSAGE (length 64 bytes):
1488 ddaf35a193617abacc417349ae204131
1489 12e6fa4e89a97ea20a9eeee64b55d39a
1490 2192992a274fc1a836ba3c23a3feebbd
1491 454d4423643ce80e2a9ac94fa54ca49f
1494 dc2a4459e7369633a52b1bf277839a00
1495 201009a3efbf3ecb69bea2186c26b589
1496 09351fc9ac90b3ecfdfbc7c66431e030
1497 3dca179c138ac17ad9bef1177331a704
15007.2. Test Vectors for Ed25519ctx
1508 0305334e381af78f141cb666f6199f57
1509 bc3495335a256a95bd2a55bf546663f6
1514Josefsson & Liusvaara Informational [Page 27]
1516RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
1520 dfc9425e4f968f7f0c29f0259cf5f9ae
1521 d6851c2bb4ad8bfb860cfee0ab248292
1523 MESSAGE (length 16 bytes):
1524 f726936d19c800494e3fdaff20b276a8
1530 55a4cc2f70a54e04288c5f4cd1e45a7b
1531 b520b36292911876cada7323198dd87a
1532 8b36950b95130022907a7fb7c4e9b2d5
1533 f6cca685a587b4b21f4b888e4e7edb0d
1541 0305334e381af78f141cb666f6199f57
1542 bc3495335a256a95bd2a55bf546663f6
1545 dfc9425e4f968f7f0c29f0259cf5f9ae
1546 d6851c2bb4ad8bfb860cfee0ab248292
1548 MESSAGE (length 16 bytes):
1549 f726936d19c800494e3fdaff20b276a8
1555 fc60d5872fc46b3aa69f8b5b4351d580
1556 8f92bcc044606db097abab6dbcb1aee3
1557 216c48e8b3b66431b5b186d1d28f8ee1
1558 5a5ca2df6668346291c2043d4eb3e90d
1570Josefsson & Liusvaara Informational [Page 28]
1572RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
1576 0305334e381af78f141cb666f6199f57
1577 bc3495335a256a95bd2a55bf546663f6
1580 dfc9425e4f968f7f0c29f0259cf5f9ae
1581 d6851c2bb4ad8bfb860cfee0ab248292
1583 MESSAGE (length 16 bytes):
1584 508e9e6882b979fea900f62adceaca35
1590 8b70c1cc8310e1de20ac53ce28ae6e72
1591 07f33c3295e03bb5c0732a1d20dc6490
1592 8922a8b052cf99b7c4fe107a5abb5b2c
1593 4085ae75890d02df26269d8945f84b0b
1601 ab9c2853ce297ddab85c993b3ae14bca
1602 d39b2c682beabc27d6d4eb20711d6560
1605 0f1d1274943b91415889152e893d80e9
1606 3275a1fc0b65fd71b4b0dda10ad7d772
1608 MESSAGE (length 16 bytes):
1609 f726936d19c800494e3fdaff20b276a8
1615 21655b5f1aa965996b3f97b3c849eafb
1616 a922a0a62992f73b3d1b73106a84ad85
1617 e9b86a7b6005ea868337ff2d20a7f5fb
1618 d4cd10b0be49a68da2b2e0dc0ad8960f
1626Josefsson & Liusvaara Informational [Page 29]
1628RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
16317.3. Test Vectors for Ed25519ph
1639 833fe62409237b9d62ec77587520911e
1640 9a759cec1d19755b7da901b96dca3d42
1643 ec172b93ad5e563bf4932c70e1245034
1644 c35467ef2efd4d64ebf819683467e2bf
1646 MESSAGE (length 3 bytes):
1650 98a70222f0b8121aa9d30f813d683f80
1651 9e462b469c7ff87639499bb94e6dae41
1652 31f85042463c2a355a2003d062adf5aa
1653 a10b8c61e636062aaad11c2a26083406
16567.4. Test Vectors for Ed448
1664 6c82a562cb808d10d632be89c8513ebf
1665 6c929f34ddfa8c9f63c9960ef6e348a3
1666 528c8a3fcc2f044e39a3fc5b94492f8f
1670 5fd7449b59b461fd2ce787ec616ad46a
1671 1da1342485a70e1f8a0ea75d80e96778
1672 edf124769b46c7061bd6783df1e50f6c
1675 MESSAGE (length 0 bytes):
1682Josefsson & Liusvaara Informational [Page 30]
1684RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
1688 533a37f6bbe457251f023c0d88f976ae
1689 2dfb504a843e34d2074fd823d41a591f
1690 2b233f034f628281f2fd7a22ddd47d78
1691 28c59bd0a21bfd3980ff0d2028d4b18a
1692 9df63e006c5d1c2d345b925d8dc00b41
1693 04852db99ac5c7cdda8530a113a0f4db
1694 b61149f05a7363268c71d95808ff2e65
1703 c4eab05d357007c632f3dbb48489924d
1704 552b08fe0c353a0d4a1f00acda2c463a
1705 fbea67c5e8d2877c5e3bc397a659949e
1709 43ba28f430cdff456ae531545f7ecd0a
1710 c834a55d9358c0372bfa0c6c6798c086
1711 6aea01eb00742802b8438ea4cb82169c
1714 MESSAGE (length 1 byte):
1718 26b8f91727bd62897af15e41eb43c377
1719 efb9c610d48f2335cb0bd0087810f435
1720 2541b143c4b981b7e18f62de8ccdf633
1721 fc1bf037ab7cd779805e0dbcc0aae1cb
1722 cee1afb2e027df36bc04dcecbf154336
1723 c19f0af7e0a6472905e799f1953d2a0f
1724 f3348ab21aa4adafd1d234441cf807c0
1727 -----1 octet (with context)
1738Josefsson & Liusvaara Informational [Page 31]
1740RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
1744 c4eab05d357007c632f3dbb48489924d
1745 552b08fe0c353a0d4a1f00acda2c463a
1746 fbea67c5e8d2877c5e3bc397a659949e
1750 43ba28f430cdff456ae531545f7ecd0a
1751 c834a55d9358c0372bfa0c6c6798c086
1752 6aea01eb00742802b8438ea4cb82169c
1755 MESSAGE (length 1 byte):
1762 d4f8f6131770dd46f40867d6fd5d5055
1763 de43541f8c5e35abbcd001b32a89f7d2
1764 151f7647f11d8ca2ae279fb842d60721
1765 7fce6e042f6815ea000c85741de5c8da
1766 1144a6a1aba7f96de42505d7a7298524
1767 fda538fccbbb754f578c1cad10d54d0d
1768 5428407e85dcbc98a49155c13764e66c
1777 cd23d24f714274e744343237b93290f5
1778 11f6425f98e64459ff203e8985083ffd
1779 f60500553abc0e05cd02184bdb89c4cc
1783 dcea9e78f35a1bf3499a831b10b86c90
1784 aac01cd84b67a0109b55a36e9328b1e3
1785 65fce161d71ce7131a543ea4cb5f7e9f
1788 MESSAGE (length 11 bytes):
1789 0c3e544074ec63b0265e0c
1794Josefsson & Liusvaara Informational [Page 32]
1796RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
1800 1f0a8888ce25e8d458a21130879b840a
1801 9089d999aaba039eaf3e3afa090a09d3
1802 89dba82c4ff2ae8ac5cdfb7c55e94d5d
1803 961a29fe0109941e00b8dbdeea6d3b05
1804 1068df7254c0cdc129cbe62db2dc957d
1805 bb47b51fd3f213fb8698f064774250a5
1806 028961c9bf8ffd973fe5d5c206492b14
1815 258cdd4ada32ed9c9ff54e63756ae582
1816 fb8fab2ac721f2c8e676a72768513d93
1817 9f63dddb55609133f29adf86ec9929dc
1821 3ba16da0c6f2cc1f30187740756f5e79
1822 8d6bc5fc015d7c63cc9510ee3fd44adc
1823 24d8e968b6e46e6f94d19b945361726b
1826 MESSAGE (length 12 bytes):
1827 64a65f3cdedcdd66811e2915
1830 7eeeab7c4e50fb799b418ee5e3197ff6
1831 bf15d43a14c34389b59dd1a7b1b85b4a
1832 e90438aca634bea45e3a2695f1270f07
1833 fdcdf7c62b8efeaf00b45c2c96ba457e
1834 b1a8bf075a3db28e5c24f6b923ed4ad7
1835 47c3c9e03c7079efb87cb110d3a99861
1836 e72003cbae6d6b8b827e4e6c143064ff
1850Josefsson & Liusvaara Informational [Page 33]
1852RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
1856 7ef4e84544236752fbb56b8f31a23a10
1857 e42814f5f55ca037cdcc11c64c9a3b29
1858 49c1bb60700314611732a6c2fea98eeb
1862 b3da079b0aa493a5772029f0467baebe
1863 e5a8112d9d3a22532361da294f7bb381
1864 5c5dc59e176b4d9f381ca0938e13c6c0
1867 MESSAGE (length 13 bytes):
1868 64a65f3cdedcdd66811e2915e7
1871 6a12066f55331b6c22acd5d5bfc5d712
1872 28fbda80ae8dec26bdd306743c5027cb
1873 4890810c162c027468675ecf645a8317
1874 6c0d7323a2ccde2d80efe5a1268e8aca
1875 1d6fbc194d3f77c44986eb4ab4177919
1876 ad8bec33eb47bbb5fc6e28196fd1caf5
1877 6b4e7e0ba5519234d047155ac727a105
1886 d65df341ad13e008567688baedda8e9d
1887 cdc17dc024974ea5b4227b6530e339bf
1888 f21f99e68ca6968f3cca6dfe0fb9f4fa
1892 df9705f58edbab802c7f8363cfe5560a
1893 b1c6132c20a9f1dd163483a26f8ac53a
1894 39d6808bf4a1dfbd261b099bb03b3fb5
1897 MESSAGE (length 64 bytes):
1898 bd0f6a3747cd561bdddf4640a332461a
1899 4a30a12a434cd0bf40d766d9c6d458e5
1900 512204a30c17d1f50b5079631f64eb31
1901 12182da3005835461113718d1a5ef944
1906Josefsson & Liusvaara Informational [Page 34]
1908RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
1912 554bc2480860b49eab8532d2a533b7d5
1913 78ef473eeb58c98bb2d0e1ce488a98b1
1914 8dfde9b9b90775e67f47d4a1c3482058
1915 efc9f40d2ca033a0801b63d45b3b722e
1916 f552bad3b4ccb667da350192b61c508c
1917 f7b6b5adadc2c8d9a446ef003fb05cba
1918 5f30e88e36ec2703b349ca229c267083
1927 2ec5fe3c17045abdb136a5e6a913e32a
1928 b75ae68b53d2fc149b77e504132d3756
1929 9b7e766ba74a19bd6162343a21c8590a
1933 79756f014dcfe2079f5dd9e718be4171
1934 e2ef2486a08f25186f6bff43a9936b9b
1935 fe12402b08ae65798a3d81e22e9ec80e
1938 MESSAGE (length 256 bytes):
1939 15777532b0bdd0d1389f636c5f6b9ba7
1940 34c90af572877e2d272dd078aa1e567c
1941 fa80e12928bb542330e8409f31745041
1942 07ecd5efac61ae7504dabe2a602ede89
1943 e5cca6257a7c77e27a702b3ae39fc769
1944 fc54f2395ae6a1178cab4738e543072f
1945 c1c177fe71e92e25bf03e4ecb72f47b6
1946 4d0465aaea4c7fad372536c8ba516a60
1947 39c3c2a39f0e4d832be432dfa9a706a6
1948 e5c7e19f397964ca4258002f7c0541b5
1949 90316dbc5622b6b2a6fe7a4abffd9610
1950 5eca76ea7b98816af0748c10df048ce0
1951 12d901015a51f189f3888145c03650aa
1952 23ce894c3bd889e030d565071c59f409
1953 a9981b51878fd6fc110624dcbcde0bf7
1954 a69ccce38fabdf86f3bef6044819de11
1962Josefsson & Liusvaara Informational [Page 35]
1964RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
1968 c650ddbb0601c19ca11439e1640dd931
1969 f43c518ea5bea70d3dcde5f4191fe53f
1970 00cf966546b72bcc7d58be2b9badef28
1971 743954e3a44a23f880e8d4f1cfce2d7a
1972 61452d26da05896f0a50da66a239a8a1
1973 88b6d825b3305ad77b73fbac0836ecc6
1974 0987fd08527c1a8e80d5823e65cafe2a
1983 872d093780f5d3730df7c212664b37b8
1984 a0f24f56810daa8382cd4fa3f77634ec
1985 44dc54f1c2ed9bea86fafb7632d8be19
1989 a81b2e8a70a5ac94ffdbcc9badfc3feb
1990 0801f258578bb114ad44ece1ec0e799d
1991 a08effb81c5d685c0c56f64eecaef8cd
1994 MESSAGE (length 1023 bytes):
1995 6ddf802e1aae4986935f7f981ba3f035
1996 1d6273c0a0c22c9c0e8339168e675412
1997 a3debfaf435ed651558007db4384b650
1998 fcc07e3b586a27a4f7a00ac8a6fec2cd
1999 86ae4bf1570c41e6a40c931db27b2faa
2000 15a8cedd52cff7362c4e6e23daec0fbc
2001 3a79b6806e316efcc7b68119bf46bc76
2002 a26067a53f296dafdbdc11c77f7777e9
2003 72660cf4b6a9b369a6665f02e0cc9b6e
2004 dfad136b4fabe723d2813db3136cfde9
2005 b6d044322fee2947952e031b73ab5c60
2006 3349b307bdc27bc6cb8b8bbd7bd32321
2007 9b8033a581b59eadebb09b3c4f3d2277
2008 d4f0343624acc817804728b25ab79717
2009 2b4c5c21a22f9c7839d64300232eb66e
2010 53f31c723fa37fe387c7d3e50bdf9813
2011 a30e5bb12cf4cd930c40cfb4e1fc6225
2012 92a49588794494d56d24ea4b40c89fc0
2013 596cc9ebb961c8cb10adde976a5d602b
2014 1c3f85b9b9a001ed3c6a4d3b1437f520
2018Josefsson & Liusvaara Informational [Page 36]
2020RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
2023 96cd1956d042a597d561a596ecd3d173
2024 5a8d570ea0ec27225a2c4aaff26306d1
2025 526c1af3ca6d9cf5a2c98f47e1c46db9
2026 a33234cfd4d81f2c98538a09ebe76998
2027 d0d8fd25997c7d255c6d66ece6fa56f1
2028 1144950f027795e653008f4bd7ca2dee
2029 85d8e90f3dc315130ce2a00375a318c7
2030 c3d97be2c8ce5b6db41a6254ff264fa6
2031 155baee3b0773c0f497c573f19bb4f42
2032 40281f0b1f4f7be857a4e59d416c06b4
2033 c50fa09e1810ddc6b1467baeac5a3668
2034 d11b6ecaa901440016f389f80acc4db9
2035 77025e7f5924388c7e340a732e554440
2036 e76570f8dd71b7d640b3450d1fd5f041
2037 0a18f9a3494f707c717b79b4bf75c984
2038 00b096b21653b5d217cf3565c9597456
2039 f70703497a078763829bc01bb1cbc8fa
2040 04eadc9a6e3f6699587a9e75c94e5bab
2041 0036e0b2e711392cff0047d0d6b05bd2
2042 a588bc109718954259f1d86678a579a3
2043 120f19cfb2963f177aeb70f2d4844826
2044 262e51b80271272068ef5b3856fa8535
2045 aa2a88b2d41f2a0e2fda7624c2850272
2046 ac4a2f561f8f2f7a318bfd5caf969614
2047 9e4ac824ad3460538fdc25421beec2cc
2048 6818162d06bbed0c40a387192349db67
2049 a118bada6cd5ab0140ee273204f628aa
2050 d1c135f770279a651e24d8c14d75a605
2051 9d76b96a6fd857def5e0b354b27ab937
2052 a5815d16b5fae407ff18222c6d1ed263
2053 be68c95f32d908bd895cd76207ae7264
2054 87567f9a67dad79abec316f683b17f2d
2055 02bf07e0ac8b5bc6162cf94697b3c27c
2056 d1fea49b27f23ba2901871962506520c
2057 392da8b6ad0d99f7013fbc06c2c17a56
2058 9500c8a7696481c1cd33e9b14e40b82e
2059 79a5f5db82571ba97bae3ad3e0479515
2060 bb0e2b0f3bfcd1fd33034efc6245eddd
2061 7ee2086ddae2600d8ca73e214e8c2b0b
2062 db2b047c6a464a562ed77b73d2d841c4
2063 b34973551257713b753632efba348169
2064 abc90a68f42611a40126d7cb21b58695
2065 568186f7e569d2ff0f9e745d0487dd2e
2066 b997cafc5abf9dd102e62ff66cba87
2074Josefsson & Liusvaara Informational [Page 37]
2076RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
2080 e301345a41a39a4d72fff8df69c98075
2081 a0cc082b802fc9b2b6bc503f926b65bd
2082 df7f4c8f1cb49f6396afc8a70abe6d8a
2083 ef0db478d4c6b2970076c6a0484fe76d
2084 76b3a97625d79f1ce240e7c576750d29
2085 5528286f719b413de9ada3e8eb78ed57
2086 3603ce30d8bb761785dc30dbc320869e
20907.5. Test Vectors for Ed448ph
2098 833fe62409237b9d62ec77587520911e
2099 9a759cec1d19755b7da901b96dca3d42
2100 ef7822e0d5104127dc05d6dbefde69e3
2104 259b71c19f83ef77a7abd26524cbdb31
2105 61b590a48f7d17de3ee0ba9c52beb743
2106 c09428a131d6b1b57303d90d8132c276
2109 MESSAGE (length 3 bytes):
2113 822f6901f7480f3d5f562c592994d969
2114 3602875614483256505600bbc281ae38
2115 1f54d6bce2ea911574932f52a4e6cadd
2116 78769375ec3ffd1b801a0d9b3f4030cd
2117 433964b6457ea39476511214f97469b5
2118 7dd32dbc560a9a94d00bff07620464a3
2119 ad203df7dc7ce360c3cd3696d9d9fab9
2130Josefsson & Liusvaara Informational [Page 38]
2132RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
2135 -----TEST abc (with context)
2141 833fe62409237b9d62ec77587520911e
2142 9a759cec1d19755b7da901b96dca3d42
2143 ef7822e0d5104127dc05d6dbefde69e3
2147 259b71c19f83ef77a7abd26524cbdb31
2148 61b590a48f7d17de3ee0ba9c52beb743
2149 c09428a131d6b1b57303d90d8132c276
2152 MESSAGE (length 3 bytes):
2159 c32299d46ec8ff02b54540982814dce9
2160 a05812f81962b649d528095916a2aa48
2161 1065b1580423ef927ecf0af5888f90da
2162 0f6a9a85ad5dc3f280d91224ba9911a3
2163 653d00e484e2ce232521481c8658df30
2164 4bb7745a73514cdb9bf3e15784ab7128
2165 4f8d0704a608c54a6b62d97beb511d13
2186Josefsson & Liusvaara Informational [Page 39]
2188RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
21918. Security Considerations
21938.1. Side-Channel Leaks
2195 For implementations performing signatures, secrecy of the private key
2196 is fundamental. It is possible to protect against some side-channel
2197 attacks by ensuring that the implementation executes exactly the same
2198 sequence of instructions and performs exactly the same memory
2199 accesses, for any value of the private key.
2201 To make an implementation side-channel silent in this way, the modulo
2202 p arithmetic must not use any data-dependent branches, e.g., related
2203 to carry propagation. Side-channel silent point addition is
2204 straightforward, thanks to the unified formulas.
2206 Scalar multiplication, multiplying a point by an integer, needs some
2207 additional effort to implement in a side-channel silent manner. One
2208 simple approach is to implement a side-channel silent conditional
2209 assignment, and use it together with the binary algorithm to examine
2210 one bit of the integer at a time.
2212 Compared to other signature schemes, avoiding data-dependent branches
2213 is easier due to side-channel silent modulo p arithmetic being easier
2214 (with recommended curves) and having complete addition formulas
2215 instead of having a number of special cases.
2217 Note that the example implementations in this document do not attempt
2218 to be side-channel silent.
22208.2. Randomness Considerations
2222 EdDSA signatures are deterministic. This protects against attacks
2223 arising from signing with bad randomness; the effects of which can,
2224 depending on the algorithm, range up to full private key compromise.
2225 It can be surprisingly hard to ensure good-quality random numbers,
2226 and there have been numerous security failures relating to this.
2228 Obviously, private key generation requires randomness, but due to the
2229 fact that the private key is hashed before use, a few missing bits of
2230 entropy doesn't constitute a disaster.
2232 The basic signature verification is also deterministic. However,
2233 some speedups by verifying multiple signatures at once do require
2242Josefsson & Liusvaara Informational [Page 40]
2244RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
2249 Contexts can be used to separate uses of the protocol between
2250 different protocols (which is very hard to reliably do otherwise) and
2251 between different uses within the same protocol. However, the
2252 following SHOULD be kept in mind when using this facility:
2254 The context SHOULD be a constant string specified by the protocol
2255 using it. It SHOULD NOT incorporate variable elements from the
2258 Contexts SHOULD NOT be used opportunistically, as that kind of use
2259 is very error prone. If contexts are used, one SHOULD require all
2260 signature schemes available for use in that purpose support
2263 Contexts are an extra input, which percolate out of APIs; as such,
2264 even if the signature scheme supports contexts, those may not be
2265 available for use. This problem is compounded by the fact that
2266 many times the application is not invoking the signing and
2267 verification functions directly but via some other protocol.
22698.4. Signature Malleability
2271 Some systems assume signatures are not malleable: that is, given a
2272 valid signature for some message under some key, the attacker can't
2273 produce another valid signature for the same message and key.
2275 Ed25519 and Ed448 signatures are not malleable due to the
2276 verification check that decoded S is smaller than l. Without this
2277 check, one can add a multiple of l into a scalar part and still pass
2278 signature verification, resulting in malleable signatures.
22808.5. Choice of Signature Primitive
2282 Ed25519 and Ed25519ph have a nominal strength of 128 bits, whereas
2283 Ed448 and Ed448ph have the strength of 224. While the lower strength
2284 is sufficient for the foreseeable future, the higher level brings
2285 some defense against possible future cryptographic advances. Both
2286 are demolished by quantum computers just about the same.
2288 The Ed25519ph and Ed448ph variants are prehashed. This is mainly
2289 useful for interoperation with legacy APIs, since in most of the
2290 cases, either the amount of data signed is not large or the protocol
2291 is in the position to do digesting in ways better than just
2292 prehashing (e.g., tree hashing or splitting the data). The
2298Josefsson & Liusvaara Informational [Page 41]
2300RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
2303 prehashing also makes the functions greatly more vulnerable to
2304 weaknesses in hash functions used. These variants SHOULD NOT be
2307 Ed25519ctx and Ed448 have contexts. However, this is balanced by the
2308 problems noted in Section 8.3 about contexts.
2310 On the implementation front, Ed25519 is widely implemented and has
2311 many high-quality implementations. The others have much worse
2314 In summary, if a high 128-bit security level is enough, use of
2315 Ed25519 is RECOMMENDED; otherwise, Ed448 is RECOMMENDED.
23178.6. Mixing Different Prehashes
2319 The schemes described in this document are designed to be resistant
2320 to mixing prehashes. That is, it is infeasible to find a message
2321 that verifies using the same signature under another scheme, even if
2322 the original signed message was chosen. Thus, one can use the same
2323 key pair for Ed25519, Ed25519ctx, and Ed25519ph and correspondingly
2324 with Ed448 and Ed448ph.
2326 The "SigEd25519 no Ed25519 collisions" constant is chosen to be a
2327 textual string such that it does not decode as a point. Because the
2328 inner hash input in the Ed25519 signature always starts with a valid
2329 point, there is no way trivial collision can be constructed. In the
2330 case of seed hash, trivial collisions are so unlikely, even with an
2331 attacker choosing all inputs, that it is much more probable that
2332 something else goes catastrophically wrong.
23348.7. Signing Large Amounts of Data at Once
2336 Avoid signing large amounts of data at once (where "large" depends on
2337 the expected verifier). In particular, unless the underlying
2338 protocol does not require it, the receiver MUST buffer the entire
2339 message (or enough information to reconstruct it, e.g., compressed or
2340 encrypted version) to be verified.
2342 This is needed because most of the time, it is unsafe to process
2343 unverified data, and verifying the signature makes a pass through the
2344 whole message, causing ultimately at least two passes through.
2346 As an API consideration, this means that any Initialize Update
2347 Finalize (IFU) verification interface is prone to misuse.
2354Josefsson & Liusvaara Informational [Page 42]
2356RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
2359 It is a bad idea to modify Ed25519 or Ed448 signing to be able to
2360 create valid Ed25519/Ed448 signatures using an IUF interface with
2361 only constant buffering. Pretty much any error in such would cause
2362 catastrophic security failure.
23648.8. Multiplication by Cofactor in Verification
2366 The given verification formulas for both Ed25519 and Ed448 multiply
2367 points by the cofactor. While this is not strictly necessary for
2368 security (in fact, any signature that meets the non-multiplied
2369 equation will satisfy the multiplied one), in some applications it is
2370 undesirable for implementations to disagree about the exact set of
2371 valid signatures. Such disagreements could open up, e.g.,
2372 fingerprinting attacks.
23748.9. Use of SHAKE256 as a Hash Function
2376 Ed448 uses SHAKE256 as a hash function, even if SHAKE256 is
2377 specifically defined not to be a hash function.
2379 The first potentially troublesome property is that shorter outputs
2380 are prefixes of longer ones. This is acceptable because output
2383 The second potentially troublesome property is failing to meet
2384 standard hash security notions (especially with preimages). However,
2385 the estimated 256-bit security level against collisions and preimages
2386 is sufficient to pair with a 224-bit level elliptic curve.
23909.1. Normative References
2392 [FIPS202] National Institute of Standards and Technology, "SHA-3
2393 Standard: Permutation-Based Hash and Extendable-Output
2394 Functions", FIPS PUB 202, August 2015,
2395 <http://dx.doi.org/10.6028/NIST.FIPS.202>.
2397 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
2398 Requirement Levels", BCP 14, RFC 2119, DOI
2399 10.17487/RFC2119, March 1997,
2400 <http://www.rfc-editor.org/info/rfc2119>.
2402 [RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms
2403 (SHA and SHA-based HMAC and HKDF)", RFC 6234,
2404 DOI 10.17487/RFC6234, May 2011,
2405 <http://www.rfc-editor.org/info/rfc6234>.
2410Josefsson & Liusvaara Informational [Page 43]
2412RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
2415 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves
2416 for Security", RFC 7748, DOI 10.17487/RFC7748, January
2417 2016, <http://www.rfc-editor.org/info/rfc7748>.
24199.2. Informative References
2422 Bernstein, D., "Curve25519: new Diffie-Hellman speed
2423 records", DOI 10.1007/11745853_14, February 2006,
2424 <http://cr.yp.to/ecdh.html>.
2426 [ED25519-LIBGCRYPT-TEST-VECTORS]
2427 Koch, W., "Ed25519 Libgcrypt test vectors", July 2014,
2428 <http://git.gnupg.org/cgi-bin/
2429 gitweb.cgi?p=libgcrypt.git;a=blob;f=tests/t-ed25519.inp;
2430 h=e13566f826321eece65e02c593bc7d885b3dbe23;hb=refs/
2433 [ED25519-TEST-VECTORS]
2434 Bernstein, D., Duif, N., Lange, T., Schwabe, P., and B.
2435 Yang, "Ed25519 test vectors", July 2011,
2436 <http://ed25519.cr.yp.to/python/sign.input>.
2438 [ED448] Hamburg, M., "Ed448-Goldilocks, a new elliptic curve",
2439 June 2015, <http://eprint.iacr.org/2015/625>.
2441 [EDDSA] Bernstein, D., Duif, N., Lange, T., Schwabe, P., and B.
2442 Yang, "High-speed high-security signatures",
2443 DOI 10.1007/978-3-642-23951-9_9, September 2011,
2444 <http://ed25519.cr.yp.to/ed25519-20110926.pdf>.
2446 [EDDSA2] Bernstein, D., Josefsson, S., Lange, T., Schwabe, P., and
2447 B. Yang, "EdDSA for more curves", July 2015,
2448 <http://ed25519.cr.yp.to/eddsa-20150704.pdf>.
2451 Hisil, H., Wong, K., Carter, G., and E. Dawson, "Twisted
2452 Edwards Curves Revisited",
2453 DOI 10.1007/978-3-540-89255-7_20, December 2008,
2454 <http://eprint.iacr.org/2008/522>.
2456 [EFD-ADD] Bernstein, D. and T. Lange, "Projective coordinates for
2457 Edwards curves", The 'add-2007-bl' addition formulas,
2458 2007, <http://www.hyperelliptic.org/EFD/g1p/
2459 auto-edwards-projective.html#addition-add-2007-bl>.
2466Josefsson & Liusvaara Informational [Page 44]
2468RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
2471 [EFD-DBL] Bernstein, D. and T. Lange, "Projective coordinates for
2472 Edwards curves", The 'dbl-2007-bl' doubling formulas,
2473 2007, <http://www.hyperelliptic.org/EFD/g1p/
2474 auto-edwards-projective.html#doubling-dbl-2007-bl>.
2477 Hisil, H., Wong, K., Carter, G., and E. Dawson, "Extended
2478 coordinates with a=-1 for twisted Edwards curves", The
2479 'add-2008-hwcd-3' addition formulas, December 2008,
2480 <http://www.hyperelliptic.org/EFD/g1p/
2481 auto-twisted-extended-1.html#addition-add-2008-hwcd-3>.
2484 Hisil, H., Wong, K., Carter, G., and E. Dawson, "Extended
2485 coordinates with a=-1 for twisted Edwards curves", The
2486 'dbl-2008-hwcd' doubling formulas, December 2008,
2487 <http://www.hyperelliptic.org/EFD/g1p/
2488 auto-twisted-extended-1.html#doubling-dbl-2008-hwcd>.
2491 Bernstein, D. and T. Lange, "Faster addition and doubling
2492 on elliptic curves", DOI 10.1007/978-3-540-76900-2_3,
2493 July 2007, <http://eprint.iacr.org/2007/286>.
2495 [RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker,
2496 "Randomness Requirements for Security", BCP 106, RFC 4086,
2497 DOI 10.17487/RFC4086, June 2005,
2498 <http://www.rfc-editor.org/info/rfc4086>.
2522Josefsson & Liusvaara Informational [Page 45]
2524RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
2527Appendix A. Ed25519/Ed448 Python Library
2529 Below is an example implementation of Ed25519/Ed448 written in
2530 Python; version 3.2 or higher is required.
2532 Note: This code is not intended for production. Although it should
2533 produce correct results for every input, it is slow and makes no
2534 attempt to avoid side-channel attacks.
2539#Compute candidate square root of x modulo p, with p = 3 (mod 4).
2540def sqrt4k3(x,p): return pow(x,(p + 1)//4,p)
2542#Compute candidate square root of x modulo p, with p = 5 (mod 8).
2544 y = pow(x,(p+3)//8,p)
2545 #If the square root exists, it is either y or y*2^(p-1)/4.
2546 if (y * y) % p == x % p: return y
2548 z = pow(2,(p - 1)//4,p)
2551#Decode a hexadecimal string representation of the integer.
2552def hexi(s): return int.from_bytes(bytes.fromhex(s),byteorder="big")
2554#Rotate a word x by b places to the left.
2555def rol(x,b): return ((x << b) | (x >> (64 - b))) & (2**64-1)
2558def from_le(s): return int.from_bytes(s, byteorder="little")
2560#Do the SHA-3 state transform on state s.
2561def sha3_transform(s):
2562 ROTATIONS = [0,1,62,28,27,36,44,6,55,20,3,10,43,25,39,41,45,15,\
2564 PERMUTATION = [1,6,9,22,14,20,2,12,13,19,23,15,4,24,21,8,16,5,3,\
2566 RC = [0x0000000000000001,0x0000000000008082,0x800000000000808a,\
2567 0x8000000080008000,0x000000000000808b,0x0000000080000001,\
2568 0x8000000080008081,0x8000000000008009,0x000000000000008a,\
2569 0x0000000000000088,0x0000000080008009,0x000000008000000a,\
2570 0x000000008000808b,0x800000000000008b,0x8000000000008089,\
2571 0x8000000000008003,0x8000000000008002,0x8000000000000080,\
2572 0x000000000000800a,0x800000008000000a,0x8000000080008081,\
2573 0x8000000000008080,0x0000000080000001,0x8000000080008008]
2578Josefsson & Liusvaara Informational [Page 46]
2580RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
2583 for rnd in range(0,24):
2584 #AddColumnParity (Theta)
2587 for i in range(0,25): c[i%5]^=s[i]
2588 for i in range(0,5): d[i]=c[(i+4)%5]^rol(c[(i+1)%5],1)
2589 for i in range(0,25): s[i]^=d[i%5]
2591 for i in range(0,25): s[i]=rol(s[i],ROTATIONS[i])
2593 t = s[PERMUTATION[0]]
2594 for i in range(0,len(PERMUTATION)-1):
2595 s[PERMUTATION[i]]=s[PERMUTATION[i+1]]
2596 s[PERMUTATION[-1]]=t;
2597 #NonlinearMixRows (Chi)
2598 for i in range(0,25,5):
2599 t=[s[i],s[i+1],s[i+2],s[i+3],s[i+4],s[i],s[i+1]]
2600 for j in range(0,5): s[i+j]=t[j]^((~t[j+1])&(t[j+2]))
2601 #AddRoundConstant (Iota)
2604#Reinterpret octet array b to word array and XOR it to state s.
2605def reinterpret_to_words_and_xor(s,b):
2606 for j in range(0,len(b)//8):
2607 s[j]^=from_le(b[8*j:][:8])
2609#Reinterpret word array w to octet array and return it.
2610def reinterpret_to_octets(w):
2612 for j in range(0,len(w)):
2613 mp+=w[j].to_bytes(8,byteorder="little")
2634Josefsson & Liusvaara Informational [Page 47]
2636RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
2639#(semi-)generic SHA-3 implementation
2640def sha3_raw(msg,r_w,o_p,e_b):
2643 #Handle whole blocks.
2645 blocks=len(msg)//r_b
2646 for i in range(0,blocks):
2647 reinterpret_to_words_and_xor(s,msg[idx:][:r_b])
2650 #Handle last block padding.
2651 m=bytearray(msg[idx:])
2653 while len(m) < r_b: m.append(0)
2655 #Handle padded last block.
2656 reinterpret_to_words_and_xor(s,m)
2661 out+=reinterpret_to_octets(s[:r_w])
2665#Implementation of SHAKE256 functions.
2666def shake256(msg,olen): return sha3_raw(msg,17,31,olen)
2690Josefsson & Liusvaara Informational [Page 48]
2692RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
2695#A (prime) field element.
2697 #Construct number x (mod p).
2698 def __init__(self,x,p):
2701 #Check that fields of self and y are the same.
2702 def __check_fields(self,y):
2703 if type(y) is not Field or self.__p!=y.__p:
2704 raise ValueError("Fields don't match")
2705 #Field addition. The fields must match.
2706 def __add__(self,y):
2707 self.__check_fields(y)
2708 return Field(self.__x+y.__x,self.__p)
2709 #Field subtraction. The fields must match.
2710 def __sub__(self,y):
2711 self.__check_fields(y)
2712 return Field(self.__p+self.__x-y.__x,self.__p)
2715 return Field(self.__p-self.__x,self.__p)
2716 #Field multiplication. The fields must match.
2717 def __mul__(self,y):
2718 self.__check_fields(y)
2719 return Field(self.__x*y.__x,self.__p)
2720 #Field division. The fields must match.
2721 def __truediv__(self,y):
2723 #Field inverse (inverse of 0 is 0).
2725 return Field(pow(self.__x,self.__p-2,self.__p),self.__p)
2726 #Field square root. Returns none if square root does not exist.
2727 #Note: not presently implemented for p mod 8 = 1 case.
2729 #Compute candidate square root.
2730 if self.__p%4==3: y=sqrt4k3(self.__x,self.__p)
2731 elif self.__p%8==5: y=sqrt8k5(self.__x,self.__p)
2732 else: raise NotImplementedError("sqrt(_,8k+1)")
2733 _y=Field(y,self.__p);
2734 #Check square root candidate valid.
2735 return _y if _y*_y==self else None
2736 #Make the field element with the same field as this, but
2737 #with a different value.
2738 def make(self,ival): return Field(ival,self.__p)
2739 #Is the field element the additive identity?
2740 def iszero(self): return self.__x==0
2741 #Are field elements equal?
2742 def __eq__(self,y): return self.__x==y.__x and self.__p==y.__p
2746Josefsson & Liusvaara Informational [Page 49]
2748RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
2751 #Are field elements not equal?
2752 def __ne__(self,y): return not (self==y)
2753 #Serialize number to b-1 bits.
2754 def tobytes(self,b):
2755 return self.__x.to_bytes(b//8,byteorder="little")
2756 #Unserialize number from bits.
2757 def frombytes(self,x,b):
2758 rv=from_le(x)%(2**(b-1))
2759 return Field(rv,self.__p) if rv<self.__p else None
2760 #Compute sign of number, 0 or 1. The sign function
2761 #has the following property:
2762 #sign(x) = 1 - sign(-x) if x != 0.
2763 def sign(self): return self.__x%2
2765#A point on (twisted) Edwards curve.
2771 def initpoint(self, x, y):
2774 self.z=self.base_field.make(1)
2775 def decode_base(self,s,b):
2776 #Check that point encoding is the correct length.
2777 if len(s)!=b//8: return (None,None)
2779 xs=s[(b-1)//8]>>((b-1)&7)
2780 #Decode y. If this fails, fail.
2781 y = self.base_field.frombytes(s,b)
2782 if y is None: return (None,None)
2783 #Try to recover x. If it does not exist, or if zero and xs
2785 x=self.solve_x2(y).sqrt()
2786 if x is None or (x.iszero() and xs!=x.sign()):
2788 #If sign of x isn't correct, flip it.
2789 if x.sign()!=xs: x=-x
2790 # Return the constructed point.
2792 def encode_base(self,b):
2793 xp,yp=self.x/self.z,self.y/self.z
2795 s=bytearray(yp.tobytes(b))
2796 #Add sign bit of x to encoding.
2797 if xp.sign()!=0: s[(b-1)//8]|=1<<(b-1)%8
2802Josefsson & Liusvaara Informational [Page 50]
2804RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
2807 def __mul__(self,x):
2816 #Check that two points are equal.
2818 #Need to check x1/z1 == x2/z2 and similarly for y, so cross
2819 #multiply to eliminate divisions.
2824 return xn1==xn2 and yn1==yn2
2825 #Check if two points are not equal.
2826 def __ne__(self,y): return not (self==y)
2828#A point on Edwards25519.
2829class Edwards25519Point(EdwardsPoint):
2830 #Create a new point on the curve.
2831 base_field=Field(1,2**255-19)
2832 d=-base_field.make(121665)/base_field.make(121666)
2833 f0=base_field.make(0)
2834 f1=base_field.make(1)
2835 xb=base_field.make(hexi("216936D3CD6E53FEC0A4E231FDD6DC5C692CC76"+\
2836 "09525A7B2C9562D608F25D51A"))
2837 yb=base_field.make(hexi("666666666666666666666666666666666666666"+\
2838 "6666666666666666666666658"))
2839 #The standard base point.
2842 return Edwards25519Point(Edwards25519Point.xb,\
2843 Edwards25519Point.yb)
2844 def __init__(self,x,y):
2845 #Check the point is actually on the curve.
2846 if y*y-x*x!=self.f1+self.d*x*x*y*y:
2847 raise ValueError("Invalid point")
2848 self.initpoint(x, y)
2850 #Decode a point representation.
2852 x,y=self.decode_base(s,256);
2853 return Edwards25519Point(x, y) if x is not None else None
2858Josefsson & Liusvaara Informational [Page 51]
2860RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
2863 #Encode a point representation.
2865 return self.encode_base(256)
2866 #Construct a neutral point on this curve.
2867 def zero_elem(self):
2868 return Edwards25519Point(self.f0,self.f1)
2870 def solve_x2(self,y):
2871 return ((y*y-self.f1)/(self.d*y*y+self.f1))
2873 def __add__(self,y):
2874 #The formulas are from EFD.
2875 tmp=self.zero_elem()
2877 A=(self.y-self.x)*(y.y-y.x)
2878 B=(self.y+self.x)*(y.y+y.x)
2879 C=(self.d+self.d)*self.t*y.t
2883 tmp.x,tmp.y,tmp.z,tmp.t=E*F,G*H,F*G,E*H
2887 #The formulas are from EFD (with assumption a=-1 propagated).
2888 tmp=self.zero_elem()
2898 tmp.x,tmp.y,tmp.z,tmp.t=E*F,G*H,F*G,E*H
2900 #Order of basepoint.
2902 return hexi("1000000000000000000000000000000014def9dea2f79cd"+\
2903 "65812631a5cf5d3ed")
2904 #The logarithm of cofactor.
2905 def c(self): return 3
2906 #The highest set bit
2907 def n(self): return 254
2909 def b(self): return 256
2914Josefsson & Liusvaara Informational [Page 52]
2916RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
2919 #Validity check (for debugging)
2920 def is_valid_point(self):
2921 x,y,z,t=self.x,self.y,self.z,self.t
2926 rhs=z2*z2+self.d*x2*y2
2930#A point on Edwards448.
2931class Edwards448Point(EdwardsPoint):
2932 #Create a new point on the curve.
2933 base_field=Field(1,2**448-2**224-1)
2934 d=base_field.make(-39081)
2935 f0=base_field.make(0)
2936 f1=base_field.make(1)
2937 xb=base_field.make(hexi("4F1970C66BED0DED221D15A622BF36DA9E14657"+\
2938 "0470F1767EA6DE324A3D3A46412AE1AF72AB66511433B80E18B00938E26"+\
2940 yb=base_field.make(hexi("693F46716EB6BC248876203756C9C7624BEA737"+\
2941 "36CA3984087789C1E05A0C2D73AD3FF1CE67C39C4FDBD132C4ED7C8AD98"+\
2943 #The standard base point.
2946 return Edwards448Point(Edwards448Point.xb,Edwards448Point.yb)
2947 def __init__(self,x,y):
2948 #Check that the point is actually on the curve.
2949 if y*y+x*x!=self.f1+self.d*x*x*y*y:
2950 raise ValueError("Invalid point")
2951 self.initpoint(x, y)
2952 #Decode a point representation.
2954 x,y=self.decode_base(s,456);
2955 return Edwards448Point(x, y) if x is not None else None
2956 #Encode a point representation.
2958 return self.encode_base(456)
2959 #Construct a neutral point on this curve.
2960 def zero_elem(self):
2961 return Edwards448Point(self.f0,self.f1)
2963 def solve_x2(self,y):
2964 return ((y*y-self.f1)/(self.d*y*y-self.f1))
2970Josefsson & Liusvaara Informational [Page 53]
2972RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
2976 def __add__(self,y):
2977 #The formulas are from EFD.
2978 tmp=self.zero_elem()
2979 xcp,ycp,zcp=self.x*y.x,self.y*y.y,self.z*y.z
2983 tmp.x=zcp*F*((self.x+self.y)*(y.x+y.y)-xcp-ycp)
2984 tmp.y,tmp.z=zcp*G*(ycp-xcp),F*G
2988 #The formulas are from EFD.
2989 tmp=self.zero_elem()
2990 x1s,y1s,z1s=self.x*self.x,self.y*self.y,self.z*self.z
2994 tmp.x,tmp.y,tmp.z=(xys*xys-x1s-y1s)*J,F*(x1s-y1s),F*J
2996 #Order of basepoint.
2998 return hexi("3ffffffffffffffffffffffffffffffffffffffffffffff"+\
2999 "fffffffff7cca23e9c44edb49aed63690216cc2728dc58f552378c2"+\
3001 #The logarithm of cofactor.
3002 def c(self): return 2
3003 #The highest set bit.
3004 def n(self): return 447
3006 def b(self): return 456
3007 #Validity check (for debugging).
3008 def is_valid_point(self):
3009 x,y,z=self.x,self.y,self.z
3014 rhs=z2*z2+self.d*x2*y2
3026Josefsson & Liusvaara Informational [Page 54]
3028RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
3032def curve_self_check(point):
3039 for i in range(0,point.b()):
3045 assert q.encode() == point.encode()
3046 assert q.encode() != p.encode()
3047 assert q.encode() != z.encode()
3050def self_check_curves():
3051 curve_self_check(Edwards25519Point.stdbase())
3052 curve_self_check(Edwards448Point.stdbase())
3055#Limitation: only b mod 8 = 0 is handled.
3057 #Create a new object.
3058 def __init__(self,properties):
3059 self.B=properties["B"]
3060 self.H=properties["H"]
3065 #Clamp a private scalar.
3066 def __clamp(self,a):
3068 for i in range(0,self.c): _a[i//8]&=~(1<<(i%8))
3069 _a[self.n//8]|=1<<(self.n%8)
3070 for i in range(self.n+1,self.b): _a[i//8]&=~(1<<(i%8))
3072 #Generate a key. If privkey is None, a random one is generated.
3073 #In any case, the (privkey, pubkey) pair is returned.
3074 def keygen(self,privkey):
3075 #If no private key data is given, generate random.
3076 if privkey is None: privkey=os.urandom(self.b//8)
3082Josefsson & Liusvaara Informational [Page 55]
3084RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
3088 khash=self.H(privkey,None,None)
3089 a=from_le(self.__clamp(khash[:self.b//8]))
3090 #Return the key pair (public key is A=Enc(aB).
3091 return privkey,(self.B*a).encode()
3092 #Sign with key pair.
3093 def sign(self,privkey,pubkey,msg,ctx,hflag):
3095 khash=self.H(privkey,None,None)
3096 a=from_le(self.__clamp(khash[:self.b//8]))
3097 seed=khash[self.b//8:]
3098 #Calculate r and R (R only used in encoded form).
3099 r=from_le(self.H(seed+msg,ctx,hflag))%self.l
3100 R=(self.B*r).encode()
3102 h=from_le(self.H(R+pubkey+msg,ctx,hflag))%self.l
3104 S=((r+h*a)%self.l).to_bytes(self.b//8,byteorder="little")
3105 #The final signature is a concatenation of R and S.
3107 #Verify signature with public key.
3108 def verify(self,pubkey,msg,sig,ctx,hflag):
3109 #Sanity-check sizes.
3110 if len(sig)!=self.b//4: return False
3111 if len(pubkey)!=self.b//8: return False
3112 #Split signature into R and S, and parse.
3113 Rraw,Sraw=sig[:self.b//8],sig[self.b//8:]
3114 R,S=self.B.decode(Rraw),from_le(Sraw)
3116 A=self.B.decode(pubkey)
3117 #Check parse results.
3118 if (R is None) or (A is None) or S>=self.l: return False
3120 h=from_le(self.H(Rraw+pubkey+msg,ctx,hflag))%self.l
3121 #Calculate left and right sides of check eq.
3124 for i in range(0, self.c):
3130def Ed25519_inthash(data,ctx,hflag):
3131 if (ctx is not None and len(ctx) > 0) or hflag:
3132 raise ValueError("Contexts/hashes not supported")
3133 return hashlib.sha512(data).digest()
3138Josefsson & Liusvaara Informational [Page 56]
3140RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
3143#The base PureEdDSA schemes.
3144pEd25519=PureEdDSA({\
3145 "B":Edwards25519Point.stdbase(),\
3146 "H":Ed25519_inthash\
3149def Ed25519ctx_inthash(data,ctx,hflag):
3151 PREFIX=b"SigEd25519 no Ed25519 collisions"
3153 if len(ctx) > 255: raise ValueError("Context too big")
3154 dompfx=PREFIX+bytes([1 if hflag else 0,len(ctx)])+ctx
3155 return hashlib.sha512(dompfx+data).digest()
3157pEd25519ctx=PureEdDSA({\
3158 "B":Edwards25519Point.stdbase(),\
3159 "H":Ed25519ctx_inthash\
3162def Ed448_inthash(data,ctx,hflag):
3165 if len(ctx) > 255: raise ValueError("Context too big")
3166 dompfx=b"SigEd448"+bytes([1 if hflag else 0,len(ctx)])+ctx
3167 return shake256(dompfx+data,114)
3169pEd448 = PureEdDSA({\
3170 "B":Edwards448Point.stdbase(),\
3176 #Create a new scheme object, with the specified PureEdDSA base
3177 #scheme and specified prehash.
3178 def __init__(self,pure_scheme,prehash):
3180 self.__pure=pure_scheme
3181 self.__prehash=prehash
3182 if self.__prehash is None:
3183 self.__prehash = lambda x,y:x
3184 self.__pflag = False
3185 # Generate a key. If privkey is none, it generates a random
3186 # privkey key, otherwise it uses a specified private key.
3187 # Returns pair (privkey, pubkey).
3188 def keygen(self,privkey): return self.__pure.keygen(privkey)
3194Josefsson & Liusvaara Informational [Page 57]
3196RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
3199 # Sign message msg using specified key pair.
3200 def sign(self,privkey,pubkey,msg,ctx=None):
3201 if ctx is None: ctx=b"";
3202 return self.__pure.sign(privkey,pubkey,self.__prehash(msg,ctx),\
3204 # Verify signature sig on message msg using public key pubkey.
3205 def verify(self,pubkey,msg,sig,ctx=None):
3206 if ctx is None: ctx=b"";
3207 return self.__pure.verify(pubkey,self.__prehash(msg,ctx),sig,\
3210def Ed448ph_prehash(data,ctx):
3211 return shake256(data,64)
3213#Our signature schemes.
3214Ed25519 = EdDSA(pEd25519,None)
3215Ed25519ctx = EdDSA(pEd25519ctx,None)
3216Ed25519ph = EdDSA(pEd25519ctx,lambda x,y:hashlib.sha512(x).digest())
3217Ed448 = EdDSA(pEd448,None)
3218Ed448ph = EdDSA(pEd448,Ed448ph_prehash)
3221 if name == "Ed25519": return Ed25519
3222 if name == "Ed25519ctx": return Ed25519ctx
3223 if name == "Ed25519ph": return Ed25519ph
3224 if name == "Ed448": return Ed448
3225 if name == "Ed448ph": return Ed448ph
3226 raise NotImplementedError("Algorithm not implemented")
3228Appendix B. Library Driver
3230 Below is a command-line tool that uses the library above to perform
3231 computations for interactive use or for self-checking.
3236from eddsa2 import Ed25519
3239def munge_string(s, pos, change):
3241 int.to_bytes(s[pos] ^ change, 1, "little") +
3250Josefsson & Liusvaara Informational [Page 58]
3252RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
3255# Read a file in the format of
3256# http://ed25519.cr.yp.to/python/sign.input
3259 line = sys.stdin.readline()
3264 fields = line.split(":")
3265 secret = (binascii.unhexlify(fields[0]))[:32]
3266 public = binascii.unhexlify(fields[1])
3267 msg = binascii.unhexlify(fields[2])
3268 signature = binascii.unhexlify(fields[3])[:64]
3270 privkey,pubkey = Ed25519.keygen(secret)
3271 assert public == pubkey
3272 assert signature == Ed25519.sign(privkey, pubkey, msg)
3273 assert Ed25519.verify(public, msg, signature)
3277 bad_msg = munge_string(msg, len(msg) // 3, 4)
3278 assert not Ed25519.verify(public,bad_msg,signature)
3279 assert not Ed25519.verify(public, msg, munge_string(signature,20,8))
3280 assert not Ed25519.verify(public,msg,munge_string(signature,40,16))
3306Josefsson & Liusvaara Informational [Page 59]
3308RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
3313 EdDSA and Ed25519 were initially described in a paper due to Daniel
3314 J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin
3315 Yang. The Ed448 curve is due to Mike Hamburg.
3317 An earlier draft version of this document was coauthored by Niels
3320 Feedback on this document was received from Werner Koch, Damien
3321 Miller, Bob Bradley, Franck Rondepierre, Alexey Melnikov, Kenny
3322 Paterson, and Robert Edmonds.
3324 The Ed25519 test vectors were double checked by Bob Bradley using
3325 three separate implementations (one based on TweetNaCl and two
3326 different implementations based on code from SUPERCOP).
3333 Email: simon@josefsson.org
3334 URI: http://josefsson.org/
3340 Email: ilariliusvaara@welho.com
3362Josefsson & Liusvaara Informational [Page 60]