v

1
module edwards25519
2

3
// d is a constant in the curve equation.
4
const d_bytes = [u8(0xa3), 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75, 0xab, 0xd8, 0x41, 0x41, 0x4d,
5
	0x0a, 0x70, 0x00, 0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c, 0x73, 0xfe, 0x6f, 0x2b, 0xee,
6
	0x6c, 0x03, 0x52]
7
const id_bytes = [u8(1), 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
8
	0, 0, 0, 0, 0, 0, 0]
9
const gen_bytes = [u8(0x58), 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
10
	0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
11
	0x66, 0x66, 0x66, 0x66]
12
const d_const = d_const_generate() or { panic(err) }
13
const d2_const = d2_const_generate() or { panic(err) }
14
// id_point is the point at infinity.
15
const id_point = id_point_generate() or { panic(err) }
16
// generator point
17
const gen_point = generator() or { panic(err) }
18

19
fn d_const_generate() !Element {
20
	mut v := Element{}
21
	v.set_bytes(d_bytes)!
22
	return v
23
}
24

25
fn d2_const_generate() !Element {
26
	mut v := Element{}
27
	v.add(d_const, d_const)
28
	return v
29
}
30

31
// id_point_generate is the point at infinity.
32
fn id_point_generate() !Point {
33
	mut p := Point{}
34
	p.set_bytes(id_bytes)!
35
	return p
36
}
37

38
// generator is the canonical curve basepoint. See TestGenerator for the
39
// correspondence of this encoding with the values in RFC 8032.
40
fn generator() !Point {
41
	mut p := Point{}
42
	p.set_bytes(gen_bytes)!
43
	return p
44
}
45

46
// Point types.
47
struct ProjectiveP1 {
48
mut:
49
	x Element
50
	y Element
51
	z Element
52
	t Element
53
}
54

55
struct ProjectiveP2 {
56
mut:
57
	x Element
58
	y Element
59
	z Element
60
}
61

62
// Point represents a point on the edwards25519 curve.
63
//
64
// This type works similarly to math/big.Int, and all arguments and receivers
65
// are allowed to alias.
66
//
67
// The zero value is NOT valid, and it may be used only as a receiver.
68
pub struct Point {
69
mut:
70
	// The point is internally represented in extended coordinates (x, y, z, T)
71
	// where x = x/z, y = y/z, and xy = T/z per https://eprint.iacr.org/2008/522.
72
	x Element
73
	y Element
74
	z Element
75
	t Element
76
	// Make the type not comparable (i.e. used with == or as a map key), as
77
	// equivalent points can be represented by different values.
78
	// _ incomparable
79
}
80

81
fn check_initialized(points ...Point) {
82
	for _, p in points {
83
		if p.x == fe_zero && p.y == fe_zero {
84
			panic('edwards25519: use of uninitialized Point')
85
		}
86
	}
87
}
88

89
struct ProjectiveCached {
90
mut:
91
	ypx Element // y + x
92
	ymx Element // y - x
93
	z   Element
94
	t2d Element
95
}
96

97
struct AffineCached {
98
mut:
99
	ypx Element // y + x
100
	ymx Element // y - x
101
	t2d Element
102
}
103

104
fn (mut v ProjectiveP2) zero() ProjectiveP2 {
105
	v.x.zero()
106
	v.y.one()
107
	v.z.one()
108
	return v
109
}
110

