← Back to branch summary

~ubuntu-branches/ubuntu/utopic/hockeypuck/utopic-proposed

« back to all changes in this revision

Viewing changes to build/src/code.google.com/p/go.crypto/bn256/bn256.go

  • Committer: Package Import Robot
  • Author(s): Casey Marshall
  • Date: 2014-04-13 20:06:01 UTC
  • Revision ID: package-import@ubuntu.com-20140413200601-oxdlqn1gy0x8m55u
Tags: 1.0~rel20140413+7a1892a~trusty
Hockeypuck 1.0 release

Show diffs side-by-side

added added

removed removed

Lines of Context:
build/src/code.google.com/p/go.crypto/bn256/bn256.go
 
1
// Copyright 2012 The Go Authors. All rights reserved.
 
2
// Use of this source code is governed by a BSD-style
 
3
// license that can be found in the LICENSE file.
 
4
 
 
5
// Package bn256 implements a particular bilinear group at the 128-bit security level.
 
6
//
 
7
// Bilinear groups are the basis of many of the new cryptographic protocols
 
8
// that have been proposed over the past decade. They consist of a triplet of
 
9
// groups (G₁, G₂ and GT) such that there exists a function e(g₁ˣ,g₂ʸ)=gTˣʸ
 
10
// (where gₓ is a generator of the respective group). That function is called
 
11
// a pairing function.
 
12
//
 
13
// This package specifically implements the Optimal Ate pairing over a 256-bit
 
14
// Barreto-Naehrig curve as described in
 
15
// http://cryptojedi.org/papers/dclxvi-20100714.pdf. Its output is compatible
 
16
// with the implementation described in that paper.
 
17
package bn256
 
18
 
 
19
import (
 
20
        "crypto/rand"
 
21
        "io"
 
22
        "math/big"
 
23
)
 
24
 
 
25
// BUG(agl): this implementation is not constant time.
 
26
// TODO(agl): keep GF(p²) elements in Mongomery form.
 
27
 
 
28
// G1 is an abstract cyclic group. The zero value is suitable for use as the
 
29
// output of an operation, but cannot be used as an input.
 
30
type G1 struct {
 
31
        p *curvePoint
 
32
}
 
33
 
 
34
// RandomG1 returns x and g₁ˣ where x is a random, non-zero number read from r.
 
35
func RandomG1(r io.Reader) (*big.Int, *G1, error) {
 
36
        var k *big.Int
 
37
        var err error
 
38
 
 
39
        for {
 
40
                k, err = rand.Int(r, Order)
 
41
                if err != nil {
 
42
                        return nil, nil, err
 
43
                }
 
44
                if k.Sign() > 0 {
 
45
                        break
 
46
                }
 
47
        }
 
48
 
 
49
        return k, new(G1).ScalarBaseMult(k), nil
 
50
}
 
51
 
 
52
func (g *G1) String() string {
 
53
        return "bn256.G1" + g.p.String()
 
54
}
 
55
 
 
56
// ScalarBaseMult sets e to g*k where g is the generator of the group and
 
57
// then returns e.
 
58
func (e *G1) ScalarBaseMult(k *big.Int) *G1 {
 
59
        if e.p == nil {
 
60
                e.p = newCurvePoint(nil)
 
61
        }
 
62
        e.p.Mul(curveGen, k, new(bnPool))
 
63
        return e
 
64
}
 
65
 
 
66
// ScalarMult sets e to a*k and then returns e.
 
67
func (e *G1) ScalarMult(a *G1, k *big.Int) *G1 {
 
68
        if e.p == nil {
 
69
                e.p = newCurvePoint(nil)
 
70
        }
 
71
        e.p.Mul(a.p, k, new(bnPool))
 
72
        return e
 
73
}
 
74
 
 
75
// Add sets e to a+b and then returns e.
 
76
// BUG(agl): this function is not complete: a==b fails.
 
77
func (e *G1) Add(a, b *G1) *G1 {
 
78
        if e.p == nil {
 
79
                e.p = newCurvePoint(nil)
 
80
        }
 
81
        e.p.Add(a.p, b.p, new(bnPool))
 
82
        return e
 
83
}
 
84
 
 
85
// Neg sets e to -a and then returns e.
 
86
func (e *G1) Neg(a *G1) *G1 {
 
87
        if e.p == nil {
 
88
                e.p = newCurvePoint(nil)
 
89
        }
 
90
        e.p.Negative(a.p)
 
91
        return e
 
92
}
 
93
 
 
94
// Marshal converts n to a byte slice.
 
