/* -------------------------------------------------------------
Decryption Process of the SimpleMatrix Encryption Scheme
loads private key from private_key.txt and ciphertext from ciphertext.txt
outputs corresponding plaintext
---------------------------------------------------------------*/
clear;
printf "*************************************************** \n";
printf "*** SimpleMatrix Encryption Scheme - Decryption *** \n";
printf "*************************************************** \n \n";

timet:= Cputime() ;
load "private_key.txt";
load "ciphertext.txt";
Vn:=VectorSpace(GF,n);
Vm:=VectorSpace(GF,m);

S:=Matrix(GF,m,m,S);
T:=Matrix(GF,n,n,T);
B:=Matrix(Pol,s,s,B);
C:=Matrix(Pol,s,s,C);
cT:=Vn!cT;
cS:=Vm!cS;

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

// first step ------------------------------------------------------------------------------------------------------------------------------
ix:=(ciphertext-cS)*Transpose(S^(-1));

E1:=ZeroMatrix(GF,s,s);
E2:=ZeroMatrix(GF,s,s);
for i:=1 to s do
	for j:=1 to s do
		E1[i][j]:=ix[(i-1)*s+j];
		E2[i][j]:=ix[n+(i-1)*s+j];
	end for;
end for;

printf "E1:= \n%o \n \n", E1;
printf "E2:= \n%o \n \n", E2; 

//Second Step
System:=ZeroMatrix(GF,m,m); 
	v:=Zero(Vm);
	A1:=ZeroMatrix(Pol,s,s);
	for i:=1 to s do
		for j:=1 to s do
			A1[i][j]:=x[n+(i-1)*s+j];
		end for;
	end for;		
	Sys1:=A1*E1-B; 
	for i:=1 to s do
		for j:=1 to s do
			for k:=1 to m do
				System[(i-1)*s+j][k]:=MonomialCoefficient(Sys1[i][j],x[k]);
			end for;
		end for;
	end for;
	Sys2:=A1*E2-C;
	for i:=1 to s do
		for j:=1 to s do
			for k:=1 to m do
				System[n+(i-1)*s+j][k]:=MonomialCoefficient(Sys2[i][j],x[k]);
			end for;
		end for;
	end for;

	_,yps,ker:=IsConsistent(Transpose(System),v);

	yps1:=[];
	ker1:=[];
	for i:=1 to n do
		yps1[i]:=yps[i];
		ker1[i]:=Basis(ker)[1][i];
	end for; 
	yps1:=VectorSpace(GF,n)!yps1;
	ker1:=VectorSpace(GF,n)!ker1;

	printf "T(message):= %o + k * %o  (k in GF) \n \n",yps1, ker1;
	
	//Third step
	k:=GF.1;
	repeat
		plaintext:= (yps1+k*ker1-cT) * Transpose(T^(-1));
		k:=k*w;
	until plaintext[1] eq 1;
	printf "time for decryption: %o\n\n",Cputime(timet);
	printf "Found Solution: k= %o, plaintext:= %o \n \n", k, plaintext;