111
// set_bytes sets v = x, where x is a 32-byte encoding of v. If x does not
112
// represent a valid point on the curve, set_bytes returns an error and
113
// the receiver is unchanged. Otherwise, set_bytes returns v.
114
//
115
// Note that set_bytes accepts all non-canonical encodings of valid points.
116
// That is, it follows decoding rules that match most implementations in
117
// the ecosystem rather than RFC 8032.
118
pub fn (mut v Point) set_bytes(x []u8) !Point {
119
	// Specifically, the non-canonical encodings that are accepted are
120
	//   1) the ones where the edwards25519 element is not reduced (see the
121
	//      (*edwards25519.Element).set_bytes docs) and
122
	//   2) the ones where the x-coordinate is zero and the sign bit is set.
123
	//
124
	// This is consistent with crypto/ed25519/internal/edwards25519. Read more
125
	// at https://hdevalence.ca/blog/2020-10-04-its-25519am, specifically the
126
	// "Canonical A, R" section.
127
	mut el0 := Element{}
128
	y := el0.set_bytes(x) or { return error('edwards25519: invalid point encoding length') }
129

130
	// -x² + y² = 1 + dx²y²
131
	// x² + dx²y² = x²(dy² + 1) = y² - 1
132
	// x² = (y² - 1) / (dy² + 1)
133

134
	// u = y² - 1
135
	mut el1 := Element{}
136
	y2 := el1.square(y)
137
	mut el2 := Element{}
138
	u := el2.subtract(y2, fe_one)
139

140
	// v = dy² + 1
141
	mut el3 := Element{}
142
	mut vv := el3.multiply(y2, d_const)
143
	vv = vv.add(vv, fe_one)
144

145
	// x = +√(u/v)
146
	mut el4 := Element{}
147
	mut xx, was_square := el4.sqrt_ratio(u, vv)
148
	if was_square == 0 {
149
		return error('edwards25519: invalid point encoding')
150
	}
151

152
	// selected the negative square root if the sign bit is set.
153
	mut el5 := Element{}
154
	xx_neg := el5.negate(xx)
155
	xx.selected(xx_neg, xx, int(x[31] >> 7))
156

157
	v.x.set(xx)
158
	v.y.set(y)
159
	v.z.one()
160
	v.t.multiply(xx, y) // xy = T / z
161

162
	return v
163
}
164

165
// set sets v = u, and returns v.
166
pub fn (mut v Point) set(u Point) Point {
167
	v = u
168
	return v
169
}
170

171
// new_identity_point returns a new Point set to the identity.
172
pub fn new_identity_point() Point {
173
	mut p := Point{}
174
	return p.set(id_point)
175
}
176

177
// new_generator_point returns a new Point set to the canonical generator.
178
pub fn new_generator_point() Point {
179
	mut p := Point{}
180
	return p.set(gen_point)
181
}
182

183
fn (mut v ProjectiveCached) zero() ProjectiveCached {
184
	v.ypx.one()
185
	v.ymx.one()
186
	v.z.one()
187
	v.t2d.zero()
188
	return v
189
}
190

191
fn (mut v AffineCached) zero() AffineCached {
192
	v.ypx.one()
193
	v.ymx.one()
194
	v.t2d.zero()
195
	return v
196
}
197

198
// Encoding.
199

200
// bytes returns the canonical 32-byte encoding of v, according to RFC 8032,
201
// Section 5.1.2.
202
pub fn (mut v Point) bytes() []u8 {
203
	// This function is outlined to make the allocations inline in the caller
204
	// rather than happen on the heap.
205
	mut buf := [32]u8{}
206
	return v.bytes_generic(mut buf)
207
}
208

209
fn (mut v Point) bytes_generic(mut buf [32]u8) []u8 {
210
	check_initialized(v)
211

212
	mut zinv := Element{}
213
	mut x := Element{}
214
	mut y := Element{}
215
	zinv.invert(v.z) // zinv = 1 / z
216
	x.multiply(v.x, zinv) // x = x / z
217
	y.multiply(v.y, zinv) // y = y / z
218

219
	mut out := copy_field_element(mut buf, mut y)
220
	unsafe {
221
		// out[31] |= u8(x.is_negative() << 7) //original one
222
		out[31] |= u8(x.is_negative() * 128) // x << 7 == x * 2^7
223
	}
224
	return out
225
}
226

227
fn copy_field_element(mut buf [32]u8, mut v Element) []u8 {
228
	// this fail in test
229
	/*
230
	copy(mut buf[..], v.bytes())
231
	return buf[..]
232
	*/
233

234
	// this pass the test
235
	mut out := []u8{len: 32}
236
	for i := 0; i <= buf.len - 1; i++ {
237
		out[i] = v.bytes()[i]
238
	}
239

240
	return out
241
}
242

