/* ====================================================================================
Decryption process of Perturbed Matsumoto Imai (Plus)
The program loads the private key from private_key.txt and the ciphertext from ciphertext.txt
and outputs the decrypted message
========================================================================================*/
load "private_key.txt";
load "ciphertext.txt";
Plaintexts:=[];

function squareandmultiply(m,e,p) // for fast exponentiation
	e:=Intseq(e,2);
	s:=# e; // bitlength of 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 "ciphertext:= %o \n \n", ciphertext;

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

//  MI ============================================================================================
//S invertieren
P:=Eltseq((ciphertext-Vns!Eltseq(cS))*Transpose(MS)^(-1));

for i:=1 to s do // discard s last elements
	Prune(~P);
end for;

Pe:=[];
for loop:=1 to q^r do
	for i:=1 to n do
	Pe[i]:=P[i] +Mu[loop][i];
end for;

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

MIA:=squareandmultiply(MIB,thetainv,irrpol);

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

Zet:=Z;
Zet2:=[];
for i:=1 to r do
	for j:=1 to n do
		Zet[i]:=Evaluate(Zet[i],x[j],Y[j]);
	end for;
	Zet2[i]:=MonomialCoefficient(Zet[i],1);
end for;

Y;
Zet2;
Lambda[loop];
printf "\n";

//if Zet eq Lambda[loop] then
// invert T
Pl:=(Y-Vn!Eltseq(cT))*Transpose(MT)^(-1);
Plaintexts:=Plaintexts cat [Eltseq(Pl)];
//end if;
end for;
//===============================================================================================
printf"S^(-1):= \n%o \n \n", MS^(-1);
printf"S^-1 (ciphertext):= %o \n \n", P;
printf"T^(-1):= \n%o \n \n", MT^(-1);
printf"Possible Plaintexts:= \n%o \n \n", Plaintexts;