version22/rust/src/ecp2.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 ECP2 {
	x:FP2,
	y:FP2,
	z:FP2,
	inf: bool
}


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

impl fmt::Display for ECP2 {
	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
		write!(f, "ECP2: [ {}, {}, {}, {} ]", self.inf, self.x, self.y, self.z)
	}
}

impl fmt::Debug for ECP2 {
	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
		write!(f, "ECP2: [ {}, {}, {}, {} ]", self.inf, self.x, self.y, self.z)
	}
}

impl PartialEq for ECP2 {
	fn eq(&self, other: &ECP2) -> bool {
		return (self.inf == other.inf) &&
			(self.x == other.x) &&
			(self.y == other.y) &&
			(self.z == other.z);
	}
}

#[allow(non_snake_case)]
impl ECP2 {

	pub fn new() -> ECP2 {
		ECP2 {
				x: FP2::new(),
				y: FP2::new(),
				z: FP2::new(),
				inf: true
		}
	}
#[allow(non_snake_case)]
/* construct this from (x,y) - but set to O if not on curve */
	pub fn new_fp2s(ix:&FP2,iy:&FP2) -> ECP2 {
		let mut E=ECP2::new();
		E.x.copy(&ix);
		E.y.copy(&iy);
		E.z.one();

		let mut rhs=ECP2::rhs(&mut E.x);
		let mut y2=FP2::new_copy(&E.y);
		y2.sqr();
		if y2.equals(&mut rhs) {
			E.inf=false;
		} else {E.x.zero();E.inf=true}
		return E;
}

/* construct this from x - but set to O if not on curve */
	pub fn new_fp2(ix:&FP2) -> ECP2 {	
		let mut E=ECP2::new();
		E.x.copy(&ix);
		E.y.one();
		E.z.one();

		let mut rhs=ECP2::rhs(&mut E.x);
		if rhs.sqrt() {
			E.y.copy(&rhs);
			E.inf=false;
		} else {E.x.zero();E.inf=true}
		return E;
	}

/* Test this=O? */
	pub fn is_infinity(&mut self) -> bool {
		return self.inf;
	}

/* copy self=P */
	pub fn copy(&mut self,P: &ECP2) {
		self.x.copy(&P.x);
		self.y.copy(&P.y);
		self.z.copy(&P.z);
		self.inf=P.inf;
	}

/* set self=O */
	pub fn inf(&mut self) {
		self.inf=true;
		self.x.zero();
		self.y.zero();
		self.z.zero();
	}

/* set self=-self */
	pub fn neg(&mut self) {
		if self.is_infinity() {return}
		self.y.neg(); self.y.reduce();
	}	

/* Conditional move of Q to self dependant on d */
	pub fn cmove(&mut self,Q: &ECP2,d: isize) {
		self.x.cmove(&Q.x,d);
		self.y.cmove(&Q.y,d);
		self.z.cmove(&Q.z,d);

		let bd:bool;
		if d==0 {bd=false}
		else {bd=true}

		self.inf=self.inf!=(self.inf!=Q.inf)&&bd;
	}

/* return 1 if b==c, no branching */
	fn teq(b: i32,c: i32) -> isize {
		let mut x=b^c;
		x-=1;  // if x=0, x now -1
		return ((x>>31)&1) as isize;
	}

/* Constant time select from pre-computed table */
	pub fn selector(&mut self,W: &[ECP2],b: i32) {
		let mut MP=ECP2::new(); 
		let m=b>>31;
		let mut babs=(b^m)-m;

		babs=(babs-1)/2;

		self.cmove(&W[0],ECP2::teq(babs,0));  // conditional move
		self.cmove(&W[1],ECP2::teq(babs,1));
		self.cmove(&W[2],ECP2::teq(babs,2));
		self.cmove(&W[3],ECP2::teq(babs,3));
		self.cmove(&W[4],ECP2::teq(babs,4));
		self.cmove(&W[5],ECP2::teq(babs,5));
		self.cmove(&W[6],ECP2::teq(babs,6));
		self.cmove(&W[7],ECP2::teq(babs,7));
 
		MP.copy(self);
		MP.neg();
		self.cmove(&MP,(m&1) as isize);
	}	

/* Test if P == Q */
	pub fn equals(&mut self,Q :&mut ECP2) -> bool {
		if self.is_infinity() && Q.is_infinity() {return true}
		if self.is_infinity() || Q.is_infinity() {return false}

		let mut zs2=FP2::new_copy(&self.z); zs2.sqr();
		let mut zo2=FP2::new_copy(&Q.z); zo2.sqr();
		let mut zs3=FP2::new_copy(&zs2); zs3.mul(&mut self.z);
		let mut zo3=FP2::new_copy(&zo2); zo3.mul(&mut Q.z);
		zs2.mul(&mut Q.x);
		zo2.mul(&mut self.x);
		if !zs2.equals(&mut zo2) {return false}
		zs3.mul(&mut Q.y);
		zo3.mul(&mut self.y);
		if !zs3.equals(&mut zo3) {return false}

		return true;
	}

/* set to Affine - (x,y,z) to (x,y) */
	pub fn affine(&mut self) {
		if self.is_infinity() {return}
		let mut one=FP2::new_int(1);
		if self.z.equals(&mut one) {return}
		self.z.inverse();

		let mut z2=FP2::new_copy(&self.z);
		z2.sqr();
		self.x.mul(&mut z2); self.x.reduce();
		self.y.mul(&mut z2); 
		self.y.mul(&mut self.z); self.y.reduce();
		self.z.copy(&one);
	}

/* extract affine x as FP2 */
	pub fn getx(&mut self) -> FP2 {
		self.affine();
		return FP2::new_copy(&self.x);
	}

/* extract affine y as FP2 */
	pub fn gety(&mut self) -> FP2 {
		self.affine();
		return FP2::new_copy(&self.y);
	}

/* extract projective x */
	pub fn getpx(&mut self) -> FP2 {
		return FP2::new_copy(&self.x);
	}
/* extract projective y */
	pub fn getpy(&mut self) -> FP2 {
		return FP2::new_copy(&self.y);
	}
/* extract projective z */
	pub fn getpz(&mut self) -> FP2 {
		return FP2::new_copy(&self.z);
	}

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

