point.go raw
1 package avx
2
3 // Point operations on the secp256k1 curve.
4 // Affine: (x, y) where y² = x³ + 7
5 // Jacobian: (X, Y, Z) where affine = (X/Z², Y/Z³)
6
7 // SetInfinity sets the point to the point at infinity.
8 func (p *AffinePoint) SetInfinity() *AffinePoint {
9 p.X = FieldZero
10 p.Y = FieldZero
11 p.Infinity = true
12 return p
13 }
14
15 // IsInfinity returns true if the point is the point at infinity.
16 func (p *AffinePoint) IsInfinity() bool {
17 return p.Infinity
18 }
19
20 // Set sets p to the value of q.
21 func (p *AffinePoint) Set(q *AffinePoint) *AffinePoint {
22 p.X = q.X
23 p.Y = q.Y
24 p.Infinity = q.Infinity
25 return p
26 }
27
28 // Equal returns true if two points are equal.
29 func (p *AffinePoint) Equal(q *AffinePoint) bool {
30 if p.Infinity && q.Infinity {
31 return true
32 }
33 if p.Infinity || q.Infinity {
34 return false
35 }
36 return p.X.Equal(&q.X) && p.Y.Equal(&q.Y)
37 }
38
39 // Negate sets p = -q (reflection over x-axis).
40 func (p *AffinePoint) Negate(q *AffinePoint) *AffinePoint {
41 if q.Infinity {
42 p.SetInfinity()
43 return p
44 }
45 p.X = q.X
46 p.Y.Negate(&q.Y)
47 p.Infinity = false
48 return p
49 }
50
51 // IsOnCurve returns true if the point is on the secp256k1 curve.
52 func (p *AffinePoint) IsOnCurve() bool {
53 if p.Infinity {
54 return true
55 }
56
57 // Check y² = x³ + 7
58 var y2, x2, x3, rhs FieldElement
59
60 y2.Sqr(&p.Y)
61
62 x2.Sqr(&p.X)
63 x3.Mul(&x2, &p.X)
64
65 // rhs = x³ + 7
66 var seven FieldElement
67 seven.N[0].Lo = 7
68 rhs.Add(&x3, &seven)
69
70 return y2.Equal(&rhs)
71 }
72
73 // SetXY sets the point to (x, y).
74 func (p *AffinePoint) SetXY(x, y *FieldElement) *AffinePoint {
75 p.X = *x
76 p.Y = *y
77 p.Infinity = false
78 return p
79 }
80
81 // SetCompressed sets the point from compressed form (x coordinate + sign bit).
82 // Returns true if successful.
83 func (p *AffinePoint) SetCompressed(x *FieldElement, odd bool) bool {
84 // Compute y² = x³ + 7
85 var y2, x2, x3 FieldElement
86
87 x2.Sqr(x)
88 x3.Mul(&x2, x)
89
90 // y² = x³ + 7
91 var seven FieldElement
92 seven.N[0].Lo = 7
93 y2.Add(&x3, &seven)
94
95 // Compute y = sqrt(y²)
96 var y FieldElement
97 if !y.Sqrt(&y2) {
98 return false // No square root exists
99 }
100
101 // Choose the correct sign
102 if y.IsOdd() != odd {
103 y.Negate(&y)
104 }
105
106 p.X = *x
107 p.Y = y
108 p.Infinity = false
109 return true
110 }
111
112 // Jacobian point operations
113
114 // SetInfinity sets the Jacobian point to the point at infinity.
115 func (p *JacobianPoint) SetInfinity() *JacobianPoint {
116 p.X = FieldOne
117 p.Y = FieldOne
118 p.Z = FieldZero
119 p.Infinity = true
120 return p
121 }
122
123 // IsInfinity returns true if the point is the point at infinity.
124 func (p *JacobianPoint) IsInfinity() bool {
125 return p.Infinity || p.Z.IsZero()
126 }
127
128 // Set sets p to the value of q.
129 func (p *JacobianPoint) Set(q *JacobianPoint) *JacobianPoint {
130 p.X = q.X
131 p.Y = q.Y
132 p.Z = q.Z
133 p.Infinity = q.Infinity
134 return p
135 }
136
137 // FromAffine converts an affine point to Jacobian coordinates.
138 func (p *JacobianPoint) FromAffine(q *AffinePoint) *JacobianPoint {
139 if q.Infinity {
140 p.SetInfinity()
141 return p
142 }
143 p.X = q.X
144 p.Y = q.Y
145 p.Z = FieldOne
146 p.Infinity = false
147 return p
148 }
149
150 // ToAffine converts a Jacobian point to affine coordinates.
151 func (p *JacobianPoint) ToAffine(q *AffinePoint) *AffinePoint {
152 if p.IsInfinity() {
153 q.SetInfinity()
154 return q
155 }
156
157 // affine = (X/Z², Y/Z³)
158 var zInv, zInv2, zInv3 FieldElement
159
160 zInv.Inverse(&p.Z)
161 zInv2.Sqr(&zInv)
162 zInv3.Mul(&zInv2, &zInv)
163
164 q.X.Mul(&p.X, &zInv2)
165 q.Y.Mul(&p.Y, &zInv3)
166 q.Infinity = false
167
168 return q
169 }
170
171 // Double sets p = 2*q using Jacobian coordinates.
172 // Standard Jacobian doubling for y²=x³+b (secp256k1 has a=0):
173 // M = 3*X₁²
174 // S = 4*X₁*Y₁²
175 // T = 8*Y₁⁴
176 // X₃ = M² - 2*S
177 // Y₃ = M*(S - X₃) - T
178 // Z₃ = 2*Y₁*Z₁
179 func (p *JacobianPoint) Double(q *JacobianPoint) *JacobianPoint {
180 if q.IsInfinity() {
181 p.SetInfinity()
182 return p
183 }
184
185 var y2, m, x2, s, t, tmp FieldElement
186 var x3, y3, z3 FieldElement // Use temporaries to avoid aliasing issues
187
188 // Y² = Y₁²
189 y2.Sqr(&q.Y)
190
191 // M = 3*X₁² (for a=0 curves like secp256k1)
192 x2.Sqr(&q.X)
193 m.MulInt(&x2, 3)
194
195 // S = 4*X₁*Y₁²
196 s.Mul(&q.X, &y2)
197 s.MulInt(&s, 4)
198
199 // T = 8*Y₁⁴
200 t.Sqr(&y2)
201 t.MulInt(&t, 8)
202
203 // X₃ = M² - 2*S
204 x3.Sqr(&m)
205 tmp.Double(&s)
206 x3.Sub(&x3, &tmp)
207
208 // Y₃ = M*(S - X₃) - T
209 tmp.Sub(&s, &x3)
210 y3.Mul(&m, &tmp)
211 y3.Sub(&y3, &t)
212
213 // Z₃ = 2*Y₁*Z₁
214 z3.Mul(&q.Y, &q.Z)
215 z3.Double(&z3)
216
217 // Now copy to output (safe even if p == q)
218 p.X = x3
219 p.Y = y3
220 p.Z = z3
221 p.Infinity = false
222 return p
223 }
224
225 // Add sets p = q + r using Jacobian coordinates.
226 // This is the complete addition formula.
227 func (p *JacobianPoint) Add(q, r *JacobianPoint) *JacobianPoint {
228 if q.IsInfinity() {
229 p.Set(r)
230 return p
231 }
232 if r.IsInfinity() {
233 p.Set(q)
234 return p
235 }
236
237 // Algorithm:
238 // U₁ = X₁*Z₂²
239 // U₂ = X₂*Z₁²
240 // S₁ = Y₁*Z₂³
241 // S₂ = Y₂*Z₁³
242 // H = U₂ - U₁
243 // R = S₂ - S₁
244 // If H = 0 and R = 0: return Double(q)
245 // If H = 0 and R ≠ 0: return Infinity
246 // X₃ = R² - H³ - 2*U₁*H²
247 // Y₃ = R*(U₁*H² - X₃) - S₁*H³
248 // Z₃ = H*Z₁*Z₂
249
250 var u1, u2, s1, s2, h, rr, h2, h3, u1h2 FieldElement
251 var z1sq, z2sq, z1cu, z2cu FieldElement
252 var x3, y3, z3 FieldElement // Use temporaries to avoid aliasing issues
253
254 z1sq.Sqr(&q.Z)
255 z2sq.Sqr(&r.Z)
256 z1cu.Mul(&z1sq, &q.Z)
257 z2cu.Mul(&z2sq, &r.Z)
258
259 u1.Mul(&q.X, &z2sq)
260 u2.Mul(&r.X, &z1sq)
261 s1.Mul(&q.Y, &z2cu)
262 s2.Mul(&r.Y, &z1cu)
263
264 h.Sub(&u2, &u1)
265 rr.Sub(&s2, &s1)
266
267 // Check for special cases
268 if h.IsZero() {
269 if rr.IsZero() {
270 // Points are equal, use doubling
271 return p.Double(q)
272 }
273 // Points are inverses, return infinity
274 p.SetInfinity()
275 return p
276 }
277
278 h2.Sqr(&h)
279 h3.Mul(&h2, &h)
280 u1h2.Mul(&u1, &h2)
281
282 // X₃ = R² - H³ - 2*U₁*H²
283 var r2, u1h2_2 FieldElement
284 r2.Sqr(&rr)
285 u1h2_2.Double(&u1h2)
286 x3.Sub(&r2, &h3)
287 x3.Sub(&x3, &u1h2_2)
288
289 // Y₃ = R*(U₁*H² - X₃) - S₁*H³
290 var tmp, s1h3 FieldElement
291 tmp.Sub(&u1h2, &x3)
292 y3.Mul(&rr, &tmp)
293 s1h3.Mul(&s1, &h3)
294 y3.Sub(&y3, &s1h3)
295
296 // Z₃ = H*Z₁*Z₂
297 z3.Mul(&q.Z, &r.Z)
298 z3.Mul(&z3, &h)
299
300 // Now copy to output (safe even if p == q or p == r)
301 p.X = x3
302 p.Y = y3
303 p.Z = z3
304 p.Infinity = false
305 return p
306 }
307
308 // AddAffine sets p = q + r where q is Jacobian and r is affine.
309 // More efficient than converting r to Jacobian first.
310 func (p *JacobianPoint) AddAffine(q *JacobianPoint, r *AffinePoint) *JacobianPoint {
311 if q.IsInfinity() {
312 p.FromAffine(r)
313 return p
314 }
315 if r.Infinity {
316 p.Set(q)
317 return p
318 }
319
320 // When Z₂ = 1 (affine point), formulas simplify:
321 // U₁ = X₁
322 // U₂ = X₂*Z₁²
323 // S₁ = Y₁
324 // S₂ = Y₂*Z₁³
325
326 var u2, s2, h, rr, h2, h3, u1h2 FieldElement
327 var z1sq, z1cu FieldElement
328 var x3, y3, z3 FieldElement // Use temporaries to avoid aliasing issues
329
330 z1sq.Sqr(&q.Z)
331 z1cu.Mul(&z1sq, &q.Z)
332
333 u2.Mul(&r.X, &z1sq)
334 s2.Mul(&r.Y, &z1cu)
335
336 h.Sub(&u2, &q.X)
337 rr.Sub(&s2, &q.Y)
338
339 if h.IsZero() {
340 if rr.IsZero() {
341 return p.Double(q)
342 }
343 p.SetInfinity()
344 return p
345 }
346
347 h2.Sqr(&h)
348 h3.Mul(&h2, &h)
349 u1h2.Mul(&q.X, &h2)
350
351 // X₃ = R² - H³ - 2*U₁*H²
352 var r2, u1h2_2 FieldElement
353 r2.Sqr(&rr)
354 u1h2_2.Double(&u1h2)
355 x3.Sub(&r2, &h3)
356 x3.Sub(&x3, &u1h2_2)
357
358 // Y₃ = R*(U₁*H² - X₃) - S₁*H³
359 var tmp, s1h3 FieldElement
360 tmp.Sub(&u1h2, &x3)
361 y3.Mul(&rr, &tmp)
362 s1h3.Mul(&q.Y, &h3)
363 y3.Sub(&y3, &s1h3)
364
365 // Z₃ = H*Z₁
366 z3.Mul(&q.Z, &h)
367
368 // Now copy to output (safe even if p == q)
369 p.X = x3
370 p.Y = y3
371 p.Z = z3
372 p.Infinity = false
373 return p
374 }
375
376 // Negate sets p = -q (reflection over x-axis).
377 func (p *JacobianPoint) Negate(q *JacobianPoint) *JacobianPoint {
378 if q.IsInfinity() {
379 p.SetInfinity()
380 return p
381 }
382 p.X = q.X
383 p.Y.Negate(&q.Y)
384 p.Z = q.Z
385 p.Infinity = false
386 return p
387 }
388
389 // ScalarMult computes p = k*q using double-and-add.
390 func (p *JacobianPoint) ScalarMult(q *JacobianPoint, k *Scalar) *JacobianPoint {
391 // Simple double-and-add (not constant-time)
392 // A proper implementation would use windowed NAF or similar
393
394 p.SetInfinity()
395
396 // Process bits from high to low
397 bytes := k.Bytes()
398 for i := 0; i < 32; i++ {
399 b := bytes[i]
400 for j := 7; j >= 0; j-- {
401 p.Double(p)
402 if (b>>j)&1 == 1 {
403 p.Add(p, q)
404 }
405 }
406 }
407
408 return p
409 }
410
411 // ScalarBaseMult computes p = k*G where G is the generator.
412 func (p *JacobianPoint) ScalarBaseMult(k *Scalar) *JacobianPoint {
413 var g JacobianPoint
414 g.FromAffine(&Generator)
415 return p.ScalarMult(&g, k)
416 }
417
418 // BasePointMult computes k*G and returns the result in affine coordinates.
419 func BasePointMult(k *Scalar) *AffinePoint {
420 var jac JacobianPoint
421 var aff AffinePoint
422 jac.ScalarBaseMult(k)
423 jac.ToAffine(&aff)
424 return &aff
425 }
426