v

1
module edwards25519
2

3
import os
4
import rand
5
import math.bits
6
import math.big
7
import encoding.hex
8

9
const github_job = os.getenv('GITHUB_JOB')
10

11
fn testsuite_begin() {
12
	if github_job != '' {
13
		// ensure that the CI does not run flaky tests:
14
		rand.seed([u32(0xffff24), 0xabcd])
15
	}
16
}
17

18
fn (mut v Element) str() string {
19
	return hex.encode(v.bytes())
20
}
21

22
const mask_low_52_bits = (u64(1) << 52) - 1
23

24
fn generate_field_element() Element {
25
	return Element{
26
		l0: rand.u64() & mask_low_52_bits
27
		l1: rand.u64() & mask_low_52_bits
28
		l2: rand.u64() & mask_low_52_bits
29
		l3: rand.u64() & mask_low_52_bits
30
		l4: rand.u64() & mask_low_52_bits
31
	}
32
}
33

34
// weirdLimbs can be combined to generate a range of edge-case edwards25519 elements.
35
// 0 and -1 are intentionally more weighted, as they combine well.
36
const two_to_51 = u64(1) << 51
37
const two_to_52 = u64(1) << 52
38
const weird_limbs_51 = [
39
	u64(0),
40
	0,
41
	0,
42
	0,
43
	1,
44
	19 - 1,
45
	19,
46
	0x2aaaaaaaaaaaa,
47
	0x5555555555555,
48
	two_to_51 - 20,
49
	two_to_51 - 19,
50
	two_to_51 - 1,
51
	two_to_51 - 1,
52
	two_to_51 - 1,
53
	two_to_51 - 1,
54
]
55
const weird_limbs_52 = [
56
	u64(0),
57
	0,
58
	0,
59
	0,
60
	0,
61
	0,
62
	1,
63
	19 - 1,
64
	19,
65
	0x2aaaaaaaaaaaa,
66
	0x5555555555555,
67
	two_to_51 - 20,
68
	two_to_51 - 19,
69
	two_to_51 - 1,
70
	two_to_51 - 1,
71
	two_to_51 - 1,
72
	two_to_51 - 1,
73
	two_to_51 - 1,
74
	two_to_51 - 1,
75
	two_to_51,
76
	two_to_51 + 1,
77
	two_to_52 - 19,
78
	two_to_52 - 1,
79
]
80

81
fn generate_weird_field_element() Element {
82
	return Element{
83
		l0: weird_limbs_52[rand.intn(weird_limbs_52.len) or { 0 }]
84
		l1: weird_limbs_51[rand.intn(weird_limbs_51.len) or { 0 }]
85
		l2: weird_limbs_51[rand.intn(weird_limbs_51.len) or { 0 }]
86
		l3: weird_limbs_51[rand.intn(weird_limbs_51.len) or { 0 }]
87
		l4: weird_limbs_51[rand.intn(weird_limbs_51.len) or { 0 }]
88
	}
89
}
90

91
fn (e Element) generate_element() Element {
92
	if rand.intn(2) or { 0 } == 0 {
93
		return generate_weird_field_element()
94
	}
95
	return generate_field_element()
96
}
97

98
fn is_in_bounds(x Element) bool {
99
	return bits.len_64(x.l0) <= 52 && bits.len_64(x.l1) <= 52 && bits.len_64(x.l2) <= 52
100
		&& bits.len_64(x.l3) <= 52 && bits.len_64(x.l4) <= 52
101
}
102

103
fn carry_gen(a [5]u64) bool {
104
	mut t1 := Element{a[0], a[1], a[2], a[3], a[4]}
105
	mut t2 := Element{a[0], a[1], a[2], a[3], a[4]}
106

107
	t1.carry_propagate_generic()
108
	t2.carry_propagate_generic()
109

110
	return t1 == t2 && is_in_bounds(t2)
111
}
112

113
fn test_carry_propagate_generic() {
114
	// closures not supported on windows
115
	for i := 0; i <= 10; i++ {
116
		els := [rand.u64(), rand.u64(), rand.u64(), rand.u64(),
117
			rand.u64()]!
118
		p := carry_gen(els)
119
		assert p == true
120
	}
121
	res := carry_gen([u64(0xffffffffffffffff), 0xffffffffffffffff, 0xffffffffffffffff,
122
		0xffffffffffffffff, 0xffffffffffffffff]!)
123
	assert res == true
124
}
125

