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