torus.go raw
1 package gnarl
2
3 // Matrix types for the Gnarl signature scheme using Montgomery field elements.
4 //
5 // Operates over the Gnarl prime P
6 // (216 bits). The non-split torus has order N = P+1 = 6Q, and the Schnorr
7 // subgroup has prime order Q = (P+1)/6.
8 //
9 // mat4 — full 2×2 matrix [[A, B], [C, D]] over Z_P.
10 // tmat — torus-constrained 2×2 matrix where B = C. Stores only (A, B, D).
11
12 import "math/big"
13
14 // mat4 is a full 2×2 matrix over Z_P in Montgomery form.
15 type mat4 struct {
16 a, b, c, d fe
17 }
18
19 // tmat is a torus-constrained 2×2 matrix where B = C, in Montgomery form.
20 type tmat struct {
21 a, b, d fe
22 }
23
24 // m4Eye returns the identity matrix.
25 func m4Eye() mat4 {
26 return mat4{a: feOne, b: feZero, c: feZero, d: feOne}
27 }
28
29 // tmEye returns the torus identity matrix.
30 func tmEye() tmat {
31 return tmat{a: feOne, b: feZero, d: feOne}
32 }
33
34 // m4Mul computes r = x * y for full 2×2 matrices. 8 field multiplications.
35 func m4Mul(r, x, y *mat4) {
36 var ra, rb, rc, rd, t1, t2 fe
37 montMul(&t1, &x.a, &y.a)
38 montMul(&t2, &x.b, &y.c)
39 feAdd(&ra, &t1, &t2)
40
41 montMul(&t1, &x.a, &y.b)
42 montMul(&t2, &x.b, &y.d)
43 feAdd(&rb, &t1, &t2)
44
45 montMul(&t1, &x.c, &y.a)
46 montMul(&t2, &x.d, &y.c)
47 feAdd(&rc, &t1, &t2)
48
49 montMul(&t1, &x.c, &y.b)
50 montMul(&t2, &x.d, &y.d)
51 feAdd(&rd, &t1, &t2)
52
53 r.a = ra
54 r.b = rb
55 r.c = rc
56 r.d = rd
57 }
58
59 // tmMul computes r = x * y for torus matrices (B=C constraint preserved).
60 // 5 field multiplications.
61 func tmMul(r, x, y *tmat) {
62 var aa, bb, dd, ab, bd, ra, rb, rd fe
63
64 montMul(&aa, &x.a, &y.a)
65 montMul(&bb, &x.b, &y.b)
66 montMul(&dd, &x.d, &y.d)
67 montMul(&ab, &x.a, &y.b)
68 montMul(&bd, &x.b, &y.d)
69
70 feAdd(&ra, &aa, &bb)
71 feAdd(&rb, &ab, &bd)
72 feAdd(&rd, &bb, &dd)
73
74 r.a = ra
75 r.b = rb
76 r.d = rd
77 }
78
79 // tmSquare computes r = x^2 for a torus matrix.
80 func tmSquare(r, x *tmat) {
81 var a2, b2, d2, apd, ra, rb, rd fe
82
83 montSquare(&a2, &x.a)
84 montSquare(&b2, &x.b)
85 montSquare(&d2, &x.d)
86 feAdd(&apd, &x.a, &x.d)
87 montMul(&rb, &x.b, &apd)
88
89 feAdd(&ra, &a2, &b2)
90 feAdd(&rd, &b2, &d2)
91
92 r.a = ra
93 r.b = rb
94 r.d = rd
95 }
96
97 // tmIsIdentity returns true if m is the identity torus matrix.
98 func tmIsIdentity(m *tmat) bool {
99 return feEqual(&m.a, &feOne) == 1 &&
100 feIsZero(&m.b) == 1 &&
101 feEqual(&m.d, &feOne) == 1
102 }
103
104 // tmEqual returns true if a and b represent the same torus matrix.
105 func tmEqual(a, b *tmat) bool {
106 return feEqual(&a.a, &b.a) == 1 &&
107 feEqual(&a.b, &b.b) == 1 &&
108 feEqual(&a.d, &b.d) == 1
109 }
110
111 // tmInv computes r = m^{-1} for a torus matrix.
112 func tmInv(r, m *tmat) {
113 var ra, rb, rd fe
114 feSet(&ra, &m.d)
115 feNeg(&rb, &m.b)
116 feSet(&rd, &m.a)
117 r.a = ra
118 r.b = rb
119 r.d = rd
120 }
121
122 // tmToMat4 converts a torus matrix to a full matrix (setting C = B).
123 func tmToMat4(r *mat4, m *tmat) {
124 feSet(&r.a, &m.a)
125 feSet(&r.b, &m.b)
126 feSet(&r.c, &m.b)
127 feSet(&r.d, &m.d)
128 }
129
130 // tmFromMat4 converts a full matrix to a torus matrix (assumes B == C).
131 func tmFromMat4(r *tmat, m *mat4) {
132 feSet(&r.a, &m.a)
133 feSet(&r.b, &m.b)
134 feSet(&r.d, &m.d)
135 }
136
137 // m4Det computes det(m) = a*d - b*c in Montgomery form.
138 func m4Det(r *fe, m *mat4) {
139 var ad, bc fe
140 montMul(&ad, &m.a, &m.d)
141 montMul(&bc, &m.b, &m.c)
142 feSub(r, &ad, &bc)
143 }
144
145 // m4Trace computes trace(m) = a + d in Montgomery form.
146 func m4Trace(r *fe, m *mat4) {
147 feAdd(r, &m.a, &m.d)
148 }
149
150 // m4Equal returns true if two full matrices are equal.
151 func m4Equal(a, b *mat4) bool {
152 return feEqual(&a.a, &b.a) == 1 &&
153 feEqual(&a.b, &b.b) == 1 &&
154 feEqual(&a.c, &b.c) == 1 &&
155 feEqual(&a.d, &b.d) == 1
156 }
157
158 // m4IsIdentity returns true if m is the identity matrix.
159 func m4IsIdentity(m *mat4) bool {
160 return feEqual(&m.a, &feOne) == 1 &&
161 feIsZero(&m.b) == 1 &&
162 feIsZero(&m.c) == 1 &&
163 feEqual(&m.d, &feOne) == 1
164 }
165
166 // m4Inv computes the inverse of an SL(2) matrix: [[d, -b], [-c, a]].
167 func m4Inv(r, m *mat4) {
168 var ra, rb, rc, rd fe
169 feSet(&ra, &m.d)
170 feNeg(&rb, &m.b)
171 feNeg(&rc, &m.c)
172 feSet(&rd, &m.a)
173 r.a = ra
174 r.b = rb
175 r.c = rc
176 r.d = rd
177 }
178
179 // m4FromSmall creates a mat4 from small integer values.
180 func m4FromSmall(a, b, c, d int64) mat4 {
181 var r mat4
182 feFromSmall(&r.a, a)
183 feFromSmall(&r.b, b)
184 feFromSmall(&r.c, c)
185 feFromSmall(&r.d, d)
186 return r
187 }
188
189 // tmToBytes serializes a torus matrix as 81 bytes (A, B, D as 3×27 bytes big-endian).
190 func tmToBytes(buf []byte, m *tmat) {
191 feToBytes27(buf[0:27], &m.a)
192 feToBytes27(buf[27:54], &m.b)
193 feToBytes27(buf[54:81], &m.d)
194 }
195
196 // tmFromBytes deserializes a torus matrix from 81 bytes.
197 func tmFromBytes(m *tmat, buf []byte) bool {
198 if len(buf) < 81 {
199 return false
200 }
201 if !feFromBytes27(&m.a, buf[0:27]) {
202 return false
203 }
204 if !feFromBytes27(&m.b, buf[27:54]) {
205 return false
206 }
207 if !feFromBytes27(&m.d, buf[54:81]) {
208 return false
209 }
210 return true
211 }
212
213 // m4PowBig computes r = base^exp for a full matrix with an arbitrary big.Int exponent.
214 func m4PowBig(r *mat4, base *mat4, exp *big.Int) {
215 *r = m4Eye()
216 var b mat4
217 b = *base
218
219 for i := 0; i < exp.BitLen(); i++ {
220 if exp.Bit(i) == 1 {
221 m4Mul(r, r, &b)
222 }
223 m4Mul(&b, &b, &b)
224 }
225 }
226
227 // bigToFe converts a big.Int to a Montgomery field element.
228 func bigToFe(r *fe, v *big.Int) {
229 pBig := new(big.Int)
230 var pbuf [27]byte
231 feToBytes27(pbuf[:], &feZero)
232 // Actually we need P as big.Int. Reconstruct from pLimbs.
233 pBig.SetUint64(pLimbs[3])
234 pBig.Lsh(pBig, 64)
235 pBig.Or(pBig, new(big.Int).SetUint64(pLimbs[2]))
236 pBig.Lsh(pBig, 64)
237 pBig.Or(pBig, new(big.Int).SetUint64(pLimbs[1]))
238 pBig.Lsh(pBig, 64)
239 pBig.Or(pBig, new(big.Int).SetUint64(pLimbs[0]))
240
241 norm := new(big.Int).Mod(v, pBig)
242 var buf [27]byte
243 normBytes := norm.Bytes()
244 copy(buf[27-len(normBytes):], normBytes)
245 // Decode big-endian into little-endian limbs.
246 r[3] = uint64(buf[0])<<16 | uint64(buf[1])<<8 | uint64(buf[2])
247 r[2] = uint64(buf[3])<<56 | uint64(buf[4])<<48 | uint64(buf[5])<<40 | uint64(buf[6])<<32 |
248 uint64(buf[7])<<24 | uint64(buf[8])<<16 | uint64(buf[9])<<8 | uint64(buf[10])
249 r[1] = uint64(buf[11])<<56 | uint64(buf[12])<<48 | uint64(buf[13])<<40 | uint64(buf[14])<<32 |
250 uint64(buf[15])<<24 | uint64(buf[16])<<16 | uint64(buf[17])<<8 | uint64(buf[18])
251 r[0] = uint64(buf[19])<<56 | uint64(buf[20])<<48 | uint64(buf[21])<<40 | uint64(buf[22])<<32 |
252 uint64(buf[23])<<24 | uint64(buf[24])<<16 | uint64(buf[25])<<8 | uint64(buf[26])
253 feToMont(r, r)
254 }
255
256 // feToBig converts a Montgomery field element to a big.Int.
257 func feToBig(a *fe) *big.Int {
258 var buf [27]byte
259 feToBytes27(buf[:], a)
260 return new(big.Int).SetBytes(buf[:])
261 }
262
263 // bigToScalar converts a big.Int to a scalar mod Q.
264 func bigToScalar(r *scalar, v *big.Int) {
265 norm := new(big.Int).Mod(v, qBig)
266 var buf [27]byte
267 normBytes := norm.Bytes()
268 copy(buf[27-len(normBytes):], normBytes)
269 scFromBytes27(r, buf[:])
270 }
271
272 // scalarToBig converts a scalar to a big.Int.
273 func scalarToBig(s *scalar) *big.Int {
274 var buf [27]byte
275 scToBytes27(buf[:], s)
276 return new(big.Int).SetBytes(buf[:])
277 }
278