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 5 package edwards25519
6 7 import "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.
11 func 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 24 var 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.
33 func (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.
85 func (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.
127 func basepointNafTable() *nafLookupTable8 {
128 basepointNafTablePrecomp.initOnce.Do(func() {
129 basepointNafTablePrecomp.table.FromP3(NewGeneratorPoint())
130 })
131 return &basepointNafTablePrecomp.table
132 }
133 134 var 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.
143 func (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