/* -------------------------------------------------------------
Key Generation Process of HFE Encryption Scheme
program generates random key pair
public key is stored in public_key.txt, private key is stored in private_key.txt
---------------------------------------------------------------*/
clear;

SetSeed(0,0);

printf "********************************************** \n";
printf "*** HFE Encryption Scheme - Key Generation *** \n";
printf "********************************************** \n \n";

timet:=Cputime();

q:=4;
n:=3; // size of extension field
D:=17 ;

r1 := Floor(Log(D)/Log(q));

GF<w>:=GaloisField(q);
messagespace:=VectorSpace(GF,n);
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,n));
Poly<X>:=quo<P1|irrpol>;
Poli<Z>:=PolynomialRing(Poly);

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

randnum:=1;

function randomelement() // generates a random element of the extension field
  Arand:=[];														
  pol:=Poly!0;
  for i:=0 to n-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(messagespace);

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,n,n);
until IsInvertible(MS) ;
cS:=Random(messagespace);

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


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

  
// linear terms 

Apow := A;
alpha := randomelement() ;
Alpha := [alpha];  // list for the coefficients alpha of HFE polynomial
B := (alpha)  ;  // constant term
B0 := alpha ;

	

for i:=0 to r1 do 
    qi := q^i ;         // linear terms
    alpha := randomelement() ;
    Alpha := Append(Alpha,alpha);
    Apow := Apow^q ;
    print "qi=",qi;
    B +:= alpha*A^qi ;

    B0 +:= alpha*Z^qi;
    for j:=0 to i do   //quadratic terms
	qij := qi+q^j;
	if qij le D then
           alpha := randomelement() ; 		
		Alpha:=Append(Alpha,alpha);
		B +:= alpha*A^qij ;
           B0 +:= alpha*Z^qij;
           printf "qij=%o\n",qij;
	end if;
    end for;
end for;


//B:=B mod irrpol;  no longer needed in quotient field

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

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

printf "HFE keygen time: %o\n\n",Cputime(timet) ;


//Output ---------------------------
printf "n:= %o ;    q:= %o ;   D:= %o ;\n \n", n,q,D;
printf "irrpol:= %o \n \n", irrpol;
printf "HFE polynomial: %o \n",B0;



SetOutputFile("public_key.txt":Overwrite:=true);
printf "GF<w>:=GaloisField(%o); \n",q;
printf "n:= %o ; \n", n;
printf "messagespace:=VectorSpace(GF,n); \n \n";
printf "Pol<[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 "D:= %o ; \n \n", D;
printf "n:= %o ; \n \n", n;
printf "GF<w>:=GaloisField(q); \n \n";
printf "Pol<X>:=PolynomialRing(GF); \n \n";
printf "irrpol:= %o; \n \n", irrpol;
printf "messagespace:=VectorSpace(GF,n); \n \n";
printf "MS:= Matrix(GF,n,n, %o); \n \n", Eltseq(MS);
printf "cS:= messagespace!(%o); \n \n", Eltseq(cS);
printf "MT:= Matrix(GF,n,n, %o); \n \n", Eltseq(MT);
printf "cT:= messagespace!(%o); \n \n", Eltseq(cT);
printf "Alpha:= %o; \n", Alpha; 

UnsetOutputFile();