← Back to branch summary

~nskaggs/+junk/xenial-test

« back to all changes in this revision

Viewing changes to src/golang.org/x/crypto/bn256/optate.go

  • Committer: Nicholas Skaggs
  • Date: 2016-10-24 20:56:05 UTC
  • Revision ID: nicholas.skaggs@canonical.com-20161024205605-z8lta0uvuhtxwzwl
Initi with beta15

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/golang.org/x/crypto/bn256/optate.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
 
6
 
 
7
func lineFunctionAdd(r, p *twistPoint, q *curvePoint, r2 *gfP2, pool *bnPool) (a, b, c *gfP2, rOut *twistPoint) {
 
8
        // See the mixed addition algorithm from "Faster Computation of the
 
9
        // Tate Pairing", http://arxiv.org/pdf/0904.0854v3.pdf
 
10
 
 
11
        B := newGFp2(pool).Mul(p.x, r.t, pool)
 
12
 
 
13
        D := newGFp2(pool).Add(p.y, r.z)
 
14
        D.Square(D, pool)
 
15
        D.Sub(D, r2)
 
16
        D.Sub(D, r.t)
 
17
        D.Mul(D, r.t, pool)
 
18
 
 
19
        H := newGFp2(pool).Sub(B, r.x)
 
20
        I := newGFp2(pool).Square(H, pool)
 
21
 
 
22
        E := newGFp2(pool).Add(I, I)
 
23
        E.Add(E, E)
 
24
 
 
25
        J := newGFp2(pool).Mul(H, E, pool)
 
26
 
 
27
        L1 := newGFp2(pool).Sub(D, r.y)
 
28
        L1.Sub(L1, r.y)
 
29
 
 
30
        V := newGFp2(pool).Mul(r.x, E, pool)
 
31
 
 
32
        rOut = newTwistPoint(pool)
 
33
        rOut.x.Square(L1, pool)
 
34
        rOut.x.Sub(rOut.x, J)
 
35
        rOut.x.Sub(rOut.x, V)
 
36
        rOut.x.Sub(rOut.x, V)
 
37
 
 
38
        rOut.z.Add(r.z, H)
 
39
        rOut.z.Square(rOut.z, pool)
 
40
        rOut.z.Sub(rOut.z, r.t)
 
41
        rOut.z.Sub(rOut.z, I)
 
42
 
 
43
        t := newGFp2(pool).Sub(V, rOut.x)
 
44
        t.Mul(t, L1, pool)
 
45
        t2 := newGFp2(pool).Mul(r.y, J, pool)
 
46
        t2.Add(t2, t2)
 
47
        rOut.y.Sub(t, t2)
 
48
 
 
49
        rOut.t.Square(rOut.z, pool)
 
50
 
 
51
        t.Add(p.y, rOut.z)
 
52
        t.Square(t, pool)
 
53
        t.Sub(t, r2)
 
54
        t.Sub(t, rOut.t)
 
55
 
 
56
        t2.Mul(L1, p.x, pool)
 
57
        t2.Add(t2, t2)
 
58
        a = newGFp2(pool)
 
59
        a.Sub(t2, t)
 
60
 
 
61
        c = newGFp2(pool)
 
62
        c.MulScalar(rOut.z, q.y)
 
63
        c.Add(c, c)
 
64
 
 
65
        b = newGFp2(pool)
 
66
        b.SetZero()
 
67
        b.Sub(b, L1)
 
68
        b.MulScalar(b, q.x)
 
69
        b.Add(b, b)
 
70
 
 
71
        B.Put(pool)
 
72
        D.Put(pool)
 
73
        H.Put(pool)
 
74
        I.Put(pool)
 
75
        E.Put(pool)
 
76
        J.Put(pool)
 
77
        L1.Put(pool)
 
78
        V.Put(pool)
 
79
        t.Put(pool)
 
80
        t2.Put(pool)
 
81
 
 
82
        return
 
83
}
 
