v

1
module edwards25519
2

3
// extended_coordinates returns v in extended coordinates (X:Y:Z:T) where
4
// x = X/Z, y = Y/Z, and xy = T/Z as in https://eprint.iacr.org/2008/522.
5
fn (mut v Point) extended_coordinates() (Element, Element, Element, Element) {
6
	// This function is outlined to make the allocations inline in the caller
7
	// rather than happen on the heap. Don't change the style without making
8
	// sure it doesn't increase the inliner cost.
9
	mut e := []Element{len: 4}
10
	x, y, z, t := v.extended_coordinates_generic(mut e)
11
	return x, y, z, t
12
}
13

14
fn (mut v Point) extended_coordinates_generic(mut e []Element) (Element, Element, Element, Element) {
15
	check_initialized(v)
16
	x := e[0].set(v.x)
17
	y := e[1].set(v.y)
18
	z := e[2].set(v.z)
19
	t := e[3].set(v.t)
20
	return x, y, z, t
21
}
22

23
// Given k > 0, set s = s**(2*i).
24
fn (mut s Scalar) pow2k(k int) {
25
	for i := 0; i < k; i++ {
26
		s.multiply(s, s)
27
	}
28
}
29

30
// set_extended_coordinates sets v = (X:Y:Z:T) in extended coordinates where
31
// x = X/Z, y = Y/Z, and xy = T/Z as in https://eprint.iacr.org/2008/522.
32
//
33
// If the coordinates are invalid or don't represent a valid point on the curve,
34
// set_extended_coordinates returns an error and the receiver is
35
// unchanged. Otherwise, set_extended_coordinates returns v.
36
fn (mut v Point) set_extended_coordinates(x Element, y Element, z Element, t Element) !Point {
37
	if !is_on_curve(x, y, z, t) {
38
		return error('edwards25519: invalid point coordinates')
39
	}
40
	v.x.set(x)
41
	v.y.set(y)
42
	v.z.set(z)
43
	v.t.set(t)
44
	return v
45
}
46

47
fn is_on_curve(x Element, y Element, z Element, t Element) bool {
48
	mut lhs := Element{}
49
	mut rhs := Element{}
50

51
	mut xx := Element{}
52
	xx.square(x)
53

54
	mut yy := Element{}
55
	yy.square(y)
56

57
	mut zz := Element{}
58
	zz.square(z)
59
	// zz := new(Element).Square(Z)
60

61
	mut tt := Element{}
62
	tt.square(t)
63
	// tt := new(Element).Square(T)
64
	// -x² + y² = 1 + dx²y²
65
	// -(X/Z)² + (Y/Z)² = 1 + d(T/Z)²
66
	// -X² + Y² = Z² + dT²
67
	lhs.subtract(yy, xx)
68
	mut d := d_const
69
	rhs.multiply(d, tt)
70
	rhs.add(rhs, zz)
71
	if lhs.equal(rhs) != 1 {
72
		return false
73
	}
74
	// xy = T/Z
75
	// XY/Z² = T/Z
76
	// XY = TZ
77
	lhs.multiply(x, y)
78
	rhs.multiply(t, z)
79
	return lhs.equal(rhs) == 1
80
}
81

82
// bytes_montgomery converts v to a point on the birationally-equivalent
83
// Curve25519 Montgomery curve, and returns its canonical 32 bytes encoding
84
// according to RFC 7748.
85
//
86
// Note that bytes_montgomery only encodes the u-coordinate, so v and -v encode
87
// to the same value. If v is the identity point, bytes_montgomery returns 32
88
// zero bytes, analogously to the X25519 function.
89
pub fn (mut v Point) bytes_montgomery() []u8 {
90
	// This function is outlined to make the allocations inline in the caller
91
	// rather than happen on the heap.
92
	mut buf := [32]u8{}
93
	return v.bytes_montgomery_generic(mut buf)
94
}
95

96
fn (mut v Point) bytes_montgomery_generic(mut buf [32]u8) []u8 {
97
	check_initialized(v)
98

99
	// RFC 7748, Section 4.1 provides the bilinear map to calculate the
100
	// Montgomery u-coordinate
101
	//
102
	//              u = (1 + y) / (1 - y)
103
	//
104
	// where y = Y / Z.
105

106
	mut y := Element{}
107
	mut recip := Element{}
108
	mut u := Element{}
109

110
	y.multiply(v.y, y.invert(v.z)) // y = Y / Z
111
	recip.invert(recip.subtract(fe_one, y)) // r = 1/(1 - y)
112
	u.multiply(u.add(fe_one, y), recip) // u = (1 + y)*r
113

114
	return copy_field_element(mut buf, mut u)
115
}
116

117
// mult_by_cofactor sets v = 8 * p, and returns v.
118
pub fn (mut v Point) mult_by_cofactor(p Point) Point {
119
	check_initialized(p)
120
	mut result := ProjectiveP1{}
121
	mut pp := ProjectiveP2{}
122
	pp.from_p3(p)
123
	result.double(pp)
124
	pp.from_p1(result)
125
	result.double(pp)
126
	pp.from_p1(result)
127
	result.double(pp)
128
	return v.from_p1(result)
129
}
130

