point.mx raw
1 package secp256k1
2
3 // Point on secp256k1 in Jacobian coordinates (X, Y, Z).
4 // Affine point is (X/Z^2, Y/Z^3). Point at infinity has Z=0.
5 type Point struct {
6 X, Y, Z Fe
7 }
8
9 // Affine point.
10 type AffinePoint struct {
11 X, Y Fe
12 }
13
14 // G returns the generator point.
15 func G() AffinePoint {
16 return AffinePoint{
17 X: Fe{
18 0x59F2815B16F81798,
19 0x029BFCDB2DCE28D9,
20 0x55A06295CE870B07,
21 0x79BE667EF9DCBBAC,
22 },
23 Y: Fe{
24 0x9C47D08FFB10D4B8,
25 0xFD17B448A6855419,
26 0x5DA4FBFC0E1108A8,
27 0x483ADA7726A3C465,
28 },
29 }
30 }
31
32 // curveN returns the curve order n.
33 func curveN() Fe {
34 return Fe{
35 0xBFD25E8CD0364141,
36 0xBAAEDCE6AF48A03B,
37 0xFFFFFFFFFFFFFFFE,
38 0xFFFFFFFFFFFFFFFF,
39 }
40 }
41
42 // Infinity returns the point at infinity.
43 func Infinity() Point { return Point{_feZero(), _feOne(), _feZero()} }
44
45 // pointFromAffine converts an affine point to Jacobian.
46 func pointFromAffine(p AffinePoint) Point {
47 return Point{p.X, p.Y, _feOne()}
48 }
49
50 // toAffine converts a Jacobian point to affine.
51 func (p Point) toAffine() AffinePoint {
52 if feIsZero(p.Z) {
53 return AffinePoint{_feZero(), _feZero()}
54 }
55 zInv := feInv(p.Z)
56 z2 := feSqr(zInv)
57 z3 := feMul(z2, zInv)
58 return AffinePoint{
59 X: feMul(p.X, z2),
60 Y: feMul(p.Y, z3),
61 }
62 }
63
64 // isInfinity returns true if the point is at infinity.
65 func (p Point) isInfinity() bool {
66 return feIsZero(p.Z)
67 }
68
69 // pointDouble computes 2*P in Jacobian coordinates.
70 func pointDouble(p Point) Point {
71 if feIsZero(p.Z) {
72 return p
73 }
74
75 // http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l
76 a := feSqr(p.X)
77 b := feSqr(p.Y)
78 c := feSqr(b)
79
80 // d = 2*((X1+B)^2-A-C)
81 xb := feAdd(p.X, b)
82 xb2 := feSqr(xb)
83 d := feSub(feSub(xb2, a), c)
84 d = feAdd(d, d)
85
86 // e = 3*A
87 e := feAdd(feAdd(a, a), a)
88
89 f := feSqr(e)
90
91 // X3 = F - 2*D
92 x3 := feSub(f, feAdd(d, d))
93
94 // Y3 = E*(D-X3) - 8*C
95 y3 := feMul(e, feSub(d, x3))
96 c8 := feAdd(c, c)
97 c8 = feAdd(c8, c8)
98 c8 = feAdd(c8, c8)
99 y3 = feSub(y3, c8)
100
101 // Z3 = 2*Y1*Z1
102 z3 := feMul(p.Y, p.Z)
103 z3 = feAdd(z3, z3)
104
105 return Point{x3, y3, z3}
106 }
107
108 // pointAdd computes P + Q in Jacobian coordinates.
109 func pointAdd(p, q Point) Point {
110 if p.isInfinity() {
111 return q
112 }
113 if q.isInfinity() {
114 return p
115 }
116
117 // U1 = X1*Z2^2, U2 = X2*Z1^2
118 z1sq := feSqr(p.Z)
119 z2sq := feSqr(q.Z)
120 u1 := feMul(p.X, z2sq)
121 u2 := feMul(q.X, z1sq)
122
123 // S1 = Y1*Z2^3, S2 = Y2*Z1^3
124 s1 := feMul(p.Y, feMul(z2sq, q.Z))
125 s2 := feMul(q.Y, feMul(z1sq, p.Z))
126
127 if u1 == u2 {
128 if s1 == s2 {
129 return pointDouble(p)
130 }
131 return Infinity()
132 }
133
134 // H = U2 - U1
135 h := feSub(u2, u1)
136 // R = S2 - S1
137 r := feSub(s2, s1)
138
139 h2 := feSqr(h)
140 h3 := feMul(h2, h)
141
142 // X3 = R^2 - H^3 - 2*U1*H^2
143 x3 := feSub(feSub(feSqr(r), h3), feAdd(feMul(u1, h2), feMul(u1, h2)))
144
145 // Y3 = R*(U1*H^2 - X3) - S1*H^3
146 y3 := feSub(feMul(r, feSub(feMul(u1, h2), x3)), feMul(s1, h3))
147
148 // Z3 = Z1*Z2*H
149 z3 := feMul(feMul(p.Z, q.Z), h)
150
151 return Point{x3, y3, z3}
152 }
153
154 // varTimeScalarMult computes k*P using variable-time double-and-add.
155 // Safe only for public inputs (e.g. verification). Do NOT use with secret scalars.
156 func varTimeScalarMult(p Point, k Fe) Point {
157 result := Infinity()
158 current := p
159 for i := 0; i < 4; i++ {
160 w := k[i]
161 for bit := 0; bit < 64; bit++ {
162 if w&1 == 1 {
163 result = pointAdd(result, current)
164 }
165 current = pointDouble(current)
166 w >>= 1
167 }
168 }
169 return result
170 }
171
172 // constantTimeByteEq returns 1 if a == b, 0 otherwise. Constant-time.
173 func constantTimeByteEq(a, b uint8) int {
174 x := uint32(a ^ b)
175 x |= x >> 4
176 x |= x >> 2
177 x |= x >> 1
178 return int(1 ^ (x & 1))
179 }
180
181 // pointCondSelect returns b if cond==1, a if cond==0. Constant-time.
182 func pointCondSelect(a, b Point, cond int) Point {
183 return Point{
184 feCondSelect(a.X, b.X, cond),
185 feCondSelect(a.Y, b.Y, cond),
186 feCondSelect(a.Z, b.Z, cond),
187 }
188 }
189
190 // pointCondNeg returns Point{X, -Y, Z} if cond==1, p unchanged if cond==0. Constant-time.
191 func pointCondNeg(p Point, cond int) Point {
192 return Point{p.X, feCondNeg(p.Y, cond), p.Z}
193 }
194
195 // projLookupTable holds [1*Q, 2*Q, ..., 8*Q] for constant-time selection.
196 type projLookupTable struct {
197 points [8]Point
198 }
199
200 func (t *projLookupTable) fromPoint(q Point) {
201 t.points[0] = q
202 for i := 0; i < 7; i++ {
203 t.points[i+1] = pointAdd(q, t.points[i])
204 }
205 }
206
207 // selectInto sets dest = x*Q for -8 <= x <= 8 in constant time.
208 // x == 0 yields the identity (Infinity).
209 func (t *projLookupTable) selectInto(dest *Point, x int8) {
210 xmask := int(x >> 7) // 0 if x >= 0, -1 if x < 0
211 xabs := uint8((x + int8(xmask)) ^ int8(xmask)) // |x|
212 *dest = Infinity()
213 for j := uint8(1); j <= 8; j++ {
214 cond := constantTimeByteEq(xabs, j)
215 *dest = pointCondSelect(*dest, t.points[j-1], cond)
216 }
217 *dest = pointCondNeg(*dest, xmask&1)
218 }
219
220 // pointAddCT adds p and q in constant time, handling identity (Z==0) via
221 // conditional select. Does NOT handle p == q (use pointDouble for that case).
222 func pointAddCT(p, q Point) Point {
223 pIsInf := ctIsZeroFe(p.Z)
224 qIsInf := ctIsZeroFe(q.Z)
225
226 z1sq := feSqr(p.Z)
227 z2sq := feSqr(q.Z)
228 u1 := feMul(p.X, z2sq)
229 u2 := feMul(q.X, z1sq)
230 s1 := feMul(p.Y, feMul(z2sq, q.Z))
231 s2 := feMul(q.Y, feMul(z1sq, p.Z))
232 h := feSub(u2, u1)
233 r := feSub(s2, s1)
234 h2 := feSqr(h)
235 h3 := feMul(h2, h)
236 x3 := feSub(feSub(feSqr(r), h3), feAdd(feMul(u1, h2), feMul(u1, h2)))
237 y3 := feSub(feMul(r, feSub(feMul(u1, h2), x3)), feMul(s1, h3))
238 z3 := feMul(feMul(p.Z, q.Z), h)
239 result := Point{x3, y3, z3}
240
241 // Identity propagation: if either input is infinity, use the other.
242 result = pointCondSelect(result, q, pIsInf)
243 result = pointCondSelect(result, p, qIsInf)
244 return result
245 }
246
247 // pointDoubleCT doubles p in constant time, handling identity (Z==0) via
248 // conditional select.
249 func pointDoubleCT(p Point) Point {
250 isInf := ctIsZeroFe(p.Z)
251
252 a := feSqr(p.X)
253 b := feSqr(p.Y)
254 c := feSqr(b)
255 xb := feAdd(p.X, b)
256 xb2 := feSqr(xb)
257 d := feSub(feSub(xb2, a), c)
258 d = feAdd(d, d)
259 e := feAdd(feAdd(a, a), a)
260 f := feSqr(e)
261 x3 := feSub(f, feAdd(d, d))
262 y3 := feMul(e, feSub(d, x3))
263 c8 := feAdd(c, c)
264 c8 = feAdd(c8, c8)
265 c8 = feAdd(c8, c8)
266 y3 = feSub(y3, c8)
267 z3 := feMul(p.Y, p.Z)
268 z3 = feAdd(z3, z3)
269
270 result := Point{x3, y3, z3}
271 result = pointCondSelect(result, p, isInf)
272 return result
273 }
274
275 // ScalarMult computes k*P in constant time using signed radix-16.
276 func ScalarMult(p Point, k Fe) Point {
277 var table projLookupTable
278 table.fromPoint(p)
279
280 digits := scalarToSignedRadix16(k)
281
282 var result Point
283 table.selectInto(&result, digits[64])
284
285 for i := 63; i >= 0; i-- {
286 result = pointDoubleCT(result)
287 result = pointDoubleCT(result)
288 result = pointDoubleCT(result)
289 result = pointDoubleCT(result)
290
291 var multiple Point
292 table.selectInto(&multiple, digits[i])
293 result = pointAddCT(result, multiple)
294 }
295 return result
296 }
297
298 // ScalarBaseMult computes k*G in constant time.
299 func ScalarBaseMult(k Fe) AffinePoint {
300 return ScalarMult(pointFromAffine(G()), k).toAffine()
301 }
302
303 // LiftX recovers a point from x-coordinate only (BIP-340).
304 // Returns the point with even y.
305 func LiftX(x Fe) (AffinePoint, bool) {
306 // y^2 = x^3 + 7
307 x3 := feMul(feSqr(x), x)
308 y2 := feAdd(x3, Fe{7, 0, 0, 0})
309 y, ok := feSqrt(y2)
310 if !ok {
311 return AffinePoint{}, false
312 }
313 // BIP-340: choose even y.
314 if !feIsEven(y) {
315 y = feNeg(y)
316 }
317 return AffinePoint{x, y}, true
318 }
319