243
// Conversions.
244

245
fn (mut v ProjectiveP2) from_p1(p ProjectiveP1) ProjectiveP2 {
246
	v.x.multiply(p.x, p.t)
247
	v.y.multiply(p.y, p.z)
248
	v.z.multiply(p.z, p.t)
249
	return v
250
}
251

252
fn (mut v ProjectiveP2) from_p3(p Point) ProjectiveP2 {
253
	v.x.set(p.x)
254
	v.y.set(p.y)
255
	v.z.set(p.z)
256
	return v
257
}
258

259
fn (mut v Point) from_p1(p ProjectiveP1) Point {
260
	v.x.multiply(p.x, p.t)
261
	v.y.multiply(p.y, p.z)
262
	v.z.multiply(p.z, p.t)
263
	v.t.multiply(p.x, p.y)
264
	return v
265
}
266

267
fn (mut v Point) from_p2(p ProjectiveP2) Point {
268
	v.x.multiply(p.x, p.z)
269
	v.y.multiply(p.y, p.z)
270
	v.z.square(p.z)
271
	v.t.multiply(p.x, p.y)
272
	return v
273
}
274

275
fn (mut v ProjectiveCached) from_p3(p Point) ProjectiveCached {
276
	v.ypx.add(p.y, p.x)
277
	v.ymx.subtract(p.y, p.x)
278
	v.z.set(p.z)
279
	v.t2d.multiply(p.t, d2_const)
280
	return v
281
}
282

283
fn (mut v AffineCached) from_p3(p Point) AffineCached {
284
	v.ypx.add(p.y, p.x)
285
	v.ymx.subtract(p.y, p.x)
286
	v.t2d.multiply(p.t, d2_const)
287

288
	mut invz := Element{}
289
	invz.invert(p.z)
290
	v.ypx.multiply(v.ypx, invz)
291
	v.ymx.multiply(v.ymx, invz)
292
	v.t2d.multiply(v.t2d, invz)
293
	return v
294
}
295

296
// (Re)addition and subtraction.
297

298
// add sets v = p + q, and returns v.
299
pub fn (mut v Point) add(p Point, q Point) Point {
300
	check_initialized(p, q)
301
	mut pc := ProjectiveCached{}
302
	mut p1 := ProjectiveP1{}
303
	qcached := pc.from_p3(q)
304

305
	result := p1.add(p, qcached)
306
	return v.from_p1(result)
307
}
308

309
// subtract sets v = p - q, and returns v.
310
pub fn (mut v Point) subtract(p Point, q Point) Point {
311
	check_initialized(p, q)
312
	mut pc := ProjectiveCached{}
313
	mut p1 := ProjectiveP1{}
314
	qcached := pc.from_p3(q)
315
	result := p1.sub(p, qcached)
316
	return v.from_p1(result)
317
}
318

319
fn (mut v ProjectiveP1) add(p Point, q ProjectiveCached) ProjectiveP1 {
320
	// var ypx, ymx, pp, mm, tt2d, zz2 edwards25519.Element
321
	mut ypx := Element{}
322
	mut ymx := Element{}
323
	mut pp := Element{}
324
	mut mm := Element{}
325
	mut tt2d := Element{}
326
	mut zz2 := Element{}
327

328
	ypx.add(p.y, p.x)
329
	ymx.subtract(p.y, p.x)
330

331
	pp.multiply(ypx, q.ypx)
332
	mm.multiply(ymx, q.ymx)
333
	tt2d.multiply(p.t, q.t2d)
334
	zz2.multiply(p.z, q.z)
335

336
	zz2.add(zz2, zz2)
337

338
	v.x.subtract(pp, mm)
339
	v.y.add(pp, mm)
340
	v.z.add(zz2, tt2d)
341
	v.t.subtract(zz2, tt2d)
342
	return v
343
}
344

