/* ==================================================================================== 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;