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