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.
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
11 B := newGFp2(pool).Mul(p.x, r.t, pool)
13 D := newGFp2(pool).Add(p.y, r.z)
19 H := newGFp2(pool).Sub(B, r.x)
20 I := newGFp2(pool).Square(H, pool)
22 E := newGFp2(pool).Add(I, I)
25 J := newGFp2(pool).Mul(H, E, pool)
27 L1 := newGFp2(pool).Sub(D, r.y)
30 V := newGFp2(pool).Mul(r.x, E, pool)
32 rOut = newTwistPoint(pool)
33 rOut.x.Square(L1, pool)
39 rOut.z.Square(rOut.z, pool)
40 rOut.z.Sub(rOut.z, r.t)
43 t := newGFp2(pool).Sub(V, rOut.x)
45 t2 := newGFp2(pool).Mul(r.y, J, pool)
49 rOut.t.Square(rOut.z, pool)
62 c.MulScalar(rOut.z, q.y)
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
89 A := newGFp2(pool).Square(r.x, pool)
90 B := newGFp2(pool).Square(r.y, pool)
91 C := newGFp2(pool).Square(B, pool)
93 D := newGFp2(pool).Add(r.x, B)
99 E := newGFp2(pool).Add(A, A)
102 G := newGFp2(pool).Square(E, pool)
104 rOut = newTwistPoint(pool)
106 rOut.x.Sub(rOut.x, D)
109 rOut.z.Square(rOut.z, pool)
110 rOut.z.Sub(rOut.z, B)
111 rOut.z.Sub(rOut.z, r.t)
113 rOut.y.Sub(D, rOut.x)
114 rOut.y.Mul(rOut.y, E, pool)
115 t := newGFp2(pool).Add(C, C)
118 rOut.y.Sub(rOut.y, t)
120 rOut.t.Square(rOut.z, pool)
139 c.Mul(rOut.z, r.t, pool)
154 func mulLine(ret *gfP12, a, b, c *gfP2, pool *bnPool) {
159 a2.Mul(a2, ret.x, pool)
160 t3 := newGFp6(pool).MulScalar(ret.y, c, pool)
168 ret.x.Add(ret.x, ret.y)
172 ret.x.Mul(ret.x, t2, pool)
174 ret.x.Sub(ret.x, ret.y)
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}
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)
193 aAffine := newTwistPoint(pool)
195 aAffine.MakeAffine(pool)
197 bAffine := newCurvePoint(pool)
199 bAffine.MakeAffine(pool)
201 minusA := newTwistPoint(pool)
202 minusA.Negative(aAffine, pool)
204 r := newTwistPoint(pool)
208 r2.Square(aAffine.y, pool)
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)
216 mulLine(ret, a, b, c, pool)
223 switch sixuPlus2NAF[i-1] {
225 a, b, c, newR = lineFunctionAdd(r, aAffine, bAffine, r2, pool)
227 a, b, c, newR = lineFunctionAdd(r, minusA, bAffine, r2, pool)
232 mulLine(ret, a, b, c, pool)
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
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
253 // A similar argument can be made for the y value.
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)
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.
269 minusQ2 := newTwistPoint(pool)
270 minusQ2.x.MulScalar(aAffine.x, xiToPSquaredMinus1Over3)
271 minusQ2.y.Set(aAffine.y)
275 r2.Square(q1.y, pool)
276 a, b, c, newR := lineFunctionAdd(r, q1, bAffine, r2, pool)
277 mulLine(ret, a, b, c, pool)
284 r2.Square(minusQ2.y, pool)
285 a, b, c, newR = lineFunctionAdd(r, minusQ2, bAffine, r2, pool)
286 mulLine(ret, a, b, c, pool)
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 {
308 // This is the p^6-Frobenius
312 inv := newGFp12(pool)
314 t1.Mul(t1, inv, pool)
316 t2 := newGFp12(pool).FrobeniusP2(t1, pool)
319 fp := newGFp12(pool).Frobenius(t1, pool)
320 fp2 := newGFp12(pool).FrobeniusP2(t1, pool)
321 fp3 := newGFp12(pool).Frobenius(fp2, pool)
323 fu, fu2, fu3 := newGFp12(pool), newGFp12(pool), newGFp12(pool)
326 fu3.Exp(fu2, u, pool)
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)
334 y0.Mul(fp, fp2, pool)
335 y0.Mul(y0, fp3, pool)
337 y1, y4, y5 := newGFp12(pool), newGFp12(pool), newGFp12(pool)
341 y4.Mul(fu, fu2p, pool)
345 y6.Mul(fu3, fu3p, pool)
385 func optimalAte(a *twistPoint, b *curvePoint, pool *bnPool) *gfP12 {
386 e := miller(a, b, pool)
387 ret := finalExponentiation(e, pool)
390 if a.IsInfinity() || b.IsInfinity() {