95
func (n *G1) Marshal() []byte {
 
96
        n.p.MakeAffine(nil)
 
97
 
 
98
        xBytes := new(big.Int).Mod(n.p.x, p).Bytes()
 
99
        yBytes := new(big.Int).Mod(n.p.y, p).Bytes()
 
100
 
 
101
        // Each value is a 256-bit number.
 
102
        const numBytes = 256 / 8
 
103
 
 
104
        ret := make([]byte, numBytes*2)
 
105
        copy(ret[1*numBytes-len(xBytes):], xBytes)
 
106
        copy(ret[2*numBytes-len(yBytes):], yBytes)
 
107
 
 
108
        return ret
 
109
}
 
110
 
 
111
// Unmarshal sets e to the result of converting the output of Marshal back into
 
112
// a group element and then returns e.
 
113
func (e *G1) Unmarshal(m []byte) (*G1, bool) {
 
114
        // Each value is a 256-bit number.
 
115
        const numBytes = 256 / 8
 
116
 
 
117
        if len(m) != 2*numBytes {
 
118
                return nil, false
 
119
        }
 
120
 
 
121
        if e.p == nil {
 
122
                e.p = newCurvePoint(nil)
 
123
        }
 
124
 
 
125
        e.p.x.SetBytes(m[0*numBytes : 1*numBytes])
 
126
        e.p.y.SetBytes(m[1*numBytes : 2*numBytes])
 
127
 
 
128
        if e.p.x.Sign() == 0 && e.p.y.Sign() == 0 {
 
129
                // This is the point at infinity.
 
130
                e.p.y.SetInt64(1)
 
131
                e.p.z.SetInt64(0)
 
132
                e.p.t.SetInt64(0)
 
133
        } else {
 
134
                e.p.z.SetInt64(1)
 
135
                e.p.t.SetInt64(1)
 
136
 
 
137
                if !e.p.IsOnCurve() {
 
138
                        return nil, false
 
139
                }
 
140
        }
 
141
 
 
142
        return e, true
 
143
}
 
144
 
 
145
// G2 is an abstract cyclic group. The zero value is suitable for use as the
 
146
// output of an operation, but cannot be used as an input.
 
147
type G2 struct {
 
148
        p *twistPoint
 
149
}
 
150
 
 
151
// RandomG1 returns x and g₂ˣ where x is a random, non-zero number read from r.
 
152
func RandomG2(r io.Reader) (*big.Int, *G2, error) {
 
153
        var k *big.Int
 
154
        var err error
 
155
 
 
156
        for {
 
157
                k, err = rand.Int(r, Order)
 
158
                if err != nil {
 
159
                        return nil, nil, err
 
160
                }
 
161
                if k.Sign() > 0 {
 
162
                        break
 
163
                }
 
164
        }
 
165
 
 
166
        return k, new(G2).ScalarBaseMult(k), nil
 
167
}
 
168
 
 
169
func (g *G2) String() string {
 
170
        return "bn256.G2" + g.p.String()
 
171
}
 
172
 
 
173
// ScalarBaseMult sets e to g*k where g is the generator of the group and
 
174
// then returns out.
 
175
func (e *G2) ScalarBaseMult(k *big.Int) *G2 {
 
176
        if e.p == nil {
 
177
                e.p = newTwistPoint(nil)
 
178
        }
 
179
        e.p.Mul(twistGen, k, new(bnPool))
 
180
        return e
 
181
}
 
182
 
 
183
// ScalarMult sets e to a*k and then returns e.
 
184
func (e *G2) ScalarMult(a *G2, k *big.Int) *G2 {
 
185
        if e.p == nil {
 
186
                e.p = newTwistPoint(nil)
 
187
        }
 
188
        e.p.Mul(a.p, k, new(bnPool))
 
189
        return e
 
190
}
 
191
 
 
192
// Add sets e to a+b and then returns e.
 
193
// BUG(agl): this function is not complete: a==b fails.
 
194
func (e *G2) Add(a, b *G2) *G2 {
 
195
        if e.p == nil {
 
196
                e.p = newTwistPoint(nil)
 
197
        }
 
198
        e.p.Add(a.p, b.p, new(bnPool))
 
199
        return e
 
200
}
 
201
 
 
202
// Marshal converts n into a byte slice.
 
