ecdsa_test.go

Documentation: crypto/ecdsa

     1  // Copyright 2011 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  	"bufio"
     9  	"bytes"
    10  	"compress/bzip2"
    11  	"crypto/elliptic"
    12  	"crypto/internal/bigmod"
    13  	"crypto/rand"
    14  	"crypto/sha1"
    15  	"crypto/sha256"
    16  	"crypto/sha512"
    17  	"encoding/hex"
    18  	"hash"
    19  	"io"
    20  	"math/big"
    21  	"os"
    22  	"strings"
    23  	"testing"
    24  )
    25  
    26  func testAllCurves(t *testing.T, f func(*testing.T, elliptic.Curve)) {
    27  	tests := []struct {
    28  		name  string
    29  		curve elliptic.Curve
    30  	}{
    31  		{"P256", elliptic.P256()},
    32  		{"P224", elliptic.P224()},
    33  		{"P384", elliptic.P384()},
    34  		{"P521", elliptic.P521()},
    35  		{"P256/Generic", genericParamsForCurve(elliptic.P256())},
    36  	}
    37  	if testing.Short() {
    38  		tests = tests[:1]
    39  	}
    40  	for _, test := range tests {
    41  		curve := test.curve
    42  		t.Run(test.name, func(t *testing.T) {
    43  			t.Parallel()
    44  			f(t, curve)
    45  		})
    46  	}
    47  }
    48  
    49  // genericParamsForCurve returns the dereferenced CurveParams for
    50  // the specified curve. This is used to avoid the logic for
    51  // upgrading a curve to its specific implementation, forcing
    52  // usage of the generic implementation.
    53  func genericParamsForCurve(c elliptic.Curve) *elliptic.CurveParams {
    54  	d := *(c.Params())
    55  	return &d
    56  }
    57  
    58  func TestKeyGeneration(t *testing.T) {
    59  	testAllCurves(t, testKeyGeneration)
    60  }
    61  
    62  func testKeyGeneration(t *testing.T, c elliptic.Curve) {
    63  	priv, err := GenerateKey(c, rand.Reader)
    64  	if err != nil {
    65  		t.Fatal(err)
    66  	}
    67  	if !c.IsOnCurve(priv.PublicKey.X, priv.PublicKey.Y) {
    68  		t.Errorf("public key invalid: %s", err)
    69  	}
    70  }
    71  
    72  func TestSignAndVerify(t *testing.T) {
    73  	testAllCurves(t, testSignAndVerify)
    74  }
    75  
    76  func testSignAndVerify(t *testing.T, c elliptic.Curve) {
    77  	priv, _ := GenerateKey(c, rand.Reader)
    78  
    79  	hashed := []byte("testing")
    80  	r, s, err := Sign(rand.Reader, priv, hashed)
    81  	if err != nil {
    82  		t.Errorf("error signing: %s", err)
    83  		return
    84  	}
    85  
    86  	if !Verify(&priv.PublicKey, hashed, r, s) {
    87  		t.Errorf("Verify failed")
    88  	}
    89  
    90  	hashed[0] ^= 0xff
    91  	if Verify(&priv.PublicKey, hashed, r, s) {
    92  		t.Errorf("Verify always works!")
    93  	}
    94  }
    95  
    96  func TestSignAndVerifyASN1(t *testing.T) {
    97  	testAllCurves(t, testSignAndVerifyASN1)
    98  }
    99  
   100  func testSignAndVerifyASN1(t *testing.T, c elliptic.Curve) {
   101  	priv, _ := GenerateKey(c, rand.Reader)
   102  
   103  	hashed := []byte("testing")
   104  	sig, err := SignASN1(rand.Reader, priv, hashed)
   105  	if err != nil {
   106  		t.Errorf("error signing: %s", err)
   107  		return
   108  	}
   109  
   110  	if !VerifyASN1(&priv.PublicKey, hashed, sig) {
   111  		t.Errorf("VerifyASN1 failed")
   112  	}
   113  
   114  	hashed[0] ^= 0xff
   115  	if VerifyASN1(&priv.PublicKey, hashed, sig) {
   116  		t.Errorf("VerifyASN1 always works!")
   117  	}
   118  }
   119  
   120  func TestNonceSafety(t *testing.T) {
   121  	testAllCurves(t, testNonceSafety)
   122  }
   123  
   124  func testNonceSafety(t *testing.T, c elliptic.Curve) {
   125  	priv, _ := GenerateKey(c, rand.Reader)
   126  
   127  	hashed := []byte("testing")
   128  	r0, s0, err := Sign(zeroReader, priv, hashed)
   129  	if err != nil {
   130  		t.Errorf("error signing: %s", err)
   131  		return
   132  	}
   133  
   134  	hashed = []byte("testing...")
   135  	r1, s1, err := Sign(zeroReader, priv, hashed)
   136  	if err != nil {
   137  		t.Errorf("error signing: %s", err)
   138  		return
   139  	}
   140  
   141  	if s0.Cmp(s1) == 0 {
   142  		// This should never happen.
   143  		t.Errorf("the signatures on two different messages were the same")
   144  	}
   145  
   146  	if r0.Cmp(r1) == 0 {
   147  		t.Errorf("the nonce used for two different messages was the same")
   148  	}
   149  }
   150  
   151  func TestINDCCA(t *testing.T) {
   152  	testAllCurves(t, testINDCCA)
   153  }
   154  
   155  func testINDCCA(t *testing.T, c elliptic.Curve) {
   156  	priv, _ := GenerateKey(c, rand.Reader)
   157  
   158  	hashed := []byte("testing")
   159  	r0, s0, err := Sign(rand.Reader, priv, hashed)
   160  	if err != nil {
   161  		t.Errorf("error signing: %s", err)
   162  		return
   163  	}
   164  
   165  	r1, s1, err := Sign(rand.Reader, priv, hashed)
   166  	if err != nil {
   167  		t.Errorf("error signing: %s", err)
   168  		return
   169  	}
   170  
   171  	if s0.Cmp(s1) == 0 {
   172  		t.Errorf("two signatures of the same message produced the same result")
   173  	}
   174  
   175  	if r0.Cmp(r1) == 0 {
   176  		t.Errorf("two signatures of the same message produced the same nonce")
   177  	}
   178  }
   179  
   180  func fromHex(s string) *big.Int {
   181  	r, ok := new(big.Int).SetString(s, 16)
   182  	if !ok {
   183  		panic("bad hex")
   184  	}
   185  	return r
   186  }
   187  
   188  func TestVectors(t *testing.T) {
   189  	// This test runs the full set of NIST test vectors from
   190  	// https://csrc.nist.gov/groups/STM/cavp/documents/dss/186-3ecdsatestvectors.zip
   191  	//
   192  	// The SigVer.rsp file has been edited to remove test vectors for
   193  	// unsupported algorithms and has been compressed.
   194  
   195  	if testing.Short() {
   196  		return
   197  	}
   198  
   199  	f, err := os.Open("testdata/SigVer.rsp.bz2")
   200  	if err != nil {
   201  		t.Fatal(err)
   202  	}
   203  
   204  	buf := bufio.NewReader(bzip2.NewReader(f))
   205  
   206  	lineNo := 1
   207  	var h hash.Hash
   208  	var msg []byte
   209  	var hashed []byte
   210  	var r, s *big.Int
   211  	pub := new(PublicKey)
   212  
   213  	for {
   214  		line, err := buf.ReadString('\n')
   215  		if len(line) == 0 {
   216  			if err == io.EOF {
   217  				break
   218  			}
   219  			t.Fatalf("error reading from input: %s", err)
   220  		}
   221  		lineNo++
   222  		// Need to remove \r\n from the end of the line.
   223  		if !strings.HasSuffix(line, "\r\n") {
   224  			t.Fatalf("bad line ending (expected \\r\\n) on line %d", lineNo)
   225  		}
   226  		line = line[:len(line)-2]
   227  
   228  		if len(line) == 0 || line[0] == '#' {
   229  			continue
   230  		}
   231  
   232  		if line[0] == '[' {
   233  			line = line[1 : len(line)-1]
   234  			curve, hash, _ := strings.Cut(line, ",")
   235  
   236  			switch curve {
   237  			case "P-224":
   238  				pub.Curve = elliptic.P224()
   239  			case "P-256":
   240  				pub.Curve = elliptic.P256()
   241  			case "P-384":
   242  				pub.Curve = elliptic.P384()
   243  			case "P-521":
   244  				pub.Curve = elliptic.P521()
   245  			default:
   246  				pub.Curve = nil
   247  			}
   248  
   249  			switch hash {
   250  			case "SHA-1":
   251  				h = sha1.New()
   252  			case "SHA-224":
   253  				h = sha256.New224()
   254  			case "SHA-256":
   255  				h = sha256.New()
   256  			case "SHA-384":
   257  				h = sha512.New384()
   258  			case "SHA-512":
   259  				h = sha512.New()
   260  			default:
   261  				h = nil
   262  			}
   263  
   264  			continue
   265  		}
   266  
   267  		if h == nil || pub.Curve == nil {
   268  			continue
   269  		}
   270  
   271  		switch {
   272  		case strings.HasPrefix(line, "Msg = "):
   273  			if msg, err = hex.DecodeString(line[6:]); err != nil {
   274  				t.Fatalf("failed to decode message on line %d: %s", lineNo, err)
   275  			}
   276  		case strings.HasPrefix(line, "Qx = "):
   277  			pub.X = fromHex(line[5:])
   278  		case strings.HasPrefix(line, "Qy = "):
   279  			pub.Y = fromHex(line[5:])
   280  		case strings.HasPrefix(line, "R = "):
   281  			r = fromHex(line[4:])
   282  		case strings.HasPrefix(line, "S = "):
   283  			s = fromHex(line[4:])
   284  		case strings.HasPrefix(line, "Result = "):
   285  			expected := line[9] == 'P'
   286  			h.Reset()
   287  			h.Write(msg)
   288  			hashed := h.Sum(hashed[:0])
   289  			if Verify(pub, hashed, r, s) != expected {
   290  				t.Fatalf("incorrect result on line %d", lineNo)
   291  			}
   292  		default:
   293  			t.Fatalf("unknown variable on line %d: %s", lineNo, line)
   294  		}
   295  	}
   296  }
   297  
   298  func TestNegativeInputs(t *testing.T) {
   299  	testAllCurves(t, testNegativeInputs)
   300  }
   301  
   302  func testNegativeInputs(t *testing.T, curve elliptic.Curve) {
   303  	key, err := GenerateKey(curve, rand.Reader)
   304  	if err != nil {
   305  		t.Errorf("failed to generate key")
   306  	}
   307  
   308  	var hash [32]byte
   309  	r := new(big.Int).SetInt64(1)
   310  	r.Lsh(r, 550 /* larger than any supported curve */)
   311  	r.Neg(r)
   312  
   313  	if Verify(&key.PublicKey, hash[:], r, r) {
   314  		t.Errorf("bogus signature accepted")
   315  	}
   316  }
   317  
   318  func TestZeroHashSignature(t *testing.T) {
   319  	testAllCurves(t, testZeroHashSignature)
   320  }
   321  
   322  func testZeroHashSignature(t *testing.T, curve elliptic.Curve) {
   323  	zeroHash := make([]byte, 64)
   324  
   325  	privKey, err := GenerateKey(curve, rand.Reader)
   326  	if err != nil {
   327  		panic(err)
   328  	}
   329  
   330  	// Sign a hash consisting of all zeros.
   331  	r, s, err := Sign(rand.Reader, privKey, zeroHash)
   332  	if err != nil {
   333  		panic(err)
   334  	}
   335  
   336  	// Confirm that it can be verified.
   337  	if !Verify(&privKey.PublicKey, zeroHash, r, s) {
   338  		t.Errorf("zero hash signature verify failed for %T", curve)
   339  	}
   340  }
   341  
   342  func TestRandomPoint(t *testing.T) {
   343  	t.Run("P-224", func(t *testing.T) { testRandomPoint(t, p224()) })
   344  	t.Run("P-256", func(t *testing.T) { testRandomPoint(t, p256()) })
   345  	t.Run("P-384", func(t *testing.T) { testRandomPoint(t, p384()) })
   346  	t.Run("P-521", func(t *testing.T) { testRandomPoint(t, p521()) })
   347  }
   348  
   349  func testRandomPoint[Point nistPoint[Point]](t *testing.T, c *nistCurve[Point]) {
   350  	t.Cleanup(func() { testingOnlyRejectionSamplingLooped = nil })
   351  	var loopCount int
   352  	testingOnlyRejectionSamplingLooped = func() { loopCount++ }
   353  
   354  	// A sequence of all ones will generate 2^N-1, which should be rejected.
   355  	// (Unless, for example, we are masking too many bits.)
   356  	r := io.MultiReader(bytes.NewReader(bytes.Repeat([]byte{0xff}, 100)), rand.Reader)
   357  	if k, p, err := randomPoint(c, r); err != nil {
   358  		t.Fatal(err)
   359  	} else if k.IsZero() == 1 {
   360  		t.Error("k is zero")
   361  	} else if p.Bytes()[0] != 4 {
   362  		t.Error("p is infinity")
   363  	}
   364  	if loopCount == 0 {
   365  		t.Error("overflow was not rejected")
   366  	}
   367  	loopCount = 0
   368  
   369  	// A sequence of all zeroes will generate zero, which should be rejected.
   370  	r = io.MultiReader(bytes.NewReader(bytes.Repeat([]byte{0}, 100)), rand.Reader)
   371  	if k, p, err := randomPoint(c, r); err != nil {
   372  		t.Fatal(err)
   373  	} else if k.IsZero() == 1 {
   374  		t.Error("k is zero")
   375  	} else if p.Bytes()[0] != 4 {
   376  		t.Error("p is infinity")
   377  	}
   378  	if loopCount == 0 {
   379  		t.Error("zero was not rejected")
   380  	}
   381  	loopCount = 0
   382  
   383  	// P-256 has a 2⁻³² chance or randomly hitting a rejection. For P-224 it's
   384  	// 2⁻¹¹², for P-384 it's 2⁻¹⁹⁴, and for P-521 it's 2⁻²⁶², so if we hit in
   385  	// tests, something is horribly wrong. (For example, we are masking the
   386  	// wrong bits.)
   387  	if c.curve == elliptic.P256() {
   388  		return
   389  	}
   390  	if k, p, err := randomPoint(c, rand.Reader); err != nil {
   391  		t.Fatal(err)
   392  	} else if k.IsZero() == 1 {
   393  		t.Error("k is zero")
   394  	} else if p.Bytes()[0] != 4 {
   395  		t.Error("p is infinity")
   396  	}
   397  	if loopCount > 0 {
   398  		t.Error("unexpected rejection")
   399  	}
   400  }
   401  
   402  func TestHashToNat(t *testing.T) {
   403  	t.Run("P-224", func(t *testing.T) { testHashToNat(t, p224()) })
   404  	t.Run("P-256", func(t *testing.T) { testHashToNat(t, p256()) })
   405  	t.Run("P-384", func(t *testing.T) { testHashToNat(t, p384()) })
   406  	t.Run("P-521", func(t *testing.T) { testHashToNat(t, p521()) })
   407  }
   408  
   409  func testHashToNat[Point nistPoint[Point]](t *testing.T, c *nistCurve[Point]) {
   410  	for l := 0; l < 600; l++ {
   411  		h := bytes.Repeat([]byte{0xff}, l)
   412  		hashToNat(c, bigmod.NewNat(), h)
   413  	}
   414  }
   415  
   416  func TestZeroSignature(t *testing.T) {
   417  	testAllCurves(t, testZeroSignature)
   418  }
   419  
   420  func testZeroSignature(t *testing.T, curve elliptic.Curve) {
   421  	privKey, err := GenerateKey(curve, rand.Reader)
   422  	if err != nil {
   423  		panic(err)
   424  	}
   425  
   426  	if Verify(&privKey.PublicKey, make([]byte, 64), big.NewInt(0), big.NewInt(0)) {
   427  		t.Errorf("Verify with r,s=0 succeeded: %T", curve)
   428  	}
   429  }
   430  
   431  func TestNegativeSignature(t *testing.T) {
   432  	testAllCurves(t, testNegativeSignature)
   433  }
   434  
   435  func testNegativeSignature(t *testing.T, curve elliptic.Curve) {
   436  	zeroHash := make([]byte, 64)
   437  
   438  	privKey, err := GenerateKey(curve, rand.Reader)
   439  	if err != nil {
   440  		panic(err)
   441  	}
   442  	r, s, err := Sign(rand.Reader, privKey, zeroHash)
   443  	if err != nil {
   444  		panic(err)
   445  	}
   446  
   447  	r = r.Neg(r)
   448  	if Verify(&privKey.PublicKey, zeroHash, r, s) {
   449  		t.Errorf("Verify with r=-r succeeded: %T", curve)
   450  	}
   451  }
   452  
   453  func TestRPlusNSignature(t *testing.T) {
   454  	testAllCurves(t, testRPlusNSignature)
   455  }
   456  
   457  func testRPlusNSignature(t *testing.T, curve elliptic.Curve) {
   458  	zeroHash := make([]byte, 64)
   459  
   460  	privKey, err := GenerateKey(curve, rand.Reader)
   461  	if err != nil {
   462  		panic(err)
   463  	}
   464  	r, s, err := Sign(rand.Reader, privKey, zeroHash)
   465  	if err != nil {
   466  		panic(err)
   467  	}
   468  
   469  	r = r.Add(r, curve.Params().N)
   470  	if Verify(&privKey.PublicKey, zeroHash, r, s) {
   471  		t.Errorf("Verify with r=r+n succeeded: %T", curve)
   472  	}
   473  }
   474  
   475  func TestRMinusNSignature(t *testing.T) {
   476  	testAllCurves(t, testRMinusNSignature)
   477  }
   478  
   479  func testRMinusNSignature(t *testing.T, curve elliptic.Curve) {
   480  	zeroHash := make([]byte, 64)
   481  
   482  	privKey, err := GenerateKey(curve, rand.Reader)
   483  	if err != nil {
   484  		panic(err)
   485  	}
   486  	r, s, err := Sign(rand.Reader, privKey, zeroHash)
   487  	if err != nil {
   488  		panic(err)
   489  	}
   490  
   491  	r = r.Sub(r, curve.Params().N)
   492  	if Verify(&privKey.PublicKey, zeroHash, r, s) {
   493  		t.Errorf("Verify with r=r-n succeeded: %T", curve)
   494  	}
   495  }
   496  
   497  func randomPointForCurve(curve elliptic.Curve, rand io.Reader) error {
   498  	switch curve.Params() {
   499  	case elliptic.P224().Params():
   500  		_, _, err := randomPoint(p224(), rand)
   501  		return err
   502  	case elliptic.P256().Params():
   503  		_, _, err := randomPoint(p256(), rand)
   504  		return err
   505  	case elliptic.P384().Params():
   506  		_, _, err := randomPoint(p384(), rand)
   507  		return err
   508  	case elliptic.P521().Params():
   509  		_, _, err := randomPoint(p521(), rand)
   510  		return err
   511  	default:
   512  		panic("unknown curve")
   513  	}
   514  }
   515  
   516  func benchmarkAllCurves(b *testing.B, f func(*testing.B, elliptic.Curve)) {
   517  	tests := []struct {
   518  		name  string
   519  		curve elliptic.Curve
   520  	}{
   521  		{"P256", elliptic.P256()},
   522  		{"P384", elliptic.P384()},
   523  		{"P521", elliptic.P521()},
   524  	}
   525  	for _, test := range tests {
   526  		curve := test.curve
   527  		b.Run(test.name, func(b *testing.B) {
   528  			f(b, curve)
   529  		})
   530  	}
   531  }
   532  
   533  func BenchmarkSign(b *testing.B) {
   534  	benchmarkAllCurves(b, func(b *testing.B, curve elliptic.Curve) {
   535  		r := bufio.NewReaderSize(rand.Reader, 1<<15)
   536  		priv, err := GenerateKey(curve, r)
   537  		if err != nil {
   538  			b.Fatal(err)
   539  		}
   540  		hashed := []byte("testing")
   541  
   542  		b.ReportAllocs()
   543  		b.ResetTimer()
   544  		for i := 0; i < b.N; i++ {
   545  			sig, err := SignASN1(r, priv, hashed)
   546  			if err != nil {
   547  				b.Fatal(err)
   548  			}
   549  			// Prevent the compiler from optimizing out the operation.
   550  			hashed[0] = sig[0]
   551  		}
   552  	})
   553  }
   554  
   555  func BenchmarkVerify(b *testing.B) {
   556  	benchmarkAllCurves(b, func(b *testing.B, curve elliptic.Curve) {
   557  		r := bufio.NewReaderSize(rand.Reader, 1<<15)
   558  		priv, err := GenerateKey(curve, r)
   559  		if err != nil {
   560  			b.Fatal(err)
   561  		}
   562  		hashed := []byte("testing")
   563  		sig, err := SignASN1(r, priv, hashed)
   564  		if err != nil {
   565  			b.Fatal(err)
   566  		}
   567  
   568  		b.ReportAllocs()
   569  		b.ResetTimer()
   570  		for i := 0; i < b.N; i++ {
   571  			if !VerifyASN1(&priv.PublicKey, hashed, sig) {
   572  				b.Fatal("verify failed")
   573  			}
   574  		}
   575  	})
   576  }
   577  
   578  func BenchmarkGenerateKey(b *testing.B) {
   579  	benchmarkAllCurves(b, func(b *testing.B, curve elliptic.Curve) {
   580  		r := bufio.NewReaderSize(rand.Reader, 1<<15)
   581  		b.ReportAllocs()
   582  		b.ResetTimer()
   583  		for i := 0; i < b.N; i++ {
   584  			if _, err := GenerateKey(curve, r); err != nil {
   585  				b.Fatal(err)
   586  			}
   587  		}
   588  	})
   589  }
   590
View as plain text