| 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 |
} |