field_32bit.go raw
1 //go:build js || wasm || tinygo || wasm32
2
3 // Copyright (c) 2024 mleku
4 // Adapted from github.com/decred/dcrd/dcrec/secp256k1/v4
5 // Copyright (c) 2013-2024 The btcsuite developers
6 // Copyright (c) 2015-2024 The Decred developers
7
8 package p256k1
9
10 import (
11 "crypto/subtle"
12 "errors"
13 "unsafe"
14 )
15
16 // FieldElement represents a field element modulo the secp256k1 field prime.
17 // This implementation uses 10 uint32 limbs in base 2^26, optimized for 32-bit platforms.
18 //
19 // The representation provides 6 bits of overflow in each word (10 bits in the MSB)
20 // for a total of 64 bits of overflow, allowing intermediate calculations without
21 // immediate carry propagation.
22 type FieldElement struct {
23 // n represents the sum(i=0..9, n[i] << (i*26)) mod p
24 // where p is the field modulus, 2^256 - 2^32 - 977
25 n [10]uint32
26
27 magnitude int // magnitude of the field element (max 32)
28 normalized bool // whether the field element is normalized
29 }
30
31 // FieldElementStorage represents a field element in storage format (4 uint64 limbs)
32 type FieldElementStorage struct {
33 n [4]uint64
34 }
35
36 // Field constants for 10x26 representation
37 const (
38 // Bit masks
39 twoBitsMask = 0x3
40 fourBitsMask = 0xf
41 sixBitsMask = 0x3f
42 eightBitsMask = 0xff
43
44 // fieldBase is the exponent used to form the numeric base of each word.
45 fieldBase32 = 26
46
47 // fieldBaseMask is the mask for the bits in each word (except MSB)
48 fieldBaseMask32 = (1 << fieldBase32) - 1
49
50 // fieldMSBBits is the number of bits in the most significant word
51 fieldMSBBits32 = 256 - (fieldBase32 * 9) // 256 - 234 = 22
52
53 // fieldMSBMask is the mask for the bits in the MSB
54 fieldMSBMask32 = (1 << fieldMSBBits32) - 1 // 0x3fffff
55
56 // Prime field words in 10x26 representation
57 fieldPrimeWord0 = 0x03fffc2f
58 fieldPrimeWord1 = 0x03ffffbf
59 fieldPrimeWord2 = 0x03ffffff
60 fieldPrimeWord3 = 0x03ffffff
61 fieldPrimeWord4 = 0x03ffffff
62 fieldPrimeWord5 = 0x03ffffff
63 fieldPrimeWord6 = 0x03ffffff
64 fieldPrimeWord7 = 0x03ffffff
65 fieldPrimeWord8 = 0x03ffffff
66 fieldPrimeWord9 = 0x003fffff
67 )
68
69 // Field element constants
70 var (
71 // FieldElementOne represents the field element 1
72 FieldElementOne = FieldElement{
73 n: [10]uint32{1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
74 magnitude: 1,
75 normalized: true,
76 }
77
78 // FieldElementZero represents the field element 0
79 FieldElementZero = FieldElement{
80 n: [10]uint32{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
81 magnitude: 0,
82 normalized: true,
83 }
84
85 // fieldBeta is the GLV endomorphism constant β (cube root of unity mod p)
86 // Value: 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee
87 fieldBeta = FieldElement{
88 n: [10]uint32{
89 0x0019501ee, // n[0]
90 0x004e5662c, // n[1]
91 0x022d7e625, // n[2]
92 0x00f51d3c0, // n[3]
93 0x0334cd1a, // n[4]
94 0x007b23d12, // n[5]
95 0x0311c923, // n[6]
96 0x02c1957b9, // n[7]
97 0x0109ab65a, // n[8]
98 0x001eb94c, // n[9]
99 },
100 magnitude: 1,
101 normalized: true,
102 }
103 )
104
105 func NewFieldElement() *FieldElement {
106 return &FieldElement{
107 n: [10]uint32{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
108 magnitude: 0,
109 normalized: true,
110 }
111 }
112
113 // setB32 sets a field element from a 32-byte big-endian array
114 func (f *FieldElement) setB32(b []byte) error {
115 if len(b) != 32 {
116 return errors.New("field element byte array must be 32 bytes")
117 }
118
119 // Pack the 256 total bits across the 10 uint32 words with max 26 bits per word
120 f.n[0] = uint32(b[31]) | uint32(b[30])<<8 | uint32(b[29])<<16 |
121 (uint32(b[28])&twoBitsMask)<<24
122 f.n[1] = uint32(b[28])>>2 | uint32(b[27])<<6 | uint32(b[26])<<14 |
123 (uint32(b[25])&fourBitsMask)<<22
124 f.n[2] = uint32(b[25])>>4 | uint32(b[24])<<4 | uint32(b[23])<<12 |
125 (uint32(b[22])&sixBitsMask)<<20
126 f.n[3] = uint32(b[22])>>6 | uint32(b[21])<<2 | uint32(b[20])<<10 |
127 uint32(b[19])<<18
128 f.n[4] = uint32(b[18]) | uint32(b[17])<<8 | uint32(b[16])<<16 |
129 (uint32(b[15])&twoBitsMask)<<24
130 f.n[5] = uint32(b[15])>>2 | uint32(b[14])<<6 | uint32(b[13])<<14 |
131 (uint32(b[12])&fourBitsMask)<<22
132 f.n[6] = uint32(b[12])>>4 | uint32(b[11])<<4 | uint32(b[10])<<12 |
133 (uint32(b[9])&sixBitsMask)<<20
134 f.n[7] = uint32(b[9])>>6 | uint32(b[8])<<2 | uint32(b[7])<<10 |
135 uint32(b[6])<<18
136 f.n[8] = uint32(b[5]) | uint32(b[4])<<8 | uint32(b[3])<<16 |
137 (uint32(b[2])&twoBitsMask)<<24
138 f.n[9] = uint32(b[2])>>2 | uint32(b[1])<<6 | uint32(b[0])<<14
139
140 f.magnitude = 1
141 f.normalized = false
142
143 return nil
144 }
145
146 // getB32 converts a field element to a 32-byte big-endian array
147 func (f *FieldElement) getB32(b []byte) {
148 if len(b) != 32 {
149 panic("field element byte array must be 32 bytes")
150 }
151
152 // Normalize first
153 var normalized FieldElement
154 normalized = *f
155 normalized.normalize()
156
157 // Unpack the 256 total bits from the 10 uint32 words
158 b[31] = byte(normalized.n[0] & eightBitsMask)
159 b[30] = byte((normalized.n[0] >> 8) & eightBitsMask)
160 b[29] = byte((normalized.n[0] >> 16) & eightBitsMask)
161 b[28] = byte((normalized.n[0]>>24)&twoBitsMask | (normalized.n[1]&sixBitsMask)<<2)
162 b[27] = byte((normalized.n[1] >> 6) & eightBitsMask)
163 b[26] = byte((normalized.n[1] >> 14) & eightBitsMask)
164 b[25] = byte((normalized.n[1]>>22)&fourBitsMask | (normalized.n[2]&fourBitsMask)<<4)
165 b[24] = byte((normalized.n[2] >> 4) & eightBitsMask)
166 b[23] = byte((normalized.n[2] >> 12) & eightBitsMask)
167 b[22] = byte((normalized.n[2]>>20)&sixBitsMask | (normalized.n[3]&twoBitsMask)<<6)
168 b[21] = byte((normalized.n[3] >> 2) & eightBitsMask)
169 b[20] = byte((normalized.n[3] >> 10) & eightBitsMask)
170 b[19] = byte((normalized.n[3] >> 18) & eightBitsMask)
171 b[18] = byte(normalized.n[4] & eightBitsMask)
172 b[17] = byte((normalized.n[4] >> 8) & eightBitsMask)
173 b[16] = byte((normalized.n[4] >> 16) & eightBitsMask)
174 b[15] = byte((normalized.n[4]>>24)&twoBitsMask | (normalized.n[5]&sixBitsMask)<<2)
175 b[14] = byte((normalized.n[5] >> 6) & eightBitsMask)
176 b[13] = byte((normalized.n[5] >> 14) & eightBitsMask)
177 b[12] = byte((normalized.n[5]>>22)&fourBitsMask | (normalized.n[6]&fourBitsMask)<<4)
178 b[11] = byte((normalized.n[6] >> 4) & eightBitsMask)
179 b[10] = byte((normalized.n[6] >> 12) & eightBitsMask)
180 b[9] = byte((normalized.n[6]>>20)&sixBitsMask | (normalized.n[7]&twoBitsMask)<<6)
181 b[8] = byte((normalized.n[7] >> 2) & eightBitsMask)
182 b[7] = byte((normalized.n[7] >> 10) & eightBitsMask)
183 b[6] = byte((normalized.n[7] >> 18) & eightBitsMask)
184 b[5] = byte(normalized.n[8] & eightBitsMask)
185 b[4] = byte((normalized.n[8] >> 8) & eightBitsMask)
186 b[3] = byte((normalized.n[8] >> 16) & eightBitsMask)
187 b[2] = byte((normalized.n[8]>>24)&twoBitsMask | (normalized.n[9]&sixBitsMask)<<2)
188 b[1] = byte((normalized.n[9] >> 6) & eightBitsMask)
189 b[0] = byte((normalized.n[9] >> 14) & eightBitsMask)
190 }
191
192 // normalize normalizes a field element to its canonical representation
193 func (f *FieldElement) normalize() {
194 // Reduce modulo the prime using the special form p = 2^256 - 2^32 - 977
195 // = 2^256 - 4294968273
196 // 4294968273 in 10x26 representation: n[0]=977, n[1]=64
197 t9 := f.n[9]
198 m := t9 >> fieldMSBBits32
199 t9 &= fieldMSBMask32
200 t0 := f.n[0] + m*977
201 t1 := (t0 >> fieldBase32) + f.n[1] + (m << 6)
202 t0 &= fieldBaseMask32
203 t2 := (t1 >> fieldBase32) + f.n[2]
204 t1 &= fieldBaseMask32
205 t3 := (t2 >> fieldBase32) + f.n[3]
206 t2 &= fieldBaseMask32
207 t4 := (t3 >> fieldBase32) + f.n[4]
208 t3 &= fieldBaseMask32
209 t5 := (t4 >> fieldBase32) + f.n[5]
210 t4 &= fieldBaseMask32
211 t6 := (t5 >> fieldBase32) + f.n[6]
212 t5 &= fieldBaseMask32
213 t7 := (t6 >> fieldBase32) + f.n[7]
214 t6 &= fieldBaseMask32
215 t8 := (t7 >> fieldBase32) + f.n[8]
216 t7 &= fieldBaseMask32
217 t9 = (t8 >> fieldBase32) + t9
218 t8 &= fieldBaseMask32
219
220 // Final reduction if needed (constant-time)
221 // Check if value >= p
222 m = constantTimeEq32(t9, fieldMSBMask32)
223 m &= constantTimeEq32(t8&t7&t6&t5&t4&t3&t2, fieldBaseMask32)
224 m &= constantTimeGreater32(t1+64+((t0+977)>>fieldBase32), fieldBaseMask32)
225 m |= t9 >> fieldMSBBits32
226
227 t0 += m * 977
228 t1 = (t0 >> fieldBase32) + t1 + (m << 6)
229 t0 &= fieldBaseMask32
230 t2 = (t1 >> fieldBase32) + t2
231 t1 &= fieldBaseMask32
232 t3 = (t2 >> fieldBase32) + t3
233 t2 &= fieldBaseMask32
234 t4 = (t3 >> fieldBase32) + t4
235 t3 &= fieldBaseMask32
236 t5 = (t4 >> fieldBase32) + t5
237 t4 &= fieldBaseMask32
238 t6 = (t5 >> fieldBase32) + t6
239 t5 &= fieldBaseMask32
240 t7 = (t6 >> fieldBase32) + t7
241 t6 &= fieldBaseMask32
242 t8 = (t7 >> fieldBase32) + t8
243 t7 &= fieldBaseMask32
244 t9 = (t8 >> fieldBase32) + t9
245 t8 &= fieldBaseMask32
246 t9 &= fieldMSBMask32
247
248 f.n[0] = t0
249 f.n[1] = t1
250 f.n[2] = t2
251 f.n[3] = t3
252 f.n[4] = t4
253 f.n[5] = t5
254 f.n[6] = t6
255 f.n[7] = t7
256 f.n[8] = t8
257 f.n[9] = t9
258 f.magnitude = 1
259 f.normalized = true
260 }
261
262 // normalizeWeak gives a field element magnitude 1 without full normalization
263 func (f *FieldElement) normalizeWeak() {
264 t9 := f.n[9]
265 m := t9 >> fieldMSBBits32
266 t9 &= fieldMSBMask32
267 t0 := f.n[0] + m*977
268 t1 := (t0 >> fieldBase32) + f.n[1] + (m << 6)
269 t0 &= fieldBaseMask32
270 t2 := (t1 >> fieldBase32) + f.n[2]
271 t1 &= fieldBaseMask32
272 t3 := (t2 >> fieldBase32) + f.n[3]
273 t2 &= fieldBaseMask32
274 t4 := (t3 >> fieldBase32) + f.n[4]
275 t3 &= fieldBaseMask32
276 t5 := (t4 >> fieldBase32) + f.n[5]
277 t4 &= fieldBaseMask32
278 t6 := (t5 >> fieldBase32) + f.n[6]
279 t5 &= fieldBaseMask32
280 t7 := (t6 >> fieldBase32) + f.n[7]
281 t6 &= fieldBaseMask32
282 t8 := (t7 >> fieldBase32) + f.n[8]
283 t7 &= fieldBaseMask32
284 t9 = (t8 >> fieldBase32) + t9
285 t8 &= fieldBaseMask32
286
287 f.n[0] = t0
288 f.n[1] = t1
289 f.n[2] = t2
290 f.n[3] = t3
291 f.n[4] = t4
292 f.n[5] = t5
293 f.n[6] = t6
294 f.n[7] = t7
295 f.n[8] = t8
296 f.n[9] = t9
297 f.magnitude = 1
298 }
299
300 func (f *FieldElement) reduce() {
301 f.normalize()
302 }
303
304 // isZero returns true if the field element represents zero
305 func (f *FieldElement) isZero() bool {
306 if !f.normalized {
307 panic("field element must be normalized")
308 }
309 bits := f.n[0] | f.n[1] | f.n[2] | f.n[3] | f.n[4] |
310 f.n[5] | f.n[6] | f.n[7] | f.n[8] | f.n[9]
311 return bits == 0
312 }
313
314 // isOdd returns true if the field element is odd
315 func (f *FieldElement) isOdd() bool {
316 if !f.normalized {
317 panic("field element must be normalized")
318 }
319 return f.n[0]&1 == 1
320 }
321
322 // normalizesToZeroVar checks if the field element normalizes to zero
323 func (f *FieldElement) normalizesToZeroVar() bool {
324 var t FieldElement
325 t = *f
326 t.normalize()
327 return t.isZero()
328 }
329
330 // equal returns true if two field elements are equal
331 func (f *FieldElement) equal(a *FieldElement) bool {
332 if !f.normalized || !a.normalized {
333 panic("field elements must be normalized for comparison")
334 }
335 return subtle.ConstantTimeCompare(
336 (*[40]byte)(unsafe.Pointer(&f.n[0]))[:40],
337 (*[40]byte)(unsafe.Pointer(&a.n[0]))[:40],
338 ) == 1
339 }
340
341 // setInt sets a field element to a small integer value
342 func (f *FieldElement) setInt(a int) {
343 if a < 0 || a > 0x7FFF {
344 panic("value out of range")
345 }
346 f.n[0] = uint32(a)
347 for i := 1; i < 10; i++ {
348 f.n[i] = 0
349 }
350 if a == 0 {
351 f.magnitude = 0
352 } else {
353 f.magnitude = 1
354 }
355 f.normalized = true
356 }
357
358 // clear clears a field element
359 func (f *FieldElement) clear() {
360 for i := 0; i < 10; i++ {
361 f.n[i] = 0
362 }
363 f.magnitude = 0
364 f.normalized = true
365 }
366
367 // negate negates a field element: r = -a
368 func (f *FieldElement) negate(a *FieldElement, m int) {
369 if m < 0 || m > 31 {
370 panic("magnitude out of range")
371 }
372 f.n[0] = (uint32(m)+1)*fieldPrimeWord0 - a.n[0]
373 f.n[1] = (uint32(m)+1)*fieldPrimeWord1 - a.n[1]
374 f.n[2] = (uint32(m)+1)*fieldPrimeWord2 - a.n[2]
375 f.n[3] = (uint32(m)+1)*fieldPrimeWord3 - a.n[3]
376 f.n[4] = (uint32(m)+1)*fieldPrimeWord4 - a.n[4]
377 f.n[5] = (uint32(m)+1)*fieldPrimeWord5 - a.n[5]
378 f.n[6] = (uint32(m)+1)*fieldPrimeWord6 - a.n[6]
379 f.n[7] = (uint32(m)+1)*fieldPrimeWord7 - a.n[7]
380 f.n[8] = (uint32(m)+1)*fieldPrimeWord8 - a.n[8]
381 f.n[9] = (uint32(m)+1)*fieldPrimeWord9 - a.n[9]
382 f.magnitude = m + 1
383 f.normalized = false
384 }
385
386 // add adds two field elements: r += a
387 func (f *FieldElement) add(a *FieldElement) {
388 f.n[0] += a.n[0]
389 f.n[1] += a.n[1]
390 f.n[2] += a.n[2]
391 f.n[3] += a.n[3]
392 f.n[4] += a.n[4]
393 f.n[5] += a.n[5]
394 f.n[6] += a.n[6]
395 f.n[7] += a.n[7]
396 f.n[8] += a.n[8]
397 f.n[9] += a.n[9]
398 f.magnitude += a.magnitude
399 f.normalized = false
400 }
401
402 // sub subtracts a field element: r -= a
403 func (f *FieldElement) sub(a *FieldElement) {
404 var negA FieldElement
405 negA.negate(a, a.magnitude)
406 f.add(&negA)
407 }
408
409 // mulInt multiplies a field element by a small integer
410 func (f *FieldElement) mulInt(a int) {
411 if a < 0 || a > 32 {
412 panic("multiplier out of range")
413 }
414 ua := uint32(a)
415 f.n[0] *= ua
416 f.n[1] *= ua
417 f.n[2] *= ua
418 f.n[3] *= ua
419 f.n[4] *= ua
420 f.n[5] *= ua
421 f.n[6] *= ua
422 f.n[7] *= ua
423 f.n[8] *= ua
424 f.n[9] *= ua
425 f.magnitude *= a
426 f.normalized = false
427 }
428
429 // cmov conditionally moves a field element
430 func (f *FieldElement) cmov(a *FieldElement, flag int) {
431 mask := uint32(-(int32(flag) & 1))
432 for i := 0; i < 10; i++ {
433 f.n[i] ^= mask & (f.n[i] ^ a.n[i])
434 }
435 if flag != 0 {
436 f.magnitude = a.magnitude
437 f.normalized = a.normalized
438 }
439 }
440
441 // toStorage converts a field element to storage format
442 func (f *FieldElement) toStorage(s *FieldElementStorage) {
443 var normalized FieldElement
444 normalized = *f
445 normalized.normalize()
446
447 // Convert from 10x26 to 4x64
448 s.n[0] = uint64(normalized.n[0]) |
449 uint64(normalized.n[1])<<26 |
450 uint64(normalized.n[2])<<52
451 s.n[1] = uint64(normalized.n[2])>>12 |
452 uint64(normalized.n[3])<<14 |
453 uint64(normalized.n[4])<<40
454 s.n[2] = uint64(normalized.n[4])>>24 |
455 uint64(normalized.n[5])<<2 |
456 uint64(normalized.n[6])<<28 |
457 uint64(normalized.n[7])<<54
458 s.n[3] = uint64(normalized.n[7])>>10 |
459 uint64(normalized.n[8])<<16 |
460 uint64(normalized.n[9])<<42
461 }
462
463 // fromStorage converts from storage format to field element
464 func (f *FieldElement) fromStorage(s *FieldElementStorage) {
465 // Convert from 4x64 to 10x26
466 f.n[0] = uint32(s.n[0]) & fieldBaseMask32
467 f.n[1] = uint32(s.n[0]>>26) & fieldBaseMask32
468 f.n[2] = uint32(s.n[0]>>52) | (uint32(s.n[1]<<12) & fieldBaseMask32)
469 f.n[3] = uint32(s.n[1]>>14) & fieldBaseMask32
470 f.n[4] = uint32(s.n[1]>>40) | (uint32(s.n[2]<<24) & fieldBaseMask32)
471 f.n[5] = uint32(s.n[2]>>2) & fieldBaseMask32
472 f.n[6] = uint32(s.n[2]>>28) & fieldBaseMask32
473 f.n[7] = uint32(s.n[2]>>54) | (uint32(s.n[3]<<10) & fieldBaseMask32)
474 f.n[8] = uint32(s.n[3]>>16) & fieldBaseMask32
475 f.n[9] = uint32(s.n[3] >> 42)
476 f.magnitude = 1
477 f.normalized = false
478 }
479
480 // half computes r = a/2 mod p
481 func (f *FieldElement) half(a *FieldElement) {
482 // If a is odd, add p first (so result is even and can be divided by 2)
483 // p = 2^256 - 2^32 - 977
484 var t [10]uint32
485 copy(t[:], a.n[:])
486
487 // Check if odd (least significant bit)
488 isOdd := t[0] & 1
489
490 // Add p if odd: p in 10x26 representation
491 if isOdd == 1 {
492 var c uint64
493 c = uint64(t[0]) + uint64(fieldPrimeWord0)
494 t[0] = uint32(c & fieldBaseMask32)
495 c = (c >> 26) + uint64(t[1]) + uint64(fieldPrimeWord1)
496 t[1] = uint32(c & fieldBaseMask32)
497 c = (c >> 26) + uint64(t[2]) + uint64(fieldPrimeWord2)
498 t[2] = uint32(c & fieldBaseMask32)
499 c = (c >> 26) + uint64(t[3]) + uint64(fieldPrimeWord3)
500 t[3] = uint32(c & fieldBaseMask32)
501 c = (c >> 26) + uint64(t[4]) + uint64(fieldPrimeWord4)
502 t[4] = uint32(c & fieldBaseMask32)
503 c = (c >> 26) + uint64(t[5]) + uint64(fieldPrimeWord5)
504 t[5] = uint32(c & fieldBaseMask32)
505 c = (c >> 26) + uint64(t[6]) + uint64(fieldPrimeWord6)
506 t[6] = uint32(c & fieldBaseMask32)
507 c = (c >> 26) + uint64(t[7]) + uint64(fieldPrimeWord7)
508 t[7] = uint32(c & fieldBaseMask32)
509 c = (c >> 26) + uint64(t[8]) + uint64(fieldPrimeWord8)
510 t[8] = uint32(c & fieldBaseMask32)
511 c = (c >> 26) + uint64(t[9]) + uint64(fieldPrimeWord9)
512 t[9] = uint32(c & fieldMSBMask32)
513 }
514
515 // Divide by 2 (right shift by 1)
516 f.n[0] = (t[0] >> 1) | ((t[1] & 1) << 25)
517 f.n[1] = (t[1] >> 1) | ((t[2] & 1) << 25)
518 f.n[2] = (t[2] >> 1) | ((t[3] & 1) << 25)
519 f.n[3] = (t[3] >> 1) | ((t[4] & 1) << 25)
520 f.n[4] = (t[4] >> 1) | ((t[5] & 1) << 25)
521 f.n[5] = (t[5] >> 1) | ((t[6] & 1) << 25)
522 f.n[6] = (t[6] >> 1) | ((t[7] & 1) << 25)
523 f.n[7] = (t[7] >> 1) | ((t[8] & 1) << 25)
524 f.n[8] = (t[8] >> 1) | ((t[9] & 1) << 25)
525 f.n[9] = t[9] >> 1
526
527 f.magnitude = (a.magnitude + 1) / 2
528 f.normalized = false
529 }
530
531 // mul multiplies two field elements: r = a * b
532 func (f *FieldElement) mul(a, b *FieldElement) {
533 // Using 32-bit multiplication with 64-bit intermediate results
534 // This is optimized for platforms without native 64-bit multiplication
535 var c, d uint64
536
537 // Compute all 100 cross products
538 c = uint64(a.n[0]) * uint64(b.n[0])
539 d0 := uint32(c & 0x3FFFFFF)
540 c >>= 26
541
542 c += uint64(a.n[0])*uint64(b.n[1]) + uint64(a.n[1])*uint64(b.n[0])
543 d1 := uint32(c & 0x3FFFFFF)
544 c >>= 26
545
546 c += uint64(a.n[0])*uint64(b.n[2]) + uint64(a.n[1])*uint64(b.n[1]) +
547 uint64(a.n[2])*uint64(b.n[0])
548 d2 := uint32(c & 0x3FFFFFF)
549 c >>= 26
550
551 c += uint64(a.n[0])*uint64(b.n[3]) + uint64(a.n[1])*uint64(b.n[2]) +
552 uint64(a.n[2])*uint64(b.n[1]) + uint64(a.n[3])*uint64(b.n[0])
553 d3 := uint32(c & 0x3FFFFFF)
554 c >>= 26
555
556 c += uint64(a.n[0])*uint64(b.n[4]) + uint64(a.n[1])*uint64(b.n[3]) +
557 uint64(a.n[2])*uint64(b.n[2]) + uint64(a.n[3])*uint64(b.n[1]) +
558 uint64(a.n[4])*uint64(b.n[0])
559 d4 := uint32(c & 0x3FFFFFF)
560 c >>= 26
561
562 c += uint64(a.n[0])*uint64(b.n[5]) + uint64(a.n[1])*uint64(b.n[4]) +
563 uint64(a.n[2])*uint64(b.n[3]) + uint64(a.n[3])*uint64(b.n[2]) +
564 uint64(a.n[4])*uint64(b.n[1]) + uint64(a.n[5])*uint64(b.n[0])
565 d5 := uint32(c & 0x3FFFFFF)
566 c >>= 26
567
568 c += uint64(a.n[0])*uint64(b.n[6]) + uint64(a.n[1])*uint64(b.n[5]) +
569 uint64(a.n[2])*uint64(b.n[4]) + uint64(a.n[3])*uint64(b.n[3]) +
570 uint64(a.n[4])*uint64(b.n[2]) + uint64(a.n[5])*uint64(b.n[1]) +
571 uint64(a.n[6])*uint64(b.n[0])
572 d6 := uint32(c & 0x3FFFFFF)
573 c >>= 26
574
575 c += uint64(a.n[0])*uint64(b.n[7]) + uint64(a.n[1])*uint64(b.n[6]) +
576 uint64(a.n[2])*uint64(b.n[5]) + uint64(a.n[3])*uint64(b.n[4]) +
577 uint64(a.n[4])*uint64(b.n[3]) + uint64(a.n[5])*uint64(b.n[2]) +
578 uint64(a.n[6])*uint64(b.n[1]) + uint64(a.n[7])*uint64(b.n[0])
579 d7 := uint32(c & 0x3FFFFFF)
580 c >>= 26
581
582 c += uint64(a.n[0])*uint64(b.n[8]) + uint64(a.n[1])*uint64(b.n[7]) +
583 uint64(a.n[2])*uint64(b.n[6]) + uint64(a.n[3])*uint64(b.n[5]) +
584 uint64(a.n[4])*uint64(b.n[4]) + uint64(a.n[5])*uint64(b.n[3]) +
585 uint64(a.n[6])*uint64(b.n[2]) + uint64(a.n[7])*uint64(b.n[1]) +
586 uint64(a.n[8])*uint64(b.n[0])
587 d8 := uint32(c & 0x3FFFFFF)
588 c >>= 26
589
590 c += uint64(a.n[0])*uint64(b.n[9]) + uint64(a.n[1])*uint64(b.n[8]) +
591 uint64(a.n[2])*uint64(b.n[7]) + uint64(a.n[3])*uint64(b.n[6]) +
592 uint64(a.n[4])*uint64(b.n[5]) + uint64(a.n[5])*uint64(b.n[4]) +
593 uint64(a.n[6])*uint64(b.n[3]) + uint64(a.n[7])*uint64(b.n[2]) +
594 uint64(a.n[8])*uint64(b.n[1]) + uint64(a.n[9])*uint64(b.n[0])
595 d9 := uint32(c & 0x3FFFFFF)
596 c >>= 26
597
598 c += uint64(a.n[1])*uint64(b.n[9]) + uint64(a.n[2])*uint64(b.n[8]) +
599 uint64(a.n[3])*uint64(b.n[7]) + uint64(a.n[4])*uint64(b.n[6]) +
600 uint64(a.n[5])*uint64(b.n[5]) + uint64(a.n[6])*uint64(b.n[4]) +
601 uint64(a.n[7])*uint64(b.n[3]) + uint64(a.n[8])*uint64(b.n[2]) +
602 uint64(a.n[9])*uint64(b.n[1])
603 d10 := uint32(c & 0x3FFFFFF)
604 c >>= 26
605
606 c += uint64(a.n[2])*uint64(b.n[9]) + uint64(a.n[3])*uint64(b.n[8]) +
607 uint64(a.n[4])*uint64(b.n[7]) + uint64(a.n[5])*uint64(b.n[6]) +
608 uint64(a.n[6])*uint64(b.n[5]) + uint64(a.n[7])*uint64(b.n[4]) +
609 uint64(a.n[8])*uint64(b.n[3]) + uint64(a.n[9])*uint64(b.n[2])
610 d11 := uint32(c & 0x3FFFFFF)
611 c >>= 26
612
613 c += uint64(a.n[3])*uint64(b.n[9]) + uint64(a.n[4])*uint64(b.n[8]) +
614 uint64(a.n[5])*uint64(b.n[7]) + uint64(a.n[6])*uint64(b.n[6]) +
615 uint64(a.n[7])*uint64(b.n[5]) + uint64(a.n[8])*uint64(b.n[4]) +
616 uint64(a.n[9])*uint64(b.n[3])
617 d12 := uint32(c & 0x3FFFFFF)
618 c >>= 26
619
620 c += uint64(a.n[4])*uint64(b.n[9]) + uint64(a.n[5])*uint64(b.n[8]) +
621 uint64(a.n[6])*uint64(b.n[7]) + uint64(a.n[7])*uint64(b.n[6]) +
622 uint64(a.n[8])*uint64(b.n[5]) + uint64(a.n[9])*uint64(b.n[4])
623 d13 := uint32(c & 0x3FFFFFF)
624 c >>= 26
625
626 c += uint64(a.n[5])*uint64(b.n[9]) + uint64(a.n[6])*uint64(b.n[8]) +
627 uint64(a.n[7])*uint64(b.n[7]) + uint64(a.n[8])*uint64(b.n[6]) +
628 uint64(a.n[9])*uint64(b.n[5])
629 d14 := uint32(c & 0x3FFFFFF)
630 c >>= 26
631
632 c += uint64(a.n[6])*uint64(b.n[9]) + uint64(a.n[7])*uint64(b.n[8]) +
633 uint64(a.n[8])*uint64(b.n[7]) + uint64(a.n[9])*uint64(b.n[6])
634 d15 := uint32(c & 0x3FFFFFF)
635 c >>= 26
636
637 c += uint64(a.n[7])*uint64(b.n[9]) + uint64(a.n[8])*uint64(b.n[8]) +
638 uint64(a.n[9])*uint64(b.n[7])
639 d16 := uint32(c & 0x3FFFFFF)
640 c >>= 26
641
642 c += uint64(a.n[8])*uint64(b.n[9]) + uint64(a.n[9])*uint64(b.n[8])
643 d17 := uint32(c & 0x3FFFFFF)
644 c >>= 26
645
646 c += uint64(a.n[9]) * uint64(b.n[9])
647 d18 := uint32(c & 0x3FFFFFF)
648 d19 := uint32(c >> 26)
649
650 // Reduce modulo p using p = 2^256 - 2^32 - 977
651 // We add 977*d10 + 64*d11 to d0, etc.
652 d = uint64(d0) + uint64(d10)*977
653 f.n[0] = uint32(d & 0x3FFFFFF)
654 d >>= 26
655 d += uint64(d1) + uint64(d10)*64 + uint64(d11)*977
656 f.n[1] = uint32(d & 0x3FFFFFF)
657 d >>= 26
658 d += uint64(d2) + uint64(d11)*64 + uint64(d12)*977
659 f.n[2] = uint32(d & 0x3FFFFFF)
660 d >>= 26
661 d += uint64(d3) + uint64(d12)*64 + uint64(d13)*977
662 f.n[3] = uint32(d & 0x3FFFFFF)
663 d >>= 26
664 d += uint64(d4) + uint64(d13)*64 + uint64(d14)*977
665 f.n[4] = uint32(d & 0x3FFFFFF)
666 d >>= 26
667 d += uint64(d5) + uint64(d14)*64 + uint64(d15)*977
668 f.n[5] = uint32(d & 0x3FFFFFF)
669 d >>= 26
670 d += uint64(d6) + uint64(d15)*64 + uint64(d16)*977
671 f.n[6] = uint32(d & 0x3FFFFFF)
672 d >>= 26
673 d += uint64(d7) + uint64(d16)*64 + uint64(d17)*977
674 f.n[7] = uint32(d & 0x3FFFFFF)
675 d >>= 26
676 d += uint64(d8) + uint64(d17)*64 + uint64(d18)*977
677 f.n[8] = uint32(d & 0x3FFFFFF)
678 d >>= 26
679 d += uint64(d9) + uint64(d18)*64 + uint64(d19)*977
680 f.n[9] = uint32(d & 0x3FFFFF)
681 d >>= 22
682
683 // Handle any overflow from the final reduction
684 d = uint64(f.n[0]) + d*977
685 f.n[0] = uint32(d & 0x3FFFFFF)
686 d >>= 26
687 d += uint64(f.n[1]) + (d >> 26) * 64
688 f.n[1] = uint32(d & 0x3FFFFFF)
689 d >>= 26
690 f.n[2] += uint32(d)
691
692 f.magnitude = 1
693 f.normalized = false
694 }
695
696 // sqr squares a field element: r = a^2
697 func (f *FieldElement) sqr(a *FieldElement) {
698 // For squaring, we can exploit the symmetry to reduce operations
699 f.mul(a, a)
700 }
701
702 // inv computes the modular inverse using Fermat's little theorem
703 func (f *FieldElement) inv(a *FieldElement) {
704 // a^(-1) = a^(p-2) mod p
705 // p-2 = 2^256 - 2^32 - 979
706 var x2, x3, x6, x9, x11, x22, x44, x88, x176, x220, x223, t1 FieldElement
707
708 x2.sqr(a)
709 x2.mul(&x2, a)
710
711 x3.sqr(&x2)
712 x3.mul(&x3, a)
713
714 x6.sqr(&x3)
715 x6.sqr(&x6)
716 x6.sqr(&x6)
717 x6.mul(&x6, &x3)
718
719 x9.sqr(&x6)
720 x9.sqr(&x9)
721 x9.sqr(&x9)
722 x9.mul(&x9, &x3)
723
724 x11.sqr(&x9)
725 x11.sqr(&x11)
726 x11.mul(&x11, &x2)
727
728 x22.sqr(&x11)
729 for i := 0; i < 10; i++ {
730 x22.sqr(&x22)
731 }
732 x22.mul(&x22, &x11)
733
734 x44.sqr(&x22)
735 for i := 0; i < 21; i++ {
736 x44.sqr(&x44)
737 }
738 x44.mul(&x44, &x22)
739
740 x88.sqr(&x44)
741 for i := 0; i < 43; i++ {
742 x88.sqr(&x88)
743 }
744 x88.mul(&x88, &x44)
745
746 x176.sqr(&x88)
747 for i := 0; i < 87; i++ {
748 x176.sqr(&x176)
749 }
750 x176.mul(&x176, &x88)
751
752 x220.sqr(&x176)
753 for i := 0; i < 43; i++ {
754 x220.sqr(&x220)
755 }
756 x220.mul(&x220, &x44)
757
758 x223.sqr(&x220)
759 x223.sqr(&x223)
760 x223.sqr(&x223)
761 x223.mul(&x223, &x3)
762
763 t1.sqr(&x223)
764 for i := 0; i < 22; i++ {
765 t1.sqr(&t1)
766 }
767 t1.mul(&t1, &x22)
768
769 t1.sqr(&t1)
770 t1.sqr(&t1)
771 t1.sqr(&t1)
772 t1.sqr(&t1)
773 t1.sqr(&t1)
774 t1.mul(&t1, a)
775
776 t1.sqr(&t1)
777 t1.sqr(&t1)
778 t1.sqr(&t1)
779 t1.mul(&t1, &x2)
780
781 *f = t1
782 f.magnitude = 1
783 f.normalized = false
784 }
785
786 // sqrt computes the modular square root if it exists
787 func (f *FieldElement) sqrt(a *FieldElement) bool {
788 // sqrt(a) = a^((p+1)/4) if it exists
789 // (p+1)/4 = (2^256 - 2^32 - 977 + 1) / 4 = 2^254 - 2^30 - 244
790 var x2, x3, x6, x9, x11, x22, x44, x88, x176, x220, x223, t1 FieldElement
791
792 x2.sqr(a)
793 x2.mul(&x2, a)
794
795 x3.sqr(&x2)
796 x3.mul(&x3, a)
797
798 x6.sqr(&x3)
799 x6.sqr(&x6)
800 x6.sqr(&x6)
801 x6.mul(&x6, &x3)
802
803 x9.sqr(&x6)
804 x9.sqr(&x9)
805 x9.sqr(&x9)
806 x9.mul(&x9, &x3)
807
808 x11.sqr(&x9)
809 x11.sqr(&x11)
810 x11.mul(&x11, &x2)
811
812 x22.sqr(&x11)
813 for i := 0; i < 10; i++ {
814 x22.sqr(&x22)
815 }
816 x22.mul(&x22, &x11)
817
818 x44.sqr(&x22)
819 for i := 0; i < 21; i++ {
820 x44.sqr(&x44)
821 }
822 x44.mul(&x44, &x22)
823
824 x88.sqr(&x44)
825 for i := 0; i < 43; i++ {
826 x88.sqr(&x88)
827 }
828 x88.mul(&x88, &x44)
829
830 x176.sqr(&x88)
831 for i := 0; i < 87; i++ {
832 x176.sqr(&x176)
833 }
834 x176.mul(&x176, &x88)
835
836 x220.sqr(&x176)
837 for i := 0; i < 43; i++ {
838 x220.sqr(&x220)
839 }
840 x220.mul(&x220, &x44)
841
842 x223.sqr(&x220)
843 x223.sqr(&x223)
844 x223.sqr(&x223)
845 x223.mul(&x223, &x3)
846
847 // Compute a^((p+1)/4) = a^(2^254 - 2^30 - 244)
848 t1.sqr(&x223)
849 for i := 0; i < 22; i++ {
850 t1.sqr(&t1)
851 }
852 t1.mul(&t1, &x22)
853
854 t1.sqr(&t1)
855 t1.sqr(&t1)
856 t1.sqr(&t1)
857 t1.sqr(&t1)
858 t1.sqr(&t1)
859 t1.sqr(&t1)
860 t1.mul(&t1, &x2)
861
862 *f = t1
863 f.normalize()
864
865 // Verify: r^2 == a
866 var check FieldElement
867 check.sqr(f)
868 check.normalize()
869
870 var aNorm FieldElement
871 aNorm = *a
872 aNorm.normalize()
873
874 return check.equal(&aNorm)
875 }
876
877 // Constant-time helper functions for 32-bit values
878 func constantTimeEq32(a, b uint32) uint32 {
879 return uint32((uint64(a^b) - 1) >> 63)
880 }
881
882 func constantTimeGreater32(a, b uint32) uint32 {
883 return uint32((uint64(b) - uint64(a)) >> 63)
884 }
885
886 // memclear clears memory
887 func memclear(ptr unsafe.Pointer, n uintptr) {
888 for i := uintptr(0); i < n; i++ {
889 *(*byte)(unsafe.Pointer(uintptr(ptr) + i)) = 0
890 }
891 }
892
893 func boolToInt(b bool) int {
894 if b {
895 return 1
896 }
897 return 0
898 }
899
900 // batchInverse computes the inverses of a slice of FieldElements
901 func batchInverse(out []FieldElement, a []FieldElement) {
902 n := len(a)
903 if n == 0 {
904 return
905 }
906
907 s := make([]FieldElement, n)
908 s[0].setInt(1)
909 for i := 1; i < n; i++ {
910 s[i].mul(&s[i-1], &a[i-1])
911 }
912
913 var u FieldElement
914 u.mul(&s[n-1], &a[n-1])
915 u.inv(&u)
916
917 for i := n - 1; i >= 0; i-- {
918 out[i].mul(&u, &s[i])
919 u.mul(&u, &a[i])
920 }
921 }
922
923 // batchInverse16 computes the inverses of exactly 16 FieldElements with zero heap allocations.
924 // This is optimized for the GLV table size (glvTableSize = 16).
925 // Uses Montgomery's trick with stack-allocated arrays.
926 func batchInverse16(out *[16]FieldElement, a *[16]FieldElement) {
927 // Stack-allocated scratch array for prefix products
928 var s [16]FieldElement
929
930 // s_i = a_0 * a_1 * ... * a_{i-1}
931 s[0].setInt(1)
932 for i := 1; i < 16; i++ {
933 s[i].mul(&s[i-1], &a[i-1])
934 }
935
936 // u = (a_0 * a_1 * ... * a_{15})^-1
937 var u FieldElement
938 u.mul(&s[15], &a[15])
939 u.inv(&u)
940
941 // out_i = (a_0 * ... * a_{i-1}) * (a_0 * ... * a_i)^-1
942 // Loop backwards for in-place computation
943 for i := 15; i >= 0; i-- {
944 out[i].mul(&u, &s[i])
945 u.mul(&u, &a[i])
946 }
947 }
948
949 // Placeholder stubs for Montgomery functions (not used in 10x26 representation)
950 const montgomeryPPrime = 0
951
952 var montgomeryR2 *FieldElement = nil
953
954 func (f *FieldElement) ToMontgomery() *FieldElement { return f }
955 func (f *FieldElement) FromMontgomery() *FieldElement { return f }
956 func MontgomeryMul(a, b *FieldElement) *FieldElement {
957 var r FieldElement
958 r.mul(a, b)
959 return &r
960 }
961
962 // Direct function versions
963 func fieldNormalize(r *FieldElement) { r.normalize() }
964 func fieldNormalizeWeak(r *FieldElement) { r.normalizeWeak() }
965 func fieldAdd(r, a *FieldElement) { r.add(a) }
966 func fieldIsZero(a *FieldElement) bool { return a.isZero() }
967 func fieldGetB32(b []byte, a *FieldElement) { a.getB32(b) }
968 func fieldMul(r, a, b []uint64) {} // Not used for 32-bit
969 func fieldSqr(r, a []uint64) {} // Not used for 32-bit
970 func fieldInvVar(r, a []uint64) {} // Not used for 32-bit
971 func fieldSqrt(r, a []uint64) bool { return false }
972