crypto/internal/nistec: use precomputed P-256 generators in purego

Change-Id: I73cd2ff857512a90585b860906061b71d1c19e41
Reviewed-on: https://go-review.googlesource.com/c/go/+/627941
Reviewed-by: Russ Cox <rsc@golang.org>
Auto-Submit: Filippo Valsorda <filippo@golang.org>
Reviewed-by: Michael Knyszek <mknyszek@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

4 files changed, 39 insertions, 49 deletions

diff --git a/src/crypto/internal/nistec/p256.go b/src/crypto/internal/nistec/p256.go
index dd025e7059..611bfbac73 100644
--- a/src/crypto/internal/nistec/p256.go
+++ b/src/crypto/internal/nistec/p256.go
@@ -9,10 +9,13 @@ package nistec
 import (
 	"crypto/internal/nistec/fiat"
 	"crypto/subtle"
+	_ "embed"
 	"errors"
 	"internal/byteorder"
+	"internal/goarch"
 	"math/bits"
 	"sync"
+	"unsafe"
 )
 
 // p256ElementLength is the length of an element of the base or scalar field,
@@ -522,40 +525,29 @@ func (table *p256AffineTable) Select(p *p256AffinePoint, n uint8) {
 	}
 }
 
-var _p256GeneratorTable *[43]p256AffineTable
-var p256GeneratorTableOnce sync.Once
+// p256GeneratorTables is a series of precomputed multiples of G, the canonical
+// generator. The first p256AffineTable contains multiples of G. The second one
+// multiples of [2⁶]G, the third one of [2¹²]G, and so on, where each successive
+// table is the previous table doubled six times. Six is the width of the
+// sliding window used in ScalarBaseMult, and having each table already
+// pre-doubled lets us avoid the doublings between windows entirely. This table
+// MUST NOT be modified, as it aliases into p256GeneratorTablesEmbed below.
+var p256GeneratorTables *[43]p256AffineTable
 
-// p256GeneratorTable returns a sequence of p256Tables. The first table contains
-// multiples of G. Each successive table is the previous table doubled four
-// times.
-func p256GeneratorTable() *[43]p256AffineTable {
-	p256GeneratorTableOnce.Do(func() {
-		_p256GeneratorTable = new([43]p256AffineTable)
-		base := NewP256Point().SetGenerator()
-		for i := 0; i < 43; i++ {
-			p := NewP256Point().Set(base)
-			_p256GeneratorTable[i][0] = *p256ToAffine(p)
-			for j := 1; j < 32; j++ {
-				p := NewP256Point().AddAffine(base, &_p256GeneratorTable[i][j-1], 1)
-				_p256GeneratorTable[i][j] = *p256ToAffine(p)
-			}
-			base.Double(base)
-			base.Double(base)
-			base.Double(base)
-			base.Double(base)
-			base.Double(base)
-			base.Double(base)
-		}
-	})
-	return _p256GeneratorTable
-}
+//go:embed p256_table.bin
+var p256GeneratorTablesEmbed string
 
