/* ---------------------------------------------------------
reads in private from private_key.txt
generates Rainbow signature for a random hash value
hash value and signature are stored in signature.txt 
------------------------------------------------------------*/

printf "******************************************************* \n";
printf "*** Rainbow Signature Scheme - Signature Generation *** \n";
printf "******************************************************* \n \n";

load "private_key.txt";

Hashspace:=VectorSpace(F,m);
Signspace:=VectorSpace(F,n);

u:=#v-1;
hashvalue:=Random(Hashspace);
printf "hashvalue= %o \n \n", Eltseq(hashvalue);


MT:=Matrix(F,n,n,MT);//read in private key
MS:=Matrix(F,m,m,MS);
cT:=Signspace!(cT);
cS:=Hashspace!(cS);

_,x,_:=IsConsistent(Transpose(MS), hashvalue- cS); // invert affine map S 
printf "S^-1(message)= %o \n \n", x;

sequ:=[];

//invert central map Q ----------------------------------------------------------------------------
repeat
	Q1:=Q;
	sequ:=[];
// guessing Vinegar variables and simplification of the system
	for i:= 1 to v[1] do
		sequ[i]:=Random(F);
		for loop:=1 to m do
			Q1[loop]:=Evaluate(Q1[loop],y[i],sequ[i]);
		end for;
	end for;

	printf "Vinegar Variables:= %o \n \n", sequ;
 
	for i:=2 to u+1 do

		// solving the linear systems
		OSpace:=VectorSpace(F,v[i]-v[i-1]);
		Qseq:=[]; c_Q1:=[];
		for loop:=v[i-1]+1-v[1] to v[i]-v[1] do
			c_Q1:= c_Q1 cat [MonomialCoefficient(Q1[loop],1)];
			for j:=v[i-1]+1 to v[i] do
				Qseq:=Qseq cat [MonomialCoefficient(Q1[loop],y[j])];
			end for;
		end for;
		MatrixQ1:=Matrix(F,v[i]-v[i-1],v[i]-v[i-1],Qseq);
		c_Q1:=OSpace!(c_Q1);

		// solution vector
		x1:=[];
		for k:=1 to v[i]-v[i-1] do
			x1[k]:=x[k+v[i-1]-v[1]];
		end for;

		tr,y1,_:=IsConsistent(Transpose(MatrixQ1),OSpace!(x1)-c_Q1);

		if tr then
			printf"Solution for Layer %o: %o \n \n", i-1, y1;
		else
			printf "No Solution for Layer %o: Choose other Vinegar Variables \n \n", i-1;
			break;
		end if;
		sequ:=sequ cat Eltseq(y1);


		// simplify the system by substituting the values of the oil variables
		for loop:=v[i]-v[1] to m do
			for j:= v[i-1]+1 to v[i] do 
				Q1[loop]:=Evaluate(Q1[loop],y[j],sequ[j]);
			end for;
		end for;

	end for;
until tr;

y:=Signspace!(sequ);
printf"T(signature):= %o \n \n", y;

_,signature,_:=IsConsistent(Transpose(MT),y-cT); // invert T 

// Output
printf "signature= %o \n \n", Eltseq(signature);

printf"Write signature.txt \n \n";
SetOutputFile("signature.txt":Overwrite:=true);
printf "Hashspace:=VectorSpace(F,m); \n \n";
printf "Signspace:= VectorSpace(F,n); \n \n";
printf "hash:=Hashspace!(%o) ; \n \n", Eltseq(hashvalue);
printf "signature:= Signspace!(%o) ; \n \n", Eltseq(signature);
UnsetOutputFile();