edwards25519.mx raw
1 // Copyright (c) 2017 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 package edwards25519
6
7 import (
8 _ "crypto/internal/fips140/check"
9 "crypto/internal/fips140/edwards25519/field"
10 "errors"
11 )
12
13 // Point types.
14
15 type projP1xP1 struct {
16 X, Y, Z, T field.Element
17 }
18
19 type projP2 struct {
20 X, Y, Z field.Element
21 }
22
23 // Point represents a point on the edwards25519 curve.
24 //
25 // This type works similarly to math/big.Int, and all arguments and receivers
26 // are allowed to alias.
27 //
28 // The zero value is NOT valid, and it may be used only as a receiver.
29 type Point struct {
30 // Make the type not comparable (i.e. used with == or as a map key), as
31 // equivalent points can be represented by different Go values.
32 _ incomparable
33
34 // The point is internally represented in extended coordinates (X, Y, Z, T)
35 // where x = X/Z, y = Y/Z, and xy = T/Z per https://eprint.iacr.org/2008/522.
36 x, y, z, t field.Element
37 }
38
39 type incomparable [0]func()
40
41 func checkInitialized(points ...*Point) {
42 for _, p := range points {
43 if p.x == (field.Element{}) && p.y == (field.Element{}) {
44 panic("edwards25519: use of uninitialized Point")
45 }
46 }
47 }
48
49 type projCached struct {
50 YplusX, YminusX, Z, T2d field.Element
51 }
52
53 type affineCached struct {
54 YplusX, YminusX, T2d field.Element
55 }
56
57 // Constructors.
58
59 func (v *projP2) Zero() *projP2 {
60 v.X.Zero()
61 v.Y.One()
62 v.Z.One()
63 return v
64 }
65
66 // identity is the point at infinity.
67 var identity, _ = (&Point{}).SetBytes([]byte{
68 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
69 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0})
70
71 // NewIdentityPoint returns a new Point set to the identity.
72 func NewIdentityPoint() *Point {
73 return (&Point{}).Set(identity)
74 }
75
76 // generator is the canonical curve basepoint. See TestGenerator for the
77 // correspondence of this encoding with the values in RFC 8032.
78 var generator, _ = (&Point{}).SetBytes([]byte{
79 0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
80 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
81 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
82 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66})
83
84 // NewGeneratorPoint returns a new Point set to the canonical generator.
85 func NewGeneratorPoint() *Point {
86 return (&Point{}).Set(generator)
87 }
88
89 func (v *projCached) Zero() *projCached {
90 v.YplusX.One()
91 v.YminusX.One()
92 v.Z.One()
93 v.T2d.Zero()
94 return v
95 }
96
97 func (v *affineCached) Zero() *affineCached {
98 v.YplusX.One()
99 v.YminusX.One()
100 v.T2d.Zero()
101 return v
102 }
103
104 // Assignments.
105
106 // Set sets v = u, and returns v.
107 func (v *Point) Set(u *Point) *Point {
108 *v = *u
109 return v
110 }
111
112 // Encoding.
113
114 // Bytes returns the canonical 32-byte encoding of v, according to RFC 8032,
115 // Section 5.1.2.
116 func (v *Point) Bytes() []byte {
117 // This function is outlined to make the allocations inline in the caller
118 // rather than happen on the heap.
119 var buf [32]byte
120 return v.bytes(&buf)
121 }
122
123 func (v *Point) bytes(buf *[32]byte) []byte {
124 checkInitialized(v)
125
126 var zInv, x, y field.Element
127 zInv.Invert(&v.z) // zInv = 1 / Z
128 x.Multiply(&v.x, &zInv) // x = X / Z
129 y.Multiply(&v.y, &zInv) // y = Y / Z
130
131 out := copyFieldElement(buf, &y)
132 out[31] |= byte(x.IsNegative() << 7)
133 return out
134 }
135
136 var feOne = (&field.Element{}).One()
137
138 // SetBytes sets v = x, where x is a 32-byte encoding of v. If x does not
139 // represent a valid point on the curve, SetBytes returns nil and an error and
140 // the receiver is unchanged. Otherwise, SetBytes returns v.
141 //
142 // Note that SetBytes accepts all non-canonical encodings of valid points.
143 // That is, it follows decoding rules that match most implementations in
144 // the ecosystem rather than RFC 8032.
145 func (v *Point) SetBytes(x []byte) (*Point, error) {
146 // Specifically, the non-canonical encodings that are accepted are
147 // 1) the ones where the field element is not reduced (see the
148 // (*field.Element).SetBytes docs) and
149 // 2) the ones where the x-coordinate is zero and the sign bit is set.
150 //
151 // Read more at https://hdevalence.ca/blog/2020-10-04-its-25519am,
152 // specifically the "Canonical A, R" section.
153
154 y, err := (&field.Element{}).SetBytes(x)
155 if err != nil {
156 return nil, errors.New("edwards25519: invalid point encoding length")
157 }
158
159 // -x² + y² = 1 + dx²y²
160 // x² + dx²y² = x²(dy² + 1) = y² - 1
161 // x² = (y² - 1) / (dy² + 1)
162
163 // u = y² - 1
164 y2 := (&field.Element{}).Square(y)
165 u := (&field.Element{}).Subtract(y2, feOne)
166
167 // v = dy² + 1
168 vv := (&field.Element{}).Multiply(y2, d)
169 vv = vv.Add(vv, feOne)
170
171 // x = +√(u/v)
172 xx, wasSquare := (&field.Element{}).SqrtRatio(u, vv)
173 if wasSquare == 0 {
174 return nil, errors.New("edwards25519: invalid point encoding")
175 }
176
177 // Select the negative square root if the sign bit is set.
178 xxNeg := (&field.Element{}).Negate(xx)
179 xx = xx.Select(xxNeg, xx, int(x[31]>>7))
180
181 v.x.Set(xx)
182 v.y.Set(y)
183 v.z.One()
184 v.t.Multiply(xx, y) // xy = T / Z
185
186 return v, nil
187 }
188
189 func copyFieldElement(buf *[32]byte, v *field.Element) []byte {
190 copy(buf[:], v.Bytes())
191 return buf[:]
192 }
193
194 // Conversions.
195
196 func (v *projP2) FromP1xP1(p *projP1xP1) *projP2 {
197 v.X.Multiply(&p.X, &p.T)
198 v.Y.Multiply(&p.Y, &p.Z)
199 v.Z.Multiply(&p.Z, &p.T)
200 return v
201 }
202
203 func (v *projP2) FromP3(p *Point) *projP2 {
204 v.X.Set(&p.x)
205 v.Y.Set(&p.y)
206 v.Z.Set(&p.z)
207 return v
208 }
209
210 func (v *Point) fromP1xP1(p *projP1xP1) *Point {
211 v.x.Multiply(&p.X, &p.T)
212 v.y.Multiply(&p.Y, &p.Z)
213 v.z.Multiply(&p.Z, &p.T)
214 v.t.Multiply(&p.X, &p.Y)
215 return v
216 }
217
218 func (v *Point) fromP2(p *projP2) *Point {
219 v.x.Multiply(&p.X, &p.Z)
220 v.y.Multiply(&p.Y, &p.Z)
221 v.z.Square(&p.Z)
222 v.t.Multiply(&p.X, &p.Y)
223 return v
224 }
225
226 // d is a constant in the curve equation.
227 var d, _ = (&field.Element{}).SetBytes([]byte{
228 0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75,
229 0xab, 0xd8, 0x41, 0x41, 0x4d, 0x0a, 0x70, 0x00,
230 0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c,
231 0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x03, 0x52})
232 var d2 = (&field.Element{}).Add(d, d)
233
234 func (v *projCached) FromP3(p *Point) *projCached {
235 v.YplusX.Add(&p.y, &p.x)
236 v.YminusX.Subtract(&p.y, &p.x)
237 v.Z.Set(&p.z)
238 v.T2d.Multiply(&p.t, d2)
239 return v
240 }
241
242 func (v *affineCached) FromP3(p *Point) *affineCached {
243 v.YplusX.Add(&p.y, &p.x)
244 v.YminusX.Subtract(&p.y, &p.x)
245 v.T2d.Multiply(&p.t, d2)
246
247 var invZ field.Element
248 invZ.Invert(&p.z)
249 v.YplusX.Multiply(&v.YplusX, &invZ)
250 v.YminusX.Multiply(&v.YminusX, &invZ)
251 v.T2d.Multiply(&v.T2d, &invZ)
252 return v
253 }
254
255 // (Re)addition and subtraction.
256
257 // Add sets v = p + q, and returns v.
258 func (v *Point) Add(p, q *Point) *Point {
259 checkInitialized(p, q)
260 qCached := (&projCached{}).FromP3(q)
261 result := (&projP1xP1{}).Add(p, qCached)
262 return v.fromP1xP1(result)
263 }
264
265 // Subtract sets v = p - q, and returns v.
266 func (v *Point) Subtract(p, q *Point) *Point {
267 checkInitialized(p, q)
268 qCached := (&projCached{}).FromP3(q)
269 result := (&projP1xP1{}).Sub(p, qCached)
270 return v.fromP1xP1(result)
271 }
272
273 func (v *projP1xP1) Add(p *Point, q *projCached) *projP1xP1 {
274 var YplusX, YminusX, PP, MM, TT2d, ZZ2 field.Element
275
276 YplusX.Add(&p.y, &p.x)
277 YminusX.Subtract(&p.y, &p.x)
278
279 PP.Multiply(&YplusX, &q.YplusX)
280 MM.Multiply(&YminusX, &q.YminusX)
281 TT2d.Multiply(&p.t, &q.T2d)
282 ZZ2.Multiply(&p.z, &q.Z)
283
284 ZZ2.Add(&ZZ2, &ZZ2)
285
286 v.X.Subtract(&PP, &MM)
287 v.Y.Add(&PP, &MM)
288 v.Z.Add(&ZZ2, &TT2d)
289 v.T.Subtract(&ZZ2, &TT2d)
290 return v
291 }
292
293 func (v *projP1xP1) Sub(p *Point, q *projCached) *projP1xP1 {
294 var YplusX, YminusX, PP, MM, TT2d, ZZ2 field.Element
295
296 YplusX.Add(&p.y, &p.x)
297 YminusX.Subtract(&p.y, &p.x)
298
299 PP.Multiply(&YplusX, &q.YminusX) // flipped sign
300 MM.Multiply(&YminusX, &q.YplusX) // flipped sign
301 TT2d.Multiply(&p.t, &q.T2d)
302 ZZ2.Multiply(&p.z, &q.Z)
303
304 ZZ2.Add(&ZZ2, &ZZ2)
305
306 v.X.Subtract(&PP, &MM)
307 v.Y.Add(&PP, &MM)
308 v.Z.Subtract(&ZZ2, &TT2d) // flipped sign
309 v.T.Add(&ZZ2, &TT2d) // flipped sign
310 return v
311 }
312
313 func (v *projP1xP1) AddAffine(p *Point, q *affineCached) *projP1xP1 {
314 var YplusX, YminusX, PP, MM, TT2d, Z2 field.Element
315
316 YplusX.Add(&p.y, &p.x)
317 YminusX.Subtract(&p.y, &p.x)
318
319 PP.Multiply(&YplusX, &q.YplusX)
320 MM.Multiply(&YminusX, &q.YminusX)
321 TT2d.Multiply(&p.t, &q.T2d)
322
323 Z2.Add(&p.z, &p.z)
324
325 v.X.Subtract(&PP, &MM)
326 v.Y.Add(&PP, &MM)
327 v.Z.Add(&Z2, &TT2d)
328 v.T.Subtract(&Z2, &TT2d)
329 return v
330 }
331
332 func (v *projP1xP1) SubAffine(p *Point, q *affineCached) *projP1xP1 {
333 var YplusX, YminusX, PP, MM, TT2d, Z2 field.Element
334
335 YplusX.Add(&p.y, &p.x)
336 YminusX.Subtract(&p.y, &p.x)
337
338 PP.Multiply(&YplusX, &q.YminusX) // flipped sign
339 MM.Multiply(&YminusX, &q.YplusX) // flipped sign
340 TT2d.Multiply(&p.t, &q.T2d)
341
342 Z2.Add(&p.z, &p.z)
343
344 v.X.Subtract(&PP, &MM)
345 v.Y.Add(&PP, &MM)
346 v.Z.Subtract(&Z2, &TT2d) // flipped sign
347 v.T.Add(&Z2, &TT2d) // flipped sign
348 return v
349 }
350
351 // Doubling.
352
353 func (v *projP1xP1) Double(p *projP2) *projP1xP1 {
354 var XX, YY, ZZ2, XplusYsq field.Element
355
356 XX.Square(&p.X)
357 YY.Square(&p.Y)
358 ZZ2.Square(&p.Z)
359 ZZ2.Add(&ZZ2, &ZZ2)
360 XplusYsq.Add(&p.X, &p.Y)
361 XplusYsq.Square(&XplusYsq)
362
363 v.Y.Add(&YY, &XX)
364 v.Z.Subtract(&YY, &XX)
365
366 v.X.Subtract(&XplusYsq, &v.Y)
367 v.T.Subtract(&ZZ2, &v.Z)
368 return v
369 }
370
371 // Negation.
372
373 // Negate sets v = -p, and returns v.
374 func (v *Point) Negate(p *Point) *Point {
375 checkInitialized(p)
376 v.x.Negate(&p.x)
377 v.y.Set(&p.y)
378 v.z.Set(&p.z)
379 v.t.Negate(&p.t)
380 return v
381 }
382
383 // Equal returns 1 if v is equivalent to u, and 0 otherwise.
384 func (v *Point) Equal(u *Point) int {
385 checkInitialized(v, u)
386
387 var t1, t2, t3, t4 field.Element
388 t1.Multiply(&v.x, &u.z)
389 t2.Multiply(&u.x, &v.z)
390 t3.Multiply(&v.y, &u.z)
391 t4.Multiply(&u.y, &v.z)
392
393 return t1.Equal(&t2) & t3.Equal(&t4)
394 }
395
396 // Constant-time operations
397
398 // Select sets v to a if cond == 1 and to b if cond == 0.
399 func (v *projCached) Select(a, b *projCached, cond int) *projCached {
400 v.YplusX.Select(&a.YplusX, &b.YplusX, cond)
401 v.YminusX.Select(&a.YminusX, &b.YminusX, cond)
402 v.Z.Select(&a.Z, &b.Z, cond)
403 v.T2d.Select(&a.T2d, &b.T2d, cond)
404 return v
405 }
406
407 // Select sets v to a if cond == 1 and to b if cond == 0.
408 func (v *affineCached) Select(a, b *affineCached, cond int) *affineCached {
409 v.YplusX.Select(&a.YplusX, &b.YplusX, cond)
410 v.YminusX.Select(&a.YminusX, &b.YminusX, cond)
411 v.T2d.Select(&a.T2d, &b.T2d, cond)
412 return v
413 }
414
415 // CondNeg negates v if cond == 1 and leaves it unchanged if cond == 0.
416 func (v *projCached) CondNeg(cond int) *projCached {
417 v.YplusX.Swap(&v.YminusX, cond)
418 v.T2d.Select((&field.Element{}).Negate(&v.T2d), &v.T2d, cond)
419 return v
420 }
421
422 // CondNeg negates v if cond == 1 and leaves it unchanged if cond == 0.
423 func (v *affineCached) CondNeg(cond int) *affineCached {
424 v.YplusX.Swap(&v.YminusX, cond)
425 v.T2d.Select((&field.Element{}).Negate(&v.T2d), &v.T2d, cond)
426 return v
427 }
428