/* ------------------------------------------------
generates key pair of UOV(o,v) over GF(q)
public key is stored in UOV/public_key.txt
private key is stored in UOV/private_key.txt
------------------------------------------------*/
clear;

q:=4; // field size
v:=3; // number of Vinegar variables
o:=2; // number of oil variables
n:=o+v;

printf "*********************************************** \n";
printf "*** (U)OV Signature Scheme - Key Generation *** \n";
printf "*********************************************** \n \n";


GF<w>:=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) eq true;
cT:=Random(Vn);

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;
	//linear terms
	for i:=1 to n do
		Q[loop]:=Q[loop]+Random(GF)*y[i];
	end for;
	//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 ; o:= %o; v:= %o; n:= %o; \n \n", q,o,v,n;

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<w>:=GaloisField(q); \n \n";
printf "P<[x]>:=PolynomialRing(GF,n); \n \n";
printf "Pk:= %o ; \n \n",D ;
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<w>:=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();