point_test.go

Documentation: github.com/cloudflare/circl/ecc/p384

     1  //go:build (!noasm && arm64) || (!noasm && amd64)
     2  // +build !noasm,arm64 !noasm,amd64
     3  
     4  package p384
     5  
     6  import (
     7  	"crypto/elliptic"
     8  	"crypto/rand"
     9  	"encoding/binary"
    10  	"testing"
    11  
    12  	"github.com/cloudflare/circl/internal/test"
    13  )
    14  
    15  func randomAffine() *affinePoint {
    16  	params := elliptic.P384().Params()
    17  	k, _ := rand.Int(rand.Reader, params.N)
    18  	return newAffinePoint(params.ScalarBaseMult(k.Bytes()))
    19  }
    20  
    21  func randomJacobian() *jacobianPoint {
    22  	params := elliptic.P384().Params()
    23  	P := randomAffine().toJacobian()
    24  	z, _ := rand.Int(rand.Reader, params.P)
    25  	var l fp384
    26  	l.SetBigInt(z)
    27  	fp384Mul(&P.z, &P.z, &l) // z = z * l^1
    28  	fp384Mul(&P.y, &P.y, &l)
    29  	fp384Sqr(&l, &l)
    30  	fp384Mul(&P.x, &P.x, &l) // x = x * l^2
    31  	fp384Mul(&P.y, &P.y, &l) // y = y * l^3
    32  	return P
    33  }
    34  
    35  func randomProjective() *projectivePoint {
    36  	return randomJacobian().toProjective()
    37  }
    38  
    39  func TestPointDouble(t *testing.T) {
    40  	t.Run("2∞=∞", func(t *testing.T) {
    41  		Z := zeroPoint().toJacobian()
    42  		Z.double()
    43  		got := Z.isZero()
    44  		want := true
    45  		if got != want {
    46  			test.ReportError(t, got, want)
    47  		}
    48  	})
    49  
    50  	t.Run("2P=P+P", func(t *testing.T) {
    51  		StdCurve := elliptic.P384()
    52  		for i := 0; i < 128; i++ {
    53  			P := randomJacobian()
    54  
    55  			x1, y1 := P.toAffine().toInt()
    56  			wantX, wantY := StdCurve.Double(x1, y1)
    57  
    58  			P.double()
    59  			gotX, gotY := P.toAffine().toInt()
    60  			if gotX.Cmp(wantX) != 0 {
    61  				test.ReportError(t, gotX, wantX, P)
    62  			}
    63  			if gotY.Cmp(wantY) != 0 {
    64  				test.ReportError(t, gotY, wantY)
    65  			}
    66  		}
    67  	})
    68  }
    69  
    70  func TestPointAdd(t *testing.T) {
    71  	StdCurve := elliptic.P384()
    72  	Q, R := &jacobianPoint{}, &jacobianPoint{}
    73  	Z := zeroPoint().toJacobian()
    74  	P := randomJacobian()
    75  
    76  	t.Run("∞+∞=∞", func(t *testing.T) {
    77  		R.add(Z, Z)
    78  		got := R.isZero()
    79  		want := true
    80  		if got != want {
    81  			test.ReportError(t, got, want)
    82  		}
    83  	})
    84  
    85  	t.Run("∞+P=P", func(t *testing.T) {
    86  		R.add(Z, P)
    87  		gotX, gotY := R.toAffine().toInt()
    88  		wantX, wantY := P.toAffine().toInt()
    89  		if gotX.Cmp(wantX) != 0 {
    90  			test.ReportError(t, gotX, wantX, P)
    91  		}
    92  		if gotY.Cmp(wantY) != 0 {
    93  			test.ReportError(t, gotY, wantY, P)
    94  		}
    95  	})
    96  
    97  	t.Run("P+∞=P", func(t *testing.T) {
    98  		R.add(P, Z)
    99  		gotX, gotY := R.toAffine().toInt()
   100  		wantX, wantY := P.toAffine().toInt()
   101  		if gotX.Cmp(wantX) != 0 {
   102  			test.ReportError(t, gotX, wantX, P)
   103  		}
   104  		if gotY.Cmp(wantY) != 0 {
   105  			test.ReportError(t, gotY, wantY, P)
   106  		}
   107  	})
   108  
   109  	t.Run("P+(-P)=∞", func(t *testing.T) {
   110  		*Q = *P
   111  		Q.neg()
   112  		R.add(P, Q)
   113  		got := R.isZero()
   114  		want := true
   115  		if got != want {
   116  			test.ReportError(t, got, want, P)
   117  		}
   118  	})
   119  
   120  	t.Run("P+P=2P", func(t *testing.T) {
   121  		// This verifies that add function cannot be used for doublings.
   122  		for i := 0; i < 128; i++ {
   123  			P = randomJacobian()
   124  
   125  			R.add(P, P)
   126  			gotX, gotY := R.toAffine().toInt()
   127  			wantX, wantY := zeroPoint().toInt()
   128  
   129  			if gotX.Cmp(wantX) != 0 {
   130  				test.ReportError(t, gotX, wantX, P)
   131  			}
   132  			if gotY.Cmp(wantY) != 0 {
   133  				test.ReportError(t, gotY, wantY, P)
   134  			}
   135  		}
   136  	})
   137  
   138  	t.Run("P+Q=R", func(t *testing.T) {
   139  		for i := 0; i < 128; i++ {
   140  			P = randomJacobian()
   141  			Q = randomJacobian()
   142  
   143  			x1, y1 := P.toAffine().toInt()
   144  			x2, y2 := Q.toAffine().toInt()
   145  			wantX, wantY := StdCurve.Add(x1, y1, x2, y2)
   146  
   147  			R.add(P, Q)
   148  			gotX, gotY := R.toAffine().toInt()
   149  
   150  			if gotX.Cmp(wantX) != 0 {
   151  				test.ReportError(t, gotX, wantX, P, Q)
   152  			}
   153  			if gotY.Cmp(wantY) != 0 {
   154  				test.ReportError(t, gotY, wantY, P, Q)
   155  			}
   156  		}
   157  	})
   158  }
   159  
   160  func TestPointCompleteAdd(t *testing.T) {
   161  	StdCurve := elliptic.P384()
   162  	Q, R := &projectivePoint{}, &projectivePoint{}
   163  	Z := zeroPoint().toProjective()
   164  	P := randomProjective()
   165  
   166  	t.Run("∞+∞=∞", func(t *testing.T) {
   167  		R.completeAdd(Z, Z)
   168  		got := R.isZero()
   169  		want := true
   170  		if got != want {
   171  			test.ReportError(t, got, want)
   172  		}
   173  	})
   174  
   175  	t.Run("∞+P=P", func(t *testing.T) {
   176  		R.completeAdd(Z, P)
   177  		gotX, gotY := R.toAffine().toInt()
   178  		wantX, wantY := P.toAffine().toInt()
   179  		if gotX.Cmp(wantX) != 0 {
   180  			test.ReportError(t, gotX, wantX, P)
   181  		}
   182  		if gotY.Cmp(wantY) != 0 {
   183  			test.ReportError(t, gotY, wantY, P)
   184  		}
   185  	})
   186  
   187  	t.Run("P+∞=P", func(t *testing.T) {
   188  		R.completeAdd(P, Z)
   189  		gotX, gotY := R.toAffine().toInt()
   190  		wantX, wantY := P.toAffine().toInt()
   191  		if gotX.Cmp(wantX) != 0 {
   192  			test.ReportError(t, gotX, wantX, P)
   193  		}
   194  		if gotY.Cmp(wantY) != 0 {
   195  			test.ReportError(t, gotY, wantY, P)
   196  		}
   197  	})
   198  
   199  	t.Run("P+(-P)=∞", func(t *testing.T) {
   200  		*Q = *P
   201  		Q.cneg(1)
   202  		R.completeAdd(P, Q)
   203  		got := R.isZero()
   204  		want := true
   205  		if got != want {
   206  			test.ReportError(t, got, want, P)
   207  		}
   208  	})
   209  
   210  	t.Run("P+P=2P", func(t *testing.T) {
   211  		// This verifies that completeAdd can be used for doublings.
   212  		for i := 0; i < 128; i++ {
   213  			P := randomJacobian()
   214  			PP := P.toProjective()
   215  
   216  			R.completeAdd(PP, PP)
   217  			P.double()
   218  
   219  			gotX, gotY := R.toAffine().toInt()
   220  			wantX, wantY := P.toAffine().toInt()
   221  
   222  			if gotX.Cmp(wantX) != 0 {
   223  				test.ReportError(t, gotX, wantX, P)
   224  			}
   225  			if gotY.Cmp(wantY) != 0 {
   226  				test.ReportError(t, gotY, wantY, P)
   227  			}
   228  		}
   229  	})
   230  
   231  	t.Run("P+Q=R", func(t *testing.T) {
   232  		for i := 0; i < 128; i++ {
   233  			P := randomProjective()
   234  			Q := randomProjective()
   235  
   236  			x1, y1 := P.toAffine().toInt()
   237  			x2, y2 := Q.toAffine().toInt()
   238  			wantX, wantY := StdCurve.Add(x1, y1, x2, y2)
   239  
   240  			R.completeAdd(P, Q)
   241  			gotX, gotY := R.toAffine().toInt()
   242  
   243  			if gotX.Cmp(wantX) != 0 {
   244  				test.ReportError(t, gotX, wantX, P, Q)
   245  			}
   246  			if gotY.Cmp(wantY) != 0 {
   247  				test.ReportError(t, gotY, wantY, P, Q)
   248  			}
   249  		}
   250  	})
   251  }
   252  
   253  func TestPointMixAdd(t *testing.T) {
   254  	StdCurve := elliptic.P384()
   255  	aZ := zeroPoint()
   256  	jZ := zeroPoint().toJacobian()
   257  	R := &jacobianPoint{}
   258  	aQ := &affinePoint{}
   259  	aP := randomAffine()
   260  	jP := randomJacobian()
   261  
   262  	t.Run("∞+∞=∞", func(t *testing.T) {
   263  		R.mixadd(jZ, aZ)
   264  		got := R.isZero()
   265  		want := true
   266  		if got != want {
   267  			test.ReportError(t, got, want)
   268  		}
   269  	})
   270  
   271  	t.Run("∞+P=P", func(t *testing.T) {
   272  		R.mixadd(jZ, aP)
   273  		gotX, gotY := R.toAffine().toInt()
   274  		wantX, wantY := aP.toInt()
   275  		if gotX.Cmp(wantX) != 0 {
   276  			test.ReportError(t, gotX, wantX, aP)
   277  		}
   278  		if gotY.Cmp(wantY) != 0 {
   279  			test.ReportError(t, gotY, wantY)
   280  		}
   281  	})
   282  
   283  	t.Run("P+∞=P", func(t *testing.T) {
   284  		R.mixadd(jP, aZ)
   285  		gotX, gotY, gotZ := R.toInt()
   286  		wantX, wantY, wantZ := jP.toInt()
   287  		if gotX.Cmp(wantX) != 0 {
   288  			test.ReportError(t, gotX, wantX, jP)
   289  		}
   290  		if gotY.Cmp(wantY) != 0 {
   291  			test.ReportError(t, gotY, wantY)
   292  		}
   293  		if gotZ.Cmp(wantZ) != 0 {
   294  			test.ReportError(t, gotZ, wantZ)
   295  		}
   296  	})
   297  
   298  	t.Run("P+(-P)=∞", func(t *testing.T) {
   299  		aQ = jP.toAffine()
   300  		aQ.neg()
   301  		R.mixadd(jP, aQ)
   302  		got := R.isZero()
   303  		want := true
   304  		if got != want {
   305  			test.ReportError(t, got, want, jP)
   306  		}
   307  	})
   308  
   309  	t.Run("P+P=2P", func(t *testing.T) {
   310  		for i := 0; i < 128; i++ {
   311  			aQ := randomAffine()
   312  			jQ := aQ.toJacobian()
   313  
   314  			x, y := aQ.toInt()
   315  			wantX, wantY := StdCurve.Double(x, y)
   316  
   317  			R.mixadd(jQ, aQ)
   318  			gotX, gotY := R.toAffine().toInt()
   319  
   320  			if gotX.Cmp(wantX) != 0 {
   321  				test.ReportError(t, gotX, wantX, aQ)
   322  			}
   323  			if gotY.Cmp(wantY) != 0 {
   324  				test.ReportError(t, gotY, wantY)
   325  			}
   326  		}
   327  	})
   328  
   329  	t.Run("P+Q=R", func(t *testing.T) {
   330  		for i := 0; i < 128; i++ {
   331  			aP = randomAffine()
   332  			jP = randomJacobian()
   333  
   334  			x1, y1 := jP.toAffine().toInt()
   335  			x2, y2 := aP.toInt()
   336  			wantX, wantY := StdCurve.Add(x1, y1, x2, y2)
   337  
   338  			R.mixadd(jP, aP)
   339  			gotX, gotY := R.toAffine().toInt()
   340  
   341  			if gotX.Cmp(wantX) != 0 {
   342  				test.ReportError(t, gotX, wantX, jP, aP)
   343  			}
   344  			if gotY.Cmp(wantY) != 0 {
   345  				test.ReportError(t, gotY, wantY)
   346  			}
   347  		}
   348  	})
   349  }
   350  
   351  func TestOddMultiples(t *testing.T) {
   352  	t.Run("invalidOmega", func(t *testing.T) {
   353  		for w := uint(0); w < 2; w++ {
   354  			P := randomAffine()
   355  			PP := P.oddMultiples(w)
   356  			got := len(PP)
   357  			want := 0
   358  			if got != want {
   359  				test.ReportError(t, got, want, w)
   360  			}
   361  		}
   362  	})
   363  
   364  	t.Run("validOmega", func(t *testing.T) {
   365  		StdCurve := elliptic.P384()
   366  		var jOdd [4]byte
   367  		for i := 0; i < 32; i++ {
   368  			P := randomAffine()
   369  			X, Y := P.toInt()
   370  			for w := uint(2); w < 10; w++ {
   371  				PP := P.oddMultiples(w)
   372  				for j, jP := range PP {
   373  					binary.BigEndian.PutUint32(jOdd[:], uint32(2*j+1))
   374  					wantX, wantY := StdCurve.ScalarMult(X, Y, jOdd[:])
   375  					gotX, gotY := jP.toAffine().toInt()
   376  					if gotX.Cmp(wantX) != 0 {
   377  						test.ReportError(t, gotX, wantX, w, j)
   378  					}
   379  					if gotY.Cmp(wantY) != 0 {
   380  						test.ReportError(t, gotY, wantY)
   381  					}
   382  				}
   383  			}
   384  		}
   385  	})
   386  }
   387  
   388  func BenchmarkPoint(b *testing.B) {
   389  	P := randomJacobian()
   390  	Q := randomJacobian()
   391  	R := randomJacobian()
   392  	QQ := randomProjective()
   393  	RR := randomProjective()
   394  	aR := randomAffine()
   395  
   396  	b.Run("addition", func(b *testing.B) {
   397  		for i := 0; i < b.N; i++ {
   398  			R.add(P, Q)
   399  		}
   400  	})
   401  	b.Run("fullAddition", func(b *testing.B) {
   402  		for i := 0; i < b.N; i++ {
   403  			RR.completeAdd(RR, QQ)
   404  		}
   405  	})
   406  	b.Run("mixadd", func(b *testing.B) {
   407  		for i := 0; i < b.N; i++ {
   408  			P.mixadd(P, aR)
   409  		}
   410  	})
   411  	b.Run("double", func(b *testing.B) {
   412  		for i := 0; i < b.N; i++ {
   413  			P.double()
   414  		}
   415  	})
   416  }
   417
View as plain text