		self.affine();
		self.x.geta().tobytes(&mut t);
		for i in 0..mb { b[i]=t[i]}
		self.x.getb().tobytes(&mut t);
		for i in 0..mb { b[i+mb]=t[i]}

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

/* convert from byte array to point */
	pub fn frombytes(b: &[u8]) -> ECP2 {
		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]=b[i]}
		let mut ra=BIG::frombytes(&t);
		for i in 0..mb {t[i]=b[i+mb]}
		let mut rb=BIG::frombytes(&t);
		let rx=FP2::new_bigs(&ra,&rb);

		for i in 0..mb {t[i]=b[i+2*mb]}
		ra.copy(&BIG::frombytes(&t));
		for i in 0..mb {t[i]=b[i+3*mb]}
		rb.copy(&BIG::frombytes(&t));
		let ry=FP2::new_bigs(&ra,&rb);

		return ECP2::new_fp2s(&rx,&ry);
	}

/* convert this to hex string */
	pub fn tostring(&mut  self) -> String {
		if self.is_infinity() {return String::from("infinity")}
		self.affine();
		return format!("({},{})",self.x.tostring(),self.y.tostring());
}

	pub fn to_hex(&self) -> String {
		let mut ret: String = String::with_capacity(7 * BIG_HEX_STRING_LEN);
		ret.push_str(&format!("{} {} {} {}", self.inf, self.x.to_hex(), self.y.to_hex(), self.z.to_hex()));
		return ret;
	}

	pub fn from_hex_iter(iter: &mut SplitWhitespace) -> ECP2 {
		let mut ret:ECP2 = ECP2::new();
		if let Some(x) = iter.next() {
			ret.inf = x == "true";
			ret.x = FP2::from_hex_iter(iter);
			ret.y = FP2::from_hex_iter(iter);
			ret.z = FP2::from_hex_iter(iter);
		}
		return ret;
	}

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

/* Calculate RHS of twisted curve equation x^3+B/i */
	pub fn rhs(x:&mut FP2) -> FP2 {
		x.norm();
		let mut r=FP2::new_copy(x);
		r.sqr();
		let mut b=FP2::new_big(&BIG::new_ints(&rom::CURVE_B));
		b.div_ip();
		r.mul(x);
		r.add(&b);

		r.reduce();
		return r;
	}

