1// Copyright (c) 2019 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
5package edwards25519
6
7import "sync"
8
9// basepointTable is a set of 32 affineLookupTables, where table i is generated
10// from 256i * basepoint. It is precomputed the first time it's used.
11func basepointTable() *[32]affineLookupTable {
12	basepointTablePrecomp.initOnce.Do(func() {
13		p := NewGeneratorPoint()
14		for i := 0; i < 32; i++ {
15			basepointTablePrecomp.table[i].FromP3(p)
16			for j := 0; j < 8; j++ {
17				p.Add(p, p)
18			}
19		}
20	})
21	return &basepointTablePrecomp.table
22}
23
24var basepointTablePrecomp struct {
25	table    [32]affineLookupTable
26	initOnce sync.Once
27}
28
29// ScalarBaseMult sets v = x * B, where B is the canonical generator, and
30// returns v.
31//
32// The scalar multiplication is done in constant time.
33func (v *Point) ScalarBaseMult(x *Scalar) *Point {
34	basepointTable := basepointTable()
35
36	// Write x = sum(x_i * 16^i) so  x*B = sum( B*x_i*16^i )
37	// as described in the Ed25519 paper
38	//
39	// Group even and odd coefficients
40	// x*B     = x_0*16^0*B + x_2*16^2*B + ... + x_62*16^62*B
41	//         + x_1*16^1*B + x_3*16^3*B + ... + x_63*16^63*B
42	// x*B     = x_0*16^0*B + x_2*16^2*B + ... + x_62*16^62*B
43	//    + 16*( x_1*16^0*B + x_3*16^2*B + ... + x_63*16^62*B)
44	//
45	// We use a lookup table for each i to get x_i*16^(2*i)*B
46	// and do four doublings to multiply by 16.
47	digits := x.signedRadix16()
48
49	multiple := &affineCached{}
50	tmp1 := &projP1xP1{}
51	tmp2 := &projP2{}
52
53	// Accumulate the odd components first
54	v.Set(NewIdentityPoint())
55	for i := 1; i < 64; i += 2 {
56		basepointTable[i/2].SelectInto(multiple, digits[i])
57		tmp1.AddAffine(v, multiple)
58		v.fromP1xP1(tmp1)
59	}
60
61	// Multiply by 16
62	tmp2.FromP3(v)       // tmp2 =    v in P2 coords
63	tmp1.Double(tmp2)    // tmp1 =  2*v in P1xP1 coords
64	tmp2.FromP1xP1(tmp1) // tmp2 =  2*v in P2 coords
65	tmp1.Double(tmp2)    // tmp1 =  4*v in P1xP1 coords
66	tmp2.FromP1xP1(tmp1) // tmp2 =  4*v in P2 coords
67	tmp1.Double(tmp2)    // tmp1 =  8*v in P1xP1 coords
68	tmp2.FromP1xP1(tmp1) // tmp2 =  8*v in P2 coords
69	tmp1.Double(tmp2)    // tmp1 = 16*v in P1xP1 coords
70	v.fromP1xP1(tmp1)    // now v = 16*(odd components)
71
72	// Accumulate the even components
73	for i := 0; i < 64; i += 2 {
74		basepointTable[i/2].SelectInto(multiple, digits[i])
75		tmp1.AddAffine(v, multiple)
76		v.fromP1xP1(tmp1)
77	}
78
79	return v
80}
81
82// ScalarMult sets v = x * q, and returns v.
83//
84// The scalar multiplication is done in constant time.
85func (v *Point) ScalarMult(x *Scalar, q *Point) *Point {
86	checkInitialized(q)
87
88	var table projLookupTable
89	table.FromP3(q)
90
91	// Write x = sum(x_i * 16^i)
92	// so  x*Q = sum( Q*x_i*16^i )
93	//         = Q*x_0 + 16*(Q*x_1 + 16*( ... + Q*x_63) ... )
94	//           <------compute inside out---------
95	//
96	// We use the lookup table to get the x_i*Q values
97	// and do four doublings to compute 16*Q
98	digits := x.signedRadix16()
99
100	// Unwrap first loop iteration to save computing 16*identity
101	multiple := &projCached{}
102	tmp1 := &projP1xP1{}
103	tmp2 := &projP2{}
104	table.SelectInto(multiple, digits[63])
105
106	v.Set(NewIdentityPoint())
107	tmp1.Add(v, multiple) // tmp1 = x_63*Q in P1xP1 coords
108	for i := 62; i >= 0; i-- {
109		tmp2.FromP1xP1(tmp1) // tmp2 =    (prev) in P2 coords
110		tmp1.Double(tmp2)    // tmp1 =  2*(prev) in P1xP1 coords
111		tmp2.FromP1xP1(tmp1) // tmp2 =  2*(prev) in P2 coords
112		tmp1.Double(tmp2)    // tmp1 =  4*(prev) in P1xP1 coords
113		tmp2.FromP1xP1(tmp1) // tmp2 =  4*(prev) in P2 coords
114		tmp1.Double(tmp2)    // tmp1 =  8*(prev) in P1xP1 coords
115		tmp2.FromP1xP1(tmp1) // tmp2 =  8*(prev) in P2 coords
116		tmp1.Double(tmp2)    // tmp1 = 16*(prev) in P1xP1 coords
117		v.fromP1xP1(tmp1)    //    v = 16*(prev) in P3 coords
118		table.SelectInto(multiple, digits[i])
119		tmp1.Add(v, multiple) // tmp1 = x_i*Q + 16*(prev) in P1xP1 coords
120	}
121	v.fromP1xP1(tmp1)
122	return v
123}
124
125// basepointNafTable is the nafLookupTable8 for the basepoint.
126// It is precomputed the first time it's used.
127func basepointNafTable() *nafLookupTable8 {
128	basepointNafTablePrecomp.initOnce.Do(func() {
129		basepointNafTablePrecomp.table.FromP3(NewGeneratorPoint())
130	})
131	return &basepointNafTablePrecomp.table
132}
133
134var basepointNafTablePrecomp struct {
135	table    nafLookupTable8
136	initOnce sync.Once
137}
138
139// VarTimeDoubleScalarBaseMult sets v = a * A + b * B, where B is the canonical
140// generator, and returns v.
141//
142// Execution time depends on the inputs.
143func (v *Point) VarTimeDoubleScalarBaseMult(a *Scalar, A *Point, b *Scalar) *Point {
144	checkInitialized(A)
145
146	// Similarly to the single variable-base approach, we compute
147	// digits and use them with a lookup table.  However, because
148	// we are allowed to do variable-time operations, we don't
149	// need constant-time lookups or constant-time digit
150	// computations.
151	//
152	// So we use a non-adjacent form of some width w instead of
153	// radix 16.  This is like a binary representation (one digit
154	// for each binary place) but we allow the digits to grow in
155	// magnitude up to 2^{w-1} so that the nonzero digits are as
156	// sparse as possible.  Intuitively, this "condenses" the
157	// "mass" of the scalar onto sparse coefficients (meaning
158	// fewer additions).
159
160	basepointNafTable := basepointNafTable()
161	var aTable nafLookupTable5
162	aTable.FromP3(A)
163	// Because the basepoint is fixed, we can use a wider NAF
164	// corresponding to a bigger table.
165	aNaf := a.nonAdjacentForm(5)
166	bNaf := b.nonAdjacentForm(8)
167
168	// Find the first nonzero coefficient.
169	i := 255
170	for j := i; j >= 0; j-- {
171		if aNaf[j] != 0 || bNaf[j] != 0 {
172			break
173		}
174	}
175
176	multA := &projCached{}
177	multB := &affineCached{}
178	tmp1 := &projP1xP1{}
179	tmp2 := &projP2{}
180	tmp2.Zero()
181
182	// Move from high to low bits, doubling the accumulator
183	// at each iteration and checking whether there is a nonzero
184	// coefficient to look up a multiple of.
185	for ; i >= 0; i-- {
186		tmp1.Double(tmp2)
187
188		// Only update v if we have a nonzero coeff to add in.
189		if aNaf[i] > 0 {
190			v.fromP1xP1(tmp1)
191			aTable.SelectInto(multA, aNaf[i])
192			tmp1.Add(v, multA)
193		} else if aNaf[i] < 0 {
194			v.fromP1xP1(tmp1)
195			aTable.SelectInto(multA, -aNaf[i])
196			tmp1.Sub(v, multA)
197		}
198
199		if bNaf[i] > 0 {
200			v.fromP1xP1(tmp1)
201			basepointNafTable.SelectInto(multB, bNaf[i])
202			tmp1.AddAffine(v, multB)
203		} else if bNaf[i] < 0 {
204			v.fromP1xP1(tmp1)
205			basepointNafTable.SelectInto(multB, -bNaf[i])
206			tmp1.SubAffine(v, multB)
207		}
208
209		tmp2.FromP1xP1(tmp1)
210	}
211
212	v.fromP2(tmp2)
213	return v
214}
215