-
Notifications
You must be signed in to change notification settings - Fork 295
/
field.go
1696 lines (1589 loc) · 71.1 KB
/
field.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// Copyright (c) 2013-2014 The btcsuite developers
// Copyright (c) 2015-2024 The Decred developers
// Copyright (c) 2013-2024 Dave Collins
// Use of this source code is governed by an ISC
// license that can be found in the LICENSE file.
package secp256k1
// References:
// [HAC]: Handbook of Applied Cryptography Menezes, van Oorschot, Vanstone.
// http://cacr.uwaterloo.ca/hac/
// All elliptic curve operations for secp256k1 are done in a finite field
// characterized by a 256-bit prime. Given this precision is larger than the
// biggest available native type, obviously some form of bignum math is needed.
// This package implements specialized fixed-precision field arithmetic rather
// than relying on an arbitrary-precision arithmetic package such as math/big
// for dealing with the field math since the size is known. As a result, rather
// large performance gains are achieved by taking advantage of many
// optimizations not available to arbitrary-precision arithmetic and generic
// modular arithmetic algorithms.
//
// There are various ways to internally represent each finite field element.
// For example, the most obvious representation would be to use an array of 4
// uint64s (64 bits * 4 = 256 bits). However, that representation suffers from
// a couple of issues. First, there is no native Go type large enough to handle
// the intermediate results while adding or multiplying two 64-bit numbers, and
// second there is no space left for overflows when performing the intermediate
// arithmetic between each array element which would lead to expensive carry
// propagation.
//
// Given the above, this implementation represents the field elements as
// 10 uint32s with each word (array entry) treated as base 2^26. This was
// chosen for the following reasons:
// 1) Most systems at the current time are 64-bit (or at least have 64-bit
// registers available for specialized purposes such as MMX) so the
// intermediate results can typically be done using a native register (and
// using uint64s to avoid the need for additional half-word arithmetic)
// 2) In order to allow addition of the internal words without having to
// propagate the carry, the max normalized value for each register must
// be less than the number of bits available in the register
// 3) Since we're dealing with 32-bit values, 64-bits of overflow is a
// reasonable choice for #2
// 4) Given the need for 256-bits of precision and the properties stated in #1,
// #2, and #3, the representation which best accommodates this is 10 uint32s
// with base 2^26 (26 bits * 10 = 260 bits, so the final word only needs 22
// bits) which leaves the desired 64 bits (32 * 10 = 320, 320 - 256 = 64) for
// overflow
//
// Since it is so important that the field arithmetic is extremely fast for high
// performance crypto, this type does not perform any validation where it
// ordinarily would. See the documentation for FieldVal for more details.
import (
"encoding/hex"
)
// Constants used to make the code more readable.
const (
twoBitsMask = 0x3
fourBitsMask = 0xf
sixBitsMask = 0x3f
eightBitsMask = 0xff
)
// Constants related to the field representation.
const (
// fieldWords is the number of words used to internally represent the
// 256-bit value.
fieldWords = 10
// fieldBase is the exponent used to form the numeric base of each word.
// 2^(fieldBase*i) where i is the word position.
fieldBase = 26
// fieldBaseMask is the mask for the bits in each word needed to
// represent the numeric base of each word (except the most significant
// word).
fieldBaseMask = (1 << fieldBase) - 1
// fieldMSBBits is the number of bits in the most significant word used
// to represent the value.
fieldMSBBits = 256 - (fieldBase * (fieldWords - 1))
// fieldMSBMask is the mask for the bits in the most significant word
// needed to represent the value.
fieldMSBMask = (1 << fieldMSBBits) - 1
// These fields provide convenient access to each of the words of the
// secp256k1 prime in the internal field representation to improve code
// readability.
fieldPrimeWordZero = 0x03fffc2f
fieldPrimeWordOne = 0x03ffffbf
fieldPrimeWordTwo = 0x03ffffff
fieldPrimeWordThree = 0x03ffffff
fieldPrimeWordFour = 0x03ffffff
fieldPrimeWordFive = 0x03ffffff
fieldPrimeWordSix = 0x03ffffff
fieldPrimeWordSeven = 0x03ffffff
fieldPrimeWordEight = 0x03ffffff
fieldPrimeWordNine = 0x003fffff
)
// FieldVal implements optimized fixed-precision arithmetic over the
// secp256k1 finite field. This means all arithmetic is performed modulo
//
// 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f.
//
// WARNING: Since it is so important for the field arithmetic to be extremely
// fast for high performance crypto, this type does not perform any validation
// of documented preconditions where it ordinarily would. As a result, it is
// IMPERATIVE for callers to understand some key concepts that are described
// below and ensure the methods are called with the necessary preconditions that
// each method is documented with. For example, some methods only give the
// correct result if the field value is normalized and others require the field
// values involved to have a maximum magnitude and THERE ARE NO EXPLICIT CHECKS
// TO ENSURE THOSE PRECONDITIONS ARE SATISFIED. This does, unfortunately, make
// the type more difficult to use correctly and while I typically prefer to
// ensure all state and input is valid for most code, this is a bit of an
// exception because those extra checks really add up in what ends up being
// critical hot paths.
//
// The first key concept when working with this type is normalization. In order
// to avoid the need to propagate a ton of carries, the internal representation
// provides additional overflow bits for each word of the overall 256-bit value.
// This means that there are multiple internal representations for the same
// value and, as a result, any methods that rely on comparison of the value,
// such as equality and oddness determination, require the caller to provide a
// normalized value.
//
// The second key concept when working with this type is magnitude. As
// previously mentioned, the internal representation provides additional
// overflow bits which means that the more math operations that are performed on
// the field value between normalizations, the more those overflow bits
// accumulate. The magnitude is effectively that maximum possible number of
// those overflow bits that could possibly be required as a result of a given
// operation. Since there are only a limited number of overflow bits available,
// this implies that the max possible magnitude MUST be tracked by the caller
// and the caller MUST normalize the field value if a given operation would
// cause the magnitude of the result to exceed the max allowed value.
//
// IMPORTANT: The max allowed magnitude of a field value is 32.
type FieldVal struct {
// Each 256-bit value is represented as 10 32-bit integers in base 2^26.
// This provides 6 bits of overflow in each word (10 bits in the most
// significant word) for a total of 64 bits of overflow (9*6 + 10 = 64). It
// only implements the arithmetic needed for elliptic curve operations.
//
// The following depicts the internal representation:
// -----------------------------------------------------------------
// | n[9] | n[8] | ... | n[0] |
// | 32 bits available | 32 bits available | ... | 32 bits available |
// | 22 bits for value | 26 bits for value | ... | 26 bits for value |
// | 10 bits overflow | 6 bits overflow | ... | 6 bits overflow |
// | Mult: 2^(26*9) | Mult: 2^(26*8) | ... | Mult: 2^(26*0) |
// -----------------------------------------------------------------
//
// For example, consider the number 2^49 + 1. It would be represented as:
// n[0] = 1
// n[1] = 2^23
// n[2..9] = 0
//
// The full 256-bit value is then calculated by looping i from 9..0 and
// doing sum(n[i] * 2^(26i)) like so:
// n[9] * 2^(26*9) = 0 * 2^234 = 0
// n[8] * 2^(26*8) = 0 * 2^208 = 0
// ...
// n[1] * 2^(26*1) = 2^23 * 2^26 = 2^49
// n[0] * 2^(26*0) = 1 * 2^0 = 1
// Sum: 0 + 0 + ... + 2^49 + 1 = 2^49 + 1
n [10]uint32
}
// String returns the field value as a normalized human-readable hex string.
//
// Preconditions: None
// Output Normalized: Field is not modified -- same as input value
// Output Max Magnitude: Field is not modified -- same as input value
func (f FieldVal) String() string {
// f is a copy, so it's safe to normalize it without mutating the original.
f.Normalize()
return hex.EncodeToString(f.Bytes()[:])
}
// Zero sets the field value to zero in constant time. A newly created field
// value is already set to zero. This function can be useful to clear an
// existing field value for reuse.
//
// Preconditions: None
// Output Normalized: Yes
// Output Max Magnitude: 1
func (f *FieldVal) Zero() {
f.n[0] = 0
f.n[1] = 0
f.n[2] = 0
f.n[3] = 0
f.n[4] = 0
f.n[5] = 0
f.n[6] = 0
f.n[7] = 0
f.n[8] = 0
f.n[9] = 0
}
// Set sets the field value equal to the passed value in constant time. The
// normalization and magnitude of the two fields will be identical.
//
// The field value is returned to support chaining. This enables syntax like:
// f := new(FieldVal).Set(f2).Add(1) so that f = f2 + 1 where f2 is not
// modified.
//
// Preconditions: None
// Output Normalized: Same as input value
// Output Max Magnitude: Same as input value
func (f *FieldVal) Set(val *FieldVal) *FieldVal {
*f = *val
return f
}
// SetInt sets the field value to the passed integer in constant time. This is
// a convenience function since it is fairly common to perform some arithmetic
// with small native integers.
//
// The field value is returned to support chaining. This enables syntax such
// as f := new(FieldVal).SetInt(2).Mul(f2) so that f = 2 * f2.
//
// Preconditions: None
// Output Normalized: Yes
// Output Max Magnitude: 1
func (f *FieldVal) SetInt(ui uint16) *FieldVal {
f.Zero()
f.n[0] = uint32(ui)
return f
}
// SetBytes packs the passed 32-byte big-endian value into the internal field
// value representation in constant time. SetBytes interprets the provided
// array as a 256-bit big-endian unsigned integer, packs it into the internal
// field value representation, and returns either 1 if it is greater than or
// equal to the field prime (aka it overflowed) or 0 otherwise in constant time.
//
// Note that a bool is not used here because it is not possible in Go to convert
// from a bool to numeric value in constant time and many constant-time
// operations require a numeric value.
//
// Preconditions: None
// Output Normalized: Yes if no overflow, no otherwise
// Output Max Magnitude: 1
func (f *FieldVal) SetBytes(b *[32]byte) uint32 {
// Pack the 256 total bits across the 10 uint32 words with a max of
// 26-bits per word. This could be done with a couple of for loops,
// but this unrolled version is significantly faster. Benchmarks show
// this is about 34 times faster than the variant which uses loops.
f.n[0] = uint32(b[31]) | uint32(b[30])<<8 | uint32(b[29])<<16 |
(uint32(b[28])&twoBitsMask)<<24
f.n[1] = uint32(b[28])>>2 | uint32(b[27])<<6 | uint32(b[26])<<14 |
(uint32(b[25])&fourBitsMask)<<22
f.n[2] = uint32(b[25])>>4 | uint32(b[24])<<4 | uint32(b[23])<<12 |
(uint32(b[22])&sixBitsMask)<<20
f.n[3] = uint32(b[22])>>6 | uint32(b[21])<<2 | uint32(b[20])<<10 |
uint32(b[19])<<18
f.n[4] = uint32(b[18]) | uint32(b[17])<<8 | uint32(b[16])<<16 |
(uint32(b[15])&twoBitsMask)<<24
f.n[5] = uint32(b[15])>>2 | uint32(b[14])<<6 | uint32(b[13])<<14 |
(uint32(b[12])&fourBitsMask)<<22
f.n[6] = uint32(b[12])>>4 | uint32(b[11])<<4 | uint32(b[10])<<12 |
(uint32(b[9])&sixBitsMask)<<20
f.n[7] = uint32(b[9])>>6 | uint32(b[8])<<2 | uint32(b[7])<<10 |
uint32(b[6])<<18
f.n[8] = uint32(b[5]) | uint32(b[4])<<8 | uint32(b[3])<<16 |
(uint32(b[2])&twoBitsMask)<<24
f.n[9] = uint32(b[2])>>2 | uint32(b[1])<<6 | uint32(b[0])<<14
// The intuition here is that the field value is greater than the prime if
// one of the higher individual words is greater than corresponding word of
// the prime and all higher words in the field value are equal to their
// corresponding word of the prime. Since this type is modulo the prime,
// being equal is also an overflow back to 0.
//
// Note that because the input is 32 bytes and it was just packed into the
// field representation, the only words that can possibly be greater are
// zero and one, because ceil(log_2(2^256 - 1 - P)) = 33 bits max and the
// internal field representation encodes 26 bits with each word.
//
// Thus, there is no need to test if the upper words of the field value
// exceeds them, hence, only equality is checked for them.
highWordsEq := constantTimeEq(f.n[9], fieldPrimeWordNine)
highWordsEq &= constantTimeEq(f.n[8], fieldPrimeWordEight)
highWordsEq &= constantTimeEq(f.n[7], fieldPrimeWordSeven)
highWordsEq &= constantTimeEq(f.n[6], fieldPrimeWordSix)
highWordsEq &= constantTimeEq(f.n[5], fieldPrimeWordFive)
highWordsEq &= constantTimeEq(f.n[4], fieldPrimeWordFour)
highWordsEq &= constantTimeEq(f.n[3], fieldPrimeWordThree)
highWordsEq &= constantTimeEq(f.n[2], fieldPrimeWordTwo)
overflow := highWordsEq & constantTimeGreater(f.n[1], fieldPrimeWordOne)
highWordsEq &= constantTimeEq(f.n[1], fieldPrimeWordOne)
overflow |= highWordsEq & constantTimeGreaterOrEq(f.n[0], fieldPrimeWordZero)
return overflow
}
// SetByteSlice interprets the provided slice as a 256-bit big-endian unsigned
// integer (meaning it is truncated to the first 32 bytes), packs it into the
// internal field value representation, and returns whether or not the resulting
// truncated 256-bit integer is greater than or equal to the field prime (aka it
// overflowed) in constant time.
//
// Note that since passing a slice with more than 32 bytes is truncated, it is
// possible that the truncated value is less than the field prime and hence it
// will not be reported as having overflowed in that case. It is up to the
// caller to decide whether it needs to provide numbers of the appropriate size
// or it if is acceptable to use this function with the described truncation and
// overflow behavior.
//
// Preconditions: None
// Output Normalized: Yes if no overflow, no otherwise
// Output Max Magnitude: 1
func (f *FieldVal) SetByteSlice(b []byte) bool {
var b32 [32]byte
b = b[:constantTimeMin(uint32(len(b)), 32)]
copy(b32[:], b32[:32-len(b)])
copy(b32[32-len(b):], b)
result := f.SetBytes(&b32)
zeroArray32(&b32)
return result != 0
}
// Normalize normalizes the internal field words into the desired range and
// performs fast modular reduction over the secp256k1 prime by making use of the
// special form of the prime in constant time.
//
// Preconditions: None
// Output Normalized: Yes
// Output Max Magnitude: 1
func (f *FieldVal) Normalize() *FieldVal {
// The field representation leaves 6 bits of overflow in each word so
// intermediate calculations can be performed without needing to
// propagate the carry to each higher word during the calculations. In
// order to normalize, we need to "compact" the full 256-bit value to
// the right while propagating any carries through to the high order
// word.
//
// Since this field is doing arithmetic modulo the secp256k1 prime, we
// also need to perform modular reduction over the prime.
//
// Per [HAC] section 14.3.4: Reduction method of moduli of special form,
// when the modulus is of the special form m = b^t - c, highly efficient
// reduction can be achieved.
//
// The secp256k1 prime is equivalent to 2^256 - 4294968273, so it fits
// this criteria.
//
// 4294968273 in field representation (base 2^26) is:
// n[0] = 977
// n[1] = 64
// That is to say (2^26 * 64) + 977 = 4294968273
//
// The algorithm presented in the referenced section typically repeats
// until the quotient is zero. However, due to our field representation
// we already know to within one reduction how many times we would need
// to repeat as it's the uppermost bits of the high order word. Thus we
// can simply multiply the magnitude by the field representation of the
// prime and do a single iteration. After this step there might be an
// additional carry to bit 256 (bit 22 of the high order word).
t9 := f.n[9]
m := t9 >> fieldMSBBits
t9 &= fieldMSBMask
t0 := f.n[0] + m*977
t1 := (t0 >> fieldBase) + f.n[1] + (m << 6)
t0 &= fieldBaseMask
t2 := (t1 >> fieldBase) + f.n[2]
t1 &= fieldBaseMask
t3 := (t2 >> fieldBase) + f.n[3]
t2 &= fieldBaseMask
t4 := (t3 >> fieldBase) + f.n[4]
t3 &= fieldBaseMask
t5 := (t4 >> fieldBase) + f.n[5]
t4 &= fieldBaseMask
t6 := (t5 >> fieldBase) + f.n[6]
t5 &= fieldBaseMask
t7 := (t6 >> fieldBase) + f.n[7]
t6 &= fieldBaseMask
t8 := (t7 >> fieldBase) + f.n[8]
t7 &= fieldBaseMask
t9 = (t8 >> fieldBase) + t9
t8 &= fieldBaseMask
// At this point, the magnitude is guaranteed to be one, however, the
// value could still be greater than the prime if there was either a
// carry through to bit 256 (bit 22 of the higher order word) or the
// value is greater than or equal to the field characteristic. The
// following determines if either or these conditions are true and does
// the final reduction in constant time.
//
// Also note that 'm' will be zero when neither of the aforementioned
// conditions are true and the value will not be changed when 'm' is zero.
m = constantTimeEq(t9, fieldMSBMask)
m &= constantTimeEq(t8&t7&t6&t5&t4&t3&t2, fieldBaseMask)
m &= constantTimeGreater(t1+64+((t0+977)>>fieldBase), fieldBaseMask)
m |= t9 >> fieldMSBBits
t0 += m * 977
t1 = (t0 >> fieldBase) + t1 + (m << 6)
t0 &= fieldBaseMask
t2 = (t1 >> fieldBase) + t2
t1 &= fieldBaseMask
t3 = (t2 >> fieldBase) + t3
t2 &= fieldBaseMask
t4 = (t3 >> fieldBase) + t4
t3 &= fieldBaseMask
t5 = (t4 >> fieldBase) + t5
t4 &= fieldBaseMask
t6 = (t5 >> fieldBase) + t6
t5 &= fieldBaseMask
t7 = (t6 >> fieldBase) + t7
t6 &= fieldBaseMask
t8 = (t7 >> fieldBase) + t8
t7 &= fieldBaseMask
t9 = (t8 >> fieldBase) + t9
t8 &= fieldBaseMask
t9 &= fieldMSBMask // Remove potential multiple of 2^256.
// Finally, set the normalized and reduced words.
f.n[0] = t0
f.n[1] = t1
f.n[2] = t2
f.n[3] = t3
f.n[4] = t4
f.n[5] = t5
f.n[6] = t6
f.n[7] = t7
f.n[8] = t8
f.n[9] = t9
return f
}
// PutBytesUnchecked unpacks the field value to a 32-byte big-endian value
// directly into the passed byte slice in constant time. The target slice must
// have at least 32 bytes available or it will panic.
//
// There is a similar function, PutBytes, which unpacks the field value into a
// 32-byte array directly. This version is provided since it can be useful
// to write directly into part of a larger buffer without needing a separate
// allocation.
//
// Preconditions:
// - The field value MUST be normalized
// - The target slice MUST have at least 32 bytes available
func (f *FieldVal) PutBytesUnchecked(b []byte) {
// Unpack the 256 total bits from the 10 uint32 words with a max of
// 26-bits per word. This could be done with a couple of for loops,
// but this unrolled version is a bit faster. Benchmarks show this is
// about 10 times faster than the variant which uses loops.
b[31] = byte(f.n[0] & eightBitsMask)
b[30] = byte((f.n[0] >> 8) & eightBitsMask)
b[29] = byte((f.n[0] >> 16) & eightBitsMask)
b[28] = byte((f.n[0]>>24)&twoBitsMask | (f.n[1]&sixBitsMask)<<2)
b[27] = byte((f.n[1] >> 6) & eightBitsMask)
b[26] = byte((f.n[1] >> 14) & eightBitsMask)
b[25] = byte((f.n[1]>>22)&fourBitsMask | (f.n[2]&fourBitsMask)<<4)
b[24] = byte((f.n[2] >> 4) & eightBitsMask)
b[23] = byte((f.n[2] >> 12) & eightBitsMask)
b[22] = byte((f.n[2]>>20)&sixBitsMask | (f.n[3]&twoBitsMask)<<6)
b[21] = byte((f.n[3] >> 2) & eightBitsMask)
b[20] = byte((f.n[3] >> 10) & eightBitsMask)
b[19] = byte((f.n[3] >> 18) & eightBitsMask)
b[18] = byte(f.n[4] & eightBitsMask)
b[17] = byte((f.n[4] >> 8) & eightBitsMask)
b[16] = byte((f.n[4] >> 16) & eightBitsMask)
b[15] = byte((f.n[4]>>24)&twoBitsMask | (f.n[5]&sixBitsMask)<<2)
b[14] = byte((f.n[5] >> 6) & eightBitsMask)
b[13] = byte((f.n[5] >> 14) & eightBitsMask)
b[12] = byte((f.n[5]>>22)&fourBitsMask | (f.n[6]&fourBitsMask)<<4)
b[11] = byte((f.n[6] >> 4) & eightBitsMask)
b[10] = byte((f.n[6] >> 12) & eightBitsMask)
b[9] = byte((f.n[6]>>20)&sixBitsMask | (f.n[7]&twoBitsMask)<<6)
b[8] = byte((f.n[7] >> 2) & eightBitsMask)
b[7] = byte((f.n[7] >> 10) & eightBitsMask)
b[6] = byte((f.n[7] >> 18) & eightBitsMask)
b[5] = byte(f.n[8] & eightBitsMask)
b[4] = byte((f.n[8] >> 8) & eightBitsMask)
b[3] = byte((f.n[8] >> 16) & eightBitsMask)
b[2] = byte((f.n[8]>>24)&twoBitsMask | (f.n[9]&sixBitsMask)<<2)
b[1] = byte((f.n[9] >> 6) & eightBitsMask)
b[0] = byte((f.n[9] >> 14) & eightBitsMask)
}
// PutBytes unpacks the field value to a 32-byte big-endian value using the
// passed byte array in constant time.
//
// There is a similar function, PutBytesUnchecked, which unpacks the field value
// into a slice that must have at least 32 bytes available. This version is
// provided since it can be useful to write directly into an array that is type
// checked.
//
// Alternatively, there is also Bytes, which unpacks the field value into a new
// array and returns that which can sometimes be more ergonomic in applications
// that aren't concerned about an additional copy.
//
// Preconditions:
// - The field value MUST be normalized
func (f *FieldVal) PutBytes(b *[32]byte) {
f.PutBytesUnchecked(b[:])
}
// Bytes unpacks the field value to a 32-byte big-endian value in constant time.
//
// See PutBytes and PutBytesUnchecked for variants that allow an array or slice
// to be passed which can be useful to cut down on the number of allocations by
// allowing the caller to reuse a buffer or write directly into part of a larger
// buffer.
//
// Preconditions:
// - The field value MUST be normalized
func (f *FieldVal) Bytes() *[32]byte {
b := new([32]byte)
f.PutBytesUnchecked(b[:])
return b
}
// IsZeroBit returns 1 when the field value is equal to zero or 0 otherwise in
// constant time.
//
// Note that a bool is not used here because it is not possible in Go to convert
// from a bool to numeric value in constant time and many constant-time
// operations require a numeric value. See IsZero for the version that returns
// a bool.
//
// Preconditions:
// - The field value MUST be normalized
func (f *FieldVal) IsZeroBit() uint32 {
// The value can only be zero if no bits are set in any of the words.
// This is a constant time implementation.
bits := f.n[0] | f.n[1] | f.n[2] | f.n[3] | f.n[4] |
f.n[5] | f.n[6] | f.n[7] | f.n[8] | f.n[9]
return constantTimeEq(bits, 0)
}
// IsZero returns whether or not the field value is equal to zero in constant
// time.
//
// Preconditions:
// - The field value MUST be normalized
func (f *FieldVal) IsZero() bool {
// The value can only be zero if no bits are set in any of the words.
// This is a constant time implementation.
bits := f.n[0] | f.n[1] | f.n[2] | f.n[3] | f.n[4] |
f.n[5] | f.n[6] | f.n[7] | f.n[8] | f.n[9]
return bits == 0
}
// IsOneBit returns 1 when the field value is equal to one or 0 otherwise in
// constant time.
//
// Note that a bool is not used here because it is not possible in Go to convert
// from a bool to numeric value in constant time and many constant-time
// operations require a numeric value. See IsOne for the version that returns a
// bool.
//
// Preconditions:
// - The field value MUST be normalized
func (f *FieldVal) IsOneBit() uint32 {
// The value can only be one if the single lowest significant bit is set in
// the first word and no other bits are set in any of the other words.
// This is a constant time implementation.
bits := (f.n[0] ^ 1) | f.n[1] | f.n[2] | f.n[3] | f.n[4] | f.n[5] |
f.n[6] | f.n[7] | f.n[8] | f.n[9]
return constantTimeEq(bits, 0)
}
// IsOne returns whether or not the field value is equal to one in constant
// time.
//
// Preconditions:
// - The field value MUST be normalized
func (f *FieldVal) IsOne() bool {
// The value can only be one if the single lowest significant bit is set in
// the first word and no other bits are set in any of the other words.
// This is a constant time implementation.
bits := (f.n[0] ^ 1) | f.n[1] | f.n[2] | f.n[3] | f.n[4] | f.n[5] |
f.n[6] | f.n[7] | f.n[8] | f.n[9]
return bits == 0
}
// IsOddBit returns 1 when the field value is an odd number or 0 otherwise in
// constant time.
//
// Note that a bool is not used here because it is not possible in Go to convert
// from a bool to numeric value in constant time and many constant-time
// operations require a numeric value. See IsOdd for the version that returns a
// bool.
//
// Preconditions:
// - The field value MUST be normalized
func (f *FieldVal) IsOddBit() uint32 {
// Only odd numbers have the bottom bit set.
return f.n[0] & 1
}
// IsOdd returns whether or not the field value is an odd number in constant
// time.
//
// Preconditions:
// - The field value MUST be normalized
func (f *FieldVal) IsOdd() bool {
// Only odd numbers have the bottom bit set.
return f.n[0]&1 == 1
}
// Equals returns whether or not the two field values are the same in constant
// time.
//
// Preconditions:
// - Both field values being compared MUST be normalized
func (f *FieldVal) Equals(val *FieldVal) bool {
// Xor only sets bits when they are different, so the two field values
// can only be the same if no bits are set after xoring each word.
// This is a constant time implementation.
bits := (f.n[0] ^ val.n[0]) | (f.n[1] ^ val.n[1]) | (f.n[2] ^ val.n[2]) |
(f.n[3] ^ val.n[3]) | (f.n[4] ^ val.n[4]) | (f.n[5] ^ val.n[5]) |
(f.n[6] ^ val.n[6]) | (f.n[7] ^ val.n[7]) | (f.n[8] ^ val.n[8]) |
(f.n[9] ^ val.n[9])
return bits == 0
}
// NegateVal negates the passed value and stores the result in f in constant
// time. The caller must provide the maximum magnitude of the passed value for
// a correct result.
//
// The field value is returned to support chaining. This enables syntax like:
// f.NegateVal(f2).AddInt(1) so that f = -f2 + 1.
//
// Preconditions:
// - The max magnitude MUST be 31
// Output Normalized: No
// Output Max Magnitude: Input magnitude + 1
func (f *FieldVal) NegateVal(val *FieldVal, magnitude uint32) *FieldVal {
// Negation in the field is just the prime minus the value. However,
// in order to allow negation against a field value without having to
// normalize/reduce it first, multiply by the magnitude (that is how
// "far" away it is from the normalized value) to adjust. Also, since
// negating a value pushes it one more order of magnitude away from the
// normalized range, add 1 to compensate.
//
// For some intuition here, imagine you're performing mod 12 arithmetic
// (picture a clock) and you are negating the number 7. So you start at
// 12 (which is of course 0 under mod 12) and count backwards (left on
// the clock) 7 times to arrive at 5. Notice this is just 12-7 = 5.
// Now, assume you're starting with 19, which is a number that is
// already larger than the modulus and congruent to 7 (mod 12). When a
// value is already in the desired range, its magnitude is 1. Since 19
// is an additional "step", its magnitude (mod 12) is 2. Since any
// multiple of the modulus is congruent to zero (mod m), the answer can
// be shortcut by simply multiplying the magnitude by the modulus and
// subtracting. Keeping with the example, this would be (2*12)-19 = 5.
f.n[0] = (magnitude+1)*fieldPrimeWordZero - val.n[0]
f.n[1] = (magnitude+1)*fieldPrimeWordOne - val.n[1]
f.n[2] = (magnitude+1)*fieldBaseMask - val.n[2]
f.n[3] = (magnitude+1)*fieldBaseMask - val.n[3]
f.n[4] = (magnitude+1)*fieldBaseMask - val.n[4]
f.n[5] = (magnitude+1)*fieldBaseMask - val.n[5]
f.n[6] = (magnitude+1)*fieldBaseMask - val.n[6]
f.n[7] = (magnitude+1)*fieldBaseMask - val.n[7]
f.n[8] = (magnitude+1)*fieldBaseMask - val.n[8]
f.n[9] = (magnitude+1)*fieldMSBMask - val.n[9]
return f
}
// Negate negates the field value in constant time. The existing field value is
// modified. The caller must provide the maximum magnitude of the field value
// for a correct result.
//
// The field value is returned to support chaining. This enables syntax like:
// f.Negate().AddInt(1) so that f = -f + 1.
//
// Preconditions:
// - The max magnitude MUST be 31
// Output Normalized: No
// Output Max Magnitude: Input magnitude + 1
func (f *FieldVal) Negate(magnitude uint32) *FieldVal {
return f.NegateVal(f, magnitude)
}
// AddInt adds the passed integer to the existing field value and stores the
// result in f in constant time. This is a convenience function since it is
// fairly common to perform some arithmetic with small native integers.
//
// The field value is returned to support chaining. This enables syntax like:
// f.AddInt(1).Add(f2) so that f = f + 1 + f2.
//
// Preconditions:
// - The field value MUST have a max magnitude of 31
// - The integer MUST be a max of 32767
// Output Normalized: No
// Output Max Magnitude: Existing field magnitude + 1
func (f *FieldVal) AddInt(ui uint16) *FieldVal {
// Since the field representation intentionally provides overflow bits,
// it's ok to use carryless addition as the carry bit is safely part of
// the word and will be normalized out.
f.n[0] += uint32(ui)
return f
}
// Add adds the passed value to the existing field value and stores the result
// in f in constant time.
//
// The field value is returned to support chaining. This enables syntax like:
// f.Add(f2).AddInt(1) so that f = f + f2 + 1.
//
// Preconditions:
// - The sum of the magnitudes of the two field values MUST be a max of 32
// Output Normalized: No
// Output Max Magnitude: Sum of the magnitude of the two individual field values
func (f *FieldVal) Add(val *FieldVal) *FieldVal {
// Since the field representation intentionally provides overflow bits,
// it's ok to use carryless addition as the carry bit is safely part of
// each word and will be normalized out. This could obviously be done
// in a loop, but the unrolled version is faster.
f.n[0] += val.n[0]
f.n[1] += val.n[1]
f.n[2] += val.n[2]
f.n[3] += val.n[3]
f.n[4] += val.n[4]
f.n[5] += val.n[5]
f.n[6] += val.n[6]
f.n[7] += val.n[7]
f.n[8] += val.n[8]
f.n[9] += val.n[9]
return f
}
// Add2 adds the passed two field values together and stores the result in f in
// constant time.
//
// The field value is returned to support chaining. This enables syntax like:
// f3.Add2(f, f2).AddInt(1) so that f3 = f + f2 + 1.
//
// Preconditions:
// - The sum of the magnitudes of the two field values MUST be a max of 32
// Output Normalized: No
// Output Max Magnitude: Sum of the magnitude of the two field values
func (f *FieldVal) Add2(val *FieldVal, val2 *FieldVal) *FieldVal {
// Since the field representation intentionally provides overflow bits,
// it's ok to use carryless addition as the carry bit is safely part of
// each word and will be normalized out. This could obviously be done
// in a loop, but the unrolled version is faster.
f.n[0] = val.n[0] + val2.n[0]
f.n[1] = val.n[1] + val2.n[1]
f.n[2] = val.n[2] + val2.n[2]
f.n[3] = val.n[3] + val2.n[3]
f.n[4] = val.n[4] + val2.n[4]
f.n[5] = val.n[5] + val2.n[5]
f.n[6] = val.n[6] + val2.n[6]
f.n[7] = val.n[7] + val2.n[7]
f.n[8] = val.n[8] + val2.n[8]
f.n[9] = val.n[9] + val2.n[9]
return f
}
// MulInt multiplies the field value by the passed int and stores the result in
// f in constant time. Note that this function can overflow if multiplying the
// value by any of the individual words exceeds a max uint32. Therefore it is
// important that the caller ensures no overflows will occur before using this
// function.
//
// The field value is returned to support chaining. This enables syntax like:
// f.MulInt(2).Add(f2) so that f = 2 * f + f2.
//
// Preconditions:
// - The field value magnitude multiplied by given val MUST be a max of 32
// Output Normalized: No
// Output Max Magnitude: Existing field magnitude times the provided integer val
func (f *FieldVal) MulInt(val uint8) *FieldVal {
// Since each word of the field representation can hold up to
// 32 - fieldBase extra bits which will be normalized out, it's safe
// to multiply each word without using a larger type or carry
// propagation so long as the values won't overflow a uint32. This
// could obviously be done in a loop, but the unrolled version is
// faster.
ui := uint32(val)
f.n[0] *= ui
f.n[1] *= ui
f.n[2] *= ui
f.n[3] *= ui
f.n[4] *= ui
f.n[5] *= ui
f.n[6] *= ui
f.n[7] *= ui
f.n[8] *= ui
f.n[9] *= ui
return f
}
// Mul multiplies the passed value to the existing field value and stores the
// result in f in constant time. Note that this function can overflow if
// multiplying any of the individual words exceeds a max uint32. In practice,
// this means the magnitude of either value involved in the multiplication must
// be a max of 8.
//
// The field value is returned to support chaining. This enables syntax like:
// f.Mul(f2).AddInt(1) so that f = (f * f2) + 1.
//
// Preconditions:
// - Both field values MUST have a max magnitude of 8
// Output Normalized: No
// Output Max Magnitude: 1
func (f *FieldVal) Mul(val *FieldVal) *FieldVal {
return f.Mul2(f, val)
}
// Mul2 multiplies the passed two field values together and stores the result in
// f in constant time. Note that this function can overflow if multiplying any
// of the individual words exceeds a max uint32. In practice, this means the
// magnitude of either value involved in the multiplication must be a max of 8.
//
// The field value is returned to support chaining. This enables syntax like:
// f3.Mul2(f, f2).AddInt(1) so that f3 = (f * f2) + 1.
//
// Preconditions:
// - Both input field values MUST have a max magnitude of 8
// Output Normalized: No
// Output Max Magnitude: 1
func (f *FieldVal) Mul2(val *FieldVal, val2 *FieldVal) *FieldVal {
// This could be done with a couple of for loops and an array to store
// the intermediate terms, but this unrolled version is significantly
// faster.
// Terms for 2^(fieldBase*0).
m := uint64(val.n[0]) * uint64(val2.n[0])
t0 := m & fieldBaseMask
// Terms for 2^(fieldBase*1).
m = (m >> fieldBase) +
uint64(val.n[0])*uint64(val2.n[1]) +
uint64(val.n[1])*uint64(val2.n[0])
t1 := m & fieldBaseMask
// Terms for 2^(fieldBase*2).
m = (m >> fieldBase) +
uint64(val.n[0])*uint64(val2.n[2]) +
uint64(val.n[1])*uint64(val2.n[1]) +
uint64(val.n[2])*uint64(val2.n[0])
t2 := m & fieldBaseMask
// Terms for 2^(fieldBase*3).
m = (m >> fieldBase) +
uint64(val.n[0])*uint64(val2.n[3]) +
uint64(val.n[1])*uint64(val2.n[2]) +
uint64(val.n[2])*uint64(val2.n[1]) +
uint64(val.n[3])*uint64(val2.n[0])
t3 := m & fieldBaseMask
// Terms for 2^(fieldBase*4).
m = (m >> fieldBase) +
uint64(val.n[0])*uint64(val2.n[4]) +
uint64(val.n[1])*uint64(val2.n[3]) +
uint64(val.n[2])*uint64(val2.n[2]) +
uint64(val.n[3])*uint64(val2.n[1]) +
uint64(val.n[4])*uint64(val2.n[0])
t4 := m & fieldBaseMask
// Terms for 2^(fieldBase*5).
m = (m >> fieldBase) +
uint64(val.n[0])*uint64(val2.n[5]) +
uint64(val.n[1])*uint64(val2.n[4]) +
uint64(val.n[2])*uint64(val2.n[3]) +
uint64(val.n[3])*uint64(val2.n[2]) +
uint64(val.n[4])*uint64(val2.n[1]) +
uint64(val.n[5])*uint64(val2.n[0])
t5 := m & fieldBaseMask
// Terms for 2^(fieldBase*6).
m = (m >> fieldBase) +
uint64(val.n[0])*uint64(val2.n[6]) +
uint64(val.n[1])*uint64(val2.n[5]) +
uint64(val.n[2])*uint64(val2.n[4]) +
uint64(val.n[3])*uint64(val2.n[3]) +
uint64(val.n[4])*uint64(val2.n[2]) +
uint64(val.n[5])*uint64(val2.n[1]) +
uint64(val.n[6])*uint64(val2.n[0])
t6 := m & fieldBaseMask
// Terms for 2^(fieldBase*7).
m = (m >> fieldBase) +
uint64(val.n[0])*uint64(val2.n[7]) +
uint64(val.n[1])*uint64(val2.n[6]) +
uint64(val.n[2])*uint64(val2.n[5]) +
uint64(val.n[3])*uint64(val2.n[4]) +
uint64(val.n[4])*uint64(val2.n[3]) +
uint64(val.n[5])*uint64(val2.n[2]) +
uint64(val.n[6])*uint64(val2.n[1]) +
uint64(val.n[7])*uint64(val2.n[0])
t7 := m & fieldBaseMask
// Terms for 2^(fieldBase*8).
m = (m >> fieldBase) +
uint64(val.n[0])*uint64(val2.n[8]) +
uint64(val.n[1])*uint64(val2.n[7]) +
uint64(val.n[2])*uint64(val2.n[6]) +
uint64(val.n[3])*uint64(val2.n[5]) +
uint64(val.n[4])*uint64(val2.n[4]) +
uint64(val.n[5])*uint64(val2.n[3]) +
uint64(val.n[6])*uint64(val2.n[2]) +
uint64(val.n[7])*uint64(val2.n[1]) +
uint64(val.n[8])*uint64(val2.n[0])
t8 := m & fieldBaseMask
// Terms for 2^(fieldBase*9).
m = (m >> fieldBase) +
uint64(val.n[0])*uint64(val2.n[9]) +
uint64(val.n[1])*uint64(val2.n[8]) +
uint64(val.n[2])*uint64(val2.n[7]) +
uint64(val.n[3])*uint64(val2.n[6]) +
uint64(val.n[4])*uint64(val2.n[5]) +
uint64(val.n[5])*uint64(val2.n[4]) +
uint64(val.n[6])*uint64(val2.n[3]) +
uint64(val.n[7])*uint64(val2.n[2]) +
uint64(val.n[8])*uint64(val2.n[1]) +
uint64(val.n[9])*uint64(val2.n[0])
t9 := m & fieldBaseMask
// Terms for 2^(fieldBase*10).
m = (m >> fieldBase) +
uint64(val.n[1])*uint64(val2.n[9]) +
uint64(val.n[2])*uint64(val2.n[8]) +
uint64(val.n[3])*uint64(val2.n[7]) +
uint64(val.n[4])*uint64(val2.n[6]) +
uint64(val.n[5])*uint64(val2.n[5]) +
uint64(val.n[6])*uint64(val2.n[4]) +
uint64(val.n[7])*uint64(val2.n[3]) +
uint64(val.n[8])*uint64(val2.n[2]) +
uint64(val.n[9])*uint64(val2.n[1])
t10 := m & fieldBaseMask
// Terms for 2^(fieldBase*11).
m = (m >> fieldBase) +
uint64(val.n[2])*uint64(val2.n[9]) +
uint64(val.n[3])*uint64(val2.n[8]) +
uint64(val.n[4])*uint64(val2.n[7]) +
uint64(val.n[5])*uint64(val2.n[6]) +
uint64(val.n[6])*uint64(val2.n[5]) +
uint64(val.n[7])*uint64(val2.n[4]) +
uint64(val.n[8])*uint64(val2.n[3]) +
uint64(val.n[9])*uint64(val2.n[2])
t11 := m & fieldBaseMask
// Terms for 2^(fieldBase*12).
m = (m >> fieldBase) +
uint64(val.n[3])*uint64(val2.n[9]) +
uint64(val.n[4])*uint64(val2.n[8]) +
uint64(val.n[5])*uint64(val2.n[7]) +
uint64(val.n[6])*uint64(val2.n[6]) +
uint64(val.n[7])*uint64(val2.n[5]) +
uint64(val.n[8])*uint64(val2.n[4]) +
uint64(val.n[9])*uint64(val2.n[3])
t12 := m & fieldBaseMask
// Terms for 2^(fieldBase*13).
m = (m >> fieldBase) +
uint64(val.n[4])*uint64(val2.n[9]) +
uint64(val.n[5])*uint64(val2.n[8]) +
uint64(val.n[6])*uint64(val2.n[7]) +
uint64(val.n[7])*uint64(val2.n[6]) +
uint64(val.n[8])*uint64(val2.n[5]) +
uint64(val.n[9])*uint64(val2.n[4])
t13 := m & fieldBaseMask
// Terms for 2^(fieldBase*14).
m = (m >> fieldBase) +
uint64(val.n[5])*uint64(val2.n[9]) +
uint64(val.n[6])*uint64(val2.n[8]) +
uint64(val.n[7])*uint64(val2.n[7]) +
uint64(val.n[8])*uint64(val2.n[6]) +
uint64(val.n[9])*uint64(val2.n[5])
t14 := m & fieldBaseMask
// Terms for 2^(fieldBase*15).
m = (m >> fieldBase) +
uint64(val.n[6])*uint64(val2.n[9]) +
uint64(val.n[7])*uint64(val2.n[8]) +
uint64(val.n[8])*uint64(val2.n[7]) +
uint64(val.n[9])*uint64(val2.n[6])
t15 := m & fieldBaseMask
// Terms for 2^(fieldBase*16).
m = (m >> fieldBase) +
uint64(val.n[7])*uint64(val2.n[9]) +
uint64(val.n[8])*uint64(val2.n[8]) +
uint64(val.n[9])*uint64(val2.n[7])
t16 := m & fieldBaseMask