v

1
module edwards25519
2

3
import sync
4

5
struct BasepointTablePrecomp {
6
mut:
7
	table    []AffineLookupTable
8
	initonce sync.Once
9
}
10

11
// basepoint_table is a set of 32 affineLookupTables, where table i is generated
12
// from 256i * basepoint. It is precomputed the first time it's used.
13
fn basepoint_table() []AffineLookupTable {
14
	mut bpt := &BasepointTablePrecomp{
15
		table:    []AffineLookupTable{len: 32}
16
		initonce: sync.new_once()
17
	}
18

19
	// replaced to use do_with_param on newest sync lib
20
	/*
21
	bpt.initonce.do(fn [mut bpt] () {
22
		mut p := new_generator_point()
23
		for i := 0; i < 32; i++ {
24
			bpt.table[i].from_p3(p)
25
			for j := 0; j < 8; j++ {
26
				p.add(p, p)
27
			}
28
		}
29
	})*/
30
	bpt.initonce.do_with_param(fn (mut o BasepointTablePrecomp) {
31
		mut p := new_generator_point()
32
		for i := 0; i < 32; i++ {
33
			o.table[i].from_p3(p)
34
			for j := 0; j < 8; j++ {
35
				p.add(p, p)
36
			}
37
		}
38
	}, bpt)
39
	return bpt.table
40
}
41

42
// scalar_base_mult sets v = x * B, where B is the canonical generator, and
43
// returns v.
44
//
45
// The scalar multiplication is done in constant time.
46
pub fn (mut v Point) scalar_base_mult(mut x Scalar) Point {
47
	mut bpt_table := basepoint_table()
48

49
	// Write x = sum(x_i * 16^i) so  x*B = sum( B*x_i*16^i )
50
	// as described in the Ed25519 paper
51
	//
52
	// Group even and odd coefficients
53
	// x*B     = x_0*16^0*B + x_2*16^2*B + ... + x_62*16^62*B
54
	//         + x_1*16^1*B + x_3*16^3*B + ... + x_63*16^63*B
55
	// x*B     = x_0*16^0*B + x_2*16^2*B + ... + x_62*16^62*B
56
	//    + 16*( x_1*16^0*B + x_3*16^2*B + ... + x_63*16^62*B)
57
	//
58
	// We use a lookup table for each i to get x_i*16^(2*i)*B
59
	// and do four doublings to multiply by 16.
60
	digits := x.signed_radix16()
61

62
	mut multiple := AffineCached{}
63
	mut tmp1 := ProjectiveP1{}
64
	mut tmp2 := ProjectiveP2{}
65

66
	// Accumulate the odd components first
67
	v.set(new_identity_point())
68
	for i := 1; i < 64; i += 2 {
69
		bpt_table[i / 2].select_into(mut multiple, digits[i])
70
		tmp1.add_affine(v, multiple)
71
		v.from_p1(tmp1)
72
	}
73

74
	// Multiply by 16
75
	tmp2.from_p3(v) // tmp2 =    v in P2 coords
76
	tmp1.double(tmp2) // tmp1 =  2*v in P1xP1 coords
77
	tmp2.from_p1(tmp1) // tmp2 =  2*v in P2 coords
78
	tmp1.double(tmp2) // tmp1 =  4*v in P1xP1 coords
79
	tmp2.from_p1(tmp1) // tmp2 =  4*v in P2 coords
80
	tmp1.double(tmp2) // tmp1 =  8*v in P1xP1 coords
81
	tmp2.from_p1(tmp1) // tmp2 =  8*v in P2 coords
82
	tmp1.double(tmp2) // tmp1 = 16*v in P1xP1 coords
83
	v.from_p1(tmp1) // now v = 16*(odd components)
84

85
	// Accumulate the even components
86
	for j := 0; j < 64; j += 2 {
87
		bpt_table[j / 2].select_into(mut multiple, digits[j])
88
		tmp1.add_affine(v, multiple)
89
		v.from_p1(tmp1)
90
	}
91

92
	return v
93
}
94

