/* HFEv-alt ---------------------------------------------------
Key Generation Process of HFEv- Signature Scheme
program generates random key pair
public key is stored in public_key.txt, private key is stored in private_key.txt
---------------------------------------------------------------*/

clear ;


printf "*********************************************** \n";
printf "*** HFEv- Signature Scheme - Key Generation *** \n";
printf "*********************************************** \n \n";


timet := Cputime() ;


q:=4;
m:=5; // size of extension field
D:=9;
r1 := Floor(Log(D)/Log(q)) ;
a:=2; // Minus-Variation
v:=2; // Vinegar
n:=m+v; // # variables


GF<w>:=GaloisField(q);

signspace:=VectorSpace(GF,n);
hashspace:=VectorSpace(GF,m-a);


P0<[x]>:=PolynomialRing(GF,n);

fieldeq:=[];  // field equations over ground field
for i:=1 to n do
	fieldeq:=fieldeq cat [x[i]^q-x[i]];
end for;


Pol<[x]> := quo<P0|fieldeq>;

P1<X>:=PolynomialRing(Pol);
irrpol:=P1!(IrreduciblePolynomial(GF,m));

Poly<X> := quo<P1|irrpol>;

Poll<[y]>:=PolynomialRing(Pol,n);

function randomelement() // generates a random element of the extension field
	pol:=Poly!0;
	for i:=0 to m-1 do
		pol:=pol+Random(GF)*X^i;
	end for;
	return pol;
end function;

// affine map T ----------------------------------------------------------------

repeat
	MT:=RandomMatrix(GF,n,n);
until IsInvertible(MT) ;

cT := Random(signspace);
T:=[];
for i:=1 to n do
	T[i]:=cT[i]+MT[i][1]*x[1];
	for j:= 2 to n do
		T[i]:=T[i]+MT[i][j]*x[j];
	end for;
end for;
// ----------------------------------------------------------------------------


//----------------affine map S ----------------------------------------------
repeat
	MS:=RandomMatrix(GF,m-a,m);
until Rank(MS) eq m-a;
cS:=Random(hashspace);

S:=[];
for i:=1 to m-a do
	S[i]:=cS[i]+MS[i][1]*y[1];
	for j:= 2 to m do
		S[i]:=S[i]+MS[i][j]*y[j];
	end for;
end for;
// -----------------------------------------------------------------------

//------------Vinegar maps------------------------------------------------

beta := [];
Beta1:= [] ;
Beta2:= [] ;

ij := 1;
for i:=0 to r1 do
     i1 := i+1;
     beta[ij] := randomelement() ;
     Beta1[i1]:=Poly!beta[ij] ;
     Beta2[i1]:=Poly!beta[ij] ;
     ij +:= 1 ;

	for j:=1 to v do
		beta[ij]:=randomelement();
		Beta1[i1] +:= beta[ij]*T[m+j];
		Beta2[i1] +:= beta[ij]*x[m+j];
           ij +:= 1 ;
	end for;
end for;

// start with constant term for equations of vinegar variables
gamma := [randomelement()];
Gamma1:=Poly!gamma[1];
Gamma2:=Poly!gamma[1];
// next linear terms for vinegar variables

ij := 1 ;
for i:=1 to v do
     ij +:= 1;
     gamma[ij] := randomelement() ; 
	Gamma1:=Gamma1 + gamma[ij] * T[m+i];
	Gamma2:=Gamma2 + gamma[ij] * x[m+i];
end for;


//quadratic terms 
for i:=1 to v do
	for j:=i to v do
           ij +:= 1 ;
           gamma[ij] := randomelement() ;
		Gamma1:=Gamma1 + gamma[ij] * T[m+i]*T[m+j];
		Gamma2:=Gamma2 + gamma[ij] * x[m+i]*x[m+j];
	end for;
end for;

//----------------------------------------------------------------------------------------

A:=Poly!0;

for i:=1 to m do
	A:=A+T[i]*X^(i-1);
end for;


Alpha :=[**];   // empty list for the coefficients alpha of HFE polynomial


//  quadratic terms only

B:=Poly!0;
for i:=1 to r1 do //quadratic terms
	for j:=0 to i-1 do
	     qij := q^i+q^j;
		if qij le D then
		   alpha := randomelement() ; 		
		   Alpha:=Append(Alpha,alpha);
		   B +:= alpha*A^qij ;
		end if;
	end for;
end for;

for i:= 0 to r1 do 
   B +:= Beta1[i+1]*A^(q^i);
end for ;

B +:= Gamma1 ;

p:=[];
for i:=1 to m do
	p[i]:=MonomialCoefficient(B,X^(i-1));
end for;



Be:=Poly!0;
for i:=1 to m do
	Be:= Be+ p[i] * X^(i-1);
end for;


Pk:=S; //public  key -------------------------------
for i:=1 to m-a do
	for j:=1 to m do
           Pk[i]:=Evaluate(Pk[i],y[j],p[j]);
	end for;
end for;

//Output ---------------------------

print "Time for key generation: ",Cputime(timet);

printf "n:= %o; q:= %o;  D:= %o \n \n", n,q,D;
printf "a:= %o  v:=%o \n \n", a,v;
printf "m := n + v; \n";

printf "irrpol:= %o \n \n", irrpol;
printf "coefficients of quadratic terms \n";
printf "Alpha:= %o; \n ", Alpha;
 printf "\n";
 
printf "coefficients of linear terms (vinegar maps): \n";
for i:=0 to r1 do
		printf "Beta2[%o]: %o \n", i+1, Beta2[i+1];
	end for;
printf "\n";

printf "constant term (vinegar map):= \n%o; \n \n", Gamma2;
 printf " ----------------------- \n \n";


printf"Write public_key.txt \n";
SetOutputFile("public_key.txt":Overwrite:=true);
printf "// alt alt alt \n";
printf "q:= %o ; \n \n", q;
printf "n:= %o ; \n \n", n;
printf "m:= %o ; \n \n", m;
printf "a:= %o ; \n \n", a;
printf "GF<w>:=GaloisField(q); \n \n";
printf "Pol<[x]>:=PolynomialRing(GF,n); \n \n";
printf "Pk:= %o ; \n ", Pk ;
UnsetOutputFile();
 
printf"Write private_key.txt \n \n";
SetOutputFile("private_key.txt":Overwrite:=true);
printf "// alt - alt - alt \n";
printf "q:= %o ; \n \n", q;
printf "D:= %o ; \n \n", D;
printf "n:= %o ; \n \n", n;
printf "a:= %o ; \n \n", a;
printf "v:= %o ; \n \n", v;
printf "m:= %o ; \n \n", m;
printf "GF<w>:=GaloisField(q); \n \n";
printf "Pol<X>:=PolynomialRing(GF); \n \n";
printf "irrpol:= %o; \n \n", irrpol;
printf "signspace:=VectorSpace(GF,n); \n \n";
printf "hashspace:=VectorSpace(GF,m-a); \n \n";
printf "MS:= Matrix(GF,m-a,m, %o); \n \n", Eltseq(MS);
printf "cS:= hashspace!(%o); \n \n", Eltseq(cS);
printf "MT:= Matrix(GF,n,n, %o); \n \n", Eltseq(MT);
printf "cT:= signspace!(%o); \n \n", Eltseq(cT);
printf "Alpha:= %o; \n", Alpha; 
printf "beta:= %o; \n", beta;
printf "gamma:= %o; \n", gamma;

UnsetOutputFile();