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