main
1package ed25519
2
3import fp "github.com/cloudflare/circl/math/fp25519"
4
5type (
6 pointR1 struct{ x, y, z, ta, tb fp.Elt }
7 pointR2 struct {
8 pointR3
9 z2 fp.Elt
10 }
11)
12type pointR3 struct{ addYX, subYX, dt2 fp.Elt }
13
14func (P *pointR1) neg() {
15 fp.Neg(&P.x, &P.x)
16 fp.Neg(&P.ta, &P.ta)
17}
18
19func (P *pointR1) SetIdentity() {
20 P.x = fp.Elt{}
21 fp.SetOne(&P.y)
22 fp.SetOne(&P.z)
23 P.ta = fp.Elt{}
24 P.tb = fp.Elt{}
25}
26
27func (P *pointR1) toAffine() {
28 fp.Inv(&P.z, &P.z)
29 fp.Mul(&P.x, &P.x, &P.z)
30 fp.Mul(&P.y, &P.y, &P.z)
31 fp.Modp(&P.x)
32 fp.Modp(&P.y)
33 fp.SetOne(&P.z)
34 P.ta = P.x
35 P.tb = P.y
36}
37
38func (P *pointR1) ToBytes(k []byte) error {
39 P.toAffine()
40 var x [fp.Size]byte
41 err := fp.ToBytes(k[:fp.Size], &P.y)
42 if err != nil {
43 return err
44 }
45 err = fp.ToBytes(x[:], &P.x)
46 if err != nil {
47 return err
48 }
49 b := x[0] & 1
50 k[paramB-1] = k[paramB-1] | (b << 7)
51 return nil
52}
53
54func (P *pointR1) FromBytes(k []byte) bool {
55 if len(k) != paramB {
56 panic("wrong size")
57 }
58 signX := k[paramB-1] >> 7
59 copy(P.y[:], k[:fp.Size])
60 P.y[fp.Size-1] &= 0x7F
61 p := fp.P()
62 if !isLessThan(P.y[:], p[:]) {
63 return false
64 }
65
66 one, u, v := &fp.Elt{}, &fp.Elt{}, &fp.Elt{}
67 fp.SetOne(one)
68 fp.Sqr(u, &P.y) // u = y^2
69 fp.Mul(v, u, ¶mD) // v = dy^2
70 fp.Sub(u, u, one) // u = y^2-1
71 fp.Add(v, v, one) // v = dy^2+1
72 isQR := fp.InvSqrt(&P.x, u, v) // x = sqrt(u/v)
73 if !isQR {
74 return false
75 }
76 fp.Modp(&P.x) // x = x mod p
77 if fp.IsZero(&P.x) && signX == 1 {
78 return false
79 }
80 if signX != (P.x[0] & 1) {
81 fp.Neg(&P.x, &P.x)
82 }
83 P.ta = P.x
84 P.tb = P.y
85 fp.SetOne(&P.z)
86 return true
87}
88
89// double calculates 2P for curves with A=-1.
90func (P *pointR1) double() {
91 Px, Py, Pz, Pta, Ptb := &P.x, &P.y, &P.z, &P.ta, &P.tb
92 a, b, c, e, f, g, h := Px, Py, Pz, Pta, Px, Py, Ptb
93 fp.Add(e, Px, Py) // x+y
94 fp.Sqr(a, Px) // A = x^2
95 fp.Sqr(b, Py) // B = y^2
96 fp.Sqr(c, Pz) // z^2
97 fp.Add(c, c, c) // C = 2*z^2
98 fp.Add(h, a, b) // H = A+B
99 fp.Sqr(e, e) // (x+y)^2
100 fp.Sub(e, e, h) // E = (x+y)^2-A-B
101 fp.Sub(g, b, a) // G = B-A
102 fp.Sub(f, c, g) // F = C-G
103 fp.Mul(Pz, f, g) // Z = F * G
104 fp.Mul(Px, e, f) // X = E * F
105 fp.Mul(Py, g, h) // Y = G * H, T = E * H
106}
107
108func (P *pointR1) mixAdd(Q *pointR3) {
109 fp.Add(&P.z, &P.z, &P.z) // D = 2*z1
110 P.coreAddition(Q)
111}
112
113func (P *pointR1) add(Q *pointR2) {
114 fp.Mul(&P.z, &P.z, &Q.z2) // D = 2*z1*z2
115 P.coreAddition(&Q.pointR3)
116}
117
118// coreAddition calculates P=P+Q for curves with A=-1.
119func (P *pointR1) coreAddition(Q *pointR3) {
120 Px, Py, Pz, Pta, Ptb := &P.x, &P.y, &P.z, &P.ta, &P.tb
121 addYX2, subYX2, dt2 := &Q.addYX, &Q.subYX, &Q.dt2
122 a, b, c, d, e, f, g, h := Px, Py, &fp.Elt{}, Pz, Pta, Px, Py, Ptb
123 fp.Mul(c, Pta, Ptb) // t1 = ta*tb
124 fp.Sub(h, Py, Px) // y1-x1
125 fp.Add(b, Py, Px) // y1+x1
126 fp.Mul(a, h, subYX2) // A = (y1-x1)*(y2-x2)
127 fp.Mul(b, b, addYX2) // B = (y1+x1)*(y2+x2)
128 fp.Mul(c, c, dt2) // C = 2*D*t1*t2
129 fp.Sub(e, b, a) // E = B-A
130 fp.Add(h, b, a) // H = B+A
131 fp.Sub(f, d, c) // F = D-C
132 fp.Add(g, d, c) // G = D+C
133 fp.Mul(Pz, f, g) // Z = F * G
134 fp.Mul(Px, e, f) // X = E * F
135 fp.Mul(Py, g, h) // Y = G * H, T = E * H
136}
137
138func (P *pointR1) oddMultiples(T []pointR2) {
139 var R pointR2
140 n := len(T)
141 T[0].fromR1(P)
142 _2P := *P
143 _2P.double()
144 R.fromR1(&_2P)
145 for i := 1; i < n; i++ {
146 P.add(&R)
147 T[i].fromR1(P)
148 }
149}
150
151func (P *pointR1) isEqual(Q *pointR1) bool {
152 l, r := &fp.Elt{}, &fp.Elt{}
153 fp.Mul(l, &P.x, &Q.z)
154 fp.Mul(r, &Q.x, &P.z)
155 fp.Sub(l, l, r)
156 b := fp.IsZero(l)
157 fp.Mul(l, &P.y, &Q.z)
158 fp.Mul(r, &Q.y, &P.z)
159 fp.Sub(l, l, r)
160 b = b && fp.IsZero(l)
161 fp.Mul(l, &P.ta, &P.tb)
162 fp.Mul(l, l, &Q.z)
163 fp.Mul(r, &Q.ta, &Q.tb)
164 fp.Mul(r, r, &P.z)
165 fp.Sub(l, l, r)
166 b = b && fp.IsZero(l)
167 return b && !fp.IsZero(&P.z) && !fp.IsZero(&Q.z)
168}
169
170func (P *pointR3) neg() {
171 P.addYX, P.subYX = P.subYX, P.addYX
172 fp.Neg(&P.dt2, &P.dt2)
173}
174
175func (P *pointR2) fromR1(Q *pointR1) {
176 fp.Add(&P.addYX, &Q.y, &Q.x)
177 fp.Sub(&P.subYX, &Q.y, &Q.x)
178 fp.Mul(&P.dt2, &Q.ta, &Q.tb)
179 fp.Mul(&P.dt2, &P.dt2, ¶mD)
180 fp.Add(&P.dt2, &P.dt2, &P.dt2)
181 fp.Add(&P.z2, &Q.z, &Q.z)
182}
183
184func (P *pointR3) cneg(b int) {
185 t := &fp.Elt{}
186 fp.Cswap(&P.addYX, &P.subYX, uint(b))
187 fp.Neg(t, &P.dt2)
188 fp.Cmov(&P.dt2, t, uint(b))
189}
190
191func (P *pointR3) cmov(Q *pointR3, b int) {
192 fp.Cmov(&P.addYX, &Q.addYX, uint(b))
193 fp.Cmov(&P.subYX, &Q.subYX, uint(b))
194 fp.Cmov(&P.dt2, &Q.dt2, uint(b))
195}