131
// invert sets s to the inverse of a nonzero scalar v, and returns s.
132
//
133
// If t is zero, invert returns zero.
134
pub fn (mut s Scalar) invert(t Scalar) Scalar {
135
	// Uses a hardcoded sliding window of width 4.
136
	mut table := [8]Scalar{}
137
	mut tt := Scalar{}
138
	tt.multiply(t, t)
139
	table[0] = t
140
	for i := 0; i < 7; i++ {
141
		table[i + 1].multiply(table[i], tt)
142
	}
143
	// Now table = [t**1, t**3, t**7, t**11, t**13, t**15]
144
	// so t**k = t[k/2] for odd k
145

146
	// To compute the sliding window digits, use the following Sage script:
147

148
	// sage: import itertools
149
	// sage: def sliding_window(w,k):
150
	// ....:     digits = []
151
	// ....:     while k > 0:
152
	// ....:         if k % 2 == 1:
153
	// ....:             kmod = k % (2**w)
154
	// ....:             digits.append(kmod)
155
	// ....:             k = k - kmod
156
	// ....:         else:
157
	// ....:             digits.append(0)
158
	// ....:         k = k // 2
159
	// ....:     return digits
160

161
	// Now we can compute s roughly as follows:
162

163
	// sage: s = 1
164
	// sage: for coeff in reversed(sliding_window(4,l-2)):
165
	// ....:     s = s*s
166
	// ....:     if coeff > 0 :
167
	// ....:         s = s*t**coeff
168

169
	// This works on one bit at a time, with many runs of zeros.
170
	// The digits can be collapsed into [(count, coeff)] as follows:
171

172
	// sage: [(len(list(group)),d) for d,group in itertools.groupby(sliding_window(4,l-2))]
173

174
	// Entries of the form (k, 0) turn into pow2k(k)
175
	// Entries of the form (1, coeff) turn into a squaring and then a table lookup.
176
	// We can fold the squaring into the previous pow2k(k) as pow2k(k+1).
177

178
	s = table[1 / 2]
179
	s.pow2k(127 + 1)
180
	s.multiply(s, table[1 / 2])
181
	s.pow2k(4 + 1)
182
	s.multiply(s, table[9 / 2])
183
	s.pow2k(3 + 1)
184
	s.multiply(s, table[11 / 2])
185
	s.pow2k(3 + 1)
186
	s.multiply(s, table[13 / 2])
187
	s.pow2k(3 + 1)
188
	s.multiply(s, table[15 / 2])
189
	s.pow2k(4 + 1)
190
	s.multiply(s, table[7 / 2])
191
	s.pow2k(4 + 1)
192
	s.multiply(s, table[15 / 2])
193
	s.pow2k(3 + 1)
194
	s.multiply(s, table[5 / 2])
195
	s.pow2k(3 + 1)
196
	s.multiply(s, table[1 / 2])
197
	s.pow2k(4 + 1)
198
	s.multiply(s, table[15 / 2])
199
	s.pow2k(4 + 1)
200
	s.multiply(s, table[15 / 2])
201
	s.pow2k(4 + 1)
202
	s.multiply(s, table[7 / 2])
203
	s.pow2k(3 + 1)
204
	s.multiply(s, table[3 / 2])
205
	s.pow2k(4 + 1)
206
	s.multiply(s, table[11 / 2])
207
	s.pow2k(5 + 1)
208
	s.multiply(s, table[11 / 2])
209
	s.pow2k(9 + 1)
210
	s.multiply(s, table[9 / 2])
211
	s.pow2k(3 + 1)
212
	s.multiply(s, table[3 / 2])
213
	s.pow2k(4 + 1)
214
	s.multiply(s, table[3 / 2])
215
	s.pow2k(4 + 1)
216
	s.multiply(s, table[3 / 2])
217
	s.pow2k(4 + 1)
218
	s.multiply(s, table[9 / 2])
219
	s.pow2k(3 + 1)
220
	s.multiply(s, table[7 / 2])
221
	s.pow2k(3 + 1)
222
	s.multiply(s, table[3 / 2])
223
	s.pow2k(3 + 1)
224
	s.multiply(s, table[13 / 2])
225
	s.pow2k(3 + 1)
226
	s.multiply(s, table[7 / 2])
227
	s.pow2k(4 + 1)
228
	s.multiply(s, table[9 / 2])
229
	s.pow2k(3 + 1)
230
	s.multiply(s, table[15 / 2])
231
	s.pow2k(4 + 1)
232
	s.multiply(s, table[11 / 2])
233

234
	return s
235
}
236

