http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/rust/src/big.rs ---------------------------------------------------------------------- diff --git a/version22/rust/src/big.rs b/version22/rust/src/big.rs new file mode 100644 index 0000000..a16fbf2 --- /dev/null +++ b/version22/rust/src/big.rs @@ -0,0 +1,1217 @@ +/* +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::cmp::Ordering; + +use rom; +use rom::Chunk; + +#[cfg(target_pointer_width = "32")] +use rom::DChunk; + +#[derive(Copy, Clone)] +pub struct BIG { + pub w: [Chunk; rom::NLEN] +} + +//mod dbig; + +use dbig::DBIG; +use rand::RAND; + +impl fmt::Display for BIG { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + let mut big = self.clone(); + write!(f, "BIG: [ {} ]", big.tostring()) + } +} + +impl fmt::Debug for BIG { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + let mut big = self.clone(); + write!(f, "BIG: [ {} ]", big.tostring()) + } +} + +impl PartialEq for BIG { + fn eq(&self, other: &BIG) -> bool { + return self.w == other.w; + } +} + +impl Ord for BIG { + fn cmp(&self, other: &BIG) -> Ordering { + let r = BIG::comp(self, other); + if r > 0 { + return Ordering::Greater; + } + if r < 0 { + return Ordering::Less; + } + return Ordering::Equal; + } +} + +impl Eq for BIG { } + +impl PartialOrd for BIG { + fn partial_cmp(&self, other: &BIG) -> Option<Ordering> { + Some(self.cmp(other)) + } +} + +impl BIG { + + pub fn new() -> BIG { + BIG { + w: [0; rom::NLEN] + } + } + + pub fn new_int(x:isize) -> BIG { + let mut s= BIG::new(); + s.w[0]=x as Chunk; + return s; + } + + pub fn new_ints(a:&[Chunk]) -> BIG { + let mut s= BIG::new(); + for i in 0..rom::NLEN {s.w[i]=a[i]} + return s; + } + + pub fn new_copy(y:&BIG) -> BIG { + let mut s= BIG::new(); + for i in 0..rom::NLEN {s.w[i]=y.w[i]} + return s; + } + + pub fn new_big(y:&BIG) -> BIG { + let mut s= BIG::new(); + for i in 0..rom::NLEN {s.w[i]=y.w[i]} + return s; + } + + pub fn new_dcopy(y:&DBIG) -> BIG { + let mut s= BIG::new(); + for i in 0..rom::NLEN {s.w[i]=y.w[i]} + return s; + } + + pub fn get(&self,i:usize) -> Chunk { + return self.w[i]; + } + + pub fn set(&mut self,i:usize,x:Chunk) { + self.w[i]=x; + } + + pub fn xortop(&mut self,x:Chunk) { + self.w[rom::NLEN-1]^=x; + } + + pub fn ortop(&mut self,x:Chunk) { + self.w[rom::NLEN-1]|=x; + } + +/* test for zero */ + pub fn iszilch(&self) -> bool { + for i in 0 ..rom::NLEN { + if self.w[i]!=0 {return false} + } + return true; + } + +/* set to zero */ + pub fn zero(&mut self) { + for i in 0 ..rom::NLEN { + self.w[i]=0 + } + } + +/* Test for equal to one */ + pub fn isunity(&self) -> bool { + for i in 1 ..rom::NLEN { + if self.w[i]!=0 {return false} + } + if self.w[0]!=1 {return false} + return true; + } + +/* set to one */ + pub fn one(&mut self) { + self.w[0]=1; + for i in 1 ..rom::NLEN { + self.w[i]=0; + } + } + +/* Copy from another BIG */ + pub fn copy(&mut self,x: &BIG) { + for i in 0 ..rom::NLEN { + self.w[i]=x.w[i] + } + } + + pub fn dcopy(&mut self,x: &DBIG) + { + for i in 0 ..rom::NLEN {self.w[i] = x.w[i]} + } + +/* calculate Field Excess */ + pub fn excess(a:&BIG) -> Chunk { + return (a.w[rom::NLEN-1]&rom::OMASK)>>(rom::MODBITS%rom::BASEBITS) + } + + pub fn ff_excess(a:&BIG) -> Chunk { + return (a.w[rom::NLEN-1]&rom::P_OMASK)>>(rom::P_MB) + } + +#[cfg(target_pointer_width = "32")] + pub fn pexceed(a: &BIG,b: &BIG) -> bool { + let ea=BIG::excess(a); + let eb=BIG::excess(b); + if ((ea+1) as DChunk)*((eb+1) as DChunk) > rom::FEXCESS as DChunk {return true} + return false + } + +#[cfg(target_pointer_width = "32")] + pub fn sexceed(a: &BIG) -> bool { + let ea=BIG::excess(a); + if ((ea+1) as DChunk)*((ea+1) as DChunk) > rom::FEXCESS as DChunk {return true} + return false + } + +#[cfg(target_pointer_width = "32")] + pub fn ff_pexceed(a: &BIG,b: &BIG) -> bool { + let ea=BIG::ff_excess(a); + let eb=BIG::ff_excess(b); + if ((ea+1) as DChunk)*((eb+1) as DChunk) > rom::P_FEXCESS as DChunk {return true} + return false; + } + +#[cfg(target_pointer_width = "32")] + pub fn ff_sexceed(a: &BIG) -> bool { + let ea=BIG::ff_excess(a); + if ((ea+1) as DChunk)*((ea+1) as DChunk) > rom::P_FEXCESS as DChunk {return true} + return false; + } + +/* Get top and bottom half of =x*y+c+r */ +#[cfg(target_pointer_width = "32")] + pub fn muladd(a: Chunk,b: Chunk,c: Chunk,r: Chunk) -> (Chunk,Chunk) { + let prod:DChunk = (a as DChunk)*(b as DChunk)+(c as DChunk)+(r as DChunk); + let bot=(prod&(rom::BMASK as DChunk)) as Chunk; + let top=(prod>>rom::BASEBITS) as Chunk; + return (top,bot); + } + +#[cfg(target_pointer_width = "64")] + pub fn pexceed(a: &BIG,b: &BIG) -> bool { + let ea=BIG::excess(a); + let eb=BIG::excess(b); + if (ea+1) > rom::FEXCESS/(eb+1) {return true} + return false + } + +#[cfg(target_pointer_width = "64")] + pub fn sexceed(a: &BIG) -> bool { + let ea=BIG::excess(a); + if (ea+1) > rom::FEXCESS/(ea+1) {return true} + return false + } + +#[cfg(target_pointer_width = "64")] + pub fn ff_pexceed(a: &BIG,b: &BIG) -> bool { + let ea=BIG::ff_excess(a); + let eb=BIG::ff_excess(b); + if (ea+1) > rom::P_FEXCESS/(eb+1) {return true} + return false; + } + +#[cfg(target_pointer_width = "64")] + pub fn ff_sexceed(a: &BIG) -> bool { + let ea=BIG::ff_excess(a); + if (ea+1) > rom::P_FEXCESS/(ea+1) {return true} + return false; + } + +#[cfg(target_pointer_width = "64")] + pub fn muladd(a: Chunk,b: Chunk,c: Chunk,r: Chunk) -> (Chunk,Chunk) { + let x0=a&rom::HMASK; + let x1=a>>rom::HBITS; + let y0=b&rom::HMASK; + let y1=b>>rom::HBITS; + let mut bot=x0*y0; + let mut top=x1*y1; + let mid=x0*y1+x1*y0; + let u0=mid&rom::HMASK; + let u1=mid>>rom::HBITS; + bot+= u0 <<rom::HBITS; + bot+=c; bot+=r; + top+=u1; + let carry=bot>>rom::BASEBITS; + bot&=rom::BMASK; + top+=carry; + return (top,bot); + } + +/* +alise BIG - force all digits < 2^rom::BASEBITS */ + pub fn norm(&mut self) -> Chunk + { + let mut carry=0 as Chunk; + for i in 0 ..rom::NLEN-1 { + let d=self.w[i]+carry; + self.w[i]=d&rom::BMASK; + carry=d>>rom::BASEBITS; + } + self.w[rom::NLEN-1]+=carry; + return (self.w[rom::NLEN-1]>>((8*rom::MODBYTES)%rom::BASEBITS)) as Chunk; + } + +/* Conditional swap of two bigs depending on d using XOR - no branches */ + pub fn cswap(&mut self,b: &mut BIG,d: isize) { + let mut c= d as Chunk; + c=!(c-1); + for i in 0 ..rom::NLEN { + let t=c&(self.w[i]^b.w[i]); + self.w[i]^=t; + b.w[i]^=t; + } + } + + pub fn cmove(&mut self,g:&BIG,d: isize) { + let b= -d as Chunk; + for i in 0 ..rom::NLEN { + self.w[i]^=(self.w[i]^g.w[i])&b; + } + } + +/* Shift right by less than a word */ + pub fn fshr(&mut self, k: usize) -> isize { + let n = k; + let w=self.w[0]&((1<<n)-1); /* shifted out part */ + for i in 0 ..rom::NLEN-1 { + self.w[i]=(self.w[i]>>k)|((self.w[i+1]<<(rom::BASEBITS-n))&rom::BMASK); + } + self.w[rom::NLEN-1]=self.w[rom::NLEN-1]>>k; + return w as isize; + } + + /* general shift right */ + pub fn shr(&mut self,k:usize) { + let n=k%rom::BASEBITS; + let m=k/rom::BASEBITS; + for i in 0 ..rom::NLEN-m-1 { + self.w[i]=(self.w[m+i]>>n)|((self.w[m+i+1]<<(rom::BASEBITS-n))&rom::BMASK) + } + self.w[rom::NLEN-m-1]=self.w[rom::NLEN-1]>>n; + for i in rom::NLEN-m ..rom::NLEN + {self.w[i]=0} + } + +/* Shift right by less than a word */ + pub fn fshl(&mut self,k:usize) -> isize { + let n=k; + self.w[rom::NLEN-1]=((self.w[rom::NLEN-1]<<n))|(self.w[rom::NLEN-2]>>(rom::BASEBITS-n)); + for i in (1 ..rom::NLEN-1).rev() { + self.w[i]=((self.w[i]<<k)&rom::BMASK)|(self.w[i-1]>>(rom::BASEBITS-n)); + } + self.w[0]=(self.w[0]<<n)&rom::BMASK; + return (self.w[rom::NLEN-1]>>((8*rom::MODBYTES)%rom::BASEBITS)) as isize /* return excess - only used in ff.c */ + } + +/* general shift left */ + pub fn shl(&mut self,k: usize) { + let n=k%rom::BASEBITS; + let m=k/rom::BASEBITS; + + self.w[rom::NLEN-1]=self.w[rom::NLEN-1-m]<<n; + if rom::NLEN>=m+2 {self.w[rom::NLEN-1]|=self.w[rom::NLEN-m-2]>>(rom::BASEBITS-n)} + for i in (m+1 ..rom::NLEN-1).rev() { + self.w[i]=((self.w[i-m]<<n)&rom::BMASK)|(self.w[i-m-1]>>(rom::BASEBITS-n)); + } + self.w[m]=(self.w[0]<<n)&rom::BMASK; + for i in 0 ..m {self.w[i]=0} + } + +/* return number of bits */ + pub fn nbits(&mut self) -> usize { + let mut k=rom::NLEN-1; + self.norm(); + while (k as isize)>=0 && self.w[k]==0 {k=k.wrapping_sub(1)} + if (k as isize) <0 {return 0} + let mut bts=rom::BASEBITS*k; + let mut c=self.w[k]; + while c!=0 {c/=2; bts+=1;} + return bts; + } + +/* Convert to Hex String */ + pub fn tostring(&mut self) -> String { + let mut s = String::new(); + let mut len=self.nbits(); + + if len%4==0 { + len/=4; + } else { + len/=4; + len+=1; + } + let mb=(rom::MODBYTES*2) as usize; + if len<mb {len=mb} + + for i in (0 ..len).rev() { + let mut b=BIG::new_copy(&self); + b.shr(i*4); + s=s + &format!("{:X}", b.w[0]&15); + } + return s; + } + + pub fn fromstring(val: String) -> BIG { + let mut res = BIG::new(); + let len = val.len(); + + let op = &val[0..1]; + let n = u8::from_str_radix(op, 16).unwrap(); + res.w[0] += n as Chunk; + + for i in 1..len { + res.shl(4); + let op = &val[i..i+1]; + let n = u8::from_str_radix(op, 16).unwrap(); + res.w[0] += n as Chunk; + } + return res; + } + + pub fn add(&mut self,r:&BIG) { + for i in 0 ..rom::NLEN { + self.w[i]+=r.w[i] + } + } + + pub fn dbl(&mut self) { + for i in 0 ..rom::NLEN { + self.w[i]+=self.w[i] + } + } + +/* return this+x */ + pub fn plus(&self,x: &BIG) -> BIG { + let mut s=BIG::new(); + for i in 0 ..rom::NLEN { + s.w[i]=self.w[i]+x.w[i]; + } + return s; + } + + pub fn inc(&mut self,x:isize) { + self.norm(); + self.w[0]+=x as Chunk; + } + +// pub fn incl(&mut self,x:Chunk) { +// self.norm(); +// self.w[0]+=x; +// } + +/* return self-x */ + pub fn minus(&self,x:& BIG) -> BIG { + let mut d=BIG::new(); + for i in 0 ..rom::NLEN { + d.w[i]=self.w[i]-x.w[i]; + } + return d; + } + +/* self-=x */ + pub fn sub(&mut self,x:&BIG) { + for i in 0 ..rom::NLEN { + self.w[i]-=x.w[i]; + } + } + +/* reverse subtract this=x-this */ + pub fn rsub(&mut self,x:&BIG) { + for i in 0 ..rom::NLEN { + self.w[i]=x.w[i]-self.w[i] + } + } + +/* self-=x, where x is int */ + pub fn dec(&mut self,x:isize) { + self.norm(); + self.w[0]-= x as Chunk; + } + +/* self*=x, where x is small int<NEXCESS */ + pub fn imul(&mut self,c: isize) { + for i in 0 ..rom::NLEN { + self.w[i]*=c as Chunk; + } + } + +/* convert this BIG to byte array */ + pub fn tobytearray(&mut self,b: &mut [u8],n:usize) { + self.norm(); + let mut c=BIG::new_copy(self); + + for i in (0 ..(rom::MODBYTES as usize)).rev() { + b[i+n]=(c.w[0]&0xff) as u8; + c.fshr(8); + } + } + +/* convert from byte array to BIG */ + pub fn frombytearray(b: &[u8],n:usize) -> BIG { + let mut m=BIG::new(); + for i in 0 ..(rom::MODBYTES as usize) { + m.fshl(8); m.w[0]+=(b[i+n]&0xff) as Chunk; + } + return m; + } + + pub fn tobytes(&mut self,b: &mut [u8]) { + self.tobytearray(b,0) + } + + pub fn frombytes(b: &[u8]) -> BIG { + return BIG::frombytearray(b,0) + } + + pub fn to_hex(&mut self) -> String { + self.tostring() + } + + pub fn from_hex(val: String) -> BIG { + BIG::fromstring(val) + } + +/* self*=x, where x is >NEXCESS */ + pub fn pmul(&mut self,c: isize) -> Chunk { + let mut carry=0 as Chunk; + self.norm(); + for i in 0 ..rom::NLEN { + let ak=self.w[i]; + let tuple=BIG::muladd(ak,c as Chunk,carry,0 as Chunk); + carry=tuple.0; self.w[i]=tuple.1; + } + return carry; + } + +/* self*=c and catch overflow in DBIG */ + pub fn pxmul(&mut self,c: isize) -> DBIG + { + let mut m=DBIG::new(); + let mut carry=0 as Chunk; + for j in 0 ..rom::NLEN { + let tuple=BIG::muladd(self.w[j],c as Chunk,carry,m.w[j]); + carry=tuple.0; m.w[j]=tuple.1; + } + m.w[rom::NLEN]=carry; + return m; + } + +/* divide by 3 */ + pub fn div3(&mut self) -> Chunk + { + let mut carry=0 as Chunk; + self.norm(); + let base=1<<rom::BASEBITS; + for i in (0 ..rom::NLEN).rev() { + let ak=carry*base+self.w[i]; + self.w[i]=ak/3; + carry=ak%3; + } + return carry; + } + +/* return a*b where result fits in a BIG */ + pub fn smul(a: &BIG,b: &BIG) -> BIG { + let mut c=BIG::new(); + for i in 0 ..rom::NLEN { + let mut carry=0 as Chunk; + for j in 0 ..rom::NLEN { + if i+j<rom::NLEN { + let tuple=BIG::muladd(a.w[i],b.w[j],carry,c.w[i+j]); + carry=tuple.0; c.w[i+j]=tuple.1; + } + } + } + return c; + } + +/* Compare a and b, return 0 if a==b, -1 if a<b, +1 if a>b. Inputs must be normalised */ + pub fn comp(a: &BIG,b: &BIG) -> isize { + for i in (0 ..rom::NLEN).rev() { + if a.w[i]==b.w[i] {continue} + if a.w[i]>b.w[i] {return 1} + else {return -1} + } + return 0; + } + +/* set x = x mod 2^m */ + pub fn mod2m(&mut self,m: usize) + { + let wd=m/rom::BASEBITS; + let bt=m%rom::BASEBITS; + let msk=(1<<bt)-1; + self.w[wd]&=msk; + for i in wd+1 ..rom::NLEN {self.w[i]=0} + } + +/* Arazi and Qi inversion mod 256 */ + pub fn invmod256(a: isize) -> isize { + let mut t1:isize=0; + let mut c=(a>>1)&1; + t1+=c; + t1&=1; + t1=2-t1; + t1<<=1; + let mut u=t1+1; + + // i=2 + let mut b=a&3; + t1=u*b; t1>>=2; + c=(a>>2)&3; + let mut t2=(u*c)&3; + t1+=t2; + t1*=u; t1&=3; + t1=4-t1; + t1<<=2; + u+=t1; + + // i=4 + b=a&15; + t1=u*b; t1>>=4; + c=(a>>4)&15; + t2=(u*c)&15; + t1+=t2; + t1*=u; t1&=15; + t1=16-t1; + t1<<=4; + u+=t1; + + return u; + } + +/* return parity */ + pub fn parity(&self) -> isize { + return (self.w[0]%2) as isize; + } + +/* return n-th bit */ + pub fn bit(&self,n: usize) -> isize { + if (self.w[n/(rom::BASEBITS as usize)]&(1<<(n%rom::BASEBITS)))>0 {return 1;} + else {return 0;} + } + +/* return n last bits */ + pub fn lastbits(&mut self,n: usize) -> isize + { + let msk = ((1<<n)-1) as Chunk; + self.norm(); + return (self.w[0]&msk) as isize; + } + +/* a=1/a mod 2^256. This is very fast! */ + pub fn invmod2m(&mut self) { + let mut u=BIG::new(); + let mut b=BIG::new(); + let mut c=BIG::new(); + + u.inc(BIG::invmod256(self.lastbits(8))); + + let mut i=8; + while i<rom::BIGBITS { + b.copy(self); + b.mod2m(i); + let mut t1=BIG::smul(&u,&b); + t1.shr(i); + c.copy(self); + c.shr(i); + c.mod2m(i); + + let mut t2=BIG::smul(&u,&c); + t2.mod2m(i); + t1.add(&t2); + b=BIG::smul(&t1,&u); + t1.copy(&b); + t1.mod2m(i); + + t2.one(); t2.shl(i); t1.rsub(&t2); t1.norm(); + t1.shl(i); + u.add(&t1); + i<<=1; + } + u.mod2m(rom::BIGBITS); + self.copy(&u); + self.norm(); + } + +/* reduce self mod m */ + pub fn rmod(&mut self,n: &BIG) { + let mut k=0; + let mut m=BIG::new_copy(n); + let mut r=BIG::new(); + self.norm(); + if BIG::comp(self,&m)<0 {return} + loop { + m.fshl(1); + k += 1; + if BIG::comp(self,&m)<0 {break} + } + + while k>0 { + m.fshr(1); + + r.copy(self); + r.sub(&m); + r.norm(); + self.cmove(&r,(1-((r.w[rom::NLEN-1]>>(rom::CHUNK-1))&1)) as isize); +/* + if BIG::comp(self,&m)>=0 { + self.sub(&m); + self.norm(); + } */ + k -= 1; + } + } + +/* divide self by m */ + pub fn div(&mut self,n: &BIG) { + let mut k=0; + self.norm(); + let mut e=BIG::new_int(1); + let mut b=BIG::new_copy(self); + let mut m=BIG::new_copy(n); + let mut r=BIG::new(); + self.zero(); + + while BIG::comp(&b,&m)>=0 { + e.fshl(1); + m.fshl(1); + k += 1; + } + + while k>0 { + m.fshr(1); + e.fshr(1); + + r.copy(&b); + r.sub(&m); + r.norm(); + let d=(1-((r.w[rom::NLEN-1]>>(rom::CHUNK-1))&1)) as isize; + b.cmove(&r,d); + r.copy(self); + r.add(&e); + r.norm(); + self.cmove(&r,d); +/* + if BIG::comp(&b,&m)>=0 { + self.add(&e); + self.norm(); + b.sub(&m); + b.norm(); + } */ + k -= 1; + } + } + +/* get 8*MODBYTES size random number */ + pub fn random(rng: &mut RAND) -> BIG { + let mut m=BIG::new(); + let mut j=0; + let mut r:u8=0; +/* generate random BIG */ + for _ in 0..8*(rom::MODBYTES as usize) { + if j==0 { + r=rng.getbyte() + } else {r>>=1} + + let b= (r as Chunk)&1; + m.shl(1); m.w[0]+=b;// m.inc(b) + j+=1; j&=7; + } + return m; + } + +/* Create random BIG in portable way, one bit at a time */ + pub fn randomnum(q: &BIG,rng: &mut RAND) -> BIG { + let mut d=DBIG::new(); + let mut j=0; + let mut r:u8=0; + for _ in 0..2*(rom::MODBITS as usize) { + if j==0 { + r=rng.getbyte(); + } else {r>>=1} + + let b= (r as Chunk)&1; + d.shl(1); d.w[0]+=b; // m.inc(b); + j+=1; j&=7; + } + let m=d.dmod(q); + return m; + } + + + /* Jacobi Symbol (this/p). Returns 0, 1 or -1 */ + pub fn jacobi(&mut self,p: &BIG) -> isize { + let mut m:usize=0; + let mut t=BIG::new(); + let mut x=BIG::new(); + let mut n=BIG::new(); + let zilch=BIG::new(); + let one=BIG::new_int(1); + if p.parity()==0 || BIG::comp(self,&zilch)==0 || BIG::comp(p,&one)<=0 {return 0} + self.norm(); + + x.copy(self); + n.copy(p); + x.rmod(p); + + while BIG::comp(&n,&one)>0 { + if BIG::comp(&x,&zilch)==0 {return 0} + let n8=n.lastbits(3) as usize; + let mut k=0; + while x.parity()==0 { + k += 1; + x.shr(1); + } + if k%2==1 {m+=(n8*n8-1)/8} + m+=(n8-1)*((x.lastbits(2) as usize)-1)/4; + t.copy(&n); + t.rmod(&x); + n.copy(&x); + x.copy(&t); + m%=2; + + } + if m==0 {return 1} + else {return -1} + } + +/* self=1/self mod p. Binary method */ + pub fn invmodp(&mut self,p: &BIG) { + self.rmod(p); + let mut u=BIG::new_copy(self); + let mut v=BIG::new_copy(p); + let mut x1=BIG::new_int(1); + let mut x2=BIG::new(); + let mut t=BIG::new(); + let one=BIG::new_int(1); + + while (BIG::comp(&u,&one) != 0 ) && (BIG::comp(&v,&one) != 0 ) { + while u.parity()==0 { + u.shr(1); + if x1.parity() != 0 { + x1.add(p); + x1.norm(); + } + x1.shr(1); + } + while v.parity()==0 { + v.shr(1); + if x2.parity() != 0 { + x2.add(p); + x2.norm(); + } + x2.shr(1); + } + if BIG::comp(&u,&v)>=0 { + u.sub(&v); + u.norm(); + if BIG::comp(&x1,&x2)>=0 {x1.sub(&x2)} + else + { + t.copy(p); + t.sub(&x2); + x1.add(&t); + } + x1.norm(); + } + else + { + v.sub(&u); + v.norm(); + if BIG::comp(&x2,&x1)>=0 {x2.sub(&x1)} + else + { + t.copy(p); + t.sub(&x1); + x2.add(&t); + } + x2.norm(); + } + } + if BIG::comp(&u,&one)==0 {self.copy(&x1)} + else {self.copy(&x2)} + } + + /* return a*b as DBIG */ +#[cfg(target_pointer_width = "32")] + pub fn mul(a: &BIG,b: &BIG) -> DBIG { + let mut c=DBIG::new(); + let rm=rom::BMASK as DChunk; + let rb=rom::BASEBITS; + // a.norm(); + // b.norm(); + + let mut d: [DChunk; rom::DNLEN] = [0; rom::DNLEN]; + for i in 0 ..rom::NLEN { + d[i]=(a.w[i] as DChunk)*(b.w[i] as DChunk); + } + let mut s=d[0]; + let mut t=s; c.w[0]=(t&rm) as Chunk; + let mut co=t>>rb; + for k in 1 ..rom::NLEN { + s+=d[k]; t=co+s; + for i in 1+k/2..k+1 + {t+=((a.w[i]-a.w[k-i]) as DChunk)*((b.w[k-i]-b.w[i]) as DChunk)} + c.w[k]=(t&rm) as Chunk; co=t>>rb; + } + for k in rom::NLEN ..2*rom::NLEN-1 { + s-=d[k-rom::NLEN]; t=co+s; + let mut i=1+k/2; + while i<rom::NLEN { + t+=((a.w[i]-a.w[k-i]) as DChunk)*((b.w[k-i]-b.w[i]) as DChunk); + i+=1; + } + + c.w[k]=(t&rm) as Chunk; co=t>>rb; + } + c.w[2*rom::NLEN-1]=co as Chunk; + return c; + } + +/* return a^2 as DBIG */ +#[cfg(target_pointer_width = "32")] + pub fn sqr(a: &BIG) -> DBIG { + let mut c=DBIG::new(); + let rm=rom::BMASK as DChunk; + let rb=rom::BASEBITS; + // a.norm(); + + let mut t=(a.w[0] as DChunk)*(a.w[0] as DChunk); + c.w[0]=(t&rm) as Chunk; let mut co=t>>rb; + t=(a.w[1] as DChunk)*(a.w[0] as DChunk); t+=t; t+=co; + c.w[1]=(t&rm) as Chunk; co=t>>rb; + + let last=rom::NLEN-(rom::NLEN%2); + let mut j=2; + while j<last { + t=(a.w[j] as DChunk)*(a.w[0] as DChunk); for i in 1 ..(j+1)/2 {t+=(a.w[j-i] as DChunk)*(a.w[i] as DChunk)} ; t+=t; t+=co; t+=(a.w[j/2] as DChunk)*(a.w[j/2] as DChunk); + c.w[j]=(t&rm) as Chunk; co=t>>rb; + t=(a.w[j+1] as DChunk)*(a.w[0] as DChunk); for i in 1 ..(j+2)/2 {t+=(a.w[j+1-i] as DChunk)*(a.w[i] as DChunk)} ; t+=t; t+=co; + c.w[j+1]=(t&rm) as Chunk; co=t>>rb; + j+=2; + } + j=last; + if rom::NLEN%2==1 { + t=(a.w[j] as DChunk)*(a.w[0] as DChunk); for i in 1 ..(j+1)/2 {t+=(a.w[j-i] as DChunk)*(a.w[i] as DChunk)} ; t+=t; t+=co; t+=(a.w[j/2] as DChunk)*(a.w[j/2] as DChunk); + c.w[j]=(t&rm) as Chunk; co=t>>rb; j += 1; + t=(a.w[rom::NLEN-1] as DChunk)*(a.w[j-rom::NLEN+1] as DChunk); for i in j-rom::NLEN+2 ..(j+1)/2 {t+=(a.w[j-i] as DChunk)*(a.w[i] as DChunk)}; t+=t; t+=co; + c.w[j]=(t&rm) as Chunk; co=t>>rb; j += 1; + } + while j<rom::DNLEN-2 { + t=(a.w[rom::NLEN-1] as DChunk)*(a.w[j-rom::NLEN+1] as DChunk); for i in j-rom::NLEN+2 ..(j+1)/2 {t+=(a.w[j-i] as DChunk)*(a.w[i] as DChunk)} ; t+=t; t+=co; t+=(a.w[j/2] as DChunk)*(a.w[j/2] as DChunk); + c.w[j]=(t&rm) as Chunk; co=t>>rb; + t=(a.w[rom::NLEN-1] as DChunk)*(a.w[j-rom::NLEN+2] as DChunk); for i in j-rom::NLEN+3 ..(j+2)/2 {t+=(a.w[j+1-i] as DChunk)*(a.w[i] as DChunk)} ; t+=t; t+=co; + c.w[j+1]=(t&rm) as Chunk; co=t>>rb; + j+=2; + } + t=(a.w[rom::NLEN-1] as DChunk)*(a.w[rom::NLEN-1] as DChunk)+co; + c.w[rom::DNLEN-2]=(t&rm) as Chunk; co=t>>rb; + c.w[rom::DNLEN-1]=co as Chunk; + + return c; + } + + +#[cfg(target_pointer_width = "32")] + fn monty(d: &mut DBIG) -> BIG { + let mut b=BIG::new(); + let md=BIG::new_ints(&rom::MODULUS); + let rm=rom::BMASK as DChunk; + let rb=rom::BASEBITS; + + let mut dd: [DChunk; rom::NLEN] = [0; rom::NLEN]; + let mut v: [Chunk; rom::NLEN] = [0; rom::NLEN]; + + b.zero(); + + let mut t=d.w[0] as DChunk; v[0]=(((t&rm) as Chunk).wrapping_mul(rom::MCONST))&rom::BMASK; t+=(v[0] as DChunk)*(md.w[0] as DChunk); let mut c=(d.w[1] as DChunk)+(t>>rb); let mut s:DChunk=0; + for k in 1 ..rom::NLEN { + t=c+s+(v[0] as DChunk)*(md.w[k] as DChunk); + let mut i=1+k/2; + while i<k { + t+=((v[k-i]-v[i]) as DChunk)*((md.w[i]-md.w[k-i]) as DChunk); + i+=1; + } + v[k]=(((t&rm) as Chunk).wrapping_mul(rom::MCONST))&rom::BMASK; t+=(v[k] as DChunk)*(md.w[0] as DChunk); c=(d.w[k+1] as DChunk)+(t>>rb); + dd[k]=(v[k] as DChunk)*(md.w[k] as DChunk); s+=dd[k]; + } + + for k in rom::NLEN ..2*rom::NLEN-1 + { + t=c+s; + let mut i=1+k/2; + while i<rom::NLEN { + t+=((v[k-i]-v[i]) as DChunk)*((md.w[i]-md.w[k-i]) as DChunk); + i+=1; + } + b.w[k-rom::NLEN]=(t&rm) as Chunk; c=(d.w[k+1] as DChunk)+(t>>rb); s-=dd[k-rom::NLEN+1]; + } + b.w[rom::NLEN-1]=(c&rm) as Chunk; + b.norm(); + return b; + } + + + +/* return a*b as DBIG */ +#[cfg(target_pointer_width = "64")] + pub fn mul(a: &BIG,b: &BIG) -> DBIG { + let mut c=DBIG::new(); + let mut carry; + + for i in 0 ..rom::NLEN { + carry=0; + for j in 0 ..rom::NLEN { + let tuple=BIG::muladd(a.w[i],b.w[j],carry,c.w[i+j]); + carry=tuple.0; c.w[i+j]=tuple.1; + } + c.w[rom::NLEN+i]=carry; + } + return c; + } + +/* return a^2 as DBIG */ +#[cfg(target_pointer_width = "64")] + pub fn sqr(a: &BIG) -> DBIG { + let mut c=DBIG::new(); + let mut carry; + + for i in 0 ..rom::NLEN { + carry=0; + for j in i+1 ..rom::NLEN { + let tuple=BIG::muladd(2*a.w[i],a.w[j],carry,c.w[i+j]); + carry=tuple.0; c.w[i+j]=tuple.1; + //carry,c.w[i+j]=muladd(2*a.w[i],a.w[j],carry,c.w[i+j]) + //carry=c.muladd(2*a.w[i],a.w[j],carry,i+j) + } + c.w[rom::NLEN+i]=carry; + } + + for i in 0 ..rom::NLEN { + let tuple=BIG::muladd(a.w[i],a.w[i],0,c.w[2*i]); + c.w[2*i]=tuple.1; + c.w[2*i+1]+=tuple.0; + //c.w[2*i+1]+=c.muladd(a.w[i],a.w[i],0,2*i) + } + c.norm(); + return c; + } + +#[cfg(target_pointer_width = "64")] + fn monty(d: &mut DBIG) -> BIG { + let mut b=BIG::new(); + let md=BIG::new_ints(&rom::MODULUS); + let mut carry; + let mut m; + for i in 0 ..rom::NLEN { + if rom::MCONST==-1 { + m=(-d.w[i])&rom::BMASK; + } else { + if rom::MCONST==1 { + m=d.w[i]; + } else { + m=(rom::MCONST.wrapping_mul(d.w[i]))&rom::BMASK; + } + } + + carry=0; + for j in 0 ..rom::NLEN { + let tuple=BIG::muladd(m,md.w[j],carry,d.w[i+j]); + carry=tuple.0; d.w[i+j]=tuple.1; + } + d.w[rom::NLEN+i]+=carry; + } + + for i in 0 ..rom::NLEN { + b.w[i]=d.w[rom::NLEN+i]; + } + b.norm(); + return b; + } + + +/* reduce a DBIG to a BIG using the appropriate form of the modulus */ +/* dd */ + pub fn modulo(d: &mut DBIG) -> BIG { + + if rom::MODTYPE==rom::PSEUDO_MERSENNE { + let mut b=BIG::new(); + let mut t=d.split(rom::MODBITS); + b.dcopy(&d); + let v=t.pmul(rom::MCONST as isize); + let tw=t.w[rom::NLEN-1]; + t.w[rom::NLEN-1] &= rom::TMASK; + t.w[0]+=rom::MCONST*((tw>>rom::TBITS)+(v<<(rom::BASEBITS-rom::TBITS))); + + b.add(&t); + b.norm(); + return b; + } + + if rom::MODTYPE==rom::MONTGOMERY_FRIENDLY + { + let mut b=BIG::new(); + for i in 0 ..rom::NLEN { + let x=d.w[i]; + + let tuple=BIG::muladd(x,rom::MCONST-1,x,d.w[rom::NLEN+i-1]); + d.w[rom::NLEN+i]+=tuple.0; d.w[rom::NLEN+i-1]=tuple.1; + } + + b.zero(); + + for i in 0 ..rom::NLEN { + b.w[i]=d.w[rom::NLEN+i]; + } + b.norm(); + return b; + } + + if rom::MODTYPE==rom::GENERALISED_MERSENNE + { // GoldiLocks Only + let mut b=BIG::new(); + let t=d.split(rom::MODBITS); + let rm2=(rom::MODBITS/2) as usize; + b.dcopy(&d); + b.add(&t); + let mut dd=DBIG::new_scopy(&t); + dd.shl(rm2); + + let mut tt=dd.split(rom::MODBITS); + let lo=BIG::new_dcopy(&dd); + b.add(&tt); + b.add(&lo); + b.norm(); + tt.shl(rm2); + b.add(&tt); + + let carry=b.w[rom::NLEN-1]>>rom::TBITS; + b.w[rom::NLEN-1]&=rom::TMASK; + b.w[0]+=carry; + + b.w[(224/rom::BASEBITS) as usize]+=carry<<(224%rom::BASEBITS); + b.norm(); + return b; + } + + if rom::MODTYPE==rom::NOT_SPECIAL { + return BIG::monty(d); + } + return BIG::new(); + } + + /* return a*b mod m */ + pub fn modmul(a: &mut BIG,b: &mut BIG,m: &BIG) -> BIG { + a.rmod(m); + b.rmod(m); + let mut d=BIG::mul(a,b); + return d.dmod(m); + } + + /* return a^2 mod m */ + pub fn modsqr(a: &mut BIG,m: &BIG) -> BIG { + a.rmod(m); + let mut d=BIG::sqr(a); + return d.dmod(m); + } + + /* return -a mod m */ + pub fn modneg(a: &mut BIG,m: &BIG) -> BIG { + a.rmod(m); + return m.minus(a); + } + + /* return this^e mod m */ + pub fn powmod(&mut self,e: &mut BIG,m: &BIG) -> BIG { + self.norm(); + e.norm(); + let mut a=BIG::new_int(1); + let mut z=BIG::new_copy(e); + let mut s=BIG::new_copy(self); + loop { + let bt=z.parity(); + z.fshr(1); + if bt==1 {a=BIG::modmul(&mut a,&mut s,m)} + if z.iszilch() {break} + s=BIG::modsqr(&mut s,m); + } + return a; + } + +} + +/* +fn main() { + let fd: [i32; rom::NLEN as usize] = [1, 2, 3, 4, 5, 6, 7, 8, 9]; + let mut x= BIG::new(); + x.inc(3); + println!("{}", x.w[0]); + let mut y= BIG::new_int(7); + println!("{}", y.w[0]); + y=BIG::new_copy(&x); + println!("{}", y.w[0]); + x.add(&y); + x.add(&y); + println!("{}", x.w[0]); + let mut z= BIG::new_ints(&fd); + println!("{}", z.w[0]); + z.shr(3); + z.norm(); + println!("{:X}", z.w[0]); + + println!("{}",z.tostring()); + + let mut a = BIG::new_int(3); + let mut m = BIG::new_ints(&MODULUS); + + println!("rom::MODULUS= {}",m.tostring()); + + let mut e = BIG::new_copy(&m); + e.dec(1); e.norm(); + println!("Exponent= {}",e.tostring()); +// for i in 0..20 +// { + a=a.powmod(&mut e,&mut m); +// a.inc(2); +// } + println!("Result= {}",a.tostring()); + +} +*/
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/rust/src/dbig.rs ---------------------------------------------------------------------- diff --git a/version22/rust/src/dbig.rs b/version22/rust/src/dbig.rs new file mode 100644 index 0000000..167cfaf --- /dev/null +++ b/version22/rust/src/dbig.rs @@ -0,0 +1,249 @@ +/* +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 rom; + +use rom::Chunk; + +//#[derive(Copy, Clone)] +pub struct DBIG { + pub w: [Chunk; rom::DNLEN] +} + +//mod big; +use big::BIG; + +impl DBIG { + pub fn new() -> DBIG { + DBIG { + w: [0; rom::DNLEN as usize] + } + } + + pub fn new_copy(y:&DBIG) -> DBIG { + let mut s= DBIG::new(); + for i in 0..rom::NLEN {s.w[i]=y.w[i]} + return s; + } + + pub fn new_scopy(x:&BIG) -> DBIG { + let mut b= DBIG::new(); + for i in 0 ..rom::NLEN { + b.w[i]=x.w[i]; + } + b.w[rom::NLEN-1]=x.get(rom::NLEN-1)&rom::BMASK; /* top word normalized */ + b.w[rom::NLEN]=x.get(rom::NLEN-1)>>rom::BASEBITS; + + for i in rom::NLEN+1 ..rom::DNLEN {b.w[i]=0} + return b; + } + +/* split DBIG at position n, return higher half, keep lower half */ + pub fn split(&mut self,n: usize) -> BIG + { + let mut t=BIG::new(); + let m=n%rom::BASEBITS; + let mut carry=self.w[rom::DNLEN-1]<<(rom::BASEBITS-m); + + for i in (rom::NLEN-1..rom::DNLEN-1).rev() { + let nw=(self.w[i]>>m)|carry; + carry= (self.w[i]<<(rom::BASEBITS-m))&rom::BMASK; + t.set(i-rom::NLEN+1,nw); + } + self.w[rom::NLEN-1]&=((1 as Chunk)<<m)-1; + return t; + } + +/* general shift left */ + pub fn shl(&mut self,k: usize) + { + let n=k%rom::BASEBITS; + let m=k/rom::BASEBITS; + self.w[rom::DNLEN-1]=((self.w[rom::DNLEN-1-m]<<n))|(self.w[rom::DNLEN-m-2]>>(rom::BASEBITS-n)); + for i in (m+1..rom::DNLEN-1).rev() { + self.w[i]=((self.w[i-m]<<n)&rom::BMASK)|(self.w[i-m-1]>>(rom::BASEBITS-n)); + } + + self.w[m]=(self.w[0]<<n)&rom::BMASK; + for i in 0 ..m {self.w[i]=0} + } + +/* general shift right */ + pub fn shr(&mut self,k: usize) { + let n=k%rom::BASEBITS; + let m=k/rom::BASEBITS; + for i in 0 ..rom::DNLEN-m-1 { + self.w[i]=(self.w[m+i]>>n)|((self.w[m+i+1]<<(rom::BASEBITS-n))&rom::BMASK); + } + self.w[rom::DNLEN-m-1]=self.w[rom::DNLEN-1]>>n; + for i in rom::DNLEN - m ..rom::DNLEN {self.w[i]=0} + } + +/* Copy from another DBIG */ + pub fn copy(&mut self,x: &DBIG) { + for i in 0 ..rom::DNLEN { + self.w[i]=x.w[i] + } + } + + pub fn cmove(&mut self,g:&DBIG,d: isize) { + let b=-d as Chunk; + for i in 0 ..rom::DNLEN { + self.w[i]^=(self.w[i]^g.w[i])&b; + } + } + +/* self-=x */ + pub fn sub(&mut self,x:&DBIG) { + for i in 0 ..rom::DNLEN { + self.w[i]-=x.w[i]; + } + } + +/* Compare a and b, return 0 if a==b, -1 if a<b, +1 if a>b. Inputs must be normalised */ + pub fn comp(a: &DBIG,b: &DBIG) -> isize { + for i in (0 ..rom::DNLEN).rev() { + if a.w[i]==b.w[i] {continue} + if a.w[i]>b.w[i] {return 1} + else {return -1} + } + return 0; + } + +/* normalise BIG - force all digits < 2^rom::BASEBITS */ + pub fn norm(&mut self) { + let mut carry=0 as Chunk; + for i in 0 ..rom::DNLEN-1 { + let d=self.w[i]+carry; + self.w[i]=d&rom::BMASK; + carry=d>>rom::BASEBITS; + } + self.w[rom::DNLEN-1]+=carry + } + +/* reduces self DBIG mod a BIG, and returns the BIG */ + pub fn dmod(&mut self,c: &BIG) -> BIG { + let mut k=0; + self.norm(); + let mut m=DBIG::new_scopy(c); + let mut dr=DBIG::new(); + + if DBIG::comp(self,&m)<0 { + let r=BIG::new_dcopy(self); + return r; + } + + loop { + m.shl(1); + k += 1; + if DBIG::comp(self,&m)<0 {break;} + } + + while k>0 { + m.shr(1); + + dr.copy(self); + dr.sub(&m); + dr.norm(); + self.cmove(&dr,(1-((dr.w[rom::DNLEN-1]>>(rom::CHUNK-1))&1)) as isize); +/* + if DBIG::comp(self,&m)>=0 { + self.sub(&m); + self.norm(); + } */ + k -= 1; + } + let r=BIG::new_dcopy(self); + return r; + } + +/* return this/c */ + pub fn div(&mut self,c: &BIG) -> BIG { + let mut k=0; + let mut m=DBIG::new_scopy(c); + let mut a=BIG::new(); + let mut e=BIG::new_int(1); + let mut dr=DBIG::new(); + let mut r=BIG::new(); + self.norm(); + + while DBIG::comp(self,&m)>=0 { + e.fshl(1); + m.shl(1); + k+=1; + } + + while k>0 { + m.shr(1); + e.shr(1); + + dr.copy(self); + dr.sub(&m); + dr.norm(); + let d=(1-((dr.w[rom::DNLEN-1]>>(rom::CHUNK-1))&1)) as isize; + self.cmove(&dr,d); + r.copy(&a); + r.add(&e); + r.norm(); + a.cmove(&r,d); +/* + if DBIG::comp(self,&m)>0 { + a.add(&e); + a.norm(); + self.sub(&m); + self.norm(); + } */ + k-=1; + } + return a; + } + +/* return number of bits */ + pub fn nbits(&mut self) -> usize { + let mut k=rom::DNLEN-1; + self.norm(); + while (k as isize)>=0 && self.w[k]==0 {k=k-1} + if (k as isize) <0 {return 0} + let mut bts=(rom::BASEBITS as usize)*k; + let mut c=self.w[k]; + while c!=0 {c/=2; bts+=1;} + return bts; + } + +/* Convert to Hex String */ + pub fn to_string(&mut self) -> String { + let mut s = String::new(); + let mut len=self.nbits(); + + if len%4==0 { + len/=4; + } else { + len/=4; + len+=1; + } + + for i in (0 ..len).rev() { + let mut b=DBIG::new_copy(&self); + b.shr(i*4); + s=s + &format!("{:X}", b.w[0]&15); + } + return s; + } + +} http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/rust/src/ecdh.rs ---------------------------------------------------------------------- diff --git a/version22/rust/src/ecdh.rs b/version22/rust/src/ecdh.rs new file mode 100644 index 0000000..1511140 --- /dev/null +++ b/version22/rust/src/ecdh.rs @@ -0,0 +1,585 @@ +/* +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 ecp::ECP; +use big::BIG; +use rand::RAND; +use hash256::HASH256; +use hash384::HASH384; +use hash512::HASH512; +use aes; +use aes::AES; +use rom; + + +pub const INVALID_PUBLIC_KEY:isize=-2; +pub const ERROR: isize=-3; +pub const INVALID: isize=-4; +pub const EFS: usize=rom::MODBYTES as usize; +pub const EGS: usize=rom::MODBYTES as usize; +pub const EAS: usize=16; +pub const EBS: usize=16; +pub const SHA256: usize=32; +pub const SHA384: usize=48; +pub const SHA512: usize=64; + +pub const HASH_TYPE: usize=SHA512; + +#[allow(non_snake_case)] + +fn inttobytes(n: usize,b:&mut [u8]) { + let mut i=b.len(); + let mut m=n; + while m>0 && i>0 { + i-=1; + b[i]=(m&0xff) as u8; + m/=256; + } +} + +fn hashit(sha: usize, a: &[u8],n: usize,b: Option<&[u8]>,pad: usize,w: &mut [u8]) { + let mut r:[u8;64]=[0;64]; + if sha==SHA256 { + let mut h=HASH256::new(); + h.process_array(a); + if n>0 {h.process_num(n as i32)} + if let Some(x) = b { + h.process_array(x); + } + let hs=h.hash(); + for i in 0..sha {r[i]=hs[i];} + } + if sha==SHA384 { + let mut h=HASH384::new(); + h.process_array(a); + if n>0 {h.process_num(n as i32)} + if let Some(x) = b { + h.process_array(x); + } + let hs=h.hash(); + for i in 0..sha {r[i]=hs[i];} + } + if sha==SHA512 { + let mut h=HASH512::new(); + h.process_array(a); + if n>0 {h.process_num(n as i32)} + if let Some(x) = b { + h.process_array(x); + } + let hs=h.hash(); + for i in 0..sha {r[i]=hs[i];} + } + + if pad==0 { + for i in 0..sha {w[i]=r[i]} + } else { + + if pad<=sha { + for i in 0..pad {w[i]=r[i]} + } else { + for i in 0..sha {w[i]=r[i]} + for i in sha..pad {w[i]=0} + } + } +} + +/* Key Derivation Functions */ +/* Input octet Z */ +/* Output key of length olen */ +pub fn kdf1(sha: usize,z: &[u8],olen: usize,k: &mut [u8]) { +/* NOTE: the parameter olen is the length of the output K in bytes */ + let hlen=sha; + let mut lk=0; + + let mut cthreshold=olen/hlen; if olen%hlen!=0 {cthreshold+=1} + + for counter in 0..cthreshold { + let mut b:[u8;64]=[0;64]; + hashit(sha,z,counter,None,0,&mut b); + if lk+hlen>olen { + for i in 0..(olen%hlen) {k[lk]=b[i]; lk+=1} + } else { + for i in 0..hlen {k[lk]=b[i]; lk+=1} + } + } +} + +pub fn kdf2(sha: usize,z: &[u8],p: Option<&[u8]>,olen: usize,k: &mut [u8]) { +/* NOTE: the parameter olen is the length of the output K in bytes */ + let hlen=sha; + let mut lk=0; + + let mut cthreshold=olen/hlen; if olen%hlen!=0 {cthreshold+=1} + + for counter in 1..cthreshold+1 { + let mut b:[u8;64]=[0;64]; + hashit(sha,z,counter,p,0,&mut b); + if lk+hlen>olen { + for i in 0..(olen%hlen) {k[lk]=b[i]; lk+=1} + } else { + for i in 0..hlen {k[lk]=b[i]; lk+=1} + } + } +} + +/* Password based Key Derivation Function */ +/* Input password p, salt s, and repeat count */ +/* Output key of length olen */ +pub fn pbkdf2(sha: usize,pass: &[u8],salt: &[u8],rep: usize,olen: usize,k: &mut [u8]) { + let mut d=olen/sha; if olen%sha!=0 {d+=1} + let mut f:[u8;64]=[0;64]; + let mut u:[u8;64]=[0;64]; + let mut ku:[u8;64]=[0;64]; + let mut s:[u8;36]=[0;36]; // Maximum salt of 32 bytes + 4 + let mut n:[u8;4]=[0;4]; + + let sl=salt.len(); + let mut kp=0; + for i in 0..d { + for j in 0..sl {s[j]=salt[j]} + inttobytes(i+1,&mut n); + for j in 0..4 {s[sl+j]=n[j]} + + hmac(sha,&s[0..sl+4],pass,sha,&mut f); + + for j in 0..sha {u[j]=f[j]} + for _ in 1..rep { + hmac(sha,&mut u,pass,sha,&mut ku); + for k in 0..sha {u[k]=ku[k]; f[k]^=u[k]} + } + for j in 0..EFS {if kp<olen {k[kp]=f[j]} kp+=1} + } +} + +/* Calculate HMAC of m using key k. HMAC is tag of length olen (which is length of tag) */ +pub fn hmac(sha: usize,m: &[u8],k: &[u8],olen: usize,tag: &mut [u8]) -> bool { + /* Input is from an octet m * + * olen is requested output length in bytes. k is the key * + * The output is the calculated tag */ + let mut b:[u8;64]=[0;64]; /* Not good */ + let mut k0:[u8;128]=[0;128]; +// let olen=tag.len(); /* length of HMAC */ + + if olen<4 /*|| olen>sha */ {return false} + + let mut lb=64; + if sha>32 {lb=128} + + for i in 0..lb {k0[i]=0} + + if k.len() > lb { + hashit(sha,k,0,None,0,&mut b); + for i in 0..sha {k0[i]=b[i]} + } else { + for i in 0..k.len() {k0[i]=k[i]} + } + + for i in 0..lb {k0[i]^=0x36} + hashit(sha,&mut k0[0..lb],0,Some(m),0,&mut b); + + for i in 0..lb {k0[i]^=0x6a} + hashit(sha,&mut k0[0..lb],0,Some(&b[0..sha]),olen,tag); + + return true; +} + +/* AES encryption/decryption. Encrypt byte array m using key k and returns ciphertext c */ +pub fn cbc_iv0_encrypt(k: &[u8],m: &[u8]) -> Vec<u8> { /* AES CBC encryption, with Null IV and key K */ + /* Input is from an octet string m, output is to an octet string c */ + /* Input is padded as necessary to make up a full final block */ + let mut a=AES::new(); + let mut fin=false; + let mut c:Vec<u8>=Vec::new(); + + let mut buff:[u8;16]=[0;16]; + + a.init(aes::CBC,k.len(),k,None); + + let mut ipt=0; +// let mut opt=0; + let mut i; + loop { + i=0; + while i<16 { + if ipt<m.len() { + buff[i]=m[ipt]; i+=1; ipt+=1; + } else {fin=true; break;} + } + if fin {break} + a.encrypt(&mut buff); + for j in 0..16 { + c.push(buff[j]); + //c[opt]=buff[j]; opt+=1; + } + } + +/* last block, filled up to i-th index */ + + let padlen=16-i; + for j in i..16 {buff[j]=padlen as u8} + + a.encrypt(&mut buff); + + for j in 0..16 { + c.push(buff[j]); + //c[opt]=buff[j]; opt+=1; + } + a.end(); + return c; +} + +/* returns plaintext if all consistent, else returns null string */ +pub fn cbc_iv0_decrypt(k: &[u8],c: &[u8]) -> Option<Vec<u8>> { /* padding is removed */ + let mut a=AES::new(); + let mut fin=false; + let mut m:Vec<u8>=Vec::new(); + + let mut buff:[u8;16]=[0;16]; + + a.init(aes::CBC,k.len(),k,None); + + let mut ipt=0; + //let mut opt=0; + let mut i; + + if c.len()==0 {return None} + let mut ch=c[ipt]; ipt+=1; + + loop { + i=0; + while i<16 { + buff[i]=ch; + if ipt>=c.len() { + fin=true; break; + } else {ch=c[ipt]; ipt+=1 } + i+=1; + } + a.decrypt(&mut buff); + if fin {break} + for j in 0..16 { + m.push(buff[j]); + //m[opt]=buff[j]; opt+=1; + } + } + + a.end(); + let mut bad=false; + let padlen=buff[15] as usize; + if i!=15 || padlen<1 || padlen>16 {bad=true} + if padlen>=2 && padlen<=16 { + for j in 16-padlen..16 { + if buff[j]!=padlen as u8 {bad=true} + } + } + + if !bad { + for _ in 0..16-padlen { + m.push(buff[i]); + //m[opt]=buff[j]; opt+=1; + } + } + + if bad {return None} + return Some(m); +} + +/* Calculate a public/private EC GF(p) key pair w,s where W=s.G mod EC(p), + * where s is the secret key and W is the public key + * and G is fixed generator. + * If RNG is NULL then the private key is provided externally in s + * otherwise it is generated randomly internally */ + #[allow(non_snake_case)] +pub fn key_pair_generate(rng: Option<&mut RAND>,s: &mut [u8],w: &mut [u8]) -> isize { + let res=0; + let mut sc:BIG; + let mut G:ECP; + + let gx=BIG::new_ints(&rom::CURVE_GX); + + if rom::CURVETYPE!=rom::MONTGOMERY { + let gy=BIG::new_ints(&rom::CURVE_GY); + G=ECP::new_bigs(&gx,&gy); + } else { + G=ECP::new_big(&gx); + } + + let r=BIG::new_ints(&rom::CURVE_ORDER); + + if let Some(mut x)=rng { + sc=BIG::randomnum(&r,&mut x); + } else { + sc=BIG::frombytes(&s); + sc.rmod(&r); + } + + if rom::AES_S>0 { + sc.mod2m(2*rom::AES_S) + } + sc.tobytes(s); + + let mut WP=G.mul(&mut sc); + + WP.tobytes(w); + + return res; +} + +/* validate public key. Set full=true for fuller check */ +#[allow(non_snake_case)] +pub fn public_key_validate(full: bool,w: &[u8]) -> isize { + let mut WP=ECP::frombytes(w); + let mut res=0; + + let mut r=BIG::new_ints(&rom::CURVE_ORDER); + + if WP.is_infinity() {res=INVALID_PUBLIC_KEY} + if res==0 && full { + WP=WP.mul(&mut r); + if !WP.is_infinity() {res=INVALID_PUBLIC_KEY} + } + return res; +} + +/* IEEE-1363 Diffie-Hellman online calculation Z=S.WD */ +#[allow(non_snake_case)] +pub fn ecpsvdp_dh(s: &[u8],wd: &[u8],z: &mut [u8]) -> isize { + let mut res=0; + let mut t:[u8;EFS]=[0;EFS]; + + let mut sc=BIG::frombytes(&s); + + let mut W=ECP::frombytes(&wd); + if W.is_infinity() {res=ERROR} + + if res==0 { + let r=BIG::new_ints(&rom::CURVE_ORDER); + sc.rmod(&r); + W=W.mul(&mut sc); + if W.is_infinity() { + res=ERROR; + } else { + W.getx().tobytes(&mut t); + for i in 0..EFS {z[i]=t[i]} + } + } + return res; +} + +/* IEEE ECDSA Signature, C and D are signature on F using private key S */ +#[allow(non_snake_case)] +pub fn ecpsp_dsa(sha: usize,rng: &mut RAND,s: &[u8],f: &[u8],c: &mut [u8],d: &mut [u8]) -> isize { + let mut t:[u8;EFS]=[0;EFS]; + let mut b:[u8;rom::MODBYTES as usize]=[0;rom::MODBYTES as usize]; + + hashit(sha,f,0,None,rom::MODBYTES as usize,&mut b); + + let gx=BIG::new_ints(&rom::CURVE_GX); + let gy=BIG::new_ints(&rom::CURVE_GY); + + let G=ECP::new_bigs(&gx,&gy); + let r=BIG::new_ints(&rom::CURVE_ORDER); + + let mut sc=BIG::frombytes(s); /* s or &s? */ + let fb=BIG::frombytes(&b); + + let mut cb=BIG::new(); + let mut db=BIG::new(); + let mut tb=BIG::new(); + let mut V=ECP::new(); + + while db.iszilch() { + let mut u=BIG::randomnum(&r,rng); + let mut w=BIG::randomnum(&r,rng); + if rom::AES_S>0 { + u.mod2m(2*rom::AES_S); + } + V.copy(&G); + V=V.mul(&mut u); + let vx=V.getx(); + cb.copy(&vx); + cb.rmod(&r); + if cb.iszilch() {continue} + + tb.copy(&BIG::modmul(&mut u,&mut w,&r)); + u.copy(&tb); + + u.invmodp(&r); + db.copy(&BIG::modmul(&mut sc,&mut cb,&r)); + db.add(&fb); + + tb.copy(&BIG::modmul(&mut db,&mut w,&r)); + db.copy(&tb); + + tb.copy(&BIG::modmul(&mut u,&mut db,&r)); + db.copy(&tb); + } + + cb.tobytes(&mut t); + for i in 0..EFS {c[i]=t[i]} + db.tobytes(&mut t); + for i in 0..EFS {d[i]=t[i]} + return 0; +} + +/* IEEE1363 ECDSA Signature Verification. Signature C and D on F is verified using public key W */ +#[allow(non_snake_case)] +pub fn ecpvp_dsa(sha: usize,w: &[u8],f: &[u8],c: &[u8],d: &[u8]) -> isize { + let mut res=0; + + let mut b:[u8;rom::MODBYTES as usize]=[0;rom::MODBYTES as usize]; + + hashit(sha,f,0,None,rom::MODBYTES as usize,&mut b); + + let gx=BIG::new_ints(&rom::CURVE_GX); + let gy=BIG::new_ints(&rom::CURVE_GY); + + let mut G=ECP::new_bigs(&gx,&gy); + let r=BIG::new_ints(&rom::CURVE_ORDER); + + let mut cb=BIG::frombytes(c); /* c or &c ? */ + let mut db=BIG::frombytes(d); /* d or &d ? */ + let mut fb=BIG::frombytes(&b); + let mut tb=BIG::new(); + + if cb.iszilch() || BIG::comp(&cb,&r)>=0 || db.iszilch() || BIG::comp(&db,&r)>=0 { + res=INVALID; + } + + if res==0 { + db.invmodp(&r); + tb.copy(&BIG::modmul(&mut fb,&mut db,&r)); + fb.copy(&tb); + let h2=BIG::modmul(&mut cb,&mut db,&r); + + let mut WP=ECP::frombytes(&w); + if WP.is_infinity() { + res=ERROR; + } else { + let mut P=ECP::new(); + P.copy(&WP); + + P=P.mul2(&h2,&mut G,&fb); + + if P.is_infinity() { + res=INVALID; + } else { + db=P.getx(); + db.rmod(&r); + + if BIG::comp(&db,&cb)!=0 {res=INVALID} + } + } + } + + return res; +} + +/* IEEE1363 ECIES encryption. Encryption of plaintext M uses public key W and produces ciphertext V,C,T */ +#[allow(non_snake_case)] +pub fn ecies_encrypt(sha: usize,p1: &[u8],p2: &[u8],rng: &mut RAND,w: &[u8],m: &[u8],v: &mut [u8],t: &mut [u8]) -> Option<Vec<u8>> { + let mut z:[u8;EFS]=[0;EFS]; + let mut k1:[u8;EAS]=[0;EAS]; + let mut k2:[u8;EAS]=[0;EAS]; + let mut u:[u8;EGS]=[0;EGS]; + let mut vz:[u8;3*EFS+1]=[0;3*EFS+1]; + let mut k:[u8;EFS]=[0;EFS]; + + if key_pair_generate(Some(rng),&mut u,v)!=0 {return None} + if ecpsvdp_dh(&u,&w,&mut z)!=0 {return None} + + for i in 0..2*EFS+1 {vz[i]=v[i]} + for i in 0..EFS {vz[2*EFS+1+i]=z[i]} + + + kdf2(sha,&vz,Some(p1),EFS,&mut k); + + for i in 0..EAS {k1[i]=k[i]; k2[i]=k[EAS+i]} + + let mut c=cbc_iv0_encrypt(&k1,m); + + let mut l2:[u8;8]=[0;8]; + let p2l=p2.len(); + + inttobytes(p2l,&mut l2); + + for i in 0..p2l { + c.push(p2[i]); + } + for i in 0..8 { + c.push(l2[i]); + } + + hmac(sha,&c,&k2,t.len(),t); + + for _ in 0..p2l+8 {c.pop();} + + return Some(c); +} + +/* IEEE1363 ECIES decryption. Decryption of ciphertext V,C,T using private key U outputs plaintext M */ +#[allow(non_snake_case)] +pub fn ecies_decrypt(sha: usize,p1: &[u8],p2: &[u8],v: &[u8],c: &mut Vec<u8>,t: &[u8],u: &[u8]) -> Option<Vec<u8>> { + let mut z:[u8;EFS]=[0;EFS]; + let mut k1:[u8;EAS]=[0;EAS]; + let mut k2:[u8;EAS]=[0;EAS]; + let mut vz:[u8;3*EFS+1]=[0;3*EFS+1]; + let mut k:[u8;EFS]=[0;EFS]; + + let mut tag:[u8;32]=[0;32]; /* 32 is max length of tag */ + + for i in 0..t.len() {tag[i]=t[i]} + + if ecpsvdp_dh(&u,&v,&mut z)!=0 {return None} + + for i in 0..2*EFS+1 {vz[i]=v[i]} + for i in 0..EFS {vz[2*EFS+1+i]=z[i]} + + kdf2(sha,&vz,Some(p1),EFS,&mut k); + + for i in 0..EAS {k1[i]=k[i]; k2[i]=k[EAS+i]} + + let m=cbc_iv0_decrypt(&k1,&c); + + if m==None {return None} + + let mut l2:[u8;8]=[0;8]; + let p2l=p2.len(); + + inttobytes(p2l,&mut l2); + + for i in 0..p2l { + c.push(p2[i]); + } + for i in 0..8 { + c.push(l2[i]); + } + + hmac(sha,&c,&k2,t.len(),&mut tag); + + for _ in 0..p2l+8 {c.pop();} + + let mut same=true; + for i in 0..t.len() { + if t[i]!=tag[i] {same=false} + } + if !same {return None} + + return m; +} + http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/rust/src/ecp.rs ---------------------------------------------------------------------- diff --git a/version22/rust/src/ecp.rs b/version22/rust/src/ecp.rs new file mode 100644 index 0000000..cfd4772 --- /dev/null +++ b/version22/rust/src/ecp.rs @@ -0,0 +1,955 @@ +/* +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 ECP { + x:FP, + y:FP, + z:FP, + inf: bool +} + + +//use rom; +//mod fp; +use fp::FP; +//mod big; +use big::BIG; +//mod dbig; +//use dbig::DBIG; +//mod rand; +//mod hash256; +//mod rom; +use rom; +use rom::BIG_HEX_STRING_LEN; + +impl fmt::Display for ECP { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f, "ECP: [ {}, {}, {}, {} ]", self.inf, self.x, self.y, self.z) + } +} + +impl fmt::Debug for ECP { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f, "ECP: [ {}, {}, {}, {} ]", self.inf, self.x, self.y, self.z) + } +} + +impl PartialEq for ECP { + fn eq(&self, other: &ECP) -> bool { + return (self.inf == other.inf) && + (self.x == other.x) && + (self.y == other.y) && + (self.z == other.z); + } +} + +#[allow(non_snake_case)] +impl ECP { + + pub fn new() -> ECP { + ECP { + x: FP::new(), + y: FP::new(), + z: FP::new(), + inf: true + } + } + +/* set (x,y) from two BIGs */ + pub fn new_bigs(ix: &BIG,iy: &BIG) -> ECP { + let mut E=ECP::new(); + E.x.bcopy(ix); + E.y.bcopy(iy); + E.z.one(); + let mut rhs=ECP::rhs(&mut E.x); + if rom::CURVETYPE==rom::MONTGOMERY { + if rhs.jacobi()==1 { + E.inf=false; + } else {E.inf()} + } else { + let mut y2=FP::new_copy(&E.y); + y2.sqr(); + if y2.equals(&mut rhs) { + E.inf=false + } else {E.inf()} + } + return E; + } + +/* set (x,y) from BIG and a bit */ + pub fn new_bigint(ix: &BIG,s: isize) -> ECP { + let mut E=ECP::new(); + E.x.bcopy(ix); + E.z.one(); + + let mut rhs=ECP::rhs(&mut E.x); + + if rhs.jacobi()==1 { + let mut ny=rhs.sqrt(); + if ny.redc().parity()!=s {ny.neg()} + E.y.copy(&ny); + E.inf=false; + } else {E.inf()} + return E; + } + +#[allow(non_snake_case)] +/* set from x - calculate y from curve equation */ + pub fn new_big(ix: &BIG) -> ECP { + let mut E=ECP::new(); + E.x.bcopy(ix); + E.z.one(); + let mut rhs=ECP::rhs(&mut E.x); + if rhs.jacobi()==1 { + if rom::CURVETYPE!=rom::MONTGOMERY {E.y.copy(&rhs.sqrt())} + E.inf=false; + } else {E.inf=true} + return E; + } + +/* set this=O */ + pub fn inf(&mut self) { + self.inf=true; + self.x.zero(); + self.y.one(); + self.z.one(); + } + +/* Calculate RHS of curve equation */ + fn rhs(x: &mut FP) -> FP { + x.norm(); + let mut r=FP::new_copy(x); + r.sqr(); + + if rom::CURVETYPE==rom::WEIERSTRASS { // x^3+Ax+B + let b=FP::new_big(&BIG::new_ints(&rom::CURVE_B)); + r.mul(x); + if rom::CURVE_A==-3 { + let mut cx=FP::new_copy(x); + cx.imul(3); + cx.neg(); cx.norm(); + r.add(&cx); + } + r.add(&b); + } + if rom::CURVETYPE==rom::EDWARDS { // (Ax^2-1)/(Bx^2-1) + let mut b=FP::new_big(&BIG::new_ints(&rom::CURVE_B)); + let one=FP::new_int(1); + b.mul(&mut r); + b.sub(&one); + if rom::CURVE_A==-1 {r.neg()} + r.sub(&one); + b.inverse(); + r.mul(&mut b); + } + if rom::CURVETYPE==rom::MONTGOMERY { // x^3+Ax^2+x + let mut x3=FP::new(); + x3.copy(&r); + x3.mul(x); + r.imul(rom::CURVE_A); + r.add(&x3); + r.add(&x); + } + r.reduce(); + return r; + } + +/* test for O point-at-infinity */ + pub fn is_infinity(&mut self) -> bool { + if rom::CURVETYPE==rom::EDWARDS { + self.x.reduce(); self.y.reduce(); self.z.reduce(); + return self.x.iszilch() && self.y.equals(&mut self.z); + } else {return self.inf} + } + +/* Conditional swap of P and Q dependant on d */ + pub fn cswap(&mut self,Q: &mut ECP,d: isize) { + self.x.cswap(&mut Q.x,d); + if rom::CURVETYPE!=rom::MONTGOMERY {self.y.cswap(&mut Q.y,d)} + self.z.cswap(&mut Q.z,d); + if rom::CURVETYPE!=rom::EDWARDS { + let mut bd=true; + if d==0 {bd=false} + bd=bd&&(self.inf!=Q.inf); + self.inf=bd!=self.inf; + Q.inf=bd!=Q.inf; + } + } + +/* Conditional move of Q to P dependant on d */ + pub fn cmove(&mut self,Q: &ECP,d: isize) { + self.x.cmove(&Q.x,d); + if rom::CURVETYPE!=rom::MONTGOMERY {self.y.cmove(&Q.y,d)} + self.z.cmove(&Q.z,d); + if rom::CURVETYPE!=rom::EDWARDS { + let mut bd=true; + if d==0 {bd=false} + 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; + } + +/* this=P */ + pub fn copy(&mut self,P: & ECP) { + self.x.copy(&P.x); + if rom::CURVETYPE!=rom::MONTGOMERY {self.y.copy(&P.y)} + self.z.copy(&P.z); + self.inf=P.inf; +} + +/* this=-this */ + pub fn neg(&mut self) { + if self.is_infinity() {return} + if rom::CURVETYPE==rom::WEIERSTRASS { + self.y.neg(); self.y.norm(); + } + if rom::CURVETYPE==rom::EDWARDS { + self.x.neg(); self.x.norm(); + } + return; + } +/* multiply x coordinate */ + pub fn mulx(&mut self,c: &mut FP) { + self.x.mul(c); + } + +/* Constant time select from pre-computed table */ + fn selector(&mut self, W: &[ECP],b: i32) { // unsure about &[& syntax. An array of pointers I hope.. + let mut MP=ECP::new(); + let m=b>>31; + let mut babs=(b^m)-m; + + babs=(babs-1)/2; + + self.cmove(&W[0],ECP::teq(babs,0)); // conditional move + self.cmove(&W[1],ECP::teq(babs,1)); + self.cmove(&W[2],ECP::teq(babs,2)); + self.cmove(&W[3],ECP::teq(babs,3)); + self.cmove(&W[4],ECP::teq(babs,4)); + self.cmove(&W[5],ECP::teq(babs,5)); + self.cmove(&W[6],ECP::teq(babs,6)); + self.cmove(&W[7],ECP::teq(babs,7)); + + MP.copy(self); + MP.neg(); + self.cmove(&MP,(m&1) as isize); + } + +/* Test P == Q */ + pub fn equals(&mut self,Q: &mut ECP) -> bool { + if self.is_infinity() && Q.is_infinity() {return true} + if self.is_infinity() || Q.is_infinity() {return false} + if rom::CURVETYPE==rom::WEIERSTRASS { + let mut zs2=FP::new_copy(&self.z); zs2.sqr(); + let mut zo2=FP::new_copy(&Q.z); zo2.sqr(); + let mut zs3=FP::new_copy(&zs2); zs3.mul(&mut self.z); + let mut zo3=FP::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} + } else { + let mut a=FP::new(); + let mut b=FP::new(); + a.copy(&self.x); a.mul(&mut Q.z); a.reduce(); + b.copy(&Q.x); b.mul(&mut self.z); b.reduce(); + if !a.equals(&mut b) {return false} + if rom::CURVETYPE==rom::EDWARDS { + a.copy(&self.y); a.mul(&mut Q.z); a.reduce(); + b.copy(&Q.y); b.mul(&mut self.z); b.reduce(); + if !a.equals(&mut b) {return false} + } + } + return true; + } + +/* set to affine - from (x,y,z) to (x,y) */ + pub fn affine(&mut self) { + if self.is_infinity() {return} + let mut one=FP::new_int(1); + if self.z.equals(&mut one) {return} + self.z.inverse(); + if rom::CURVETYPE==rom::WEIERSTRASS { + let mut z2=FP::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(); + } + if rom::CURVETYPE==rom::EDWARDS { + self.x.mul(&mut self.z); self.x.reduce(); + self.y.mul(&mut self.z); self.y.reduce(); + } + if rom::CURVETYPE==rom::MONTGOMERY { + self.x.mul(&mut self.z); self.x.reduce(); + } + self.z.one(); + } + +/* extract x as a BIG */ + pub fn getx(&mut self) -> BIG { + self.affine(); + return self.x.redc(); + } + +/* extract y as a BIG */ + pub fn gety(&mut self) -> BIG { + self.affine(); + return self.y.redc(); + } + +/* get sign of Y */ + pub fn gets(&mut self) -> isize { + self.affine(); + let y=self.gety(); + return y.parity(); + } + +/* extract x as an FP */ + pub fn getpx(&self) -> FP { + let w=FP::new_copy(&self.x); + return w; + } +/* extract y as an FP */ + pub fn getpy(&self) -> FP { + let w=FP::new_copy(&self.y); + return w; + } + +/* extract z as an FP */ + pub fn getpz(&self) -> FP { + let w=FP::new_copy(&self.z); + return w; + } + +/* convert to byte array */ + pub fn tobytes(&mut self,b: &mut [u8]) { + let mb=rom::MODBYTES as usize; + let mut t:[u8;rom::MODBYTES as usize]=[0;rom::MODBYTES as usize]; + if rom::CURVETYPE!=rom::MONTGOMERY { + b[0]=0x04; + } else {b[0]=0x02} + + self.affine(); + self.x.redc().tobytes(&mut t); + for i in 0..mb {b[i+1]=t[i]} + if rom::CURVETYPE!=rom::MONTGOMERY { + self.y.redc().tobytes(&mut t); + for i in 0..mb {b[i+mb+1]=t[i]} + } + } + +/* convert from byte array to point */ + pub fn frombytes(b: &[u8]) -> ECP { + let mut t:[u8;rom::MODBYTES as usize]=[0;rom::MODBYTES as usize]; + let mb=rom::MODBYTES as usize; + let p=BIG::new_ints(&rom::MODULUS); + + for i in 0..mb {t[i]=b[i+1]} + let px=BIG::frombytes(&t); + if BIG::comp(&px,&p)>=0 {return ECP::new()} + + if b[0]==0x04 { + for i in 0..mb {t[i]=b[i+mb+1]} + let py=BIG::frombytes(&t); + if BIG::comp(&py,&p)>=0 {return ECP::new()} + return ECP::new_bigs(&px,&py); + } else {return ECP::new_big(&px)} + } + + pub fn to_hex(&self) -> String { + let mut ret: String = String::with_capacity(4 * 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) -> ECP { + let mut ret:ECP = ECP::new(); + if let Some(x) = iter.next() { + ret.inf = x == "true"; + ret.x = FP::from_hex(iter.next().unwrap_or("").to_string()); + ret.y = FP::from_hex(iter.next().unwrap_or("").to_string()); + ret.z = FP::from_hex(iter.next().unwrap_or("").to_string()); + } + return ret; + } + + pub fn from_hex(val: String) -> ECP { + let mut iter = val.split_whitespace(); + return ECP::from_hex_iter(&mut iter); + } + +/* convert to hex string */ + pub fn tostring(&mut self) -> String { + if self.is_infinity() {return String::from("infinity")} + self.affine(); + if rom::CURVETYPE==rom::MONTGOMERY { + return format!("({})",self.x.redc().tostring()); + } else {return format!("({},{})",self.x.redc().tostring(),self.y.redc().tostring())} ; + } + +/* this*=2 */ + pub fn dbl(&mut self) { + if rom::CURVETYPE==rom::WEIERSTRASS { + if self.inf {return} + if self.y.iszilch() { + self.inf(); + return; + } + + let mut w1=FP::new_copy(&self.x); + let mut w6=FP::new_copy(&self.z); + let mut w2=FP::new(); + let mut w3=FP::new_copy(&self.x); + let mut w8=FP::new_copy(&self.x); + + if rom::CURVE_A==-3 { + w6.sqr(); + w1.copy(&w6); + w1.neg(); + w3.add(&w1); + + w8.add(&w6); + + w3.mul(&mut w8); + w8.copy(&w3); + w8.imul(3); + } else { + 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(); + } + if rom::CURVETYPE==rom::EDWARDS { + let mut c=FP::new_copy(&self.x); + let mut d=FP::new_copy(&self.y); + let mut h=FP::new_copy(&self.z); + let mut j=FP::new(); + + self.x.mul(&mut self.y); self.x.dbl(); + c.sqr(); + d.sqr(); + if rom::CURVE_A == -1 {c.neg()} + self.y.copy(&c); self.y.add(&d); + self.y.norm(); + h.sqr(); h.dbl(); + self.z.copy(&self.y); + j.copy(&self.y); j.sub(&h); + self.x.mul(&mut j); + c.sub(&d); + self.y.mul(&mut c); + self.z.mul(&mut j); + + self.x.norm(); + self.y.norm(); + self.z.norm(); + } + if rom::CURVETYPE==rom::MONTGOMERY { + let mut a=FP::new_copy(&self.x); + let mut b=FP::new_copy(&self.x); + let mut aa=FP::new(); + let mut bb=FP::new(); + let mut c=FP::new(); + + if self.inf {return} + + a.add(&self.z); + aa.copy(&a); aa.sqr(); + b.sub(&self.z); + bb.copy(&b); bb.sqr(); + c.copy(&aa); c.sub(&bb); + + self.x.copy(&aa); self.x.mul(&mut bb); + + a.copy(&c); a.imul((rom::CURVE_A+2)/4); + + bb.add(&a); + self.z.copy(&bb); self.z.mul(&mut c); + self.x.norm(); + self.z.norm(); + } + return; + } + + /* self+=Q */ + pub fn add(&mut self,Q:&mut ECP) + { + if rom::CURVETYPE==rom::WEIERSTRASS { + if self.inf { + self.copy(&Q); + return; + } + if Q.inf {return} + + let mut aff=false; + + let mut one=FP::new_int(1); + if Q.z.equals(&mut one) {aff=true} + + let mut a=FP::new(); + let mut c=FP::new(); + let mut b=FP::new_copy(&self.z); + let mut d=FP::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; + } + else + { + self.inf=true; + return; + } + } + + if !aff {self.z.mul(&mut Q.z)} + self.z.mul(&mut b); + + let mut e=FP::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(); + } + if rom::CURVETYPE==rom::EDWARDS { + let mut bb=FP::new_big(&BIG::new_ints(&rom::CURVE_B)); + let mut a=FP::new_copy(&self.z); + let mut b=FP::new(); + let mut c=FP::new_copy(&self.x); + let mut d=FP::new_copy(&self.y); + let mut e=FP::new(); + let mut f=FP::new(); + let mut g=FP::new(); + + a.mul(&mut Q.z); + b.copy(&a); b.sqr(); + c.mul(&mut Q.x); + d.mul(&mut Q.y); + + e.copy(&c); e.mul(&mut d); e.mul(&mut bb); + f.copy(&b); f.sub(&e); + g.copy(&b); g.add(&e); + + if rom::CURVE_A==1 { + e.copy(&d); e.sub(&c); + } + c.add(&d); + + b.copy(&self.x); b.add(&self.y); + d.copy(&Q.x); d.add(&Q.y); + b.mul(&mut d); + b.sub(&c); + b.mul(&mut f); + self.x.copy(&a); self.x.mul(&mut b); + + if rom::CURVE_A==1 { + c.copy(&e); c.mul(&mut g); + } + if rom::CURVE_A == -1 { + c.mul(&mut g); + } + self.y.copy(&a); self.y.mul(&mut c); + self.z.copy(&f); self.z.mul(&mut g); + self.x.norm(); self.y.norm(); self.z.norm(); + } + return; + } + +/* Differential Add for Montgomery curves. this+=Q where W is this-Q and is affine. */ + pub fn dadd(&mut self,Q: &ECP,W: &ECP) { + let mut a=FP::new_copy(&self.x); + let mut b=FP::new_copy(&self.x); + let mut c=FP::new_copy(&Q.x); + let mut d=FP::new_copy(&Q.x); + let mut da=FP::new(); + let mut cb=FP::new(); + + a.add(&self.z); + b.sub(&self.z); + + c.add(&Q.z); + d.sub(&Q.z); + + da.copy(&d); da.mul(&mut a); + cb.copy(&c); cb.mul(&mut b); + + a.copy(&da); a.add(&cb); a.sqr(); + b.copy(&da); b.sub(&cb); b.sqr(); + + self.x.copy(&a); + self.z.copy(&W.x); self.z.mul(&mut b); + + if self.z.iszilch() { + self.inf(); + } else {self.inf=false;} + + self.x.norm(); + } + +/* self-=Q */ + pub fn sub(&mut self,Q:&mut ECP) { + Q.neg(); + self.add(Q); + Q.neg(); + } + + fn multiaffine(P: &mut [ECP]) { + let mut t1=FP::new(); + let mut t2=FP::new(); + + let mut work:[FP;8]=[FP::new(),FP::new(),FP::new(),FP::new(),FP::new(),FP::new(),FP::new(),FP::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); + } + } + +/* constant time multiply by small integer of length bts - use ladder */ + pub fn pinmul(&mut self,e: i32,bts: i32) -> ECP { + if rom::CURVETYPE==rom::MONTGOMERY { + return self.mul(&mut BIG::new_int(e as isize)); + } else { + let mut P=ECP::new(); + let mut R0=ECP::new(); + let mut R1=ECP::new(); R1.copy(&self); + + for i in (0..bts).rev() { + let b=((e>>i)&1) as isize; + P.copy(&R1); + P.add(&mut R0); + R0.cswap(&mut R1,b); + R1.copy(&P); + R0.dbl(); + R0.cswap(&mut R1,b); + } + P.copy(&R0); + P.affine(); + return P; + } + } + +/* return e.self */ + + pub fn mul(&mut self,e:&mut BIG) -> ECP { + if e.iszilch() || self.is_infinity() {return ECP::new()} + let mut P=ECP::new(); + if rom::CURVETYPE==rom::MONTGOMERY { +/* use Ladder */ + let mut D=ECP::new(); + let mut R0=ECP::new(); R0.copy(&self); + let mut R1=ECP::new(); R1.copy(&self); + R1.dbl(); + D.copy(&self); D.affine(); + let nb=e.nbits(); + + for i in (0..nb-1).rev() { + let b=e.bit(i); + P.copy(&R1); + P.dadd(&mut R0,&D); + R0.cswap(&mut R1,b); + R1.copy(&P); + R0.dbl(); + R0.cswap(&mut R1,b); + } + P.copy(&R0) + } else { +// fixed size windows + let mut mt=BIG::new(); + let mut t=BIG::new(); + let mut Q=ECP::new(); + let mut C=ECP::new(); + + let mut W:[ECP;8]=[ECP::new(),ECP::new(),ECP::new(),ECP::new(),ECP::new(),ECP::new(),ECP::new(),ECP::new()]; + + const CT:usize=1+(rom::NLEN*(rom::BASEBITS as usize)+3)/4; + let mut w:[i8;CT]=[0;CT]; + + self.affine(); + + 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 + if rom::CURVETYPE==rom::WEIERSTRASS { + ECP::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); /* apply correction */ + } + P.affine(); + return P; + } + +/* Return e.this+f.Q */ + + pub fn mul2(&mut self,e: &BIG,Q: &mut ECP,f: &BIG) -> ECP { + let mut te=BIG::new(); + let mut tf=BIG::new(); + let mut mt=BIG::new(); + let mut S=ECP::new(); + let mut T=ECP::new(); + let mut C=ECP::new(); + + let mut W:[ECP;8]=[ECP::new(),ECP::new(),ECP::new(),ECP::new(),ECP::new(),ECP::new(),ECP::new(),ECP::new()]; + + const CT:usize=1+(rom::NLEN*(rom::BASEBITS as usize)+1)/2; + let mut w: [i8;CT]=[0;CT]; + + self.affine(); + Q.affine(); + + te.copy(e); + tf.copy(f); + +// precompute table + + W[1].copy(&self); W[1].sub(Q); + W[2].copy(&self); W[2].add(Q); + S.copy(&Q); S.dbl(); + C.copy(&W[1]); W[0].copy(&C); W[0].sub(&mut S); // copy to C is stupid Rust thing.. + C.copy(&W[2]); W[3].copy(&C); W[3].add(&mut S); + T.copy(&self); T.dbl(); + C.copy(&W[1]); W[5].copy(&C); W[5].add(&mut T); + C.copy(&W[2]); W[6].copy(&C); W[6].add(&mut T); + C.copy(&W[5]); W[4].copy(&C); W[4].sub(&mut S); + C.copy(&W[6]); W[7].copy(&C); W[7].add(&mut S); + +// convert the table to affine + if rom::CURVETYPE==rom::WEIERSTRASS { + ECP::multiaffine(&mut W); + } + +// if multiplier is odd, add 2, else add 1 to multiplier, and add 2P or P to correction + + let mut s=te.parity(); + te.inc(1); te.norm(); let mut ns=te.parity(); mt.copy(&te); mt.inc(1); mt.norm(); + te.cmove(&mt,s); + T.cmove(&self,ns); + C.copy(&T); + + s=tf.parity(); + tf.inc(1); tf.norm(); ns=tf.parity(); mt.copy(&tf); mt.inc(1); mt.norm(); + tf.cmove(&mt,s); + S.cmove(&Q,ns); + C.add(&mut S); + + mt.copy(&te); mt.add(&tf); mt.norm(); + let nb=1+(mt.nbits()+1)/2; + +// convert exponent to signed 2-bit window + for i in 0..nb { + let a=te.lastbits(3)-4; + te.dec(a); te.norm(); + te.fshr(2); + let b=tf.lastbits(3)-4; + tf.dec(b); tf.norm(); + tf.fshr(2); + w[i]=(4*a+b) as i8; + } + w[nb]=(4*te.lastbits(3)+tf.lastbits(3)) as i8; + S.copy(&W[((w[nb] as usize)-1)/2]); + + for i in (0..nb).rev() { + T.selector(&W,w[i] as i32); + S.dbl(); + S.dbl(); + S.add(&mut T); + } + S.sub(&mut C); /* apply correction */ + S.affine(); + return S; + } + + +} +/* +fn main() +{ + let mut E=ECP::new(); + + let mut W:[&ECP;8]=[&ECP::new(),&ECP::new(),&ECP::new(),&ECP::new(),&ECP::new(),&ECP::new(),&ECP::new(),&ECP::new()]; + + let mut gx=BIG::new_ints(&rom::CURVE_GX); + let mut gy=BIG::new(); + let mut P=ECP::new(); + + if rom::CURVETYPE!=rom::MONTGOMERY {gy.copy(&BIG::new_ints(&rom::CURVE_GY))} + let mut r=BIG::new_ints(&rom::CURVE_ORDER); + + //r.dec(7); + + println!("gx= {}",gx.tostring()); + + if rom::CURVETYPE!=rom::MONTGOMERY { + println!("gy= {}",gy.tostring()); + } + + if rom::CURVETYPE!=rom::MONTGOMERY { + P.copy(&ECP::new_bigs(&gx,&gy))} + else {P.copy(&ECP::new_big(&gx))} + + println!("P= {}",P.tostring()); + + let mut R=P.mul(&mut r); + //for i in 0..10000 (R=P.mul(r)); + + println!("R= {}",R.tostring()); + +} +*/
