//============================================
// Signature Generation of (projected) SFLASH
// the program reads in the private key from private_key.txt
// and generates a signature for a randomly chosen message
// message and signature are stored in message.txt
//==============================================

function squareandmultiply(m,e,p) // for efficient exponentiation
	e:=Intseq(e,2);
	s:=# e;
	erg:=1;
	for i:=1 to s do
		if e[i] eq 1 then
			erg:=erg *m mod p;
		end if;
		m:=m^2 mod p;
	end for;
	return erg;
end function;

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

load "private_key.txt";

Vn:=VectorSpace(F,n);
Poly<X>:=PolynomialRing(F);

hashspace:=VectorSpace(F,n-a);
hash:=Random(hashspace);
printf"Generate Signature for the message %o \n \n", hash;


MS:=Matrix(F,n-a,n,MS); // read in private key
MT:=Matrix(F,n,n,MT);
cS:=Matrix(F,n-a,1,cS);
cT:=Matrix(F,n,1,cT);

repeat // ------------------------------------------------------------------------------------------------------------

	//find pre image of hash under S

	_,x,kernel:=IsConsistent(Transpose(MS), hash - hashspace!Eltseq(cS));
	x:=Eltseq(x+Random(kernel));


	//central map

	MIB:=0; // lift to the extension field
	for i:=1 to n do
		MIB:=MIB+x[i]*X^(n-i);
	end for;

	MIA:=squareandmultiply(MIB,thetainv,irrpol); // invert central MI map

	y:=[]; // move the result to the vector space
	for i:=1 to n do
		y[i]:=MonomialCoefficient(MIA,X^(n-i));
	end for;


	// map T
	_,signature,kernel:=IsConsistent(Transpose(MT), Vn!(y) - Vn!Eltseq(cT));
	signature:=Eltseq(signature);

	tr:=true; // test if the last s components of signature are 0
	for i:=n-s+1 to n do
		if signature[i] ne 0 then
			tr:=false;
		end if;
	end for;

	printf"S^-1 (message):= %o \n \n", x;
	printf"MIB:= %o \n \n", MIB;
	printf"MIA:= %o \n \n", MIA;
	printf"T (signature):= %o \n \n", y;
	printf"signature := %o \n \n", signature;
	if tr eq false then
		printf" Projection fails. Choose other preimage. \n \n -------------------------- \n \n";
	end if;

until tr ; //------------------------------------------------------------------------------------

for i:=1 to s do // remove the last s elements from signature
	Prune(~signature);
end for;

if s gt 0 then
	printf "\n ------------------ \n \n signature:= %o \n", signature;
end if;





printf "Write signature.txt \n \n";

SetOutputFile("signature.txt":Overwrite:=true);
printf "hashspace:=VectorSpace(F,n-a); \n \n";
printf "signspace:=VectorSpace(F,n-s); \n \n";
printf "hash:= hashspace!(%o) ; \n \n", Eltseq(hash);
printf "signature:= signspace!(%o); \n \n", Eltseq(signature);
UnsetOutputFile();