84
 
 
85
func lineFunctionDouble(r *twistPoint, q *curvePoint, pool *bnPool) (a, b, c *gfP2, rOut *twistPoint) {
 
86
        // See the doubling algorithm for a=0 from "Faster Computation of the
 
87
        // Tate Pairing", http://arxiv.org/pdf/0904.0854v3.pdf
 
88
 
 
89
        A := newGFp2(pool).Square(r.x, pool)
 
90
        B := newGFp2(pool).Square(r.y, pool)
 
91
        C := newGFp2(pool).Square(B, pool)
 
92
 
 
93
        D := newGFp2(pool).Add(r.x, B)
 
94
        D.Square(D, pool)
 
95
        D.Sub(D, A)
 
96
        D.Sub(D, C)
 
97
        D.Add(D, D)
 
98
 
 
99
        E := newGFp2(pool).Add(A, A)
 
100
        E.Add(E, A)
 
101
 
 
102
        G := newGFp2(pool).Square(E, pool)
 
103
 
 
104
        rOut = newTwistPoint(pool)
 
105
        rOut.x.Sub(G, D)
 
106
        rOut.x.Sub(rOut.x, D)
 
107
 
 
108
        rOut.z.Add(r.y, r.z)
 
109
        rOut.z.Square(rOut.z, pool)
 
110
        rOut.z.Sub(rOut.z, B)
 
111
        rOut.z.Sub(rOut.z, r.t)
 
112
 
 
113
        rOut.y.Sub(D, rOut.x)
 
114
        rOut.y.Mul(rOut.y, E, pool)
 
115
        t := newGFp2(pool).Add(C, C)
 
116
        t.Add(t, t)
 
117
        t.Add(t, t)
 
118
        rOut.y.Sub(rOut.y, t)
 
119
 
 
120
        rOut.t.Square(rOut.z, pool)
 
121
 
 
122
        t.Mul(E, r.t, pool)
 
123
        t.Add(t, t)
 
124
        b = newGFp2(pool)
 
125
        b.SetZero()
 
126
        b.Sub(b, t)
 
127
        b.MulScalar(b, q.x)
 
128
 
 
129
        a = newGFp2(pool)
 
130
        a.Add(r.x, E)
 
131
        a.Square(a, pool)
 
132
        a.Sub(a, A)
 
133
        a.Sub(a, G)
 
134
        t.Add(B, B)
 
135
        t.Add(t, t)
 
136
        a.Sub(a, t)
 
137
 
 
138
        c = newGFp2(pool)
 
139
        c.Mul(rOut.z, r.t, pool)
 
140
        c.Add(c, c)
 
141
        c.MulScalar(c, q.y)
 
142
 
 
143
        A.Put(pool)
 
144
        B.Put(pool)
 
145
        C.Put(pool)
 
146
        D.Put(pool)
 
147
        E.Put(pool)
 
148
        G.Put(pool)
 
149
        t.Put(pool)
 
150
 
 
151
        return
 
152
}
 
153
 
 
154
func mulLine(ret *gfP12, a, b, c *gfP2, pool *bnPool) {
 
155
        a2 := newGFp6(pool)
 
156
        a2.x.SetZero()
 
157
        a2.y.Set(a)
 
158
        a2.z.Set(b)
 
159
        a2.Mul(a2, ret.x, pool)
 
160
        t3 := newGFp6(pool).MulScalar(ret.y, c, pool)
 
161
 
 
162
        t := newGFp2(pool)
 
163
        t.Add(b, c)
 
164
        t2 := newGFp6(pool)
 
165
        t2.x.SetZero()
 
166
        t2.y.Set(a)
 
167
        t2.z.Set(t)
 
168
        ret.x.Add(ret.x, ret.y)
 
169
 
 
170
        ret.y.Set(t3)
 
171
 
 
172
        ret.x.Mul(ret.x, t2, pool)
 
173
        ret.x.Sub(ret.x, a2)
 
174
        ret.x.Sub(ret.x, ret.y)
 
175
        a2.MulTau(a2, pool)
 
176
        ret.y.Add(ret.y, a2)
 
177
 
 
178
        a2.Put(pool)
 
179
        t3.Put(pool)
 
180
        t2.Put(pool)
 
181
        t.Put(pool)
 
182
}
 
183
 
 
184
// sixuPlus2NAF is 6u+2 in non-adjacent form.
 
185
var sixuPlus2NAF = []int8{0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, -1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, -1, 0, 1, 0, 0, 0, 1, 0, -1, 0, 0, 0, -1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, -1, 0, -1, 0, 0, 0, 0, 1, 0, 0, 0, 1}
 
186
 
 
187
// miller implements the Miller loop for calculating the Optimal Ate pairing.
 
188
// See algorithm 1 from http://cryptojedi.org/papers/dclxvi-20100714.pdf
 