237
// multi_scalar_mult sets v = sum(scalars[i] * points[i]), and returns v.
238
//
239
// Execution time depends only on the lengths of the two slices, which must match.
240
pub fn (mut v Point) multi_scalar_mult(scalars []Scalar, points []Point) Point {
241
	if scalars.len != points.len {
242
		panic('edwards25519: called multi_scalar_mult with different size inputs')
243
	}
244
	check_initialized(...points)
245

246
	mut sc := scalars.clone()
247
	// Proceed as in the single-base case, but share doublings
248
	// between each point in the multiscalar equation.
249

250
	// Build lookup tables for each point
251
	mut tables := []ProjLookupTable{len: points.len}
252
	for i, _ in tables {
253
		tables[i].from_p3(points[i])
254
	}
255
	// Compute signed radix-16 digits for each scalar
256
	// digits := make([][64]int8, len(scalars))
257
	mut digits := [][]i8{len: sc.len, init: []i8{len: 64, cap: 64}}
258

259
	for j, _ in digits {
260
		digits[j] = sc[j].signed_radix16()
261
	}
262

263
	// Unwrap first loop iteration to save computing 16*identity
264
	mut multiple := ProjectiveCached{}
265
	mut tmp1 := ProjectiveP1{}
266
	mut tmp2 := ProjectiveP2{}
267
	// Lookup-and-add the appropriate multiple of each input point
268
	for k, _ in tables {
269
		tables[k].select_into(mut multiple, digits[k][63])
270
		tmp1.add(v, multiple) // tmp1 = v + x_(j,63)*Q in P1xP1 coords
271
		v.from_p1(tmp1) // update v
272
	}
273
	tmp2.from_p3(v) // set up tmp2 = v in P2 coords for next iteration
274
	for r := 62; r >= 0; r-- {
275
		tmp1.double(tmp2) // tmp1 =  2*(prev) in P1xP1 coords
276
		tmp2.from_p1(tmp1) // tmp2 =  2*(prev) in P2 coords
277
		tmp1.double(tmp2) // tmp1 =  4*(prev) in P1xP1 coords
278
		tmp2.from_p1(tmp1) // tmp2 =  4*(prev) in P2 coords
279
		tmp1.double(tmp2) // tmp1 =  8*(prev) in P1xP1 coords
280
		tmp2.from_p1(tmp1) // tmp2 =  8*(prev) in P2 coords
281
		tmp1.double(tmp2) // tmp1 = 16*(prev) in P1xP1 coords
282
		v.from_p1(tmp1) //    v = 16*(prev) in P3 coords
283
		// Lookup-and-add the appropriate multiple of each input point
284
		for s, _ in tables {
285
			tables[s].select_into(mut multiple, digits[s][r])
286
			tmp1.add(v, multiple) // tmp1 = v + x_(j,i)*Q in P1xP1 coords
287
			v.from_p1(tmp1) // update v
288
		}
289
		tmp2.from_p3(v) // set up tmp2 = v in P2 coords for next iteration
290
	}
291
	return v
292
}
293

294
// vartime_multiscalar_mult sets v = sum(scalars[i] * points[i]), and returns v.
295
//
296
// Execution time depends on the inputs.
297
pub fn (mut v Point) vartime_multiscalar_mult(scalars []Scalar, points []Point) Point {
298
	if scalars.len != points.len {
299
		panic('edwards25519: called VarTimeMultiScalarMult with different size inputs')
300
	}
301
	check_initialized(...points)
302

303
	// Generalize double-base NAF computation to arbitrary sizes.
304
	// Here all the points are dynamic, so we only use the smaller
305
	// tables.
306

307
	// Build lookup tables for each point
308
	mut tables := []NafLookupTable5{len: points.len}
309
	for i, _ in tables {
310
		tables[i].from_p3(points[i])
311
	}
312
	mut sc := scalars.clone()
313
	// Compute a NAF for each scalar
314
	// mut nafs := make([][256]int8, len(scalars))
315
	mut nafs := [][]i8{len: sc.len, init: []i8{len: 256, cap: 256}}
316
	for j, _ in nafs {
317
		nafs[j] = sc[j].non_adjacent_form(5)
318
	}
319

320
	mut multiple := ProjectiveCached{}
321
	mut tmp1 := ProjectiveP1{}
322
	mut tmp2 := ProjectiveP2{}
323
	tmp2.zero()
324

325
	// Move from high to low bits, doubling the accumulator
326
	// at each iteration and checking whether there is a nonzero
327
	// coefficient to look up a multiple of.
328
	//
329
	// Skip trying to find the first nonzero coefficient, because
330
	// searching might be more work than a few extra doublings.
331
	// k == i, l == j
332
	for k := 255; k >= 0; k-- {
333
		tmp1.double(tmp2)
334

335
		for l, _ in nafs {
336
			if nafs[l][k] > 0 {
337
				v.from_p1(tmp1)
338
				tables[l].select_into(mut multiple, nafs[l][k])
339
				tmp1.add(v, multiple)
340
			} else if nafs[l][k] < 0 {
341
				v.from_p1(tmp1)
342
				tables[l].select_into(mut multiple, -nafs[l][k])
343
				tmp1.sub(v, multiple)
344
			}
345
		}
346

347
		tmp2.from_p1(tmp1)
348
	}
349

350
	v.from_p2(tmp2)
351
	return v
352
}
353