gnarl.go raw
1 // Package gnarl implements Schnorr signatures over the non-split torus of
2 // SL(2, Z_P) for a 216-bit prime P.
3 //
4 // Uses a 216-bit prime giving 27-byte field elements and ~107-bit
5 // Pollard-rho security.
6 //
7 // Key sizes:
8 // - Secret key: 27 bytes (scalar mod Q)
9 // - Public key: 27 bytes (torus y-coordinate, y < P/3)
10 // - Signature: 54 bytes (27-byte challenge + 27-byte response)
11 //
12 // The challenge hash uses GnarlMid (27-byte trinary Hamadryad hash) from
13 // pkg/crypto, binding the signature to the trinary hash primitive.
14 //
15 // Prime P satisfies:
16 // - P ≡ 2 mod 3 (unique cube roots, eliminates trinary x-only ambiguity)
17 // - 5 is QNR mod P (non-split torus condition)
18 // - N = P+1 = 6Q where Q is a ~213-bit prime
19 //
20 // The constraint P ≡ 2 mod 3 means there are 3 cosets of the index-6
21 // subgroup of order Q inside the torus, so we canonicalize the public key
22 // y-coordinate to [0, P/3) by trying s, 2s, Q-s, etc.
23 package gnarl
24
25 import (
26 "crypto/sha256"
27 "errors"
28 "math/big"
29 )
30
31 // P, Q, N as big.Int for subgroup membership checks and scalar reduction.
32 var (
33 pBig *big.Int // field prime
34 qBig *big.Int // subgroup order (prime), Q = (P+1)/6
35 nBig *big.Int // torus order = P + 1 = 6Q
36 )
37
38 // SchnorrGen is the Schnorr signature generator on the non-split torus.
39 var schnorrGenTM tmat
40
41 func init() {
42 initPrime()
43 initGenerators()
44 }
45
46 func initPrime() {
47 seed := sha256.Sum256([]byte("gnarl-bethe-sl2-dendrite-v1"))
48
49 one := big.NewInt(1)
50 two := big.NewInt(2)
51 five := big.NewInt(5)
52 six := big.NewInt(6)
53
54 // Q starting point from seed.
55 // Take first 27 bytes, mask to 213 bits, set bit 212, make odd.
56 maxQ := new(big.Int).Div(new(big.Int).Lsh(one, 216), six)
57 q := new(big.Int).SetBytes(seed[:27])
58 qMask := new(big.Int).Sub(new(big.Int).Lsh(one, 213), one)
59 q.And(q, qMask)
60 q.SetBit(q, 212, 1)
61 if q.Bit(0) == 0 {
62 q.Add(q, one)
63 }
64
65 for {
66 if q.Cmp(maxQ) > 0 {
67 panic("gnarl: prime search exhausted")
68 }
69
70 // Q mod 5 must be 3 or 4 for P = 6Q-1 to have 5 as QNR.
71 qm5 := new(big.Int).Mod(q, five).Int64()
72 if qm5 == 3 || qm5 == 4 {
73 if q.ProbablyPrime(1) {
74 p := new(big.Int).Mul(six, q)
75 p.Sub(p, one)
76 if p.ProbablyPrime(1) {
77 if q.ProbablyPrime(20) && p.ProbablyPrime(20) {
78 // Verify 5 is QNR mod P.
79 pm1 := new(big.Int).Sub(p, one)
80 exp := new(big.Int).Rsh(pm1, 1)
81 euler := new(big.Int).Exp(five, exp, p)
82 if euler.Cmp(pm1) == 0 {
83 pBig = p
84 qBig = q
85 nBig = new(big.Int).Add(p, one)
86
87 // Verify the derived constants match our hardcoded values.
88 verifyConstants(p, q)
89 return
90 }
91 }
92 }
93 }
94 }
95 q.Add(q, two)
96 }
97 }
98
99 func verifyConstants(p, q *big.Int) {
100 // Verify pLimbs matches P.
101 pCheck := new(big.Int)
102 pCheck.SetUint64(pLimbs[3])
103 pCheck.Lsh(pCheck, 64)
104 pCheck.Or(pCheck, new(big.Int).SetUint64(pLimbs[2]))
105 pCheck.Lsh(pCheck, 64)
106 pCheck.Or(pCheck, new(big.Int).SetUint64(pLimbs[1]))
107 pCheck.Lsh(pCheck, 64)
108 pCheck.Or(pCheck, new(big.Int).SetUint64(pLimbs[0]))
109 if pCheck.Cmp(p) != 0 {
110 panic("gnarl: pLimbs mismatch")
111 }
112
113 // Verify qLimbs matches Q.
114 qCheck := new(big.Int)
115 qCheck.SetUint64(qLimbs[3])
116 qCheck.Lsh(qCheck, 64)
117 qCheck.Or(qCheck, new(big.Int).SetUint64(qLimbs[2]))
118 qCheck.Lsh(qCheck, 64)
119 qCheck.Or(qCheck, new(big.Int).SetUint64(qLimbs[1]))
120 qCheck.Lsh(qCheck, 64)
121 qCheck.Or(qCheck, new(big.Int).SetUint64(qLimbs[0]))
122 if qCheck.Cmp(q) != 0 {
123 panic("gnarl: qLimbs mismatch")
124 }
125 }
126
127 func initGenerators() {
128 // g0 = [[1,1],[0,1]], g1 = [[1,0],[1,1]]
129 g0 := m4FromSmall(1, 1, 0, 1)
130 g1 := m4FromSmall(1, 0, 1, 1)
131
132 // g0*g1 = [[2,1],[1,1]], which is on the torus (B = C = 1, symmetric).
133 // This element has order dividing N = P+1 = 6Q.
134 // To get an element of exact order Q, raise to the 6th power: G = (g0*g1)^6.
135 var g01 mat4
136 m4Mul(&g01, &g0, &g1)
137
138 // (g0*g1)^2
139 var g01sq mat4
140 m4Mul(&g01sq, &g01, &g01)
141
142 // (g0*g1)^3
143 var g01cu mat4
144 m4Mul(&g01cu, &g01sq, &g01)
145
146 // (g0*g1)^6
147 var gen mat4
148 m4Mul(&gen, &g01cu, &g01cu)
149
150 // Store as torus matrix (B should equal C for this generator).
151 tmFromMat4(&schnorrGenTM, &gen)
152
153 // Verify it's not the identity (it should have order Q).
154 if m4IsIdentity(&gen) {
155 panic("gnarl: generator is identity")
156 }
157
158 // Initialize precomputed exponentiation table.
159 initGenTable(&schnorrGenTM)
160 }
161
162 // PrivateKey is a scalar in [1, Q).
163 type PrivateKey struct {
164 s scalar
165 }
166
167 // PublicKey is a torus y-coordinate (27 bytes, y < P/3).
168 type PublicKey struct {
169 tm tmat
170 }
171
172 // Signature is (e, z) where e is the 27-byte challenge and z is the 27-byte response.
173 type Signature struct {
174 e [27]byte // challenge (GnarlMid hash output)
175 z scalar // response scalar
176 }
177
178 // GenerateKey creates a new keypair.
179 func GenerateKey() (*PrivateKey, *PublicKey, error) {
180 var s scalar
181 if err := scRandom(&s); err != nil {
182 return nil, nil, err
183 }
184
185 // PK = SchnorrGen^s
186 var pkTM tmat
187 tmFixedExp(&pkTM, &s)
188
189 // Canonicalize y: find an equivalent s such that y < P/3.
190 // The torus has order 6Q, and Q is the subgroup order.
191 // If y >= P/3, try negating (s -> Q - s gives inverse: y -> -y).
192 // If still >= P/3, try doubling (s -> 2s mod Q).
193 // With 3 cosets in [0,P) split into [0,P/3), [P/3,2P/3), [2P/3,P),
194 // exactly one of {s, Q-s, ...} will land in [0, P/3).
195 //
196 // Simpler approach: just try s and Q-s; one of them should give y < P/3
197 // with high probability for a uniformly random s. If neither works,
198 // we can multiply by a cube root of unity, but for P ≡ 2 mod 3 there
199 // are no non-trivial cube roots in Z_P, so -y is the only other option.
200 // Since P ≡ 2 mod 3, exactly (P-1)/3 values are in [0, P/3) and
201 // (P-1)/3 more in [P/3, 2P/3). So y and P-y together cover 2 of the
202 // 3 thirds. We need the third case: if y is in [2P/3, P), then P-y is
203 // in [0, P/3). So at most one negation suffices.
204 var bNorm fe
205 feFromMont(&bNorm, &pkTM.b)
206 if feIsGtThirdP(&bNorm) == 1 {
207 // Try negating: s -> Q - s, which inverts the matrix.
208 scNeg(&s, &s)
209 tmInv(&pkTM, &pkTM)
210
211 // Check again.
212 feFromMont(&bNorm, &pkTM.b)
213 if feIsGtThirdP(&bNorm) == 1 {
214 // y is in the middle third [P/3, 2P/3). P-y is in (P/3, 2P/3).
215 // Neither is < P/3. This shouldn't happen: if y is in [P/3, 2P/3)
216 // then P-y is in (P/3, 2P/3] which is also > P/3.
217 // But y = 0 maps to itself, and y in (P/3, 2P/3) maps to (P/3, 2P/3).
218 // So we accept the middle third as canonical with the constraint y < P/2.
219 feFromMont(&bNorm, &pkTM.b)
220 if feIsGtHalfP(&bNorm) == 1 {
221 scNeg(&s, &s)
222 tmInv(&pkTM, &pkTM)
223 }
224 }
225 }
226
227 sk := &PrivateKey{s: s}
228 pk := &PublicKey{tm: pkTM}
229 return sk, pk, nil
230 }
231
232 // PrivateKeyFromBytes deserializes a 27-byte secret key.
233 func PrivateKeyFromBytes(data []byte) (*PrivateKey, error) {
234 if len(data) < 27 {
235 return nil, errors.New("gnarl: short private key")
236 }
237 var s scalar
238 scFromBytes27(&s, data)
239 if scIsZero(&s) {
240 return nil, errors.New("gnarl: zero private key")
241 }
242 return &PrivateKey{s: s}, nil
243 }
244
245 // Bytes serializes the private key as 27 bytes.
246 func (sk *PrivateKey) Bytes() []byte {
247 buf := make([]byte, 27)
248 scToBytes27(buf, &sk.s)
249 return buf
250 }
251
252 // PublicKeyFromPrivate derives the public key from a private key.
253 func PublicKeyFromPrivate(sk *PrivateKey) *PublicKey {
254 var pkTM tmat
255 tmFixedExp(&pkTM, &sk.s)
256 return &PublicKey{tm: pkTM}
257 }
258
259 // YBytes serializes the public key as 27 bytes (y-coordinate only).
260 func (pk *PublicKey) YBytes() []byte {
261 buf := make([]byte, 27)
262 feToBytes27(buf, &pk.tm.b)
263 return buf
264 }
265
266 // FullBytes serializes the torus matrix (a, b, d) as 81 bytes.
267 func (pk *PublicKey) FullBytes() []byte {
268 buf := make([]byte, 81)
269 tmToBytes(buf, &pk.tm)
270 return buf
271 }
272
273 // PublicKeyFromYBytes reconstructs a public key from a 27-byte y-coordinate.
274 func PublicKeyFromYBytes(data []byte) (*PublicKey, error) {
275 if len(data) < 27 {
276 return nil, errors.New("gnarl: short public key")
277 }
278
279 var yfe fe
280 if !feFromBytes27(&yfe, data) {
281 return nil, errors.New("gnarl: y >= P")
282 }
283
284 // x^2 = 1 + 5*y^2/4 mod P
285 var y2, five, inv4, fiveY2o4, x2, xfe fe
286 montSquare(&y2, &yfe)
287 feFromSmall(&five, 5)
288 feFromSmall(&inv4, 4)
289 feInv(&inv4, &inv4)
290 montMul(&fiveY2o4, &five, &y2)
291 montMul(&fiveY2o4, &fiveY2o4, &inv4)
292 feAdd(&x2, &feOne, &fiveY2o4)
293
294 if !feSqrt(&xfe, &x2) {
295 return nil, errors.New("gnarl: no square root (y not on torus)")
296 }
297
298 // M = [[x + y/2, y], [y, x - y/2]]
299 var inv2, yHalf, afe, dfe fe
300 feFromSmall(&inv2, 2)
301 feInv(&inv2, &inv2)
302 montMul(&yHalf, &yfe, &inv2)
303 feAdd(&afe, &xfe, &yHalf)
304 feSub(&dfe, &xfe, &yHalf)
305
306 // Check subgroup membership: M^Q = I.
307 tm1 := tmat{a: afe, b: yfe, d: dfe}
308 var m4check, m4cand mat4
309 tmToMat4(&m4cand, &tm1)
310 m4PowBig(&m4check, &m4cand, qBig)
311 if m4IsIdentity(&m4check) {
312 return &PublicKey{tm: tm1}, nil
313 }
314
315 // Try the other root (-x).
316 var xNeg fe
317 feNeg(&xNeg, &xfe)
318 feAdd(&afe, &xNeg, &yHalf)
319 feSub(&dfe, &xNeg, &yHalf)
320
321 tm2 := tmat{a: afe, b: yfe, d: dfe}
322 tmToMat4(&m4cand, &tm2)
323 m4PowBig(&m4check, &m4cand, qBig)
324 if m4IsIdentity(&m4check) {
325 return &PublicKey{tm: tm2}, nil
326 }
327
328 return nil, errors.New("gnarl: neither root in subgroup")
329 }
330
331 // Sign produces a Gnarl signature on msg.
332 // The challenge hash is GMid(msg || R.FullBytes()), using the trinary
333 // Hamadryad hash. The challengeFunc parameter allows the caller to
334 // provide the hash function (avoiding a circular import with pkg/crypto).
335 func Sign(sk *PrivateKey, msg []byte, challengeFunc func([]byte) [27]byte) (*Signature, error) {
336 // k <- random in [1, Q)
337 var k scalar
338 if err := scRandom(&k); err != nil {
339 return nil, err
340 }
341
342 // R = SchnorrGen^k
343 var rTM tmat
344 tmFixedExp(&rTM, &k)
345
346 // Serialize R for challenge hash.
347 rBytes := make([]byte, 81)
348 tmToBytes(rBytes, &rTM)
349
350 // e = GMid(msg || R.FullBytes())
351 hashInput := make([]byte, len(msg)+81)
352 copy(hashInput, msg)
353 copy(hashInput[len(msg):], rBytes)
354 eBytes := challengeFunc(hashInput)
355
356 // z = (k - e*s) mod Q
357 var eSc, es, z scalar
358 scFromBytes27(&eSc, eBytes[:])
359 scMul(&es, &eSc, &sk.s)
360 scSub(&z, &k, &es)
361
362 return &Signature{e: eBytes, z: z}, nil
363 }
364
365 // Verify checks a Gnarl signature.
366 func Verify(pk *PublicKey, msg []byte, sig *Signature, challengeFunc func([]byte) [27]byte) bool {
367 // R' = SchnorrGen^z * PK^e
368 var eSc scalar
369 scFromBytes27(&eSc, sig.e[:])
370
371 var rPrime tmat
372 tmShamirExp(&rPrime, &sig.z, &pk.tm, &eSc)
373
374 // Serialize R' and compute challenge.
375 rBytes := make([]byte, 81)
376 tmToBytes(rBytes, &rPrime)
377
378 hashInput := make([]byte, len(msg)+81)
379 copy(hashInput, msg)
380 copy(hashInput[len(msg):], rBytes)
381 ePrime := challengeFunc(hashInput)
382
383 return sig.e == ePrime
384 }
385
386 // SignatureBytes serializes a signature as 54 bytes (27 challenge + 27 response).
387 func (sig *Signature) Bytes() []byte {
388 buf := make([]byte, 54)
389 copy(buf[:27], sig.e[:])
390 scToBytes27(buf[27:], &sig.z)
391 return buf
392 }
393
394 // SignatureFromBytes deserializes a 54-byte signature.
395 func SignatureFromBytes(data []byte) (*Signature, error) {
396 if len(data) < 54 {
397 return nil, errors.New("gnarl: short signature")
398 }
399 sig := &Signature{}
400 copy(sig.e[:], data[:27])
401 scFromBytes27(&sig.z, data[27:54])
402 return sig, nil
403 }
404
405 // Params returns the scheme parameters.
406 func Params() (prime, subgroupOrder, torusOrder *big.Int) {
407 return new(big.Int).Set(pBig), new(big.Int).Set(qBig), new(big.Int).Set(nBig)
408 }
409