Adding upstream version 1.18.10.upstream/1.18.10upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 214 insertions, 0 deletions

diff --git a/src/crypto/ed25519/internal/edwards25519/scalarmult.go b/src/crypto/ed25519/internal/edwards25519/scalarmult.go
new file mode 100644
index 0000000..f7ca3ce
--- /dev/null
+++ b/src/crypto/ed25519/internal/edwards25519/scalarmult.go
@@ -0,0 +1,214 @@
+// Copyright (c) 2019 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package edwards25519
+
+import "sync"
+
+// basepointTable is a set of 32 affineLookupTables, where table i is generated
+// from 256i * basepoint. It is precomputed the first time it's used.
+func basepointTable() *[32]affineLookupTable {
+	basepointTablePrecomp.initOnce.Do(func() {
+		p := NewGeneratorPoint()
+		for i := 0; i < 32; i++ {
+			basepointTablePrecomp.table[i].FromP3(p)
+			for j := 0; j < 8; j++ {
+				p.Add(p, p)
+			}
+		}
+	})
+	return &basepointTablePrecomp.table
+}
+
+var basepointTablePrecomp struct {
+	table    [32]affineLookupTable
+	initOnce sync.Once
+}
+
+// ScalarBaseMult sets v = x * B, where B is the canonical generator, and
+// returns v.
+//
+// The scalar multiplication is done in constant time.
+func (v *Point) ScalarBaseMult(x *Scalar) *Point {
+	basepointTable := basepointTable()
+
+	// Write x = sum(x_i * 16^i) so  x*B = sum( B*x_i*16^i )
+	// as described in the Ed25519 paper
+	//
+	// Group even and odd coefficients
+	// x*B     = x_0*16^0*B + x_2*16^2*B + ... + x_62*16^62*B
+	//         + x_1*16^1*B + x_3*16^3*B + ... + x_63*16^63*B
+	// x*B     = x_0*16^0*B + x_2*16^2*B + ... + x_62*16^62*B
+	//    + 16*( x_1*16^0*B + x_3*16^2*B + ... + x_63*16^62*B)
+	//
+	// We use a lookup table for each i to get x_i*16^(2*i)*B
+	// and do four doublings to multiply by 16.
+	digits := x.signedRadix16()
+
+	multiple := &affineCached{}
+	tmp1 := &projP1xP1{}
+	tmp2 := &projP2{}
+
+	// Accumulate the odd components first
+	v.Set(NewIdentityPoint())
+	for i := 1; i < 64; i += 2 {
+		basepointTable[i/2].SelectInto(multiple, digits[i])
+		tmp1.AddAffine(v, multiple)
+		v.fromP1xP1(tmp1)
+	}
+
+	// Multiply by 16
+	tmp2.FromP3(v)       // tmp2 =    v in P2 coords
+	tmp1.Double(tmp2)    // tmp1 =  2*v in P1xP1 coords
+	tmp2.FromP1xP1(tmp1) // tmp2 =  2*v in P2 coords
+	tmp1.Double(tmp2)    // tmp1 =  4*v in P1xP1 coords
+	tmp2.FromP1xP1(tmp1) // tmp2 =  4*v in P2 coords
+	tmp1.Double(tmp2)    // tmp1 =  8*v in P1xP1 coords
+	tmp2.FromP1xP1(tmp1) // tmp2 =  8*v in P2 coords
+	tmp1.Double(tmp2)    // tmp1 = 16*v in P1xP1 coords
+	v.fromP1xP1(tmp1)    // now v = 16*(odd components)
+
+	// Accumulate the even components
+	for i := 0; i < 64; i += 2 {
+		basepointTable[i/2].SelectInto(multiple, digits[i])
+		tmp1.AddAffine(v, multiple)
+		v.fromP1xP1(tmp1)
+	}
+
+	return v
+}
+
+// ScalarMult sets v = x * q, and returns v.
+//
+// The scalar multiplication is done in constant time.
+func (v *Point) ScalarMult(x *Scalar, q *Point) *Point {
+	checkInitialized(q)
+
+	var table projLookupTable
+	table.FromP3(q)
+
+	// Write x = sum(x_i * 16^i)
+	// so  x*Q = sum( Q*x_i*16^i )
+	//         = Q*x_0 + 16*(Q*x_1 + 16*( ... + Q*x_63) ... )
+	//           <------compute inside out---------
+	//
+	// We use the lookup table to get the x_i*Q values
+	// and do four doublings to compute 16*Q
+	digits := x.signedRadix16()
+
+	// Unwrap first loop iteration to save computing 16*identity
+	multiple := &projCached{}
+	tmp1 := &projP1xP1{}
+	tmp2 := &projP2{}
+	table.SelectInto(multiple, digits[63])
+
+	v.Set(NewIdentityPoint())
+	tmp1.Add(v, multiple) // tmp1 = x_63*Q in P1xP1 coords
+	for i := 62; i >= 0; i-- {
+		tmp2.FromP1xP1(tmp1) // tmp2 =    (prev) in P2 coords
+		tmp1.Double(tmp2)    // tmp1 =  2*(prev) in P1xP1 coords
+		tmp2.FromP1xP1(tmp1) // tmp2 =  2*(prev) in P2 coords
+		tmp1.Double(tmp2)    // tmp1 =  4*(prev) in P1xP1 coords
+		tmp2.FromP1xP1(tmp1) // tmp2 =  4*(prev) in P2 coords
+		tmp1.Double(tmp2)    // tmp1 =  8*(prev) in P1xP1 coords
+		tmp2.FromP1xP1(tmp1) // tmp2 =  8*(prev) in P2 coords
+		tmp1.Double(tmp2)    // tmp1 = 16*(prev) in P1xP1 coords
+		v.fromP1xP1(tmp1)    //    v = 16*(prev) in P3 coords
+		table.SelectInto(multiple, digits[i])
+		tmp1.Add(v, multiple) // tmp1 = x_i*Q + 16*(prev) in P1xP1 coords
+	}
+	v.fromP1xP1(tmp1)
+	return v
+}
+
+// basepointNafTable is the nafLookupTable8 for the basepoint.
+// It is precomputed the first time it's used.
+func basepointNafTable() *nafLookupTable8 {
+	basepointNafTablePrecomp.initOnce.Do(func() {
+		basepointNafTablePrecomp.table.FromP3(NewGeneratorPoint())
+	})
+	return &basepointNafTablePrecomp.table
+}
+
+var basepointNafTablePrecomp struct {
+	table    nafLookupTable8
+	initOnce sync.Once
+}
+
+// VarTimeDoubleScalarBaseMult sets v = a * A + b * B, where B is the canonical
+// generator, and returns v.
+//
+// Execution time depends on the inputs.
+func (v *Point) VarTimeDoubleScalarBaseMult(a *Scalar, A *Point, b *Scalar) *Point {
+	checkInitialized(A)
+
+	// Similarly to the single variable-base approach, we compute
+	// digits and use them with a lookup table.  However, because
+	// we are allowed to do variable-time operations, we don't
+	// need constant-time lookups or constant-time digit
+	// computations.
+	//
+	// So we use a non-adjacent form of some width w instead of
+	// radix 16.  This is like a binary representation (one digit
+	// for each binary place) but we allow the digits to grow in
+	// magnitude up to 2^{w-1} so that the nonzero digits are as
+	// sparse as possible.  Intuitively, this "condenses" the
+	// "mass" of the scalar onto sparse coefficients (meaning
+	// fewer additions).
+
+	basepointNafTable := basepointNafTable()
+	var aTable nafLookupTable5
+	aTable.FromP3(A)
+	// Because the basepoint is fixed, we can use a wider NAF
+	// corresponding to a bigger table.
+	aNaf := a.nonAdjacentForm(5)
+	bNaf := b.nonAdjacentForm(8)
+
+	// Find the first nonzero coefficient.
+	i := 255
+	for j := i; j >= 0; j-- {
+		if aNaf[j] != 0 || bNaf[j] != 0 {
+			break
+		}
+	}
+
+	multA := &projCached{}
+	multB := &affineCached{}
+	tmp1 := &projP1xP1{}
+	tmp2 := &projP2{}
+	tmp2.Zero()
+
+	// Move from high to low bits, doubling the accumulator
+	// at each iteration and checking whether there is a nonzero
+	// coefficient to look up a multiple of.
+	for ; i >= 0; i-- {
+		tmp1.Double(tmp2)
+
+		// Only update v if we have a nonzero coeff to add in.
+		if aNaf[i] > 0 {
+			v.fromP1xP1(tmp1)
+			aTable.SelectInto(multA, aNaf[i])
+			tmp1.Add(v, multA)
+		} else if aNaf[i] < 0 {
+			v.fromP1xP1(tmp1)
+			aTable.SelectInto(multA, -aNaf[i])
+			tmp1.Sub(v, multA)
+		}
+
+		if bNaf[i] > 0 {
+			v.fromP1xP1(tmp1)
+			basepointNafTable.SelectInto(multB, bNaf[i])
+			tmp1.AddAffine(v, multB)
+		} else if bNaf[i] < 0 {
+			v.fromP1xP1(tmp1)
+			basepointNafTable.SelectInto(multB, -bNaf[i])
+			tmp1.SubAffine(v, multB)
+		}
+
+		tmp2.FromP1xP1(tmp1)
+	}
+
+	v.fromP2(tmp2)
+	return v
+}