126
fn test_fe_mul_generic() {
127
	for i in 0 .. 20 {
128
		el := Element{}
129
		a := el.generate_element()
130
		b := el.generate_element()
131
		a1 := a
132
		a2 := a
133

134
		b1 := b
135
		b2 := b
136

137
		a1b1 := fe_mul_generic(a1, b1)
138
		a2b2 := fe_mul_generic(a2, b2)
139
		assert a1b1 == a2b2 && is_in_bounds(a1b1) && is_in_bounds(a2b2)
140
	}
141
}
142

143
fn test_fe_square_generic() {
144
	for i in 0 .. 20 {
145
		a := generate_field_element()
146

147
		a1 := a
148
		a2 := a
149

150
		a11 := fe_square_generic(a1)
151
		a22 := fe_square_generic(a2)
152
		assert a11 == a22 && is_in_bounds(a11) && is_in_bounds(a22)
153
	}
154
}
155

156
struct SqrtRatioTest {
157
	u          string
158
	v          string
159
	was_square int
160
	r          string
161
}
162

163
fn test_sqrt_ratio() {
164
	// From draft-irtf-cfrg-ristretto255-decaf448-00, Appendix A.4.
165

166
	tests := [
167
		// If u is 0, the function is defined to return (0, TRUE), even if v
168
		// is zero. Note that where used in this package, the denominator v
169
		// is never zero.
170
		SqrtRatioTest{'0000000000000000000000000000000000000000000000000000000000000000', '0000000000000000000000000000000000000000000000000000000000000000', 1, '0000000000000000000000000000000000000000000000000000000000000000'},
171
		// 0/1 == 0²
172
		SqrtRatioTest{'0000000000000000000000000000000000000000000000000000000000000000', '0100000000000000000000000000000000000000000000000000000000000000', 1, '0000000000000000000000000000000000000000000000000000000000000000'},
173
		// If u is non-zero and v is zero, defined to return (0, FALSE).
174
		SqrtRatioTest{'0100000000000000000000000000000000000000000000000000000000000000', '0000000000000000000000000000000000000000000000000000000000000000', 0, '0000000000000000000000000000000000000000000000000000000000000000'},
175
		// 2/1 is not square in this edwards25519.
176
		SqrtRatioTest{'0200000000000000000000000000000000000000000000000000000000000000', '0100000000000000000000000000000000000000000000000000000000000000', 0, '3c5ff1b5d8e4113b871bd052f9e7bcd0582804c266ffb2d4f4203eb07fdb7c54'},
177
		// 4/1 == 2²
178
		SqrtRatioTest{'0400000000000000000000000000000000000000000000000000000000000000', '0100000000000000000000000000000000000000000000000000000000000000', 1, '0200000000000000000000000000000000000000000000000000000000000000'},
179
		// 1/4 == (2⁻¹)² == (2^(p-2))² per Euler's theorem
180
		SqrtRatioTest{'0100000000000000000000000000000000000000000000000000000000000000', '0400000000000000000000000000000000000000000000000000000000000000', 1, 'f6ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff3f'},
181
	]
182

183
	for i, tt in tests {
184
		mut elu := Element{}
185
		mut elv := Element{}
186
		mut elw := Element{}
187
		mut elg := Element{}
188

189
		u := elu.set_bytes(hex.decode(tt.u)!)!
190
		v := elv.set_bytes(hex.decode(tt.v)!)!
191
		want := elw.set_bytes(hex.decode(tt.r)!)!
192
		mut got, was_square := elg.sqrt_ratio(u, v)
193

194
		assert got.equal(want) != 0
195
		assert was_square == tt.was_square
196
		// if got.Equal(want) == 0 || wasSquare != tt.wasSquare {
197
		// 	t.Errorf("%d: got (%v, %v), want (%v, %v)", i, got, wasSquare, want, tt.wasSquare)
198
		// }
199
	}
200
}
201

202
fn test_set_bytes_normal() {
203
	for i in 0 .. 15 {
204
		mut el := Element{}
205
		mut random_inp := rand.bytes(32)!
206

207
		el = el.set_bytes(random_inp.clone())!
208
		random_inp[random_inp.len - 1] &= (1 << 7) - 1
209
		// assert f1(random_inp, el) == true
210

211
		assert random_inp == el.bytes()
212
		assert is_in_bounds(el) == true
213
	}
214
}
215