345
fn (mut v ProjectiveP1) sub(p Point, q ProjectiveCached) ProjectiveP1 {
346
	mut ypx := Element{}
347
	mut ymx := Element{}
348
	mut pp := Element{}
349
	mut mm := Element{}
350
	mut tt2d := Element{}
351
	mut zz2 := Element{}
352

353
	ypx.add(p.y, p.x)
354
	ymx.subtract(p.y, p.x)
355

356
	pp.multiply(ypx, q.ymx) // flipped sign
357
	mm.multiply(ymx, q.ypx) // flipped sign
358
	tt2d.multiply(p.t, q.t2d)
359
	zz2.multiply(p.z, q.z)
360

361
	zz2.add(zz2, zz2)
362

363
	v.x.subtract(pp, mm)
364
	v.y.add(pp, mm)
365
	v.z.subtract(zz2, tt2d) // flipped sign
366
	v.t.add(zz2, tt2d) // flipped sign
367
	return v
368
}
369

370
fn (mut v ProjectiveP1) add_affine(p Point, q AffineCached) ProjectiveP1 {
371
	mut ypx := Element{}
372
	mut ymx := Element{}
373
	mut pp := Element{}
374
	mut mm := Element{}
375
	mut tt2d := Element{}
376
	mut z2 := Element{}
377

378
	ypx.add(p.y, p.x)
379
	ymx.subtract(p.y, p.x)
380

381
	pp.multiply(ypx, q.ypx)
382
	mm.multiply(ymx, q.ymx)
383
	tt2d.multiply(p.t, q.t2d)
384

385
	z2.add(p.z, p.z)
386

387
	v.x.subtract(pp, mm)
388
	v.y.add(pp, mm)
389
	v.z.add(z2, tt2d)
390
	v.t.subtract(z2, tt2d)
391
	return v
392
}
393

394
fn (mut v ProjectiveP1) sub_affine(p Point, q AffineCached) ProjectiveP1 {
395
	mut ypx := Element{}
396
	mut ymx := Element{}
397
	mut pp := Element{}
398
	mut mm := Element{}
399
	mut tt2d := Element{}
400
	mut z2 := Element{}
401

402
	ypx.add(p.y, p.x)
403
	ymx.subtract(p.y, p.x)
404

405
	pp.multiply(ypx, q.ymx) // flipped sign
406
	mm.multiply(ymx, q.ypx) // flipped sign
407
	tt2d.multiply(p.t, q.t2d)
408

409
	z2.add(p.z, p.z)
410

411
	v.x.subtract(pp, mm)
412
	v.y.add(pp, mm)
413
	v.z.subtract(z2, tt2d) // flipped sign
414
	v.t.add(z2, tt2d) // flipped sign
415
	return v
416
}
417

418
// Doubling.
419

420
fn (mut v ProjectiveP1) double(p ProjectiveP2) ProjectiveP1 {
421
	// var xx, yy, zz2, xplusysq edwards25519.Element
422
	mut xx := Element{}
423
	mut yy := Element{}
424
	mut zz2 := Element{}
425
	mut xplusysq := Element{}
426

427
	xx.square(p.x)
428
	yy.square(p.y)
429
	zz2.square(p.z)
430
	zz2.add(zz2, zz2)
431
	xplusysq.add(p.x, p.y)
432
	xplusysq.square(xplusysq)
433

434
	v.y.add(yy, xx)
435
	v.z.subtract(yy, xx)
436

437
	v.x.subtract(xplusysq, v.y)
438
	v.t.subtract(zz2, v.z)
439
	return v
440
}
441

442
// Negation.
443

444
// negate sets v = -p, and returns v.
445
pub fn (mut v Point) negate(p Point) Point {
446
	check_initialized(p)
447
	v.x.negate(p.x)
448
	v.y.set(p.y)
449
	v.z.set(p.z)
450
	v.t.negate(p.t)
451
	return v
452
}
453

