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 ecdsa
6 7 import (
8 "bytes"
9 "crypto/internal/fips140"
10 "crypto/internal/fips140/bigmod"
11 "crypto/internal/fips140/drbg"
12 "crypto/internal/fips140/nistec"
13 "errors"
14 "hash"
15 "io"
16 "sync"
17 )
18 19 // PrivateKey and PublicKey are not generic to make it possible to use them
20 // in other types without instantiating them with a specific point type.
21 // They are tied to one of the Curve types below through the curveID field.
22 23 type PrivateKey struct {
24 pub PublicKey
25 d []byte // bigmod.(*Nat).Bytes output (same length as the curve order)
26 }
27 28 func (priv *PrivateKey) Bytes() []byte {
29 return priv.d
30 }
31 32 func (priv *PrivateKey) PublicKey() *PublicKey {
33 return &priv.pub
34 }
35 36 type PublicKey struct {
37 curve curveID
38 q []byte // uncompressed nistec Point.Bytes output
39 }
40 41 func (pub *PublicKey) Bytes() []byte {
42 return pub.q
43 }
44 45 type curveID string
46 47 const (
48 p224 curveID = "P-224"
49 p256 curveID = "P-256"
50 p384 curveID = "P-384"
51 p521 curveID = "P-521"
52 )
53 54 type Curve[P Point[P]] struct {
55 curve curveID
56 newPoint func() P
57 ordInverse func([]byte) ([]byte, error)
58 N *bigmod.Modulus
59 nMinus2 []byte
60 }
61 62 // Point is a generic constraint for the [nistec] Point types.
63 type Point[P any] interface {
64 *nistec.P224Point | *nistec.P256Point | *nistec.P384Point | *nistec.P521Point
65 Bytes() []byte
66 BytesX() ([]byte, error)
67 SetBytes([]byte) (P, error)
68 ScalarMult(P, []byte) (P, error)
69 ScalarBaseMult([]byte) (P, error)
70 Add(p1, p2 P) P
71 }
72 73 func precomputeParams[P Point[P]](c *Curve[P], order []byte) {
74 var err error
75 c.N, err = bigmod.NewModulus(order)
76 if err != nil {
77 panic(err)
78 }
79 two, _ := bigmod.NewNat().SetBytes([]byte{2}, c.N)
80 c.nMinus2 = bigmod.NewNat().ExpandFor(c.N).Sub(two, c.N).Bytes(c.N)
81 }
82 83 func P224() *Curve[*nistec.P224Point] { return _P224() }
84 85 var _P224 = sync.OnceValue(func() *Curve[*nistec.P224Point] {
86 c := &Curve[*nistec.P224Point]{
87 curve: p224,
88 newPoint: nistec.NewP224Point,
89 }
90 precomputeParams(c, p224Order)
91 return c
92 })
93 94 var p224Order = []byte{
95 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
96 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x16, 0xa2,
97 0xe0, 0xb8, 0xf0, 0x3e, 0x13, 0xdd, 0x29, 0x45,
98 0x5c, 0x5c, 0x2a, 0x3d,
99 }
100 101 func P256() *Curve[*nistec.P256Point] { return _P256() }
102 103 var _P256 = sync.OnceValue(func() *Curve[*nistec.P256Point] {
104 c := &Curve[*nistec.P256Point]{
105 curve: p256,
106 newPoint: nistec.NewP256Point,
107 ordInverse: nistec.P256OrdInverse,
108 }
109 precomputeParams(c, p256Order)
110 return c
111 })
112 113 var p256Order = []byte{
114 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
115 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
116 0xbc, 0xe6, 0xfa, 0xad, 0xa7, 0x17, 0x9e, 0x84,
117 0xf3, 0xb9, 0xca, 0xc2, 0xfc, 0x63, 0x25, 0x51}
118 119 func P384() *Curve[*nistec.P384Point] { return _P384() }
120 121 var _P384 = sync.OnceValue(func() *Curve[*nistec.P384Point] {
122 c := &Curve[*nistec.P384Point]{
123 curve: p384,
124 newPoint: nistec.NewP384Point,
125 }
126 precomputeParams(c, p384Order)
127 return c
128 })
129 130 var p384Order = []byte{
131 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
132 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
133 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
134 0xc7, 0x63, 0x4d, 0x81, 0xf4, 0x37, 0x2d, 0xdf,
135 0x58, 0x1a, 0x0d, 0xb2, 0x48, 0xb0, 0xa7, 0x7a,
136 0xec, 0xec, 0x19, 0x6a, 0xcc, 0xc5, 0x29, 0x73}
137 138 func P521() *Curve[*nistec.P521Point] { return _P521() }
139 140 var _P521 = sync.OnceValue(func() *Curve[*nistec.P521Point] {
141 c := &Curve[*nistec.P521Point]{
142 curve: p521,
143 newPoint: nistec.NewP521Point,
144 }
145 precomputeParams(c, p521Order)
146 return c
147 })
148 149 var p521Order = []byte{0x01, 0xff,
150 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
151 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
152 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
153 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfa,
154 0x51, 0x86, 0x87, 0x83, 0xbf, 0x2f, 0x96, 0x6b,
155 0x7f, 0xcc, 0x01, 0x48, 0xf7, 0x09, 0xa5, 0xd0,
156 0x3b, 0xb5, 0xc9, 0xb8, 0x89, 0x9c, 0x47, 0xae,
157 0xbb, 0x6f, 0xb7, 0x1e, 0x91, 0x38, 0x64, 0x09}
158 159 func NewPrivateKey[P Point[P]](c *Curve[P], D, Q []byte) (*PrivateKey, error) {
160 fips140.RecordApproved()
161 pub, err := NewPublicKey(c, Q)
162 if err != nil {
163 return nil, err
164 }
165 d, err := bigmod.NewNat().SetBytes(D, c.N)
166 if err != nil {
167 return nil, err
168 }
169 priv := &PrivateKey{pub: *pub, d: d.Bytes(c.N)}
170 return priv, nil
171 }
172 173 func NewPublicKey[P Point[P]](c *Curve[P], Q []byte) (*PublicKey, error) {
174 // SetBytes checks that Q is a valid point on the curve, and that its
175 // coordinates are reduced modulo p, fulfilling the requirements of SP
176 // 800-89, Section 5.3.2.
177 _, err := c.newPoint().SetBytes(Q)
178 if err != nil {
179 return nil, err
180 }
181 return &PublicKey{curve: c.curve, q: Q}, nil
182 }
183 184 // GenerateKey generates a new ECDSA private key pair for the specified curve.
185 func GenerateKey[P Point[P]](c *Curve[P], rand io.Reader) (*PrivateKey, error) {
186 fips140.RecordApproved()
187 188 k, Q, err := randomPoint(c, func(b []byte) error {
189 return drbg.ReadWithReader(rand, b)
190 })
191 if err != nil {
192 return nil, err
193 }
194 195 priv := &PrivateKey{
196 pub: PublicKey{
197 curve: c.curve,
198 q: Q.Bytes(),
199 },
200 d: k.Bytes(c.N),
201 }
202 fipsPCT(c, priv)
203 return priv, nil
204 }
205 206 // randomPoint returns a random scalar and the corresponding point using a
207 // procedure equivalent to FIPS 186-5, Appendix A.2.2 (ECDSA Key Pair Generation
208 // by Rejection Sampling) and to Appendix A.3.2 (Per-Message Secret Number
209 // Generation of Private Keys by Rejection Sampling) or Appendix A.3.3
210 // (Per-Message Secret Number Generation for Deterministic ECDSA) followed by
211 // Step 5 of Section 6.4.1.
212 func randomPoint[P Point[P]](c *Curve[P], generate func([]byte) error) (k *bigmod.Nat, p P, err error) {
213 for {
214 b := []byte{:c.N.Size()}
215 if err := generate(b); err != nil {
216 return nil, nil, err
217 }
218 219 // Take only the leftmost bits of the generated random value. This is
220 // both necessary to increase the chance of the random value being in
221 // the correct range and to match the specification. It's unfortunate
222 // that we need to do a shift instead of a mask, but see the comment on
223 // rightShift.
224 //
225 // These are the most dangerous lines in the package and maybe in the
226 // library: a single bit of bias in the selection of nonces would likely
227 // lead to key recovery, but no tests would fail. Look but DO NOT TOUCH.
228 if excess := len(b)*8 - c.N.BitLen(); excess > 0 {
229 // Just to be safe, assert that this only happens for the one curve that
230 // doesn't have a round number of bits.
231 if c.curve != p521 {
232 panic("ecdsa: internal error: unexpectedly masking off bits")
233 }
234 b = rightShift(b, excess)
235 }
236 237 // FIPS 186-5, Appendix A.4.2 makes us check x <= N - 2 and then return
238 // x + 1. Note that it follows that 0 < x + 1 < N. Instead, SetBytes
239 // checks that k < N, and we explicitly check 0 != k. Since k can't be
240 // negative, this is strictly equivalent. None of this matters anyway
241 // because the chance of selecting zero is cryptographically negligible.
242 if k, err := bigmod.NewNat().SetBytes(b, c.N); err == nil && k.IsZero() == 0 {
243 p, err := c.newPoint().ScalarBaseMult(k.Bytes(c.N))
244 return k, p, err
245 }
246 247 if testingOnlyRejectionSamplingLooped != nil {
248 testingOnlyRejectionSamplingLooped()
249 }
250 }
251 }
252 253 // testingOnlyRejectionSamplingLooped is called when rejection sampling in
254 // randomPoint rejects a candidate for being higher than the modulus.
255 var testingOnlyRejectionSamplingLooped func()
256 257 // Signature is an ECDSA signature, where r and s are represented as big-endian
258 // byte slices of the same length as the curve order.
259 type Signature struct {
260 R, S []byte
261 }
262 263 // Sign signs a hash (which shall be the result of hashing a larger message with
264 // the hash function H) using the private key, priv. If the hash is longer than
265 // the bit-length of the private key's curve order, the hash will be truncated
266 // to that length.
267 func Sign[P Point[P], H hash.Hash](c *Curve[P], h func() H, priv *PrivateKey, rand io.Reader, hash []byte) (*Signature, error) {
268 if priv.pub.curve != c.curve {
269 return nil, errors.New("ecdsa: private key does not match curve")
270 }
271 fips140.RecordApproved()
272 fipsSelfTest()
273 274 // Random ECDSA is dangerous, because a failure of the RNG would immediately
275 // leak the private key. Instead, we use a "hedged" approach, as specified
276 // in draft-irtf-cfrg-det-sigs-with-noise-04, Section 4. This has also the
277 // advantage of closely resembling Deterministic ECDSA.
278 279 Z := []byte{:len(priv.d)}
280 if err := drbg.ReadWithReader(rand, Z); err != nil {
281 return nil, err
282 }
283 284 // See https://github.com/cfrg/draft-irtf-cfrg-det-sigs-with-noise/issues/6
285 // for the FIPS compliance of this method. In short Z is entropy from the
286 // main DRBG, of length 3/2 of security_strength, so the nonce is optional
287 // per SP 800-90Ar1, Section 8.6.7, and the rest is a personalization
288 // string, which per SP 800-90Ar1, Section 8.7.1 may contain secret
289 // information.
290 drbg := newDRBG(h, Z, nil, blockAlignedPersonalizationString{priv.d, bits2octets(c, hash)})
291 292 return sign(c, priv, drbg, hash)
293 }
294 295 // SignDeterministic signs a hash (which shall be the result of hashing a
296 // larger message with the hash function H) using the private key, priv. If the
297 // hash is longer than the bit-length of the private key's curve order, the hash
298 // will be truncated to that length. This applies Deterministic ECDSA as
299 // specified in FIPS 186-5 and RFC 6979.
300 func SignDeterministic[P Point[P], H hash.Hash](c *Curve[P], h func() H, priv *PrivateKey, hash []byte) (*Signature, error) {
301 if priv.pub.curve != c.curve {
302 return nil, errors.New("ecdsa: private key does not match curve")
303 }
304 fips140.RecordApproved()
305 fipsSelfTestDeterministic()
306 drbg := newDRBG(h, priv.d, bits2octets(c, hash), nil) // RFC 6979, Section 3.3
307 return sign(c, priv, drbg, hash)
308 }
309 310 // bits2octets as specified in FIPS 186-5, Appendix B.2.4 or RFC 6979,
311 // Section 2.3.4. See RFC 6979, Section 3.5 for the rationale.
312 func bits2octets[P Point[P]](c *Curve[P], hash []byte) []byte {
313 e := bigmod.NewNat()
314 hashToNat(c, e, hash)
315 return e.Bytes(c.N)
316 }
317 318 func signGeneric[P Point[P]](c *Curve[P], priv *PrivateKey, drbg *hmacDRBG, hash []byte) (*Signature, error) {
319 // FIPS 186-5, Section 6.4.1
320 321 k, R, err := randomPoint(c, func(b []byte) error {
322 drbg.Generate(b)
323 return nil
324 })
325 if err != nil {
326 return nil, err
327 }
328 329 // kInv = k⁻¹
330 kInv := bigmod.NewNat()
331 inverse(c, kInv, k)
332 333 Rx, err := R.BytesX()
334 if err != nil {
335 return nil, err
336 }
337 r, err := bigmod.NewNat().SetOverflowingBytes(Rx, c.N)
338 if err != nil {
339 return nil, err
340 }
341 342 // The spec wants us to retry here, but the chance of hitting this condition
343 // on a large prime-order group like the NIST curves we support is
344 // cryptographically negligible. If we hit it, something is awfully wrong.
345 if r.IsZero() == 1 {
346 return nil, errors.New("ecdsa: internal error: r is zero")
347 }
348 349 e := bigmod.NewNat()
350 hashToNat(c, e, hash)
351 352 s, err := bigmod.NewNat().SetBytes(priv.d, c.N)
353 if err != nil {
354 return nil, err
355 }
356 s.Mul(r, c.N)
357 s.Add(e, c.N)
358 s.Mul(kInv, c.N)
359 360 // Again, the chance of this happening is cryptographically negligible.
361 if s.IsZero() == 1 {
362 return nil, errors.New("ecdsa: internal error: s is zero")
363 }
364 365 return &Signature{r.Bytes(c.N), s.Bytes(c.N)}, nil
366 }
367 368 // inverse sets kInv to the inverse of k modulo the order of the curve.
369 func inverse[P Point[P]](c *Curve[P], kInv, k *bigmod.Nat) {
370 if c.ordInverse != nil {
371 kBytes, err := c.ordInverse(k.Bytes(c.N))
372 // Some platforms don't implement ordInverse, and always return an error.
373 if err == nil {
374 _, err := kInv.SetBytes(kBytes, c.N)
375 if err != nil {
376 panic("ecdsa: internal error: ordInverse produced an invalid value")
377 }
378 return
379 }
380 }
381 382 // Calculate the inverse of s in GF(N) using Fermat's method
383 // (exponentiation modulo P - 2, per Euler's theorem)
384 kInv.Exp(k, c.nMinus2, c.N)
385 }
386 387 // hashToNat sets e to the left-most bits of hash, according to
388 // FIPS 186-5, Section 6.4.1, point 2 and Section 6.4.2, point 3.
389 func hashToNat[P Point[P]](c *Curve[P], e *bigmod.Nat, hash []byte) {
390 // ECDSA asks us to take the left-most log2(N) bits of hash, and use them as
391 // an integer modulo N. This is the absolute worst of all worlds: we still
392 // have to reduce, because the result might still overflow N, but to take
393 // the left-most bits for P-521 we have to do a right shift.
394 if size := c.N.Size(); len(hash) >= size {
395 hash = hash[:size]
396 if excess := len(hash)*8 - c.N.BitLen(); excess > 0 {
397 hash = rightShift(hash, excess)
398 }
399 }
400 _, err := e.SetOverflowingBytes(hash, c.N)
401 if err != nil {
402 panic("ecdsa: internal error: truncated hash is too long")
403 }
404 }
405 406 // rightShift implements the right shift necessary for bits2int, which takes the
407 // leftmost bits of either the hash or HMAC_DRBG output.
408 //
409 // Note how taking the rightmost bits would have been as easy as masking the
410 // first byte, but we can't have nice things.
411 func rightShift(b []byte, shift int) []byte {
412 if shift <= 0 || shift >= 8 {
413 panic("ecdsa: internal error: shift can only be by 1 to 7 bits")
414 }
415 b = bytes.Clone(b)
416 for i := len(b) - 1; i >= 0; i-- {
417 b[i] >>= shift
418 if i > 0 {
419 b[i] |= b[i-1] << (8 - shift)
420 }
421 }
422 return b
423 }
424 425 // Verify verifies the signature, sig, of hash (which should be the result of
426 // hashing a larger message) using the public key, pub. If the hash is longer
427 // than the bit-length of the private key's curve order, the hash will be
428 // truncated to that length.
429 //
430 // The inputs are not considered confidential, and may leak through timing side
431 // channels, or if an attacker has control of part of the inputs.
432 func Verify[P Point[P]](c *Curve[P], pub *PublicKey, hash []byte, sig *Signature) error {
433 if pub.curve != c.curve {
434 return errors.New("ecdsa: public key does not match curve")
435 }
436 fips140.RecordApproved()
437 fipsSelfTest()
438 return verify(c, pub, hash, sig)
439 }
440 441 func verifyGeneric[P Point[P]](c *Curve[P], pub *PublicKey, hash []byte, sig *Signature) error {
442 // FIPS 186-5, Section 6.4.2
443 444 Q, err := c.newPoint().SetBytes(pub.q)
445 if err != nil {
446 return err
447 }
448 449 r, err := bigmod.NewNat().SetBytes(sig.R, c.N)
450 if err != nil {
451 return err
452 }
453 if r.IsZero() == 1 {
454 return errors.New("ecdsa: invalid signature: r is zero")
455 }
456 s, err := bigmod.NewNat().SetBytes(sig.S, c.N)
457 if err != nil {
458 return err
459 }
460 if s.IsZero() == 1 {
461 return errors.New("ecdsa: invalid signature: s is zero")
462 }
463 464 e := bigmod.NewNat()
465 hashToNat(c, e, hash)
466 467 // w = s⁻¹
468 w := bigmod.NewNat()
469 inverse(c, w, s)
470 471 // p₁ = [e * s⁻¹]G
472 p1, err := c.newPoint().ScalarBaseMult(e.Mul(w, c.N).Bytes(c.N))
473 if err != nil {
474 return err
475 }
476 // p₂ = [r * s⁻¹]Q
477 p2, err := Q.ScalarMult(Q, w.Mul(r, c.N).Bytes(c.N))
478 if err != nil {
479 return err
480 }
481 // BytesX returns an error for the point at infinity.
482 Rx, err := p1.Add(p1, p2).BytesX()
483 if err != nil {
484 return err
485 }
486 487 v, err := bigmod.NewNat().SetOverflowingBytes(Rx, c.N)
488 if err != nil {
489 return err
490 }
491 492 if v.Equal(r) != 1 {
493 return errors.New("ecdsa: signature did not verify")
494 }
495 return nil
496 }
497