189
func miller(q *twistPoint, p *curvePoint, pool *bnPool) *gfP12 {
 
190
        ret := newGFp12(pool)
 
191
        ret.SetOne()
 
192
 
 
193
        aAffine := newTwistPoint(pool)
 
194
        aAffine.Set(q)
 
195
        aAffine.MakeAffine(pool)
 
196
 
 
197
        bAffine := newCurvePoint(pool)
 
198
        bAffine.Set(p)
 
199
        bAffine.MakeAffine(pool)
 
200
 
 
201
        minusA := newTwistPoint(pool)
 
202
        minusA.Negative(aAffine, pool)
 
203
 
 
204
        r := newTwistPoint(pool)
 
205
        r.Set(aAffine)
 
206
 
 
207
        r2 := newGFp2(pool)
 
208
        r2.Square(aAffine.y, pool)
 
209
 
 
210
        for i := len(sixuPlus2NAF) - 1; i > 0; i-- {
 
211
                a, b, c, newR := lineFunctionDouble(r, bAffine, pool)
 
212
                if i != len(sixuPlus2NAF)-1 {
 
213
                        ret.Square(ret, pool)
 
214
                }
 
215
 
 
216
                mulLine(ret, a, b, c, pool)
 
217
                a.Put(pool)
 
218
                b.Put(pool)
 
219
                c.Put(pool)
 
220
                r.Put(pool)
 
221
                r = newR
 
222
 
 
223
                switch sixuPlus2NAF[i-1] {
 
224
                case 1:
 
225
                        a, b, c, newR = lineFunctionAdd(r, aAffine, bAffine, r2, pool)
 
226
                case -1:
 
227
                        a, b, c, newR = lineFunctionAdd(r, minusA, bAffine, r2, pool)
 
228
                default:
 
229
                        continue
 
230
                }
 
231
 
 
232
                mulLine(ret, a, b, c, pool)
 
233
                a.Put(pool)
 
234
                b.Put(pool)
 
235
                c.Put(pool)
 
236
                r.Put(pool)
 
237
                r = newR
 
238
        }
 
239
 
 
240
        // In order to calculate Q1 we have to convert q from the sextic twist
 
241
        // to the full GF(p^12) group, apply the Frobenius there, and convert
 
242
        // back.
 
243
        //
 
244
        // The twist isomorphism is (x', y') -> (xω², yω³). If we consider just
 
245
        // x for a moment, then after applying the Frobenius, we have x̄ω^(2p)
 
246
        // where x̄ is the conjugate of x. If we are going to apply the inverse
 
247
        // isomorphism we need a value with a single coefficient of ω² so we
 
248
        // rewrite this as x̄ω^(2p-2)ω². ξ⁶ = ω and, due to the construction of
 
249
        // p, 2p-2 is a multiple of six. Therefore we can rewrite as
 
250
        // x̄ξ^((p-1)/3)ω² and applying the inverse isomorphism eliminates the
 
251
        // ω².
 
252
        //
 
253
        // A similar argument can be made for the y value.
 
254
 
 
255
        q1 := newTwistPoint(pool)
 
256
        q1.x.Conjugate(aAffine.x)
 
257
        q1.x.Mul(q1.x, xiToPMinus1Over3, pool)
 
258
        q1.y.Conjugate(aAffine.y)
 
259
        q1.y.Mul(q1.y, xiToPMinus1Over2, pool)
 
260
        q1.z.SetOne()
 
261
        q1.t.SetOne()
 
262
 
 
263
        // For Q2 we are applying the p² Frobenius. The two conjugations cancel
 
264
        // out and we are left only with the factors from the isomorphism. In
 
265
        // the case of x, we end up with a pure number which is why
 
266
        // xiToPSquaredMinus1Over3 is ∈ GF(p). With y we get a factor of -1. We
 
267
        // ignore this to end up with -Q2.
 
268
 
 
269
        minusQ2 := newTwistPoint(pool)
 
270
        minusQ2.x.MulScalar(aAffine.x, xiToPSquaredMinus1Over3)
 
271
        minusQ2.y.Set(aAffine.y)
 
272
        minusQ2.z.SetOne()
 
273
        minusQ2.t.SetOne()
 
274
 
 
275
        r2.Square(q1.y, pool)
 
276
        a, b, c, newR := lineFunctionAdd(r, q1, bAffine, r2, pool)
 
277
        mulLine(ret, a, b, c, pool)
 
278
        a.Put(pool)
 
279
        b.Put(pool)
 
280
        c.Put(pool)
 
281
        r.Put(pool)
 
282
        r = newR
 
283
 
 
284
        r2.Square(minusQ2.y, pool)
 
285
        a, b, c, newR = lineFunctionAdd(r, minusQ2, bAffine, r2, pool)
 
286
        mulLine(ret, a, b, c, pool)
 
287
        a.Put(pool)
 
288
        b.Put(pool)
 
289
        c.Put(pool)
 
290
        r.Put(pool)
 
291
        r = newR
 
292
 
 
293
        aAffine.Put(pool)
 
294
        bAffine.Put(pool)
 
295
        minusA.Put(pool)
 
296
        r.Put(pool)
 
297
        r2.Put(pool)
 
298
 
 
299
        return ret
 
300
}
 