216
fn test_set_bytes_reduced() {
217
	mut fe := Element{}
218
	mut r := Element{}
219
	mut random_inp := rand.bytes(32) or { return }
220

221
	fe.set_bytes(random_inp) or { return }
222
	r.set_bytes(fe.bytes()) or { return }
223

224
	assert fe == r
225
}
226

227
// Check some fixed vectors from dalek
228
struct FeRTTest {
229
mut:
230
	fe Element
231
	b  []u8
232
}
233

234
fn test_set_bytes_from_dalek_test_vectors() {
235
	mut tests := [
236
		FeRTTest{
237
			fe: Element{358744748052810, 1691584618240980, 977650209285361, 1429865912637724, 560044844278676}
238
			b:  [u8(74), 209, 69, 197, 70, 70, 161, 222, 56, 226, 229, 19, 112, 60, 25, 92, 187,
239
				74, 222, 56, 50, 153, 51, 233, 40, 74, 57, 6, 160, 185, 213, 31]
240
		},
241
		FeRTTest{
242
			fe: Element{84926274344903, 473620666599931, 365590438845504, 1028470286882429, 2146499180330972}
243
			b:  [u8(199), 23, 106, 112, 61, 77, 216, 79, 186, 60, 11, 118, 13, 16, 103, 15, 42,
244
				32, 83, 250, 44, 57, 204, 198, 78, 199, 253, 119, 146, 172, 3, 122]
245
		},
246
	]
247
	for _, mut tt in tests {
248
		b := tt.fe.bytes()
249
		mut el := Element{}
250
		mut fe := el.set_bytes(tt.b)!
251

252
		assert b == tt.b
253
		assert fe.equal(tt.fe) == 1
254
	}
255
}
256

257
fn test_equal() {
258
	mut x := Element{1, 1, 1, 1, 1}
259
	y := Element{5, 4, 3, 2, 1}
260

261
	mut eq1 := x.equal(x)
262
	assert eq1 == 1
263

264
	eq1 = x.equal(y)
265
	assert eq1 == 0
266
}
267

268
fn test_invert() {
269
	mut x := Element{1, 1, 1, 1, 1}
270
	mut one := Element{1, 0, 0, 0, 0}
271
	mut xinv := Element{}
272
	mut r := Element{}
273

274
	xinv.invert(x)
275
	r.multiply(x, xinv)
276
	r.reduce()
277

278
	assert one == r
279
	bytes := rand.bytes(32)!
280

281
	x.set_bytes(bytes)!
282

283
	xinv.invert(x)
284
	r.multiply(x, xinv)
285
	r.reduce()
286

287
	assert one == r
288

289
	zero := Element{}
290
	x.set(zero)
291

292
	xx := xinv.invert(x)
293
	assert xx == xinv
294
	assert xinv.equal(zero) == 1
295
	// s := if num % 2 == 0 { 'even' } else { 'odd' }
296
}
297

298
fn test_mult_32() {
299
	for j in 0 .. 10 {
300
		mut x := Element{}
301
		mut t1 := Element{}
302
		y := u32(0)
303
		for i := 0; i < 100; i++ {
304
			t1.mult_32(x, y)
305
		}
306
		mut ty := Element{}
307
		ty.l0 = u64(y)
308
		mut t2 := Element{}
309
		for i := 0; i < 100; i++ {
310
			t2.multiply(x, ty)
311
		}
312
		assert t1.equal(t2) == 1 && is_in_bounds(t1) && is_in_bounds(t2)
313
	}
314
}
315

316
fn test_selected_and_swap() {
317
	a := Element{358744748052810, 1691584618240980, 977650209285361, 1429865912637724, 560044844278676}
318
	b := Element{84926274344903, 473620666599931, 365590438845504, 1028470286882429, 2146499180330972}
319

320
	mut c := Element{}
321
	mut d := Element{}
322

323
	c.selected(a, b, 1)
324
	d.selected(a, b, 0)
325

326
	assert c.equal(a) == 1
327
	assert d.equal(b) == 1
328

329
	c.swap(mut d, 0)
330
	assert c.equal(a) == 1
331
	assert d.equal(b) == 1
332

333
	c.swap(mut d, 1)
334
	assert c.equal(b) == 1
335
	assert d.equal(a) == 1
336
}
337

