version22/rust/src/fp12.rs

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

use std::fmt;
use std::str::SplitWhitespace;

#[derive(Copy, Clone)]
pub struct FP12 {
	a:FP4,
	b:FP4,
	c:FP4
}

use rom::BIG_HEX_STRING_LEN;

//mod fp;
//use fp::FP;
//mod fp2;
use fp2::FP2;
//mod fp4;
use fp4::FP4;
//mod big;
use big::BIG;
//mod dbig;
//use dbig::DBIG;
//mod rand;
//mod hash256;
//mod rom;
use rom;

impl PartialEq for FP12 {
	fn eq(&self, other: &FP12) -> bool {
		return (self.a == other.a) &&
			(self.b == other.b) &&
			(self.c == other.c);
	}
}

impl fmt::Display for FP12 {
	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
		write!(f, "FP12: [ {}, {}, {} ]", self.a, self.b, self.c)
	}
}

impl fmt::Debug for FP12 {
	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
		write!(f, "FP12: [ {}, {}, {} ]", self.a, self.b, self.c)
	}
}

impl FP12 {

	pub fn new() -> FP12 {
		FP12 {
				a: FP4::new(),
				b: FP4::new(),
				c: FP4::new()
		}
	}

	pub fn new_int(a: isize) -> FP12 {
		let mut f=FP12::new();
		f.a.copy(&FP4::new_int(a));
		f.b.zero();
		f.c.zero();
		return f;
	}	

	pub fn new_copy(x: &FP12) -> FP12 {
		let mut f=FP12::new();
		f.a.copy(&x.a);
		f.b.copy(&x.b);
		f.c.copy(&x.c);
		return f;
	}

	pub fn new_fp4s(d: &FP4,e: &FP4,f: &FP4) -> FP12 {
		let mut g=FP12::new();
		g.a.copy(d);
		g.b.copy(e);
		g.c.copy(f);
		return g;
	}	

	pub fn new_fp4(d: &FP4) -> FP12 {
		let mut g=FP12::new();
		g.a.copy(d);
		g.b.zero();
		g.c.zero();
		return g;
	}

/* reduce components mod Modulus */
	pub fn reduce(&mut self) {
		self.a.reduce();
		self.b.reduce();
		self.c.reduce();
	}

/* normalise components of w */
	pub fn norm(&mut self) {
		self.a.norm();
		self.b.norm();
		self.c.norm();
	}	

/* test self=0 ? */
	pub fn iszilch(&mut self) -> bool {
		self.reduce();
		return self.a.iszilch() && self.b.iszilch() && self.c.iszilch();
	}	

/* test self=1 ? */
	pub fn isunity(&mut self) -> bool {
		let mut one=FP4::new_int(1);
		return self.a.equals(&mut one) && self.b.iszilch() && self.c.iszilch();
	}

/* test self=x */
	pub fn equals(&mut self,x:&mut FP12) -> bool {
		return self.a.equals(&mut x.a) && self.b.equals(&mut x.b) && self.c.equals(&mut x.c);
	}

	pub fn geta(&mut self) -> FP4 {
		let f=FP4::new_copy(&self.a);
		return f;
	}

	pub fn getb(&mut self) -> FP4 {
		let f=FP4::new_copy(&self.b);
		return f;
	}