454
// equal returns 1 if v is equivalent to u, and 0 otherwise.
455
pub fn (mut v Point) equal(u Point) int {
456
	check_initialized(v, u)
457

458
	mut t1 := Element{}
459
	mut t2 := Element{}
460
	mut t3 := Element{}
461
	mut t4 := Element{}
462

463
	t1.multiply(v.x, u.z)
464
	t2.multiply(u.x, v.z)
465
	t3.multiply(v.y, u.z)
466
	t4.multiply(u.y, v.z)
467

468
	return t1.equal(t2) & t3.equal(t4)
469
}
470

471
// Constant-time operations
472

473
// selected sets v to a if cond == 1 and to b if cond == 0.
474
fn (mut v ProjectiveCached) selected(a ProjectiveCached, b ProjectiveCached, cond int) ProjectiveCached {
475
	v.ypx.selected(a.ypx, b.ypx, cond)
476
	v.ymx.selected(a.ymx, b.ymx, cond)
477
	v.z.selected(a.z, b.z, cond)
478
	v.t2d.selected(a.t2d, b.t2d, cond)
479
	return v
480
}
481

482
// selected sets v to a if cond == 1 and to b if cond == 0.
483
fn (mut v AffineCached) selected(a AffineCached, b AffineCached, cond int) AffineCached {
484
	v.ypx.selected(a.ypx, b.ypx, cond)
485
	v.ymx.selected(a.ymx, b.ymx, cond)
486
	v.t2d.selected(a.t2d, b.t2d, cond)
487
	return v
488
}
489

490
// cond_neg negates v if cond == 1 and leaves it unchanged if cond == 0.
491
fn (mut v ProjectiveCached) cond_neg(cond int) ProjectiveCached {
492
	mut el := Element{}
493
	v.ypx.swap(mut v.ymx, cond)
494
	v.t2d.selected(el.negate(v.t2d), v.t2d, cond)
495
	return v
496
}
497

498
// cond_neg negates v if cond == 1 and leaves it unchanged if cond == 0.
499
fn (mut v AffineCached) cond_neg(cond int) AffineCached {
500
	mut el := Element{}
501
	v.ypx.swap(mut v.ymx, cond)
502
	v.t2d.selected(el.negate(v.t2d), v.t2d, cond)
503
	return v
504
}
505

506
fn check_on_curve(points ...Point) bool {
507
	for p in points {
508
		mut xx := Element{}
509
		mut yy := Element{}
510
		mut zz := Element{}
511
		mut zzzz := Element{}
512
		xx.square(p.x)
513
		yy.square(p.y)
514
		zz.square(p.z)
515
		zzzz.square(zz)
516
		// -x² + y² = 1 + dx²y²
517
		// -(X/Z)² + (Y/Z)² = 1 + d(X/Z)²(Y/Z)²
518
		// (-X² + Y²)/Z² = 1 + (dX²Y²)/Z⁴
519
		// (-X² + Y²)*Z² = Z⁴ + dX²Y²
520
		mut lhs := Element{}
521
		mut rhs := Element{}
522
		lhs.subtract(yy, xx)
523
		lhs.multiply(lhs, zz)
524
		rhs.multiply(d_const, xx)
525
		rhs.multiply(rhs, yy)
526
		rhs.add(rhs, zzzz)
527

528
		if lhs.equal(rhs) != 1 {
529
			return false
530
		}
531
		/*
532
		if lhs.equal(rhs) != 1 {
533
			lg.error('X, Y, and Z do not specify a point on the curve\nX = $p.x \nY = $p.y\nZ = $p.z')
534
		}*/
535

536
		// xy = T/Z
537
		lhs.multiply(p.x, p.y)
538
		rhs.multiply(p.z, p.t)
539
		/*
540
		if lhs.equal(rhs) != 1 {
541
			lg.error('point $i is not valid\nX = $p.x\nY = $p.y\nZ = $p.z')
542
		}*/
543
		if lhs.equal(rhs) != 1 {
544
			return false
545
		}
546
	}
547
	return true
548
}
549