field.mx raw
1 // Package secp256k1 implements secp256k1 curve operations and BIP-340 Schnorr signatures.
2 // Pure Go, no math/big, no stdlib crypto.
3 package secp256k1
4
5 // Field element: 256-bit integer mod p, stored as 4 x uint64 (little-endian limbs).
6 // p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
7
8 type Fe [4]uint64
9
10 var feZero = Fe{0, 0, 0, 0}
11
12 var feOne = Fe{1, 0, 0, 0}
13
14 // p = field prime
15 var feP = Fe{
16 0xFFFFFFFEFFFFFC2F,
17 0xFFFFFFFFFFFFFFFF,
18 0xFFFFFFFFFFFFFFFF,
19 0xFFFFFFFFFFFFFFFF,
20 }
21
22 // feAdd returns a + b mod p.
23 func feAdd(a, b Fe) Fe {
24 var r Fe
25 var carry uint64
26
27 r[0], carry = addWithCarry(a[0], b[0], 0)
28 r[1], carry = addWithCarry(a[1], b[1], carry)
29 r[2], carry = addWithCarry(a[2], b[2], carry)
30 r[3], carry = addWithCarry(a[3], b[3], carry)
31
32 // Reduce mod p if needed.
33 return feReduce(r, carry)
34 }
35
36 // feSub returns a - b mod p.
37 func feSub(a, b Fe) Fe {
38 var r Fe
39 var borrow uint64
40
41 r[0], borrow = subWithBorrow(a[0], b[0], 0)
42 r[1], borrow = subWithBorrow(a[1], b[1], borrow)
43 r[2], borrow = subWithBorrow(a[2], b[2], borrow)
44 r[3], borrow = subWithBorrow(a[3], b[3], borrow)
45
46 if borrow != 0 {
47 // Add p.
48 var c uint64
49 r[0], c = addWithCarry(r[0], feP[0], 0)
50 r[1], c = addWithCarry(r[1], feP[1], c)
51 r[2], c = addWithCarry(r[2], feP[2], c)
52 r[3], _ = addWithCarry(r[3], feP[3], c)
53 }
54 return r
55 }
56
57 // feNeg returns -a mod p.
58 func feNeg(a Fe) Fe {
59 if a == feZero {
60 return feZero
61 }
62 return feSub(feP, a)
63 }
64
65 // feMul returns a * b mod p using schoolbook multiplication + Barrett-like reduction.
66 func feMul(a, b Fe) Fe {
67 // Full 512-bit product in 8 limbs.
68 var t [8]uint64
69
70 // Schoolbook 4x4 multiply.
71 for i := 0; i < 4; i++ {
72 var carry uint64
73 for j := 0; j < 4; j++ {
74 hi, lo := mul64(a[i], b[j])
75 lo, c1 := addWithCarry(lo, t[i+j], 0)
76 hi += c1
77 lo, c2 := addWithCarry(lo, carry, 0)
78 hi += c2
79 t[i+j] = lo
80 carry = hi
81 }
82 t[i+4] = carry
83 }
84
85 return feReduceFull(t)
86 }
87
88 // feSqr returns a^2 mod p.
89 func feSqr(a Fe) Fe {
90 return feMul(a, a)
91 }
92
93 // feInv returns a^(-1) mod p using Fermat's little theorem: a^(p-2) mod p.
94 func feInv(a Fe) Fe {
95 // p-2 = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2D
96 // Use square-and-multiply with a compact addition chain.
97 // For simplicity, use binary method on p-2.
98 pm2 := Fe{
99 0xFFFFFFFEFFFFFC2D,
100 0xFFFFFFFFFFFFFFFF,
101 0xFFFFFFFFFFFFFFFF,
102 0xFFFFFFFFFFFFFFFF,
103 }
104 return feExp(a, pm2)
105 }
106
107 // feExp computes a^e mod p via square-and-multiply.
108 func feExp(base, exp Fe) Fe {
109 result := feOne
110 b := base
111 for i := 0; i < 4; i++ {
112 w := exp[i]
113 for bit := 0; bit < 64; bit++ {
114 if w&1 == 1 {
115 result = feMul(result, b)
116 }
117 b = feSqr(b)
118 w >>= 1
119 }
120 }
121 return result
122 }
123
124 // feSqrt computes sqrt(a) mod p. Returns (result, exists).
125 // p % 4 == 3, so sqrt(a) = a^((p+1)/4) mod p.
126 func feSqrt(a Fe) (Fe, bool) {
127 // (p+1)/4
128 exp := Fe{
129 0xFFFFFFFFBFFFFF0C,
130 0xFFFFFFFFFFFFFFFF,
131 0xFFFFFFFFFFFFFFFF,
132 0x3FFFFFFFFFFFFFFF,
133 }
134 r := feExp(a, exp)
135 // Verify: r^2 == a?
136 check := feSqr(r)
137 if check == a {
138 return r, true
139 }
140 return feZero, false
141 }
142
143 // feFromBytes reads a 32-byte big-endian integer into an Fe.
144 func feFromBytes(b []byte) Fe {
145 var r Fe
146 if len(b) < 32 {
147 return r
148 }
149 r[3] = beUint64(b[0:8])
150 r[2] = beUint64(b[8:16])
151 r[1] = beUint64(b[16:24])
152 r[0] = beUint64(b[24:32])
153 return r
154 }
155
156 // feToBytes writes an Fe as 32-byte big-endian.
157 func feToBytes(a Fe) [32]byte {
158 var b [32]byte
159 putBeUint64(b[0:8], a[3])
160 putBeUint64(b[8:16], a[2])
161 putBeUint64(b[16:24], a[1])
162 putBeUint64(b[24:32], a[0])
163 return b
164 }
165
166 // feIsZero returns true if a == 0.
167 func feIsZero(a Fe) bool {
168 return a == feZero
169 }
170
171 // feIsEven returns true if a is even.
172 func feIsEven(a Fe) bool {
173 return a[0]&1 == 0
174 }
175
176 // feCmp returns -1, 0, or 1 comparing a and b.
177 func feCmp(a, b Fe) int {
178 for i := 3; i >= 0; i-- {
179 if a[i] < b[i] {
180 return -1
181 }
182 if a[i] > b[i] {
183 return 1
184 }
185 }
186 return 0
187 }
188
189 // feReduce reduces r with carry into [0, p).
190 func feReduce(r Fe, carry uint64) Fe {
191 // If carry or r >= p, subtract p.
192 if carry != 0 || feCmp(r, feP) >= 0 {
193 var borrow uint64
194 r[0], borrow = subWithBorrow(r[0], feP[0], 0)
195 r[1], borrow = subWithBorrow(r[1], feP[1], borrow)
196 r[2], borrow = subWithBorrow(r[2], feP[2], borrow)
197 r[3], _ = subWithBorrow(r[3], feP[3], borrow)
198 }
199 return r
200 }
201
202 // feReduceFull reduces a 512-bit product modulo p.
203 // Uses the property: 2^256 ≡ 0x1000003D1 (mod p).
204 func feReduceFull(t [8]uint64) Fe {
205 // r = t[0..3] + t[4..7] * 2^256
206 // 2^256 mod p = 0x1000003D1
207 const c = 0x1000003D1
208
209 var r Fe
210 var carry uint64
211
212 // Multiply high part by c and add to low part.
213 for i := 0; i < 4; i++ {
214 hi, lo := mul64(t[i+4], c)
215 lo, c1 := addWithCarry(lo, t[i], 0)
216 hi += c1
217 lo, c2 := addWithCarry(lo, carry, 0)
218 hi += c2
219 r[i] = lo
220 carry = hi
221 }
222
223 // carry might still be non-zero; reduce again.
224 if carry != 0 {
225 hi, lo := mul64(carry, c)
226 _ = hi // at most ~38 bits, second reduction won't overflow
227 var c3 uint64
228 r[0], c3 = addWithCarry(r[0], lo, 0)
229 r[1], c3 = addWithCarry(r[1], hi, c3)
230 r[2], c3 = addWithCarry(r[2], 0, c3)
231 r[3], _ = addWithCarry(r[3], 0, c3)
232 }
233
234 // Final reduction: if r >= p, subtract p.
235 if feCmp(r, feP) >= 0 {
236 var borrow uint64
237 r[0], borrow = subWithBorrow(r[0], feP[0], 0)
238 r[1], borrow = subWithBorrow(r[1], feP[1], borrow)
239 r[2], borrow = subWithBorrow(r[2], feP[2], borrow)
240 r[3], _ = subWithBorrow(r[3], feP[3], borrow)
241 }
242
243 return r
244 }
245
246 // 64-bit arithmetic helpers.
247
248 func addWithCarry(a, b, carry uint64) (uint64, uint64) {
249 sum := a + b + carry
250 // Carry if sum < a or (sum == a and carry was 1) etc.
251 var c uint64
252 if sum < a || (sum == a && (b|carry) != 0) {
253 c = 1
254 }
255 return sum, c
256 }
257
258 func subWithBorrow(a, b, borrow uint64) (uint64, uint64) {
259 diff := a - b - borrow
260 var c uint64
261 if a < b+borrow || (borrow != 0 && b == 0xFFFFFFFFFFFFFFFF) {
262 c = 1
263 }
264 return diff, c
265 }
266
267 // mul64 returns the full 128-bit product of a * b as (hi, lo).
268 func mul64(a, b uint64) (uint64, uint64) {
269 // Split into 32-bit halves to avoid overflow.
270 aHi := a >> 32
271 aLo := a & 0xFFFFFFFF
272 bHi := b >> 32
273 bLo := b & 0xFFFFFFFF
274
275 ll := aLo * bLo
276 hl := aHi * bLo
277 lh := aLo * bHi
278 hh := aHi * bHi
279
280 mid := hl + (ll >> 32)
281 // Check for overflow in mid.
282 if mid < hl {
283 hh += 1 << 32
284 }
285 mid2 := mid + lh
286 if mid2 < mid {
287 hh += 1 << 32
288 }
289
290 lo := (mid2 << 32) | (ll & 0xFFFFFFFF)
291 hi := hh + (mid2 >> 32)
292
293 return hi, lo
294 }
295
296 func beUint64(b []byte) uint64 {
297 return uint64(b[0])<<56 | uint64(b[1])<<48 | uint64(b[2])<<40 | uint64(b[3])<<32 |
298 uint64(b[4])<<24 | uint64(b[5])<<16 | uint64(b[6])<<8 | uint64(b[7])
299 }
300
301 func putBeUint64(b []byte, v uint64) {
302 b[0] = byte(v >> 56)
303 b[1] = byte(v >> 48)
304 b[2] = byte(v >> 40)
305 b[3] = byte(v >> 32)
306 b[4] = byte(v >> 24)
307 b[5] = byte(v >> 16)
308 b[6] = byte(v >> 8)
309 b[7] = byte(v)
310 }
311