	pub fn getc(&mut self) -> FP4 {
		let f=FP4::new_copy(&self.c);
		return f;
	}	

/* copy self=x */
	pub fn copy(&mut self,x :&FP12) {
		self.a.copy(&x.a);
		self.b.copy(&x.b);
		self.c.copy(&x.c);
	}

/* set self=1 */
	pub fn one(&mut self) {
		self.a.one();
		self.b.zero();
		self.c.zero();
	}

/* this=conj(this) */
	pub fn conj(&mut self) {
		self.a.conj();
		self.b.nconj();
		self.c.conj();
	}

/* Granger-Scott Unitary Squaring */
	pub fn usqr(&mut self) {
		let mut a=FP4::new_copy(&self.a);
		let mut b=FP4::new_copy(&self.c);
		let mut c=FP4::new_copy(&self.b);
		let mut d=FP4::new();

		self.a.sqr();
		d.copy(&self.a); d.add(&self.a);
		self.a.add(&d);

		self.a.norm();
		a.nconj();

		a.dbl();
		self.a.add(&a);
		b.sqr();
		b.times_i();

		d.copy(&b); d.add(&b);
		b.add(&d);
		b.norm();

		c.sqr();
		d.copy(&c); d.add(&c);
		c.add(&d);
		c.norm();

		self.b.conj();
		self.b.dbl();
		self.c.nconj();

		self.c.dbl();
		self.b.add(&b);
		self.c.add(&c);
		self.reduce();

	}

/* Chung-Hasan SQR2 method from http://cacr.uwaterloo.ca/techreports/2006/cacr2006-24.pdf */
	pub fn sqr(&mut self) {
		let mut a=FP4::new_copy(&self.a);
		let mut b=FP4::new_copy(&self.b);
		let mut c=FP4::new_copy(&self.c);
		let mut d=FP4::new_copy(&self.a);

		a.sqr();
		b.mul(&mut self.c);
		b.dbl();
		c.sqr();
		d.mul(&mut self.b);
		d.dbl();

		self.c.add(&self.a);
		self.c.add(&self.b);
		self.c.sqr();

		self.a.copy(&a);
		a.add(&b);
		a.norm();
		a.add(&c);
		a.add(&d);
		a.norm();

		a.neg();
		b.times_i();
		c.times_i();

		self.a.add(&b);

		self.b.copy(&c); self.b.add(&d);
		self.c.add(&a);
		self.norm();
	}


/* FP12 full multiplication self=self*y */
	pub fn mul(&mut self,y: &mut FP12) {
		let mut z0=FP4::new_copy(&self.a);
		let mut z1=FP4::new();
		let mut z2=FP4::new_copy(&mut self.b);
		let mut z3=FP4::new();
		let mut t0=FP4::new_copy(&self.a);
		let mut t1=FP4::new_copy(&y.a);

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

		t0.add(&self.b);
		t1.add(&y.b);

		z1.copy(&t0); z1.mul(&mut t1);
		t0.copy(&self.b); t0.add(&self.c);

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

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

		z1.add(&t0);
		z1.norm();
		self.b.copy(&z1); self.b.add(&t1);

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

		t0.copy(&self.a); t0.add(&self.c);
		t1.copy(&y.a); t1.add(&y.c);
		t0.mul(&mut t1);
		z2.add(&t0);

		t0.copy(&self.c); t0.mul(&mut y.c);
		t1.copy(&t0); t1.neg();

		z2.norm();
		z3.norm();
		self.b.norm();

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

		z3.times_i();
		self.a.copy(&z0); self.a.add(&z3);
		self.norm();
	}

/* Special case of multiplication arises from special form of ATE pairing line function */
	pub fn smul(&mut self,y: &mut FP12) {
		let mut z0=FP4::new_copy(&self.a);
		let mut z2=FP4::new_copy(&self.b);
		let mut z3=FP4::new_copy(&self.b);
		let mut t0=FP4::new();
		let mut t1=FP4::new_copy(&y.a);
		
		z0.mul(&mut y.a);
		z2.pmul(&mut y.b.real());
		self.b.add(&self.a);
		t1.padd(&y.b.real());

		self.b.mul(&mut t1);
		z3.add(&self.c);
		z3.pmul(&mut y.b.real());

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

		self.b.add(&t0);
		self.b.norm();

		self.b.add(&t1);
		z3.add(&t1);
		z2.add(&t0);

		t0.copy(&self.a); t0.add(&self.c);
		t0.mul(&mut y.a);
		self.c.copy(&z2); self.c.add(&t0);

		z3.times_i();
		self.a.copy(&z0); self.a.add(&z3);

		self.norm();
	}

/* self=1/self */
	pub fn inverse(&mut self) {
		let mut f0=FP4::new_copy(&self.a);
		let mut f1=FP4::new_copy(&self.b);
		let mut f2=FP4::new_copy(&self.a);
		let mut f3=FP4::new();

		self.norm();
		f0.sqr();
		f1.mul(&mut self.c);
		f1.times_i();
		f0.sub(&f1);

		f1.copy(&self.c); f1.sqr();
		f1.times_i();
		f2.mul(&mut self.b);
		f1.sub(&f2);

		f2.copy(&self.b); f2.sqr();
		f3.copy(&self.a); f3.mul(&mut self.c);
		f2.sub(&f3);

		f3.copy(&self.b); f3.mul(&mut f2);
		f3.times_i();
		self.a.mul(&mut f0);
		f3.add(&self.a);
		self.c.mul(&mut f1);
		self.c.times_i();

		f3.add(&self.c);
		f3.inverse();
		self.a.copy(&f0); self.a.mul(&mut f3);
		self.b.copy(&f1); self.b.mul(&mut f3);
		self.c.copy(&f2); self.c.mul(&mut f3);
	}

/* self=self^p using Frobenius */
	pub fn frob(&mut self,f: &mut FP2) {
		let mut f2=FP2::new_copy(f);
		let mut f3=FP2::new_copy(f);

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

		self.a.frob(&mut f3);
		self.b.frob(&mut f3);
		self.c.frob(&mut f3);

		self.b.pmul(f);
		self.c.pmul(&mut f2);
	}

/* trace function */
	pub fn trace(&mut self) -> FP4 {
		let mut t=FP4::new();
		t.copy(&self.a);
		t.imul(3);
		t.reduce();
		return t;
	}

/* convert from byte array to FP12 */
	pub fn frombytes(w: &[u8]) -> FP12 {
		let mut t:[u8;rom::MODBYTES as usize]=[0;rom::MODBYTES as usize];
		let mb=rom::MODBYTES as usize;

		for i in 0..mb {t[i]=w[i]}
		let mut a=BIG::frombytes(&t);
		for i in 0..mb {t[i]=w[i+mb]}
		let mut b=BIG::frombytes(&t);
		let mut c=FP2::new_bigs(&a,&b);

		for i in 0..mb {t[i]=w[i+2*mb]}
		a=BIG::frombytes(&t);
		for i in 0..mb {t[i]=w[i+3*mb]}
		b=BIG::frombytes(&t);
		let mut d=FP2::new_bigs(&a,&b);

		let e=FP4::new_fp2s(&c,&d);


		for i in 0..mb {t[i]=w[i+4*mb]}
		a=BIG::frombytes(&t);
		for i in 0..mb {t[i]=w[i+5*mb]}
		b=BIG::frombytes(&t);
		c=FP2::new_bigs(&a,&b);

		for i in 0..mb {t[i]=w[i+6*mb]}
		a=BIG::frombytes(&t);
		for i in 0..mb {t[i]=w[i+7*mb]}
		b=BIG::frombytes(&t);
		d=FP2::new_bigs(&a,&b);

		let f=FP4::new_fp2s(&c,&d);


		for i in 0..mb {t[i]=w[i+8*mb]}
		a=BIG::frombytes(&t);
		for i in 0..mb {t[i]=w[i+9*mb]}
		b=BIG::frombytes(&t);
		
		c=FP2::new_bigs(&a,&b);

		for i in 0..mb {t[i]=w[i+10*mb]}
		a=BIG::frombytes(&t);
		for i in 0..mb {t[i]=w[i+11*mb]}
		b=BIG::frombytes(&t);
		d=FP2::new_bigs(&a,&b);

		let g=FP4::new_fp2s(&c,&d);

		return FP12::new_fp4s(&e,&f,&g);
	}

/* convert this to byte array */
	pub fn tobytes(&mut self,w: &mut [u8]) {
		let mut t:[u8;rom::MODBYTES as usize]=[0;rom::MODBYTES as usize];
		let mb=rom::MODBYTES as usize;

		self.a.geta().geta().tobytes(&mut t);
		for i in 0..mb {w[i]=t[i]}
		self.a.geta().getb().tobytes(&mut t);
		for i in 0..mb {w[i+mb]=t[i]}
		self.a.getb().geta().tobytes(&mut t);
		for i in 0..mb {w[i+2*mb]=t[i]}
		self.a.getb().getb().tobytes(&mut t);
		for i in 0..mb {w[i+3*mb]=t[i]}

		self.b.geta().geta().tobytes(&mut t);
		for i in 0..mb {w[i+4*mb]=t[i]}
		self.b.geta().getb().tobytes(&mut t);
		for i in 0..mb {w[i+5*mb]=t[i]}
		self.b.getb().geta().tobytes(&mut t);
		for i in 0..mb {w[i+6*mb]=t[i]}
		self.b.getb().getb().tobytes(&mut t);
		for i in 0..mb {w[i+7*mb]=t[i]}

		self.c.geta().geta().tobytes(&mut t);
		for i in 0..mb {w[i+8*mb]=t[i]}
		self.c.geta().getb().tobytes(&mut t);
		for i in 0..mb {w[i+9*mb]=t[i]}
		self.c.getb().geta().tobytes(&mut t);
		for i in 0..mb {w[i+10*mb]=t[i]}
		self.c.getb().getb().tobytes(&mut t);
		for i in 0..mb {w[i+11*mb]=t[i]}
	}

/* output to hex string */
	pub fn tostring(&mut self) -> String {
		return format!("[{},{},{}]",self.a.tostring(),self.b.tostring(),self.c.tostring());		
	}

