version22/js/FP12.js

/*
	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.
*/

/* AMCL Fp^12 functions */

/* FP12 elements are of the form a+i.b+i^2.c */

/* general purpose constructor */
var FP12= function(d,e,f) 
{
	if (d instanceof FP12)
	{
		this.a=new FP4(d.a);
		this.b=new FP4(d.b);
		this.c=new FP4(d.c);
	}
	else
	{
		this.a=new FP4(d);
		this.b=new FP4(e);
		this.c=new FP4(f);
	}
};

FP12.prototype={
/* reduce all components of this mod Modulus */
	reduce: function()
	{
		this.a.reduce();
		this.b.reduce();
		this.c.reduce();
	},
/* normalize all components of this mod Modulus */
	norm: function()
	{
		this.a.norm();
		this.b.norm();
		this.c.norm();
	},
/* test x==0 ? */
	iszilch: function() 
	{
		this.reduce();
		return (this.a.iszilch() && this.b.iszilch() && this.c.iszilch());
	},
/* test x==1 ? */
	isunity: function() 
	{
		var one=new FP4(1);
		return (this.a.equals(one) && this.b.iszilch() && this.b.iszilch());
	},
/* extract a from this */
	geta: function()
	{
		return this.a;
	},
/* extract b */
	getb: function()
	{
		return this.b;
	},
/* extract c */
	getc: function()
	{
		return this.c;
	},
/* return 1 if x==y, else 0 */
	equals: function(x)
	{
		return (this.a.equals(x.a) && this.b.equals(x.b)&& this.c.equals(x.c));
	},
/* copy this=x */
	copy: function(x)
	{
		this.a.copy(x.a);
		this.b.copy(x.b);
		this.c.copy(x.c);
	},
/* set this=1 */
	one: function()
	{
		this.a.one();
		this.b.zero();
		this.c.zero();
	},
/* this=conj(this) */
	conj: function()
	{
		this.a.conj();
		this.b.nconj();
		this.c.conj();
	},

/* set this from 3 FP4s */
	set: function(d,e,f)
	{
		this.a.copy(d);
		this.b.copy(e);
		this.c.copy(f);
	},
/* set this from one FP4 */
	seta: function(d)
	{
		this.a.copy(d);
		this.b.zero();
		this.c.zero();
	},

/* Granger-Scott Unitary Squaring */
	usqr: function()
	{
		var A=new FP4(this.a); //A.copy(this.a);
		var B=new FP4(this.c); //B.copy(this.c);
		var C=new FP4(this.b); //C.copy(this.b);
		var D=new FP4(0);

		this.a.sqr();
		D.copy(this.a); D.add(this.a);
		this.a.add(D);

		A.nconj();

		A.add(A);
		this.a.add(A);
		B.sqr();
		B.times_i();

		D.copy(B); D.add(B);
		B.add(D);

		C.sqr();
		D.copy(C); D.add(C);
		C.add(D);

		this.b.conj();
		this.b.add(this.b);
		this.c.nconj();

		this.c.add(this.c);
		this.b.add(B);
		this.c.add(C);
		this.reduce();
	},

/* Chung-Hasan SQR2 method from http://cacr.uwaterloo.ca/techreports/2006/cacr2006-24.pdf */
	sqr: function()
	{
		var A=new FP4(this.a); //A.copy(this.a);
		var B=new FP4(this.b); //B.copy(this.b);
		var C=new FP4(this.c); //C.copy(this.c);
		var D=new FP4(this.a); //D.copy(this.a);

		A.sqr();
		B.mul(this.c);
		B.add(B);
		C.sqr();
		D.mul(this.b);
		D.add(D);

		this.c.add(this.a);
		this.c.add(this.b);
		this.c.sqr();

		this.a.copy(A);

		A.add(B);
		A.add(C);
		A.add(D);
		A.neg();
		B.times_i();
		C.times_i();

		this.a.add(B);
		this.b.copy(C); this.b.add(D);
		this.c.add(A);

		this.norm();
	},

/* FP12 full multiplication this=this*y */
	mul: function(y)
	{
		var z0=new FP4(this.a); //z0.copy(this.a);
		var z1=new FP4(0);
		var z2=new FP4(this.b); //z2.copy(this.b);
		var z3=new FP4(0);
		var t0=new FP4(this.a); //t0.copy(this.a);
		var t1=new FP4(y.a); //t1.copy(y.a);

		z0.mul(y.a);
		z2.mul(y.b);

		t0.add(this.b);
		t1.add(y.b);

		z1.copy(t0); z1.mul(t1);
		t0.copy(this.b); t0.add(this.c);

		t1.copy(y.b); t1.add(y.c);
		z3.copy(t0); z3.mul(t1);

		t0.copy(z0); t0.neg();
		t1.copy(z2); t1.neg();

		z1.add(t0);
		this.b.copy(z1); this.b.add(t1);

		z3.add(t1);
		z2.add(t0);

		t0.copy(this.a); t0.add(this.c);
		t1.copy(y.a); t1.add(y.c);
		t0.mul(t1);
		z2.add(t0);

		t0.copy(this.c); t0.mul(y.c);
		t1.copy(t0); t1.neg();

		this.c.copy(z2); this.c.add(t1);
		z3.add(t1);
		t0.times_i();
		this.b.add(t0);

		z3.times_i();
		this.a.copy(z0); this.a.add(z3);

		this.norm();
	},

/* Special case this*=y that arises from special form of ATE pairing line function */
	smul: function(y)
	{
		var z0=new FP4(this.a); //z0.copy(this.a);
		var z2=new FP4(this.b); //z2.copy(this.b);
		var z3=new FP4(this.b); //z3.copy(this.b);
		var t0=new FP4(0); 
		var t1=new FP4(y.a); //t1.copy(y.a);
		
		z0.mul(y.a);
		z2.pmul(y.b.real());
		this.b.add(this.a);
		t1.real().add(y.b.real());

		this.b.mul(t1);
		z3.add(this.c);
		z3.pmul(y.b.real());

		t0.copy(z0); t0.neg();
		t1.copy(z2); t1.neg();

		this.b.add(t0);

		this.b.add(t1);
		z3.add(t1);
		z2.add(t0);

		t0.copy(this.a); t0.add(this.c);
		t0.mul(y.a);
		this.c.copy(z2); this.c.add(t0);

		z3.times_i();
		this.a.copy(z0); this.a.add(z3);

		this.norm();
	},

/* this=1/this */
	inverse: function()
	{
		var f0=new FP4(this.a); //f0.copy(this.a);
		var f1=new FP4(this.b); //f1.copy(this.b);
		var f2=new FP4(this.a); //f2.copy(this.a);
		var f3=new FP4(0);

		f0.sqr();
		f1.mul(this.c);
		f1.times_i();
		f0.sub(f1);

		f1.copy(this.c); f1.sqr();
		f1.times_i();
		f2.mul(this.b);
		f1.sub(f2);

		f2.copy(this.b); f2.sqr();
		f3.copy(this.a); f3.mul(this.c);
		f2.sub(f3);

		f3.copy(this.b); f3.mul(f2);
		f3.times_i();
		this.a.mul(f0);
		f3.add(this.a);
		this.c.mul(f1);
		this.c.times_i();

		f3.add(this.c);
		f3.inverse();
		this.a.copy(f0); this.a.mul(f3);
		this.b.copy(f1); this.b.mul(f3);
		this.c.copy(f2); this.c.mul(f3);
	},

/* this=this^p, where p=Modulus, using Frobenius */
	frob: function(f)
	{
		var f2=new FP2(f); 
		var f3=new FP2(f); 

		f2.sqr();
		f3.mul(f2);

		this.a.frob(f3);
		this.b.frob(f3);
		this.c.frob(f3);

		this.b.pmul(f);
		this.c.pmul(f2);
	},

/* trace function */
	trace: function()
	{
		var t=new FP4(0);
		t.copy(this.a);
		t.imul(3);
		t.reduce();
		return t;
	},
/* convert this to hex string */
	toString: function() 
	{
		return ("["+this.a.toString()+","+this.b.toString()+","+this.c.toString()+"]");
	},
/* convert this to byte array */
	toBytes: function(w)
	{
		var i;
		var t=[];
		this.a.geta().getA().toBytes(t);
		for (i=0;i<ROM.MODBYTES;i++) w[i]=t[i];
		this.a.geta().getB().toBytes(t);
		for (i=0;i<ROM.MODBYTES;i++) w[i+ROM.MODBYTES]=t[i];
		this.a.getb().getA().toBytes(t);
		for (i=0;i<ROM.MODBYTES;i++) w[i+2*ROM.MODBYTES]=t[i];
		this.a.getb().getB().toBytes(t);
		for (i=0;i<ROM.MODBYTES;i++) w[i+3*ROM.MODBYTES]=t[i];

		this.b.geta().getA().toBytes(t);
		for (i=0;i<ROM.MODBYTES;i++) w[i+4*ROM.MODBYTES]=t[i];
		this.b.geta().getB().toBytes(t);
		for (i=0;i<ROM.MODBYTES;i++) w[i+5*ROM.MODBYTES]=t[i];
		this.b.getb().getA().toBytes(t);
		for (i=0;i<ROM.MODBYTES;i++) w[i+6*ROM.MODBYTES]=t[i];
		this.b.getb().getB().toBytes(t);
		for (i=0;i<ROM.MODBYTES;i++) w[i+7*ROM.MODBYTES]=t[i];

		this.c.geta().getA().toBytes(t);
		for (i=0;i<ROM.MODBYTES;i++) w[i+8*ROM.MODBYTES]=t[i];
		this.c.geta().getB().toBytes(t);
		for (i=0;i<ROM.MODBYTES;i++) w[i+9*ROM.MODBYTES]=t[i];
		this.c.getb().getA().toBytes(t);
		for (i=0;i<ROM.MODBYTES;i++) w[i+10*ROM.MODBYTES]=t[i];
		this.c.getb().getB().toBytes(t);
		for (i=0;i<ROM.MODBYTES;i++) w[i+11*ROM.MODBYTES]=t[i];
	},

/* set this=this^e */
	pow: function(e)
	{
		this.norm();
		e.norm();
		var w=new FP12(this); //w.copy(this);
		var z=new BIG(e); //z.copy(e);
		var r=new FP12(1);

		while (true)
		{
			var bt=z.parity();
			z.fshr(1);
			if (bt==1) r.mul(w);
			if (z.iszilch()) break;
			w.usqr();
		}
		r.reduce();
		return r;
	},

/* constant time powering by small integer of max length bts */
	pinpow: function(e,bts)
	{
		var i,b;
		var R=[];
		R[0]=new FP12(1);
		R[1]=new FP12(this);
		for (i=bts-1;i>=0;i--)
		{
			b=(e>>i)&1;
			R[1-b].mul(R[b]);
			R[b].usqr();
		}
		this.copy(R[0]);
	}
};

