/* -------------------------------------------------------------
Decryption Process of the of HFE Encryption Scheme
loads private key from private_key.txt and ciphertext from ciphertext.txt
and outputs the corresponding plaintext
---------------------------------------------------------------*/

clear ;

printf "****************************************** \n";
printf "*** HFE Encryption Scheme - Decryption *** \n";
printf "****************************************** \n \n";

SetSeed(0,0) ;

timet:= Cputime() ;
load "private_key.txt";
load "ciphertext.txt";

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

Id:= ideal < Pol | irrpol>;
Q<X>:= quo < Pol | Id >;
Poly<A>:=PolynomialRing(Q);

printf"ciphertext:= %o \n", messagespace!(ciphertext);

//S invertieren
_,k,kernel:=IsConsistent(Transpose(MS), messagespace!(ciphertext) - cS);

printf "timet1: %o\n", Cputime(timet);

k:=Eltseq(k+Random(kernel));
printf "S^(-1)(ciphertext):= %o \n \n", k;

//central map

B:=Q!0;
for i:=1 to n do
	B:=B+k[i]*X^(i-1);
end for;

printf "B:= %o \n\n", B;


polA:=Q!Alpha[1];  // Build the central map
ij := 2 ;

for i:=0 to  r1 do
     polA:=polA+Q!Alpha[ij]*A^(q^i);
     ij +:= 1 ;
     for j:=0 to i do
	if q^i+q^j le D then
		polA:=polA+Q!Alpha[ij]*A^(q^i+q^j);
		ij +:= 1;
	end if;
     end for;
end for;

printf "timet3: %o\n", Cputime(timet);

polA:=polA-B;

fact:=Roots(polA);

printf "roots=%o\n  timet4: %o\n",fact,Cputime(timet);


y:=[];
i:=1;
while i le #fact  do

     
printf "i= %o  timet5: %o\n",i ,Cputime(timet);
	
	sol:=Q!(fact[i][1]);

	printf "Found root A:= %o \n \n", sol;

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

	printf "y:= %o \n\n", y;


// T invertieren
	_,plaintext,kernel:=IsConsistent(Transpose(MT), messagespace!(y) - cT);

	printf"plaintext := %o \n", plaintext;
	printf"original  := %o \n",original  ;

	i:=i+1;

end while;

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