-func p256ToAffine(p *P256Point) *p256AffinePoint {
-	inv := new(fiat.P256Element).Invert(&p.z)
-	pa := &p256AffinePoint{}
-	pa.x.Mul(&p.x, inv)
-	pa.y.Mul(&p.y, inv)
-	return pa
+func init() {
+	p256GeneratorTablesPtr := (*unsafe.Pointer)(unsafe.Pointer(&p256GeneratorTablesEmbed))
+	if goarch.BigEndian {
+		var newTable [43 * 32 * 2 * 4]uint64
+		for i, x := range (*[43 * 32 * 2 * 4][8]byte)(*p256GeneratorTablesPtr) {
+			newTable[i] = byteorder.LeUint64(x[:])
+		}
+		newTablePtr := unsafe.Pointer(&newTable)
+		p256GeneratorTablesPtr = &newTablePtr
+	}
+	p256GeneratorTables = (*[43]p256AffineTable)(*p256GeneratorTablesPtr)
 }
 
 func boothW6(in uint64) (uint8, int) {
@@ -575,7 +567,6 @@ func (p *P256Point) ScalarBaseMult(scalar []byte) (*P256Point, error) {
 	s := new(p256OrdElement)
 	p256OrdBigToLittle(s, (*[32]byte)(scalar))
 	p256OrdReduce(s)
-	tables := p256GeneratorTable()
 
 	p.Set(NewP256Point())
 
@@ -589,7 +580,7 @@ func (p *P256Point) ScalarBaseMult(scalar []byte) (*P256Point, error) {
 	_ = sign
 
 	t := &p256AffinePoint{}
-	table := &tables[(index+1)/6]
+	table := &p256GeneratorTables[(index+1)/6]
 	table.Select(t, sel)
 	selIsNotZero := subtle.ConstantTimeByteEq(sel, 0) ^ 1
 	p.x.Select(&t.x, &p.x, selIsNotZero)
@@ -610,7 +601,7 @@ func (p *P256Point) ScalarBaseMult(scalar []byte) (*P256Point, error) {
 
 		selIsNotZero := subtle.ConstantTimeByteEq(sel, 0) ^ 1
 
-		table := &tables[(index+1)/6]
+		table := &p256GeneratorTables[(index+1)/6]
 		table.Select(t, sel)
 		t.Negate(sign)
 		p.AddAffine(p, t, selIsNotZero)
diff --git a/src/crypto/internal/nistec/p256_asm.go b/src/crypto/internal/nistec/p256_asm.go
index 599eee9623..632a64127e 100644
--- a/src/crypto/internal/nistec/p256_asm.go
+++ b/src/crypto/internal/nistec/p256_asm.go
@@ -324,12 +324,12 @@ type p256AffineTable [32]p256AffinePoint
 // generator. The first p256AffineTable contains multiples of G. The second one
 // multiples of [2⁶]G, the third one of [2¹²]G, and so on, where each successive
 // table is the previous table doubled six times. Six is the width of the
-// sliding window used in p256ScalarMult, and having each table already
+// sliding window used in p256ScalarBaseMult, and having each table already
 // pre-doubled lets us avoid the doublings between windows entirely. This table
 // MUST NOT be modified, as it aliases into p256PrecomputedEmbed below.
 var p256Precomputed *[43]p256AffineTable
 
-//go:embed p256_asm_table.bin
+//go:embed p256_table.bin
 var p256PrecomputedEmbed string
 
 func init() {
diff --git a/src/crypto/internal/nistec/p256_asm_table.bin b/src/crypto/internal/nistec/p256_table.bin
index 20c527e4e0..20c527e4e0 100644
--- a/src/crypto/internal/nistec/p256_asm_table.bin
+++ b/src/crypto/internal/nistec/p256_table.bin
diff --git a/src/crypto/internal/nistec/p256_asm_table_test.go b/src/crypto/internal/nistec/p256_test.go
index cba455d32d..7ebe7209dc 100644
--- a/src/crypto/internal/nistec/p256_asm_table_test.go
+++ b/src/crypto/internal/nistec/p256_test.go
@@ -2,11 +2,13 @@
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
-//go:build !purego && (amd64 || arm64 || ppc64le || s390x)
+//go:build (!amd64 && !arm64 && !ppc64le && !s390x) || purego
 
 package nistec
 
 import (
+	"bytes"
+	"crypto/internal/nistec/fiat"
 	"fmt"
 	"testing"
 )
@@ -16,7 +18,7 @@ func TestP256PrecomputedTable(t *testing.T) {
 
 	for i := 0; i < 43; i++ {
 		t.Run(fmt.Sprintf("table[%d]", i), func(t *testing.T) {
-			testP256AffineTable(t, base, &p256Precomputed[i])
+			testP256AffineTable(t, base, &p256GeneratorTables[i])
 		})
 
 		for k := 0; k < 6; k++ {
@@ -27,22 +29,19 @@ func TestP256PrecomputedTable(t *testing.T) {
 
 func testP256AffineTable(t *testing.T, base *P256Point, table *p256AffineTable) {
 	p := NewP256Point()
-	zInv := new(p256Element)
-	zInvSq := new(p256Element)
+	zInv := new(fiat.P256Element)
 
 	for j := 0; j < 32; j++ {
 		p.Add(p, base)
 
 		// Convert p to affine coordinates.
-		p256Inverse(zInv, &p.z)
-		p256Sqr(zInvSq, zInv, 1)
-		p256Mul(zInv, zInv, zInvSq)
+		zInv.Invert(&p.z)
+		p.x.Mul(&p.x, zInv)
+		p.y.Mul(&p.y, zInv)
+		p.z.One()
 
-		p256Mul(&p.x, &p.x, zInvSq)
-		p256Mul(&p.y, &p.y, zInv)
-		p.z = p256One
-
-		if p256Equal(&table[j].x, &p.x) != 1 || p256Equal(&table[j].y, &p.y) != 1 {
+		if !bytes.Equal(table[j].x.Bytes(), p.x.Bytes()) ||
+			!bytes.Equal(table[j].y.Bytes(), p.y.Bytes()) {
 			t.Fatalf("incorrect table entry at index %d", j)
 		}
 	}