/* convert from byte array to FP12 */
FP12.fromBytes= function(w)
{
	var i,a,b,c,d,e,f,g;
	var t=[];

	for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i];
	a=BIG.fromBytes(t);
	for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+ROM.MODBYTES];
	b=BIG.fromBytes(t);
	c=new FP2(a,b); //c.bset(a,b);

	for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+2*ROM.MODBYTES];
	a=BIG.fromBytes(t);
	for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+3*ROM.MODBYTES];
	b=BIG.fromBytes(t);
	d=new FP2(a,b); //d.bset(a,b);

	e=new FP4(c,d); //e.set(c,d);

	for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+4*ROM.MODBYTES];
	a=BIG.fromBytes(t);
	for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+5*ROM.MODBYTES];
	b=BIG.fromBytes(t);
	c=new FP2(a,b); //c.bset(a,b);

	for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+6*ROM.MODBYTES];
	a=BIG.fromBytes(t);
	for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+7*ROM.MODBYTES];
	b=BIG.fromBytes(t);
	d=new FP2(a,b);

	f=new FP4(c,d); //f.set(c,d);

	for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+8*ROM.MODBYTES];
	a=BIG.fromBytes(t);
	for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+9*ROM.MODBYTES];
	b=BIG.fromBytes(t);
	c=new FP2(a,b); //c.bset(a,b);

	for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+10*ROM.MODBYTES];
	a=BIG.fromBytes(t);
	for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+11*ROM.MODBYTES];
	b=BIG.fromBytes(t);
	d=new FP2(a,b); //d.bset(a,b);

	g=new FP4(c,d); //g.set(c,d);

	var r=new FP12(e,f,g); //r.set(e,f,g);

	return r;
};