203
func (n *G2) Marshal() []byte {
 
204
        n.p.MakeAffine(nil)
 
205
 
 
206
        xxBytes := new(big.Int).Mod(n.p.x.x, p).Bytes()
 
207
        xyBytes := new(big.Int).Mod(n.p.x.y, p).Bytes()
 
208
        yxBytes := new(big.Int).Mod(n.p.y.x, p).Bytes()
 
209
        yyBytes := new(big.Int).Mod(n.p.y.y, p).Bytes()
 
210
 
 
211
        // Each value is a 256-bit number.
 
212
        const numBytes = 256 / 8
 
213
 
 
214
        ret := make([]byte, numBytes*4)
 
215
        copy(ret[1*numBytes-len(xxBytes):], xxBytes)
 
216
        copy(ret[2*numBytes-len(xyBytes):], xyBytes)
 
217
        copy(ret[3*numBytes-len(yxBytes):], yxBytes)
 
218
        copy(ret[4*numBytes-len(yyBytes):], yyBytes)
 
219
 
 
220
        return ret
 
221
}
 
222
 
 
223
// Unmarshal sets e to the result of converting the output of Marshal back into
 
224
// a group element and then returns e.
 
225
func (e *G2) Unmarshal(m []byte) (*G2, bool) {
 
226
        // Each value is a 256-bit number.
 
227
        const numBytes = 256 / 8
 
228
 
 
229
        if len(m) != 4*numBytes {
 
230
                return nil, false
 
231
        }
 
232
 
 
233
        if e.p == nil {
 
234
                e.p = newTwistPoint(nil)
 
235
        }
 
236
 
 
237
        e.p.x.x.SetBytes(m[0*numBytes : 1*numBytes])
 
238
        e.p.x.y.SetBytes(m[1*numBytes : 2*numBytes])
 
239
        e.p.y.x.SetBytes(m[2*numBytes : 3*numBytes])
 
240
        e.p.y.y.SetBytes(m[3*numBytes : 4*numBytes])
 
241
 
 
242
        if e.p.x.x.Sign() == 0 &&
 
243
                e.p.x.y.Sign() == 0 &&
 
244
                e.p.y.x.Sign() == 0 &&
 
245
                e.p.y.y.Sign() == 0 {
 
246
                // This is the point at infinity.
 
247
                e.p.y.SetOne()
 
248
                e.p.z.SetZero()
 
249
                e.p.t.SetZero()
 
250
        } else {
 
251
                e.p.z.SetOne()
 
252
                e.p.t.SetOne()
 
253
 
 
254
                if !e.p.IsOnCurve() {
 
255
                        return nil, false
 
256
                }
 
257
        }
 
258
 
 
259
        return e, true
 
260
}
 
261
 
 
262
// GT is an abstract cyclic group. The zero value is suitable for use as the
 
263
// output of an operation, but cannot be used as an input.
 
264
type GT struct {
 
265
        p *gfP12
 
266
}
 
267
 
 
268
func (g *GT) String() string {
 
269
        return "bn256.GT" + g.p.String()
 
270
}
 
271
 
 
272
// ScalarMult sets e to a*k and then returns e.
 
273
func (e *GT) ScalarMult(a *GT, k *big.Int) *GT {
 
274
        if e.p == nil {
 
275
                e.p = newGFp12(nil)
 
276
        }
 
277
        e.p.Exp(a.p, k, new(bnPool))
 
278
        return e
 
279
}
 
280
 
 
281
// Add sets e to a+b and then returns e.
 
282
func (e *GT) Add(a, b *GT) *GT {
 
283
        if e.p == nil {
 
284
                e.p = newGFp12(nil)
 
285
        }
 
286
        e.p.Mul(a.p, b.p, new(bnPool))
 
287
        return e
 
288
}
 
289
 
 
290
// Neg sets e to -a and then returns e.
 
291
func (e *GT) Neg(a *GT) *GT {
 
292
        if e.p == nil {
 
293
                e.p = newGFp12(nil)
 
294
        }
 
295
        e.p.Invert(a.p, new(bnPool))
 
296
        return e
 
297
}
 
298
 
 
299
// Marshal converts n into a byte slice.
 