301
 
 
302
// finalExponentiation computes the (p¹²-1)/Order-th power of an element of
 
303
// GF(p¹²) to obtain an element of GT (steps 13-15 of algorithm 1 from
 
304
// http://cryptojedi.org/papers/dclxvi-20100714.pdf)
 
305
func finalExponentiation(in *gfP12, pool *bnPool) *gfP12 {
 
306
        t1 := newGFp12(pool)
 
307
 
 
308
        // This is the p^6-Frobenius
 
309
        t1.x.Negative(in.x)
 
310
        t1.y.Set(in.y)
 
311
 
 
312
        inv := newGFp12(pool)
 
313
        inv.Invert(in, pool)
 
314
        t1.Mul(t1, inv, pool)
 
315
 
 
316
        t2 := newGFp12(pool).FrobeniusP2(t1, pool)
 
317
        t1.Mul(t1, t2, pool)
 
318
 
 
319
        fp := newGFp12(pool).Frobenius(t1, pool)
 
320
        fp2 := newGFp12(pool).FrobeniusP2(t1, pool)
 
321
        fp3 := newGFp12(pool).Frobenius(fp2, pool)
 
322
 
 
323
        fu, fu2, fu3 := newGFp12(pool), newGFp12(pool), newGFp12(pool)
 
324
        fu.Exp(t1, u, pool)
 
325
        fu2.Exp(fu, u, pool)
 
326
        fu3.Exp(fu2, u, pool)
 
327
 
 
328
        y3 := newGFp12(pool).Frobenius(fu, pool)
 
329
        fu2p := newGFp12(pool).Frobenius(fu2, pool)
 
330
        fu3p := newGFp12(pool).Frobenius(fu3, pool)
 
331
        y2 := newGFp12(pool).FrobeniusP2(fu2, pool)
 
332
 
 
333
        y0 := newGFp12(pool)
 
334
        y0.Mul(fp, fp2, pool)
 
335
        y0.Mul(y0, fp3, pool)
 
336
 
 
337
        y1, y4, y5 := newGFp12(pool), newGFp12(pool), newGFp12(pool)
 
338
        y1.Conjugate(t1)
 
339
        y5.Conjugate(fu2)
 
340
        y3.Conjugate(y3)
 
341
        y4.Mul(fu, fu2p, pool)
 
342
        y4.Conjugate(y4)
 
343
 
 
344
        y6 := newGFp12(pool)
 
345
        y6.Mul(fu3, fu3p, pool)
 
346
        y6.Conjugate(y6)
 
347
 
 
348
        t0 := newGFp12(pool)
 
349
        t0.Square(y6, pool)
 
350
        t0.Mul(t0, y4, pool)
 
351
        t0.Mul(t0, y5, pool)
 
352
        t1.Mul(y3, y5, pool)
 
353
        t1.Mul(t1, t0, pool)
 
354
        t0.Mul(t0, y2, pool)
 
355
        t1.Square(t1, pool)
 
356
        t1.Mul(t1, t0, pool)
 
357
        t1.Square(t1, pool)
 
358
        t0.Mul(t1, y1, pool)
 
359
        t1.Mul(t1, y0, pool)
 
360
        t0.Square(t0, pool)
 
361
        t0.Mul(t0, t1, pool)
 
362
 
 
363
        inv.Put(pool)
 
364
        t1.Put(pool)
 
365
        t2.Put(pool)
 
366
        fp.Put(pool)
 
367
        fp2.Put(pool)
 
368
        fp3.Put(pool)
 
369
        fu.Put(pool)
 
370
        fu2.Put(pool)
 
371
        fu3.Put(pool)
 
372
        fu2p.Put(pool)
 
373
        fu3p.Put(pool)
 
374
        y0.Put(pool)
 
375
        y1.Put(pool)
 
376
        y2.Put(pool)
 
377
        y3.Put(pool)
 
378
        y4.Put(pool)
 
379
        y5.Put(pool)
 
380
        y6.Put(pool)
 
381
 
 
382
        return t0
 
383
}
 
384
 
 
385
func optimalAte(a *twistPoint, b *curvePoint, pool *bnPool) *gfP12 {
 
386
        e := miller(a, b, pool)
 
387
        ret := finalExponentiation(e, pool)
 
388
        e.Put(pool)
 
389
 
 
390
        if a.IsInfinity() || b.IsInfinity() {
 
391
                ret.SetOne()
 
392
        }
 
393
 
 
394
        return ret
 
395
}