gnarl.mx 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 // Key sizes:
5 // - Secret key: 27 bytes (scalar mod Q)
6 // - Public key: 27 bytes (torus y-coordinate, y < P/3)
7 // - Signature: 54 bytes (27-byte challenge + 27-byte response)
8 package gnarl
9
10 import (
11 "crypto/sha256"
12 "errors"
13 "math/big"
14 )
15
16 // P, Q, N as big.Int for subgroup membership checks and scalar reduction.
17 var pBig *big.Int
18 var qBig *big.Int
19 var nBig *big.Int
20
21 // SchnorrGen is the Schnorr signature generator on the non-split torus.
22 var schnorrGenTM tmat
23
24 func main() {
25 initFieldConstants()
26 initScalarConstants()
27 initPrime()
28 initGenerators()
29 }
30
31 func initPrime() {
32 seed := sha256.Sum256([]byte("gnarl-bethe-sl2-dendrite-v1"))
33
34 one := (&big.Int{}).SetInt64(1)
35 two := (&big.Int{}).SetInt64(2)
36 five := (&big.Int{}).SetInt64(5)
37 six := (&big.Int{}).SetInt64(6)
38
39 maxQ := (&big.Int{}).Div((&big.Int{}).Lsh(one, 216), six)
40 q := (&big.Int{}).SetBytes(seed[:27])
41 qMask := (&big.Int{}).Sub((&big.Int{}).Lsh(one, 213), one)
42 q.And(q, qMask)
43 q.SetBit(q, 212, 1)
44 if q.Bit(0) == 0 {
45 q.Add(q, one)
46 }
47
48 for {
49 if q.Cmp(maxQ) > 0 {
50 panic("gnarl: prime search exhausted")
51 }
52
53 qm5 := (&big.Int{}).Mod(q, five).Int64()
54 if qm5 == 3 || qm5 == 4 {
55 if q.ProbablyPrime(1) {
56 p := (&big.Int{}).Mul(six, q)
57 p.Sub(p, one)
58 if p.ProbablyPrime(1) {
59 if q.ProbablyPrime(20) && p.ProbablyPrime(20) {
60 pm1 := (&big.Int{}).Sub(p, one)
61 exp := (&big.Int{}).Rsh(pm1, 1)
62 euler := (&big.Int{}).Exp(five, exp, p)
63 if euler.Cmp(pm1) == 0 {
64 pBig = p
65 qBig = q
66 nBig = (&big.Int{}).Add(p, one)
67
68 verifyConstants(p, q)
69 return
70 }
71 }
72 }
73 }
74 }
75 q.Add(q, two)
76 }
77 }
78
79 func verifyConstants(p, q *big.Int) {
80 pCheck := &big.Int{}
81 pCheck.SetUint64(pLimbs[3])
82 pCheck.Lsh(pCheck, 64)
83 pCheck.Or(pCheck, (&big.Int{}).SetUint64(pLimbs[2]))
84 pCheck.Lsh(pCheck, 64)
85 pCheck.Or(pCheck, (&big.Int{}).SetUint64(pLimbs[1]))
86 pCheck.Lsh(pCheck, 64)
87 pCheck.Or(pCheck, (&big.Int{}).SetUint64(pLimbs[0]))
88 if pCheck.Cmp(p) != 0 {
89 panic("gnarl: pLimbs mismatch")
90 }
91
92 qCheck := &big.Int{}
93 qCheck.SetUint64(qLimbs[3])
94 qCheck.Lsh(qCheck, 64)
95 qCheck.Or(qCheck, (&big.Int{}).SetUint64(qLimbs[2]))
96 qCheck.Lsh(qCheck, 64)
97 qCheck.Or(qCheck, (&big.Int{}).SetUint64(qLimbs[1]))
98 qCheck.Lsh(qCheck, 64)
99 qCheck.Or(qCheck, (&big.Int{}).SetUint64(qLimbs[0]))
100 if qCheck.Cmp(q) != 0 {
101 panic("gnarl: qLimbs mismatch")
102 }
103 }
104
105 func initGenerators() {
106 g0 := m4FromSmall(1, 1, 0, 1)
107 g1 := m4FromSmall(1, 0, 1, 1)
108
109 var g01 mat4
110 m4Mul(&g01, &g0, &g1)
111
112 var g01sq mat4
113 m4Mul(&g01sq, &g01, &g01)
114
115 var g01cu mat4
116 m4Mul(&g01cu, &g01sq, &g01)
117
118 var gen mat4
119 m4Mul(&gen, &g01cu, &g01cu)
120
121 tmFromMat4(&schnorrGenTM, &gen)
122
123 if m4IsIdentity(&gen) {
124 panic("gnarl: generator is identity")
125 }
126
127 initGenTable(&schnorrGenTM)
128 }
129
130 type PrivateKey struct {
131 s scalar
132 }
133
134 type PublicKey struct {
135 tm tmat
136 }
137
138 type Signature struct {
139 e [27]byte
140 z scalar
141 }
142
143 func GenerateKey() (sk *PrivateKey, pk *PublicKey, err error) {
144 var s scalar
145 err = scRandom(&s)
146 if err != nil {
147 return nil, nil, err
148 }
149
150 var pkTM tmat
151 tmFixedExp(&pkTM, &s)
152
153 var bNorm fe
154 feFromMont(&bNorm, &pkTM.b)
155 if feIsGtThirdP(&bNorm) == 1 {
156 scNeg(&s, &s)
157 tmInv(&pkTM, &pkTM)
158
159 feFromMont(&bNorm, &pkTM.b)
160 if feIsGtThirdP(&bNorm) == 1 {
161 feFromMont(&bNorm, &pkTM.b)
162 if feIsGtHalfP(&bNorm) == 1 {
163 scNeg(&s, &s)
164 tmInv(&pkTM, &pkTM)
165 }
166 }
167 }
168
169 sk = &PrivateKey{s: s}
170 pk = &PublicKey{tm: pkTM}
171 return sk, pk, nil
172 }
173
174 func PrivateKeyFromBytes(data []byte) (sk *PrivateKey, err error) {
175 if int32(len(data)) < 27 {
176 return nil, errors.New("gnarl: short private key")
177 }
178 var s scalar
179 scFromBytes27(&s, data)
180 if scIsZero(&s) {
181 return nil, errors.New("gnarl: zero private key")
182 }
183 return &PrivateKey{s: s}, nil
184 }
185
186 func (sk *PrivateKey) Bytes() (buf []byte) {
187 buf = []byte{:27}
188 scToBytes27(buf, &sk.s)
189 return buf
190 }
191
192 func PublicKeyFromPrivate(sk *PrivateKey) (pk *PublicKey) {
193 var pkTM tmat
194 tmFixedExp(&pkTM, &sk.s)
195 return &PublicKey{tm: pkTM}
196 }
197
198 func (pk *PublicKey) YBytes() (buf []byte) {
199 buf = []byte{:27}
200 feToBytes27(buf, &pk.tm.b)
201 return buf
202 }
203
204 func (pk *PublicKey) FullBytes() (buf []byte) {
205 buf = []byte{:81}
206 tmToBytes(buf, &pk.tm)
207 return buf
208 }
209
210 func PublicKeyFromYBytes(data []byte) (pk *PublicKey, err error) {
211 if int32(len(data)) < 27 {
212 return nil, errors.New("gnarl: short public key")
213 }
214
215 var yfe fe
216 if !feFromBytes27(&yfe, data) {
217 return nil, errors.New("gnarl: y >= P")
218 }
219
220 var y2, fiveFe, inv4, fiveY2o4, x2, xfe fe
221 montSquare(&y2, &yfe)
222 feFromSmall(&fiveFe, 5)
223 feFromSmall(&inv4, 4)
224 feInv(&inv4, &inv4)
225 montMul(&fiveY2o4, &fiveFe, &y2)
226 montMul(&fiveY2o4, &fiveY2o4, &inv4)
227 feAdd(&x2, &feOne, &fiveY2o4)
228
229 if !feSqrt(&xfe, &x2) {
230 return nil, errors.New("gnarl: no square root (y not on torus)")
231 }
232
233 var inv2, yHalf, afe, dfe fe
234 feFromSmall(&inv2, 2)
235 feInv(&inv2, &inv2)
236 montMul(&yHalf, &yfe, &inv2)
237 feAdd(&afe, &xfe, &yHalf)
238 feSub(&dfe, &xfe, &yHalf)
239
240 tm1 := tmat{a: afe, b: yfe, d: dfe}
241 var m4check, m4cand mat4
242 tmToMat4(&m4cand, &tm1)
243 m4PowBig(&m4check, &m4cand, qBig)
244 if m4IsIdentity(&m4check) {
245 return &PublicKey{tm: tm1}, nil
246 }
247
248 var xNeg fe
249 feNeg(&xNeg, &xfe)
250 feAdd(&afe, &xNeg, &yHalf)
251 feSub(&dfe, &xNeg, &yHalf)
252
253 tm2 := tmat{a: afe, b: yfe, d: dfe}
254 tmToMat4(&m4cand, &tm2)
255 m4PowBig(&m4check, &m4cand, qBig)
256 if m4IsIdentity(&m4check) {
257 return &PublicKey{tm: tm2}, nil
258 }
259
260 return nil, errors.New("gnarl: neither root in subgroup")
261 }
262
263 func Sign(sk *PrivateKey, msg []byte, challengeFunc func([]byte) [27]byte) (sig *Signature, err error) {
264 var k scalar
265 err = scRandom(&k)
266 if err != nil {
267 return nil, err
268 }
269
270 var rTM tmat
271 tmFixedExp(&rTM, &k)
272
273 rBytes := []byte{:81}
274 tmToBytes(rBytes, &rTM)
275
276 hashInput := []byte{:int32(len(msg)) + 81}
277 copy(hashInput, msg)
278 copy(hashInput[int32(len(msg)):], rBytes)
279 eBytes := challengeFunc(hashInput)
280
281 var eSc, es, z scalar
282 scFromBytes27(&eSc, eBytes[:])
283 scMul(&es, &eSc, &sk.s)
284 scSub(&z, &k, &es)
285
286 return &Signature{e: eBytes, z: z}, nil
287 }
288
289 func Verify(pk *PublicKey, msg []byte, sig *Signature, challengeFunc func([]byte) [27]byte) (ok bool) {
290 var eSc scalar
291 scFromBytes27(&eSc, sig.e[:])
292
293 var rPrime tmat
294 tmShamirExp(&rPrime, &sig.z, &pk.tm, &eSc)
295
296 rBytes := []byte{:81}
297 tmToBytes(rBytes, &rPrime)
298
299 hashInput := []byte{:int32(len(msg)) + 81}
300 copy(hashInput, msg)
301 copy(hashInput[int32(len(msg)):], rBytes)
302 ePrime := challengeFunc(hashInput)
303
304 return sig.e == ePrime
305 }
306
307 func (sig *Signature) Bytes() (buf []byte) {
308 buf = []byte{:54}
309 copy(buf[:27], sig.e[:])
310 scToBytes27(buf[27:], &sig.z)
311 return buf
312 }
313
314 func SignatureFromBytes(data []byte) (sig *Signature, err error) {
315 if int32(len(data)) < 54 {
316 return nil, errors.New("gnarl: short signature")
317 }
318 sig = &Signature{}
319 copy(sig.e[:], data[:27])
320 scFromBytes27(&sig.z, data[27:54])
321 return sig, nil
322 }
323
324 func Params() (prime, subgroupOrder, torusOrder *big.Int) {
325 return (&big.Int{}).Set(pBig), (&big.Int{}).Set(qBig), (&big.Int{}).Set(nBig)
326 }
327