/* self+=self */
	pub fn dbl(&mut self) -> isize {
		if self.inf {return -1}
		if self.y.iszilch() {
			self.inf();
			return -1
		}

		let mut w1=FP2::new_copy(&self.x);
		let mut w2=FP2::new();
		let mut w3=FP2::new_copy(&self.x);
		let mut w8=FP2::new_copy(&self.x);

		w1.sqr();
		w8.copy(&w1);
		w8.imul(3);

		w2.copy(&self.y); w2.sqr();
		w3.copy(&self.x); w3.mul(&mut w2);
		w3.imul(4);
		w1.copy(&w3); w1.neg();
		w1.norm();

		self.x.copy(&w8); self.x.sqr();
		self.x.add(&w1);
		self.x.add(&w1);
		self.x.norm();

		self.z.mul(&mut self.y);
		self.z.dbl();

		w2.dbl();
		w2.sqr();
		w2.dbl();
		w3.sub(&self.x);
		self.y.copy(&w8); self.y.mul(&mut w3);
		w2.norm();
		self.y.sub(&w2);

		self.y.norm();
		self.z.norm();

		return 1;
	}

/* self+=Q - return 0 for add, 1 for double, -1 for O */
	pub fn add(&mut self,Q:&mut ECP2) -> isize {
		if self.inf {
			self.copy(Q);
			return -1;
		}
		if Q.inf {return -1}

		let mut aff=false;

		if Q.z.isunity() {aff=true}

		let mut a=FP2::new();
		let mut c=FP2::new();
		let mut b=FP2::new_copy(&self.z);
		let mut d=FP2::new_copy(&self.z);

		if !aff {
			a.copy(&Q.z);
			c.copy(&Q.z);

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

			a.mul(&mut self.x);
			c.mul(&mut self.y);
		} else {
			a.copy(&self.x);
			c.copy(&self.y);
	
			b.sqr();
			d.mul(&mut b);
		}

		b.mul(&mut Q.x); b.sub(&a);
		d.mul(&mut Q.y); d.sub(&c);

		if b.iszilch() {
			if d.iszilch() {
				self.dbl();
				return 1;
			} else	{
				self.inf=true;
				return -1;
			}
		}

		if !aff {self.z.mul(&mut Q.z)}
		self.z.mul(&mut b);

		let mut e=FP2::new_copy(&b); e.sqr();
		b.mul(&mut e);
		a.mul(&mut e);

		e.copy(&a);
		e.add(&a); e.add(&b);
		self.x.copy(&d); self.x.sqr(); self.x.sub(&e);

		a.sub(&self.x);
		self.y.copy(&a); self.y.mul(&mut d);
		c.mul(&mut b); self.y.sub(&c);

		self.x.norm();
		self.y.norm();
		self.z.norm();

		return 0;
	}

/* set this-=Q */
	pub fn sub(&mut self,Q :&mut ECP2) -> isize {
		Q.neg();
		let d=self.add(Q);
		Q.neg();
		return d;
	}

/* set this*=q, where q is Modulus, using Frobenius */
	pub fn frob(&mut self,x:&mut FP2) {
	 	if self.inf {return}
		let mut x2=FP2::new_copy(x);
		x2.sqr();
		self.x.conj();
		self.y.conj();
		self.z.conj();
		self.z.reduce();
		self.x.mul(&mut x2);
		self.y.mul(&mut x2);
		self.y.mul(x);
	}

/* normalises m-array of ECP2 points. Requires work vector of m FP2s */

	pub fn multiaffine(P: &mut [ECP2]) {
		let mut t1=FP2::new();
		let mut t2=FP2::new();

		let mut work:[FP2;8]=[FP2::new(),FP2::new(),FP2::new(),FP2::new(),FP2::new(),FP2::new(),FP2::new(),FP2::new()];
		let m=8;

		work[0].one();
		work[1].copy(&P[0].z);

		for i in 2..m {
			t1.copy(&work[i-1]);
			work[i].copy(&t1);
			work[i].mul(&mut P[i-1].z)
		}

		t1.copy(&work[m-1]); 
		t1.mul(&mut P[m-1].z);
		t1.inverse();
		t2.copy(&P[m-1].z);
		work[m-1].mul(&mut t1);

		let mut i=m-2;

		loop {
			if i==0 {
				work[0].copy(&t1);
				work[0].mul(&mut t2);
				break;
			}
			work[i].mul(&mut t2);
			work[i].mul(&mut t1);
			t2.mul(&mut P[i].z);
			i-=1;
		}
/* now work[] contains inverses of all Z coordinates */

		for i in 0..m {
			P[i].z.one();
			t1.copy(&work[i]); t1.sqr();
			P[i].x.mul(&mut t1);
			t1.mul(&mut work[i]);
			P[i].y.mul(&mut t1);
		}    
	}