	pub fn to_hex(&self) -> String {
		let mut ret: String = String::with_capacity(12 * BIG_HEX_STRING_LEN);
		ret.push_str(&format!("{} {} {}", self.a.to_hex(), self.b.to_hex(), self.c.to_hex()));
		return ret;
	}

	pub fn from_hex_iter(iter: &mut SplitWhitespace) -> FP12 {
		let mut ret:FP12 = FP12::new();
		ret.a = FP4::from_hex_iter(iter);
		ret.b = FP4::from_hex_iter(iter);
		ret.c = FP4::from_hex_iter(iter);
		return ret;
	}

	pub fn from_hex(val: String) -> FP12 {
		let mut iter = val.split_whitespace();
		return FP12::from_hex_iter(&mut iter);
	}

/* self=self^e */
	pub fn pow(&mut self,e: &mut BIG) -> FP12 {
		self.norm();
		e.norm();
		let mut w=FP12::new_copy(self);
		let mut z=BIG::new_copy(&e);
		let mut r=FP12::new_int(1);
		loop {
			let bt=z.parity();
			z.fshr(1);
			if bt==1 {r.mul(&mut w)};
			if z.iszilch() {break}
			w.usqr();
		}
		r.reduce();
		return r;
	}	

/* constant time powering by small integer of max length bts */
	pub fn pinpow(&mut self,e: i32,bts: i32) {
		let mut r:[FP12;2]=[FP12::new_int(1),FP12::new_copy(self)];
		let mut t=FP12::new();

		for i in (0..bts).rev() {
			let b:usize=((e>>i)&1) as usize;
			t.copy(&r[b]);
			r[1-b].mul(&mut t);
			r[b].usqr();
		}
		self.copy(&r[0]);
	}

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