95
// scalar_mult sets v = x * q, and returns v.
96
//
97
// The scalar multiplication is done in constant time.
98
pub fn (mut v Point) scalar_mult(mut x Scalar, q Point) Point {
99
	check_initialized(q)
100

101
	mut table := ProjLookupTable{}
102
	table.from_p3(q)
103

104
	// Write x = sum(x_i * 16^i)
105
	// so  x*Q = sum( Q*x_i*16^i )
106
	//         = Q*x_0 + 16*(Q*x_1 + 16*( ... + Q*x_63) ... )
107
	//           <------compute inside out---------
108
	//
109
	// We use the lookup table to get the x_i*Q values
110
	// and do four doublings to compute 16*Q
111
	digits := x.signed_radix16()
112

113
	// Unwrap first loop iteration to save computing 16*identity
114
	mut multiple := ProjectiveCached{}
115
	mut tmp1 := ProjectiveP1{}
116
	mut tmp2 := ProjectiveP2{}
117
	table.select_into(mut multiple, digits[63])
118

119
	v.set(new_identity_point())
120
	tmp1.add(v, multiple) // tmp1 = x_63*Q in P1xP1 coords
121
	for i := 62; i >= 0; i-- {
122
		tmp2.from_p1(tmp1) // tmp2 =    (prev) in P2 coords
123
		tmp1.double(tmp2) // tmp1 =  2*(prev) in P1xP1 coords
124
		tmp2.from_p1(tmp1) // tmp2 =  2*(prev) in P2 coords
125
		tmp1.double(tmp2) // tmp1 =  4*(prev) in P1xP1 coords
126
		tmp2.from_p1(tmp1) // tmp2 =  4*(prev) in P2 coords
127
		tmp1.double(tmp2) // tmp1 =  8*(prev) in P1xP1 coords
128
		tmp2.from_p1(tmp1) // tmp2 =  8*(prev) in P2 coords
129
		tmp1.double(tmp2) // tmp1 = 16*(prev) in P1xP1 coords
130
		v.from_p1(tmp1) //    v = 16*(prev) in P3 coords
131
		table.select_into(mut multiple, digits[i])
132
		tmp1.add(v, multiple) // tmp1 = x_i*Q + 16*(prev) in P1xP1 coords
133
	}
134
	v.from_p1(tmp1)
135
	return v
136
}
137

138
struct BasepointNaftablePrecomp {
139
mut:
140
	table    NafLookupTable8
141
	initonce sync.Once
142
}
143

144
fn basepoint_naf_table() NafLookupTable8 {
145
	mut bnft := &BasepointNaftablePrecomp{}
146
	bnft.initonce.do_with_param(fn (mut o BasepointNaftablePrecomp) {
147
		o.table.from_p3(new_generator_point())
148
	}, bnft)
149
	return bnft.table
150
}
151

152
// vartime_double_scalar_base_mult sets v = a * A + b * B, where B is the canonical
153
// generator, and returns v.
154
//
155
// Execution time depends on the inputs.
156
pub fn (mut v Point) vartime_double_scalar_base_mult(xa Scalar, aa Point, xb Scalar) Point {
157
	check_initialized(aa)
158

159
	// Similarly to the single variable-base approach, we compute
160
	// digits and use them with a lookup table.  However, because
161
	// we are allowed to do variable-time operations, we don't
162
	// need constant-time lookups or constant-time digit
163
	// computations.
164
	//
165
	// So we use a non-adjacent form of some width w instead of
166
	// radix 16.  This is like a binary representation (one digit
167
	// for each binary place) but we allow the digits to grow in
168
	// magnitude up to 2^{w-1} so that the nonzero digits are as
169
	// sparse as possible.  Intuitively, this "condenses" the
170
	// "mass" of the scalar onto sparse coefficients (meaning
171
	// fewer additions).
172

173
	mut bp_naftable := basepoint_naf_table()
174
	mut atable := NafLookupTable5{}
175
	atable.from_p3(aa)
176
	// Because the basepoint is fixed, we can use a wider NAF
177
	// corresponding to a bigger table.
178
	mut a := xa
179
	mut b := xb
180
	anaf := a.non_adjacent_form(5)
181
	bnaf := b.non_adjacent_form(8)
182

183
	// Find the first nonzero coefficient.
184
	mut i := 255
185
	for j := i; j >= 0; j-- {
186
		if anaf[j] != 0 || bnaf[j] != 0 {
187
			break
188
		}
189
	}
190

191
	mut multa := ProjectiveCached{}
192
	mut multb := AffineCached{}
193
	mut tmp1 := ProjectiveP1{}
194
	mut tmp2 := ProjectiveP2{}
195
	tmp2.zero()
196

197
	// Move from high to low bits, doubling the accumulator
198
	// at each iteration and checking whether there is a nonzero
199
	// coefficient to look up a multiple of.
200
	for ; i >= 0; i-- {
201
		tmp1.double(tmp2)
202

203
		// Only update v if we have a nonzero coeff to add in.
204
		if anaf[i] > 0 {
205
			v.from_p1(tmp1)
206
			atable.select_into(mut multa, anaf[i])
207
			tmp1.add(v, multa)
208
		} else if anaf[i] < 0 {
209
			v.from_p1(tmp1)
210
			atable.select_into(mut multa, -anaf[i])
211
			tmp1.sub(v, multa)
212
		}
213

214
		if bnaf[i] > 0 {
215
			v.from_p1(tmp1)
216
			bp_naftable.select_into(mut multb, bnaf[i])
217
			tmp1.add_affine(v, multb)
218
		} else if bnaf[i] < 0 {
219
			v.from_p1(tmp1)
220
			bp_naftable.select_into(mut multb, -bnaf[i])
221
			tmp1.sub_affine(v, multb)
222
		}
223

224
		tmp2.from_p1(tmp1)
225
	}
226

227
	v.from_p2(tmp2)
228
	return v
229
}
230