Debian Codegraph @

libgo/go/crypto/ed25519/internal/edwards25519/edwards25519.go

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/ed25519/internal/edwards25519/field"
9 "errors"
10 )
11
12 // Point types.
13
14 type projP1xP1 struct {
15 X, Y, Z, T field.Element
16 }
17
18 type projP2 struct {
19 X, Y, Z field.Element
20 }
21
22 // Point represents a point on the edwards25519 curve.
23 //
24 // This type works similarly to math/big.Int, and all arguments and receivers
25 // are allowed to alias.
26 //
27 // The zero value is NOT valid, and it may be used only as a receiver.
28 type Point struct {
29 // The point is internally represented in extended coordinates (X, Y, Z, T)
30 // where x = X/Z, y = Y/Z, and xy = T/Z per https://eprint.iacr.org/2008/522.
31 x, y, z, t field.Element
32
33 // Make the type not comparable (i.e. used with == or as a map key), as
34 // equivalent points can be represented by different Go values.
35 _ incomparable
36 }
37
38 type incomparable [0]func()
39
40 func checkInitialized(points ...*Point) {
41 for _, p := range points {
42 if p.x == (field.Element{}) && p.y == (field.Element{}) {
43 panic("edwards25519: use of uninitialized Point")
44 }
45 }
46 }
47
48 type projCached struct {
49 YplusX, YminusX, Z, T2d field.Element
50 }
51
52 type affineCached struct {
53 YplusX, YminusX, T2d field.Element
54 }
55
56 // Constructors.
57
58 func (v *projP2) Zero() *projP2 {
59 v.X.Zero()
60 v.Y.One()
61 v.Z.One()
62 return v
63 }
64
65 // identity is the point at infinity.
66 var identity, _ = new(Point).SetBytes([]byte{
67 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
68 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0})
69
70 // NewIdentityPoint returns a new Point set to the identity.
71 func NewIdentityPoint() *Point {
72 return new(Point).Set(identity)
73 }
74
75 // generator is the canonical curve basepoint. See TestGenerator for the
76 // correspondence of this encoding with the values in RFC 8032.
77 var generator, _ = new(Point).SetBytes([]byte{
78 0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
79 0x66, 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
83 // NewGeneratorPoint returns a new Point set to the canonical generator.
84 func NewGeneratorPoint() *Point {
85 return new(Point).Set(generator)
86 }
87
88 func (v *projCached) Zero() *projCached {
89 v.YplusX.One()
90 v.YminusX.One()
91 v.Z.One()
92 v.T2d.Zero()
93 return v
94 }
95
96 func (v *affineCached) Zero() *affineCached {
97 v.YplusX.One()
98 v.YminusX.One()
99 v.T2d.Zero()
100 return v
101 }
102
103 // Assignments.
104
105 // Set sets v = u, and returns v.
106 func (v *Point) Set(u *Point) *Point {
107 *v = *u
108 return v
109 }
110
111 // Encoding.
112
113 // Bytes returns the canonical 32-byte encoding of v, according to RFC 8032,
114 // Section 5.1.2.
115 func (v *Point) Bytes() []byte {
116 // This function is outlined to make the allocations inline in the caller
117 // rather than happen on the heap.
118 var buf [32]byte
119 return v.bytes(&buf)
120 }
121
122 func (v *Point) bytes(buf *[32]byte) []byte {
123 checkInitialized(v)
124
125 var zInv, x, y field.Element
126 zInv.Invert(&v.z) // zInv = 1 / Z
127 x.Multiply(&v.x, &zInv) // x = X / Z
128 y.Multiply(&v.y, &zInv) // y = Y / Z
129
130 out := copyFieldElement(buf, &y)
131 out[31] |= byte(x.IsNegative() << 7)
132 return out
133 }
134
135 var feOne = new(field.Element).One()
136
137 // SetBytes sets v = x, where x is a 32-byte encoding of v. If x does not
138 // represent a valid point on the curve, SetBytes returns nil and an error and
139 // the receiver is unchanged. Otherwise, SetBytes returns v.
140 //
141 // Note that SetBytes accepts all non-canonical encodings of valid points.
142 // That is, it follows decoding rules that match most implementations in
143 // the ecosystem rather than RFC 8032.
144 func (v *Point) SetBytes(x []byte) (*Point, error) {
145 // Specifically, the non-canonical encodings that are accepted are
146 // 1) the ones where the field element is not reduced (see the
147 // (*field.Element).SetBytes docs) and
148 // 2) the ones where the x-coordinate is zero and the sign bit is set.
149 //
150 // This is consistent with crypto/ed25519/internal/edwards25519. Read more
151 // at https://hdevalence.ca/blog/2020-10-04-its-25519am, specifically the
152 // "Canonical A, R" section.
153
154 if len(x) != 32 {
155 return nil, errors.New("edwards25519: invalid point encoding length")
156 }
157 y := new(field.Element).SetBytes(x)
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 := new(field.Element).Square(y)
165 u := new(field.Element).Subtract(y2, feOne)
166
167 // v = dy² + 1
168 vv := new(field.Element).Multiply(y2, d)
169 vv = vv.Add(vv, feOne)
170
171 // x = +√(u/v)
172 xx, wasSquare := new(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 := new(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 = new(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 = new(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 := new(projCached).FromP3(q)
261 result := new(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 := new(projCached).FromP3(q)
269 result := new(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(new(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(new(field.Element).Negate(&v.T2d), &v.T2d, cond)
426 return v
427 }