scalar.go raw
1 package gnarl
2
3 // Scalar arithmetic modulo Q (the prime order of the Schnorr subgroup).
4 //
5 // Q = (P+1)/6 is a ~213-bit prime. Scalars are used for private keys,
6 // nonces, challenges, and responses in the Schnorr protocol.
7 //
8 // N = P + 1 = 6Q. The full non-split torus has order N, and the
9 // Schnorr subgroup has prime order Q.
10 //
11 // Representation: 4×uint64 little-endian limbs, reduced to [0, Q).
12 // Like the Cayley scheme, scalars are NOT in Montgomery form.
13
14 import (
15 "crypto/rand"
16 "math/big"
17 "math/bits"
18 )
19
20 // scalar is a 256-bit value mod Q in 4 little-endian uint64 limbs.
21 type scalar [4]uint64
22
23 // Q limbs (little-endian). Q = (P+1)/6.
24 // Q hex = 0x18e5f11e7959f44807ba64d85a69a223c0776edda9942fad452629
25 // Q bits = 213
26 var qLimbs = scalar{
27 0xdda9942fad452629,
28 0xd85a69a223c0776e,
29 0x1e7959f44807ba64,
30 0x000000000018e5f1,
31 }
32
33 // scZero is the zero scalar.
34 var scZero scalar
35
36 // scOneVal is the scalar 1.
37 var scOneVal = scalar{1, 0, 0, 0}
38
39 // scIsZero returns true if s == 0.
40 func scIsZero(s *scalar) bool {
41 return (s[0] | s[1] | s[2] | s[3]) == 0
42 }
43
44 // scGte returns true if a >= b as unsigned 256-bit integers.
45 func scGte(a, b *scalar) bool {
46 _, borrow := bits.Sub64(a[0], b[0], 0)
47 _, borrow = bits.Sub64(a[1], b[1], borrow)
48 _, borrow = bits.Sub64(a[2], b[2], borrow)
49 _, borrow = bits.Sub64(a[3], b[3], borrow)
50 return borrow == 0
51 }
52
53 // scReduce reduces s to [0, Q).
54 // Q is ~213 bits but values can be up to 256 bits (4 full limbs),
55 // so we use big.Int for the reduction rather than repeated subtraction.
56 func scReduce(s *scalar) {
57 if !scGte(s, &qLimbs) {
58 return
59 }
60 // Convert to big.Int, reduce, convert back.
61 val := new(big.Int)
62 val.SetUint64(s[3])
63 val.Lsh(val, 64)
64 val.Or(val, new(big.Int).SetUint64(s[2]))
65 val.Lsh(val, 64)
66 val.Or(val, new(big.Int).SetUint64(s[1]))
67 val.Lsh(val, 64)
68 val.Or(val, new(big.Int).SetUint64(s[0]))
69 val.Mod(val, qBig)
70
71 mask64 := new(big.Int).SetUint64(0xFFFFFFFFFFFFFFFF)
72 s[0] = new(big.Int).And(val, mask64).Uint64()
73 val.Rsh(val, 64)
74 s[1] = new(big.Int).And(val, mask64).Uint64()
75 val.Rsh(val, 64)
76 s[2] = new(big.Int).And(val, mask64).Uint64()
77 val.Rsh(val, 64)
78 s[3] = val.Uint64()
79 }
80
81 // scAdd computes r = a + b mod Q.
82 func scAdd(r, a, b *scalar) {
83 var carry uint64
84 r[0], carry = bits.Add64(a[0], b[0], 0)
85 r[1], carry = bits.Add64(a[1], b[1], carry)
86 r[2], carry = bits.Add64(a[2], b[2], carry)
87 r[3], carry = bits.Add64(a[3], b[3], carry)
88
89 d0, borrow := bits.Sub64(r[0], qLimbs[0], 0)
90 d1, borrow := bits.Sub64(r[1], qLimbs[1], borrow)
91 d2, borrow := bits.Sub64(r[2], qLimbs[2], borrow)
92 d3, borrow := bits.Sub64(r[3], qLimbs[3], borrow)
93
94 underflow := borrow &^ carry
95 mask := uint64(0) - underflow
96 r[0] = (r[0] & mask) | (d0 & ^mask)
97 r[1] = (r[1] & mask) | (d1 & ^mask)
98 r[2] = (r[2] & mask) | (d2 & ^mask)
99 r[3] = (r[3] & mask) | (d3 & ^mask)
100 }
101
102 // scSub computes r = a - b mod Q.
103 func scSub(r, a, b *scalar) {
104 var borrow uint64
105 r[0], borrow = bits.Sub64(a[0], b[0], 0)
106 r[1], borrow = bits.Sub64(a[1], b[1], borrow)
107 r[2], borrow = bits.Sub64(a[2], b[2], borrow)
108 r[3], borrow = bits.Sub64(a[3], b[3], borrow)
109
110 mask := uint64(0) - borrow
111 var carry uint64
112 r[0], carry = bits.Add64(r[0], qLimbs[0]&mask, 0)
113 r[1], carry = bits.Add64(r[1], qLimbs[1]&mask, carry)
114 r[2], carry = bits.Add64(r[2], qLimbs[2]&mask, carry)
115 r[3], _ = bits.Add64(r[3], qLimbs[3]&mask, carry)
116 }
117
118 // scNeg computes r = -a mod Q.
119 func scNeg(r, a *scalar) {
120 scSub(r, &scZero, a)
121 }
122
123 // scMul computes r = a * b mod Q.
124 // Uses big.Int for the full 512-bit product and reduction (scalar muls are infrequent).
125 func scMul(r, a, b *scalar) {
126 var abuf, bbuf [27]byte
127 scToBytes27(abuf[:], a)
128 scToBytes27(bbuf[:], b)
129 aBig := new(big.Int).SetBytes(abuf[:])
130 bBig := new(big.Int).SetBytes(bbuf[:])
131 prod := new(big.Int).Mul(aBig, bBig)
132 prod.Mod(prod, qBig)
133
134 var rbuf [27]byte
135 prodBytes := prod.Bytes()
136 copy(rbuf[27-len(prodBytes):], prodBytes)
137 scFromBytes27(r, rbuf[:])
138 }
139
140 // scFromBytes27 sets s from a 27-byte big-endian encoding.
141 // The value is reduced mod Q.
142 func scFromBytes27(s *scalar, b []byte) {
143 if len(b) < 27 {
144 *s = scZero
145 return
146 }
147 // 27 bytes = 216 bits. Same layout as feFromBytes27:
148 // b[0..2] → low 24 bits of limb[3] (bits 192..215)
149 // b[3..10] → limb[2] (bits 128..191)
150 // b[11..18] → limb[1] (bits 64..127)
151 // b[19..26] → limb[0] (bits 0..63)
152 s[3] = uint64(b[0])<<16 | uint64(b[1])<<8 | uint64(b[2])
153 s[2] = uint64(b[3])<<56 | uint64(b[4])<<48 | uint64(b[5])<<40 | uint64(b[6])<<32 |
154 uint64(b[7])<<24 | uint64(b[8])<<16 | uint64(b[9])<<8 | uint64(b[10])
155 s[1] = uint64(b[11])<<56 | uint64(b[12])<<48 | uint64(b[13])<<40 | uint64(b[14])<<32 |
156 uint64(b[15])<<24 | uint64(b[16])<<16 | uint64(b[17])<<8 | uint64(b[18])
157 s[0] = uint64(b[19])<<56 | uint64(b[20])<<48 | uint64(b[21])<<40 | uint64(b[22])<<32 |
158 uint64(b[23])<<24 | uint64(b[24])<<16 | uint64(b[25])<<8 | uint64(b[26])
159 scReduce(s)
160 }
161
162 // scToBytes27 writes s to a 27-byte big-endian buffer.
163 func scToBytes27(b []byte, s *scalar) {
164 // limb[3] low 24 bits → b[0..2]
165 b[0] = byte(s[3] >> 16)
166 b[1] = byte(s[3] >> 8)
167 b[2] = byte(s[3])
168 // limb[2] → b[3..10]
169 b[3] = byte(s[2] >> 56)
170 b[4] = byte(s[2] >> 48)
171 b[5] = byte(s[2] >> 40)
172 b[6] = byte(s[2] >> 32)
173 b[7] = byte(s[2] >> 24)
174 b[8] = byte(s[2] >> 16)
175 b[9] = byte(s[2] >> 8)
176 b[10] = byte(s[2])
177 // limb[1] → b[11..18]
178 b[11] = byte(s[1] >> 56)
179 b[12] = byte(s[1] >> 48)
180 b[13] = byte(s[1] >> 40)
181 b[14] = byte(s[1] >> 32)
182 b[15] = byte(s[1] >> 24)
183 b[16] = byte(s[1] >> 16)
184 b[17] = byte(s[1] >> 8)
185 b[18] = byte(s[1])
186 // limb[0] → b[19..26]
187 b[19] = byte(s[0] >> 56)
188 b[20] = byte(s[0] >> 48)
189 b[21] = byte(s[0] >> 40)
190 b[22] = byte(s[0] >> 32)
191 b[23] = byte(s[0] >> 24)
192 b[24] = byte(s[0] >> 16)
193 b[25] = byte(s[0] >> 8)
194 b[26] = byte(s[0])
195 }
196
197 // scRandom generates a uniform random scalar in [1, Q).
198 func scRandom(s *scalar) error {
199 var buf [27]byte
200 for {
201 if _, err := rand.Read(buf[:]); err != nil {
202 return err
203 }
204 // Clear top 5 bits to ensure < 2^213 (Q is ~213 bits).
205 // Q top byte starts with 0x18 = 0001_1000, so clearing top 3 bits
206 // gives values < 2^213 which covers Q's range. We'll reduce mod Q anyway.
207 buf[0] &= 0x1F
208 scFromBytes27(s, buf[:])
209 if !scIsZero(s) {
210 return nil
211 }
212 }
213 }
214