http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto-c/blob/8d28d2c3/src/fp8.c.in ---------------------------------------------------------------------- diff --git a/src/fp8.c.in b/src/fp8.c.in new file mode 100644 index 0000000..fdd37f3 --- /dev/null +++ b/src/fp8.c.in @@ -0,0 +1,670 @@ +/* +Licensed to the Apache Software Foundation (ASF) under one +or more contributor license agreements. See the NOTICE file +distributed with this work for additional information +regarding copyright ownership. The ASF licenses this file +to you under the Apache License, Version 2.0 (the +"License"); you may not use this file except in compliance +with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, +software distributed under the License is distributed on an +"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +KIND, either express or implied. See the License for the +specific language governing permissions and limitations +under the License. +*/ + +/* AMCL Fp^8 functions */ + +/* FP8 elements are of the form a+ib, where i is sqrt(sqrt(-1+sqrt(-1))) */ + +#include "fp8_YYY.h" + + +/* test x==0 ? */ +int FP8_YYY_iszilch(FP8_YYY *x) +{ + if (FP4_YYY_iszilch(&(x->a)) && FP4_YYY_iszilch(&(x->b))) return 1; + return 0; +} + +/* test x==1 ? */ +int FP8_YYY_isunity(FP8_YYY *x) +{ + if (FP4_YYY_isunity(&(x->a)) && FP4_YYY_iszilch(&(x->b))) return 1; + return 0; +} + +/* test is w real? That is in a+ib test b is zero */ +int FP8_YYY_isreal(FP8_YYY *w) +{ + return FP4_YYY_iszilch(&(w->b)); +} + +/* return 1 if x==y, else 0 */ +int FP8_YYY_equals(FP8_YYY *x,FP8_YYY *y) +{ + if (FP4_YYY_equals(&(x->a),&(y->a)) && FP4_YYY_equals(&(x->b),&(y->b))) + return 1; + return 0; +} + +/* set FP8 from two FP4s */ +void FP8_YYY_from_FP4s(FP8_YYY *w,FP4_YYY * x,FP4_YYY* y) +{ + FP4_YYY_copy(&(w->a), x); + FP4_YYY_copy(&(w->b), y); +} + +/* set FP8 from FP4 */ +void FP8_YYY_from_FP4(FP8_YYY *w,FP4_YYY *x) +{ + FP4_YYY_copy(&(w->a), x); + FP4_YYY_zero(&(w->b)); +} + +/* set high part of FP8 from FP4 */ +void FP8_YYY_from_FP4H(FP8_YYY *w,FP4_YYY *x) +{ + FP4_YYY_copy(&(w->b), x); + FP4_YYY_zero(&(w->a)); +} + +/* FP8 copy w=x */ +void FP8_YYY_copy(FP8_YYY *w,FP8_YYY *x) +{ + if (w==x) return; + FP4_YYY_copy(&(w->a), &(x->a)); + FP4_YYY_copy(&(w->b), &(x->b)); +} + +/* FP8 w=0 */ +void FP8_YYY_zero(FP8_YYY *w) +{ + FP4_YYY_zero(&(w->a)); + FP4_YYY_zero(&(w->b)); +} + +/* FP8 w=1 */ +void FP8_YYY_one(FP8_YYY *w) +{ + FP4_YYY_one(&(w->a)); + FP4_YYY_zero(&(w->b)); +} + +/* Set w=-x */ +void FP8_YYY_neg(FP8_YYY *w,FP8_YYY *x) +{ + /* Just one field neg */ + FP4_YYY m,t; + FP8_YYY_norm(x); + FP4_YYY_add(&m,&(x->a),&(x->b)); + FP4_YYY_norm(&m); + FP4_YYY_neg(&m,&m); + FP4_YYY_add(&t,&m,&(x->b)); + FP4_YYY_add(&(w->b),&m,&(x->a)); + FP4_YYY_copy(&(w->a),&t); + FP8_YYY_norm(w); +} + +/* Set w=conj(x) */ +void FP8_YYY_conj(FP8_YYY *w,FP8_YYY *x) +{ + FP4_YYY_copy(&(w->a), &(x->a)); + FP4_YYY_neg(&(w->b), &(x->b)); + FP8_YYY_norm(w); +} + +/* Set w=-conj(x) */ +void FP8_YYY_nconj(FP8_YYY *w,FP8_YYY *x) +{ + FP4_YYY_copy(&(w->b),&(x->b)); + FP4_YYY_neg(&(w->a), &(x->a)); + FP8_YYY_norm(w); +} + +/* Set w=x+y */ +void FP8_YYY_add(FP8_YYY *w,FP8_YYY *x,FP8_YYY *y) +{ + FP4_YYY_add(&(w->a), &(x->a), &(y->a)); + FP4_YYY_add(&(w->b), &(x->b), &(y->b)); +} + +/* Set w=x-y */ +/* Input y MUST be normed */ +void FP8_YYY_sub(FP8_YYY *w,FP8_YYY *x,FP8_YYY *y) +{ + FP8_YYY my; + + FP8_YYY_neg(&my, y); + FP8_YYY_add(w, x, &my); +} + +/* reduce all components of w mod Modulus */ +void FP8_YYY_reduce(FP8_YYY *w) +{ + FP4_YYY_reduce(&(w->a)); + FP4_YYY_reduce(&(w->b)); +} + +/* normalise all elements of w */ +void FP8_YYY_norm(FP8_YYY *w) +{ + FP4_YYY_norm(&(w->a)); + FP4_YYY_norm(&(w->b)); +} + +/* Set w=s*x, where s is FP4 */ +void FP8_YYY_pmul(FP8_YYY *w,FP8_YYY *x,FP4_YYY *s) +{ + FP4_YYY_mul(&(w->a),&(x->a),s); + FP4_YYY_mul(&(w->b),&(x->b),s); +} + +/* Set w=s*x, where s is FP2 */ +void FP8_YYY_qmul(FP8_YYY *w,FP8_YYY *x,FP2_YYY *s) +{ + FP4_YYY_pmul(&(w->a),&(x->a),s); + FP4_YYY_pmul(&(w->b),&(x->b),s); +} + +/* Set w=s*x, where s is FP2 */ +void FP8_YYY_tmul(FP8_YYY *w,FP8_YYY *x,FP_YYY *s) +{ + FP4_YYY_qmul(&(w->a),&(x->a),s); + FP4_YYY_qmul(&(w->b),&(x->b),s); +} + +/* Set w=s*x, where s is int */ +void FP8_YYY_imul(FP8_YYY *w,FP8_YYY *x,int s) +{ + FP4_YYY_imul(&(w->a),&(x->a),s); + FP4_YYY_imul(&(w->b),&(x->b),s); +} + +/* Set w=x^2 */ +/* Input MUST be normed */ +void FP8_YYY_sqr(FP8_YYY *w,FP8_YYY *x) +{ + FP4_YYY t1,t2,t3; + + FP4_YYY_mul(&t3,&(x->a),&(x->b)); /* norms x */ + FP4_YYY_copy(&t2,&(x->b)); + FP4_YYY_add(&t1,&(x->a),&(x->b)); + FP4_YYY_times_i(&t2); + + FP4_YYY_add(&t2,&(x->a),&t2); + + FP4_YYY_norm(&t1); // 2 + FP4_YYY_norm(&t2); // 2 + + FP4_YYY_mul(&(w->a),&t1,&t2); + + FP4_YYY_copy(&t2,&t3); + FP4_YYY_times_i(&t2); + + FP4_YYY_add(&t2,&t2,&t3); + + FP4_YYY_norm(&t2); // 2 + FP4_YYY_neg(&t2,&t2); + FP4_YYY_add(&(w->a),&(w->a),&t2); /* a=(a+b)(a+i^2.b)-i^2.ab-ab = a*a+ib*ib */ + FP4_YYY_add(&(w->b),&t3,&t3); /* b=2ab */ + + FP8_YYY_norm(w); +} + +/* Set w=x*y */ +/* Inputs MUST be normed */ +void FP8_YYY_mul(FP8_YYY *w,FP8_YYY *x,FP8_YYY *y) +{ + FP4_YYY t1,t2,t3,t4; + FP4_YYY_mul(&t1,&(x->a),&(y->a)); + FP4_YYY_mul(&t2,&(x->b),&(y->b)); + + FP4_YYY_add(&t3,&(y->b),&(y->a)); + FP4_YYY_add(&t4,&(x->b),&(x->a)); + + FP4_YYY_norm(&t4); // 2 + FP4_YYY_norm(&t3); // 2 + + FP4_YYY_mul(&t4,&t4,&t3); /* (xa+xb)(ya+yb) */ + + FP4_YYY_neg(&t3,&t1); // 1 + FP4_YYY_add(&t4,&t4,&t3); //t4E=3 + FP4_YYY_norm(&t4); + + FP4_YYY_neg(&t3,&t2); // 1 + FP4_YYY_add(&(w->b),&t4,&t3); //wbE=3 + + FP4_YYY_times_i(&t2); + FP4_YYY_add(&(w->a),&t2,&t1); + + FP8_YYY_norm(w); +} + +/* output FP8 in format [a,b] */ +void FP8_YYY_output(FP8_YYY *w) +{ + printf("["); + FP4_YYY_output(&(w->a)); + printf(","); + FP4_YYY_output(&(w->b)); + printf("]"); +} + +void FP8_YYY_rawoutput(FP8_YYY *w) +{ + printf("["); + FP4_YYY_rawoutput(&(w->a)); + printf(","); + FP4_YYY_rawoutput(&(w->b)); + printf("]"); +} + +/* Set w=1/x */ +void FP8_YYY_inv(FP8_YYY *w,FP8_YYY *x) +{ + FP4_YYY t1,t2; + FP4_YYY_sqr(&t1,&(x->a)); + FP4_YYY_sqr(&t2,&(x->b)); + FP4_YYY_times_i(&t2); + FP4_YYY_norm(&t2); + + FP4_YYY_sub(&t1,&t1,&t2); + FP4_YYY_norm(&t1); + FP4_YYY_inv(&t1,&t1); + FP4_YYY_mul(&(w->a),&t1,&(x->a)); + FP4_YYY_neg(&t1,&t1); + FP4_YYY_norm(&t1); + FP4_YYY_mul(&(w->b),&t1,&(x->b)); +} + +/* w*=i where i = sqrt(sqrt(-1+sqrt(-1))) */ +void FP8_YYY_times_i(FP8_YYY *w) +{ + FP4_YYY s,t; + FP4_YYY_copy(&s,&(w->b)); + FP4_YYY_copy(&t,&(w->a)); + FP4_YYY_times_i(&s); + FP4_YYY_copy(&(w->a),&s); + FP4_YYY_copy(&(w->b),&t); + FP8_YYY_norm(w); +} + +void FP8_YYY_times_i2(FP8_YYY *w) +{ + FP4_YYY_times_i(&(w->a)); + FP4_YYY_times_i(&(w->b)); +} + +/* Set w=w^p using Frobenius */ +void FP8_YYY_frob(FP8_YYY *w,FP2_YYY *f) +{ + // f=(i+1)^(p-3)/4 + FP2_YYY ff; + FP2_YYY_sqr(&ff,f); // (i+1)^(p-3)/2 + FP2_YYY_mul_ip(&ff); // (i+1)^(p-1)/2 + FP2_YYY_norm(&ff); + FP4_YYY_frob(&(w->a),&ff); + FP4_YYY_frob(&(w->b),&ff); + FP4_YYY_pmul(&(w->b),&(w->b),f); // times (1+i)^(p-3)/4 + FP4_YYY_times_i(&(w->b)); // (i+1)^(p-1)/4 +} + +/* Set r=a^b mod m */ +void FP8_YYY_pow(FP8_YYY *r,FP8_YYY* a,BIG_XXX b) +{ + FP8_YYY w; + BIG_XXX z,zilch; + int bt; + + BIG_XXX_zero(zilch); + BIG_XXX_norm(b); + BIG_XXX_copy(z,b); + FP8_YYY_copy(&w,a); + FP8_YYY_one(r); + + while(1) + { + bt=BIG_XXX_parity(z); + BIG_XXX_shr(z,1); + if (bt) FP8_YYY_mul(r,r,&w); + if (BIG_XXX_comp(z,zilch)==0) break; + FP8_YYY_sqr(&w,&w); + } + FP8_YYY_reduce(r); +} + +#if CURVE_SECURITY_ZZZ == 192 + +/* XTR xtr_a function */ +void FP8_YYY_xtr_A(FP8_YYY *r,FP8_YYY *w,FP8_YYY *x,FP8_YYY *y,FP8_YYY *z) +{ + FP8_YYY t1,t2; + + FP8_YYY_copy(r,x); + FP8_YYY_sub(&t1,w,y); + FP8_YYY_norm(&t1); + FP8_YYY_pmul(&t1,&t1,&(r->a)); + FP8_YYY_add(&t2,w,y); + FP8_YYY_norm(&t2); + FP8_YYY_pmul(&t2,&t2,&(r->b)); + FP8_YYY_times_i(&t2); + + FP8_YYY_add(r,&t1,&t2); + FP8_YYY_add(r,r,z); + + FP8_YYY_reduce(r); +} + +/* XTR xtr_d function */ +void FP8_YYY_xtr_D(FP8_YYY *r,FP8_YYY *x) +{ + FP8_YYY w; + FP8_YYY_copy(r,x); + FP8_YYY_conj(&w,r); + FP8_YYY_add(&w,&w,&w); + FP8_YYY_sqr(r,r); + FP8_YYY_norm(&w); + FP8_YYY_sub(r,r,&w); + FP8_YYY_reduce(r); /* reduce here as multiple calls trigger automatic reductions */ +} + +/* r=x^n using XTR method on traces of FP12s */ +void FP8_YYY_xtr_pow(FP8_YYY *r,FP8_YYY *x,BIG_XXX n) +{ + int i,par,nb; + BIG_XXX v; + FP2_YYY w2; + FP4_YYY w4; + FP8_YYY t,a,b,c; + + BIG_XXX_zero(v); + BIG_XXX_inc(v,3); + BIG_XXX_norm(v); + FP2_YYY_from_BIG(&w2,v); + FP4_YYY_from_FP2(&w4,&w2); + FP8_YYY_from_FP4(&a,&w4); + + FP8_YYY_copy(&b,x); + FP8_YYY_xtr_D(&c,x); + + BIG_XXX_norm(n); + par=BIG_XXX_parity(n); + BIG_XXX_copy(v,n); + BIG_XXX_shr(v,1); + if (par==0) + { + BIG_XXX_dec(v,1); + BIG_XXX_norm(v); + } + + nb=BIG_XXX_nbits(v); + for (i=nb-1; i>=0; i--) + { + if (!BIG_XXX_bit(v,i)) + { + FP8_YYY_copy(&t,&b); + FP8_YYY_conj(x,x); + FP8_YYY_conj(&c,&c); + FP8_YYY_xtr_A(&b,&a,&b,x,&c); + FP8_YYY_conj(x,x); + FP8_YYY_xtr_D(&c,&t); + FP8_YYY_xtr_D(&a,&a); + } + else + { + FP8_YYY_conj(&t,&a); + FP8_YYY_xtr_D(&a,&b); + FP8_YYY_xtr_A(&b,&c,&b,x,&t); + FP8_YYY_xtr_D(&c,&c); + } + } + + if (par==0) FP8_YYY_copy(r,&c); + else FP8_YYY_copy(r,&b); + FP8_YYY_reduce(r); +} + +/* r=ck^a.cl^n using XTR double exponentiation method on traces of FP12s. See Stam thesis. */ +void FP8_YYY_xtr_pow2(FP8_YYY *r,FP8_YYY *ck,FP8_YYY *cl,FP8_YYY *ckml,FP8_YYY *ckm2l,BIG_XXX a,BIG_XXX b) +{ + int i,f2; + BIG_XXX d,e,w; + FP8_YYY t,cu,cv,cumv,cum2v; + + BIG_XXX_norm(a); + BIG_XXX_norm(b); + BIG_XXX_copy(e,a); + BIG_XXX_copy(d,b); + FP8_YYY_copy(&cu,ck); + FP8_YYY_copy(&cv,cl); + FP8_YYY_copy(&cumv,ckml); + FP8_YYY_copy(&cum2v,ckm2l); + + f2=0; + while (BIG_XXX_parity(d)==0 && BIG_XXX_parity(e)==0) + { + BIG_XXX_shr(d,1); + BIG_XXX_shr(e,1); + f2++; + } + while (BIG_XXX_comp(d,e)!=0) + { + if (BIG_XXX_comp(d,e)>0) + { + BIG_XXX_imul(w,e,4); + BIG_XXX_norm(w); + if (BIG_XXX_comp(d,w)<=0) + { + BIG_XXX_copy(w,d); + BIG_XXX_copy(d,e); + BIG_XXX_sub(e,w,e); + BIG_XXX_norm(e); + FP8_YYY_xtr_A(&t,&cu,&cv,&cumv,&cum2v); + FP8_YYY_conj(&cum2v,&cumv); + FP8_YYY_copy(&cumv,&cv); + FP8_YYY_copy(&cv,&cu); + FP8_YYY_copy(&cu,&t); + } + else if (BIG_XXX_parity(d)==0) + { + BIG_XXX_shr(d,1); + FP8_YYY_conj(r,&cum2v); + FP8_YYY_xtr_A(&t,&cu,&cumv,&cv,r); + FP8_YYY_xtr_D(&cum2v,&cumv); + FP8_YYY_copy(&cumv,&t); + FP8_YYY_xtr_D(&cu,&cu); + } + else if (BIG_XXX_parity(e)==1) + { + BIG_XXX_sub(d,d,e); + BIG_XXX_norm(d); + BIG_XXX_shr(d,1); + FP8_YYY_xtr_A(&t,&cu,&cv,&cumv,&cum2v); + FP8_YYY_xtr_D(&cu,&cu); + FP8_YYY_xtr_D(&cum2v,&cv); + FP8_YYY_conj(&cum2v,&cum2v); + FP8_YYY_copy(&cv,&t); + } + else + { + BIG_XXX_copy(w,d); + BIG_XXX_copy(d,e); + BIG_XXX_shr(d,1); + BIG_XXX_copy(e,w); + FP8_YYY_xtr_D(&t,&cumv); + FP8_YYY_conj(&cumv,&cum2v); + FP8_YYY_conj(&cum2v,&t); + FP8_YYY_xtr_D(&t,&cv); + FP8_YYY_copy(&cv,&cu); + FP8_YYY_copy(&cu,&t); + } + } + if (BIG_XXX_comp(d,e)<0) + { + BIG_XXX_imul(w,d,4); + BIG_XXX_norm(w); + if (BIG_XXX_comp(e,w)<=0) + { + BIG_XXX_sub(e,e,d); + BIG_XXX_norm(e); + FP8_YYY_xtr_A(&t,&cu,&cv,&cumv,&cum2v); + FP8_YYY_copy(&cum2v,&cumv); + FP8_YYY_copy(&cumv,&cu); + FP8_YYY_copy(&cu,&t); + } + else if (BIG_XXX_parity(e)==0) + { + BIG_XXX_copy(w,d); + BIG_XXX_copy(d,e); + BIG_XXX_shr(d,1); + BIG_XXX_copy(e,w); + FP8_YYY_xtr_D(&t,&cumv); + FP8_YYY_conj(&cumv,&cum2v); + FP8_YYY_conj(&cum2v,&t); + FP8_YYY_xtr_D(&t,&cv); + FP8_YYY_copy(&cv,&cu); + FP8_YYY_copy(&cu,&t); + } + else if (BIG_XXX_parity(d)==1) + { + BIG_XXX_copy(w,e); + BIG_XXX_copy(e,d); + BIG_XXX_sub(w,w,d); + BIG_XXX_norm(w); + BIG_XXX_copy(d,w); + BIG_XXX_shr(d,1); + FP8_YYY_xtr_A(&t,&cu,&cv,&cumv,&cum2v); + FP8_YYY_conj(&cumv,&cumv); + FP8_YYY_xtr_D(&cum2v,&cu); + FP8_YYY_conj(&cum2v,&cum2v); + FP8_YYY_xtr_D(&cu,&cv); + FP8_YYY_copy(&cv,&t); + } + else + { + BIG_XXX_shr(d,1); + FP8_YYY_conj(r,&cum2v); + FP8_YYY_xtr_A(&t,&cu,&cumv,&cv,r); + FP8_YYY_xtr_D(&cum2v,&cumv); + FP8_YYY_copy(&cumv,&t); + FP8_YYY_xtr_D(&cu,&cu); + } + } + } + FP8_YYY_xtr_A(r,&cu,&cv,&cumv,&cum2v); + for (i=0; i<f2; i++) FP8_YYY_xtr_D(r,r); + FP8_YYY_xtr_pow(r,r,d); +} + +#endif + + +/* New stuff for ECp8 support */ + +/* Move b to a if d=1 */ +void FP8_YYY_cmove(FP8_YYY *f,FP8_YYY *g,int d) +{ + FP4_YYY_cmove(&(f->a),&(g->a),d); + FP4_YYY_cmove(&(f->b),&(g->b),d); +} + +#if CURVE_SECURITY_ZZZ == 256 + +/* sqrt(a+xb) = sqrt((a+sqrt(a*a-n*b*b))/2)+x.b/(2*sqrt((a+sqrt(a*a-n*b*b))/2)) */ +/* returns true if x is QR */ +int FP8_YYY_sqrt(FP8_YYY *r,FP8_YYY* x) +{ + FP4_YYY a,s,t; + + FP8_YYY_copy(r,x); + if (FP8_YYY_iszilch(x)) + return 1; + + FP4_YYY_copy(&a,&(x->a)); + FP4_YYY_copy(&s,&(x->b)); + + if (FP4_YYY_iszilch(&s)) + { + if (FP4_YYY_sqrt(&t,&a)) + { + FP8_YYY_from_FP4(r,&t); + } + else + { + FP4_YYY_div_i(&a); + FP4_YYY_sqrt(&t,&a); + FP8_YYY_from_FP4H(r,&t); + } + return 1; + } + + FP4_YYY_sqr(&s,&s); // s*=s + FP4_YYY_sqr(&a,&a); // a*=a + FP4_YYY_times_i(&s); + FP4_YYY_norm(&s); + FP4_YYY_sub(&a,&a,&s); // a-=txx(s) + + if (!FP4_YYY_sqrt(&s,&a)) return 0; + + FP4_YYY_sqr(&t,&s); + + + FP4_YYY_copy(&t,&(x->a)); + FP4_YYY_add(&a,&t,&s); + FP4_YYY_norm(&a); + FP4_YYY_div2(&a,&a); + + if (!FP4_YYY_sqrt(&a,&a)) + { + FP4_YYY_sub(&a,&t,&s); + FP4_YYY_norm(&a); + FP4_YYY_div2(&a,&a); + if (!FP4_YYY_sqrt(&a,&a)) return 0; + } + + FP4_YYY_copy(&t,&(x->b)); + FP4_YYY_add(&s,&a,&a); + FP4_YYY_inv(&s,&s); + + FP4_YYY_mul(&t,&t,&s); + FP8_YYY_from_FP4s(r,&a,&t); + + return 1; +} + + +void FP8_YYY_div_i(FP8_YYY *f) +{ + FP4_YYY u,v; + FP4_YYY_copy(&u,&(f->a)); + FP4_YYY_copy(&v,&(f->b)); + FP4_YYY_div_i(&u); + FP4_YYY_copy(&(f->a),&v); + FP4_YYY_copy(&(f->b),&u); +} + +void FP8_YYY_div_i2(FP8_YYY *f) +{ + FP4_YYY_div_i(&(f->a)); + FP4_YYY_div_i(&(f->b)); +} + + +void FP8_YYY_div_2i(FP8_YYY *f) +{ + FP4_YYY u,v; + FP4_YYY_copy(&u,&(f->a)); + FP4_YYY_copy(&v,&(f->b)); + FP4_YYY_div_2i(&u); + FP4_YYY_add(&v,&v,&v); + FP4_YYY_norm(&v); + FP4_YYY_copy(&(f->a),&v); + FP4_YYY_copy(&(f->b),&u); +} + +#endif
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto-c/blob/8d28d2c3/src/gcm.c ---------------------------------------------------------------------- diff --git a/src/gcm.c b/src/gcm.c new file mode 100644 index 0000000..e3a5494 --- /dev/null +++ b/src/gcm.c @@ -0,0 +1,411 @@ +/* +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. +*/ + +/* + * Implementation of the AES-GCM Encryption/Authentication + * + * Some restrictions.. + * 1. Only for use with AES + * 2. Returned tag is always 128-bits. Truncate at your own risk. + * 3. The order of function calls must follow some rules + * + * Typical sequence of calls.. + * 1. call GCM_init + * 2. call GCM_add_header any number of times, as long as length of header is multiple of 16 bytes (block size) + * 3. call GCM_add_header one last time with any length of header + * 4. call GCM_add_cipher any number of times, as long as length of cipher/plaintext is multiple of 16 bytes + * 5. call GCM_add_cipher one last time with any length of cipher/plaintext + * 6. call GCM_finish to extract the tag. + * + * See http://www.mindspring.com/~dmcgrew/gcm-nist-6.pdf + */ +/* SU=m, m is Stack Usage */ + +#include <stdlib.h> +#include <string.h> +#include "arch.h" +#include "amcl.h" + +#define NB 4 +#define MR_TOBYTE(x) ((uchar)((x))) + +static unsign32 pack(const uchar *b) +{ + /* pack bytes into a 32-bit Word */ + return ((unsign32)b[0]<<24)|((unsign32)b[1]<<16)|((unsign32)b[2]<<8)|(unsign32)b[3]; +} + +static void unpack(unsign32 a,uchar *b) +{ + /* unpack bytes from a word */ + b[3]=MR_TOBYTE(a); + b[2]=MR_TOBYTE(a>>8); + b[1]=MR_TOBYTE(a>>16); + b[0]=MR_TOBYTE(a>>24); +} + +static void precompute(gcm *g,uchar *H) +{ + /* precompute small 2k bytes gf2m table of x^n.H */ + int i,j; + unsign32 *last,*next,b; + + for (i=j=0; i<NB; i++,j+=4) g->table[0][i]=pack((uchar *)&H[j]); + + for (i=1; i<128; i++) + { + next=g->table[i]; + last=g->table[i-1]; + b=0; + for (j=0; j<NB; j++) + { + next[j]=b|(last[j])>>1; + b=last[j]<<31; + } + if (b) next[0]^=0xE1000000; /* irreducible polynomial */ + } +} + +/* SU= 32 */ +static void gf2mul(gcm *g) +{ + /* gf2m mul - Z=H*X mod 2^128 */ + int i,j,m,k; + unsign32 P[4]; + unsign32 b; + + P[0]=P[1]=P[2]=P[3]=0; + j=8; + m=0; + for (i=0; i<128; i++) + { + b=(unsign32)(g->stateX[m]>>(--j))&1; + b=~b+1; + for (k=0; k<NB; k++) P[k]^=(g->table[i][k]&b); + if (j==0) + { + j=8; + m++; + if (m==16) break; + } + } + for (i=j=0; i<NB; i++,j+=4) unpack(P[i],(uchar *)&g->stateX[j]); +} + +/* SU= 32 */ +static void GCM_wrap(gcm *g) +{ + /* Finish off GHASH */ + int i,j; + unsign32 F[4]; + uchar L[16]; + + /* convert lengths from bytes to bits */ + F[0]=(g->lenA[0]<<3)|(g->lenA[1]&0xE0000000)>>29; + F[1]=g->lenA[1]<<3; + F[2]=(g->lenC[0]<<3)|(g->lenC[1]&0xE0000000)>>29; + F[3]=g->lenC[1]<<3; + for (i=j=0; i<NB; i++,j+=4) unpack(F[i],(uchar *)&L[j]); + + for (i=0; i<16; i++) g->stateX[i]^=L[i]; + gf2mul(g); +} + +static int GCM_ghash(gcm *g,char *plain,int len) +{ + int i,j=0; + if (g->status==GCM_ACCEPTING_HEADER) g->status=GCM_ACCEPTING_CIPHER; + if (g->status!=GCM_ACCEPTING_CIPHER) return 0; + + while (j<len) + { + for (i=0; i<16 && j<len; i++) + { + g->stateX[i]^=plain[j++]; + g->lenC[1]++; + if (g->lenC[1]==0) g->lenC[0]++; + } + gf2mul(g); + } + if (len%16!=0) g->status=GCM_NOT_ACCEPTING_MORE; + return 1; +} + +/* SU= 48 */ +/* Initialize GCM mode */ +void GCM_init(gcm* g,int nk,char *key,int niv,char *iv) +{ + /* iv size niv is usually 12 bytes (96 bits). AES key size nk can be 16,24 or 32 bytes */ + int i; + uchar H[16]; + for (i=0; i<16; i++) + { + H[i]=0; + g->stateX[i]=0; + } + + AES_init(&(g->a),ECB,nk,key,iv); + AES_ecb_encrypt(&(g->a),H); /* E(K,0) */ + precompute(g,H); + + g->lenA[0]=g->lenC[0]=g->lenA[1]=g->lenC[1]=0; + if (niv==12) + { + for (i=0; i<12; i++) g->a.f[i]=iv[i]; + unpack((unsign32)1,(uchar *)&(g->a.f[12])); /* initialise IV */ + for (i=0; i<16; i++) g->Y_0[i]=g->a.f[i]; + } + else + { + g->status=GCM_ACCEPTING_CIPHER; + GCM_ghash(g,iv,niv); /* GHASH(H,0,IV) */ + GCM_wrap(g); + for (i=0; i<16; i++) + { + g->a.f[i]=g->stateX[i]; + g->Y_0[i]=g->a.f[i]; + g->stateX[i]=0; + } + g->lenA[0]=g->lenC[0]=g->lenA[1]=g->lenC[1]=0; + } + g->status=GCM_ACCEPTING_HEADER; +} + +/* SU= 24 */ +/* Add Header data - included but not encrypted */ +int GCM_add_header(gcm* g,char *header,int len) +{ + /* Add some header. Won't be encrypted, but will be authenticated. len is length of header */ + int i,j=0; + if (g->status!=GCM_ACCEPTING_HEADER) return 0; + + while (j<len) + { + for (i=0; i<16 && j<len; i++) + { + g->stateX[i]^=header[j++]; + g->lenA[1]++; + if (g->lenA[1]==0) g->lenA[0]++; + } + gf2mul(g); + } + if (len%16!=0) g->status=GCM_ACCEPTING_CIPHER; + return 1; +} + +/* SU= 48 */ +/* Add Plaintext - included and encrypted */ +int GCM_add_plain(gcm *g,char *cipher,char *plain,int len) +{ + /* Add plaintext to extract ciphertext, len is length of plaintext. */ + int i,j=0; + unsign32 counter; + uchar B[16]; + if (g->status==GCM_ACCEPTING_HEADER) g->status=GCM_ACCEPTING_CIPHER; + if (g->status!=GCM_ACCEPTING_CIPHER) return 0; + + while (j<len) + { + counter=pack((uchar *)&(g->a.f[12])); + counter++; + unpack(counter,(uchar *)&(g->a.f[12])); /* increment counter */ + for (i=0; i<16; i++) B[i]=g->a.f[i]; + AES_ecb_encrypt(&(g->a),B); /* encrypt it */ + + for (i=0; i<16 && j<len; i++) + { + cipher[j]=plain[j]^B[i]; + g->stateX[i]^=cipher[j++]; + g->lenC[1]++; + if (g->lenC[1]==0) g->lenC[0]++; + } + gf2mul(g); + } + if (len%16!=0) g->status=GCM_NOT_ACCEPTING_MORE; + return 1; +} + +/* SU= 48 */ +/* Add Ciphertext - decrypts to plaintext */ +int GCM_add_cipher(gcm *g,char *plain,char *cipher,int len) +{ + /* Add ciphertext to extract plaintext, len is length of ciphertext. */ + int i,j=0; + unsign32 counter; + char oc; + uchar B[16]; + if (g->status==GCM_ACCEPTING_HEADER) g->status=GCM_ACCEPTING_CIPHER; + if (g->status!=GCM_ACCEPTING_CIPHER) return 0; + + while (j<len) + { + counter=pack((uchar *)&(g->a.f[12])); + counter++; + unpack(counter,(uchar *)&(g->a.f[12])); /* increment counter */ + for (i=0; i<16; i++) B[i]=g->a.f[i]; + AES_ecb_encrypt(&(g->a),B); /* encrypt it */ + for (i=0; i<16 && j<len; i++) + { + oc=cipher[j]; + plain[j]=cipher[j]^B[i]; + g->stateX[i]^=oc; + j++; + g->lenC[1]++; + if (g->lenC[1]==0) g->lenC[0]++; + } + gf2mul(g); + } + if (len%16!=0) g->status=GCM_NOT_ACCEPTING_MORE; + return 1; +} + +/* SU= 16 */ +/* Finish and extract Tag */ +void GCM_finish(gcm *g,char *tag) +{ + /* Finish off GHASH and extract tag (MAC) */ + int i; + + GCM_wrap(g); + + /* extract tag */ + if (tag!=NULL) + { + AES_ecb_encrypt(&(g->a),g->Y_0); /* E(K,Y0) */ + for (i=0; i<16; i++) g->Y_0[i]^=g->stateX[i]; + for (i=0; i<16; i++) + { + tag[i]=g->Y_0[i]; + g->Y_0[i]=g->stateX[i]=0; + } + } + g->status=GCM_FINISHED; + AES_end(&(g->a)); +} + + +// Compile with +// gcc -O2 gcm.c aes.c -o gcm.exe +/* SU= 16 +*/ + +/* static void hex2bytes(char *hex,char *bin) */ +/* { */ +/* int i; */ +/* char v; */ +/* int len=strlen(hex); */ +/* for (i = 0; i < len/2; i++) { */ +/* char c = hex[2*i]; */ +/* if (c >= '0' && c <= '9') { */ +/* v = c - '0'; */ +/* } else if (c >= 'A' && c <= 'F') { */ +/* v = c - 'A' + 10; */ +/* } else if (c >= 'a' && c <= 'f') { */ +/* v = c - 'a' + 10; */ +/* } else { */ +/* v = 0; */ +/* } */ +/* v <<= 4; */ +/* c = hex[2*i + 1]; */ +/* if (c >= '0' && c <= '9') { */ +/* v += c - '0'; */ +/* } else if (c >= 'A' && c <= 'F') { */ +/* v += c - 'A' + 10; */ +/* } else if (c >= 'a' && c <= 'f') { */ +/* v += c - 'a' + 10; */ +/* } else { */ +/* v = 0; */ +/* } */ +/* bin[i] = v; */ +/* } */ +/* } */ + +/* +int main() +{ + int i; + +// char* KT="feffe9928665731c6d6a8f9467308308"; +// char* MT="d9313225f88406e5a55909c5aff5269a86a7a9531534f7da2e4c303d8a318a721c3c0c95956809532fcf0e2449a6b525b16aedf5aa0de657ba637b39"; +// char* HT="feedfacedeadbeeffeedfacedeadbeefabaddad2"; +// char* NT="cafebabefacedbaddecaf888"; +// Tag should be 5bc94fbc3221a5db94fae95ae7121a47 +// char* NT="9313225df88406e555909c5aff5269aa6a7a9538534f7da1e4c303d2a318a728c3c0c95156809539fcf0e2429a6b525416aedbf5a0de6a57a637b39b"; +// Tag should be 619cc5aefffe0bfa462af43c1699d050 + + char* KT="6dfb5dc68af6ae2f3242e9184f100918"; + char* MT="47809d16c2c6ec685962c90e53fe1bba"; + char* HT="dd0fa6e494031139d71ee45f00d56fa4"; + char* NT="37d36f5c54d53479d4745dd1"; + + + int len=strlen(MT)/2; + int lenH=strlen(HT)/2; + int lenK=strlen(KT)/2; + int lenIV=strlen(NT)/2; + + char T[16]; // Tag + char K[16]; // AES Key + char H[64]; // Header - to be included in Authentication, but not encrypted + char N[100]; // IV - Initialization vector + char M[100]; // Plaintext to be encrypted/authenticated + char C[100]; // Ciphertext + char P[100]; // Recovered Plaintext + + gcm g; + + hex2bytes(MT, M); + hex2bytes(HT, H); + hex2bytes(NT, N); + hex2bytes(KT, K); + + printf("lenK= %d\n",lenK); + + printf("Plaintext=\n"); + for (i=0;i<len;i++) printf("%02x",(unsigned char)M[i]); + printf("\n"); + + GCM_init(&g,16,K,lenIV,N); + GCM_add_header(&g,H,lenH); + GCM_add_plain(&g,C,M,len); + GCM_finish(&g,T); + + printf("Ciphertext=\n"); + for (i=0;i<len;i++) printf("%02x",(unsigned char)C[i]); + printf("\n"); + + printf("Tag=\n"); + for (i=0;i<16;i++) printf("%02x",(unsigned char)T[i]); + printf("\n"); + + GCM_init(&g,16,K,lenIV,N); + GCM_add_header(&g,H,lenH); + GCM_add_cipher(&g,P,C,len); + GCM_finish(&g,T); + + printf("Plaintext=\n"); + for (i=0;i<len;i++) printf("%02x",(unsigned char)P[i]); + printf("\n"); + + printf("Tag=\n"); + for (i=0;i<16;i++) printf("%02x",(unsigned char)T[i]); + printf("\n"); +} + +*/ http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto-c/blob/8d28d2c3/src/hash.c ---------------------------------------------------------------------- diff --git a/src/hash.c b/src/hash.c new file mode 100644 index 0000000..b095036 --- /dev/null +++ b/src/hash.c @@ -0,0 +1,606 @@ +/* +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. +*/ + +/* + * Implementation of the Secure Hashing Algorithm (SHA-256/384/512 and SHA3) + * + * Generates a message digest. It should be impossible to come + * come up with two messages that hash to the same value ("collision free"). + * + * For use with byte-oriented messages only. Could/Should be speeded + * up by unwinding loops in HASH_transform(), and assembly patches. + */ + +#include "arch.h" +#include "amcl.h" + + +#define H0_256 0x6A09E667L +#define H1_256 0xBB67AE85L +#define H2_256 0x3C6EF372L +#define H3_256 0xA54FF53AL +#define H4_256 0x510E527FL +#define H5_256 0x9B05688CL +#define H6_256 0x1F83D9ABL +#define H7_256 0x5BE0CD19L + +static const unsign32 K_256[64]= +{ + 0x428a2f98L,0x71374491L,0xb5c0fbcfL,0xe9b5dba5L,0x3956c25bL,0x59f111f1L,0x923f82a4L,0xab1c5ed5L, + 0xd807aa98L,0x12835b01L,0x243185beL,0x550c7dc3L,0x72be5d74L,0x80deb1feL,0x9bdc06a7L,0xc19bf174L, + 0xe49b69c1L,0xefbe4786L,0x0fc19dc6L,0x240ca1ccL,0x2de92c6fL,0x4a7484aaL,0x5cb0a9dcL,0x76f988daL, + 0x983e5152L,0xa831c66dL,0xb00327c8L,0xbf597fc7L,0xc6e00bf3L,0xd5a79147L,0x06ca6351L,0x14292967L, + 0x27b70a85L,0x2e1b2138L,0x4d2c6dfcL,0x53380d13L,0x650a7354L,0x766a0abbL,0x81c2c92eL,0x92722c85L, + 0xa2bfe8a1L,0xa81a664bL,0xc24b8b70L,0xc76c51a3L,0xd192e819L,0xd6990624L,0xf40e3585L,0x106aa070L, + 0x19a4c116L,0x1e376c08L,0x2748774cL,0x34b0bcb5L,0x391c0cb3L,0x4ed8aa4aL,0x5b9cca4fL,0x682e6ff3L, + 0x748f82eeL,0x78a5636fL,0x84c87814L,0x8cc70208L,0x90befffaL,0xa4506cebL,0xbef9a3f7L,0xc67178f2L +}; + +#define PAD 0x80 +#define ZERO 0 + +/* functions */ + +#define S(m,n,x) (((x)>>n) | ((x)<<(m-n))) +#define R(n,x) ((x)>>n) + +#define Ch(x,y,z) ((x&y)^(~(x)&z)) +#define Maj(x,y,z) ((x&y)^(x&z)^(y&z)) +#define Sig0_256(x) (S(32,2,x)^S(32,13,x)^S(32,22,x)) +#define Sig1_256(x) (S(32,6,x)^S(32,11,x)^S(32,25,x)) +#define theta0_256(x) (S(32,7,x)^S(32,18,x)^R(3,x)) +#define theta1_256(x) (S(32,17,x)^S(32,19,x)^R(10,x)) + +#define Sig0_512(x) (S(64,28,x)^S(64,34,x)^S(64,39,x)) +#define Sig1_512(x) (S(64,14,x)^S(64,18,x)^S(64,41,x)) +#define theta0_512(x) (S(64,1,x)^S(64,8,x)^R(7,x)) +#define theta1_512(x) (S(64,19,x)^S(64,61,x)^R(6,x)) + + +/* SU= 72 */ +static void HASH256_transform(hash256 *sh) +{ + /* basic transformation step */ + unsign32 a,b,c,d,e,f,g,h,t1,t2; + int j; + for (j=16; j<64; j++) + sh->w[j]=theta1_256(sh->w[j-2])+sh->w[j-7]+theta0_256(sh->w[j-15])+sh->w[j-16]; + + a=sh->h[0]; + b=sh->h[1]; + c=sh->h[2]; + d=sh->h[3]; + e=sh->h[4]; + f=sh->h[5]; + g=sh->h[6]; + h=sh->h[7]; + + for (j=0; j<64; j++) + { + /* 64 times - mush it up */ + t1=h+Sig1_256(e)+Ch(e,f,g)+K_256[j]+sh->w[j]; + t2=Sig0_256(a)+Maj(a,b,c); + h=g; + g=f; + f=e; + e=d+t1; + d=c; + c=b; + b=a; + a=t1+t2; + } + + sh->h[0]+=a; + sh->h[1]+=b; + sh->h[2]+=c; + sh->h[3]+=d; + sh->h[4]+=e; + sh->h[5]+=f; + sh->h[6]+=g; + sh->h[7]+=h; +} + +/* Initialise Hash function */ +void HASH256_init(hash256 *sh) +{ + /* re-initialise */ + int i; + for (i=0; i<64; i++) sh->w[i]=0L; + sh->length[0]=sh->length[1]=0L; + sh->h[0]=H0_256; + sh->h[1]=H1_256; + sh->h[2]=H2_256; + sh->h[3]=H3_256; + sh->h[4]=H4_256; + sh->h[5]=H5_256; + sh->h[6]=H6_256; + sh->h[7]=H7_256; + + sh->hlen=32; +} + +/* process a single byte */ +void HASH256_process(hash256 *sh,int byt) +{ + /* process the next message byte */ + int cnt; + cnt=(int)((sh->length[0]/32)%16); + + sh->w[cnt]<<=8; + sh->w[cnt]|=(unsign32)(byt&0xFF); + + sh->length[0]+=8; + if (sh->length[0]==0L) + { + sh->length[1]++; + sh->length[0]=0L; + } + if ((sh->length[0]%512)==0) HASH256_transform(sh); +} + +/* SU= 24 */ +/* Generate 32-byte Hash */ +void HASH256_hash(hash256 *sh,char *digest) +{ + /* pad message and finish - supply digest */ + int i; + unsign32 len0,len1; + len0=sh->length[0]; + len1=sh->length[1]; + HASH256_process(sh,PAD); + while ((sh->length[0]%512)!=448) HASH256_process(sh,ZERO); + sh->w[14]=len1; + sh->w[15]=len0; + HASH256_transform(sh); + for (i=0; i<sh->hlen; i++) + { + /* convert to bytes */ + digest[i]=(char)((sh->h[i/4]>>(8*(3-i%4))) & 0xffL); + } + HASH256_init(sh); +} + + +#define H0_512 0x6a09e667f3bcc908 +#define H1_512 0xbb67ae8584caa73b +#define H2_512 0x3c6ef372fe94f82b +#define H3_512 0xa54ff53a5f1d36f1 +#define H4_512 0x510e527fade682d1 +#define H5_512 0x9b05688c2b3e6c1f +#define H6_512 0x1f83d9abfb41bd6b +#define H7_512 0x5be0cd19137e2179 + +#define H8_512 0xcbbb9d5dc1059ed8 +#define H9_512 0x629a292a367cd507 +#define HA_512 0x9159015a3070dd17 +#define HB_512 0x152fecd8f70e5939 +#define HC_512 0x67332667ffc00b31 +#define HD_512 0x8eb44a8768581511 +#define HE_512 0xdb0c2e0d64f98fa7 +#define HF_512 0x47b5481dbefa4fa4 + +/* */ + +static const unsign64 K_512[80]= +{ + 0x428a2f98d728ae22,0x7137449123ef65cd,0xb5c0fbcfec4d3b2f,0xe9b5dba58189dbbc, + 0x3956c25bf348b538,0x59f111f1b605d019,0x923f82a4af194f9b,0xab1c5ed5da6d8118, + 0xd807aa98a3030242,0x12835b0145706fbe,0x243185be4ee4b28c,0x550c7dc3d5ffb4e2, + 0x72be5d74f27b896f,0x80deb1fe3b1696b1,0x9bdc06a725c71235,0xc19bf174cf692694, + 0xe49b69c19ef14ad2,0xefbe4786384f25e3,0x0fc19dc68b8cd5b5,0x240ca1cc77ac9c65, + 0x2de92c6f592b0275,0x4a7484aa6ea6e483,0x5cb0a9dcbd41fbd4,0x76f988da831153b5, + 0x983e5152ee66dfab,0xa831c66d2db43210,0xb00327c898fb213f,0xbf597fc7beef0ee4, + 0xc6e00bf33da88fc2,0xd5a79147930aa725,0x06ca6351e003826f,0x142929670a0e6e70, + 0x27b70a8546d22ffc,0x2e1b21385c26c926,0x4d2c6dfc5ac42aed,0x53380d139d95b3df, + 0x650a73548baf63de,0x766a0abb3c77b2a8,0x81c2c92e47edaee6,0x92722c851482353b, + 0xa2bfe8a14cf10364,0xa81a664bbc423001,0xc24b8b70d0f89791,0xc76c51a30654be30, + 0xd192e819d6ef5218,0xd69906245565a910,0xf40e35855771202a,0x106aa07032bbd1b8, + 0x19a4c116b8d2d0c8,0x1e376c085141ab53,0x2748774cdf8eeb99,0x34b0bcb5e19b48a8, + 0x391c0cb3c5c95a63,0x4ed8aa4ae3418acb,0x5b9cca4f7763e373,0x682e6ff3d6b2b8a3, + 0x748f82ee5defb2fc,0x78a5636f43172f60,0x84c87814a1f0ab72,0x8cc702081a6439ec, + 0x90befffa23631e28,0xa4506cebde82bde9,0xbef9a3f7b2c67915,0xc67178f2e372532b, + 0xca273eceea26619c,0xd186b8c721c0c207,0xeada7dd6cde0eb1e,0xf57d4f7fee6ed178, + 0x06f067aa72176fba,0x0a637dc5a2c898a6,0x113f9804bef90dae,0x1b710b35131c471b, + 0x28db77f523047d84,0x32caab7b40c72493,0x3c9ebe0a15c9bebc,0x431d67c49c100d4c, + 0x4cc5d4becb3e42b6,0x597f299cfc657e2a,0x5fcb6fab3ad6faec,0x6c44198c4a475817 +}; + + +static void HASH512_transform(hash512 *sh) +{ + /* basic transformation step */ + unsign64 a,b,c,d,e,f,g,h,t1,t2; + int j; + for (j=16; j<80; j++) + sh->w[j]=theta1_512(sh->w[j-2])+sh->w[j-7]+theta0_512(sh->w[j-15])+sh->w[j-16]; + + a=sh->h[0]; + b=sh->h[1]; + c=sh->h[2]; + d=sh->h[3]; + e=sh->h[4]; + f=sh->h[5]; + g=sh->h[6]; + h=sh->h[7]; + + for (j=0; j<80; j++) + { + /* 80 times - mush it up */ + t1=h+Sig1_512(e)+Ch(e,f,g)+K_512[j]+sh->w[j]; + t2=Sig0_512(a)+Maj(a,b,c); + h=g; + g=f; + f=e; + e=d+t1; + d=c; + c=b; + b=a; + a=t1+t2; + } + sh->h[0]+=a; + sh->h[1]+=b; + sh->h[2]+=c; + sh->h[3]+=d; + sh->h[4]+=e; + sh->h[5]+=f; + sh->h[6]+=g; + sh->h[7]+=h; +} + +void HASH384_init(hash384 *sh) +{ + /* re-initialise */ + int i; + for (i=0; i<80; i++) sh->w[i]=0; + sh->length[0]=sh->length[1]=0; + sh->h[0]=H8_512; + sh->h[1]=H9_512; + sh->h[2]=HA_512; + sh->h[3]=HB_512; + sh->h[4]=HC_512; + sh->h[5]=HD_512; + sh->h[6]=HE_512; + sh->h[7]=HF_512; + + sh->hlen=48; + +} + +void HASH384_process(hash384 *sh,int byt) +{ + /* process the next message byte */ + HASH512_process(sh,byt); +} + +void HASH384_hash(hash384 *sh,char *hash) +{ + /* pad message and finish - supply digest */ + HASH512_hash(sh,hash); +} + +void HASH512_init(hash512 *sh) +{ + /* re-initialise */ + int i; + + for (i=0; i<80; i++) sh->w[i]=0; + sh->length[0]=sh->length[1]=0; + sh->h[0]=H0_512; + sh->h[1]=H1_512; + sh->h[2]=H2_512; + sh->h[3]=H3_512; + sh->h[4]=H4_512; + sh->h[5]=H5_512; + sh->h[6]=H6_512; + sh->h[7]=H7_512; + + sh->hlen=64; +} + +void HASH512_process(hash512 *sh,int byt) +{ + /* process the next message byte */ + int cnt; + + cnt=(int)((sh->length[0]/64)%16); + + sh->w[cnt]<<=8; + sh->w[cnt]|=(unsign64)(byt&0xFF); + + sh->length[0]+=8; + if (sh->length[0]==0L) + { + sh->length[1]++; + sh->length[0]=0L; + } + if ((sh->length[0]%1024)==0) HASH512_transform(sh); +} + +void HASH512_hash(hash512 *sh,char *hash) +{ + /* pad message and finish - supply digest */ + int i; + unsign64 len0,len1; + len0=sh->length[0]; + len1=sh->length[1]; + HASH512_process(sh,PAD); + while ((sh->length[0]%1024)!=896) HASH512_process(sh,ZERO); + sh->w[14]=len1; + sh->w[15]=len0; + HASH512_transform(sh); + for (i=0; i<sh->hlen; i++) + { + /* convert to bytes */ + hash[i]=(char)((sh->h[i/8]>>(8*(7-i%8))) & 0xffL); + } + HASH512_init(sh); +} + + + +/* SHA3 */ + +#define SHA3_ROUNDS 24 +#define rotl(x,n) (((x)<<n) | ((x)>>(64-n))) + +/* round constants */ + +static const unsign64 RC[24]= +{ + 0x0000000000000001UL,0x0000000000008082UL,0x800000000000808AUL,0x8000000080008000UL, + 0x000000000000808BUL,0x0000000080000001UL,0x8000000080008081UL,0x8000000000008009UL, + 0x000000000000008AUL,0x0000000000000088UL,0x0000000080008009UL,0x000000008000000AUL, + 0x000000008000808BUL,0x800000000000008BUL,0x8000000000008089UL,0x8000000000008003UL, + 0x8000000000008002UL,0x8000000000000080UL,0x000000000000800AUL,0x800000008000000AUL, + 0x8000000080008081UL,0x8000000000008080UL,0x0000000080000001UL,0x8000000080008008UL +}; + +/* permutation */ + +static void SHA3_transform(sha3 *sh) +{ + int i,j,k; + unsign64 C[5],D[5],B[5][5]; + + for (k=0; k<SHA3_ROUNDS; k++) + { + C[0]=sh->S[0][0]^sh->S[0][1]^sh->S[0][2]^sh->S[0][3]^sh->S[0][4]; + C[1]=sh->S[1][0]^sh->S[1][1]^sh->S[1][2]^sh->S[1][3]^sh->S[1][4]; + C[2]=sh->S[2][0]^sh->S[2][1]^sh->S[2][2]^sh->S[2][3]^sh->S[2][4]; + C[3]=sh->S[3][0]^sh->S[3][1]^sh->S[3][2]^sh->S[3][3]^sh->S[3][4]; + C[4]=sh->S[4][0]^sh->S[4][1]^sh->S[4][2]^sh->S[4][3]^sh->S[4][4]; + + D[0]=C[4]^rotl(C[1],1); + D[1]=C[0]^rotl(C[2],1); + D[2]=C[1]^rotl(C[3],1); + D[3]=C[2]^rotl(C[4],1); + D[4]=C[3]^rotl(C[0],1); + + for (i=0; i<5; i++) + for (j=0; j<5; j++) + sh->S[i][j]^=D[i]; /* let the compiler unroll it! */ + + B[0][0]=sh->S[0][0]; + B[1][3]=rotl(sh->S[0][1],36); + B[2][1]=rotl(sh->S[0][2],3); + B[3][4]=rotl(sh->S[0][3],41); + B[4][2]=rotl(sh->S[0][4],18); + + B[0][2]=rotl(sh->S[1][0],1); + B[1][0]=rotl(sh->S[1][1],44); + B[2][3]=rotl(sh->S[1][2],10); + B[3][1]=rotl(sh->S[1][3],45); + B[4][4]=rotl(sh->S[1][4],2); + + B[0][4]=rotl(sh->S[2][0],62); + B[1][2]=rotl(sh->S[2][1],6); + B[2][0]=rotl(sh->S[2][2],43); + B[3][3]=rotl(sh->S[2][3],15); + B[4][1]=rotl(sh->S[2][4],61); + + B[0][1]=rotl(sh->S[3][0],28); + B[1][4]=rotl(sh->S[3][1],55); + B[2][2]=rotl(sh->S[3][2],25); + B[3][0]=rotl(sh->S[3][3],21); + B[4][3]=rotl(sh->S[3][4],56); + + B[0][3]=rotl(sh->S[4][0],27); + B[1][1]=rotl(sh->S[4][1],20); + B[2][4]=rotl(sh->S[4][2],39); + B[3][2]=rotl(sh->S[4][3],8); + B[4][0]=rotl(sh->S[4][4],14); + + for (i=0; i<5; i++) + for (j=0; j<5; j++) + sh->S[i][j]=B[i][j]^(~B[(i+1)%5][j]&B[(i+2)%5][j]); + + sh->S[0][0]^=RC[k]; + } +} + +/* Re-Initialize. olen is output length in bytes - + should be 28, 32, 48 or 64 (224, 256, 384, 512 bits resp.) */ + +void SHA3_init(sha3 *sh,int olen) +{ + int i,j; + for (i=0; i<5; i++) + for (j=0; j<5; j++) + sh->S[i][j]=0; /* 5x5x8 bytes = 200 bytes of state */ + sh->length=0; + sh->len=olen; + sh->rate=200-2*olen; /* number of bytes consumed in one gulp. Note that some bytes in the + state ("capacity") are not touched. Gulps are smaller for larger digests. + Important that olen<rate */ +} + +/* process a single byte */ +void SHA3_process(sha3 *sh,int byt) +{ + int cnt=(int)(sh->length%sh->rate); + int i,j,b=cnt%8; + cnt/=8; + i=cnt%5; + j=cnt/5; /* process by columns! */ + sh->S[i][j]^=((unsign64)byt<<(8*b)); + sh->length++; + if (sh->length%sh->rate==0) SHA3_transform(sh); +} + +/* squeeze the sponge */ +void SHA3_squeeze(sha3 *sh,char *buff,int len) +{ + int done,i,j,k,m=0; + unsign64 el; + /* extract by columns */ + done=0; + for (;;) + { + for (j=0; j<5; j++) + { + for (i=0; i<5; i++) + { + el=sh->S[i][j]; + for (k=0; k<8; k++) + { + buff[m++]=(el&0xff); + if (m>=len || m%sh->rate==0) + { + done=1; + break; + } + el>>=8; + } + if (done) break; + } + if (done) break; + } + if (m>=len) break; + done=0; + SHA3_transform(sh); + } +} + +void SHA3_hash(sha3 *sh,char *hash) +{ + /* generate a SHA3 hash of appropriate size */ + int q=sh->rate-(sh->length%sh->rate); + if (q==1) SHA3_process(sh,0x86); + else + { + SHA3_process(sh,0x06); /* 0x06 for SHA-3 */ + while ((int)sh->length%sh->rate!=sh->rate-1) SHA3_process(sh,0x00); + SHA3_process(sh,0x80); /* this will force a final transform */ + } + SHA3_squeeze(sh,hash,sh->len); +} + +void SHA3_shake(sha3 *sh,char *buff,int len) +{ + /* SHAKE out a buffer of variable length len */ + int q=sh->rate-(sh->length%sh->rate); + if (q==1) SHA3_process(sh,0x9f); + else + { + SHA3_process(sh,0x1f); // 0x06 for SHA-3 !!!! + while ((int) sh->length%sh->rate!=sh->rate-1) SHA3_process(sh,0x00); + SHA3_process(sh,0x80); /* this will force a final transform */ + } + SHA3_squeeze(sh,buff,len); +} + + +/* test program: should produce digest + +160 bit + +84983e44 1c3bd26e baae4aa1 f95129e5 e54670f1 + +256 bit + +248d6a61 d20638b8 e5c02693 0c3e6039 a33ce459 64ff2167 f6ecedd4 19db06c1 + +512 bit + +8e959b75dae313da 8cf4f72814fc143f 8f7779c6eb9f7fa1 7299aeadb6889018 +501d289e4900f7e4 331b99dec4b5433a c7d329eeb6dd2654 5e96e55b874be909 + +384 bit + +09330c33f71147e8 3d192fc782cd1b47 53111b173b3b05d2 2fa08086e3b0f712 +fcc7c71a557e2db9 66c3e9fa91746039 +*/ +/* +#include <stdio.h> + +char test160[]="abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"; +char test256[]="abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"; +char test512[]="abcdefghbcdefghicdefghijdefghijkefghijklfghijklmghijklmnhijklmnoijklmnopjklmnopqklmnopqrlmnopqrsmnopqrstnopqrstu"; + +int main() +{ + char digest[100]; + int i; + + hash256 sh256; + hash384 sh384; + hash512 sh512; + sha3 SHA3; + + HASH256_init(&sh256); + for (i=0;test256[i]!=0;i++) HASH256_process(&sh256,test256[i]); + HASH256_hash(&sh256,digest); + for (i=0;i<32;i++) printf("%02x",(unsigned char)digest[i]); + printf("\n"); + + HASH384_init(&sh384); + for (i=0;test512[i]!=0;i++) HASH384_process(&sh384,test512[i]); + HASH384_hash(&sh384,digest); + for (i=0;i<48;i++) printf("%02x",(unsigned char)digest[i]); + printf("\n"); + + HASH512_init(&sh512); + for (i=0;test512[i]!=0;i++) HASH512_process(&sh512,test512[i]); + HASH512_hash(&sh512,digest); + for (i=0;i<64;i++) printf("%02x",(unsigned char)digest[i]); + printf("\n"); + + SHA3_init(&SHA3,SHA3_HASH256); + for (i=0;test512[i]!=0;i++) SHA3_process(&SHA3,test512[i]); + SHA3_hash(&sh512,digest); + for (i=0;i<32;i++) printf("%02x",(unsigned char)digest[i]); + printf("\n"); + + SHA3_init(&SHA3,SHA3_HASH512); + for (i=0;test512[i]!=0;i++) SHA3_process(&SHA3,test512[i]); + SHA3_hash(&sh512,digest); + for (i=0;i<64;i++) printf("%02x",(unsigned char)digest[i]); + printf("\n"); + + SHA3_init(&SHA3,SHAKE256); + for (i=0;test512[i]!=0;i++) SHA3_process(&SHA3,test512[i]); + SHA3_shake(&sh512,digest,72); + for (i=0;i<72;i++) printf("%02x",(unsigned char)digest[i]); + printf("\n"); + + + return 0; +} + +*/ http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto-c/blob/8d28d2c3/src/mpin.c.in ---------------------------------------------------------------------- diff --git a/src/mpin.c.in b/src/mpin.c.in new file mode 100644 index 0000000..defbab4 --- /dev/null +++ b/src/mpin.c.in @@ -0,0 +1,939 @@ +/* +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. +*/ + +/* MPIN Functions */ + +/* Version 3.0 - supports Time Permits */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> +#include "mpin_ZZZ.h" + +#define ROUNDUP(a,b) ((a)-1)/(b)+1 + +/* Special mpin hashing */ +static void mpin_hash(int sha,FP4_YYY *f, ECP_ZZZ *P,octet *w) +{ + int i; + BIG_XXX x,y; + char h[64]; + hash256 sha256; + hash512 sha512; + char t[6*MODBYTES_XXX]; // to hold 6 BIGs + int hlen=sha; + + + FP_YYY_redc(x,&(f->a.a)); + BIG_XXX_toBytes(&t[0],x); + FP_YYY_redc(x,&(f->a.b)); + BIG_XXX_toBytes(&t[MODBYTES_XXX],x); + FP_YYY_redc(x,&(f->b.a)); + BIG_XXX_toBytes(&t[2*MODBYTES_XXX],x); + FP_YYY_redc(x,&(f->b.b)); + BIG_XXX_toBytes(&t[3*MODBYTES_XXX],x); + ECP_ZZZ_get(x,y,P); + BIG_XXX_toBytes(&t[4*MODBYTES_XXX],x); + BIG_XXX_toBytes(&t[5*MODBYTES_XXX],y); + + OCT_empty(w); + switch (sha) + { + case SHA256: + HASH256_init(&sha256); + for (i=0; i<6*MODBYTES_XXX; i++) HASH256_process(&sha256,t[i]); + HASH256_hash(&sha256,h); + break; + case SHA384: + HASH384_init(&sha512); + for (i=0; i<6*MODBYTES_XXX; i++) HASH384_process(&sha512,t[i]); + HASH384_hash(&sha512,h); + break; + case SHA512: + HASH512_init(&sha512); + for (i=0; i<6*MODBYTES_XXX; i++) HASH512_process(&sha512,t[i]); + HASH512_hash(&sha512,h); + break; + } + + OCT_jbytes(w,h,AESKEY_ZZZ); + for (i=0; i<hlen; i++) h[i]=0; +} + +/* these next two functions help to implement elligator squared - http://eprint.iacr.org/2014/043 */ +/* maps a random u to a point on the curve */ +static void map(ECP_ZZZ *P,BIG_XXX u,int cb) +{ + BIG_XXX x,q; + + BIG_XXX_rcopy(q,Modulus_YYY); + BIG_XXX_copy(x,u); + BIG_XXX_mod(x,q); + + while (!ECP_ZZZ_setx(P,x,cb)) + { + BIG_XXX_inc(x,1); + BIG_XXX_norm(x); + } +} + +/* returns u derived from P. Random value in range 1 to return value should then be added to u */ +static int unmap(BIG_XXX u,int *cb,ECP_ZZZ *P) +{ + int s,r=0; + BIG_XXX x; + + s=ECP_ZZZ_get(x,x,P); + BIG_XXX_copy(u,x); + do + { + BIG_XXX_dec(u,1); + BIG_XXX_norm(u); + r++; + } + while (!ECP_ZZZ_setx(P,u,s)); + ECP_ZZZ_setx(P,x,s); + + *cb=s; + + return r; +} + +/* these next two functions implement elligator squared - http://eprint.iacr.org/2014/043 */ +/* Elliptic curve point E in format (0x04,x,y} is converted to form {0x0-,u,v} */ +/* Note that u and v are indistinguisible from random strings */ +int MPIN_ZZZ_ENCODING(csprng *RNG,octet *E) +{ + int rn,m,su,sv,res=0; + + BIG_XXX q,u,v; + ECP_ZZZ P,W; + + if (!ECP_ZZZ_fromOctet(&P,E)) res=MPIN_INVALID_POINT; + if (res==0) + { + BIG_XXX_rcopy(q,Modulus_YYY); + + BIG_XXX_randomnum(u,q,RNG); + + su=RAND_byte(RNG); + if (su<0) su=-su; + su%=2; + map(&W,u,su); + ECP_ZZZ_sub(&P,&W); + + rn=unmap(v,&sv,&P); + m=RAND_byte(RNG); + if (m<0) m=-m; + m%=rn; + BIG_XXX_inc(v,m+1); + E->val[0]=su+2*sv; + BIG_XXX_toBytes(&(E->val[1]),u); + BIG_XXX_toBytes(&(E->val[PFS_ZZZ+1]),v); + } + return res; +} + +int MPIN_ZZZ_DECODING(octet *D) +{ + int su,sv; + BIG_XXX u,v; + ECP_ZZZ P,W; + int res=0; + + if ((D->val[0]&0x04)!=0) res=MPIN_INVALID_POINT; + if (res==0) + { + + BIG_XXX_fromBytes(u,&(D->val[1])); + BIG_XXX_fromBytes(v,&(D->val[PFS_ZZZ+1])); + + su=D->val[0]&1; + sv=(D->val[0]>>1)&1; + map(&W,u,su); + map(&P,v,sv); + ECP_ZZZ_add(&P,&W); + ECP_ZZZ_toOctet(D,&P); + } + + return res; +} + +/* R=R1+R2 in group G1 */ +int MPIN_ZZZ_RECOMBINE_G1(octet *R1,octet *R2,octet *R) +{ + ECP_ZZZ P,T; + int res=0; + if (res==0) + { + if (!ECP_ZZZ_fromOctet(&P,R1)) res=MPIN_INVALID_POINT; + if (!ECP_ZZZ_fromOctet(&T,R2)) res=MPIN_INVALID_POINT; + } + if (res==0) + { + ECP_ZZZ_add(&P,&T); + ECP_ZZZ_toOctet(R,&P); + } + return res; +} + +/* W=W1+W2 in group G2 */ +int MPIN_ZZZ_RECOMBINE_G2(octet *W1,octet *W2,octet *W) +{ + ECP2_ZZZ Q,T; + int res=0; + if (!ECP2_ZZZ_fromOctet(&Q,W1)) res=MPIN_INVALID_POINT; + if (!ECP2_ZZZ_fromOctet(&T,W2)) res=MPIN_INVALID_POINT; + if (res==0) + { + ECP2_ZZZ_add(&Q,&T); + ECP2_ZZZ_toOctet(W,&Q); + } + return res; +} + +/* create random secret S */ +int MPIN_ZZZ_RANDOM_GENERATE(csprng *RNG,octet* S) +{ + BIG_XXX r,s; + + BIG_XXX_rcopy(r,CURVE_Order_ZZZ); + BIG_XXX_randomnum(s,r,RNG); +#ifdef AES_S + BIG_XXX_mod2m(s,2*AES_S); +#endif + BIG_XXX_toBytes(S->val,s); + S->len=MODBYTES_XXX; + return 0; +} + +/* Extract PIN from TOKEN for identity CID */ +int MPIN_ZZZ_EXTRACT_PIN(int sha,octet *CID,int pin,octet *TOKEN) +{ + pin%=MAXPIN; + return MPIN_ZZZ_EXTRACT_FACTOR(sha,CID,pin,PBLEN,TOKEN); +} + +/* Extract a factor < 32 bits for identity CID */ +int MPIN_ZZZ_EXTRACT_FACTOR(int sha,octet *CID,int factor,int facbits,octet *TOKEN) +{ + ECP_ZZZ P,R; + int res=0; + char h[MODBYTES_XXX]; + octet H= {0,sizeof(h),h}; + + if (!ECP_ZZZ_fromOctet(&P,TOKEN)) res=MPIN_INVALID_POINT; + if (res==0) + { + mhashit(sha,-1,CID,&H); + ECP_ZZZ_mapit(&R,&H); + + ECP_ZZZ_pinmul(&R,factor,facbits); + ECP_ZZZ_sub(&P,&R); + + ECP_ZZZ_toOctet(TOKEN,&P); + } + return res; +} + +/* Extract a factor < 32 bits for identity CID */ +int MPIN_ZZZ_RESTORE_FACTOR(int sha,octet *CID,int factor,int facbits,octet *TOKEN) +{ + ECP_ZZZ P,R; + int res=0; + char h[MODBYTES_XXX]; + octet H= {0,sizeof(h),h}; + + if (!ECP_ZZZ_fromOctet(&P,TOKEN)) res=MPIN_INVALID_POINT; + if (res==0) + { + mhashit(sha,-1,CID,&H); + ECP_ZZZ_mapit(&R,&H); + + ECP_ZZZ_pinmul(&R,factor,facbits); + ECP_ZZZ_add(&P,&R); + + ECP_ZZZ_toOctet(TOKEN,&P); + } + return res; +} + +/* Implement step 2 on client side of MPin protocol - SEC=-(x+y)*SEC */ +int MPIN_ZZZ_CLIENT_2(octet *X,octet *Y,octet *SEC) +{ + BIG_XXX px,py,r; + ECP_ZZZ P; + int res=0; + BIG_XXX_rcopy(r,CURVE_Order_ZZZ); + if (!ECP_ZZZ_fromOctet(&P,SEC)) res=MPIN_INVALID_POINT; + if (res==0) + { + BIG_XXX_fromBytes(px,X->val); + BIG_XXX_fromBytes(py,Y->val); + BIG_XXX_add(px,px,py); + BIG_XXX_mod(px,r); + // BIG_XXX_sub(px,r,px); + PAIR_ZZZ_G1mul(&P,px); + ECP_ZZZ_neg(&P); + ECP_ZZZ_toOctet(SEC,&P); + } + return res; +} + +/* + W=x*H(G); + if RNG == NULL then X is passed in + if RNG != NULL the X is passed out + if type=0 W=x*G where G is point on the curve, else W=x*M(G), where M(G) is mapping of octet G to point on the curve +*/ + +int MPIN_ZZZ_GET_G1_MULTIPLE(csprng *RNG,int type,octet *X,octet *G,octet *W) +{ + ECP_ZZZ P; + BIG_XXX r,x; + int res=0; + if (RNG!=NULL) + { + BIG_XXX_rcopy(r,CURVE_Order_ZZZ); + BIG_XXX_randomnum(x,r,RNG); +#ifdef AES_S + BIG_XXX_mod2m(x,2*AES_S); +#endif + X->len=MODBYTES_XXX; + BIG_XXX_toBytes(X->val,x); + } + else + BIG_XXX_fromBytes(x,X->val); + + if (type==0) + { + if (!ECP_ZZZ_fromOctet(&P,G)) res=MPIN_INVALID_POINT; + } + else + { + ECP_ZZZ_mapit(&P,G); + } + + if (res==0) + { + PAIR_ZZZ_G1mul(&P,x); + ECP_ZZZ_toOctet(W,&P); + } + return res; +} + +/* + if RNG == NULL then X is passed in + if RNG != NULL the X is passed out + W=x*G where G is point on the curve + if type==1 W=(x^-1)G +*/ + +int MPIN_ZZZ_GET_G2_MULTIPLE(csprng *RNG,int type,octet *X,octet *G,octet *W) +{ + ECP2_ZZZ P; + BIG_XXX r,x; + int res=0; + BIG_XXX_rcopy(r,CURVE_Order_ZZZ); + if (RNG!=NULL) + { + BIG_XXX_randomnum(x,r,RNG); +#ifdef AES_S + BIG_XXX_mod2m(x,2*AES_S); +#endif + X->len=MODBYTES_XXX; + BIG_XXX_toBytes(X->val,x); + } + else + { + BIG_XXX_fromBytes(x,X->val); + if (type==1) BIG_XXX_invmodp(x,x,r); + } + + if (!ECP2_ZZZ_fromOctet(&P,G)) res=MPIN_INVALID_POINT; + + if (res==0) + { + PAIR_ZZZ_G2mul(&P,x); + ECP2_ZZZ_toOctet(W,&P); + } + return res; +} + + + +/* Client secret CST=s*H(CID) where CID is client ID and s is master secret */ +/* CID is hashed externally */ +int MPIN_ZZZ_GET_CLIENT_SECRET(octet *S,octet *CID,octet *CST) +{ + return MPIN_ZZZ_GET_G1_MULTIPLE(NULL,1,S,CID,CST); +} + +/* Implement step 1 on client side of MPin protocol */ +int MPIN_ZZZ_CLIENT_1(int sha,int date,octet *CLIENT_ID,csprng *RNG,octet *X,int pin,octet *TOKEN,octet *SEC,octet *xID,octet *xCID,octet *PERMIT) +{ + BIG_XXX r,x; + ECP_ZZZ P,T,W; + int res=0; + char h[MODBYTES_XXX]; + octet H= {0,sizeof(h),h}; + + BIG_XXX_rcopy(r,CURVE_Order_ZZZ); + if (RNG!=NULL) + { + BIG_XXX_randomnum(x,r,RNG); +#ifdef AES_S + BIG_XXX_mod2m(x,2*AES_S); +#endif + X->len=MODBYTES_XXX; + BIG_XXX_toBytes(X->val,x); + } + else + BIG_XXX_fromBytes(x,X->val); + + mhashit(sha,-1,CLIENT_ID,&H); + + ECP_ZZZ_mapit(&P,&H); + + if (!ECP_ZZZ_fromOctet(&T,TOKEN)) res=MPIN_INVALID_POINT; + + if (res==0) + { + pin%=MAXPIN; + + ECP_ZZZ_copy(&W,&P); // W=H(ID) + ECP_ZZZ_pinmul(&W,pin,PBLEN); // W=alpha.H(ID) + ECP_ZZZ_add(&T,&W); // T=Token+alpha.H(ID) = s.H(ID) + + if (date) + { + if (PERMIT!=NULL) + { + if (!ECP_ZZZ_fromOctet(&W,PERMIT)) res=MPIN_INVALID_POINT; + ECP_ZZZ_add(&T,&W); // SEC=s.H(ID)+s.H(T|ID) + } + mhashit(sha,date,&H,&H); + + ECP_ZZZ_mapit(&W,&H); + if (xID!=NULL) + { + PAIR_ZZZ_G1mul(&P,x); // P=x.H(ID) + ECP_ZZZ_toOctet(xID,&P); // xID + PAIR_ZZZ_G1mul(&W,x); // W=x.H(T|ID) + ECP_ZZZ_add(&P,&W); + } + else + { + ECP_ZZZ_add(&P,&W); + PAIR_ZZZ_G1mul(&P,x); + } + if (xCID!=NULL) ECP_ZZZ_toOctet(xCID,&P); // U + } + else + { + if (xID!=NULL) + { + PAIR_ZZZ_G1mul(&P,x); // P=x.H(ID) + ECP_ZZZ_toOctet(xID,&P); // xID + } + } + } + + if (res==0) + ECP_ZZZ_toOctet(SEC,&T); // V + + return res; +} + +/* Extract Server Secret SST=S*Q where Q is fixed generator in G2 and S is master secret */ +int MPIN_ZZZ_GET_SERVER_SECRET(octet *S,octet *SST) +{ + BIG_XXX r,s; + ECP2_ZZZ Q; + int res=0; + + BIG_XXX_rcopy(r,CURVE_Order_ZZZ); + + ECP2_ZZZ_generator(&Q); + + if (res==0) + { + + BIG_XXX_fromBytes(s,S->val); + PAIR_ZZZ_G2mul(&Q,s); + ECP2_ZZZ_toOctet(SST,&Q); + } + + return res; +} + + +/* Time Permit CTT=s*H(date|H(CID)) where s is master secret */ +int MPIN_ZZZ_GET_CLIENT_PERMIT(int sha,int date,octet *S,octet *CID,octet *CTT) +{ + BIG_XXX s; + ECP_ZZZ P; + char h[MODBYTES_XXX]; + octet H= {0,sizeof(h),h}; + + mhashit(sha,date,CID,&H); + + ECP_ZZZ_mapit(&P,&H); + BIG_XXX_fromBytes(s,S->val); + + PAIR_ZZZ_G1mul(&P,s); + ECP_ZZZ_toOctet(CTT,&P); + return 0; +} + +// if date=0 only use HID, set HCID=NULL +// if date and PE, use HID and HCID + +/* Outputs H(CID) and H(CID)+H(T|H(CID)) for time permits. If no time permits set HTID=NULL */ +void MPIN_ZZZ_SERVER_1(int sha,int date,octet *CID,octet *HID,octet *HTID) +{ + char h[MODBYTES_XXX]; + octet H= {0,sizeof(h),h}; + ECP_ZZZ P,R; + +#ifdef USE_ANONYMOUS + ECP_ZZZ_mapit(&P,CID); +#else + mhashit(sha,-1,CID,&H); + ECP_ZZZ_mapit(&P,&H); +#endif + + ECP_ZZZ_toOctet(HID,&P); // new + + if (date) + { +#ifdef USE_ANONYMOUS + mhashit(sha,date,CID,&H); +#else + mhashit(sha,date,&H,&H); +#endif + ECP_ZZZ_mapit(&R,&H); + ECP_ZZZ_add(&P,&R); + ECP_ZZZ_toOctet(HTID,&P); + } +} + +/* Implement M-Pin on server side */ +int MPIN_ZZZ_SERVER_2(int date,octet *HID,octet *HTID,octet *Y,octet *SST,octet *xID,octet *xCID,octet *mSEC,octet *E,octet *F,octet *Pa) +{ + BIG_XXX px,py,y; + FP12_YYY g; + ECP2_ZZZ Q,sQ; + ECP_ZZZ P,R; + int res=0; + + ECP2_ZZZ_generator(&Q); + + // key-escrow less scheme: use Pa instead of Q in pairing computation + // Q left for backward compatiblity + if (Pa!=NULL) + { + if (!ECP2_ZZZ_fromOctet(&Q, Pa)) res=MPIN_INVALID_POINT; + } + + if (res==0) + { + if (!ECP2_ZZZ_fromOctet(&sQ,SST)) res=MPIN_INVALID_POINT; + } + + if (res==0) + { + if (date) + { + BIG_XXX_fromBytes(px,&(xCID->val[1])); + BIG_XXX_fromBytes(py,&(xCID->val[PFS_ZZZ+1])); + } + else + { + BIG_XXX_fromBytes(px,&(xID->val[1])); + BIG_XXX_fromBytes(py,&(xID->val[PFS_ZZZ+1])); + } + if (!ECP_ZZZ_set(&R,px,py)) res=MPIN_INVALID_POINT; // x(A+AT) + } + if (res==0) + { + BIG_XXX_fromBytes(y,Y->val); + if (date) + { + if (!ECP_ZZZ_fromOctet(&P,HTID)) res=MPIN_INVALID_POINT; + } + else + { + if (!ECP_ZZZ_fromOctet(&P,HID)) res=MPIN_INVALID_POINT; + } + } + if (res==0) + { + PAIR_ZZZ_G1mul(&P,y); // y(A+AT) + ECP_ZZZ_add(&P,&R); // x(A+AT)+y(A+T) + ECP_ZZZ_affine(&P); + if (!ECP_ZZZ_fromOctet(&R,mSEC)) res=MPIN_INVALID_POINT; // V + } + if (res==0) + { + + PAIR_ZZZ_double_ate(&g,&Q,&R,&sQ,&P); + PAIR_ZZZ_fexp(&g); + + if (!FP12_YYY_isunity(&g)) + { + if (HID!=NULL && xID!=NULL && E!=NULL && F !=NULL) + { + /* xID is set to NULL if there is no way to calculate PIN error */ + FP12_YYY_toOctet(E,&g); + + /* Note error is in the PIN, not in the time permit! Hence the need to exclude Time Permit from this check */ + + if (date) + { + if (!ECP_ZZZ_fromOctet(&P,HID)) res=MPIN_INVALID_POINT; + if (!ECP_ZZZ_fromOctet(&R,xID)) res=MPIN_INVALID_POINT; // U + + if (res==0) + { + PAIR_ZZZ_G1mul(&P,y); // yA + ECP_ZZZ_add(&P,&R); // yA+xA + ECP_ZZZ_affine(&P); + } + } + if (res==0) + { + PAIR_ZZZ_ate(&g,&Q,&P); + PAIR_ZZZ_fexp(&g); + FP12_YYY_toOctet(F,&g); + } + } + res=MPIN_BAD_PIN; + } + } + + return res; +} + +#if MAXPIN==10000 +#define MR_TS 10 /* 2^10/10 approx = sqrt(MAXPIN) */ +#define TRAP 200 /* 2*sqrt(MAXPIN) */ +#endif + +#if MAXPIN==1000000 +#define MR_TS 14 +#define TRAP 2000 +#endif + +/* Pollards kangaroos used to return PIN error */ +int MPIN_ZZZ_KANGAROO(octet *E,octet *F) +{ + int i,j,m,s,dn,dm,steps; + int distance[MR_TS]; + FP12_YYY ge,gf,t,table[MR_TS]; + int res=0; + + FP12_YYY_fromOctet(&ge,E); + FP12_YYY_fromOctet(&gf,F); + + FP12_YYY_copy(&t,&gf); + + for (s=1,m=0; m<MR_TS; m++) + { + distance[m]=s; + FP12_YYY_copy(&table[m],&t); + s*=2; + FP12_YYY_usqr(&t,&t); + FP12_YYY_reduce(&t); + } + + FP12_YYY_one(&t); + + for (dn=0,j=0; j<TRAP; j++) + { + i=t.a.a.a.g[0]%MR_TS; + + FP12_YYY_mul(&t,&table[i]); + FP12_YYY_reduce(&t); + dn+=distance[i]; + } + + FP12_YYY_conj(&gf,&t); + steps=0; + dm=0; + while (dm-dn<MAXPIN) + { + steps++; + if (steps>4*TRAP) break; + + i=ge.a.a.a.g[0]%MR_TS; + + FP12_YYY_mul(&ge,&table[i]); + FP12_YYY_reduce(&ge); + dm+=distance[i]; + if (FP12_YYY_equals(&ge,&t)) + { + res=dm-dn; + break; + } + if (FP12_YYY_equals(&ge,&gf)) + { + res=dn-dm; + break; + } + } + if (steps>4*TRAP || dm-dn>=MAXPIN) + { + res=0; /* Trap Failed - probable invalid token */ + } + + return res; +} + +/* Functions to support M-Pin Full */ + +int MPIN_ZZZ_PRECOMPUTE(octet *TOKEN,octet *CID,octet *CP,octet *G1,octet *G2) +{ + ECP_ZZZ P,T; + ECP2_ZZZ Q; + FP12_YYY g; + int res=0; + + if (!ECP_ZZZ_fromOctet(&T,TOKEN)) res=MPIN_INVALID_POINT; + + if (res==0) + { + ECP_ZZZ_mapit(&P,CID); + if (CP!=NULL) + { + if (!ECP2_ZZZ_fromOctet(&Q,CP)) res=MPIN_INVALID_POINT; + } + else + { + ECP2_ZZZ_generator(&Q); + } + } + if (res==0) + { + PAIR_ZZZ_ate(&g,&Q,&T); + PAIR_ZZZ_fexp(&g); + + FP12_YYY_toOctet(G1,&g); + if (G2!=NULL) + { + PAIR_ZZZ_ate(&g,&Q,&P); + PAIR_ZZZ_fexp(&g); + FP12_YYY_toOctet(G2,&g); + } + } + return res; +} + +/* calculate common key on client side */ +/* wCID = w.(A+AT) */ +int MPIN_ZZZ_CLIENT_KEY(int sha,octet *G1,octet *G2,int pin,octet *R,octet *X,octet *H,octet *wCID,octet *CK) +{ + FP12_YYY g1,g2; + FP4_YYY c; + ECP_ZZZ W; + int res=0; + BIG_XXX r,z,x,h; + + FP12_YYY_fromOctet(&g1,G1); + FP12_YYY_fromOctet(&g2,G2); + BIG_XXX_fromBytes(z,R->val); + BIG_XXX_fromBytes(x,X->val); + BIG_XXX_fromBytes(h,H->val); + + if (!ECP_ZZZ_fromOctet(&W,wCID)) res=MPIN_INVALID_POINT; + + if (res==0) + { + BIG_XXX_rcopy(r,CURVE_Order_ZZZ); + BIG_XXX_add(z,z,h); // new + BIG_XXX_mod(z,r); + + FP12_YYY_pinpow(&g2,pin,PBLEN); + FP12_YYY_mul(&g1,&g2); + + PAIR_ZZZ_G1mul(&W,x); + + FP12_YYY_compow(&c,&g1,z,r); + + mpin_hash(sha,&c,&W,CK); + + } + return res; +} + +/* calculate common key on server side */ +/* Z=r.A - no time permits involved */ + +int MPIN_ZZZ_SERVER_KEY(int sha,octet *Z,octet *SST,octet *W,octet *H,octet *HID,octet *xID,octet *xCID,octet *SK) +{ + int res=0; + FP12_YYY g; + FP4_YYY c; + ECP_ZZZ R,U,A; + ECP2_ZZZ sQ; + BIG_XXX w,h; + + if (!ECP2_ZZZ_fromOctet(&sQ,SST)) res=MPIN_INVALID_POINT; + if (!ECP_ZZZ_fromOctet(&R,Z)) res=MPIN_INVALID_POINT; + + + if (!ECP_ZZZ_fromOctet(&A,HID)) res=MPIN_INVALID_POINT; + + // new + if (xCID!=NULL) + { + if (!ECP_ZZZ_fromOctet(&U,xCID)) res=MPIN_INVALID_POINT; + } + else + { + if (!ECP_ZZZ_fromOctet(&U,xID)) res=MPIN_INVALID_POINT; + } + BIG_XXX_fromBytes(w,W->val); + BIG_XXX_fromBytes(h,H->val); + + + PAIR_ZZZ_ate(&g,&sQ,&A); + PAIR_ZZZ_fexp(&g); + + if (res==0) + { + PAIR_ZZZ_G1mul(&A,h); + ECP_ZZZ_add(&R,&A); // new + ECP_ZZZ_affine(&R); + PAIR_ZZZ_ate(&g,&sQ,&R); + PAIR_ZZZ_fexp(&g); + PAIR_ZZZ_G1mul(&U,w); + FP12_YYY_trace(&c,&g); + mpin_hash(sha,&c,&U,SK); + } + return res; +} + +/* Generate Y = H(TimeValue, xCID/xID) */ +void MPIN_ZZZ_GET_Y(int sha,int TimeValue,octet *xCID,octet *Y) +{ + BIG_XXX q,y; + char h[MODBYTES_XXX]; + octet H= {0,sizeof(h),h}; + + mhashit(sha,TimeValue,xCID,&H); + BIG_XXX_fromBytes(y,H.val); + BIG_XXX_rcopy(q,CURVE_Order_ZZZ); + BIG_XXX_mod(y,q); + BIG_XXX_toBytes(Y->val,y); + Y->len=PGS_ZZZ; +} + +/* One pass MPIN Client */ +int MPIN_ZZZ_CLIENT(int sha,int date,octet *ID,csprng *RNG,octet *X,int pin,octet *TOKEN,octet *V,octet *U,octet *UT,octet *TP,octet *MESSAGE,int TimeValue,octet *Y) +{ + int rtn=0; + char m[M_SIZE_ZZZ]; + octet M= {0,sizeof(m),m}; + + octet *pID; + if (date == 0) + pID = U; + else + pID = UT; + + rtn = MPIN_ZZZ_CLIENT_1(sha,date,ID,RNG,X,pin,TOKEN,V,U,UT,TP); + if (rtn != 0) + return rtn; + + OCT_joctet(&M,pID); + if (MESSAGE!=NULL) + { + OCT_joctet(&M,MESSAGE); + } + + MPIN_ZZZ_GET_Y(sha,TimeValue,&M,Y); + + rtn = MPIN_ZZZ_CLIENT_2(X,Y,V); + if (rtn != 0) + return rtn; + + return 0; +} + +/* One pass MPIN Server */ +int MPIN_ZZZ_SERVER(int sha,int date,octet *HID,octet *HTID,octet *Y,octet *sQ,octet *U,octet *UT,octet *V,octet *E,octet *F,octet *ID,octet *MESSAGE,int TimeValue, octet *Pa) +{ + int rtn=0; + char m[M_SIZE_ZZZ]; + octet M= {0,sizeof(m),m}; + + octet *pU; + if (date == 0) + pU = U; + else + pU = UT; + + MPIN_ZZZ_SERVER_1(sha,date,ID,HID,HTID); + + OCT_joctet(&M,pU); + if (MESSAGE!=NULL) + { + OCT_joctet(&M,MESSAGE); + } + + MPIN_ZZZ_GET_Y(sha,TimeValue,&M,Y); + + rtn = MPIN_ZZZ_SERVER_2(date,HID,HTID,Y,sQ,U,UT,V,E,F,Pa); + if (rtn != 0) + return rtn; + + return 0; +} + +int MPIN_ZZZ_GET_DVS_KEYPAIR(csprng *R,octet *Z,octet *Pa) +{ + BIG_XXX z,r; + ECP2_ZZZ Q; + int res=0; + + BIG_XXX_rcopy(r,CURVE_Order_ZZZ); + + if (R!=NULL) + { + BIG_XXX_randomnum(z,r,R); + Z->len=MODBYTES_XXX; + BIG_XXX_toBytes(Z->val,z); + } + else + BIG_XXX_fromBytes(z,Z->val); + + BIG_XXX_invmodp(z,z,r); + + ECP2_ZZZ_generator(&Q); + + if (res==0) + { + PAIR_ZZZ_G2mul(&Q,z); + ECP2_ZZZ_toOctet(Pa,&Q); + } + + return res; +}