300
func (n *GT) Marshal() []byte {
 
301
        n.p.Minimal()
 
302
 
 
303
        xxxBytes := n.p.x.x.x.Bytes()
 
304
        xxyBytes := n.p.x.x.y.Bytes()
 
305
        xyxBytes := n.p.x.y.x.Bytes()
 
306
        xyyBytes := n.p.x.y.y.Bytes()
 
307
        xzxBytes := n.p.x.z.x.Bytes()
 
308
        xzyBytes := n.p.x.z.y.Bytes()
 
309
        yxxBytes := n.p.y.x.x.Bytes()
 
310
        yxyBytes := n.p.y.x.y.Bytes()
 
311
        yyxBytes := n.p.y.y.x.Bytes()
 
312
        yyyBytes := n.p.y.y.y.Bytes()
 
313
        yzxBytes := n.p.y.z.x.Bytes()
 
314
        yzyBytes := n.p.y.z.y.Bytes()
 
315
 
 
316
        // Each value is a 256-bit number.
 
317
        const numBytes = 256 / 8
 
318
 
 
319
        ret := make([]byte, numBytes*12)
 
320
        copy(ret[1*numBytes-len(xxxBytes):], xxxBytes)
 
321
        copy(ret[2*numBytes-len(xxyBytes):], xxyBytes)
 
322
        copy(ret[3*numBytes-len(xyxBytes):], xyxBytes)
 
323
        copy(ret[4*numBytes-len(xyyBytes):], xyyBytes)
 
324
        copy(ret[5*numBytes-len(xzxBytes):], xzxBytes)
 
325
        copy(ret[6*numBytes-len(xzyBytes):], xzyBytes)
 
326
        copy(ret[7*numBytes-len(yxxBytes):], yxxBytes)
 
327
        copy(ret[8*numBytes-len(yxyBytes):], yxyBytes)
 
328
        copy(ret[9*numBytes-len(yyxBytes):], yyxBytes)
 
329
        copy(ret[10*numBytes-len(yyyBytes):], yyyBytes)
 
330
        copy(ret[11*numBytes-len(yzxBytes):], yzxBytes)
 
331
        copy(ret[12*numBytes-len(yzyBytes):], yzyBytes)
 
332
 
 
333
        return ret
 
334
}
 
335
 
 
336
// Unmarshal sets e to the result of converting the output of Marshal back into
 
337
// a group element and then returns e.
 
338
func (e *GT) Unmarshal(m []byte) (*GT, bool) {
 
339
        // Each value is a 256-bit number.
 
340
        const numBytes = 256 / 8
 
341
 
 
342
        if len(m) != 12*numBytes {
 
343
                return nil, false
 
344
        }
 
345
 
 
346
        if e.p == nil {
 
347
                e.p = newGFp12(nil)
 
348
        }
 
349
 
 
350
        e.p.x.x.x.SetBytes(m[0*numBytes : 1*numBytes])
 
351
        e.p.x.x.y.SetBytes(m[1*numBytes : 2*numBytes])
 
352
        e.p.x.y.x.SetBytes(m[2*numBytes : 3*numBytes])
 
353
        e.p.x.y.y.SetBytes(m[3*numBytes : 4*numBytes])
 
354
        e.p.x.z.x.SetBytes(m[4*numBytes : 5*numBytes])
 
355
        e.p.x.z.y.SetBytes(m[5*numBytes : 6*numBytes])
 
356
        e.p.y.x.x.SetBytes(m[6*numBytes : 7*numBytes])
 
357
        e.p.y.x.y.SetBytes(m[7*numBytes : 8*numBytes])
 
358
        e.p.y.y.x.SetBytes(m[8*numBytes : 9*numBytes])
 
359
        e.p.y.y.y.SetBytes(m[9*numBytes : 10*numBytes])
 
360
        e.p.y.z.x.SetBytes(m[10*numBytes : 11*numBytes])
 
361
        e.p.y.z.y.SetBytes(m[11*numBytes : 12*numBytes])
 
362
 
 
363
        return e, true
 
364
}
 
365
 
 
366
// Pair calculates an Optimal Ate pairing.
 
367
func Pair(g1 *G1, g2 *G2) *GT {
 
368
        return &GT{optimalAte(g2.p, g1.p, new(bnPool))}
 
369
}
 
370
 
 
371
// bnPool implements a tiny cache of *big.Int objects that's used to reduce the
 
372
// number of allocations made during processing.
 
373
type bnPool struct {
 
374
        bns   []*big.Int
 
375
        count int
 
376
}
 
377
 
 
378
func (pool *bnPool) Get() *big.Int {
 
379
        if pool == nil {
 
380
                return new(big.Int)
 
381
        }
 
382
 
 
383
        pool.count++
 
384
        l := len(pool.bns)
 
385
        if l == 0 {
 
386
                return new(big.Int)
 
387
        }
 
388
 
 
389
        bn := pool.bns[l-1]
 
390
        pool.bns = pool.bns[:l-1]
 
391
        return bn
 
392
}
 
393
 
 
394
func (pool *bnPool) Put(bn *big.Int) {
 
395
        if pool == nil {
 
396
                return
 
397
        }
 
398
        pool.bns = append(pool.bns, bn)
 
399
        pool.count--
 
400
}
 
401
 
 
402
func (pool *bnPool) Count() int {
 
403
        return pool.count
 
404
}