/* | |
Licensed to the Apache Software Foundation (ASF) under one | |
or more contributor license agreements. See the NOTICE file | |
distributed with this work for additional information | |
regarding copyright ownership. The ASF licenses this file | |
to you under the Apache License, Version 2.0 (the | |
"License"); you may not use this file except in compliance | |
with the License. You may obtain a copy of the License at | |
http://www.apache.org/licenses/LICENSE-2.0 | |
Unless required by applicable law or agreed to in writing, | |
software distributed under the License is distributed on an | |
"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY | |
KIND, either express or implied. See the License for the | |
specific language governing permissions and limitations | |
under the License. | |
*/ | |
// | |
// pair.swift | |
// | |
// | |
// Created by Michael Scott on 07/07/2015. | |
// Copyright (c) 2015 Michael Scott. All rights reserved. | |
// | |
/* CLINT BN Curve Pairing functions */ | |
final class PAIR { | |
/* Line function */ | |
static func line(A:ECP2,_ B:ECP2,_ Qx:FP,_ Qy:FP) -> FP12 | |
{ | |
let P=ECP2() | |
var a:FP4 | |
var b:FP4 | |
var c:FP4 | |
P.copy(A); | |
let ZZ=FP2(P.getz()) | |
ZZ.sqr(); | |
var D:Int | |
if A===B {D=A.dbl()} /* Check this return value in clint_ec2.c */ | |
else {D=A.add(B)} | |
if (D<0) {return FP12(1)} | |
let Z3=FP2(A.getz()) | |
c=FP4(0) | |
if D==0 | |
{ /* Addition */ | |
let X=FP2(B.getx()) | |
let Y=FP2(B.gety()) | |
let T=FP2(P.getz()) | |
T.mul(Y) | |
ZZ.mul(T) | |
let NY=FP2(P.gety()); NY.neg() | |
ZZ.add(NY) | |
Z3.pmul(Qy) | |
T.mul(P.getx()) | |
X.mul(NY) | |
T.add(X) | |
a=FP4(Z3,T) | |
ZZ.neg() | |
ZZ.pmul(Qx) | |
b=FP4(ZZ) | |
} | |
else | |
{ /* Doubling */ | |
let X=FP2(P.getx()) | |
let Y=FP2(P.gety()) | |
let T=FP2(P.getx()) | |
T.sqr() | |
T.imul(3) | |
Y.sqr() | |
Y.add(Y) | |
Z3.mul(ZZ) | |
Z3.pmul(Qy) | |
X.mul(T) | |
X.sub(Y) | |
a=FP4(Z3,X) | |
T.neg() | |
ZZ.mul(T) | |
ZZ.pmul(Qx) | |
b=FP4(ZZ) | |
} | |
return FP12(a,b,c) | |
} | |
/* Optimal R-ate pairing */ | |
static func ate(P:ECP2,_ Q:ECP) -> FP12 | |
{ | |
let f=FP2(BIG(ROM.CURVE_Fra),BIG(ROM.CURVE_Frb)) | |
let x=BIG(ROM.CURVE_Bnx) | |
let n=BIG(x) | |
let K=ECP2() | |
var lv:FP12 | |
n.pmul(6); n.dec(2); n.norm() | |
P.affine() | |
Q.affine() | |
let Qx=FP(Q.getx()) | |
let Qy=FP(Q.gety()) | |
let A=ECP2() | |
let r=FP12(1) | |
A.copy(P) | |
let nb=n.nbits() | |
for var i=nb-2;i>=1;i-- | |
{ | |
lv=line(A,A,Qx,Qy) | |
r.smul(lv) | |
if (n.bit(i)==1) | |
{ | |
lv=line(A,P,Qx,Qy) | |
r.smul(lv) | |
} | |
r.sqr() | |
} | |
lv=line(A,A,Qx,Qy) | |
r.smul(lv) | |
/* R-ate fixup */ | |
r.conj() | |
K.copy(P) | |
K.frob(f) | |
A.neg() | |
lv=line(A,K,Qx,Qy) | |
r.smul(lv) | |
K.frob(f) | |
K.neg() | |
lv=line(A,K,Qx,Qy) | |
r.smul(lv) | |
return r | |
} | |
/* Optimal R-ate double pairing e(P,Q).e(R,S) */ | |
static func ate2(P:ECP2,_ Q:ECP,_ R:ECP2,_ S:ECP) -> FP12 | |
{ | |
let f=FP2(BIG(ROM.CURVE_Fra),BIG(ROM.CURVE_Frb)) | |
let x=BIG(ROM.CURVE_Bnx) | |
let n=BIG(x) | |
let K=ECP2() | |
var lv:FP12 | |
n.pmul(6); n.dec(2); n.norm() | |
P.affine() | |
Q.affine() | |
R.affine() | |
S.affine() | |
let Qx=FP(Q.getx()) | |
let Qy=FP(Q.gety()) | |
let Sx=FP(S.getx()) | |
let Sy=FP(S.gety()) | |
let A=ECP2() | |
let B=ECP2() | |
let r=FP12(1) | |
A.copy(P) | |
B.copy(R) | |
let nb=n.nbits() | |
for var i=nb-2;i>=1;i-- | |
{ | |
lv=line(A,A,Qx,Qy) | |
r.smul(lv) | |
lv=line(B,B,Sx,Sy) | |
r.smul(lv) | |
if n.bit(i)==1 | |
{ | |
lv=line(A,P,Qx,Qy) | |
r.smul(lv) | |
lv=line(B,R,Sx,Sy) | |
r.smul(lv) | |
} | |
r.sqr() | |
} | |
lv=line(A,A,Qx,Qy) | |
r.smul(lv) | |
lv=line(B,B,Sx,Sy) | |
r.smul(lv) | |
/* R-ate fixup */ | |
r.conj() | |
K.copy(P) | |
K.frob(f) | |
A.neg() | |
lv=line(A,K,Qx,Qy) | |
r.smul(lv) | |
K.frob(f) | |
K.neg() | |
lv=line(A,K,Qx,Qy) | |
r.smul(lv) | |
K.copy(R) | |
K.frob(f) | |
B.neg() | |
lv=line(B,K,Sx,Sy) | |
r.smul(lv) | |
K.frob(f) | |
K.neg() | |
lv=line(B,K,Sx,Sy) | |
r.smul(lv) | |
return r | |
} | |
/* final exponentiation - keep separate for multi-pairings and to avoid thrashing stack */ | |
static func fexp(m:FP12) -> FP12 | |
{ | |
let f=FP2(BIG(ROM.CURVE_Fra),BIG(ROM.CURVE_Frb)); | |
let x=BIG(ROM.CURVE_Bnx) | |
let r=FP12(m) | |
/* Easy part of final exp */ | |
var lv=FP12(r) | |
lv.inverse() | |
r.conj() | |
r.mul(lv) | |
lv.copy(r) | |
r.frob(f) | |
r.frob(f) | |
r.mul(lv) | |
/* Hard part of final exp */ | |
lv.copy(r) | |
lv.frob(f) | |
let x0=FP12(lv) | |
x0.frob(f) | |
lv.mul(r) | |
x0.mul(lv) | |
x0.frob(f) | |
let x1=FP12(r) | |
x1.conj() | |
let x4=r.pow(x) | |
let x3=FP12(x4) | |
x3.frob(f) | |
let x2=x4.pow(x) | |
let x5=FP12(x2); x5.conj() | |
lv=x2.pow(x) | |
x2.frob(f) | |
r.copy(x2); r.conj() | |
x4.mul(r) | |
x2.frob(f) | |
r.copy(lv) | |
r.frob(f) | |
lv.mul(r) | |
lv.usqr() | |
lv.mul(x4) | |
lv.mul(x5) | |
r.copy(x3) | |
r.mul(x5) | |
r.mul(lv) | |
lv.mul(x2) | |
r.usqr() | |
r.mul(lv) | |
r.usqr() | |
lv.copy(r) | |
lv.mul(x1) | |
r.mul(x0) | |
lv.usqr() | |
r.mul(lv) | |
r.reduce() | |
return r | |
} | |
/* GLV method */ | |
static func glv(e:BIG) -> [BIG] | |
{ | |
let t=BIG(0) | |
let q=BIG(ROM.CURVE_Order) | |
var u=[BIG](); | |
var v=[BIG](); | |
for var j=0;j<2;j++ | |
{ | |
u.append(BIG(0)) | |
v.append(BIG(0)) | |
} | |
for var i=0;i<2;i++ | |
{ | |
t.copy(BIG(ROM.CURVE_W[i])) | |
let d=BIG.mul(t,e) | |
v[i].copy(d.div(q)) | |
} | |
u[0].copy(e); | |
for var i=0;i<2;i++ | |
{ | |
for var j=0;j<2;j++ | |
{ | |
t.copy(BIG(ROM.CURVE_SB[j][i])) | |
t.copy(BIG.modmul(v[j],t,q)) | |
u[i].add(q) | |
u[i].sub(t) | |
u[i].mod(q) | |
} | |
} | |
return u | |
} | |
/* Galbraith & Scott Method */ | |
static func gs(e:BIG) -> [BIG] | |
{ | |
let t=BIG(0) | |
let q=BIG(ROM.CURVE_Order) | |
var u=[BIG](); | |
var v=[BIG](); | |
for var j=0;j<4;j++ | |
{ | |
u.append(BIG(0)) | |
v.append(BIG(0)) | |
} | |
for var i=0;i<4;i++ | |
{ | |
t.copy(BIG(ROM.CURVE_WB[i])) | |
let d=BIG.mul(t,e) | |
v[i].copy(d.div(q)) | |
} | |
u[0].copy(e); | |
for var i=0;i<4;i++ | |
{ | |
for var j=0;j<4;j++ | |
{ | |
t.copy(BIG(ROM.CURVE_BB[j][i])) | |
t.copy(BIG.modmul(v[j],t,q)) | |
u[i].add(q) | |
u[i].sub(t) | |
u[i].mod(q) | |
} | |
} | |
return u | |
} | |
/* Multiply P by e in group G1 */ | |
static func G1mul(P:ECP,_ e:BIG) -> ECP | |
{ | |
var R:ECP | |
if (ROM.USE_GLV) | |
{ | |
P.affine() | |
R=ECP() | |
R.copy(P) | |
let Q=ECP() | |
Q.copy(P) | |
let q=BIG(ROM.CURVE_Order) | |
let cru=FP(BIG(ROM.CURVE_Cru)) | |
let t=BIG(0) | |
var u=PAIR.glv(e) | |
Q.getx().mul(cru); | |
var np=u[0].nbits() | |
t.copy(BIG.modneg(u[0],q)) | |
var nn=t.nbits() | |
if (nn<np) | |
{ | |
u[0].copy(t) | |
R.neg() | |
} | |
np=u[1].nbits() | |
t.copy(BIG.modneg(u[1],q)) | |
nn=t.nbits() | |
if (nn<np) | |
{ | |
u[1].copy(t) | |
Q.neg() | |
} | |
R=R.mul2(u[0],Q,u[1]) | |
} | |
else | |
{ | |
R=P.mul(e) | |
} | |
return R | |
} | |
/* Multiply P by e in group G2 */ | |
static func G2mul(P:ECP2,_ e:BIG) -> ECP2 | |
{ | |
var R:ECP2 | |
if (ROM.USE_GS_G2) | |
{ | |
var Q=[ECP2]() | |
let f=FP2(BIG(ROM.CURVE_Fra),BIG(ROM.CURVE_Frb)); | |
let q=BIG(ROM.CURVE_Order); | |
var u=PAIR.gs(e); | |
let t=BIG(0); | |
P.affine() | |
Q.append(ECP2()) | |
Q[0].copy(P); | |
for var i=1;i<4;i++ | |
{ | |
Q.append(ECP2()); Q[i].copy(Q[i-1]); | |
Q[i].frob(f); | |
} | |
for var i=0;i<4;i++ | |
{ | |
let np=u[i].nbits(); | |
t.copy(BIG.modneg(u[i],q)); | |
let nn=t.nbits(); | |
if (nn<np) | |
{ | |
u[i].copy(t); | |
Q[i].neg(); | |
} | |
} | |
R=ECP2.mul4(Q,u); | |
} | |
else | |
{ | |
R=P.mul(e); | |
} | |
return R; | |
} | |
/* f=f^e */ | |
/* Note that this method requires a lot of RAM! Better to use compressed XTR method, see FP4.java */ | |
static func GTpow(d:FP12,_ e:BIG) -> FP12 | |
{ | |
var r:FP12 | |
if (ROM.USE_GS_GT) | |
{ | |
var g=[FP12]() | |
let f=FP2(BIG(ROM.CURVE_Fra),BIG(ROM.CURVE_Frb)) | |
let q=BIG(ROM.CURVE_Order) | |
let t=BIG(0) | |
var u=gs(e) | |
g.append(FP12(0)) | |
g[0].copy(d); | |
for var i=1;i<4;i++ | |
{ | |
g.append(FP12(0)); g[i].copy(g[i-1]) | |
g[i].frob(f) | |
} | |
for var i=0;i<4;i++ | |
{ | |
let np=u[i].nbits() | |
t.copy(BIG.modneg(u[i],q)) | |
let nn=t.nbits() | |
if (nn<np) | |
{ | |
u[i].copy(t) | |
g[i].conj() | |
} | |
} | |
r=FP12.pow4(g,u) | |
} | |
else | |
{ | |
r=d.pow(e) | |
} | |
return r | |
} | |
/* test group membership */ | |
/* with GT-Strong curve, now only check that m!=1, conj(m)*m==1, and m.m^{p^4}=m^{p^2} */ | |
static func GTmember(m:FP12) -> Bool | |
{ | |
if m.isunity() {return false} | |
let r=FP12(m) | |
r.conj() | |
r.mul(m) | |
if !r.isunity() {return false} | |
let f=FP2(BIG(ROM.CURVE_Fra),BIG(ROM.CURVE_Frb)) | |
r.copy(m); r.frob(f); r.frob(f) | |
var w=FP12(r); w.frob(f); w.frob(f) | |
w.mul(m) | |
if !ROM.GT_STRONG | |
{ | |
if !w.equals(r) {return false} | |
let x=BIG(ROM.CURVE_Bnx) | |
r.copy(m); w=r.pow(x); w=w.pow(x) | |
r.copy(w); r.sqr(); r.mul(w); r.sqr() | |
w.copy(m); w.frob(f) | |
} | |
return w.equals(r) | |
} | |
} | |