http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/c/fp12.c ---------------------------------------------------------------------- diff --git a/version22/c/fp12.c b/version22/c/fp12.c new file mode 100644 index 0000000..f7d9815 --- /dev/null +++ b/version22/c/fp12.c @@ -0,0 +1,727 @@ +/* +Licensed to the Apache Software Foundation (ASF) under one +or more contributor license agreements. See the NOTICE file +distributed with this work for additional information +regarding copyright ownership. The ASF licenses this file +to you under the Apache License, Version 2.0 (the +"License"); you may not use this file except in compliance +with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, +software distributed under the License is distributed on an +"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +KIND, either express or implied. See the License for the +specific language governing permissions and limitations +under the License. +*/ + +/* AMCL Fp^12 functions */ +/* SU=m, m is Stack Usage (no lazy )*/ +/* FP12 elements are of the form a+i.b+i^2.c */ + +#include "amcl.h" + +/* test x==0 ? */ +/* SU= 8 */ +int FP12_iszilch(FP12 *x) +{ + if (FP4_iszilch(&(x->a)) && FP4_iszilch(&(x->b)) && FP4_iszilch(&(x->c))) return 1; + return 0; +} + +/* test x==1 ? */ +/* SU= 8 */ +int FP12_isunity(FP12 *x) +{ + if (FP4_isunity(&(x->a)) && FP4_iszilch(&(x->b)) && FP4_iszilch(&(x->c))) return 1; + return 0; +} + +/* FP12 copy w=x */ +/* SU= 16 */ +void FP12_copy(FP12 *w,FP12 *x) +{ + if (x==w) return; + FP4_copy(&(w->a),&(x->a)); + FP4_copy(&(w->b),&(x->b)); + FP4_copy(&(w->c),&(x->c)); +} + +/* FP12 w=1 */ +/* SU= 8 */ +void FP12_one(FP12 *w) +{ + FP4_one(&(w->a)); + FP4_zero(&(w->b)); + FP4_zero(&(w->c)); +} + +/* return 1 if x==y, else 0 */ +/* SU= 16 */ +int FP12_equals(FP12 *x,FP12 *y) +{ + if (FP4_equals(&(x->a),&(y->a)) && FP4_equals(&(x->b),&(y->b)) && FP4_equals(&(x->b),&(y->b))) + return 1; + return 0; +} + +/* Set w=conj(x) */ +/* SU= 8 */ +void FP12_conj(FP12 *w,FP12 *x) +{ + FP12_copy(w,x); + FP4_conj(&(w->a),&(w->a)); + FP4_nconj(&(w->b),&(w->b)); + FP4_conj(&(w->c),&(w->c)); +} + +/* Create FP12 from FP4 */ +/* SU= 8 */ +void FP12_from_FP4(FP12 *w,FP4 *a) +{ + FP4_copy(&(w->a),a); + FP4_zero(&(w->b)); + FP4_zero(&(w->c)); +} + +/* Create FP12 from 3 FP4's */ +/* SU= 16 */ +void FP12_from_FP4s(FP12 *w,FP4 *a,FP4 *b,FP4 *c) +{ + FP4_copy(&(w->a),a); + FP4_copy(&(w->b),b); + FP4_copy(&(w->c),c); +} + +/* Granger-Scott Unitary Squaring. This does not benefit from lazy reduction */ +/* SU= 600 */ +void FP12_usqr(FP12 *w,FP12 *x) +{ + FP4 A,B,C,D; + + FP4_copy(&A,&(x->a)); + + FP4_sqr(&(w->a),&(x->a)); + FP4_add(&D,&(w->a),&(w->a)); + FP4_add(&(w->a),&D,&(w->a)); + + FP4_norm(&(w->a)); + FP4_nconj(&A,&A); + + FP4_add(&A,&A,&A); + FP4_add(&(w->a),&(w->a),&A); + FP4_sqr(&B,&(x->c)); + FP4_times_i(&B); + + FP4_add(&D,&B,&B); + FP4_add(&B,&B,&D); + FP4_norm(&B); + + FP4_sqr(&C,&(x->b)); + + FP4_add(&D,&C,&C); + FP4_add(&C,&C,&D); + + FP4_norm(&C); + FP4_conj(&(w->b),&(x->b)); + FP4_add(&(w->b),&(w->b),&(w->b)); + FP4_nconj(&(w->c),&(x->c)); + + FP4_add(&(w->c),&(w->c),&(w->c)); + FP4_add(&(w->b),&B,&(w->b)); + FP4_add(&(w->c),&C,&(w->c)); + FP12_reduce(w); /* reduce here as in pow function repeated squarings would trigger multiple reductions */ + +} + +/* FP12 squaring w=x^2 */ +/* SU= 600 */ +void FP12_sqr(FP12 *w,FP12 *x) +{ + /* Use Chung-Hasan SQR2 method from http://cacr.uwaterloo.ca/techreports/2006/cacr2006-24.pdf */ + + FP4 A,B,C,D; + + FP4_sqr(&A,&(x->a)); + FP4_mul(&B,&(x->b),&(x->c)); + FP4_add(&B,&B,&B); + FP4_sqr(&C,&(x->c)); + FP4_mul(&D,&(x->a),&(x->b)); + FP4_add(&D,&D,&D); + FP4_add(&(w->c),&(x->a),&(x->c)); + FP4_add(&(w->c),&(x->b),&(w->c)); + + FP4_sqr(&(w->c),&(w->c)); + + FP4_copy(&(w->a),&A); + + FP4_add(&A,&A,&B); + + FP4_norm(&A); + + FP4_add(&A,&A,&C); + FP4_add(&A,&A,&D); + + FP4_norm(&A); + + FP4_neg(&A,&A); + FP4_times_i(&B); + FP4_times_i(&C); + + FP4_add(&(w->a),&(w->a),&B); + FP4_add(&(w->b),&C,&D); + FP4_add(&(w->c),&(w->c),&A); + + FP12_norm(w); +} + +/* FP12 full multiplication w=w*y */ + + +/* SU= 896 */ +/* FP12 full multiplication w=w*y */ +void FP12_mul(FP12 *w,FP12 *y) +{ + FP4 z0,z1,z2,z3,t0,t1; + + FP4_mul(&z0,&(w->a),&(y->a)); + FP4_mul(&z2,&(w->b),&(y->b)); // + + FP4_add(&t0,&(w->a),&(w->b)); + FP4_add(&t1,&(y->a),&(y->b)); // + FP4_mul(&z1,&t0,&t1); + FP4_add(&t0,&(w->b),&(w->c)); + + FP4_add(&t1,&(y->b),&(y->c)); // + FP4_mul(&z3,&t0,&t1); + + FP4_neg(&t0,&z0); + FP4_neg(&t1,&z2); + + FP4_add(&z1,&z1,&t0); // z1=z1-z0 + + FP4_norm(&z1); + + FP4_add(&(w->b),&z1,&t1); +// z1=z1-z2 + FP4_add(&z3,&z3,&t1); // z3=z3-z2 + FP4_add(&z2,&z2,&t0); // z2=z2-z0 + + FP4_add(&t0,&(w->a),&(w->c)); + + FP4_add(&t1,&(y->a),&(y->c)); + FP4_mul(&t0,&t1,&t0); + FP4_add(&z2,&z2,&t0); + + FP4_mul(&t0,&(w->c),&(y->c)); + FP4_neg(&t1,&t0); + + FP4_norm(&z2); + FP4_norm(&z3); + FP4_norm(&(w->b)); + + FP4_add(&(w->c),&z2,&t1); + FP4_add(&z3,&z3,&t1); + FP4_times_i(&t0); + FP4_add(&(w->b),&(w->b),&t0); + + FP4_times_i(&z3); + FP4_add(&(w->a),&z0,&z3); + + FP12_norm(w); +} + +/* FP12 multiplication w=w*y */ +/* SU= 744 */ +/* catering for special case that arises from special form of ATE pairing line function */ +void FP12_smul(FP12 *w,FP12 *y) +{ + FP4 z0,z2,z3,t0,t1; + + FP4_copy(&z3,&(w->b)); + FP4_mul(&z0,&(w->a),&(y->a)); + FP4_pmul(&z2,&(w->b),&(y->b).a); + FP4_add(&(w->b),&(w->a),&(w->b)); + FP4_copy(&t1,&(y->a)); + FP2_add(&t1.a,&t1.a,&(y->b).a); + + FP4_mul(&(w->b),&(w->b),&t1); + FP4_add(&z3,&z3,&(w->c)); + FP4_pmul(&z3,&z3,&(y->b).a); + FP4_neg(&t0,&z0); + FP4_neg(&t1,&z2); + + FP4_add(&(w->b),&(w->b),&t0); // z1=z1-z0 + + FP4_norm(&(w->b)); + + FP4_add(&(w->b),&(w->b),&t1); // z1=z1-z2 + + FP4_add(&z3,&z3,&t1); // z3=z3-z2 + FP4_add(&z2,&z2,&t0); // z2=z2-z0 + + FP4_add(&t0,&(w->a),&(w->c)); + + FP4_mul(&t0,&(y->a),&t0); + FP4_add(&(w->c),&z2,&t0); + + FP4_times_i(&z3); + FP4_add(&(w->a),&z0,&z3); + + FP12_norm(w); +} + +/* Set w=1/x */ +/* SU= 600 */ +void FP12_inv(FP12 *w,FP12 *x) +{ + FP4 f0,f1,f2,f3; + FP12_norm(x); + + FP4_sqr(&f0,&(x->a)); + FP4_mul(&f1,&(x->b),&(x->c)); + FP4_times_i(&f1); + FP4_sub(&f0,&f0,&f1); /* y.a */ + + FP4_sqr(&f1,&(x->c)); + FP4_times_i(&f1); + FP4_mul(&f2,&(x->a),&(x->b)); + FP4_sub(&f1,&f1,&f2); /* y.b */ + + FP4_sqr(&f2,&(x->b)); + FP4_mul(&f3,&(x->a),&(x->c)); + FP4_sub(&f2,&f2,&f3); /* y.c */ + + FP4_mul(&f3,&(x->b),&f2); + FP4_times_i(&f3); + FP4_mul(&(w->a),&f0,&(x->a)); + FP4_add(&f3,&(w->a),&f3); + FP4_mul(&(w->c),&f1,&(x->c)); + FP4_times_i(&(w->c)); + + FP4_add(&f3,&(w->c),&f3); + FP4_inv(&f3,&f3); + + FP4_mul(&(w->a),&f0,&f3); + FP4_mul(&(w->b),&f1,&f3); + FP4_mul(&(w->c),&f2,&f3); + +} + +/* constant time powering by small integer of max length bts */ + +void FP12_pinpow(FP12 *r,int e,int bts) +{ + int i,b; + FP12 R[2]; + + FP12_one(&R[0]); + FP12_copy(&R[1],r); + + for (i=bts-1; i>=0; i--) + { + b=(e>>i)&1; + FP12_mul(&R[1-b],&R[b]); + FP12_usqr(&R[b],&R[b]); + } + FP12_copy(r,&R[0]); +} + +/* SU= 528 */ +/* set r=a^b */ +/* Note this is simple square and multiply, so not side-channel safe */ + +void FP12_pow(FP12 *r,FP12 *a,BIG b) +{ + FP12 w; + BIG z,zilch; + int bt; + BIG_zero(zilch); + BIG_norm(b); + BIG_copy(z,b); + FP12_copy(&w,a); + FP12_one(r); + + while(1) + { + bt=BIG_parity(z); + BIG_shr(z,1); + if (bt) + FP12_mul(r,&w); + if (BIG_comp(z,zilch)==0) break; + FP12_usqr(&w,&w); + } + + FP12_reduce(r); +} + +/* p=q0^u0.q1^u1.q2^u2.q3^u3 */ +/* Timing attack secure, but not cache attack secure */ + +void FP12_pow4(FP12 *p,FP12 *q,BIG u[4]) +{ + int i,j,a[4],nb,m; + FP12 g[8],c,s[2]; + BIG t[4],mt; + sign8 w[NLEN*BASEBITS+1]; + + for (i=0; i<4; i++) + BIG_copy(t[i],u[i]); + + FP12_copy(&g[0],&q[0]); + FP12_conj(&s[0],&q[1]); + FP12_mul(&g[0],&s[0]); /* P/Q */ + FP12_copy(&g[1],&g[0]); + FP12_copy(&g[2],&g[0]); + FP12_copy(&g[3],&g[0]); + FP12_copy(&g[4],&q[0]); + FP12_mul(&g[4],&q[1]); /* P*Q */ + FP12_copy(&g[5],&g[4]); + FP12_copy(&g[6],&g[4]); + FP12_copy(&g[7],&g[4]); + + FP12_copy(&s[1],&q[2]); + FP12_conj(&s[0],&q[3]); + FP12_mul(&s[1],&s[0]); /* R/S */ + FP12_conj(&s[0],&s[1]); + FP12_mul(&g[1],&s[0]); + FP12_mul(&g[2],&s[1]); + FP12_mul(&g[5],&s[0]); + FP12_mul(&g[6],&s[1]); + FP12_copy(&s[1],&q[2]); + FP12_mul(&s[1],&q[3]); /* R*S */ + FP12_conj(&s[0],&s[1]); + FP12_mul(&g[0],&s[0]); + FP12_mul(&g[3],&s[1]); + FP12_mul(&g[4],&s[0]); + FP12_mul(&g[7],&s[1]); + + /* if power is even add 1 to power, and add q to correction */ + FP12_one(&c); + + BIG_zero(mt); + for (i=0; i<4; i++) + { + if (BIG_parity(t[i])==0) + { + BIG_inc(t[i],1); + BIG_norm(t[i]); + FP12_mul(&c,&q[i]); + } + BIG_add(mt,mt,t[i]); + BIG_norm(mt); + } + + FP12_conj(&c,&c); + nb=1+BIG_nbits(mt); + + /* convert exponent to signed 1-bit window */ + for (j=0; j<nb; j++) + { + for (i=0; i<4; i++) + { + a[i]=BIG_lastbits(t[i],2)-2; + BIG_dec(t[i],a[i]); + BIG_norm(t[i]); + BIG_fshr(t[i],1); + } + w[j]=8*a[0]+4*a[1]+2*a[2]+a[3]; + } + w[nb]=8*BIG_lastbits(t[0],2)+4*BIG_lastbits(t[1],2)+2*BIG_lastbits(t[2],2)+BIG_lastbits(t[3],2); + FP12_copy(p,&g[(w[nb]-1)/2]); + + for (i=nb-1; i>=0; i--) + { + m=w[i]>>7; + j=(w[i]^m)-m; /* j=abs(w[i]) */ + j=(j-1)/2; + FP12_copy(&s[0],&g[j]); + FP12_conj(&s[1],&g[j]); + FP12_usqr(p,p); + FP12_mul(p,&s[m&1]); + } + FP12_mul(p,&c); /* apply correction */ + FP12_reduce(p); +} + +/* Set w=w^p using Frobenius */ +/* SU= 160 */ +void FP12_frob(FP12 *w,FP2 *f) +{ + FP2 f2,f3; + FP2_sqr(&f2,f); /* f2=f^2 */ + FP2_mul(&f3,&f2,f); /* f3=f^3 */ + + FP4_frob(&(w->a),&f3); + FP4_frob(&(w->b),&f3); + FP4_frob(&(w->c),&f3); + + FP4_pmul(&(w->b),&(w->b),f); + FP4_pmul(&(w->c),&(w->c),&f2); +} + +/* SU= 8 */ +/* normalise all components of w */ +void FP12_norm(FP12 *w) +{ + FP4_norm(&(w->a)); + FP4_norm(&(w->b)); + FP4_norm(&(w->c)); +} + +/* SU= 8 */ +/* reduce all components of w */ +void FP12_reduce(FP12 *w) +{ + FP4_reduce(&(w->a)); + FP4_reduce(&(w->b)); + FP4_reduce(&(w->c)); +} + +/* trace function w=trace(x) */ +/* SU= 8 */ +void FP12_trace(FP4 *w,FP12 *x) +{ + FP4_imul(w,&(x->a),3); + FP4_reduce(w); +} + +/* SU= 8 */ +/* Output w in hex */ +void FP12_output(FP12 *w) +{ + printf("["); + FP4_output(&(w->a)); + printf(","); + FP4_output(&(w->b)); + printf(","); + FP4_output(&(w->c)); + printf("]"); +} + +/* SU= 64 */ +/* Convert g to octet string w */ +void FP12_toOctet(octet *W,FP12 *g) +{ + BIG a; + W->len=12*MODBYTES; + + BIG_copy(a,(*g).a.a.a); + FP_redc(a); + BIG_toBytes(&(W->val[0]),a); + BIG_copy(a,(*g).a.a.b); + FP_redc(a); + BIG_toBytes(&(W->val[MODBYTES]),a); + BIG_copy(a,(*g).a.b.a); + FP_redc(a); + BIG_toBytes(&(W->val[2*MODBYTES]),a); + BIG_copy(a,(*g).a.b.b); + FP_redc(a); + BIG_toBytes(&(W->val[3*MODBYTES]),a); + BIG_copy(a,(*g).b.a.a); + FP_redc(a); + BIG_toBytes(&(W->val[4*MODBYTES]),a); + BIG_copy(a,(*g).b.a.b); + FP_redc(a); + BIG_toBytes(&(W->val[5*MODBYTES]),a); + BIG_copy(a,(*g).b.b.a); + FP_redc(a); + BIG_toBytes(&(W->val[6*MODBYTES]),a); + BIG_copy(a,(*g).b.b.b); + FP_redc(a); + BIG_toBytes(&(W->val[7*MODBYTES]),a); + BIG_copy(a,(*g).c.a.a); + FP_redc(a); + BIG_toBytes(&(W->val[8*MODBYTES]),a); + BIG_copy(a,(*g).c.a.b); + FP_redc(a); + BIG_toBytes(&(W->val[9*MODBYTES]),a); + BIG_copy(a,(*g).c.b.a); + FP_redc(a); + BIG_toBytes(&(W->val[10*MODBYTES]),a); + BIG_copy(a,(*g).c.b.b); + FP_redc(a); + BIG_toBytes(&(W->val[11*MODBYTES]),a); +} + +/* SU= 24 */ +/* Restore g from octet string w */ +void FP12_fromOctet(FP12 *g,octet *W) +{ + BIG_fromBytes((*g).a.a.a,&W->val[0]); + FP_nres((*g).a.a.a); + BIG_fromBytes((*g).a.a.b,&W->val[MODBYTES]); + FP_nres((*g).a.a.b); + BIG_fromBytes((*g).a.b.a,&W->val[2*MODBYTES]); + FP_nres((*g).a.b.a); + BIG_fromBytes((*g).a.b.b,&W->val[3*MODBYTES]); + FP_nres((*g).a.b.b); + BIG_fromBytes((*g).b.a.a,&W->val[4*MODBYTES]); + FP_nres((*g).b.a.a); + BIG_fromBytes((*g).b.a.b,&W->val[5*MODBYTES]); + FP_nres((*g).b.a.b); + BIG_fromBytes((*g).b.b.a,&W->val[6*MODBYTES]); + FP_nres((*g).b.b.a); + BIG_fromBytes((*g).b.b.b,&W->val[7*MODBYTES]); + FP_nres((*g).b.b.b); + BIG_fromBytes((*g).c.a.a,&W->val[8*MODBYTES]); + FP_nres((*g).c.a.a); + BIG_fromBytes((*g).c.a.b,&W->val[9*MODBYTES]); + FP_nres((*g).c.a.b); + BIG_fromBytes((*g).c.b.a,&W->val[10*MODBYTES]); + FP_nres((*g).c.b.a); + BIG_fromBytes((*g).c.b.b,&W->val[11*MODBYTES]); + FP_nres((*g).c.b.b); +} + +/* +int main(){ + FP2 f,w0,w1; + FP4 t0,t1,t2; + FP12 w,t,lv; + BIG a,b; + BIG p; + + //Test w^(P^4) = w mod p^2 +// BIG_randomnum(a); +// BIG_randomnum(b); +// BIG_mod(a,Modulus); BIG_mod(b,Modulus); + BIG_zero(a); BIG_zero(b); BIG_inc(a,1); BIG_inc(b,2); FP_nres(a); FP_nres(b); + FP2_from_zps(&w0,a,b); + +// BIG_randomnum(a); BIG_randomnum(b); +// BIG_mod(a,Modulus); BIG_mod(b,Modulus); + BIG_zero(a); BIG_zero(b); BIG_inc(a,3); BIG_inc(b,4); FP_nres(a); FP_nres(b); + FP2_from_zps(&w1,a,b); + + FP4_from_FP2s(&t0,&w0,&w1); + FP4_reduce(&t0); + +// BIG_randomnum(a); +// BIG_randomnum(b); +// BIG_mod(a,Modulus); BIG_mod(b,Modulus); + BIG_zero(a); BIG_zero(b); BIG_inc(a,5); BIG_inc(b,6); FP_nres(a); FP_nres(b); + FP2_from_zps(&w0,a,b); + +// BIG_randomnum(a); BIG_randomnum(b); +// BIG_mod(a,Modulus); BIG_mod(b,Modulus); + + BIG_zero(a); BIG_zero(b); BIG_inc(a,7); BIG_inc(b,8); FP_nres(a); FP_nres(b); + FP2_from_zps(&w1,a,b); + + FP4_from_FP2s(&t1,&w0,&w1); + FP4_reduce(&t1); + +// BIG_randomnum(a); +// BIG_randomnum(b); +// BIG_mod(a,Modulus); BIG_mod(b,Modulus); + BIG_zero(a); BIG_zero(b); BIG_inc(a,9); BIG_inc(b,10); FP_nres(a); FP_nres(b); + FP2_from_zps(&w0,a,b); + +// BIG_randomnum(a); BIG_randomnum(b); +// BIG_mod(a,Modulus); BIG_mod(b,Modulus); + BIG_zero(a); BIG_zero(b); BIG_inc(a,11); BIG_inc(b,12); FP_nres(a); FP_nres(b); + FP2_from_zps(&w1,a,b); + + FP4_from_FP2s(&t2,&w0,&w1); + FP4_reduce(&t2); + + FP12_from_FP4s(&w,&t0,&t1,&t2); + + FP12_copy(&t,&w); + + printf("w= "); + FP12_output(&w); + printf("\n"); + + BIG_rcopy(p,Modulus); + //BIG_zero(p); BIG_inc(p,7); + + FP12_pow(&w,&w,p); + + printf("w^p= "); + FP12_output(&w); + printf("\n"); + + FP2_gfc(&f,12); + FP12_frob(&t,&f); + printf("w^p= "); + FP12_output(&t); + printf("\n"); + +//exit(0); + + FP12_pow(&w,&w,p); + //printf("w^p^2= "); + //FP12_output(&w); + //printf("\n"); + FP12_pow(&w,&w,p); + //printf("w^p^3= "); + //FP12_output(&w); + //printf("\n"); + FP12_pow(&w,&w,p); + FP12_pow(&w,&w,p); + FP12_pow(&w,&w,p); + printf("w^p^6= "); + FP12_output(&w); + printf("\n"); + FP12_pow(&w,&w,p); + FP12_pow(&w,&w,p); + printf("w^p^8= "); + FP12_output(&w); + printf("\n"); + FP12_pow(&w,&w,p); + FP12_pow(&w,&w,p); + FP12_pow(&w,&w,p); + printf("w^p^11= "); + FP12_output(&w); + printf("\n"); + + // BIG_zero(p); BIG_inc(p,7); BIG_norm(p); + FP12_pow(&w,&w,p); + + printf("w^p12= "); + FP12_output(&w); + printf("\n"); +//exit(0); + + FP12_inv(&t,&w); + printf("1/w mod p^4 = "); + FP12_output(&t); + printf("\n"); + + FP12_inv(&w,&t); + printf("1/(1/w) mod p^4 = "); + FP12_output(&w); + printf("\n"); + + + + FP12_inv(&lv,&w); +//printf("w= "); FP12_output(&w); printf("\n"); + FP12_conj(&w,&w); +//printf("w= "); FP12_output(&w); printf("\n"); +//exit(0); + FP12_mul(&w,&w,&lv); +//printf("w= "); FP12_output(&w); printf("\n"); + FP12_copy(&lv,&w); + FP12_frob(&w,&f); + FP12_frob(&w,&f); + FP12_mul(&w,&w,&lv); + +//printf("w= "); FP12_output(&w); printf("\n"); +//exit(0); + +w.unitary=0; +FP12_conj(&lv,&w); + printf("rx= "); FP12_output(&lv); printf("\n"); +FP12_inv(&lv,&w); + printf("ry= "); FP12_output(&lv); printf("\n"); + + + return 0; +} + +*/
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/c/fp2.c ---------------------------------------------------------------------- diff --git a/version22/c/fp2.c b/version22/c/fp2.c new file mode 100644 index 0000000..93aa31e --- /dev/null +++ b/version22/c/fp2.c @@ -0,0 +1,435 @@ +/* +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^2 functions */ +/* SU=m, m is Stack Usage (no lazy )*/ + +/* FP2 elements are of the form a+ib, where i is sqrt(-1) */ + +#include "amcl.h" + +/* test x==0 ? */ +/* SU= 8 */ +int FP2_iszilch(FP2 *x) +{ + FP2_reduce(x); + if (BIG_iszilch(x->a) && BIG_iszilch(x->b)) return 1; + return 0; +} + +/* Move b to a if d=1 */ +void FP2_cmove(FP2 *f,FP2 *g,int d) +{ + BIG_cmove(f->a,g->a,d); + BIG_cmove(f->b,g->b,d); +} + +/* test x==1 ? */ +/* SU= 48 */ +int FP2_isunity(FP2 *x) +{ + BIG one; + FP_one(one); + FP2_reduce(x); + if (BIG_comp(x->a,one)==0 && BIG_iszilch(x->b)) return 1; + return 0; +} + +/* SU= 8 */ +/* Fully reduce a and b mod Modulus */ +void FP2_reduce(FP2 *w) +{ + FP_reduce(w->a); + FP_reduce(w->b); +} + +/* return 1 if x==y, else 0 */ +/* SU= 16 */ +int FP2_equals(FP2 *x,FP2 *y) +{ + FP2_reduce(x); + FP2_reduce(y); + if (BIG_comp(x->a,y->a)==0 && BIG_comp(x->b,y->b)==0) + return 1; + return 0; +} + +/* Create FP2 from two FPs */ +/* SU= 16 */ +void FP2_from_FPs(FP2 *w,BIG x,BIG y) +{ + BIG_copy(w->a,x); + BIG_copy(w->b,y); +} + +/* Create FP2 from two BIGS */ +/* SU= 16 */ +void FP2_from_BIGs(FP2 *w,BIG x,BIG y) +{ + BIG_copy(w->a,x); + BIG_copy(w->b,y); + FP_nres(w->a); + FP_nres(w->b); +} + +/* Create FP2 from FP */ +/* SU= 8 */ +void FP2_from_FP(FP2 *w,BIG x) +{ + BIG_copy(w->a,x); + BIG_zero(w->b); +} + +/* Create FP2 from BIG */ +/* SU= 8 */ +void FP2_from_BIG(FP2 *w,BIG x) +{ + BIG_copy(w->a,x); + FP_nres(w->a); + BIG_zero(w->b); +} + +/* FP2 copy w=x */ +/* SU= 16 */ +void FP2_copy(FP2 *w,FP2 *x) +{ + if (w==x) return; + BIG_copy(w->a,x->a); + BIG_copy(w->b,x->b); +} + +/* FP2 set w=0 */ +/* SU= 8 */ +void FP2_zero(FP2 *w) +{ + BIG_zero(w->a); + BIG_zero(w->b); +} + +/* FP2 set w=1 */ +/* SU= 48 */ +void FP2_one(FP2 *w) +{ + BIG one; + FP_one(one); + FP2_from_FP(w,one); +} + +/* Set w=-x */ +/* SU= 88 */ +void FP2_neg(FP2 *w,FP2 *x) +{ + /* Just one neg! */ + BIG m,t; + FP2_norm(x); + FP_add(m,x->a,x->b); + FP_neg(m,m); + BIG_norm(m); + FP_add(t,m,x->b); + FP_add(w->b,m,x->a); + BIG_copy(w->a,t); +} + +/* Set w=conj(x) */ +/* SU= 16 */ +void FP2_conj(FP2 *w,FP2 *x) +{ + BIG_copy(w->a,x->a); + FP_neg(w->b,x->b); +} + +/* Set w=x+y */ +/* SU= 16 */ +void FP2_add(FP2 *w,FP2 *x,FP2 *y) +{ + FP_add(w->a,x->a,y->a); + FP_add(w->b,x->b,y->b); +} + +/* Set w=x-y */ +/* SU= 16 */ +void FP2_sub(FP2 *w,FP2 *x,FP2 *y) +{ + FP2 m; + FP2_neg(&m,y); + FP2_add(w,x,&m); +} + +/* Set w=s*x, where s is FP */ +/* SU= 16 */ +void FP2_pmul(FP2 *w,FP2 *x,BIG s) +{ + FP_mul(w->a,x->a,s); + FP_mul(w->b,x->b,s); +} + +/* SU= 16 */ +/* Set w=s*x, where s is int */ +void FP2_imul(FP2 *w,FP2 *x,int s) +{ + FP_imul(w->a,x->a,s); + FP_imul(w->b,x->b,s); +} + +/* Set w=x^2 */ +/* SU= 128 */ +void FP2_sqr(FP2 *w,FP2 *x) +{ + BIG w1,w3,mb; + + FP_mul(w3,x->a,x->b); /* norms x */ + FP_add(w1,x->a,x->b); /* w1#2 w1=2 */ + FP_neg(mb,x->b); /* mb#2 mb=1 */ + FP_add(w->a,x->a,mb); /* w2#3 w2=3 */ + FP_mul(w->a,w1,w->a); /* w->a#2 w->a=1 w1&w2=6 w1*w2=2 */ + + FP_add(w->b,w3,w3); /* w->b#4 w->b=2 */ + + FP2_norm(w); + +} + + +/* Set w=x*y */ +/* SU= 168 */ +void FP2_mul(FP2 *w,FP2 *x,FP2 *y) +{ + BIG w1,w2,w5,mw; + + FP_mul(w1,x->a,y->a); /* norms x */ + FP_mul(w2,x->b,y->b); /* and y */ + + FP_add(w5,x->a,x->b); + + FP_add(w->b,y->a,y->b); + + FP_mul(w->b,w->b,w5); + FP_add(mw,w1,w2); + FP_neg(mw,mw); + + FP_add(w->b,w->b,mw); + FP_add(mw,w1,mw); + FP_add(w->a,w1,mw); + + FP2_norm(w); + +} + +/* output FP2 in hex format [a,b] */ +/* SU= 16 */ +void FP2_output(FP2 *w) +{ + FP2_reduce(w); + FP_redc(w->a); + FP_redc(w->b); + printf("["); + BIG_output(w->a); + printf(","); + BIG_output(w->b); + printf("]"); + FP_nres(w->a); + FP_nres(w->b); +} + +/* SU= 8 */ +void FP2_rawoutput(FP2 *w) +{ + printf("["); + BIG_rawoutput(w->a); + printf(","); + BIG_rawoutput(w->b); + printf("]"); +} + + +/* Set w=1/x */ +/* SU= 128 */ +void FP2_inv(FP2 *w,FP2 *x) +{ + BIG m,w1,w2; + BIG_rcopy(m,Modulus); + FP2_norm(x); + FP_sqr(w1,x->a); + FP_sqr(w2,x->b); + FP_add(w1,w1,w2); + + FP_redc(w1); + BIG_invmodp(w1,w1,m); + FP_nres(w1); + FP_mul(w->a,x->a,w1); + FP_neg(w1,w1); + FP_mul(w->b,x->b,w1); +// FP2_norm(w); +} + + +/* Set w=x/2 */ +/* SU= 16 */ +void FP2_div2(FP2 *w,FP2 *x) +{ + FP_div2(w->a,x->a); + FP_div2(w->b,x->b); +} + +/* Set w*=(1+sqrt(-1)) */ +/* where X^2-(1+sqrt(-1)) is irreducible for FP4, assumes p=3 mod 8 */ + +/* SU= 128 */ +void FP2_mul_ip(FP2 *w) +{ + FP2 t; + BIG z; + + FP2_norm(w); + FP2_copy(&t,w); + + BIG_copy(z,w->a); + FP_neg(w->a,w->b); + BIG_copy(w->b,z); + + FP2_add(w,&t,w); + FP2_norm(w); +} + +/* Set w/=(1+sqrt(-1)) */ +/* SU= 88 */ +void FP2_div_ip(FP2 *w) +{ + FP2 t; + FP2_norm(w); + FP_add(t.a,w->a,w->b); + FP_sub(t.b,w->b,w->a); + FP2_div2(w,&t); +} + +/* SU= 8 */ +/* normalise a and b components of w */ +void FP2_norm(FP2 *w) +{ + BIG_norm(w->a); + BIG_norm(w->b); +} + +/* Set w=a^b mod m */ +/* SU= 208 */ +void FP2_pow(FP2 *r,FP2* a,BIG b) +{ + FP2 w; + BIG z,one,zilch; + int bt; + + BIG_norm(b); + BIG_copy(z,b); + FP2_copy(&w,a); + FP_one(one); + BIG_zero(zilch); + FP2_from_FP(r,one); + while(1) + { + bt=BIG_parity(z); + BIG_shr(z,1); + if (bt) FP2_mul(r,r,&w); + if (BIG_comp(z,zilch)==0) break; + FP2_sqr(&w,&w); + } + FP2_reduce(r); +} + +/* sqrt(a+ib) = sqrt(a+sqrt(a*a-n*b*b)/2)+ib/(2*sqrt(a+sqrt(a*a-n*b*b)/2)) */ +/* returns true if u is QR */ + +int FP2_sqrt(FP2 *w,FP2 *u) +{ + BIG w1,w2,q; + FP2_copy(w,u); + if (FP2_iszilch(w)) return 1; + + BIG_rcopy(q,Modulus); + FP_sqr(w1,w->b); + FP_sqr(w2,w->a); + FP_add(w1,w1,w2); + if (!FP_qr(w1)) + { + FP2_zero(w); + return 0; + } + FP_sqrt(w1,w1); + FP_add(w2,w->a,w1); + FP_div2(w2,w2); + if (!FP_qr(w2)) + { + FP_sub(w2,w->a,w1); + FP_div2(w2,w2); + if (!FP_qr(w2)) + { + FP2_zero(w); + return 0; + } + } + FP_sqrt(w2,w2); + BIG_copy(w->a,w2); + FP_add(w2,w2,w2); + FP_redc(w2); + BIG_invmodp(w2,w2,q); + FP_nres(w2); + FP_mul(w->b,w->b,w2); + return 1; +} + +/* +int main() +{ + int i; + FP2 w,z; + BIG a,b,e; + BIG pp1,pm1; + BIG_unity(a); BIG_unity(b); + FP2_from_BIGs(&w,a,b); +// for (i=0;i<100;i++) +// { +// BIG_randomnum(a); BIG_randomnum(b); +// BIG_mod(a,Modulus); BIG_mod(b,Modulus); +// FP2_from_FPs(&w,a,b); +// FP2_output(&w); +// FP2_inv(&z,&w); +// FP2_output(&z); +// FP2_inv(&z,&z); +// FP2_output(&z); +// FP2_output(&w); +// if (FP2_comp(&w,&z)!=1) printf("error \n"); +// else printf("OK \n"); +// } +//exit(0); + printf("w= "); FP2_output(&w); printf("\n"); + BIG_zero(e); BIG_inc(e,27); + FP2_pow(&w,&w,e); + FP2_output(&w); +exit(0); + BIG_rcopy(pp1,Modulus); + BIG_rcopy(pm1,Modulus); + BIG_inc(pp1,1); + BIG_dec(pm1,1); + BIG_norm(pp1); + BIG_norm(pm1); + FP2_pow(&w,&w,pp1); + FP2_pow(&w,&w,pm1); + FP2_output(&w); +} + +*/ http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/c/fp4.c ---------------------------------------------------------------------- diff --git a/version22/c/fp4.c b/version22/c/fp4.c new file mode 100644 index 0000000..f61811f --- /dev/null +++ b/version22/c/fp4.c @@ -0,0 +1,651 @@ +/* +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^4 functions */ +/* SU=m, m is Stack Usage (no lazy )*/ + +/* FP4 elements are of the form a+ib, where i is sqrt(-1+sqrt(-1)) */ + +#include "amcl.h" + +/* test x==0 ? */ +/* SU= 8 */ +int FP4_iszilch(FP4 *x) +{ + if (FP2_iszilch(&(x->a)) && FP2_iszilch(&(x->b))) return 1; + return 0; +} + +/* test x==1 ? */ +/* SU= 8 */ +int FP4_isunity(FP4 *x) +{ + if (FP2_isunity(&(x->a)) && FP2_iszilch(&(x->b))) return 1; + return 0; +} + +/* test is w real? That is in a+ib test b is zero */ +int FP4_isreal(FP4 *w) +{ + return FP2_iszilch(&(w->b)); +} + +/* return 1 if x==y, else 0 */ +/* SU= 16 */ +int FP4_equals(FP4 *x,FP4 *y) +{ + if (FP2_equals(&(x->a),&(y->a)) && FP2_equals(&(x->b),&(y->b))) + return 1; + return 0; +} + +/* set FP4 from two FP2s */ +/* SU= 16 */ +void FP4_from_FP2s(FP4 *w,FP2 * x,FP2* y) +{ + FP2_copy(&(w->a), x); + FP2_copy(&(w->b), y); +} + +/* set FP4 from FP2 */ +/* SU= 8 */ +void FP4_from_FP2(FP4 *w,FP2 *x) +{ + FP2_copy(&(w->a), x); + FP2_zero(&(w->b)); +} + +/* FP4 copy w=x */ +/* SU= 16 */ +void FP4_copy(FP4 *w,FP4 *x) +{ + if (w==x) return; + FP2_copy(&(w->a), &(x->a)); + FP2_copy(&(w->b), &(x->b)); +} + +/* FP4 w=0 */ +/* SU= 8 */ +void FP4_zero(FP4 *w) +{ + FP2_zero(&(w->a)); + FP2_zero(&(w->b)); +} + +/* FP4 w=1 */ +/* SU= 8 */ +void FP4_one(FP4 *w) +{ + FP2_one(&(w->a)); + FP2_zero(&(w->b)); +} + +/* Set w=-x */ +/* SU= 160 */ +void FP4_neg(FP4 *w,FP4 *x) +{ + /* Just one field neg */ + FP2 m,t; + FP2_add(&m,&(x->a),&(x->b)); + FP2_neg(&m,&m); + FP2_norm(&m); + FP2_add(&t,&m,&(x->b)); + FP2_add(&(w->b),&m,&(x->a)); + FP2_copy(&(w->a),&t); +} + +/* Set w=conj(x) */ +/* SU= 16 */ +void FP4_conj(FP4 *w,FP4 *x) +{ + FP2_copy(&(w->a), &(x->a)); + FP2_neg(&(w->b), &(x->b)); + FP2_norm(&(w->b)); +} + +/* Set w=-conj(x) */ +/* SU= 16 */ +void FP4_nconj(FP4 *w,FP4 *x) +{ + FP2_copy(&(w->b),&(x->b)); + FP2_neg(&(w->a), &(x->a)); + FP2_norm(&(w->a)); +} + +/* Set w=x+y */ +/* SU= 16 */ +void FP4_add(FP4 *w,FP4 *x,FP4 *y) +{ + FP2_add(&(w->a), &(x->a), &(y->a)); + FP2_add(&(w->b), &(x->b), &(y->b)); +} + +/* Set w=x-y */ +/* SU= 160 */ +void FP4_sub(FP4 *w,FP4 *x,FP4 *y) +{ + FP4 my; + FP4_neg(&my, y); + FP4_add(w, x, &my); + +} +/* SU= 8 */ +/* reduce all components of w mod Modulus */ +void FP4_reduce(FP4 *w) +{ + FP2_reduce(&(w->a)); + FP2_reduce(&(w->b)); +} + +/* SU= 8 */ +/* normalise all elements of w */ +void FP4_norm(FP4 *w) +{ + FP2_norm(&(w->a)); + FP2_norm(&(w->b)); +} + +/* Set w=s*x, where s is FP2 */ +/* SU= 16 */ +void FP4_pmul(FP4 *w,FP4 *x,FP2 *s) +{ + FP2_mul(&(w->a),&(x->a),s); + FP2_mul(&(w->b),&(x->b),s); +} + +/* SU= 16 */ +/* Set w=s*x, where s is int */ +void FP4_imul(FP4 *w,FP4 *x,int s) +{ + FP2_imul(&(w->a),&(x->a),s); + FP2_imul(&(w->b),&(x->b),s); +} + +/* Set w=x^2 */ +/* SU= 232 */ +void FP4_sqr(FP4 *w,FP4 *x) +{ + FP2 t1,t2,t3; + + FP2_mul(&t3,&(x->a),&(x->b)); /* norms x */ + FP2_copy(&t2,&(x->b)); + FP2_add(&t1,&(x->a),&(x->b)); + FP2_mul_ip(&t2); + + FP2_add(&t2,&(x->a),&t2); + + FP2_mul(&(w->a),&t1,&t2); + + FP2_copy(&t2,&t3); + FP2_mul_ip(&t2); + + FP2_add(&t2,&t2,&t3); + + FP2_neg(&t2,&t2); + FP2_add(&(w->a),&(w->a),&t2); /* a=(a+b)(a+i^2.b)-i^2.ab-ab = a*a+ib*ib */ + FP2_add(&(w->b),&t3,&t3); /* b=2ab */ + + FP4_norm(w); +} + +/* Set w=x*y */ +/* SU= 312 */ +void FP4_mul(FP4 *w,FP4 *x,FP4 *y) +{ + + FP2 t1,t2,t3,t4; + FP2_mul(&t1,&(x->a),&(y->a)); /* norms x */ + FP2_mul(&t2,&(x->b),&(y->b)); /* and y */ + FP2_add(&t3,&(y->b),&(y->a)); + FP2_add(&t4,&(x->b),&(x->a)); + + + FP2_mul(&t4,&t4,&t3); /* (xa+xb)(ya+yb) */ + FP2_sub(&t4,&t4,&t1); + FP2_norm(&t4); + + FP2_sub(&(w->b),&t4,&t2); + FP2_mul_ip(&t2); + FP2_add(&(w->a),&t2,&t1); + + FP4_norm(w); +} + +/* output FP4 in format [a,b] */ +/* SU= 8 */ +void FP4_output(FP4 *w) +{ + printf("["); + FP2_output(&(w->a)); + printf(","); + FP2_output(&(w->b)); + printf("]"); +} + +/* SU= 8 */ +void FP4_rawoutput(FP4 *w) +{ + printf("["); + FP2_rawoutput(&(w->a)); + printf(","); + FP2_rawoutput(&(w->b)); + printf("]"); +} + +/* Set w=1/x */ +/* SU= 160 */ +void FP4_inv(FP4 *w,FP4 *x) +{ + FP2 t1,t2; + FP2_sqr(&t1,&(x->a)); + FP2_sqr(&t2,&(x->b)); + FP2_mul_ip(&t2); + FP2_sub(&t1,&t1,&t2); + FP2_inv(&t1,&t1); + FP2_mul(&(w->a),&t1,&(x->a)); + FP2_neg(&t1,&t1); + FP2_mul(&(w->b),&t1,&(x->b)); +} + +/* w*=i where i = sqrt(-1+sqrt(-1)) */ +/* SU= 200 */ +void FP4_times_i(FP4 *w) +{ + BIG z; + FP2 s,t; + + FP4_norm(w); + FP2_copy(&t,&(w->b)); + + FP2_copy(&s,&t); + + BIG_copy(z,s.a); + FP_neg(s.a,s.b); + BIG_copy(s.b,z); + + FP2_add(&t,&t,&s); + FP2_norm(&t); + + FP2_copy(&(w->b),&(w->a)); + FP2_copy(&(w->a),&t); +} + +/* Set w=w^p using Frobenius */ +/* SU= 16 */ +void FP4_frob(FP4 *w,FP2 *f) +{ + FP2_conj(&(w->a),&(w->a)); + FP2_conj(&(w->b),&(w->b)); + FP2_mul( &(w->b),f,&(w->b)); +} + +/* Set r=a^b mod m */ +/* SU= 240 */ +void FP4_pow(FP4 *r,FP4* a,BIG b) +{ + FP4 w; + BIG z,zilch; + int bt; + + BIG_zero(zilch); + BIG_norm(b); + BIG_copy(z,b); + FP4_copy(&w,a); + FP4_one(r); + + while(1) + { + bt=BIG_parity(z); + BIG_shr(z,1); + if (bt) FP4_mul(r,r,&w); + if (BIG_comp(z,zilch)==0) break; + FP4_sqr(&w,&w); + } + FP4_reduce(r); +} + +/* SU= 304 */ +/* XTR xtr_a function */ +void FP4_xtr_A(FP4 *r,FP4 *w,FP4 *x,FP4 *y,FP4 *z) +{ + FP4 t1,t2; + + FP4_copy(r,x); + + FP4_sub(&t1,w,y); + + FP4_pmul(&t1,&t1,&(r->a)); + FP4_add(&t2,w,y); + FP4_pmul(&t2,&t2,&(r->b)); + FP4_times_i(&t2); + + FP4_add(r,&t1,&t2); + FP4_add(r,r,z); + + FP4_norm(r); +} + +/* SU= 152 */ +/* XTR xtr_d function */ +void FP4_xtr_D(FP4 *r,FP4 *x) +{ + FP4 w; + FP4_copy(r,x); + FP4_conj(&w,r); + FP4_add(&w,&w,&w); + FP4_sqr(r,r); + FP4_sub(r,r,&w); + FP4_reduce(r); /* reduce here as multiple calls trigger automatic reductions */ +} + +/* SU= 728 */ +/* r=x^n using XTR method on traces of FP12s */ +void FP4_xtr_pow(FP4 *r,FP4 *x,BIG n) +{ + int i,par,nb; + BIG v; + FP2 w; + FP4 t,a,b,c; + + BIG_zero(v); + BIG_inc(v,3); + FP2_from_BIG(&w,v); + FP4_from_FP2(&a,&w); + FP4_copy(&b,x); + FP4_xtr_D(&c,x); + + BIG_norm(n); + par=BIG_parity(n); + BIG_copy(v,n); + BIG_shr(v,1); + if (par==0) + { + BIG_dec(v,1); + BIG_norm(v); + } + + nb=BIG_nbits(v); + + for (i=nb-1; i>=0; i--) + { + if (!BIG_bit(v,i)) + { + FP4_copy(&t,&b); + FP4_conj(x,x); + FP4_conj(&c,&c); + FP4_xtr_A(&b,&a,&b,x,&c); + FP4_conj(x,x); + FP4_xtr_D(&c,&t); + FP4_xtr_D(&a,&a); + } + else + { + FP4_conj(&t,&a); + FP4_xtr_D(&a,&b); + FP4_xtr_A(&b,&c,&b,x,&t); + FP4_xtr_D(&c,&c); + } + } + if (par==0) FP4_copy(r,&c); + else FP4_copy(r,&b); + FP4_reduce(r); +} + +/* SU= 872 */ +/* r=ck^a.cl^n using XTR double exponentiation method on traces of FP12s. See Stam thesis. */ +void FP4_xtr_pow2(FP4 *r,FP4 *ck,FP4 *cl,FP4 *ckml,FP4 *ckm2l,BIG a,BIG b) +{ + int i,f2; + BIG d,e,w; + FP4 t,cu,cv,cumv,cum2v; + + BIG_norm(a); + BIG_norm(b); + BIG_copy(e,a); + BIG_copy(d,b); + FP4_copy(&cu,ck); + FP4_copy(&cv,cl); + FP4_copy(&cumv,ckml); + FP4_copy(&cum2v,ckm2l); + + f2=0; + while (BIG_parity(d)==0 && BIG_parity(e)==0) + { + BIG_shr(d,1); + BIG_shr(e,1); + f2++; + } + while (BIG_comp(d,e)!=0) + { + if (BIG_comp(d,e)>0) + { + BIG_imul(w,e,4); + BIG_norm(w); + if (BIG_comp(d,w)<=0) + { + BIG_copy(w,d); + BIG_copy(d,e); + BIG_sub(e,w,e); + BIG_norm(e); + FP4_xtr_A(&t,&cu,&cv,&cumv,&cum2v); + FP4_conj(&cum2v,&cumv); + FP4_copy(&cumv,&cv); + FP4_copy(&cv,&cu); + FP4_copy(&cu,&t); + } + else if (BIG_parity(d)==0) + { + BIG_shr(d,1); + FP4_conj(r,&cum2v); + FP4_xtr_A(&t,&cu,&cumv,&cv,r); + FP4_xtr_D(&cum2v,&cumv); + FP4_copy(&cumv,&t); + FP4_xtr_D(&cu,&cu); + } + else if (BIG_parity(e)==1) + { + BIG_sub(d,d,e); + BIG_norm(d); + BIG_shr(d,1); + FP4_xtr_A(&t,&cu,&cv,&cumv,&cum2v); + FP4_xtr_D(&cu,&cu); + FP4_xtr_D(&cum2v,&cv); + FP4_conj(&cum2v,&cum2v); + FP4_copy(&cv,&t); + } + else + { + BIG_copy(w,d); + BIG_copy(d,e); + BIG_shr(d,1); + BIG_copy(e,w); + FP4_xtr_D(&t,&cumv); + FP4_conj(&cumv,&cum2v); + FP4_conj(&cum2v,&t); + FP4_xtr_D(&t,&cv); + FP4_copy(&cv,&cu); + FP4_copy(&cu,&t); + } + } + if (BIG_comp(d,e)<0) + { + BIG_imul(w,d,4); + BIG_norm(w); + if (BIG_comp(e,w)<=0) + { + BIG_sub(e,e,d); + BIG_norm(e); + FP4_xtr_A(&t,&cu,&cv,&cumv,&cum2v); + FP4_copy(&cum2v,&cumv); + FP4_copy(&cumv,&cu); + FP4_copy(&cu,&t); + } + else if (BIG_parity(e)==0) + { + BIG_copy(w,d); + BIG_copy(d,e); + BIG_shr(d,1); + BIG_copy(e,w); + FP4_xtr_D(&t,&cumv); + FP4_conj(&cumv,&cum2v); + FP4_conj(&cum2v,&t); + FP4_xtr_D(&t,&cv); + FP4_copy(&cv,&cu); + FP4_copy(&cu,&t); + } + else if (BIG_parity(d)==1) + { + BIG_copy(w,e); + BIG_copy(e,d); + BIG_sub(w,w,d); + BIG_norm(w); + BIG_copy(d,w); + BIG_shr(d,1); + FP4_xtr_A(&t,&cu,&cv,&cumv,&cum2v); + FP4_conj(&cumv,&cumv); + FP4_xtr_D(&cum2v,&cu); + FP4_conj(&cum2v,&cum2v); + FP4_xtr_D(&cu,&cv); + FP4_copy(&cv,&t); + } + else + { + BIG_shr(d,1); + FP4_conj(r,&cum2v); + FP4_xtr_A(&t,&cu,&cumv,&cv,r); + FP4_xtr_D(&cum2v,&cumv); + FP4_copy(&cumv,&t); + FP4_xtr_D(&cu,&cu); + } + } + } + FP4_xtr_A(r,&cu,&cv,&cumv,&cum2v); + for (i=0; i<f2; i++) FP4_xtr_D(r,r); + FP4_xtr_pow(r,r,d); +} +/* +int main(){ + FP2 w0,w1,f; + FP4 w,t; + FP4 c1,c2,c3,c4,cr; + BIG a,b; + BIG e,e1,e2; + BIG p,md; + + + BIG_rcopy(md,Modulus); + //Test w^(P^4) = w mod p^2 + BIG_zero(a); BIG_inc(a,27); + BIG_zero(b); BIG_inc(b,45); + FP2_from_BIGs(&w0,a,b); + + BIG_zero(a); BIG_inc(a,33); + BIG_zero(b); BIG_inc(b,54); + FP2_from_BIGs(&w1,a,b); + + FP4_from_FP2s(&w,&w0,&w1); + FP4_reduce(&w); + + printf("w= "); + FP4_output(&w); + printf("\n"); + + + FP4_copy(&t,&w); + + + BIG_copy(p,md); + FP4_pow(&w,&w,p); + + printf("w^p= "); + FP4_output(&w); + printf("\n"); +//exit(0); + + BIG_rcopy(a,CURVE_Fra); + BIG_rcopy(b,CURVE_Frb); + FP2_from_BIGs(&f,a,b); + + FP4_frob(&t,&f); + printf("w^p= "); + FP4_output(&t); + printf("\n"); + + FP4_pow(&w,&w,p); + FP4_pow(&w,&w,p); + FP4_pow(&w,&w,p); + printf("w^p4= "); + FP4_output(&w); + printf("\n"); + +// Test 1/(1/x) = x mod p^4 + FP4_from_FP2s(&w,&w0,&w1); + printf("Test Inversion \nw= "); + FP4_output(&w); + printf("\n"); + + FP4_inv(&w,&w); + printf("1/w mod p^4 = "); + FP4_output(&w); + printf("\n"); + + FP4_inv(&w,&w); + printf("1/(1/w) mod p^4 = "); + FP4_output(&w); + printf("\n"); + + BIG_zero(e); BIG_inc(e,12); + + + + // FP4_xtr_A(&w,&t,&w,&t,&t); + FP4_xtr_pow(&w,&w,e); + + printf("w^e= "); + FP4_output(&w); + printf("\n"); + + + BIG_zero(a); BIG_inc(a,37); + BIG_zero(b); BIG_inc(b,17); + FP2_from_BIGs(&w0,a,b); + + BIG_zero(a); BIG_inc(a,49); + BIG_zero(b); BIG_inc(b,31); + FP2_from_BIGs(&w1,a,b); + + FP4_from_FP2s(&c1,&w0,&w1); + FP4_from_FP2s(&c2,&w0,&w1); + FP4_from_FP2s(&c3,&w0,&w1); + FP4_from_FP2s(&c4,&w0,&w1); + + BIG_zero(e1); BIG_inc(e1,3331); + BIG_zero(e2); BIG_inc(e2,3372); + + FP4_xtr_pow2(&w,&c1,&w,&c2,&c3,e1,e2); + + printf("c^e= "); + FP4_output(&w); + printf("\n"); + + + return 0; +} +*/ + http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/c/gcm.c ---------------------------------------------------------------------- diff --git a/version22/c/gcm.c b/version22/c/gcm.c new file mode 100644 index 0000000..3bd9b8d --- /dev/null +++ b/version22/c/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 - Initialisation 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/blob/c25f9e5c/version22/c/hash.c ---------------------------------------------------------------------- diff --git a/version22/c/hash.c b/version22/c/hash.c new file mode 100644 index 0000000..6e6192d --- /dev/null +++ b/version22/c/hash.c @@ -0,0 +1,422 @@ +/* +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) + * + * Generates a 256/384/512 bit 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 byte) +{ + /* process the next message byte */ + int cnt; +//printf("byt= %x\n",byte); + cnt=(int)((sh->length[0]/32)%16); + + sh->w[cnt]<<=8; + sh->w[cnt]|=(unsign32)(byte&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 byte) +{ + /* process the next message byte */ + HASH512_process(sh,byte); +} + +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 byte) +{ + /* process the next message byte */ + int cnt; + + cnt=(int)((sh->length[0]/64)%16); + + sh->w[cnt]<<=8; + sh->w[cnt]|=(unsign64)(byte&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); +} + + +/* 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> +#include "aracrypt.h" + +char test160[]="abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"; +char test256[]="abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"; +char test512[]="abcdefghbcdefghicdefghijdefghijkefghijklfghijklmghijklmnhijklmnoijklmnopjklmnopqklmnopqrlmnopqrsmnopqrstnopqrstu"; + +int main() +{ + char digest[64]; + int i; + hash160 sh160; + hash256 sh256; + hash384 sh384; + hash512 sh512; + + HASH160_init(&sh160); + for (i=0;test256[i]!=0;i++) HASH160_process(&sh160,test160[i]); + HASH160_hash(&sh160,digest); + for (i=0;i<20;i++) printf("%02x",(unsigned char)digest[i]); + printf("\n"); + + 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"); + + + return 0; +} + +*/ http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/c/maxstack.c ---------------------------------------------------------------------- diff --git a/version22/c/maxstack.c b/version22/c/maxstack.c new file mode 100644 index 0000000..77b2062 --- /dev/null +++ b/version22/c/maxstack.c @@ -0,0 +1,62 @@ +/* +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. +*/ + +/* + How to determine maximum stack usage + 1. Compile this file *with no optimization*, for example gcc -c maxstack.c + 2. Rename your main() function to mymain() + 3. Compile with normal level of optimization, linking to maxstack.o for example gcc maxstack.o -O3 myprogram.c -o myprogam + 4. Execute myprogram + 5. Program runs, at end prints out maximum stack usage + + Caveat Code! + Mike Scott October 2014 +*/ + +#include <stdio.h> + +#define MAXSTACK 65536 /* greater than likely stack requirement */ + +extern void mymain(); + +void start() +{ + char stack[MAXSTACK]; + int i; + for (i=0; i<MAXSTACK; i++) stack[i]=0x55; +} + +void finish() +{ + char stack[MAXSTACK]; + int i; + for (i=0; i<MAXSTACK; i++) + if (stack[i]!=0x55) break; + printf("Max Stack usage = %d\n",MAXSTACK-i); +} + +int main() +{ + start(); + + mymain(); + + finish(); + return 0; +}
