-
Notifications
You must be signed in to change notification settings - Fork 22
/
table.go
109 lines (92 loc) · 2.76 KB
/
table.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
package edwards448
import (
"sync"
"crypto/subtle"
)
type lookupTable struct {
points [8]Point
}
var initBasepointOnce sync.Once
var varBasepointTable [56]lookupTable
// 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() *[56]lookupTable {
initBasepointOnce.Do(func() {
p := NewGeneratorPoint()
for i := 0; i < 56; i++ {
varBasepointTable[i].Init(p)
for j := 0; j < 8; j++ {
p.Add(p, p)
}
}
})
return &varBasepointTable
}
var initBasepointNAFOnce sync.Once
var varBasepointNAFTable nafLookupTable8
func basepointNAFTable() *nafLookupTable8 {
initBasepointNAFOnce.Do(func() {
varBasepointNAFTable.Init(NewGeneratorPoint())
})
return &varBasepointNAFTable
}
func (v *lookupTable) Init(p *Point) {
// Goal: v.points[i] = (i+1)*Q, i.e., Q, 2Q, ..., 8Q
// This allows lookup of -8Q, ..., -Q, 0, Q, ..., 8Q
points := &v.points
points[0].Set(p)
for i := 1; i < 8; i++ {
var v Point
points[i].Set(v.Add(&points[i-1], p))
}
}
// Set dest to x*Q, where -8 <= x <= 8, in constant time.
func (v *lookupTable) SelectInto(dest *Point, x int8) {
// Compute xabs = |x|
xmask := x >> 7
xabs := uint8((x + xmask) ^ xmask)
dest.Zero()
for i := 1; i <= 8; i++ {
// Set dest = i*Q if |x| = i
cond := subtle.ConstantTimeByteEq(xabs, uint8(i))
dest.Select(&v.points[i-1], dest, cond)
}
// Now dest = |x|*Q, conditionally negate to get x*Q
dest.CondNeg(int(xmask & 1))
}
type nafLookupTable5 struct {
points [8]Point
}
// Builds a lookup table at runtime. Fast.
func (v *nafLookupTable5) Init(q *Point) {
// Goal: v.points[i] = (2*i+1)*Q, i.e., Q, 3Q, 5Q, ..., 15Q
// This allows lookup of -15Q, ..., -3Q, -Q, 0, Q, 3Q, ..., 15Q
v.points[0].Set(q)
var q2 Point
q2.Add(q, q)
for i := 1; i < 8; i++ {
v.points[i].Add(&v.points[i-1], &q2)
}
}
// Given odd x with 0 < x < 2^4, return x*Q (in variable time).
func (v *nafLookupTable5) SelectInto(dest *Point, x int8) {
*dest = v.points[x/2]
}
type nafLookupTable8 struct {
points [64]Point
}
// Builds a lookup table at runtime. Fast.
func (v *nafLookupTable8) Init(q *Point) {
// Goal: v.points[i] = (2*i+1)*Q, i.e., Q, 3Q, 5Q, ..., 63Q
// This allows lookup of -63Q, ..., -3Q, -Q, 0, Q, 3Q, ..., 63Q
v.points[0].Set(q)
var q2 Point
q2.Add(q, q)
for i := 1; i < 64; i++ {
v.points[i].Add(&v.points[i-1], &q2)
}
}
// Given odd x with 0 < x < 2^7, return x*Q (in variable time).
func (v *nafLookupTable8) SelectInto(dest *Point, x int8) {
*dest = v.points[x/2]
}