ed25519.mx raw
1 // Copyright 2024 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 package ed25519
6
7 import (
8 "bytes"
9 "crypto/internal/fips140"
10 "crypto/internal/fips140/drbg"
11 "crypto/internal/fips140/edwards25519"
12 "crypto/internal/fips140/sha512"
13 "errors"
14 "strconv"
15 )
16
17 // See https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/ for the
18 // components of the keys and the moving parts of the algorithm.
19
20 const (
21 seedSize = 32
22 publicKeySize = 32
23 privateKeySize = seedSize + publicKeySize
24 signatureSize = 64
25 sha512Size = 64
26 )
27
28 type PrivateKey struct {
29 seed [seedSize]byte
30 pub [publicKeySize]byte
31 s edwards25519.Scalar
32 prefix [sha512Size / 2]byte
33 }
34
35 func (priv *PrivateKey) Bytes() []byte {
36 k := []byte{:0:privateKeySize}
37 k = append(k, priv.seed[:]...)
38 k = append(k, priv.pub[:]...)
39 return k
40 }
41
42 func (priv *PrivateKey) Seed() []byte {
43 seed := priv.seed
44 return seed[:]
45 }
46
47 func (priv *PrivateKey) PublicKey() []byte {
48 pub := priv.pub
49 return pub[:]
50 }
51
52 type PublicKey struct {
53 a edwards25519.Point
54 aBytes [32]byte
55 }
56
57 func (pub *PublicKey) Bytes() []byte {
58 a := pub.aBytes
59 return a[:]
60 }
61
62 // GenerateKey generates a new Ed25519 private key pair.
63 func GenerateKey() (*PrivateKey, error) {
64 priv := &PrivateKey{}
65 return generateKey(priv)
66 }
67
68 func generateKey(priv *PrivateKey) (*PrivateKey, error) {
69 fips140.RecordApproved()
70 drbg.Read(priv.seed[:])
71 precomputePrivateKey(priv)
72 fipsPCT(priv)
73 return priv, nil
74 }
75
76 func NewPrivateKeyFromSeed(seed []byte) (*PrivateKey, error) {
77 priv := &PrivateKey{}
78 return newPrivateKeyFromSeed(priv, seed)
79 }
80
81 func newPrivateKeyFromSeed(priv *PrivateKey, seed []byte) (*PrivateKey, error) {
82 fips140.RecordApproved()
83 if l := len(seed); l != seedSize {
84 return nil, errors.New("ed25519: bad seed length: " + strconv.Itoa(l))
85 }
86 copy(priv.seed[:], seed)
87 precomputePrivateKey(priv)
88 return priv, nil
89 }
90
91 func precomputePrivateKey(priv *PrivateKey) {
92 hs := sha512.New()
93 hs.Write(priv.seed[:])
94 h := hs.Sum([]byte{:0:sha512Size})
95
96 s, err := priv.s.SetBytesWithClamping(h[:32])
97 if err != nil {
98 panic("ed25519: internal error: setting scalar failed")
99 }
100 A := (&edwards25519.Point{}).ScalarBaseMult(s)
101 copy(priv.pub[:], A.Bytes())
102
103 copy(priv.prefix[:], h[32:])
104 }
105
106 func NewPrivateKey(priv []byte) (*PrivateKey, error) {
107 p := &PrivateKey{}
108 return newPrivateKey(p, priv)
109 }
110
111 func newPrivateKey(priv *PrivateKey, privBytes []byte) (*PrivateKey, error) {
112 fips140.RecordApproved()
113 if l := len(privBytes); l != privateKeySize {
114 return nil, errors.New("ed25519: bad private key length: " + strconv.Itoa(l))
115 }
116
117 copy(priv.seed[:], privBytes[:32])
118
119 hs := sha512.New()
120 hs.Write(priv.seed[:])
121 h := hs.Sum([]byte{:0:sha512Size})
122
123 if _, err := priv.s.SetBytesWithClamping(h[:32]); err != nil {
124 panic("ed25519: internal error: setting scalar failed")
125 }
126 // Note that we are not decompressing the public key point here,
127 // because it takes > 20% of the time of a signature generation.
128 // Signing doesn't use it as a point anyway.
129 copy(priv.pub[:], privBytes[32:])
130
131 copy(priv.prefix[:], h[32:])
132
133 return priv, nil
134 }
135
136 func NewPublicKey(pub []byte) (*PublicKey, error) {
137 p := &PublicKey{}
138 return newPublicKey(p, pub)
139 }
140
141 func newPublicKey(pub *PublicKey, pubBytes []byte) (*PublicKey, error) {
142 if l := len(pubBytes); l != publicKeySize {
143 return nil, errors.New("ed25519: bad public key length: " + strconv.Itoa(l))
144 }
145 // SetBytes checks that the point is on the curve.
146 if _, err := pub.a.SetBytes(pubBytes); err != nil {
147 return nil, errors.New("ed25519: bad public key")
148 }
149 copy(pub.aBytes[:], pubBytes)
150 return pub, nil
151 }
152
153 // Domain separation prefixes used to disambiguate Ed25519/Ed25519ph/Ed25519ctx.
154 // See RFC 8032, Section 2 and Section 5.1.
155 const (
156 // domPrefixPure is empty for pure Ed25519.
157 domPrefixPure = ""
158 // domPrefixPh is dom2(phflag=1) for Ed25519ph. It must be followed by the
159 // uint8-length prefixed context.
160 domPrefixPh = "SigEd25519 no Ed25519 collisions\x01"
161 // domPrefixCtx is dom2(phflag=0) for Ed25519ctx. It must be followed by the
162 // uint8-length prefixed context.
163 domPrefixCtx = "SigEd25519 no Ed25519 collisions\x00"
164 )
165
166 func Sign(priv *PrivateKey, message []byte) []byte {
167 // Outline the function body so that the returned signature can be
168 // stack-allocated.
169 signature := []byte{:signatureSize}
170 return sign(signature, priv, message)
171 }
172
173 func sign(signature []byte, priv *PrivateKey, message []byte) []byte {
174 fipsSelfTest()
175 fips140.RecordApproved()
176 return signWithDom(signature, priv, message, domPrefixPure, "")
177 }
178
179 func SignPH(priv *PrivateKey, message []byte, context string) ([]byte, error) {
180 // Outline the function body so that the returned signature can be
181 // stack-allocated.
182 signature := []byte{:signatureSize}
183 return signPH(signature, priv, message, context)
184 }
185
186 func signPH(signature []byte, priv *PrivateKey, message []byte, context string) ([]byte, error) {
187 fipsSelfTest()
188 fips140.RecordApproved()
189 if l := len(message); l != sha512Size {
190 return nil, errors.New("ed25519: bad Ed25519ph message hash length: " + strconv.Itoa(l))
191 }
192 if l := len(context); l > 255 {
193 return nil, errors.New("ed25519: bad Ed25519ph context length: " + strconv.Itoa(l))
194 }
195 return signWithDom(signature, priv, message, domPrefixPh, context), nil
196 }
197
198 func SignCtx(priv *PrivateKey, message []byte, context string) ([]byte, error) {
199 // Outline the function body so that the returned signature can be
200 // stack-allocated.
201 signature := []byte{:signatureSize}
202 return signCtx(signature, priv, message, context)
203 }
204
205 func signCtx(signature []byte, priv *PrivateKey, message []byte, context string) ([]byte, error) {
206 fipsSelfTest()
207 // FIPS 186-5 specifies Ed25519 and Ed25519ph (with context), but not Ed25519ctx.
208 fips140.RecordNonApproved()
209 // Note that per RFC 8032, Section 5.1, the context SHOULD NOT be empty.
210 if l := len(context); l > 255 {
211 return nil, errors.New("ed25519: bad Ed25519ctx context length: " + strconv.Itoa(l))
212 }
213 return signWithDom(signature, priv, message, domPrefixCtx, context), nil
214 }
215
216 func signWithDom(signature []byte, priv *PrivateKey, message []byte, domPrefix, context string) []byte {
217 mh := sha512.New()
218 if domPrefix != domPrefixPure {
219 mh.Write([]byte(domPrefix))
220 mh.Write([]byte{byte(len(context))})
221 mh.Write([]byte(context))
222 }
223 mh.Write(priv.prefix[:])
224 mh.Write(message)
225 messageDigest := []byte{:0:sha512Size}
226 messageDigest = mh.Sum(messageDigest)
227 r, err := edwards25519.NewScalar().SetUniformBytes(messageDigest)
228 if err != nil {
229 panic("ed25519: internal error: setting scalar failed")
230 }
231
232 R := (&edwards25519.Point{}).ScalarBaseMult(r)
233
234 kh := sha512.New()
235 if domPrefix != domPrefixPure {
236 kh.Write([]byte(domPrefix))
237 kh.Write([]byte{byte(len(context))})
238 kh.Write([]byte(context))
239 }
240 kh.Write(R.Bytes())
241 kh.Write(priv.pub[:])
242 kh.Write(message)
243 hramDigest := []byte{:0:sha512Size}
244 hramDigest = kh.Sum(hramDigest)
245 k, err := edwards25519.NewScalar().SetUniformBytes(hramDigest)
246 if err != nil {
247 panic("ed25519: internal error: setting scalar failed")
248 }
249
250 S := edwards25519.NewScalar().MultiplyAdd(k, &priv.s, r)
251
252 copy(signature[:32], R.Bytes())
253 copy(signature[32:], S.Bytes())
254
255 return signature
256 }
257
258 func Verify(pub *PublicKey, message, sig []byte) error {
259 return verify(pub, message, sig)
260 }
261
262 func verify(pub *PublicKey, message, sig []byte) error {
263 fipsSelfTest()
264 fips140.RecordApproved()
265 return verifyWithDom(pub, message, sig, domPrefixPure, "")
266 }
267
268 func VerifyPH(pub *PublicKey, message []byte, sig []byte, context string) error {
269 fipsSelfTest()
270 fips140.RecordApproved()
271 if l := len(message); l != sha512Size {
272 return errors.New("ed25519: bad Ed25519ph message hash length: " + strconv.Itoa(l))
273 }
274 if l := len(context); l > 255 {
275 return errors.New("ed25519: bad Ed25519ph context length: " + strconv.Itoa(l))
276 }
277 return verifyWithDom(pub, message, sig, domPrefixPh, context)
278 }
279
280 func VerifyCtx(pub *PublicKey, message []byte, sig []byte, context string) error {
281 fipsSelfTest()
282 // FIPS 186-5 specifies Ed25519 and Ed25519ph (with context), but not Ed25519ctx.
283 fips140.RecordNonApproved()
284 if l := len(context); l > 255 {
285 return errors.New("ed25519: bad Ed25519ctx context length: " + strconv.Itoa(l))
286 }
287 return verifyWithDom(pub, message, sig, domPrefixCtx, context)
288 }
289
290 func verifyWithDom(pub *PublicKey, message, sig []byte, domPrefix, context string) error {
291 if l := len(sig); l != signatureSize {
292 return errors.New("ed25519: bad signature length: " + strconv.Itoa(l))
293 }
294
295 if sig[63]&224 != 0 {
296 return errors.New("ed25519: invalid signature")
297 }
298
299 kh := sha512.New()
300 if domPrefix != domPrefixPure {
301 kh.Write([]byte(domPrefix))
302 kh.Write([]byte{byte(len(context))})
303 kh.Write([]byte(context))
304 }
305 kh.Write(sig[:32])
306 kh.Write(pub.aBytes[:])
307 kh.Write(message)
308 hramDigest := []byte{:0:sha512Size}
309 hramDigest = kh.Sum(hramDigest)
310 k, err := edwards25519.NewScalar().SetUniformBytes(hramDigest)
311 if err != nil {
312 panic("ed25519: internal error: setting scalar failed")
313 }
314
315 S, err := edwards25519.NewScalar().SetCanonicalBytes(sig[32:])
316 if err != nil {
317 return errors.New("ed25519: invalid signature")
318 }
319
320 // [S]B = R + [k]A --> [k](-A) + [S]B = R
321 minusA := (&edwards25519.Point{}).Negate(&pub.a)
322 R := (&edwards25519.Point{}).VarTimeDoubleScalarBaseMult(k, minusA, S)
323
324 if !bytes.Equal(sig[:32], R.Bytes()) {
325 return errors.New("ed25519: invalid signature")
326 }
327 return nil
328 }
329