//********************************************************* // Linearization Equations Attack against MI // The program reads in the public key from public_key.txt // and performs Patarins Linearization Equations Attack to decrypt // a randomly chosen ciphertext //********************************************************* printf "**************************************************************************\n"; printf "Linearization Equations Attack against the Matsumoto-Imai Cryptosystem *** \n"; printf "*************************************************************************** \n \n"; load "public_key.txt"; Vn:=VectorSpace(F,n); ciphertext:=Random(Vn); printf "We want to find the plaintext corresponding to the ciphertext %o \n \n", Vn!ciphertext; number1:=(n+1)^2; // find equations of the form \sum a_ij x_iy_j + \sum b_i x_i + sum c_j y_j + d = 0 printf" Create %o plaintext/ciphertext pairs \n \n ", number1; // Table of plaintext/ciphertext pairs Plaintexts:=[]; Ciphertexts:=[]; for i:=1 to number1 do Pub:=Pk; plaintext:=Random(Vn); for loop:=1 to n do for j:=1 to n do Pub[loop]:=Evaluate(Pub[loop],x[j],plaintext[j]); end for; end for; Plaintexts[i]:=plaintext; Ciphertexts[i]:=Vn!Pub; end for; // -------------------------------------------------------------------------------------------- printf" Plaintexts \t \t Ciphertexts \n"; for i:=1 to number1 do printf" %o \t \t %o \n", Plaintexts[i], Ciphertexts[i]; end for; printf" \n \n"; printf"Find Linearization equations of the form \sum x_iy_i + \sum x_i + \sum y_i + d =0 \n \n"; //Matrix for the equations LinEq:=ZeroMatrix(F,number1,n*n+n+n+1); for loop:=1 to number1 do counter:=1; for i:=1 to n do // a_ij for j:=1 to n do LinEq[loop][counter]:=Plaintexts[loop][i]*Ciphertexts[loop][j]; counter:=counter+1; end for; end for; for i:=1 to n do // b_i LinEq[loop][counter]:=Plaintexts[loop][i]; counter:=counter+1; end for; for j:=1 to n do //c_i LinEq[loop][counter]:=Ciphertexts[loop][j]; counter:=counter+1; end for; LinEq[loop][counter]:=1; // d; end for; Kera:=Kernel(Transpose(LinEq)); dim:=Dimension(Kera); printf " Found %o linear independent Linearization Equations \n \n", dim; Base:=Basis(Kera); //============================================================================================================= Poly:=PolynomialRing(F,2*n); nam:=[]; for i:=1 to n do nam[i]:= "u[" cat IntegerToString(i) cat "]"; end for; for i:=n+1 to 2*n do nam[i]:= "v[" cat IntegerToString(i-n) cat "]"; end for; AssignNames(~Poly,nam); Lineq1:=[]; //Linearization Equations for loop:=1 to #Base do Lineq1[loop]:=Poly!0; counter:=1; for i:=1 to n do for j:=n+1 to 2*n do Lineq1[loop]:=Lineq1[loop]+ Base[loop][counter]*Poly.i*Poly.j; // a_ij counter:=counter+1; end for; end for; for i:=1 to n do Lineq1[loop]:=Lineq1[loop]+Base[loop][counter]*Poly.i; // b_i counter:=counter+1; end for; for j:=n+1 to 2*n do Lineq1[loop]:=Lineq1[loop]+Base[loop][counter]*Poly.j; // c_j counter:=counter+1; end for; Lineq1[loop]:=Lineq1[loop]+Base[loop][counter]; // d end for; Lineq1; //=========================================================================================================== printf "Insert ciphertext into the linearization equations \n \n"; for loop:=1 to #Base do // substitute ciphertext into linearization equations for i:=1 to n do Lineq1[loop]:=Evaluate(Lineq1[loop],Poly.(i+n),ciphertext[i]); end for; end for; Mat:=ZeroMatrix(F,#Base,n+1); // Equations for plaintext variables for loop:=1 to #Base do for i:=1 to n do Mat[loop][i]:=MonomialCoefficient(Lineq1[loop],Poly.i); end for; Mat[loop][n+1]:=MonomialCoefficient(Lineq1[loop],1); end for; Mat:=EchelonForm(Mat); t:=Rank(Mat); printf"Found %o linear equations in the plaintext variables \n \n", t; pol:=[]; for loop:=1 to t do pol[loop]:=Pol!0; for i:=1 to n do pol[loop]:=pol[loop]+ Mat[loop][i]*x[i]; end for; pol[loop]:=pol[loop]+Mat[loop][n+1]; end for; for loop:=1 to t do printf" %o = 0 \n", pol[loop]; end for; V:=Variety(Ideal(pol)); printf "\n possible Plaintexts \t \t Ciphertexts \n"; for i:=1 to #V do ciph:= Pk; for j:=1 to n do for k:=1 to n do ciph[j]:= Evaluate(ciph[j],x[k],V[i][k]); end for; end for; printf" %o \t \t %o \n", V[i], Vn!ciph; if Vn!ciph eq ciphertext then sol:=V[i]; end if; end for; printf"\nOur ciphertext %o corresponds to the plaintext %o \n \n", ciphertext, sol;