Source file src/github.com/decred/dcrd/dcrec/secp256k1/v4/curve_test.go

Documentation: github.com/decred/dcrd/dcrec/secp256k1/v4

     1  // Copyright (c) 2015-2024 The Decred developers
     2  // Copyright 2013-2016 The btcsuite developers
     3  // Use of this source code is governed by an ISC
     4  // license that can be found in the LICENSE file.
     5  
     6  package secp256k1
     7  
     8  import (
     9  	"fmt"
    10  	"math/big"
    11  	"math/bits"
    12  	mrand "math/rand"
    13  	"testing"
    14  	"time"
    15  )
    16  
    17  var (
    18  	// oneModN is simply the number 1 as a mod n scalar.
    19  	oneModN = hexToModNScalar("1")
    20  
    21  	// endoLambda is the positive version of the lambda constant used in the
    22  	// endomorphism.  It is stored here for convenience and to avoid recomputing
    23  	// it throughout the tests.
    24  	endoLambda = new(ModNScalar).NegateVal(endoNegLambda)
    25  )
    26  
    27  // isValidJacobianPoint returns true if the point (x,y,z) is on the secp256k1
    28  // curve or is the point at infinity.
    29  func isValidJacobianPoint(point *JacobianPoint) bool {
    30  	if (point.X.IsZero() && point.Y.IsZero()) || point.Z.IsZero() {
    31  		return true
    32  	}
    33  
    34  	// Elliptic curve equation for secp256k1 is: y^2 = x^3 + 7
    35  	// In Jacobian coordinates, Y = y/z^3 and X = x/z^2
    36  	// Thus:
    37  	// (y/z^3)^2 = (x/z^2)^3 + 7
    38  	// y^2/z^6 = x^3/z^6 + 7
    39  	// y^2 = x^3 + 7*z^6
    40  	var y2, z2, x3, result FieldVal
    41  	y2.SquareVal(&point.Y).Normalize()
    42  	z2.SquareVal(&point.Z)
    43  	x3.SquareVal(&point.X).Mul(&point.X)
    44  	result.SquareVal(&z2).Mul(&z2).MulInt(7).Add(&x3).Normalize()
    45  	return y2.Equals(&result)
    46  }
    47  
    48  // jacobianPointFromHex decodes the passed big-endian hex strings into a
    49  // Jacobian point with its internal fields set to the resulting values.  Only
    50  // the first 32-bytes are used.
    51  func jacobianPointFromHex(x, y, z string) JacobianPoint {
    52  	var p JacobianPoint
    53  	p.X.SetHex(x)
    54  	p.Y.SetHex(y)
    55  	p.Z.SetHex(z)
    56  	return p
    57  }
    58  
    59  // IsStrictlyEqual returns whether or not the two Jacobian points are strictly
    60  // equal for use in the tests.  Recall that several Jacobian points can be equal
    61  // in affine coordinates, while not having the same coordinates in projective
    62  // space, so the two points not being equal doesn't necessarily mean they aren't
    63  // actually the same affine point.
    64  func (p *JacobianPoint) IsStrictlyEqual(other *JacobianPoint) bool {
    65  	return p.X.Equals(&other.X) && p.Y.Equals(&other.Y) && p.Z.Equals(&other.Z)
    66  }
    67  
    68  // TestAddJacobian tests addition of points projected in Jacobian coordinates
    69  // works as intended.
    70  func TestAddJacobian(t *testing.T) {
    71  	tests := []struct {
    72  		name       string // test description
    73  		x1, y1, z1 string // hex encoded coordinates of first point to add
    74  		x2, y2, z2 string // hex encoded coordinates of second point to add
    75  		x3, y3, z3 string // hex encoded coordinates of expected point
    76  	}{{
    77  		// Addition with the point at infinity (left hand side).
    78  		name: "∞ + P = P",
    79  		x1:   "0",
    80  		y1:   "0",
    81  		z1:   "0",
    82  		x2:   "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
    83  		y2:   "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
    84  		z2:   "1",
    85  		x3:   "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
    86  		y3:   "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
    87  		z3:   "1",
    88  	}, {
    89  		// Addition with the point at infinity (right hand side).
    90  		name: "P + ∞ = P",
    91  		x1:   "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
    92  		y1:   "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
    93  		z1:   "1",
    94  		x2:   "0",
    95  		y2:   "0",
    96  		z2:   "0",
    97  		x3:   "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
    98  		y3:   "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
    99  		z3:   "1",
   100  	}, {
   101  		// Addition with z1=z2=1 different x values.
   102  		name: "P(x1, y1, 1) + P(x2, y1, 1)",
   103  		x1:   "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
   104  		y1:   "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
   105  		z1:   "1",
   106  		x2:   "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
   107  		y2:   "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
   108  		z2:   "1",
   109  		x3:   "0cfbc7da1e569b334460788faae0286e68b3af7379d5504efc25e4dba16e46a6",
   110  		y3:   "e205f79361bbe0346b037b4010985dbf4f9e1e955e7d0d14aca876bfa79aad87",
   111  		z3:   "44a5646b446e3877a648d6d381370d9ef55a83b666ebce9df1b1d7d65b817b2f",
   112  	}, {
   113  		// Addition with z1=z2=1 same x opposite y.
   114  		name: "P(x, y, 1) + P(x, -y, 1) = ∞",
   115  		x1:   "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
   116  		y1:   "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
   117  		z1:   "1",
   118  		x2:   "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
   119  		y2:   "f48e156428cf0276dc092da5856e182288d7569f97934a56fe44be60f0d359fd",
   120  		z2:   "1",
   121  		x3:   "0",
   122  		y3:   "0",
   123  		z3:   "0",
   124  	}, {
   125  		// Addition with z1=z2=1 same point.
   126  		name: "P(x, y, 1) + P(x, y, 1) = 2P",
   127  		x1:   "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
   128  		y1:   "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
   129  		z1:   "1",
   130  		x2:   "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
   131  		y2:   "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
   132  		z2:   "1",
   133  		x3:   "ec9f153b13ee7bd915882859635ea9730bf0dc7611b2c7b0e37ee64f87c50c27",
   134  		y3:   "b082b53702c466dcf6e984a35671756c506c67c2fcb8adb408c44dd0755c8f2a",
   135  		z3:   "16e3d537ae61fb1247eda4b4f523cfbaee5152c0d0d96b520376833c1e594464",
   136  	}, {
   137  		// Addition with z1=z2 (!=1) different x values.
   138  		name: "P(x1, y1, 2) + P(x2, y2, 2)",
   139  		x1:   "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
   140  		y1:   "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
   141  		z1:   "2",
   142  		x2:   "5d2fe112c21891d440f65a98473cb626111f8a234d2cd82f22172e369f002147",
   143  		y2:   "98e3386a0a622a35c4561ffb32308d8e1c6758e10ebb1b4ebd3d04b4eb0ecbe8",
   144  		z2:   "2",
   145  		x3:   "cfbc7da1e569b334460788faae0286e68b3af7379d5504efc25e4dba16e46a60",
   146  		y3:   "817de4d86ef80d1ac0ded00426176fd3e787a5579f43452b2a1db021e6ac3778",
   147  		z3:   "129591ad11b8e1de99235b4e04dc367bd56a0ed99baf3a77c6c75f5a6e05f08d",
   148  	}, {
   149  		// Addition with z1=z2 (!=1) same x opposite y.
   150  		name: "P(x, y, 2) + P(x, -y, 2) = ∞",
   151  		x1:   "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
   152  		y1:   "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
   153  		z1:   "2",
   154  		x2:   "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
   155  		y2:   "a470ab21467813b6e0496d2c2b70c11446bab4fcbc9a52b7f225f30e869aea9f",
   156  		z2:   "2",
   157  		x3:   "0",
   158  		y3:   "0",
   159  		z3:   "0",
   160  	}, {
   161  		// Addition with z1=z2 (!=1) same point.
   162  		name: "P(x, y, 2) + P(x, y, 2) = 2P",
   163  		x1:   "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
   164  		y1:   "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
   165  		z1:   "2",
   166  		x2:   "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
   167  		y2:   "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
   168  		z2:   "2",
   169  		x3:   "9f153b13ee7bd915882859635ea9730bf0dc7611b2c7b0e37ee65073c50fabac",
   170  		y3:   "2b53702c466dcf6e984a35671756c506c67c2fcb8adb408c44dd125dc91cb988",
   171  		z3:   "6e3d537ae61fb1247eda4b4f523cfbaee5152c0d0d96b520376833c2e5944a11",
   172  	}, {
   173  		// Addition with z1!=z2 and z2=1 different x values.
   174  		name: "P(x1, y1, 2) + P(x2, y2, 1)",
   175  		x1:   "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
   176  		y1:   "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
   177  		z1:   "2",
   178  		x2:   "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
   179  		y2:   "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
   180  		z2:   "1",
   181  		x3:   "3ef1f68795a6ccd1181e23eab80a1b9a2cebdcde755413bf097936eb5b91b4f3",
   182  		y3:   "0bef26c377c068d606f6802130bb7e9f3c3d2abcfa1a295950ed81133561cb04",
   183  		z3:   "252b235a2371c3bd3246b69c09b86cf7aad41db3375e74ef8d8ebeb4dc0be11a",
   184  	}, {
   185  		// Addition with z1!=z2 and z2=1 same x opposite y.
   186  		name: "P(x, y, 2) + P(x, -y, 1) = ∞",
   187  		x1:   "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
   188  		y1:   "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
   189  		z1:   "2",
   190  		x2:   "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
   191  		y2:   "f48e156428cf0276dc092da5856e182288d7569f97934a56fe44be60f0d359fd",
   192  		z2:   "1",
   193  		x3:   "0",
   194  		y3:   "0",
   195  		z3:   "0",
   196  	}, {
   197  		// Addition with z1!=z2 and z2=1 same point.
   198  		name: "P(x, y, 2) + P(x, y, 1) = 2P",
   199  		x1:   "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
   200  		y1:   "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
   201  		z1:   "2",
   202  		x2:   "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
   203  		y2:   "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
   204  		z2:   "1",
   205  		x3:   "9f153b13ee7bd915882859635ea9730bf0dc7611b2c7b0e37ee65073c50fabac",
   206  		y3:   "2b53702c466dcf6e984a35671756c506c67c2fcb8adb408c44dd125dc91cb988",
   207  		z3:   "6e3d537ae61fb1247eda4b4f523cfbaee5152c0d0d96b520376833c2e5944a11",
   208  	}, {
   209  		// Addition with z1!=z2 and z2!=1 different x values.
   210  		name: "P(x1, y1, 2) + P(x2, y2, 3)",
   211  		x1:   "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
   212  		y1:   "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
   213  		z1:   "2",
   214  		x2:   "91abba6a34b7481d922a4bd6a04899d5a686f6cf6da4e66a0cb427fb25c04bd4",
   215  		y2:   "03fede65e30b4e7576a2abefc963ddbf9fdccbf791b77c29beadefe49951f7d1",
   216  		z2:   "3",
   217  		x3:   "3f07081927fd3f6dadd4476614c89a09eba7f57c1c6c3b01fa2d64eac1eef31e",
   218  		y3:   "949166e04ebc7fd95a9d77e5dfd88d1492ecffd189792e3944eb2b765e09e031",
   219  		z3:   "eb8cba81bcffa4f44d75427506737e1f045f21e6d6f65543ee0e1d163540c931",
   220  	}, {
   221  		// Addition with z1!=z2 and z2!=1 same x opposite y.
   222  		name: "P(x, y, 2) + P(x, -y, 3) = ∞",
   223  		x1:   "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
   224  		y1:   "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
   225  		z1:   "2",
   226  		x2:   "dcc3768780c74a0325e2851edad0dc8a566fa61a9e7fc4a34d13dcb509f99bc7",
   227  		y2:   "cafc41904dd5428934f7d075129c8ba46eb622d4fc88d72cd1401452664add18",
   228  		z2:   "3",
   229  		x3:   "0",
   230  		y3:   "0",
   231  		z3:   "0",
   232  	}, {
   233  		// Addition with z1!=z2 and z2!=1 same point.
   234  		name: "P(x, y, 2) + P(x, y, 3) = 2P",
   235  		x1:   "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
   236  		y1:   "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
   237  		z1:   "2",
   238  		x2:   "dcc3768780c74a0325e2851edad0dc8a566fa61a9e7fc4a34d13dcb509f99bc7",
   239  		y2:   "3503be6fb22abd76cb082f8aed63745b9149dd2b037728d32ebfebac99b51f17",
   240  		z2:   "3",
   241  		x3:   "9f153b13ee7bd915882859635ea9730bf0dc7611b2c7b0e37ee65073c50fabac",
   242  		y3:   "2b53702c466dcf6e984a35671756c506c67c2fcb8adb408c44dd125dc91cb988",
   243  		z3:   "6e3d537ae61fb1247eda4b4f523cfbaee5152c0d0d96b520376833c2e5944a11",
   244  	}}
   245  
   246  	for _, test := range tests {
   247  		// Convert hex to Jacobian points.
   248  		p1 := jacobianPointFromHex(test.x1, test.y1, test.z1)
   249  		p2 := jacobianPointFromHex(test.x2, test.y2, test.z2)
   250  		want := jacobianPointFromHex(test.x3, test.y3, test.z3)
   251  
   252  		// Ensure the test data is using points that are actually on the curve
   253  		// (or the point at infinity).
   254  		if !isValidJacobianPoint(&p1) {
   255  			t.Errorf("%s: first point is not on the curve", test.name)
   256  			continue
   257  		}
   258  		if !isValidJacobianPoint(&p2) {
   259  			t.Errorf("%s: second point is not on the curve", test.name)
   260  			continue
   261  		}
   262  		if !isValidJacobianPoint(&want) {
   263  			t.Errorf("%s: expected point is not on the curve", test.name)
   264  			continue
   265  		}
   266  
   267  		// Add the two points.
   268  		var r JacobianPoint
   269  		AddNonConst(&p1, &p2, &r)
   270  
   271  		// Ensure result matches expected.
   272  		if !r.IsStrictlyEqual(&want) {
   273  			t.Errorf("%s: wrong result\ngot: (%v, %v, %v)\nwant: (%v, %v, %v)",
   274  				test.name, r.X, r.Y, r.Z, want.X, want.Y, want.Z)
   275  			continue
   276  		}
   277  	}
   278  }
   279  
   280  // TestDoubleJacobian tests doubling of points projected in Jacobian coordinates
   281  // works as intended for some edge cases and known good values.
   282  func TestDoubleJacobian(t *testing.T) {
   283  	tests := []struct {
   284  		name       string // test description
   285  		x1, y1, z1 string // hex encoded coordinates of point to double
   286  		x3, y3, z3 string // hex encoded coordinates of expected point
   287  	}{{
   288  		// Doubling the point at infinity is still infinity.
   289  		name: "2*∞ = ∞ (point at infinity)",
   290  		x1:   "0",
   291  		y1:   "0",
   292  		z1:   "0",
   293  		x3:   "0",
   294  		y3:   "0",
   295  		z3:   "0",
   296  	}, {
   297  		// Doubling with z1=1.
   298  		name: "2*P(x, y, 1)",
   299  		x1:   "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
   300  		y1:   "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
   301  		z1:   "1",
   302  		x3:   "ec9f153b13ee7bd915882859635ea9730bf0dc7611b2c7b0e37ee64f87c50c27",
   303  		y3:   "b082b53702c466dcf6e984a35671756c506c67c2fcb8adb408c44dd0755c8f2a",
   304  		z3:   "16e3d537ae61fb1247eda4b4f523cfbaee5152c0d0d96b520376833c1e594464",
   305  	}, {
   306  		// Doubling with z1!=1.
   307  		name: "2*P(x, y, 2)",
   308  		x1:   "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
   309  		y1:   "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
   310  		z1:   "2",
   311  		x3:   "9f153b13ee7bd915882859635ea9730bf0dc7611b2c7b0e37ee65073c50fabac",
   312  		y3:   "2b53702c466dcf6e984a35671756c506c67c2fcb8adb408c44dd125dc91cb988",
   313  		z3:   "6e3d537ae61fb1247eda4b4f523cfbaee5152c0d0d96b520376833c2e5944a11",
   314  	}, {
   315  		// From btcd issue #709.
   316  		name: "carry to bit 256 during normalize",
   317  		x1:   "201e3f75715136d2f93c4f4598f91826f94ca01f4233a5bd35de9708859ca50d",
   318  		y1:   "bdf18566445e7562c6ada68aef02d498d7301503de5b18c6aef6e2b1722412e1",
   319  		z1:   "0000000000000000000000000000000000000000000000000000000000000001",
   320  		x3:   "4a5e0559863ebb4e9ed85f5c4fa76003d05d9a7626616e614a1f738621e3c220",
   321  		y3:   "00000000000000000000000000000000000000000000000000000001b1388778",
   322  		z3:   "7be30acc88bceac58d5b4d15de05a931ae602a07bcb6318d5dedc563e4482993",
   323  	}}
   324  
   325  	for _, test := range tests {
   326  		// Convert hex to field values.
   327  		p1 := jacobianPointFromHex(test.x1, test.y1, test.z1)
   328  		want := jacobianPointFromHex(test.x3, test.y3, test.z3)
   329  
   330  		// Ensure the test data is using points that are actually on the curve
   331  		// (or the point at infinity).
   332  		if !isValidJacobianPoint(&p1) {
   333  			t.Errorf("%s: first point is not on the curve", test.name)
   334  			continue
   335  		}
   336  		if !isValidJacobianPoint(&want) {
   337  			t.Errorf("%s: expected point is not on the curve", test.name)
   338  			continue
   339  		}
   340  
   341  		// Double the point.
   342  		var result JacobianPoint
   343  		DoubleNonConst(&p1, &result)
   344  
   345  		// Ensure result matches expected.
   346  		if !result.IsStrictlyEqual(&want) {
   347  			t.Errorf("%s: wrong result\ngot: (%v, %v, %v)\nwant: (%v, %v, %v)",
   348  				test.name, result.X, result.Y, result.Z, want.X, want.Y,
   349  				want.Z)
   350  			continue
   351  		}
   352  	}
   353  }
   354  
   355  // checkNAFEncoding returns an error if the provided positive and negative
   356  // portions of an overall NAF encoding do not adhere to the requirements or they
   357  // do not sum back to the provided original value.
   358  func checkNAFEncoding(pos, neg []byte, origValue *big.Int) error {
   359  	// NAF must not have a leading zero byte and the number of negative
   360  	// bytes must not exceed the positive portion.
   361  	if len(pos) > 0 && pos[0] == 0 {
   362  		return fmt.Errorf("positive has leading zero -- got %x", pos)
   363  	}
   364  	if len(neg) > len(pos) {
   365  		return fmt.Errorf("negative has len %d > pos len %d", len(neg),
   366  			len(pos))
   367  	}
   368  
   369  	// Ensure the result doesn't have any adjacent non-zero digits.
   370  	gotPos := new(big.Int).SetBytes(pos)
   371  	gotNeg := new(big.Int).SetBytes(neg)
   372  	posOrNeg := new(big.Int).Or(gotPos, gotNeg)
   373  	prevBit := posOrNeg.Bit(0)
   374  	for bit := 1; bit < posOrNeg.BitLen(); bit++ {
   375  		thisBit := posOrNeg.Bit(bit)
   376  		if prevBit == 1 && thisBit == 1 {
   377  			return fmt.Errorf("adjacent non-zero digits found at bit pos %d",
   378  				bit-1)
   379  		}
   380  		prevBit = thisBit
   381  	}
   382  
   383  	// Ensure the resulting positive and negative portions of the overall
   384  	// NAF representation sum back to the original value.
   385  	gotValue := new(big.Int).Sub(gotPos, gotNeg)
   386  	if origValue.Cmp(gotValue) != 0 {
   387  		return fmt.Errorf("pos-neg is not original value: got %x, want %x",
   388  			gotValue, origValue)
   389  	}
   390  
   391  	return nil
   392  }
   393  
   394  // TestNAF ensures encoding various edge cases and values to non-adjacent form
   395  // produces valid results.
   396  func TestNAF(t *testing.T) {
   397  	tests := []struct {
   398  		name string // test description
   399  		in   string // hex encoded test value
   400  	}{{
   401  		name: "empty is zero",
   402  		in:   "",
   403  	}, {
   404  		name: "zero",
   405  		in:   "00",
   406  	}, {
   407  		name: "just before first carry",
   408  		in:   "aa",
   409  	}, {
   410  		name: "first carry",
   411  		in:   "ab",
   412  	}, {
   413  		name: "leading zeroes",
   414  		in:   "002f20569b90697ad471c1be6107814f53f47446be298a3a2a6b686b97d35cf9",
   415  	}, {
   416  		name: "257 bits when NAF encoded",
   417  		in:   "c000000000000000000000000000000000000000000000000000000000000001",
   418  	}, {
   419  		name: "32-byte scalar",
   420  		in:   "6df2b5d30854069ccdec40ae022f5c948936324a4e9ebed8eb82cfd5a6b6d766",
   421  	}, {
   422  		name: "first term of balanced length-two representation #1",
   423  		in:   "b776e53fb55f6b006a270d42d64ec2b1",
   424  	}, {
   425  		name: "second term balanced length-two representation #1",
   426  		in:   "d6cc32c857f1174b604eefc544f0c7f7",
   427  	}, {
   428  		name: "first term of balanced length-two representation #2",
   429  		in:   "45c53aa1bb56fcd68c011e2dad6758e4",
   430  	}, {
   431  		name: "second term of balanced length-two representation #2",
   432  		in:   "a2e79d200f27f2360fba57619936159b",
   433  	}}
   434  
   435  	for _, test := range tests {
   436  		// Ensure the resulting positive and negative portions of the overall
   437  		// NAF representation adhere to the requirements of NAF encoding and
   438  		// they sum back to the original value.
   439  		result := naf(hexToBytes(test.in))
   440  		pos, neg := result.Pos(), result.Neg()
   441  		if err := checkNAFEncoding(pos, neg, fromHex(test.in)); err != nil {
   442  			t.Errorf("%q: %v", test.name, err)
   443  		}
   444  	}
   445  }
   446  
   447  // TestNAFRandom ensures that encoding randomly-generated values to non-adjacent
   448  // form produces valid results.
   449  func TestNAFRandom(t *testing.T) {
   450  	// Use a unique random seed each test instance and log it if the tests fail.
   451  	seed := time.Now().Unix()
   452  	rng := mrand.New(mrand.NewSource(seed))
   453  	defer func(t *testing.T, seed int64) {
   454  		if t.Failed() {
   455  			t.Logf("random seed: %d", seed)
   456  		}
   457  	}(t, seed)
   458  
   459  	for i := 0; i < 100; i++ {
   460  		// Ensure the resulting positive and negative portions of the overall
   461  		// NAF representation adhere to the requirements of NAF encoding and
   462  		// they sum back to the original value.
   463  		bigIntVal, modNVal := randIntAndModNScalar(t, rng)
   464  		valBytes := modNVal.Bytes()
   465  		result := naf(valBytes[:])
   466  		pos, neg := result.Pos(), result.Neg()
   467  		if err := checkNAFEncoding(pos, neg, bigIntVal); err != nil {
   468  			t.Fatalf("encoding err: %v\nin: %x\npos: %x\nneg: %x", err,
   469  				bigIntVal, pos, neg)
   470  		}
   471  	}
   472  }
   473  
   474  // TestScalarBaseMultJacobian ensures multiplying a given scalar by the base
   475  // point projected in Jacobian coordinates works as intended for some edge cases
   476  // and known values.  It also verifies in affine coordinates as well.
   477  func TestScalarBaseMultJacobian(t *testing.T) {
   478  	tests := []struct {
   479  		name       string // test description
   480  		k          string // hex encoded scalar
   481  		x1, y1, z1 string // hex encoded Jacobian coordinates of expected point
   482  		x2, y2     string // hex encoded affine coordinates of expected point
   483  	}{{
   484  		name: "zero",
   485  		k:    "0000000000000000000000000000000000000000000000000000000000000000",
   486  		x1:   "0000000000000000000000000000000000000000000000000000000000000000",
   487  		y1:   "0000000000000000000000000000000000000000000000000000000000000000",
   488  		z1:   "0000000000000000000000000000000000000000000000000000000000000001",
   489  		x2:   "0000000000000000000000000000000000000000000000000000000000000000",
   490  		y2:   "0000000000000000000000000000000000000000000000000000000000000000",
   491  	}, {
   492  		name: "one (aka 1*G = G)",
   493  		k:    "0000000000000000000000000000000000000000000000000000000000000001",
   494  		x1:   "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798",
   495  		y1:   "483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8",
   496  		z1:   "0000000000000000000000000000000000000000000000000000000000000001",
   497  		x2:   "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798",
   498  		y2:   "483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8",
   499  	}, {
   500  		name: "group order - 1 (aka -1*G = -G)",
   501  		k:    "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
   502  		x1:   "667d5346809ba7602db1ea0bd990eee6ff75d7a64004d563534123e6f12a12d7",
   503  		y1:   "344f2f772f8f4cbd04709dba7837ff1422db8fa6f99a00f93852de2c45284838",
   504  		z1:   "19e5a058ef4eaada40d19063917bb4dc07f50c3a0f76bd5348a51057a3721c57",
   505  		x2:   "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798",
   506  		y2:   "b7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777",
   507  	}, {
   508  		name: "known good point 1",
   509  		k:    "aa5e28d6a97a2479a65527f7290311a3624d4cc0fa1578598ee3c2613bf99522",
   510  		x1:   "5f64fd9364bac24dc32bc01b7d63aaa8249babbdc26b03233e14120840ae20f6",
   511  		y1:   "a4ced9be1e1ed6ef73bec6866c3adc0695347303c30b814fb0dfddb3a22b090d",
   512  		z1:   "931a3477a1b1d866842b22577618e134c89ba12e5bb38c465265c8a2cefa69dc",
   513  		x2:   "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
   514  		y2:   "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
   515  	}, {
   516  		name: "known good point 2",
   517  		k:    "7e2b897b8cebc6361663ad410835639826d590f393d90a9538881735256dfae3",
   518  		x1:   "c2cb761af4d6410bea0ed7d5f3c7397b63739b0f37e5c3047f8a45537a9d413e",
   519  		y1:   "34b9204c55336d2fb94e20e53d5aa2ffe4da6f80d72315b4dcafca11e7c0f768",
   520  		z1:   "ca5d9e8024575c80fe185416ff4736aff8278873da60cf101d10ab49780ee33b",
   521  		x2:   "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
   522  		y2:   "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
   523  	}, {
   524  		name: "known good point 3",
   525  		k:    "6461e6df0fe7dfd05329f41bf771b86578143d4dd1f7866fb4ca7e97c5fa945d",
   526  		x1:   "09160b87ee751ef9fd51db49afc7af9c534917fad72bf461d21fec2590878267",
   527  		y1:   "dbc2757c5038e0b059d1e05c2d3706baf1a164e3836a02c240173b22c92da7c0",
   528  		z1:   "c157ea3f784c37603d9f55e661dd1d6b8759fccbfb2c8cf64c46529d94c8c950",
   529  		x2:   "e8aecc370aedd953483719a116711963ce201ac3eb21d3f3257bb48668c6a72f",
   530  		y2:   "c25caf2f0eba1ddb2f0f3f47866299ef907867b7d27e95b3873bf98397b24ee1",
   531  	}, {
   532  		name: "known good point 4",
   533  		k:    "376a3a2cdcd12581efff13ee4ad44c4044b8a0524c42422a7e1e181e4deeccec",
   534  		x1:   "7820c46de3b5a0202bea06870013fcb23adb4a000f89d5b86fe1df24be58fa79",
   535  		y1:   "95e5a977eb53a582677ff0432eef5bc66f1dd983c3e8c07e1c77c3655542c31e",
   536  		z1:   "7d71ecfdfa66b003fe96f925b5907f67a1a4a6489f4940ec3b78edbbf847334f",
   537  		x2:   "14890e61fcd4b0bd92e5b36c81372ca6fed471ef3aa60a3e415ee4fe987daba1",
   538  		y2:   "297b858d9f752ab42d3bca67ee0eb6dcd1c2b7b0dbe23397e66adc272263f982",
   539  	}, {
   540  		name: "known good point 5",
   541  		k:    "1b22644a7be026548810c378d0b2994eefa6d2b9881803cb02ceff865287d1b9",
   542  		x1:   "68a934fa2d28fb0b0d2b6801a9335d62e65acef9467be2ea67f5b11614b59c78",
   543  		y1:   "5edd7491e503acf61ed651a10cf466de06bf5c6ba285a7a2885a384bbdd32898",
   544  		z1:   "f3b28d36c3132b6f4bd66bf0da64b8dc79d66f9a854ba8b609558b6328796755",
   545  		x2:   "f73c65ead01c5126f28f442d087689bfa08e12763e0cec1d35b01751fd735ed3",
   546  		y2:   "f449a8376906482a84ed01479bd18882b919c140d638307f0c0934ba12590bde",
   547  	}}
   548  
   549  	for _, test := range tests {
   550  		// Parse test data.
   551  		want := jacobianPointFromHex(test.x1, test.y1, test.z1)
   552  		wantAffine := jacobianPointFromHex(test.x2, test.y2, "01")
   553  		k := hexToModNScalar(test.k)
   554  
   555  		// Ensure the test data is using points that are actually on the curve
   556  		// (or the point at infinity).
   557  		if !isValidJacobianPoint(&want) {
   558  			t.Errorf("%q: expected point is not on the curve", test.name)
   559  			continue
   560  		}
   561  		if !isValidJacobianPoint(&wantAffine) {
   562  			t.Errorf("%q: expected affine point is not on the curve", test.name)
   563  			continue
   564  		}
   565  
   566  		// Ensure the result matches the expected value in Jacobian coordinates.
   567  		var r JacobianPoint
   568  		scalarBaseMultNonConstFast(k, &r)
   569  		if !r.IsStrictlyEqual(&want) {
   570  			t.Errorf("%q: wrong result:\ngot: (%s, %s, %s)\nwant: (%s, %s, %s)",
   571  				test.name, r.X, r.Y, r.Z, want.X, want.Y, want.Z)
   572  			continue
   573  		}
   574  
   575  		// Ensure the result matches the expected value in affine coordinates.
   576  		r.ToAffine()
   577  		if !r.IsStrictlyEqual(&wantAffine) {
   578  			t.Errorf("%q: wrong affine result:\ngot: (%s, %s)\nwant: (%s, %s)",
   579  				test.name, r.X, r.Y, wantAffine.X, wantAffine.Y)
   580  			continue
   581  		}
   582  
   583  		// The slow fallback doesn't return identical Jacobian coordinates,
   584  		// but the affine coordinates should match.
   585  		scalarBaseMultNonConstSlow(k, &r)
   586  		r.ToAffine()
   587  		if !r.IsStrictlyEqual(&wantAffine) {
   588  			t.Errorf("%q: wrong affine result:\ngot: (%s, %s)\nwant: (%s, %s)",
   589  				test.name, r.X, r.Y, wantAffine.X, wantAffine.Y)
   590  			continue
   591  		}
   592  	}
   593  }
   594  
   595  // modNBitLen returns the minimum number of bits required to represent the mod n
   596  // scalar.  The result is 0 when the value is 0.
   597  func modNBitLen(s *ModNScalar) uint16 {
   598  	if w := s.n[7]; w > 0 {
   599  		return uint16(bits.Len32(w)) + 224
   600  	}
   601  	if w := s.n[6]; w > 0 {
   602  		return uint16(bits.Len32(w)) + 192
   603  	}
   604  	if w := s.n[5]; w > 0 {
   605  		return uint16(bits.Len32(w)) + 160
   606  	}
   607  	if w := s.n[4]; w > 0 {
   608  		return uint16(bits.Len32(w)) + 128
   609  	}
   610  	if w := s.n[3]; w > 0 {
   611  		return uint16(bits.Len32(w)) + 96
   612  	}
   613  	if w := s.n[2]; w > 0 {
   614  		return uint16(bits.Len32(w)) + 64
   615  	}
   616  	if w := s.n[1]; w > 0 {
   617  		return uint16(bits.Len32(w)) + 32
   618  	}
   619  	return uint16(bits.Len32(s.n[0]))
   620  }
   621  
   622  // checkLambdaDecomposition returns an error if the provided decomposed scalars
   623  // do not satisfy the required equation or they are not small in magnitude.
   624  func checkLambdaDecomposition(origK, k1, k2 *ModNScalar) error {
   625  	// Recompose the scalar from the decomposed scalars to ensure they satisfy
   626  	// the required equation.
   627  	calcK := new(ModNScalar).Mul2(k2, endoLambda).Add(k1)
   628  	if !calcK.Equals(origK) {
   629  		return fmt.Errorf("recomposed scalar %v != orig scalar", calcK)
   630  	}
   631  
   632  	// Ensure the decomposed scalars are small in magnitude by affirming their
   633  	// bit lengths do not exceed one more than half of the bit size of the
   634  	// underlying field.  This value is max(||v1||, ||v2||), where:
   635  	//
   636  	// vector v1 = <endoA1, endoB1>
   637  	// vector v2 = <endoA2, endoB2>
   638  	const maxBitLen = 129
   639  	if k1.IsOverHalfOrder() {
   640  		k1.Negate()
   641  	}
   642  	if k2.IsOverHalfOrder() {
   643  		k2.Negate()
   644  	}
   645  	k1BitLen, k2BitLen := modNBitLen(k1), modNBitLen(k2)
   646  	if k1BitLen > maxBitLen {
   647  		return fmt.Errorf("k1 scalar bit len %d > max allowed %d",
   648  			k1BitLen, maxBitLen)
   649  	}
   650  	if k2BitLen > maxBitLen {
   651  		return fmt.Errorf("k2 scalar bit len %d > max allowed %d",
   652  			k2BitLen, maxBitLen)
   653  	}
   654  
   655  	return nil
   656  }
   657  
   658  // TestSplitK ensures decomposing various edge cases and values into a balanced
   659  // length-two representation produces valid results.
   660  func TestSplitK(t *testing.T) {
   661  	// Values computed from the group half order and lambda such that they
   662  	// exercise the decomposition edge cases and maximize the bit lengths of the
   663  	// produced scalars.
   664  	h := "7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0"
   665  	negOne := new(ModNScalar).NegateVal(oneModN)
   666  	halfOrder := hexToModNScalar(h)
   667  	halfOrderMOne := new(ModNScalar).Add2(halfOrder, negOne)
   668  	halfOrderPOne := new(ModNScalar).Add2(halfOrder, oneModN)
   669  	lambdaMOne := new(ModNScalar).Add2(endoLambda, negOne)
   670  	lambdaPOne := new(ModNScalar).Add2(endoLambda, oneModN)
   671  	negLambda := new(ModNScalar).NegateVal(endoLambda)
   672  	halfOrderMOneMLambda := new(ModNScalar).Add2(halfOrderMOne, negLambda)
   673  	halfOrderMLambda := new(ModNScalar).Add2(halfOrder, negLambda)
   674  	halfOrderPOneMLambda := new(ModNScalar).Add2(halfOrderPOne, negLambda)
   675  	lambdaPHalfOrder := new(ModNScalar).Add2(endoLambda, halfOrder)
   676  	lambdaPOnePHalfOrder := new(ModNScalar).Add2(lambdaPOne, halfOrder)
   677  
   678  	tests := []struct {
   679  		name string      // test description
   680  		k    *ModNScalar // scalar to decompose
   681  	}{{
   682  		name: "zero",
   683  		k:    new(ModNScalar),
   684  	}, {
   685  		name: "one",
   686  		k:    oneModN,
   687  	}, {
   688  		name: "group order - 1 (aka -1 mod N)",
   689  		k:    negOne,
   690  	}, {
   691  		name: "group half order - 1 - lambda",
   692  		k:    halfOrderMOneMLambda,
   693  	}, {
   694  		name: "group half order - lambda",
   695  		k:    halfOrderMLambda,
   696  	}, {
   697  		name: "group half order + 1 - lambda",
   698  		k:    halfOrderPOneMLambda,
   699  	}, {
   700  		name: "group half order - 1",
   701  		k:    halfOrderMOne,
   702  	}, {
   703  		name: "group half order",
   704  		k:    halfOrder,
   705  	}, {
   706  		name: "group half order + 1",
   707  		k:    halfOrderPOne,
   708  	}, {
   709  		name: "lambda - 1",
   710  		k:    lambdaMOne,
   711  	}, {
   712  		name: "lambda",
   713  		k:    endoLambda,
   714  	}, {
   715  		name: "lambda + 1",
   716  		k:    lambdaPOne,
   717  	}, {
   718  		name: "lambda + group half order",
   719  		k:    lambdaPHalfOrder,
   720  	}, {
   721  		name: "lambda + 1 + group half order",
   722  		k:    lambdaPOnePHalfOrder,
   723  	}}
   724  
   725  	for _, test := range tests {
   726  		// Decompose the scalar and ensure the resulting decomposition satisfies
   727  		// the required equation and consists of scalars that are small in
   728  		// magnitude.
   729  		k1, k2 := splitK(test.k)
   730  		if err := checkLambdaDecomposition(test.k, &k1, &k2); err != nil {
   731  			t.Errorf("%q: %v", test.name, err)
   732  		}
   733  	}
   734  }
   735  
   736  // TestSplitKRandom ensures that decomposing randomly-generated scalars into a
   737  // balanced length-two representation produces valid results.
   738  func TestSplitKRandom(t *testing.T) {
   739  	// Use a unique random seed each test instance and log it if the tests fail.
   740  	seed := time.Now().Unix()
   741  	rng := mrand.New(mrand.NewSource(seed))
   742  	defer func(t *testing.T, seed int64) {
   743  		if t.Failed() {
   744  			t.Logf("random seed: %d", seed)
   745  		}
   746  	}(t, seed)
   747  
   748  	for i := 0; i < 100; i++ {
   749  		// Generate a random scalar, decompose it, and ensure the resulting
   750  		// decomposition satisfies the required equation and consists of scalars
   751  		// that are small in magnitude.
   752  		origK := randModNScalar(t, rng)
   753  		k1, k2 := splitK(origK)
   754  		if err := checkLambdaDecomposition(origK, &k1, &k2); err != nil {
   755  			t.Fatalf("decomposition err: %v\nin: %v\nk1: %v\nk2: %v", err,
   756  				origK, k1, k2)
   757  		}
   758  	}
   759  }
   760  
   761  // TestScalarMultJacobianRandom ensures scalar point multiplication with points
   762  // projected into Jacobian coordinates works as intended for randomly-generated
   763  // scalars and points.
   764  func TestScalarMultJacobianRandom(t *testing.T) {
   765  	// Use a unique random seed each test instance and log it if the tests fail.
   766  	seed := time.Now().Unix()
   767  	rng := mrand.New(mrand.NewSource(seed))
   768  	defer func(t *testing.T, seed int64) {
   769  		if t.Failed() {
   770  			t.Logf("random seed: %d", seed)
   771  		}
   772  	}(t, seed)
   773  
   774  	// isSamePoint returns whether or not the two Jacobian points represent the
   775  	// same affine point without modifying the provided points.
   776  	isSamePoint := func(p1, p2 *JacobianPoint) bool {
   777  		var p1Affine, p2Affine JacobianPoint
   778  		p1Affine.Set(p1)
   779  		p1Affine.ToAffine()
   780  		p2Affine.Set(p2)
   781  		p2Affine.ToAffine()
   782  		return p1Affine.IsStrictlyEqual(&p2Affine)
   783  	}
   784  
   785  	// The overall idea is to compute the same point different ways.  The
   786  	// strategy uses two properties:
   787  	//
   788  	// 1) Compatibility of scalar multiplication with field multiplication
   789  	// 2) A point added to its negation is the point at infinity (P+(-P) = ∞)
   790  	//
   791  	// First, calculate a "chained" point by starting with the base (generator)
   792  	// point and then consecutively multiply the resulting points by a series of
   793  	// random scalars.
   794  	//
   795  	// Then, multiply the base point by the product of all of the random scalars
   796  	// and ensure the "chained" point matches.
   797  	//
   798  	// In other words:
   799  	//
   800  	// k[n]*(...*(k[2]*(k[1]*(k[0]*G)))) = (k[0]*k[1]*k[2]*...*k[n])*G
   801  	//
   802  	// Along the way, also calculate (-k)*P for each chained point and ensure it
   803  	// sums with the current point to the point at infinity.
   804  	//
   805  	// That is:
   806  	//
   807  	// k*P + ((-k)*P) = ∞
   808  	const numIterations = 1024
   809  	var infinity JacobianPoint
   810  	var chained, negChained, result JacobianPoint
   811  	var negK ModNScalar
   812  	bigAffineToJacobian(curveParams.Gx, curveParams.Gy, &chained)
   813  	product := new(ModNScalar).SetInt(1)
   814  	for i := 0; i < numIterations; i++ {
   815  		// Generate a random scalar and calculate:
   816  		//
   817  		//  P = k*P
   818  		// -P = (-k)*P
   819  		//
   820  		// Notice that this is intentionally doing the full scalar mult with -k
   821  		// as opposed to just flipping the Y coordinate in order to test scalar
   822  		// multiplication.
   823  		k := randModNScalar(t, rng)
   824  		negK.NegateVal(k)
   825  		ScalarMultNonConst(&negK, &chained, &negChained)
   826  		ScalarMultNonConst(k, &chained, &chained)
   827  
   828  		// Ensure kP + ((-k)P) = ∞.
   829  		AddNonConst(&chained, &negChained, &result)
   830  		if !isSamePoint(&result, &infinity) {
   831  			t.Fatalf("%d: expected point at infinity\ngot (%v, %v, %v)\n", i,
   832  				result.X, result.Y, result.Z)
   833  		}
   834  
   835  		product.Mul(k)
   836  	}
   837  
   838  	// Ensure the point calculated above matches the product of the scalars
   839  	// times the base point.
   840  	scalarBaseMultNonConstFast(product, &result)
   841  	if !isSamePoint(&chained, &result) {
   842  		t.Fatalf("unexpected result \ngot (%v, %v, %v)\n"+
   843  			"want (%v, %v, %v)", chained.X, chained.Y, chained.Z, result.X,
   844  			result.Y, result.Z)
   845  	}
   846  
   847  	scalarBaseMultNonConstSlow(product, &result)
   848  	if !isSamePoint(&chained, &result) {
   849  		t.Fatalf("unexpected result \ngot (%v, %v, %v)\n"+
   850  			"want (%v, %v, %v)", chained.X, chained.Y, chained.Z, result.X,
   851  			result.Y, result.Z)
   852  	}
   853  }
   854  
   855  // TestDecompressY ensures that decompressY works as expected for some edge
   856  // cases.
   857  func TestDecompressY(t *testing.T) {
   858  	tests := []struct {
   859  		name      string // test description
   860  		x         string // hex encoded x coordinate
   861  		valid     bool   // expected decompress result
   862  		wantOddY  string // hex encoded expected odd y coordinate
   863  		wantEvenY string // hex encoded expected even y coordinate
   864  	}{{
   865  		name:      "x = 0 -- not a point on the curve",
   866  		x:         "0",
   867  		valid:     false,
   868  		wantOddY:  "",
   869  		wantEvenY: "",
   870  	}, {
   871  		name:      "x = 1",
   872  		x:         "1",
   873  		valid:     true,
   874  		wantOddY:  "bde70df51939b94c9c24979fa7dd04ebd9b3572da7802290438af2a681895441",
   875  		wantEvenY: "4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee",
   876  	}, {
   877  		name:      "x = secp256k1 prime (aka 0) -- not a point on the curve",
   878  		x:         "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f",
   879  		valid:     false,
   880  		wantOddY:  "",
   881  		wantEvenY: "",
   882  	}, {
   883  		name:      "x = secp256k1 prime - 1 -- not a point on the curve",
   884  		x:         "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2e",
   885  		valid:     false,
   886  		wantOddY:  "",
   887  		wantEvenY: "",
   888  	}, {
   889  		name:      "x = secp256k1 group order",
   890  		x:         "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",
   891  		valid:     true,
   892  		wantOddY:  "670999be34f51e8894b9c14211c28801d9a70fde24b71d3753854b35d07c9a11",
   893  		wantEvenY: "98f66641cb0ae1776b463ebdee3d77fe2658f021db48e2c8ac7ab4c92f83621e",
   894  	}, {
   895  		name:      "x = secp256k1 group order - 1 -- not a point on the curve",
   896  		x:         "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
   897  		valid:     false,
   898  		wantOddY:  "",
   899  		wantEvenY: "",
   900  	}}
   901  
   902  	for _, test := range tests {
   903  		// Decompress the test odd y coordinate for the given test x coordinate
   904  		// and ensure the returned validity flag matches the expected result.
   905  		var oddY FieldVal
   906  		fx := new(FieldVal).SetHex(test.x)
   907  		valid := DecompressY(fx, true, &oddY)
   908  		if valid != test.valid {
   909  			t.Errorf("%s: unexpected valid flag -- got: %v, want: %v",
   910  				test.name, valid, test.valid)
   911  			continue
   912  		}
   913  
   914  		// Decompress the test even y coordinate for the given test x coordinate
   915  		// and ensure the returned validity flag matches the expected result.
   916  		var evenY FieldVal
   917  		valid = DecompressY(fx, false, &evenY)
   918  		if valid != test.valid {
   919  			t.Errorf("%s: unexpected valid flag -- got: %v, want: %v",
   920  				test.name, valid, test.valid)
   921  			continue
   922  		}
   923  
   924  		// Skip checks related to the y coordinate when there isn't one.
   925  		if !valid {
   926  			continue
   927  		}
   928  
   929  		// Ensure the decompressed odd Y coordinate is the expected value.
   930  		oddY.Normalize()
   931  		wantOddY := new(FieldVal).SetHex(test.wantOddY)
   932  		if !wantOddY.Equals(&oddY) {
   933  			t.Errorf("%s: mismatched odd y\ngot: %v, want: %v", test.name,
   934  				oddY, wantOddY)
   935  			continue
   936  		}
   937  
   938  		// Ensure the decompressed even Y coordinate is the expected value.
   939  		evenY.Normalize()
   940  		wantEvenY := new(FieldVal).SetHex(test.wantEvenY)
   941  		if !wantEvenY.Equals(&evenY) {
   942  			t.Errorf("%s: mismatched even y\ngot: %v, want: %v", test.name,
   943  				evenY, wantEvenY)
   944  			continue
   945  		}
   946  
   947  		// Ensure the decompressed odd y coordinate is actually odd.
   948  		if !oddY.IsOdd() {
   949  			t.Errorf("%s: odd y coordinate is even", test.name)
   950  			continue
   951  		}
   952  
   953  		// Ensure the decompressed even y coordinate is actually even.
   954  		if evenY.IsOdd() {
   955  			t.Errorf("%s: even y coordinate is odd", test.name)
   956  			continue
   957  		}
   958  	}
   959  }
   960  
   961  // TestDecompressYRandom ensures that decompressY works as expected with
   962  // randomly-generated x coordinates.
   963  func TestDecompressYRandom(t *testing.T) {
   964  	// Use a unique random seed each test instance and log it if the tests fail.
   965  	seed := time.Now().Unix()
   966  	rng := mrand.New(mrand.NewSource(seed))
   967  	defer func(t *testing.T, seed int64) {
   968  		if t.Failed() {
   969  			t.Logf("random seed: %d", seed)
   970  		}
   971  	}(t, seed)
   972  
   973  	for i := 0; i < 100; i++ {
   974  		origX := randFieldVal(t, rng)
   975  
   976  		// Calculate both corresponding y coordinates for the random x when it
   977  		// is a valid coordinate.
   978  		var oddY, evenY FieldVal
   979  		x := new(FieldVal).Set(origX)
   980  		oddSuccess := DecompressY(x, true, &oddY)
   981  		evenSuccess := DecompressY(x, false, &evenY)
   982  
   983  		// Ensure that the decompression success matches for both the even and
   984  		// odd cases depending on whether or not x is a valid coordinate.
   985  		if oddSuccess != evenSuccess {
   986  			t.Fatalf("mismatched decompress success for x = %v -- odd: %v, "+
   987  				"even: %v", x, oddSuccess, evenSuccess)
   988  		}
   989  		if !oddSuccess {
   990  			continue
   991  		}
   992  
   993  		// Ensure the x coordinate was not changed.
   994  		if !x.Equals(origX) {
   995  			t.Fatalf("x coordinate changed -- orig: %v, changed: %v", origX, x)
   996  		}
   997  
   998  		// Ensure that the resulting y coordinates match their respective
   999  		// expected oddness.
  1000  		oddY.Normalize()
  1001  		evenY.Normalize()
  1002  		if !oddY.IsOdd() {
  1003  			t.Fatalf("requested odd y is even for x = %v", x)
  1004  		}
  1005  		if evenY.IsOdd() {
  1006  			t.Fatalf("requested even y is odd for x = %v", x)
  1007  		}
  1008  
  1009  		// Ensure that the resulting x and y coordinates are actually on the
  1010  		// curve for both cases.
  1011  		if !isOnCurve(x, &oddY) {
  1012  			t.Fatalf("(%v, %v) is not a valid point", x, oddY)
  1013  		}
  1014  		if !isOnCurve(x, &evenY) {
  1015  			t.Fatalf("(%v, %v) is not a valid point", x, evenY)
  1016  		}
  1017  	}
  1018  }
  1019  

View as plain text