/* ------------------------------------------------ generates key pair of balanced OV(o,v) over GF(q) public key is stored in public_key.txt private key is stored in private_key.txt at the moment this program and the forgery is for a homogeneous case and cT is set to zero instead a random vector ------------------------------------------------*/ clear ; q:=2^4; // field size use either 2^n (even characteristic) or a prime number (odd characteristic) v:=5; // number of Vinegar variables o:=v; // number of oil variables n:=o+v; //SetSeed(534392861, 34453) ; // used for book edition 1 printf "*********************************************** \n"; printf "*** Balanced OV Signature Scheme - Key Generation *** \n"; printf "*********************************************** \n \n"; timet := Cputime() ; GF:=GaloisField(q); P<[x]>:=PolynomialRing(GF,n); Pol<[y]>:=PolynomialRing(P,n); Vn:=VectorSpace(GF,n); // affine map T ----------------------------------------------------------------------------- repeat MT:=RandomMatrix(GF,n,n); until IsInvertible(MT) ; cT:=Random(Vn); cT:=[GF!0:i in [1..n]]; T:=[]; for loop:=1 to n do T[loop]:=P!0; for i:=1 to n do T[loop]:=T[loop]+MT[loop][i]*x[i]; end for; T[loop]:=T[loop]+cT[loop]; end for; // central map Q --------------------------------------------------------------------------- Q:=[]; for loop:=1 to o do Q[loop]:=Pol!0; //quadratic terms for i:=1 to v do for j:=i to n do Q[loop]:=Q[loop]+Random(GF)*y[i]*y[j]; end for; end for; //no linear terms // for i:=1 to n do // Q[loop]:=Q[loop]+Random(GF)*y[i]; //end for; //no constant terms //Q[loop]:=Q[loop]+Random(GF); end for; // public key Pk ---------------------------------------------------------------------------- Pk:=Q; D:=[]; for loop:=1 to o do for j:=1 to n do Pk[loop]:=Evaluate(Pk[loop],y[j],T[j]); end for; end for; for loop:=1 to o do D[loop]:=MonomialCoefficient(Pk[loop],1); end for; // Output ---------------------------------------------------------------------------- printf "q:= %o ; \n \n", q; printf "o:= v:= %o ; \n \n",o ; printf "n:= o + v := %o; \n \n",n; printf "Balanced OV key generation time: %o\n",Cputime(timet); printf "Write public_key.txt \n \n"; SetOutputFile("public_key.txt":Overwrite:=true); printf "q:= %o ; \n \n", q; printf "o:= %o ; \n \n", o; printf "v:= %o ; \n \n", v; printf "n:= o + v; \n \n"; printf "GF:=GaloisField(q); \n \n"; printf "P<[x]>:=PolynomialRing(GF,n); \n \n"; printf "Pk:= %o ; \n \n", Pk; UnsetOutputFile(); printf "Write private_key.txt \n \n"; SetOutputFile("private_key.txt":Overwrite:=true); printf "q:= %o ; \n \n", q; printf "o:= %o ; \n \n", o; printf "v:= %o ; \n \n", v; printf "n:=o+v; \n \n"; printf "GF:=GaloisField(q); \n \n"; printf "P<[x]>:=PolynomialRing(GF,n); \n \n"; printf "Pol<[y]>:=PolynomialRing(P,n); \n \n"; printf "MT:= %o ; \n \n", Eltseq(MT); printf "cT:= %o ; \n \n", Eltseq(cT); printf "Q:= %o ; \n \n", Q; UnsetOutputFile();