twistPoint.go raw
1 package goldilocks
2
3 import (
4 "fmt"
5
6 fp "github.com/cloudflare/circl/math/fp448"
7 )
8
9 type twistPoint struct{ x, y, z, ta, tb fp.Elt }
10
11 type preTwistPointAffine struct{ addYX, subYX, dt2 fp.Elt }
12
13 type preTwistPointProy struct {
14 preTwistPointAffine
15 z2 fp.Elt
16 }
17
18 func (P *twistPoint) String() string {
19 return fmt.Sprintf("x: %v\ny: %v\nz: %v\nta: %v\ntb: %v", P.x, P.y, P.z, P.ta, P.tb)
20 }
21
22 // cneg conditionally negates the point if b=1.
23 func (P *twistPoint) cneg(b uint) {
24 t := &fp.Elt{}
25 fp.Neg(t, &P.x)
26 fp.Cmov(&P.x, t, b)
27 fp.Neg(t, &P.ta)
28 fp.Cmov(&P.ta, t, b)
29 }
30
31 // Double updates P with 2P.
32 func (P *twistPoint) Double() {
33 // This is formula (7) from "Twisted Edwards Curves Revisited" by
34 // Hisil H., Wong K.KH., Carter G., Dawson E. (2008)
35 // https://doi.org/10.1007/978-3-540-89255-7_20
36 Px, Py, Pz, Pta, Ptb := &P.x, &P.y, &P.z, &P.ta, &P.tb
37 a, b, c, e, f, g, h := Px, Py, Pz, Pta, Px, Py, Ptb
38 fp.Add(e, Px, Py) // x+y
39 fp.Sqr(a, Px) // A = x^2
40 fp.Sqr(b, Py) // B = y^2
41 fp.Sqr(c, Pz) // z^2
42 fp.Add(c, c, c) // C = 2*z^2
43 fp.Add(h, a, b) // H = A+B
44 fp.Sqr(e, e) // (x+y)^2
45 fp.Sub(e, e, h) // E = (x+y)^2-A-B
46 fp.Sub(g, b, a) // G = B-A
47 fp.Sub(f, c, g) // F = C-G
48 fp.Mul(Pz, f, g) // Z = F * G
49 fp.Mul(Px, e, f) // X = E * F
50 fp.Mul(Py, g, h) // Y = G * H, T = E * H
51 }
52
53 // mixAdd calculates P= P+Q, where Q is a precomputed point with Z_Q = 1.
54 func (P *twistPoint) mixAddZ1(Q *preTwistPointAffine) {
55 fp.Add(&P.z, &P.z, &P.z) // D = 2*z1 (z2=1)
56 P.coreAddition(Q)
57 }
58
59 // coreAddition calculates P=P+Q for curves with A=-1.
60 func (P *twistPoint) coreAddition(Q *preTwistPointAffine) {
61 // This is the formula following (5) from "Twisted Edwards Curves Revisited" by
62 // Hisil H., Wong K.KH., Carter G., Dawson E. (2008)
63 // https://doi.org/10.1007/978-3-540-89255-7_20
64 Px, Py, Pz, Pta, Ptb := &P.x, &P.y, &P.z, &P.ta, &P.tb
65 addYX2, subYX2, dt2 := &Q.addYX, &Q.subYX, &Q.dt2
66 a, b, c, d, e, f, g, h := Px, Py, &fp.Elt{}, Pz, Pta, Px, Py, Ptb
67 fp.Mul(c, Pta, Ptb) // t1 = ta*tb
68 fp.Sub(h, Py, Px) // y1-x1
69 fp.Add(b, Py, Px) // y1+x1
70 fp.Mul(a, h, subYX2) // A = (y1-x1)*(y2-x2)
71 fp.Mul(b, b, addYX2) // B = (y1+x1)*(y2+x2)
72 fp.Mul(c, c, dt2) // C = 2*D*t1*t2
73 fp.Sub(e, b, a) // E = B-A
74 fp.Add(h, b, a) // H = B+A
75 fp.Sub(f, d, c) // F = D-C
76 fp.Add(g, d, c) // G = D+C
77 fp.Mul(Pz, f, g) // Z = F * G
78 fp.Mul(Px, e, f) // X = E * F
79 fp.Mul(Py, g, h) // Y = G * H, T = E * H
80 }
81
82 func (P *preTwistPointAffine) neg() {
83 P.addYX, P.subYX = P.subYX, P.addYX
84 fp.Neg(&P.dt2, &P.dt2)
85 }
86
87 func (P *preTwistPointAffine) cneg(b int) {
88 t := &fp.Elt{}
89 fp.Cswap(&P.addYX, &P.subYX, uint(b))
90 fp.Neg(t, &P.dt2)
91 fp.Cmov(&P.dt2, t, uint(b))
92 }
93
94 func (P *preTwistPointAffine) cmov(Q *preTwistPointAffine, b uint) {
95 fp.Cmov(&P.addYX, &Q.addYX, b)
96 fp.Cmov(&P.subYX, &Q.subYX, b)
97 fp.Cmov(&P.dt2, &Q.dt2, b)
98 }
99
100 // mixAdd calculates P= P+Q, where Q is a precomputed point with Z_Q != 1.
101 func (P *twistPoint) mixAdd(Q *preTwistPointProy) {
102 fp.Mul(&P.z, &P.z, &Q.z2) // D = 2*z1*z2
103 P.coreAddition(&Q.preTwistPointAffine)
104 }
105
106 // oddMultiples calculates T[i] = (2*i-1)P for 0 < i < len(T).
107 func (P *twistPoint) oddMultiples(T []preTwistPointProy) {
108 if n := len(T); n > 0 {
109 T[0].FromTwistPoint(P)
110 _2P := *P
111 _2P.Double()
112 R := &preTwistPointProy{}
113 R.FromTwistPoint(&_2P)
114 for i := 1; i < n; i++ {
115 P.mixAdd(R)
116 T[i].FromTwistPoint(P)
117 }
118 }
119 }
120
121 // cmov conditionally moves Q into P if b=1.
122 func (P *preTwistPointProy) cmov(Q *preTwistPointProy, b uint) {
123 P.preTwistPointAffine.cmov(&Q.preTwistPointAffine, b)
124 fp.Cmov(&P.z2, &Q.z2, b)
125 }
126
127 // FromTwistPoint precomputes some coordinates of Q for missed addition.
128 func (P *preTwistPointProy) FromTwistPoint(Q *twistPoint) {
129 fp.Add(&P.addYX, &Q.y, &Q.x) // addYX = X + Y
130 fp.Sub(&P.subYX, &Q.y, &Q.x) // subYX = Y - X
131 fp.Mul(&P.dt2, &Q.ta, &Q.tb) // T = ta*tb
132 fp.Mul(&P.dt2, &P.dt2, ¶mDTwist) // D*T
133 fp.Add(&P.dt2, &P.dt2, &P.dt2) // dt2 = 2*D*T
134 fp.Add(&P.z2, &Q.z, &Q.z) // z2 = 2*Z
135 }
136