/* p=q0^u0.q1^u1.q2^u2.q3^u3 */
/* Timing attack secure, but not cache attack secure */

FP12.pow4= function(q,u)
{
	var i,j,nb,m;
	var a=[];
	var g=[];
	var s=[];

	var c=new FP12(1);
	var p=new FP12(0);
	var t=[];

	var mt=new BIG(0);
	var w=[];

	for (i=0;i<4;i++)
		t[i]=new BIG(u[i]);

	s[0]=new FP12(0);
	s[1]=new FP12(0);

	g[0]=new FP12(q[0]); s[0].copy(q[1]); s[0].conj(); g[0].mul(s[0]);
	g[1]=new FP12(g[0]);
	g[2]=new FP12(g[0]);
	g[3]=new FP12(g[0]);
	g[4]=new FP12(q[0]); g[4].mul(q[1]);
	g[5]=new FP12(g[4]);
	g[6]=new FP12(g[4]);
	g[7]=new FP12(g[4]);

	s[1].copy(q[2]); s[0].copy(q[3]); s[0].conj(); s[1].mul(s[0]);
	s[0].copy(s[1]); s[0].conj(); g[1].mul(s[0]);
	g[2].mul(s[1]);
	g[5].mul(s[0]);
	g[6].mul(s[1]);
	s[1].copy(q[2]); s[1].mul(q[3]);
	s[0].copy(s[1]); s[0].conj(); g[0].mul(s[0]);
	g[3].mul(s[1]);
	g[4].mul(s[0]);
	g[7].mul(s[1]);

/* if power is even add 1 to power, and add q to correction */

	for (i=0;i<4;i++)
	{
		if (t[i].parity()==0)
		{
			t[i].inc(1); t[i].norm();
			c.mul(q[i]);
		}
		mt.add(t[i]); mt.norm();
	}
	c.conj();
	nb=1+mt.nbits();

/* convert exponent to signed 1-bit window */
	for (j=0;j<nb;j++)
	{
		for (i=0;i<4;i++)
		{
			a[i]=(t[i].lastbits(2)-2);
			t[i].dec(a[i]); t[i].norm(); 
			t[i].fshr(1);
		}
		w[j]=(8*a[0]+4*a[1]+2*a[2]+a[3]);
	}
	w[nb]=(8*t[0].lastbits(2)+4*t[1].lastbits(2)+2*t[2].lastbits(2)+t[3].lastbits(2));
	p.copy(g[Math.floor((w[nb]-1)/2)]);  

	for (i=nb-1;i>=0;i--)
	{
		m=w[i]>>31;
		j=(w[i]^m)-m;  /* j=abs(w[i]) */
		j=(j-1)/2;
		s[0].copy(g[j]); s[1].copy(g[j]); s[1].conj();
		p.usqr();
		p.mul(s[m&1]);
	}
	p.mul(c);  /* apply correction */
	p.reduce();
	return p;
};