yaole
290 lines
7.9 KiB
Go
290 lines
7.9 KiB
Go
package bn256
|
|
|
|
func lineFunctionAdd(a, b, c *gfP2, rOut *twistPoint, r, p *twistPoint, q *curvePoint, r2 *gfP2) {
|
|
// See the mixed addition algorithm from "Faster Computation of the
|
|
// Tate Pairing", http://arxiv.org/pdf/0904.0854v3.pdf
|
|
B := (&gfP2{}).Mul(&p.x, &r.t)
|
|
|
|
D := (&gfP2{}).Add(&p.y, &r.z)
|
|
D.Square(D).Sub(D, r2).Sub(D, &r.t).Mul(D, &r.t)
|
|
|
|
H := (&gfP2{}).Sub(B, &r.x)
|
|
I := (&gfP2{}).Square(H)
|
|
|
|
E := (&gfP2{}).Add(I, I)
|
|
E.Add(E, E)
|
|
|
|
J := (&gfP2{}).Mul(H, E)
|
|
|
|
L1 := (&gfP2{}).Sub(D, &r.y)
|
|
L1.Sub(L1, &r.y)
|
|
|
|
V := (&gfP2{}).Mul(&r.x, E)
|
|
|
|
// rOut = &twistPoint{}
|
|
t, t2 := &gfP2{}, &gfP2{}
|
|
rOut.x.Square(L1).Sub(&rOut.x, J).Sub(&rOut.x, V).Sub(&rOut.x, V)
|
|
rOut.z.Add(&r.z, H).Square(&rOut.z).Sub(&rOut.z, &r.t).Sub(&rOut.z, I)
|
|
t.Sub(V, &rOut.x).Mul(t, L1)
|
|
t2.Mul(&r.y, J).Add(t2, t2)
|
|
rOut.y.Sub(t, t2)
|
|
rOut.t.Square(&rOut.z)
|
|
|
|
t.Add(&p.y, &rOut.z).Square(t).Sub(t, r2).Sub(t, &rOut.t)
|
|
|
|
t2.Mul(L1, &p.x).Add(t2, t2)
|
|
a.Sub(t2, t)
|
|
|
|
c.MulScalar(&rOut.z, &q.y)
|
|
c.Add(c, c)
|
|
|
|
b.Neg(L1)
|
|
b.MulScalar(b, &q.x).Add(b, b)
|
|
}
|
|
|
|
func lineFunctionDouble(a, b, c *gfP2, rOut *twistPoint, r *twistPoint, q *curvePoint) {
|
|
// See the doubling algorithm for a=0 from "Faster Computation of the
|
|
// Tate Pairing", http://arxiv.org/pdf/0904.0854v3.pdf
|
|
A := (&gfP2{}).Square(&r.x)
|
|
B := (&gfP2{}).Square(&r.y)
|
|
C := (&gfP2{}).Square(B)
|
|
|
|
D := (&gfP2{}).Add(&r.x, B)
|
|
D.Square(D).Sub(D, A).Sub(D, C).Add(D, D)
|
|
|
|
E := (&gfP2{}).Add(A, A)
|
|
E.Add(E, A)
|
|
|
|
G := (&gfP2{}).Square(E)
|
|
|
|
// rOut = &twistPoint{}
|
|
rOut.x.Sub(G, D).Sub(&rOut.x, D)
|
|
|
|
rOut.z.Add(&r.y, &r.z).Square(&rOut.z).Sub(&rOut.z, B).Sub(&rOut.z, &r.t)
|
|
|
|
rOut.y.Sub(D, &rOut.x).Mul(&rOut.y, E)
|
|
t := (&gfP2{}).Add(C, C)
|
|
t.Add(t, t).Add(t, t)
|
|
rOut.y.Sub(&rOut.y, t)
|
|
|
|
rOut.t.Square(&rOut.z)
|
|
|
|
t.Mul(E, &r.t).Add(t, t)
|
|
b.Neg(t)
|
|
b.MulScalar(b, &q.x)
|
|
|
|
a.Add(&r.x, E)
|
|
a.Square(a).Sub(a, A).Sub(a, G)
|
|
t.Add(B, B).Add(t, t)
|
|
a.Sub(a, t)
|
|
|
|
c.Mul(&rOut.z, &r.t)
|
|
c.Add(c, c).MulScalar(c, &q.y)
|
|
}
|
|
func mulLine(ret *gfP12, a, b, c *gfP2) {
|
|
if false {
|
|
a2 := &gfP6{}
|
|
a2.y.Set(a)
|
|
a2.z.Set(b)
|
|
a2.Mul(a2, &ret.x)
|
|
t3 := (&gfP6{}).MulScalar(&ret.y, c)
|
|
|
|
t := (&gfP2{}).Add(b, c)
|
|
t2 := &gfP6{}
|
|
t2.y.Set(a)
|
|
t2.z.Set(t)
|
|
ret.x.Add(&ret.x, &ret.y)
|
|
|
|
ret.y.Set(t3)
|
|
|
|
ret.x.Mul(&ret.x, t2).Sub(&ret.x, a2).Sub(&ret.x, &ret.y)
|
|
a2.MulTau(a2)
|
|
ret.y.Add(&ret.y, a2)
|
|
} else {
|
|
// ret = ret * [ cτ*w + (bτ+a) ]
|
|
a2 := &gfP12{}
|
|
a2.x.x.SetZero()
|
|
a2.x.y.Set(c)
|
|
a2.x.z.SetZero()
|
|
|
|
a2.y.x.SetZero()
|
|
a2.y.y.Set(b)
|
|
a2.y.z.Set(a)
|
|
|
|
ret.Mul(ret, a2)
|
|
}
|
|
}
|
|
|
|
// sixuPlus2NAF is 6u+2 in non-adjacent form.
|
|
// 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}
|
|
var sixuPlus2NAF = []int8{0, -1, 0, 0, 0, 0, 1, 0, 1, 0, 0, -1, 0, -1, 0, 0, 0, -1, 0, -1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1}
|
|
|
|
// miller implements the Miller loop for calculating the Optimal Ate pairing.
|
|
// See algorithm 1 from http://cryptojedi.org/papers/dclxvi-20100714.pdf
|
|
func miller(ret *gfP12, q *twistPoint, p *curvePoint) {
|
|
ret.SetOne()
|
|
|
|
aAffine := &twistPoint{}
|
|
aAffine.Set(q)
|
|
aAffine.MakeAffine()
|
|
|
|
bAffine := &curvePoint{}
|
|
bAffine.Set(p)
|
|
bAffine.MakeAffine()
|
|
|
|
minusA := &twistPoint{}
|
|
minusA.Neg(aAffine)
|
|
|
|
r := &twistPoint{}
|
|
r.Set(aAffine)
|
|
|
|
r2 := (&gfP2{}).Square(&aAffine.y)
|
|
a := &gfP2{}
|
|
b := &gfP2{}
|
|
c := &gfP2{}
|
|
newR := &twistPoint{}
|
|
for i := len(sixuPlus2NAF) - 1; i > 0; i-- {
|
|
lineFunctionDouble(a, b, c, newR, r, bAffine)
|
|
if i != len(sixuPlus2NAF)-1 {
|
|
ret.Square(ret)
|
|
}
|
|
|
|
mulLine(ret, a, b, c)
|
|
r.Set(newR)
|
|
|
|
switch sixuPlus2NAF[i-1] {
|
|
case 1:
|
|
lineFunctionAdd(a, b, c, newR, r, aAffine, bAffine, r2)
|
|
case -1:
|
|
lineFunctionAdd(a, b, c, newR, r, minusA, bAffine, r2)
|
|
default:
|
|
continue
|
|
}
|
|
|
|
mulLine(ret, a, b, c)
|
|
r.Set(newR)
|
|
}
|
|
|
|
// In order to calculate Q1 we have to convert q from the sextic twist
|
|
// to the full GF(P^12) group, apply the Frobenius there, and convert
|
|
// back.
|
|
//
|
|
// The twist isomorphism is (x', y') -> (xω², yω³). If we consider just
|
|
// x for a moment, then after applying the Frobenius, we have x̄ω^(2p)
|
|
// where x̄ is the conjugate of x. If we are going to apply the inverse
|
|
// isomorphism we need a value with a single coefficient of ω² so we
|
|
// rewrite this as x̄ω^(2p-2)ω². ξ⁶ = ω and, due to the construction of
|
|
// P, 2p-2 is a multiple of six. Therefore we can rewrite as
|
|
// x̄ξ^((P-1)/3)ω² and applying the inverse isomorphism eliminates the
|
|
// ω².
|
|
//
|
|
// A similar argument can be made for the y value.
|
|
q1 := &twistPoint{}
|
|
q1.x.Conjugate(&aAffine.x).MulScalar(&q1.x, xiTo1MinusPOver3)
|
|
q1.y.Conjugate(&aAffine.y).MulScalar(&q1.y, xiTo1MinusPOver2)
|
|
q1.z.SetOne()
|
|
q1.t.SetOne()
|
|
|
|
// For Q2 we are applying the P² Frobenius. The two conjugations cancel
|
|
// out and we are left only with the factors from the isomorphism. In
|
|
// the case of x, we end up with a pure number which is why
|
|
// xiToPSquaredMinus1Over3 is ∈ GF(P). With y we get a factor of -1. We
|
|
// ignore this to end up with -Q2.
|
|
minusQ2 := &twistPoint{}
|
|
minusQ2.x.MulScalar(&aAffine.x, xiTo2Minus2POver3)
|
|
minusQ2.y.Set(&aAffine.y)
|
|
minusQ2.z.SetOne()
|
|
minusQ2.t.SetOne()
|
|
|
|
r2.Square(&q1.y)
|
|
lineFunctionAdd(a, b, c, newR, r, q1, bAffine, r2)
|
|
mulLine(ret, a, b, c)
|
|
r = newR
|
|
|
|
r2.Square(&minusQ2.y)
|
|
lineFunctionAdd(a, b, c, newR, r, minusQ2, bAffine, r2) // nolint
|
|
mulLine(ret, a, b, c)
|
|
r = newR // nolint
|
|
}
|
|
|
|
// finalExponentiation computes the (P¹²-1)/Order-th power of an element of
|
|
// GF(P¹²) to obtain an element of GT (steps 13-15 of algorithm 1 from
|
|
// http://cryptojedi.org/papers/dclxvi-20100714.pdf)
|
|
func finalExponentiation(out *gfP12, in *gfP12) {
|
|
if false {
|
|
// The naive algorithm. For rightness test.
|
|
e := bigFromBase16("61835e8b12594991a09a6ae43ade454acef6f4e86411255c16be7fbaca54d38dd9d1d3019dba1539bf41bcb4067aa64be8cb0476c5042cb93b5122d974b7ba196f691269ceb7907239e0cb2a13873665ed57cd410455806b97559b180ee9629f1c8d7d0598eee9b93dc562fa23afa5a3bed65f00632c9cc80357732739295edcb5a6b4b9ec19ba7a4defa394c04689ab78bd480ff56fa0696fd3135583d5aa1335d59c358aac66ee2c3601d19f32c692fb14fc5412315ec5a54d51e82f7dd634550e98dca2042c36b948ebd4aa170bae804f361d729e88dc3e3945f87bf22030f4c6983d64089bdf703b00c9e53535a5bbd6c4aa78c62f31d16182c1d978ad0efe915cab1b62d11b760558913d719f2bb6793f9fe39f2568478b1a3e843d1fa0b48ee8fd4c31b8f6fe5e935a4b5f799cbd806a8225955b05b83e3d7e2d0b9698e4890ab7e824dc7c6135fec864e1676b19fe1764ac0b7482facdd0f0d042330")
|
|
out.Exp(in, e)
|
|
return
|
|
}
|
|
|
|
t1 := &gfP12{}
|
|
|
|
// This is the P^6-Frobenius
|
|
t1.x.Neg(&in.x)
|
|
t1.y.Set(&in.y)
|
|
|
|
inv := &gfP12{}
|
|
inv.Invert(in)
|
|
t1.Mul(t1, inv)
|
|
|
|
t2 := (&gfP12{}).FrobeniusP2(t1)
|
|
t1.Mul(t1, t2)
|
|
|
|
fp := (&gfP12{}).Frobenius(t1)
|
|
fp2 := (&gfP12{}).FrobeniusP2(t1)
|
|
fp3 := (&gfP12{}).Frobenius(fp2)
|
|
|
|
fu := (&gfP12{}).Exp(t1, u)
|
|
fu2 := (&gfP12{}).Exp(fu, u)
|
|
fu3 := (&gfP12{}).Exp(fu2, u)
|
|
|
|
y3 := (&gfP12{}).Frobenius(fu)
|
|
fu2p := (&gfP12{}).Frobenius(fu2)
|
|
fu3p := (&gfP12{}).Frobenius(fu3)
|
|
y2 := (&gfP12{}).FrobeniusP2(fu2)
|
|
|
|
y0 := &gfP12{}
|
|
y0.Mul(fp, fp2).Mul(y0, fp3)
|
|
|
|
y1 := (&gfP12{}).Conjugate(t1)
|
|
y5 := (&gfP12{}).Conjugate(fu2)
|
|
y3.Conjugate(y3)
|
|
y4 := (&gfP12{}).Mul(fu, fu2p)
|
|
y4.Conjugate(y4)
|
|
|
|
y6 := (&gfP12{}).Mul(fu3, fu3p)
|
|
y6.Conjugate(y6)
|
|
|
|
if false {
|
|
t0 := (&gfP12{}).Square(y6)
|
|
t0.Mul(t0, y4).Mul(t0, y5)
|
|
t1.Mul(y3, y5).Mul(t1, t0)
|
|
t0.Mul(t0, y2)
|
|
t1.Square(t1).Mul(t1, t0).Square(t1)
|
|
t0.Mul(t1, y1)
|
|
t1.Mul(t1, y0)
|
|
t0.Square(t0).Mul(t0, t1)
|
|
// return t0
|
|
} else {
|
|
out.Square(y6)
|
|
out.Mul(out, y4).Mul(out, y5)
|
|
t1.Mul(y3, y5).Mul(t1, out)
|
|
out.Mul(out, y2)
|
|
t1.Square(t1).Mul(t1, out).Square(t1)
|
|
out.Mul(t1, y1)
|
|
t1.Mul(t1, y0)
|
|
out.Square(out).Mul(out, t1)
|
|
}
|
|
}
|
|
|
|
func optimalAte(e *gfP12, a *twistPoint, b *curvePoint) *gfP12 {
|
|
if a.IsInfinity() || b.IsInfinity() {
|
|
e.SetOne()
|
|
return e
|
|
}
|
|
miller(e, a, b)
|
|
finalExponentiation(e, e)
|
|
return e
|
|
}
|