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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
package goldilocks
import (
"fmt"
fp "github.com/cloudflare/circl/math/fp448"
)
type twistPoint struct{ x, y, z, ta, tb fp.Elt }
type preTwistPointAffine struct{ addYX, subYX, dt2 fp.Elt }
type preTwistPointProy struct {
preTwistPointAffine
z2 fp.Elt
}
func (P *twistPoint) String() string {
return fmt.Sprintf("x: %v\ny: %v\nz: %v\nta: %v\ntb: %v", P.x, P.y, P.z, P.ta, P.tb)
}
// cneg conditionally negates the point if b=1.
func (P *twistPoint) cneg(b uint) {
t := &fp.Elt{}
fp.Neg(t, &P.x)
fp.Cmov(&P.x, t, b)
fp.Neg(t, &P.ta)
fp.Cmov(&P.ta, t, b)
}
// Double updates P with 2P.
func (P *twistPoint) Double() {
// This is formula (7) from "Twisted Edwards Curves Revisited" by
// Hisil H., Wong K.KH., Carter G., Dawson E. (2008)
// https://doi.org/10.1007/978-3-540-89255-7_20
Px, Py, Pz, Pta, Ptb := &P.x, &P.y, &P.z, &P.ta, &P.tb
a, b, c, e, f, g, h := Px, Py, Pz, Pta, Px, Py, Ptb
fp.Add(e, Px, Py) // x+y
fp.Sqr(a, Px) // A = x^2
fp.Sqr(b, Py) // B = y^2
fp.Sqr(c, Pz) // z^2
fp.Add(c, c, c) // C = 2*z^2
fp.Add(h, a, b) // H = A+B
fp.Sqr(e, e) // (x+y)^2
fp.Sub(e, e, h) // E = (x+y)^2-A-B
fp.Sub(g, b, a) // G = B-A
fp.Sub(f, c, g) // F = C-G
fp.Mul(Pz, f, g) // Z = F * G
fp.Mul(Px, e, f) // X = E * F
fp.Mul(Py, g, h) // Y = G * H, T = E * H
}
// mixAdd calculates P= P+Q, where Q is a precomputed point with Z_Q = 1.
func (P *twistPoint) mixAddZ1(Q *preTwistPointAffine) {
fp.Add(&P.z, &P.z, &P.z) // D = 2*z1 (z2=1)
P.coreAddition(Q)
}
// coreAddition calculates P=P+Q for curves with A=-1.
func (P *twistPoint) coreAddition(Q *preTwistPointAffine) {
// This is the formula following (5) from "Twisted Edwards Curves Revisited" by
// Hisil H., Wong K.KH., Carter G., Dawson E. (2008)
// https://doi.org/10.1007/978-3-540-89255-7_20
Px, Py, Pz, Pta, Ptb := &P.x, &P.y, &P.z, &P.ta, &P.tb
addYX2, subYX2, dt2 := &Q.addYX, &Q.subYX, &Q.dt2
a, b, c, d, e, f, g, h := Px, Py, &fp.Elt{}, Pz, Pta, Px, Py, Ptb
fp.Mul(c, Pta, Ptb) // t1 = ta*tb
fp.Sub(h, Py, Px) // y1-x1
fp.Add(b, Py, Px) // y1+x1
fp.Mul(a, h, subYX2) // A = (y1-x1)*(y2-x2)
fp.Mul(b, b, addYX2) // B = (y1+x1)*(y2+x2)
fp.Mul(c, c, dt2) // C = 2*D*t1*t2
fp.Sub(e, b, a) // E = B-A
fp.Add(h, b, a) // H = B+A
fp.Sub(f, d, c) // F = D-C
fp.Add(g, d, c) // G = D+C
fp.Mul(Pz, f, g) // Z = F * G
fp.Mul(Px, e, f) // X = E * F
fp.Mul(Py, g, h) // Y = G * H, T = E * H
}
func (P *preTwistPointAffine) neg() {
P.addYX, P.subYX = P.subYX, P.addYX
fp.Neg(&P.dt2, &P.dt2)
}
func (P *preTwistPointAffine) cneg(b int) {
t := &fp.Elt{}
fp.Cswap(&P.addYX, &P.subYX, uint(b))
fp.Neg(t, &P.dt2)
fp.Cmov(&P.dt2, t, uint(b))
}
func (P *preTwistPointAffine) cmov(Q *preTwistPointAffine, b uint) {
fp.Cmov(&P.addYX, &Q.addYX, b)
fp.Cmov(&P.subYX, &Q.subYX, b)
fp.Cmov(&P.dt2, &Q.dt2, b)
}
// mixAdd calculates P= P+Q, where Q is a precomputed point with Z_Q != 1.
func (P *twistPoint) mixAdd(Q *preTwistPointProy) {
fp.Mul(&P.z, &P.z, &Q.z2) // D = 2*z1*z2
P.coreAddition(&Q.preTwistPointAffine)
}
// oddMultiples calculates T[i] = (2*i-1)P for 0 < i < len(T).
func (P *twistPoint) oddMultiples(T []preTwistPointProy) {
if n := len(T); n > 0 {
T[0].FromTwistPoint(P)
_2P := *P
_2P.Double()
R := &preTwistPointProy{}
R.FromTwistPoint(&_2P)
for i := 1; i < n; i++ {
P.mixAdd(R)
T[i].FromTwistPoint(P)
}
}
}
// cmov conditionally moves Q into P if b=1.
func (P *preTwistPointProy) cmov(Q *preTwistPointProy, b uint) {
P.preTwistPointAffine.cmov(&Q.preTwistPointAffine, b)
fp.Cmov(&P.z2, &Q.z2, b)
}
// FromTwistPoint precomputes some coordinates of Q for missed addition.
func (P *preTwistPointProy) FromTwistPoint(Q *twistPoint) {
fp.Add(&P.addYX, &Q.y, &Q.x) // addYX = X + Y
fp.Sub(&P.subYX, &Q.y, &Q.x) // subYX = Y - X
fp.Mul(&P.dt2, &Q.ta, &Q.tb) // T = ta*tb
fp.Mul(&P.dt2, &P.dt2, ¶mDTwist) // D*T
fp.Add(&P.dt2, &P.dt2, &P.dt2) // dt2 = 2*D*T
fp.Add(&P.z2, &Q.z, &Q.z) // z2 = 2*Z
}
|
