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