 	pub fn pow4(q:&mut [FP12],u:&[BIG]) -> FP12 {
		let mut a:[i8;4]=[0;4];
		let mut s:[FP12;2]=[FP12::new(),FP12::new()];
		let mut g:[FP12;8]=[FP12::new(),FP12::new(),FP12::new(),FP12::new(),FP12::new(),FP12::new(),FP12::new(),FP12::new()];

		let mut c=FP12::new_int(1);
		let mut p=FP12::new();
		const CT:usize=1+rom::NLEN*(rom::BASEBITS as usize);		
		let mut w:[i8;CT]=[0;CT];

		let mut mt=BIG::new();
		let mut t:[BIG;4]=[BIG::new_copy(&u[0]),BIG::new_copy(&u[1]),BIG::new_copy(&u[2]),BIG::new_copy(&u[3])];

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


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

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

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

/* convert exponent to signed 1-bit window */
		for j in 0..nb {
			for i in 0..4 {
				a[i]=(t[i].lastbits(2)-2) as i8;
				t[i].dec(a[i] as isize); 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)) as i8;
		p.copy(&g[((w[nb] as usize)-1)/2]);

		for i in (0..nb).rev() {
			let m=w[i]>>7;
			let mut j=((w[i]^m)-m) as usize;  /* 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(&mut s[(m&1) as usize]);
		}
		p.mul(&mut c);  /* apply correction */
		p.reduce();
		return p;
	}


}
/*
fn main()
{
	let mut w=FP12::new();
}
*/