/* ====================================================================================
Decryption process of Matsumoto Imai
The program loads the private key from private_key.txt and the ciphertext from ciphertext.txt
and outputs the decrypted message
========================================================================================*/
timet:=Cputime();
mem:= GetMemoryUsage();
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 "************************************************\n";
printf "*** Matsumoto-Imai Cryptosystem - Decryption *** \n";
printf "************************************************ \n \n";

load "private_key.txt";
load "ciphertext.txt";

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

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

// lift into extension field
MIB:=Poly!0;
for i:=1 to n do
	MIB:=MIB+ P[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;

// invert T
Z:=(Y-Vn!Eltseq(cT))*Transpose(MT)^(-1);

//mem:= GetMemoryUsage(mem);
PrintFile("times_decrypt",Cputime(timet));
timet:=Cputime(timet);
print "MI decrypt time:",timet;

//===============================================================================================
printf"S^(-1):= \n%o \n \n", MS^(-1);
printf"T^(-1):= \n%o \n \n", MT^(-1);
printf "ciphertext:= %o \n \n", ciphertext;
printf"S^-1 (ciphertext):= %o \n \n", P;
printf"MIB:= %o \n \n", MIB;
printf"MIA:= %o \n \n", MIA;
printf"T (message):= %o \n \n", Y;
printf"message:= %o \n \n", Z;
printf"\nMemory usage: %o\n", mem;