1 package secp256k1
2 3 // Scalar arithmetic modulo the curve order n.
4 // n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
5 6 // scalarAdd returns (a + b) mod n.
7 func scalarAdd(a, b Fe) Fe {
8 var r Fe
9 var carry uint64
10 r[0], carry = addWithCarry(a[0], b[0], 0)
11 r[1], carry = addWithCarry(a[1], b[1], carry)
12 r[2], carry = addWithCarry(a[2], b[2], carry)
13 r[3], carry = addWithCarry(a[3], b[3], carry)
14 15 if carry != 0 || feCmp(r, curveN) >= 0 {
16 var borrow uint64
17 r[0], borrow = subWithBorrow(r[0], curveN[0], 0)
18 r[1], borrow = subWithBorrow(r[1], curveN[1], borrow)
19 r[2], borrow = subWithBorrow(r[2], curveN[2], borrow)
20 r[3], _ = subWithBorrow(r[3], curveN[3], borrow)
21 }
22 return r
23 }
24 25 // scalarMul returns (a * b) mod n.
26 func scalarMul(a, b Fe) Fe {
27 var t [8]uint64
28 for i := 0; i < 4; i++ {
29 var carry uint64
30 for j := 0; j < 4; j++ {
31 hi, lo := mul64(a[i], b[j])
32 lo, c1 := addWithCarry(lo, t[i+j], 0)
33 hi += c1
34 lo, c2 := addWithCarry(lo, carry, 0)
35 hi += c2
36 t[i+j] = lo
37 carry = hi
38 }
39 t[i+4] = carry
40 }
41 return scalarReduceFull(t)
42 }
43 44 // scalarNeg returns -a mod n.
45 func scalarNeg(a Fe) Fe {
46 if a == feZero {
47 return feZero
48 }
49 return scalarSub(curveN, a)
50 }
51 52 // scalarSub returns (a - b) mod n.
53 func scalarSub(a, b Fe) Fe {
54 var r Fe
55 var borrow uint64
56 r[0], borrow = subWithBorrow(a[0], b[0], 0)
57 r[1], borrow = subWithBorrow(r[1]+a[1], b[1], borrow)
58 r[2], borrow = subWithBorrow(r[2]+a[2], b[2], borrow)
59 r[3], borrow = subWithBorrow(r[3]+a[3], b[3], borrow)
60 if borrow != 0 {
61 var c uint64
62 r[0], c = addWithCarry(r[0], curveN[0], 0)
63 r[1], c = addWithCarry(r[1], curveN[1], c)
64 r[2], c = addWithCarry(r[2], curveN[2], c)
65 r[3], _ = addWithCarry(r[3], curveN[3], c)
66 }
67 return r
68 }
69 70 // scalarInv returns a^(-1) mod n via Fermat: a^(n-2) mod n.
71 func scalarInv(a Fe) Fe {
72 nm2 := Fe{
73 0xBFD25E8CD036413F,
74 0xBAAEDCE6AF48A03B,
75 0xFFFFFFFFFFFFFFFE,
76 0xFFFFFFFFFFFFFFFF,
77 }
78 return scalarExp(a, nm2)
79 }
80 81 func scalarExp(base, exp Fe) Fe {
82 result := feOne
83 b := base
84 for i := 0; i < 4; i++ {
85 w := exp[i]
86 for bit := 0; bit < 64; bit++ {
87 if w&1 == 1 {
88 result = scalarMul(result, b)
89 }
90 b = scalarMul(b, b)
91 w >>= 1
92 }
93 }
94 return result
95 }
96 97 // scalarReduceFull reduces a 512-bit number modulo n.
98 // Uses iterative folding: 2^256 ≡ cc (mod n) where cc = 2^256 - n (129 bits).
99 // Each fold reduces the high part's bit count by ~127 bits, so two rounds
100 // plus a final subtraction are always sufficient.
101 func scalarReduceFull(t [8]uint64) Fe {
102 // cc = 2^256 - n (little-endian, 3 non-zero limbs, 129 bits)
103 cc := [3]uint64{
104 0x402DA1732FC9BEBF,
105 0x4551231950B75FC4,
106 0x0000000000000001,
107 }
108 109 // Round 1: fold t[4..7] into t[0..3] via high*cc + low.
110 r := scalarFoldHigh(t, cc)
111 112 // Round 2: after round 1, r[4..7] has at most ~130 bits.
113 // One more fold drives it to zero (or a tiny residual in r[4]).
114 r = scalarFoldHigh(r, cc)
115 116 // At this point r[4..7] should be zero. If r[4] has a residual
117 // from carry propagation, fold it one more time (single limb × cc).
118 var res Fe
119 res[0] = r[0]
120 res[1] = r[1]
121 res[2] = r[2]
122 res[3] = r[3]
123 124 if r[4] != 0 {
125 var carry uint64
126 hi, lo := mul64(r[4], cc[0])
127 lo, k := addWithCarry(lo, res[0], 0)
128 hi += k
129 res[0] = lo
130 carry = hi
131 132 hi, lo = mul64(r[4], cc[1])
133 lo, k = addWithCarry(lo, res[1], 0)
134 hi += k
135 lo, k = addWithCarry(lo, carry, 0)
136 hi += k
137 res[1] = lo
138 carry = hi
139 140 hi, lo = mul64(r[4], cc[2])
141 lo, k = addWithCarry(lo, res[2], 0)
142 hi += k
143 lo, k = addWithCarry(lo, carry, 0)
144 hi += k
145 res[2] = lo
146 carry = hi
147 148 res[3], _ = addWithCarry(res[3], carry, 0)
149 }
150 151 // Final: subtract n while result >= n.
152 for feCmp(res, curveN) >= 0 {
153 var borrow uint64
154 res[0], borrow = subWithBorrow(res[0], curveN[0], 0)
155 res[1], borrow = subWithBorrow(res[1], curveN[1], borrow)
156 res[2], borrow = subWithBorrow(res[2], curveN[2], borrow)
157 res[3], _ = subWithBorrow(res[3], curveN[3], borrow)
158 }
159 160 return res
161 }
162 163 // scalarFoldHigh folds the upper 4 limbs of an 8-limb number down into
164 // the lower 4 limbs using the identity 2^256 ≡ cc (mod n).
165 func scalarFoldHigh(t [8]uint64, cc [3]uint64) [8]uint64 {
166 var r [8]uint64
167 r[0] = t[0]
168 r[1] = t[1]
169 r[2] = t[2]
170 r[3] = t[3]
171 172 // Accumulate t[i+4] * cc into r at offset i.
173 for i := 0; i < 4; i++ {
174 if t[i+4] == 0 {
175 continue
176 }
177 var carry uint64
178 for j := 0; j < 3; j++ {
179 hi, lo := mul64(t[i+4], cc[j])
180 lo, k := addWithCarry(lo, r[i+j], 0)
181 hi += k
182 lo, k = addWithCarry(lo, carry, 0)
183 hi += k
184 r[i+j] = lo
185 carry = hi
186 }
187 // Propagate remaining carry upward.
188 for k := i + 3; carry != 0 && k < 8; k++ {
189 r[k], carry = addWithCarry(r[k], carry, 0)
190 }
191 }
192 193 return r
194 }
195 196 // scalarIsZero returns true if s == 0.
197 func scalarIsZero(s Fe) bool {
198 return s == feZero
199 }
200 201 // scalarFromBytes reads a 32-byte big-endian scalar.
202 func scalarFromBytes(b []byte) Fe {
203 return feFromBytes(b) // Same format, different modulus.
204 }
205