/* self*=e */
	pub fn mul(&mut self,e: &BIG) -> ECP2 {
/* fixed size windows */
		let mut mt=BIG::new();
		let mut t=BIG::new();
		let mut P=ECP2::new();
		let mut Q=ECP2::new();
		let mut C=ECP2::new();

		if self.is_infinity() {return P}

		let mut W:[ECP2;8]=[ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new()];

		const CT:usize=1+(rom::NLEN*(rom::BASEBITS as usize)+3)/4;
		let mut w:[i8;CT]=[0;CT]; 

		self.affine();

/* precompute table */
		Q.copy(&self);
		Q.dbl();
		
		W[0].copy(&self);

		for i in 1..8 {
			C.copy(&W[i-1]);
			W[i].copy(&C);
			W[i].add(&mut Q);
		}

/* convert the table to affine */

		ECP2::multiaffine(&mut W);

/* make exponent odd - add 2P if even, P if odd */
		t.copy(&e);
		let s=t.parity();
		t.inc(1); t.norm(); let ns=t.parity(); mt.copy(&t); mt.inc(1); mt.norm();
		t.cmove(&mt,s);
		Q.cmove(&self,ns);
		C.copy(&Q);

		let nb=1+(t.nbits()+3)/4;

/* convert exponent to signed 4-bit window */
		for i in 0..nb {
			w[i]=(t.lastbits(5)-16) as i8;
			t.dec(w[i] as isize); t.norm();
			t.fshr(4);	
		}
		w[nb]=(t.lastbits(5)) as i8;
		
		P.copy(&W[((w[nb] as usize) -1)/2]);
		for i in (0..nb).rev() {
			Q.selector(&W,w[i] as i32);
			P.dbl();
			P.dbl();
			P.dbl();
			P.dbl();
			P.add(&mut Q);
		}
		P.sub(&mut C);
		P.affine();
		return P;
	}

/* P=u0.Q0+u1*Q1+u2*Q2+u3*Q3 */
	pub fn mul4(Q: &mut [ECP2],u: &[BIG]) -> ECP2 {
		let mut a:[i8;4]=[0;4];
		let mut T=ECP2::new();
		let mut C=ECP2::new();
		let mut P=ECP2::new();

		let mut W:[ECP2;8]=[ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new(),ECP2::new()];

		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])];

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

		for i in 0..4 {
			Q[i].affine();
		}

/* precompute table */

		W[0].copy(&Q[0]); W[0].sub(&mut Q[1]);
		C.copy(&W[0]); W[1].copy(&C);
		W[2].copy(&C);
		W[3].copy(&C);
		W[4].copy(&Q[0]); W[4].add(&mut Q[1]);
		C.copy(&W[4]); W[5].copy(&C);
		W[6].copy(&C);
		W[7].copy(&C);

		T.copy(&Q[2]); T.sub(&mut Q[3]);
		W[1].sub(&mut T);
		W[2].add(&mut T);
		W[5].sub(&mut T);
		W[6].add(&mut T);
		T.copy(&Q[2]); T.add(&mut Q[3]);
		W[0].sub(&mut T);
		W[3].add(&mut T);
		W[4].sub(&mut T);
		W[7].add(&mut T);

		ECP2::multiaffine(&mut W);

/* if multiplier is even add 1 to multiplier, and add P to correction */
		mt.zero(); C.inf();
		for i in 0..4 {
			if t[i].parity()==0 {
				t[i].inc(1); t[i].norm();
				C.add(&mut Q[i]);
			}
			mt.add(&t[i]); mt.norm();
		}

		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(&W[((w[nb] as usize)-1)/2]);  
		for i in (0..nb).rev() {
			T.selector(&W,w[i] as i32);
			P.dbl();
			P.add(&mut T);
		}
		P.sub(&mut C); /* apply correction */

		P.affine();
		return P;
	}

}
/*
fn main()
{
	let mut r=BIG::new_ints(&rom::MODULUS);

	let pxa=BIG::new_ints(&rom::CURVE_PXA);
	let pxb=BIG::new_ints(&rom::CURVE_PXB);
	let pya=BIG::new_ints(&rom::CURVE_PYA);
	let pyb=BIG::new_ints(&rom::CURVE_PYB);

	let fra=BIG::new_ints(&rom::CURVE_FRA);
	let frb=BIG::new_ints(&rom::CURVE_FRB);

	let mut f=FP2::new_bigs(&fra,&frb);

	let px=FP2::new_bigs(&pxa,&pxb);
	let py=FP2::new_bigs(&pya,&pyb);

	let mut P=ECP2::new_fp2s(&px,&py);

	println!("P= {}",P.tostring());

	P=P.mul(&mut r);
	println!("P= {}",P.tostring());

	let mut  Q=ECP2::new_fp2s(&px,&py);
	Q.frob(&mut f);
	println!("Q= {}",Q.tostring());
}
*/