-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathrfc8032.txt
More file actions
3363 lines (2285 loc) · 101 KB
/
rfc8032.txt
File metadata and controls
3363 lines (2285 loc) · 101 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
Internet Research Task Force (IRTF) S. Josefsson
Request for Comments: 8032 SJD AB
Category: Informational I. Liusvaara
ISSN: 2070-1721 Independent
January 2017
Edwards-Curve Digital Signature Algorithm (EdDSA)
Abstract
This document describes elliptic curve signature scheme Edwards-curve
Digital Signature Algorithm (EdDSA). The algorithm is instantiated
with recommended parameters for the edwards25519 and edwards448
curves. An example implementation and test vectors are provided.
Status of This Memo
This document is not an Internet Standards Track specification; it is
published for informational purposes.
This document is a product of the Internet Research Task Force
(IRTF). The IRTF publishes the results of Internet-related research
and development activities. These results might not be suitable for
deployment. This RFC represents the consensus of the Crypto Forum
Research Group of the Internet Research Task Force (IRTF). Documents
approved for publication by the IRSG are not a candidate for any
level of Internet Standard; see Section 2 of RFC 7841.
Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
http://www.rfc-editor.org/info/rfc8032.
Copyright Notice
Copyright (c) 2017 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.
Josefsson & Liusvaara Informational [Page 1]
RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Notation and Conventions . . . . . . . . . . . . . . . . . . 4
3. EdDSA Algorithm . . . . . . . . . . . . . . . . . . . . . . . 5
3.1. Encoding . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2. Keys . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3. Sign . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.4. Verify . . . . . . . . . . . . . . . . . . . . . . . . . 8
4. PureEdDSA, HashEdDSA, and Naming . . . . . . . . . . . . . . 8
5. EdDSA Instances . . . . . . . . . . . . . . . . . . . . . . . 9
5.1. Ed25519ph, Ed25519ctx, and Ed25519 . . . . . . . . . . . 9
5.1.1. Modular Arithmetic . . . . . . . . . . . . . . . . . 10
5.1.2. Encoding . . . . . . . . . . . . . . . . . . . . . . 10
5.1.3. Decoding . . . . . . . . . . . . . . . . . . . . . . 11
5.1.4. Point Addition . . . . . . . . . . . . . . . . . . . 11
5.1.5. Key Generation . . . . . . . . . . . . . . . . . . . 13
5.1.6. Sign . . . . . . . . . . . . . . . . . . . . . . . . 13
5.1.7. Verify . . . . . . . . . . . . . . . . . . . . . . . 14
5.2. Ed448ph and Ed448 . . . . . . . . . . . . . . . . . . . . 15
5.2.1. Modular Arithmetic . . . . . . . . . . . . . . . . . 16
5.2.2. Encoding . . . . . . . . . . . . . . . . . . . . . . 16
5.2.3. Decoding . . . . . . . . . . . . . . . . . . . . . . 16
5.2.4. Point Addition . . . . . . . . . . . . . . . . . . . 17
5.2.5. Key Generation . . . . . . . . . . . . . . . . . . . 18
5.2.6. Sign . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2.7. Verify . . . . . . . . . . . . . . . . . . . . . . . 19
6. Ed25519 Python Illustration . . . . . . . . . . . . . . . . . 20
7. Test Vectors . . . . . . . . . . . . . . . . . . . . . . . . 23
7.1. Test Vectors for Ed25519 . . . . . . . . . . . . . . . . 24
7.2. Test Vectors for Ed25519ctx . . . . . . . . . . . . . . . 27
7.3. Test Vectors for Ed25519ph . . . . . . . . . . . . . . . 30
7.4. Test Vectors for Ed448 . . . . . . . . . . . . . . . . . 30
7.5. Test Vectors for Ed448ph . . . . . . . . . . . . . . . . 38
8. Security Considerations . . . . . . . . . . . . . . . . . . . 40
8.1. Side-Channel Leaks . . . . . . . . . . . . . . . . . . . 40
8.2. Randomness Considerations . . . . . . . . . . . . . . . . 40
8.3. Use of Contexts . . . . . . . . . . . . . . . . . . . . . 41
8.4. Signature Malleability . . . . . . . . . . . . . . . . . 41
8.5. Choice of Signature Primitive . . . . . . . . . . . . . . 41
8.6. Mixing Different Prehashes . . . . . . . . . . . . . . . 42
8.7. Signing Large Amounts of Data at Once . . . . . . . . . . 42
8.8. Multiplication by Cofactor in Verification . . . . . . . 43
8.9. Use of SHAKE256 as a Hash Function . . . . . . . . . . . 43
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 43
9.1. Normative References . . . . . . . . . . . . . . . . . . 43
9.2. Informative References . . . . . . . . . . . . . . . . . 44
Josefsson & Liusvaara Informational [Page 2]
RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
Appendix A. Ed25519/Ed448 Python Library . . . . . . . . . . . . 46
Appendix B. Library Driver . . . . . . . . . . . . . . . . . . . 58
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 60
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 60
1. Introduction
The Edwards-curve Digital Signature Algorithm (EdDSA) is a variant of
Schnorr's signature system with (possibly twisted) Edwards curves.
EdDSA needs to be instantiated with certain parameters, and this
document describes some recommended variants.
To facilitate adoption of EdDSA in the Internet community, this
document describes the signature scheme in an implementation-oriented
way and provides sample code and test vectors.
The advantages with EdDSA are as follows:
1. EdDSA provides high performance on a variety of platforms;
2. The use of a unique random number for each signature is not
required;
3. It is more resilient to side-channel attacks;
4. EdDSA uses small public keys (32 or 57 bytes) and signatures (64
or 114 bytes) for Ed25519 and Ed448, respectively;
5. The formulas are "complete", 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; and
6. EdDSA provides collision resilience, meaning that hash-function
collisions do not break this system (only holds for PureEdDSA).
The original EdDSA paper [EDDSA] and the generalized version
described in "EdDSA for more curves" [EDDSA2] provide further
background. RFC 7748 [RFC7748] discusses specific curves, including
Curve25519 [CURVE25519] and Ed448-Goldilocks [ED448].
Ed25519 is intended to operate at around the 128-bit security level
and Ed448 at around the 224-bit security level. A sufficiently large
quantum computer would be able to break both. Reasonable projections
of the abilities of classical computers conclude that Ed25519 is
perfectly safe. Ed448 is provided for those applications with
relaxed performance requirements and where there is a desire to hedge
against analytical attacks on elliptic curves.
Josefsson & Liusvaara Informational [Page 3]
RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
2. Notation and Conventions
The following notation is used throughout the document:
p Denotes the prime number defining the underlying field
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]X X added to itself n times
h[i] The i'th octet of octet string
h_i The i'th bit of h
a || b (bit-)string a concatenated with (bit-)string b
a <= b a is less than or equal to b
a >= b a is greater than or equal to b
i+j Sum of i and j
i*j Multiplication of i and j
i-j Subtraction of j from i
i/j Division of i by j
i x j Cartesian product of i and j
(u,v) Elliptic curve point with x-coordinate u and
y-coordinate v
SHAKE256(x, y) The y first octets of SHAKE256 [FIPS202] output for
input x
OCTET(x) The octet with value x
OLEN(x) The number of octets in string x
Josefsson & Liusvaara Informational [Page 4]
RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
dom2(x, y) The blank octet string when signing or verifying
Ed25519. Otherwise, the octet string: "SigEd25519 no
Ed25519 collisions" || octet(x) || octet(OLEN(y)) ||
y, where x is in range 0-255 and y is an octet string
of at most 255 octets. "SigEd25519 no Ed25519
collisions" is in ASCII (32 octets).
dom4(x, y) The octet string "SigEd448" || octet(x) ||
octet(OLEN(y)) || y, where x is in range 0-255 and y
is an octet string of at most 255 octets. "SigEd448"
is in ASCII (8 octets).
Parentheses (i.e., '(' and ')') are used to group expressions, in
order to avoid having the description depend on a binding order
between operators.
Bit strings are converted to octet strings by taking bits from left
to right, packing those from the least significant bit of each octet
to the most significant bit, and moving to the next octet when each
octet fills up. The conversion from octet string to bit string is
the reverse of this process; for example, the 16-bit bit string
b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15
is converted into two octets x0 and x1 (in this order) as
x0 = b7*128+b6*64+b5*32+b4*16+b3*8+b2*4+b1*2+b0
x1 = b15*128+b14*64+b13*32+b12*16+b11*8+b10*4+b9*2+b8
Little-endian encoding into bits places bits from left to right and
from least significant to most significant. If combined with
bit-string-to-octet-string conversion defined above, this results in
little-endian encoding into octets (if length is not a multiple of 8,
the most significant bits of the last octet remain unused).
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119].
3. EdDSA Algorithm
EdDSA is a digital signature system with 11 parameters.
The generic EdDSA digital signature system with its 11 input
parameters is not intended to be implemented directly. Choosing
parameters is critical for secure and efficient operation. Instead,
you would implement a particular parameter choice for EdDSA (such as
Josefsson & Liusvaara Informational [Page 5]
RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
Ed25519 or Ed448), sometimes slightly generalized to achieve code
reuse to cover Ed25519 and Ed448.
Therefore, a precise explanation of the generic EdDSA is thus not
particularly useful for implementers. For background and
completeness, a succinct description of the generic EdDSA algorithm
is given here.
The definition of some parameters, such as n and c, may help to
explain some steps of the algorithm that are not intuitive.
This description closely follows [EDDSA2].
EdDSA has 11 parameters:
1. An odd prime power p. EdDSA uses an elliptic curve over the
finite field GF(p).
2. An integer b with 2^(b-1) > p. EdDSA public keys have exactly b
bits, and EdDSA signatures have exactly 2*b bits. b is
recommended to be a multiple of 8, so public key and signature
lengths are an integral number of octets.
3. A (b-1)-bit encoding of elements of the finite field GF(p).
4. A cryptographic hash function H producing 2*b-bit output.
Conservative hash functions (i.e., hash functions where it is
infeasible to create collisions) are recommended and do not have
much impact on the total cost of EdDSA.
5. An integer c that is 2 or 3. Secret EdDSA scalars are multiples
of 2^c. The integer c is the base-2 logarithm of the so-called
cofactor.
6. An integer n with c <= n < b. Secret EdDSA scalars have exactly
n + 1 bits, with the top bit (the 2^n position) always set and
the bottom c bits always cleared.
7. A non-square element d of GF(p). The usual recommendation is to
take it as the value nearest to zero that gives an acceptable
curve.
8. A non-zero square element a of GF(p). The usual recommendation
for best performance is a = -1 if p mod 4 = 1, and a = 1 if
p mod 4 = 3.
9. An element B != (0,1) of the set E = { (x,y) is a member of
GF(p) x GF(p) such that a * x^2 + y^2 = 1 + d * x^2 * y^2 }.
Josefsson & Liusvaara Informational [Page 6]
RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
10. An odd prime L such that [L]B = 0 and 2^c * L = #E. The number
#E (the number of points on the curve) is part of the standard
data provided for an elliptic curve E, or it can be computed as
cofactor * order.
11. A "prehash" function PH. PureEdDSA means EdDSA where PH is the
identity function, i.e., PH(M) = M. HashEdDSA means EdDSA where
PH generates a short output, no matter how long the message is;
for example, PH(M) = SHA-512(M).
Points on the curve form a group under addition, (x3, y3) = (x1, y1)
+ (x2, y2), with the formulas
x1 * y2 + x2 * y1 y1 * y2 - a * 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 many other curves used for cryptographic applications, these
formulas are "complete"; 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 complete, that use
homogeneous coordinates to avoid the expensive modulo p inversions.
See [Faster-ECC] and [Edwards-revisited].
3.1. Encoding
An integer 0 < S < L - 1 is encoded in little-endian form as a b-bit
string ENC(S).
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.
The encoding of GF(p) is used to define "negative" elements of GF(p):
specifically, x is negative if the (b-1)-bit encoding of x is
lexicographically larger than the (b-1)-bit encoding of -x.
3.2. Keys
An EdDSA private key is a b-bit string k. Let the hash H(k) =
(h_0, h_1, ..., h_(2b-1)) determine an integer s, which is 2^n plus
the sum of m = 2^i * h_i for all integer i, c <= i < n. Let s
determine the multiple A = [s]B. The EdDSA public key is ENC(A).
The bits h_b, ..., h_(2b-1) are used below during signing.
Josefsson & Liusvaara Informational [Page 7]
RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
3.3. Sign
The EdDSA signature of a message M under a private key k is defined
as the PureEdDSA signature of PH(M). In other words, EdDSA simply
uses PureEdDSA to sign PH(M).
The PureEdDSA signature of a message M under a private key k is the
2*b-bit string ENC(R) || ENC(S). R and S are derived as follows.
First define r = H(h_b || ... || h_(2b-1) || M) interpreting 2*b-bit
strings in little-endian form as integers in {0, 1, ..., 2^(2*b) -
1}. Let R = [r]B and S = (r + H(ENC(R) || ENC(A) || PH(M)) * s) mod
L. The s used here is from the previous section.
3.4. Verify
To verify a PureEdDSA 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 are elements 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 [2^c * S] B = 2^c * R + [2^c * h] A in E. The signature is
rejected if parsing fails (including S being out of range) or if the
group equation does not hold.
EdDSA verification for a message M is defined as PureEdDSA
verification for PH(M).
4. PureEdDSA, HashEdDSA, and Naming
One of the parameters of the EdDSA algorithm is the "prehash"
function. This may be the identity function, resulting in an
algorithm called PureEdDSA, or a collision-resistant hash function
such as SHA-512, resulting in an algorithm called HashEdDSA.
Choosing which variant to use depends on which property is deemed to
be more important between 1) collision resilience and 2) a single-
pass interface for creating signatures. The collision resilience
property means EdDSA is secure even if it is feasible to compute
collisions for the hash function. The single-pass interface property
means that only one pass over the input message is required to create
a signature. PureEdDSA requires two passes over the input. Many
existing APIs, protocols, and environments assume digital signature
algorithms only need one pass over the input and may have API or
bandwidth concerns supporting anything else.
Note that single-pass verification is not possible with most uses of
signatures, no matter which signature algorithm is chosen. This is
because most of the time, one can't process the message until the
signature is validated, which needs a pass on the entire message.
Josefsson & Liusvaara Informational [Page 8]
RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
This document specifies parameters resulting in the HashEdDSA
variants Ed25519ph and Ed448ph and the PureEdDSA variants Ed25519 and
Ed448.
5. EdDSA Instances
This section instantiates the general EdDSA algorithm for the
edwards25519 and edwards448 curves, each for the PureEdDSA and
HashEdDSA variants (plus a contextualized extension of the Ed25519
scheme). Thus, five different parameter sets are described.
5.1. Ed25519ph, Ed25519ctx, and Ed25519
Ed25519 is EdDSA instantiated with:
+-----------+-------------------------------------------------------+
| Parameter | Value |
+-----------+-------------------------------------------------------+
| p | p of edwards25519 in [RFC7748] (i.e., 2^255 - 19) |
| b | 256 |
| encoding | 255-bit little-endian encoding of {0, 1, ..., p-1} |
| of GF(p) | |
| H(x) | SHA-512(dom2(phflag,context)||x) [RFC6234] |
| c | base 2 logarithm of cofactor of edwards25519 in |
| | [RFC7748] (i.e., 3) |
| n | 254 |
| d | d of edwards25519 in [RFC7748] (i.e., -121665/121666 |
| | = 370957059346694393431380835087545651895421138798432 |
| | 19016388785533085940283555) |
| a | -1 |
| B | (X(P),Y(P)) of edwards25519 in [RFC7748] (i.e., (1511 |
| | 22213495354007725011514095885315114540126930418572060 |
| | 46113283949847762202, 4631683569492647816942839400347 |
| | 5163141307993866256225615783033603165251855960)) |
| L | order of edwards25519 in [RFC7748] (i.e., |
| | 2^252+27742317777372353535851937790883648493). |
| PH(x) | x (i.e., the identity function) |
+-----------+-------------------------------------------------------+
Table 1: Parameters of Ed25519
For Ed25519, dom2(f,c) is the empty string. The phflag value is
irrelevant. The context (if present at all) MUST be empty. This
causes the scheme to be one and the same with the Ed25519 scheme
published earlier.
For Ed25519ctx, phflag=0. The context input SHOULD NOT be empty.
Josefsson & Liusvaara Informational [Page 9]
RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
For Ed25519ph, phflag=1 and PH is SHA512 instead. That is, the input
is hashed using SHA-512 before signing with Ed25519.
Value of context is set by the signer and verifier (maximum of 255
octets; the default is empty string, except for Ed25519, which can't
have context) and has to match octet by octet for verification to be
successful.
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.
5.1.1. Modular Arithmetic
For advice on how to implement arithmetic modulo p = 2^255 - 19
efficiently and securely, see Curve25519 [CURVE25519]. For inversion
modulo p, it is recommended to use the identity x^-1 = x^(p-2) (mod
p). Inverting zero should never happen, as it would require invalid
input, which would have been detected before, or would be a
calculation error.
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.1.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 coordinates 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.
Josefsson & Liusvaara Informational [Page 10]
RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
5.1.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). The denominator is always
non-zero mod 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 root x = (u/v)^((p+3)/8). This can be done with the
following trick, using 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 for 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.1.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 neutral point is (0,1), or equivalently in extended homogeneous
coordinates (0, Z, Z, 0) for any non-zero Z.
Josefsson & Liusvaara Informational [Page 11]
RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
The following formulas for adding two points, (x3,y3) =
(x1,y1)+(x2,y2), on twisted Edwards curves with a=-1, square a, and
non-square d are described in Section 3.1 of [Edwards-revisited] and
in [EFD-TWISTED-ADD]. They are complete, 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
For point doubling, (x3,y3) = (x1,y1)+(x1,y1), one could just
substitute equal points in the above (because of completeness, such
substitution is valid) and observe that four multiplications turn
into squares. However, using the formulas described in Section 3.2
of [Edwards-revisited] and in [EFD-TWISTED-DBL] saves a few smaller
operations.
A = X1^2
B = Y1^2
C = 2*Z1^2
H = A+B
E = H-(X1+Y1)^2
G = A-B
F = C+G
X3 = E*F
Y3 = G*H
T3 = E*H
Z3 = F*G
Josefsson & Liusvaara Informational [Page 12]
RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
5.1.5. Key Generation
The private key 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 private key 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: The lowest three bits of the first octet are
cleared, the highest bit of the last octet is cleared, and the
second highest bit of the last octet is set.
3. Interpret the buffer as the little-endian integer, forming a
secret scalar s. Perform a fixed-base scalar multiplication
[s]B.
4. The public key A is the encoding of the point [s]B. 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
[s]B, 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.1.6. Sign
The inputs to the signing procedure is the private key, a 32-octet
string, and a message M of arbitrary size. For Ed25519ctx and
Ed25519ph, there is additionally a context C of at most 255 octets
and a flag F, 0 for Ed25519ctx and 1 for Ed25519ph.
1. Hash the private key, 32 octets, using SHA-512. Let h denote the
resulting digest. Construct the secret scalar s 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(dom2(F, C) || prefix || PH(M)), where M is the
message to be signed. Interpret the 64-octet digest as a little-
endian integer r.
3. Compute the point [r]B. For efficiency, do this by first
reducing r modulo L, the group order of B. Let the string R be
the encoding of this point.
Josefsson & Liusvaara Informational [Page 13]
RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
4. Compute SHA512(dom2(F, C) || R || A || PH(M)), and interpret the
64-octet digest as a little-endian integer k.
5. Compute S = (r + k * s) mod L. For efficiency, again reduce k
modulo L first.
6. Form the signature of the concatenation of R (32 octets) and the
little-endian encoding of S (32 octets; the three most
significant bits of the final octet are always zero).
5.1.7. Verify
1. To verify a signature on a message M using public key A, with F
being 0 for Ed25519ctx, 1 for Ed25519ph, and if Ed25519ctx or
Ed25519ph is being used, C being the context, 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 < L. Decode the public key A as point A'. If any of the
decodings fail (including S being out of range), the signature is
invalid.
2. Compute SHA512(dom2(F, C) || R || A || PH(M)), and interpret the
64-octet digest as a little-endian integer k.
3. Check the group equation [8][S]B = [8]R + [8][k]A'. It's
sufficient, but not required, to instead check [S]B = R + [k]A'.
Josefsson & Liusvaara Informational [Page 14]
RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
5.2. Ed448ph and Ed448
Ed448 is EdDSA instantiated with:
+-----------+-------------------------------------------------------+
| Parameter | Value |
+-----------+-------------------------------------------------------+
| p | p of edwards448 in [RFC7748] (i.e., 2^448 - 2^224 - |
| | 1) |
| b | 456 |
| encoding | 455-bit little-endian encoding of {0, 1, ..., p-1} |
| of GF(p) | |
| H(x) | SHAKE256(dom4(phflag,context)||x, 114) |
| phflag | 0 |
| c | base 2 logarithm of cofactor of edwards448 in |
| | [RFC7748] (i.e., 2) |
| n | 447 |
| d | d of edwards448 in [RFC7748] (i.e., -39081) |
| a | 1 |
| B | (X(P),Y(P)) of edwards448 in [RFC7748] (i.e., (224580 |
| | 04029592430018760433409989603624678964163256413424612 |
| | 54616869504154674060329090291928693579532825780320751 |
| | 46446173674602635247710, 2988192100784814926760179304 |
| | 43930673437544040154080242095928241372331506189835876 |
| | 00353687865541878473398230323350346250053154506283266 |
| | 0)) |
| L | order of edwards448 in [RFC7748] (i.e., 2^446 - 13818 |
| | 06680989511535200738674851542688033669247488217860989 |
| | 4547503885). |
| PH(x) | x (i.e., the identity function) |
+-----------+-------------------------------------------------------+
Table 2: Parameters of Ed448
Ed448ph is the same but with PH being SHAKE256(x, 64) and phflag
being 1, i.e., the input is hashed before signing with Ed448 with a
hash constant modified.
Value of context is set by signer and verifier (maximum of 255
octets; the default is empty string) and has to match octet by octet
for verification to be successful.
The curve is equivalent to Ed448-Goldilocks under change of the
basepoint, which preserves difficulty of the discrete logarithm.
Josefsson & Liusvaara Informational [Page 15]
RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
5.2.1. Modular Arithmetic
For advice on how to implement arithmetic modulo p = 2^448 - 2^224 -
1 efficiently and securely, see [ED448]. For inversion modulo p, it
is recommended to use the identity x^-1 = x^(p-2) (mod p). Inverting
zero should never happen, as it would require invalid input, which
would have been detected before, or would be a calculation error.
For point decoding or "decompression", square roots modulo p are
needed. They can be computed by first computing candidate root
x = a ^ (p+1)/4 (mod p) and then checking if x^2 = a. If it is, then
x is the square root of a; if it isn't, then a does not have a square
root.
5.2.2. Encoding
All values are coded as octet strings, and integers are coded using
little-endian convention, i.e., a 57-octet string h h[0],...h[56]
represents the integer h[0] + 2^8 * h[1] + ... + 2^448 * h[56].
A curve point (x,y), with coordinates in the range 0 <= x,y < p, is
coded as follows. First, encode the y-coordinate as a little-endian
string of 57 octets. 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.2.3. Decoding
Decoding a point, given as a 57-octet string, is a little more
complicated.
1. First, interpret the string as an integer in little-endian
representation. Bit 455 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). The denominator is always
non-zero mod 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 root x = (u/v)^((p+1)/4). 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+1)/4 3 (p-3)/4
x = (u/v) = u v (u^5 v^3) (mod p)
Josefsson & Liusvaara Informational [Page 16]
RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
3. If v * x^2 = u, the recovered x-coordinate is x. Otherwise, no
square root exists, and the 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.2.4. Point Addition
For point addition, the following method is recommended. A point
(x,y) is represented in projective coordinates (X, Y, Z), with
x = X/Z, y = Y/Z.
The neutral point is (0,1), or equivalently in projective coordinates
(0, Z, Z) for any non-zero Z.
The following formulas for adding two points, (x3,y3) =
(x1,y1)+(x2,y2) on untwisted Edwards curve (i.e., a=1) with non-
square d, are described in Section 4 of [Faster-ECC] and in
[EFD-ADD]. They are complete, i.e., they work for any pair of valid
input points.
A = Z1*Z2
B = A^2
C = X1*X2
D = Y1*Y2
E = d*C*D
F = B-E
G = B+E
H = (X1+Y1)*(X2+Y2)
X3 = A*F*(H-C-D)
Y3 = A*G*(D-C)
Z3 = F*G
Josefsson & Liusvaara Informational [Page 17]
RFC 8032 EdDSA: Ed25519 and Ed448 January 2017
Again, similar to the other curve, doubling formulas can be obtained
by substituting equal points, turning four multiplications into
squares. However, this is not even nearly optimal; the following
formulas described in Section 4 of [Faster-ECC] and in [EFD-DBL] save
multiple multiplications.
B = (X1+Y1)^2
C = X1^2
D = Y1^2
E = C+D
H = Z1^2
J = E-2*H
X3 = (B-E)*J
Y3 = E*(C-D)
Z3 = E*J
5.2.5. Key Generation
The private key is 57 octets (456 bits, corresponding to b) of
cryptographically secure random data. See [RFC4086] for a discussion
about randomness.
The 57-byte public key is generated by the following steps:
1. Hash the 57-byte private key using SHAKE256(x, 114), storing the
digest in a 114-octet large buffer, denoted h. Only the lower 57
bytes are used for generating the public key.
2. Prune the buffer: The two least significant bits of the first
octet are cleared, all eight bits the last octet are cleared, and
the highest bit of the second to last octet is set.
3. Interpret the buffer as the little-endian integer, forming a
secret scalar s. Perform a known-base-point scalar
multiplication [s]B.
4. The public key A is the encoding of the point [s]B. First encode
the y-coordinate (in the range 0 <= y < p) as a little-endian
string of 57 octets. The most significant bit of the final octet
is always zero. To form the encoding of the point [s]B, copy the
least significant bit of the x coordinate to the most significant
bit of the final octet. The result is the public key.