main
1// Package ed25519 implements Ed25519 signature scheme as described in RFC-8032.
2//
3// This package provides optimized implementations of the three signature
4// variants and maintaining closer compatibility with crypto/ed25519.
5//
6// | Scheme Name | Sign Function | Verification | Context |
7// |-------------|-------------------|---------------|-------------------|
8// | Ed25519 | Sign | Verify | None |
9// | Ed25519Ph | SignPh | VerifyPh | Yes, can be empty |
10// | Ed25519Ctx | SignWithCtx | VerifyWithCtx | Yes, non-empty |
11// | All above | (PrivateKey).Sign | VerifyAny | As above |
12//
13// Specific functions for sign and verify are defined. A generic signing
14// function for all schemes is available through the crypto.Signer interface,
15// which is implemented by the PrivateKey type. A correspond all-in-one
16// verification method is provided by the VerifyAny function.
17//
18// Signing with Ed25519Ph or Ed25519Ctx requires a context string for domain
19// separation. This parameter is passed using a SignerOptions struct defined
20// in this package. While Ed25519Ph accepts an empty context, Ed25519Ctx
21// enforces non-empty context strings.
22//
23// # Compatibility with crypto.ed25519
24//
25// These functions are compatible with the “Ed25519” function defined in
26// RFC-8032. However, unlike RFC 8032's formulation, this package's private
27// key representation includes a public key suffix to make multiple signing
28// operations with the same key more efficient. This package refers to the
29// RFC-8032 private key as the “seed”.
30//
31// References
32//
33// - RFC-8032: https://rfc-editor.org/rfc/rfc8032.txt
34// - Ed25519: https://ed25519.cr.yp.to/
35// - EdDSA: High-speed high-security signatures. https://doi.org/10.1007/s13389-012-0027-1
36package ed25519
37
38import (
39 "bytes"
40 "crypto"
41 cryptoRand "crypto/rand"
42 "crypto/sha512"
43 "crypto/subtle"
44 "errors"
45 "fmt"
46 "io"
47 "strconv"
48
49 "github.com/cloudflare/circl/sign"
50)
51
52const (
53 // ContextMaxSize is the maximum length (in bytes) allowed for context.
54 ContextMaxSize = 255
55 // PublicKeySize is the size, in bytes, of public keys as used in this package.
56 PublicKeySize = 32
57 // PrivateKeySize is the size, in bytes, of private keys as used in this package.
58 PrivateKeySize = 64
59 // SignatureSize is the size, in bytes, of signatures generated and verified by this package.
60 SignatureSize = 64
61 // SeedSize is the size, in bytes, of private key seeds. These are the private key representations used by RFC 8032.
62 SeedSize = 32
63)
64
65const (
66 paramB = 256 / 8 // Size of keys in bytes.
67)
68
69// SignerOptions implements crypto.SignerOpts and augments with parameters
70// that are specific to the Ed25519 signature schemes.
71type SignerOptions struct {
72 // Hash must be crypto.Hash(0) for Ed25519/Ed25519ctx, or crypto.SHA512
73 // for Ed25519ph.
74 crypto.Hash
75
76 // Context is an optional domain separation string for Ed25519ph and a
77 // must for Ed25519ctx. Its length must be less or equal than 255 bytes.
78 Context string
79
80 // Scheme is an identifier for choosing a signature scheme. The zero value
81 // is ED25519.
82 Scheme SchemeID
83}
84
85// SchemeID is an identifier for each signature scheme.
86type SchemeID uint
87
88const (
89 ED25519 SchemeID = iota
90 ED25519Ph
91 ED25519Ctx
92)
93
94// PrivateKey is the type of Ed25519 private keys. It implements crypto.Signer.
95type PrivateKey []byte
96
97// Equal reports whether priv and x have the same value.
98func (priv PrivateKey) Equal(x crypto.PrivateKey) bool {
99 xx, ok := x.(PrivateKey)
100 return ok && subtle.ConstantTimeCompare(priv, xx) == 1
101}
102
103// Public returns the PublicKey corresponding to priv.
104func (priv PrivateKey) Public() crypto.PublicKey {
105 publicKey := make(PublicKey, PublicKeySize)
106 copy(publicKey, priv[SeedSize:])
107 return publicKey
108}
109
110// Seed returns the private key seed corresponding to priv. It is provided for
111// interoperability with RFC 8032. RFC 8032's private keys correspond to seeds
112// in this package.
113func (priv PrivateKey) Seed() []byte {
114 seed := make([]byte, SeedSize)
115 copy(seed, priv[:SeedSize])
116 return seed
117}
118
119func (priv PrivateKey) Scheme() sign.Scheme { return sch }
120
121func (pub PublicKey) Scheme() sign.Scheme { return sch }
122
123func (priv PrivateKey) MarshalBinary() (data []byte, err error) {
124 privateKey := make(PrivateKey, PrivateKeySize)
125 copy(privateKey, priv)
126 return privateKey, nil
127}
128
129func (pub PublicKey) MarshalBinary() (data []byte, err error) {
130 publicKey := make(PublicKey, PublicKeySize)
131 copy(publicKey, pub)
132 return publicKey, nil
133}
134
135// Equal reports whether pub and x have the same value.
136func (pub PublicKey) Equal(x crypto.PublicKey) bool {
137 xx, ok := x.(PublicKey)
138 return ok && bytes.Equal(pub, xx)
139}
140
141// Sign creates a signature of a message with priv key.
142// This function is compatible with crypto.ed25519 and also supports the
143// three signature variants defined in RFC-8032, namely Ed25519 (or pure
144// EdDSA), Ed25519Ph, and Ed25519Ctx.
145// The opts.HashFunc() must return zero to specify either Ed25519 or Ed25519Ctx
146// variant. This can be achieved by passing crypto.Hash(0) as the value for
147// opts.
148// The opts.HashFunc() must return SHA512 to specify the Ed25519Ph variant.
149// This can be achieved by passing crypto.SHA512 as the value for opts.
150// Use a SignerOptions struct (defined in this package) to pass a context
151// string for signing.
152func (priv PrivateKey) Sign(
153 rand io.Reader,
154 message []byte,
155 opts crypto.SignerOpts,
156) (signature []byte, err error) {
157 var ctx string
158 var scheme SchemeID
159 if o, ok := opts.(SignerOptions); ok {
160 ctx = o.Context
161 scheme = o.Scheme
162 }
163
164 switch true {
165 case scheme == ED25519 && opts.HashFunc() == crypto.Hash(0):
166 return Sign(priv, message), nil
167 case scheme == ED25519Ph && opts.HashFunc() == crypto.SHA512:
168 return SignPh(priv, message, ctx), nil
169 case scheme == ED25519Ctx && opts.HashFunc() == crypto.Hash(0) && len(ctx) > 0:
170 return SignWithCtx(priv, message, ctx), nil
171 default:
172 return nil, errors.New("ed25519: bad hash algorithm")
173 }
174}
175
176// GenerateKey generates a public/private key pair using entropy from rand.
177// If rand is nil, crypto/rand.Reader will be used.
178func GenerateKey(rand io.Reader) (PublicKey, PrivateKey, error) {
179 if rand == nil {
180 rand = cryptoRand.Reader
181 }
182
183 seed := make([]byte, SeedSize)
184 if _, err := io.ReadFull(rand, seed); err != nil {
185 return nil, nil, err
186 }
187
188 privateKey := NewKeyFromSeed(seed)
189 publicKey := make(PublicKey, PublicKeySize)
190 copy(publicKey, privateKey[SeedSize:])
191
192 return publicKey, privateKey, nil
193}
194
195// NewKeyFromSeed calculates a private key from a seed. It will panic if
196// len(seed) is not SeedSize. This function is provided for interoperability
197// with RFC 8032. RFC 8032's private keys correspond to seeds in this
198// package.
199func NewKeyFromSeed(seed []byte) PrivateKey {
200 privateKey := make(PrivateKey, PrivateKeySize)
201 newKeyFromSeed(privateKey, seed)
202 return privateKey
203}
204
205func newKeyFromSeed(privateKey, seed []byte) {
206 if l := len(seed); l != SeedSize {
207 panic("ed25519: bad seed length: " + strconv.Itoa(l))
208 }
209 var P pointR1
210 k := sha512.Sum512(seed)
211 clamp(k[:])
212 reduceModOrder(k[:paramB], false)
213 P.fixedMult(k[:paramB])
214 copy(privateKey[:SeedSize], seed)
215 _ = P.ToBytes(privateKey[SeedSize:])
216}
217
218func signAll(signature []byte, privateKey PrivateKey, message, ctx []byte, preHash bool) {
219 if l := len(privateKey); l != PrivateKeySize {
220 panic("ed25519: bad private key length: " + strconv.Itoa(l))
221 }
222
223 H := sha512.New()
224 var PHM []byte
225
226 if preHash {
227 _, _ = H.Write(message)
228 PHM = H.Sum(nil)
229 H.Reset()
230 } else {
231 PHM = message
232 }
233
234 // 1. Hash the 32-byte private key using SHA-512.
235 _, _ = H.Write(privateKey[:SeedSize])
236 h := H.Sum(nil)
237 clamp(h[:])
238 prefix, s := h[paramB:], h[:paramB]
239
240 // 2. Compute SHA-512(dom2(F, C) || prefix || PH(M))
241 H.Reset()
242
243 writeDom(H, ctx, preHash)
244
245 _, _ = H.Write(prefix)
246 _, _ = H.Write(PHM)
247 r := H.Sum(nil)
248 reduceModOrder(r[:], true)
249
250 // 3. Compute the point [r]B.
251 var P pointR1
252 P.fixedMult(r[:paramB])
253 R := (&[paramB]byte{})[:]
254 if err := P.ToBytes(R); err != nil {
255 panic(err)
256 }
257
258 // 4. Compute SHA512(dom2(F, C) || R || A || PH(M)).
259 H.Reset()
260
261 writeDom(H, ctx, preHash)
262
263 _, _ = H.Write(R)
264 _, _ = H.Write(privateKey[SeedSize:])
265 _, _ = H.Write(PHM)
266 hRAM := H.Sum(nil)
267
268 reduceModOrder(hRAM[:], true)
269
270 // 5. Compute S = (r + k * s) mod order.
271 S := (&[paramB]byte{})[:]
272 calculateS(S, r[:paramB], hRAM[:paramB], s)
273
274 // 6. The signature is the concatenation of R and S.
275 copy(signature[:paramB], R[:])
276 copy(signature[paramB:], S[:])
277}
278
279// Sign signs the message with privateKey and returns a signature.
280// This function supports the signature variant defined in RFC-8032: Ed25519,
281// also known as the pure version of EdDSA.
282// It will panic if len(privateKey) is not PrivateKeySize.
283func Sign(privateKey PrivateKey, message []byte) []byte {
284 signature := make([]byte, SignatureSize)
285 signAll(signature, privateKey, message, []byte(""), false)
286 return signature
287}
288
289// SignPh creates a signature of a message with private key and context.
290// This function supports the signature variant defined in RFC-8032: Ed25519ph,
291// meaning it internally hashes the message using SHA-512, and optionally
292// accepts a context string.
293// It will panic if len(privateKey) is not PrivateKeySize.
294// Context could be passed to this function, which length should be no more than
295// ContextMaxSize=255. It can be empty.
296func SignPh(privateKey PrivateKey, message []byte, ctx string) []byte {
297 if len(ctx) > ContextMaxSize {
298 panic(fmt.Errorf("ed25519: bad context length: %v", len(ctx)))
299 }
300
301 signature := make([]byte, SignatureSize)
302 signAll(signature, privateKey, message, []byte(ctx), true)
303 return signature
304}
305
306// SignWithCtx creates a signature of a message with private key and context.
307// This function supports the signature variant defined in RFC-8032: Ed25519ctx,
308// meaning it accepts a non-empty context string.
309// It will panic if len(privateKey) is not PrivateKeySize.
310// Context must be passed to this function, which length should be no more than
311// ContextMaxSize=255 and cannot be empty.
312func SignWithCtx(privateKey PrivateKey, message []byte, ctx string) []byte {
313 if len(ctx) == 0 || len(ctx) > ContextMaxSize {
314 panic(fmt.Errorf("ed25519: bad context length: %v > %v", len(ctx), ContextMaxSize))
315 }
316
317 signature := make([]byte, SignatureSize)
318 signAll(signature, privateKey, message, []byte(ctx), false)
319 return signature
320}
321
322func verify(public PublicKey, message, signature, ctx []byte, preHash bool) bool {
323 if len(public) != PublicKeySize ||
324 len(signature) != SignatureSize ||
325 !isLessThanOrder(signature[paramB:]) {
326 return false
327 }
328
329 var P pointR1
330 if ok := P.FromBytes(public); !ok {
331 return false
332 }
333
334 H := sha512.New()
335 var PHM []byte
336
337 if preHash {
338 _, _ = H.Write(message)
339 PHM = H.Sum(nil)
340 H.Reset()
341 } else {
342 PHM = message
343 }
344
345 R := signature[:paramB]
346
347 writeDom(H, ctx, preHash)
348
349 _, _ = H.Write(R)
350 _, _ = H.Write(public)
351 _, _ = H.Write(PHM)
352 hRAM := H.Sum(nil)
353 reduceModOrder(hRAM[:], true)
354
355 var Q pointR1
356 encR := (&[paramB]byte{})[:]
357 P.neg()
358 Q.doubleMult(&P, signature[paramB:], hRAM[:paramB])
359 _ = Q.ToBytes(encR)
360 return bytes.Equal(R, encR)
361}
362
363// VerifyAny returns true if the signature is valid. Failure cases are invalid
364// signature, or when the public key cannot be decoded.
365// This function supports all the three signature variants defined in RFC-8032,
366// namely Ed25519 (or pure EdDSA), Ed25519Ph, and Ed25519Ctx.
367// The opts.HashFunc() must return zero to specify either Ed25519 or Ed25519Ctx
368// variant. This can be achieved by passing crypto.Hash(0) as the value for opts.
369// The opts.HashFunc() must return SHA512 to specify the Ed25519Ph variant.
370// This can be achieved by passing crypto.SHA512 as the value for opts.
371// Use a SignerOptions struct to pass a context string for signing.
372func VerifyAny(public PublicKey, message, signature []byte, opts crypto.SignerOpts) bool {
373 var ctx string
374 var scheme SchemeID
375 if o, ok := opts.(SignerOptions); ok {
376 ctx = o.Context
377 scheme = o.Scheme
378 }
379
380 switch true {
381 case scheme == ED25519 && opts.HashFunc() == crypto.Hash(0):
382 return Verify(public, message, signature)
383 case scheme == ED25519Ph && opts.HashFunc() == crypto.SHA512:
384 return VerifyPh(public, message, signature, ctx)
385 case scheme == ED25519Ctx && opts.HashFunc() == crypto.Hash(0) && len(ctx) > 0:
386 return VerifyWithCtx(public, message, signature, ctx)
387 default:
388 return false
389 }
390}
391
392// Verify returns true if the signature is valid. Failure cases are invalid
393// signature, or when the public key cannot be decoded.
394// This function supports the signature variant defined in RFC-8032: Ed25519,
395// also known as the pure version of EdDSA.
396func Verify(public PublicKey, message, signature []byte) bool {
397 return verify(public, message, signature, []byte(""), false)
398}
399
400// VerifyPh returns true if the signature is valid. Failure cases are invalid
401// signature, or when the public key cannot be decoded.
402// This function supports the signature variant defined in RFC-8032: Ed25519ph,
403// meaning it internally hashes the message using SHA-512.
404// Context could be passed to this function, which length should be no more than
405// 255. It can be empty.
406func VerifyPh(public PublicKey, message, signature []byte, ctx string) bool {
407 return verify(public, message, signature, []byte(ctx), true)
408}
409
410// VerifyWithCtx returns true if the signature is valid. Failure cases are invalid
411// signature, or when the public key cannot be decoded, or when context is
412// not provided.
413// This function supports the signature variant defined in RFC-8032: Ed25519ctx,
414// meaning it does not handle prehashed messages. Non-empty context string must be
415// provided, and must not be more than 255 of length.
416func VerifyWithCtx(public PublicKey, message, signature []byte, ctx string) bool {
417 if len(ctx) == 0 || len(ctx) > ContextMaxSize {
418 return false
419 }
420
421 return verify(public, message, signature, []byte(ctx), false)
422}
423
424func clamp(k []byte) {
425 k[0] &= 248
426 k[paramB-1] = (k[paramB-1] & 127) | 64
427}
428
429// isLessThanOrder returns true if 0 <= x < order.
430func isLessThanOrder(x []byte) bool {
431 i := len(order) - 1
432 for i > 0 && x[i] == order[i] {
433 i--
434 }
435 return x[i] < order[i]
436}
437
438func writeDom(h io.Writer, ctx []byte, preHash bool) {
439 dom2 := "SigEd25519 no Ed25519 collisions"
440
441 if len(ctx) > 0 {
442 _, _ = h.Write([]byte(dom2))
443 if preHash {
444 _, _ = h.Write([]byte{byte(0x01), byte(len(ctx))})
445 } else {
446 _, _ = h.Write([]byte{byte(0x00), byte(len(ctx))})
447 }
448 _, _ = h.Write(ctx)
449 } else if preHash {
450 _, _ = h.Write([]byte(dom2))
451 _, _ = h.Write([]byte{0x01, 0x00})
452 }
453}