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 // Generator point G.
15 var G = AffinePoint{
16 X: Fe{
17 0x59F2815B16F81798,
18 0x029BFCDB2DCE28D9,
19 0x55A06295CE870B07,
20 0x79BE667EF9DCBBAC,
21 },
22 Y: Fe{
23 0x9C47D08FFB10D4B8,
24 0xFD17B448A6855419,
25 0x5DA4FBFC0E1108A8,
26 0x483ADA7726A3C465,
27 },
28 }
29
30 // Curve order n.
31 var curveN = Fe{
32 0xBFD25E8CD0364141,
33 0xBAAEDCE6AF48A03B,
34 0xFFFFFFFFFFFFFFFE,
35 0xFFFFFFFFFFFFFFFF,
36 }
37
38 // Infinity is the point at infinity.
39 var Infinity = Point{feZero, feOne, feZero}
40
41 // pointFromAffine converts an affine point to Jacobian.
42 func pointFromAffine(p AffinePoint) Point {
43 return Point{p.X, p.Y, feOne}
44 }
45
46 // toAffine converts a Jacobian point to affine.
47 func (p Point) toAffine() AffinePoint {
48 if feIsZero(p.Z) {
49 return AffinePoint{feZero, feZero}
50 }
51 zInv := feInv(p.Z)
52 z2 := feSqr(zInv)
53 z3 := feMul(z2, zInv)
54 return AffinePoint{
55 X: feMul(p.X, z2),
56 Y: feMul(p.Y, z3),
57 }
58 }
59
60 // isInfinity returns true if the point is at infinity.
61 func (p Point) isInfinity() bool {
62 return feIsZero(p.Z)
63 }
64
65 // pointDouble computes 2*P in Jacobian coordinates.
66 func pointDouble(p Point) Point {
67 if feIsZero(p.Z) {
68 return p
69 }
70
71 // http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l
72 a := feSqr(p.X)
73 b := feSqr(p.Y)
74 c := feSqr(b)
75
76 // d = 2*((X1+B)^2-A-C)
77 xb := feAdd(p.X, b)
78 xb2 := feSqr(xb)
79 d := feSub(feSub(xb2, a), c)
80 d = feAdd(d, d)
81
82 // e = 3*A
83 e := feAdd(feAdd(a, a), a)
84
85 f := feSqr(e)
86
87 // X3 = F - 2*D
88 x3 := feSub(f, feAdd(d, d))
89
90 // Y3 = E*(D-X3) - 8*C
91 y3 := feMul(e, feSub(d, x3))
92 c8 := feAdd(c, c)
93 c8 = feAdd(c8, c8)
94 c8 = feAdd(c8, c8)
95 y3 = feSub(y3, c8)
96
97 // Z3 = 2*Y1*Z1
98 z3 := feMul(p.Y, p.Z)
99 z3 = feAdd(z3, z3)
100
101 return Point{x3, y3, z3}
102 }
103
104 // pointAdd computes P + Q in Jacobian coordinates.
105 func pointAdd(p, q Point) Point {
106 if p.isInfinity() {
107 return q
108 }
109 if q.isInfinity() {
110 return p
111 }
112
113 // U1 = X1*Z2^2, U2 = X2*Z1^2
114 z1sq := feSqr(p.Z)
115 z2sq := feSqr(q.Z)
116 u1 := feMul(p.X, z2sq)
117 u2 := feMul(q.X, z1sq)
118
119 // S1 = Y1*Z2^3, S2 = Y2*Z1^3
120 s1 := feMul(p.Y, feMul(z2sq, q.Z))
121 s2 := feMul(q.Y, feMul(z1sq, p.Z))
122
123 if u1 == u2 {
124 if s1 == s2 {
125 return pointDouble(p)
126 }
127 return Infinity
128 }
129
130 // H = U2 - U1
131 h := feSub(u2, u1)
132 // R = S2 - S1
133 r := feSub(s2, s1)
134
135 h2 := feSqr(h)
136 h3 := feMul(h2, h)
137
138 // X3 = R^2 - H^3 - 2*U1*H^2
139 x3 := feSub(feSub(feSqr(r), h3), feAdd(feMul(u1, h2), feMul(u1, h2)))
140
141 // Y3 = R*(U1*H^2 - X3) - S1*H^3
142 y3 := feSub(feMul(r, feSub(feMul(u1, h2), x3)), feMul(s1, h3))
143
144 // Z3 = Z1*Z2*H
145 z3 := feMul(feMul(p.Z, q.Z), h)
146
147 return Point{x3, y3, z3}
148 }
149
150 // ScalarBaseMult computes k*G using double-and-add.
151 func ScalarBaseMult(k Fe) AffinePoint {
152 return ScalarMult(pointFromAffine(G), k).toAffine()
153 }
154
155 // ScalarMult computes k*P.
156 func ScalarMult(p Point, k Fe) Point {
157 result := Infinity
158 current := p
159
160 for i := 0; i < 4; i++ {
161 w := k[i]
162 for bit := 0; bit < 64; bit++ {
163 if w&1 == 1 {
164 result = pointAdd(result, current)
165 }
166 current = pointDouble(current)
167 w >>= 1
168 }
169 }
170 return result
171 }
172
173 // LiftX recovers a point from x-coordinate only (BIP-340).
174 // Returns the point with even y.
175 func LiftX(x Fe) (AffinePoint, bool) {
176 // y^2 = x^3 + 7
177 x3 := feMul(feSqr(x), x)
178 y2 := feAdd(x3, Fe{7, 0, 0, 0})
179 y, ok := feSqrt(y2)
180 if !ok {
181 return AffinePoint{}, false
182 }
183 // BIP-340: choose even y.
184 if !feIsEven(y) {
185 y = feNeg(y)
186 }
187 return AffinePoint{x, y}, true
188 }
189