338
// Tests self-consistency between multiply and Square.
339
fn test_consistency_between_mult_and_square() {
340
	mut x := Element{1, 1, 1, 1, 1}
341
	mut x2 := Element{}
342
	mut x2sq := Element{}
343

344
	x2.multiply(x, x)
345
	x2sq.square(x)
346

347
	assert x2 == x2sq
348

349
	bytes := rand.bytes(32) or { return }
350
	x.set_bytes(bytes) or { return }
351
	x2.multiply(x, x)
352
	x2sq.square(x)
353

354
	assert x2 == x2sq
355
}
356

357
// to_big_integer returns v as a big.Integer.
358
fn (mut v Element) to_big_integer() big.Integer {
359
	buf := v.bytes()
360
	return big.integer_from_bytes(buf)
361
}
362

363
// from_big_integer sets v = n, and returns v. The bit length of n must not exceed 256.
364
fn (mut v Element) from_big_integer(n big.Integer) !Element {
365
	if n.bin_str().len > 32 * 8 {
366
		return error('invalid edwards25519 element input size')
367
	}
368
	mut bytes, _ := n.bytes()
369
	swap_endianness(mut bytes) // SHOULD I SWAP IT?
370
	v.set_bytes(bytes)!
371

372
	return v
373
}
374

375
fn (mut v Element) from_decimal_string(s string) !Element {
376
	num := big.integer_from_string(s)!
377

378
	v = v.from_big_integer(num)!
379
	return v
380
}
381

382
fn test_bytes_big_equivalence() {
383
	mut inp := rand.bytes(32)!
384
	el := Element{}
385
	mut fe := el.generate_element()
386
	mut fe1 := el.generate_element()
387

388
	fe.set_bytes(inp) or { panic(err) }
389
	inp[inp.len - 1] &= (1 << 7) - 1 // mask the most significant bit
390

391
	mut b := big.integer_from_bytes(swap_endianness(mut inp)) // need swap_endianness
392
	fe1.from_big_integer(b) or { panic(err) } // do swap_endianness internally
393

394
	assert fe == fe1
395

396
	mut buf := []u8{len: 32} // pad with zeroes
397
	fedtobig := fe1.to_big_integer()
398
	mut fedbig_bytes, _ := fedtobig.bytes()
399
	copy(mut buf, fedbig_bytes) // does not need to do swap_endianness
400

401
	assert fe.bytes() == buf && is_in_bounds(fe) && is_in_bounds(fe1)
402
	// assert big_equivalence(inp, fe, fe1) == true
403
}
404

405
fn test_decimal_constants() {
406
	sqrtm1string := '19681161376707505956807079304988542015446066515923890162744021073123829784752'
407
	mut el := Element{}
408
	mut exp := el.from_decimal_string(sqrtm1string)!
409

410
	assert sqrt_m1.equal(exp) == 1
411

412
	dstring := '37095705934669439343138083508754565189542113879843219016388785533085940283555'
413
	exp = el.from_decimal_string(dstring)!
414
	mut d := d_const
415

416
	assert d.equal(exp) == 1
417
}
418

419
fn test_mul_64_to_128() {
420
	mut a := u64(5)
421
	mut b := u64(5)
422
	mut r := mul_64(a, b)
423

424
	assert r.lo == 0x19
425
	assert r.hi == 0
426

427
	a = u64(18014398509481983) // 2^54 - 1
428
	b = u64(18014398509481983) // 2^54 - 1
429
	r = mul_64(a, b)
430

431
	assert r.lo == 0xff80000000000001 && r.hi == 0xfffffffffff
432

433
	a = u64(1125899906842661)
434
	b = u64(2097155)
435
	r = mul_64(a, b)
436
	r = add_mul_64(r, a, b)
437
	r = add_mul_64(r, a, b)
438
	r = add_mul_64(r, a, b)
439
	r = add_mul_64(r, a, b)
440

441
	assert r.lo == 16888498990613035 && r.hi == 640
442
}
443

444
fn test_multiply_distributes_over_add() {
445
	for i in 0 .. 10 {
446
		el := Element{}
447
		x := el.generate_element()
448
		y := el.generate_element()
449
		z := el.generate_element()
450
		mut t1 := Element{}
451
		t1.add(x, y)
452
		t1.multiply(t1, z)
453

454
		// Compute t2 = x*z + y*z
455
		mut t2 := Element{}
456
		mut t3 := Element{}
457
		t2.multiply(x, z)
458
		t3.multiply(y, z)
459
		t2.add(t2, t3)
460
		assert t1.equal(t2) == 1 && is_in_bounds(t1) && is_in_bounds(t2)
461
	}
462
}
463