Disclaimer: This page refers to former member of the group. Validity or accuracy of the following information is thus not guaranteed in any way.
I'm a post-doctoral student at the University of Louvain-la-Neuve in the UCL Crypto Group. I defended my Ph.D. at Marne-la-Vallée University (France) on october 2005. My research interests include applications of Groebner bases in cryptography, and public key cryptosystems based on words.
| Address: | 3, place du Levant |
| Office: | b.012 |
| Voice: | +32 (0) 10 47 22 84 |
| E-Mail: | |
| Homepage: | http://www.dice.ucl.ac.be/~perret |
Seminars given
June 24, 2005 - Algorithms for solving the Isomorphism of Polynomials with One Secret
by Dr. Ludovic Perret
| Abstract: | //Smale Scale Variants of AES n:=4; // number of round (sans compter le round d'addition de la clef// nous avons donc n+1 tours ) r:=2; // number of rows c:=2; // number of columns e:=4; // size of a word // Un état est donc un tabeau de r*c éléments de F_2^e nc:=1; // nb message clair F4<theta>:=FiniteField(2^e); AssertAttribute(F4,"PowerPrinting",false); //(n+1)*r*c*e+n*r*e variables de clefs/// n*e*r*c variables d'etat F:=PolynomialRing(F4, (n+1)*r*c*e+n*r*e+nc*n*r*c*e); // Parties linneaire et affine de la Sbox e=4 Lin4:=Matrix(F,4,4,[1,1,1,0, 0,1,1,1, 1,0,1,1, 1,1,0,1]); // Matrice de la partie linéaire Const4:=theta^2+theta; // Partie affine (Constante) // Parties lineaire et affine de la Sbox e=8 Lin8:=Matrix(F,8,8,[1,0,0,0,1,1,1,1, 1,1,0,0,0,1,1,1, 1,1,1,0,0,0,1,1, 1,1,1,1,0,0,0,1, 1,1,1,1,1,0,0,0, 0,1,1,1,1,1,0,0, 0,0,1,1,1,1,1,0, 0,0,0,1,1,1,1,1]); Const8:=Random(F4); // a revoir !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Set_Poly:=function(f,e) SysEq:=[]; MonTemp:=Monomials(f); CoeffTemp:=Coefficients(f); CoeffTemp:=[Eltseq(CoeffTemp[j]): j in [1..#CoeffTemp]]; for l in [1..e] do EqTemp:=0; for k in [1..#CoeffTemp] do EqTemp:=EqTemp+CoeffTemp[k][l]*MonTemp[k]; end for; SysEq:=SysEq cat [EqTemp]; end for; return SysEq; end function; SymbMatWord:=function(n,r,c,e,cptv) ListWord:=[]; for i in [1..r] do for j in [1..c] do aux:=[]; for k in [0..e-1] do aux:= aux cat [theta^k*F.cptv]; cptv:=cptv+1; end for; ListWord:=ListWord cat [&+aux]; end for; end for; return [* Matrix(F,r,c,ListWord), cptv *]; end function; SymbMatkey:=function(n,r,c,e,cptk) ListWord:=[]; for i in [1..r] do for j in [1..c] do aux:=[]; for k in [0..e-1] do aux:= aux cat [theta^k*F.cptk]; cptk:=cptk+1; end for; ListWord:=ListWord cat [&+aux]; end for; end for; return [* Matrix(F,r,c,ListWord), cptk *]; end function; SymbSubBytes:=function(n,r,c,e,InputWord,OutputWord) // Application de Sbox sur les elements de InputWord SboxMat:=Matrix(F,r,c,[0: i in [1..r*c]]); for i in [1..r] do for j in [1..c] do SboxMat[i,j]:=InputWord[i,j]*OutputWord[i,j]-1; end for; end for; if e eq 4 then for i in [1..r] do for j in [1..c] do OutputWord[i,j]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Set_Poly(OutputWord[i,j],e)))[k]*theta^(k-1): k in [1..e]]; end for; end for; elif e eq 8 then for i in [1..r] do for j in [1..c] do OutputWord[i,j]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Set_Poly(OutputWord[i,j],e)))[k]*theta^(k-1): k in [1..e]]; end for; end for; end if; return SboxMat, OutputWord; end function; ShiftRows:=function(n,r,c,e, InputWord) Aux:=InputWord; for i in [0..r-1] do for j in [0..c-1] do InputWord[i+1,j+1]:=Aux[i+1,1+(j+i)mod c]; end for; end for; return InputWord; end function; MixColumns:=function(n,r,c,e, InputWord) AuxSeq:=[]; if e eq 4 then if r eq 1 then Mat41:=Matrix(F,r,r,[1]); for i in [1..c] do temp:=Matrix(F,r,1,Eltseq(Transpose(InputWord)[i])); AuxSeq:=AuxSeq cat Eltseq(Mat41*temp); end for; return Matrix(F,r,c,AuxSeq); elif r eq 2 then Mat42:= Matrix(F,r,r,[1+theta, theta, theta, 1+theta]); for i in [1..c] do temp:=Matrix(F,r,1,Eltseq(Transpose(InputWord)[i])); AuxSeq:=AuxSeq cat Eltseq(Mat42*temp); end for; return Matrix(F,r,c,AuxSeq); else Mat44:= Matrix(F,r,r,[theta, theta+1, 1, 1, 1, theta, theta+1, 1, 1, 1, theta, theta+1, theta+1, 1, 1, theta ]); for i in [1..c] do temp:=Matrix(F,r,1,Eltseq(Transpose(InputWord)[i])); AuxSeq:=AuxSeq cat Eltseq(Mat44*temp); end for; return Matrix(F,r,c,AuxSeq); end if; else if r eq 1 then Mat81:=Matrix(F,r,r,[1]); for i in [1..c] do temp:=Matrix(F,r,1,Eltseq(Transpose(InputWord)[i])); AuxSeq:=AuxSeq cat Eltseq(Mat81*temp); end for; return Matrix(F,r,c,AuxSeq); elif r eq 2 then Mat82:= Matrix(F,r,r,[1+theta, theta, theta, 1+theta]); for i in [1..c] do temp:=Matrix(F,r,1,Eltseq(Transpose(InputWord)[i])); AuxSeq:=AuxSeq cat Eltseq(Mat82*temp); end for; return Matrix(F,r,c,AuxSeq); else Mat84:= Matrix(F,r,r,[theta, theta+1, 1, 1, 1, theta, theta+1, 1, 1, 1, theta, theta+1, theta+1, 1, 1, theta ]); for i in [1..c] do temp:=Matrix(F,r,1,Eltseq(Transpose(InputWord)[i])); AuxSeq:=AuxSeq cat Eltseq(Mat84*temp); end for; return Matrix(F,r,c,AuxSeq); end if; end if; end function; Gen_Eq_Cipher:=function(n,r,c,e, Message) cptv:=(n+1)*r*c*e+n*r*e+1; //compteur des variables d'etat ListeState:=[]; ListeEq:=[]; ListeKey:=[]; for j in [1..#Message] do cptk:=1; //compteur des variables de clef AuxK:=SymbMatkey(n,r,c,e,cptk); ListeKey:=ListeKey cat [AuxK[1]]; InputWord:=ChangeRing(Message[j],F)+AuxK[1]; cptk:=AuxK[2]; ListeState:=ListeState cat [InputWord]; // Round 1..n for i in [1..n] do AuxW:=SymbMatWord(n,r,c,e,cptv); OutputWord:=AuxW[1]; cptv:=AuxW[2]; // OutputWord est la sortie de la Sbox au round n SboxMat, InputWord:=SymbSubBytes(n,r,c,e,InputWord,OutputWord); ListeEq:=ListeEq cat [SboxMat]; AuxK:=SymbMatkey(n,r,c,e,cptk); cptk:=AuxK[2]; if i ne n then InputWord:=ShiftRows(n,r,c,e, MixColumns(n,r,c,e,InputWord))+AuxK[1]; else InputWord:=ShiftRows(n,r,c,e,InputWord)+AuxK[1]; end if; // InputWord est la sortie du round de chiffrement n, et l'entrée du round n+1 ListeState:=ListeState cat [InputWord]; if j eq 1 then ListeKey:=ListeKey cat [AuxK[1]]; end if; end for; // ListeState[i]=etat apres le round i end for; return ListeEq, ListeState, ListeKey; end function; Gen_Eq_Key:=function(n,r,c,e) //compteur des variables de clef cptk:=1; ListeEq:=[]; SboxMat:=Matrix(F,r,c,[0: i in [1..r*c]]); AuxK:=SymbMatkey(n,r,c,e,cptk); InitKey:=AuxK[1]; cptk:=(n+1)*r*c*e+1; Exkey:=[InitKey:i in [1..n+1]]; if e eq 4 then if r eq 1 then SboxMat:=Matrix(F,1,1,[0]); for i in [2..n+1] do s0:=[]; for k in [0..e-1] do s0:= s0 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s0:=&+s0; Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); SboxMat[1,1]:=s0*Auxb[c]-1; ListeEq:=ListeEq cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 do Auxa[q+1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[t+1]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; elif r eq 2 then SboxMat:=Matrix(F,2,1,[0,0]); for i in [2..n+1] do s0:=[];s1:=[]; for k in [0..e-1] do s0:= s0 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s0:=&+s0; for k in [0..e-1] do s1:= s1 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s1:=&+s1; Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); SboxMat[1,1]:=s0*Auxb[2*c]-1; SboxMat[2,1]:=s1*Auxb[2*c-1]-1; ListeEq:=ListeEq cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]; Auxa[2]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Set_Poly(s1,e)))[k]*theta^(k-1): k in[1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 by 2 do Auxa[r*q+1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; Auxa[r*q+2]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Set_Poly(s1,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+2]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; elif r eq 4 then SboxMat:=Matrix(F,4,1,[0,0,0,0]); for i in [2..n+1] do s0:=[];s1:=[]; s2:=[]; s3:=[]; for k in [0..e-1] do s0:= s0 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s0:=&+s0; for k in [0..e-1] do s1:= s1 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s1:=&+s1; for k in [0..e-1] do s2:= s2 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s2:=&+s2; for k in [0..e-1] do s3:= s3 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s3:=&+s3; Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); SboxMat[1,1]:=s0*Auxb[4*c]-1; SboxMat[2,1]:=s1*Auxb[4*c-1]-1; SboxMat[3,1]:=s2*Auxb[4*c-2]-1; SboxMat[4,1]:=s3*Auxb[4*c-3]-1; ListeEq:=ListeEq cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]; Auxa[2]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Set_Poly(s1,e)))[k]*theta^(k-1): k in [1..e]]; Auxa[3]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Set_Poly(s2,e)))[k]*theta^(k-1): k in [1..e]]; Auxa[4]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Set_Poly(s3,e)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 by 4 do Auxa[r*q+1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; Auxa[r*q+2]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Set_Poly(s1,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+2]:t in [0..q]]; Auxa[r*q+3]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Set_Poly(s2,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+3]:t in [0..q]]; Auxa[r*q+4]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Set_Poly(s3,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+4]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; end if; elif e eq 8 then if r eq 1 then SboxMat:=Matrix(F,1,1,[0]); for i in [2..n+1] do s0:=[]; for k in [0..e-1] do s0:= s0 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s0:=&+s0; Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); SboxMat[1,1]:=s0*Auxb[c]-1; ListeEq:=ListeEq cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 do Auxa[q+1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[t+1]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; elif r eq 2 then SboxMat:=Matrix(F,2,1,[0,0]); for i in [2..n+1] do s0:=[];s1:=[]; for k in [0..e-1] do s0:= s0 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s0:=&+s0; for k in [0..e-1] do s1:= s1 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s1:=&+s1; Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); SboxMat[1,1]:=s0*Auxb[2*c]-1; SboxMat[2,1]:=s1*Auxb[2*c-1]-1; ListeEq:=ListeEq cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]; Auxa[2]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Set_Poly(s1,e)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 by 2 do Auxa[r*q+1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; Auxa[r*q+2]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Set_Poly(s1,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+2]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; elif r eq 4 then SboxMat:=Matrix(F,4,1,[0,0,0,0]); for i in [2..n+1] do s0:=[];s1:=[]; s2:=[]; s3:=[]; for k in [0..e-1] do s0:= s0 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s0:=&+s0; for k in [0..e-1] do s1:= s1 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s1:=&+s1; for k in [0..e-1] do s2:= s2 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s2:=&+s2; for k in [0..e-1] do s3:= s3 cat [theta^k*F.cptk]; cptk:=cptk+1; end for; s3:=&+s3; Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); SboxMat[1,1]:=s0*Auxb[4*c]-1; SboxMat[2,1]:=s1*Auxb[4*c-1]-1; SboxMat[3,1]:=s2*Auxb[4*c-2]-1; SboxMat[4,1]:=s3*Auxb[4*c-3]-1; ListeEq:=ListeEq cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]; Auxa[2]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Set_Poly(s1,e)))[k]*theta^(k-1): k in [1..e]]; Auxa[3]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Set_Poly(s2,e)))[k]*theta^(k-1): k in [1..e]]; Auxa[4]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Set_Poly(s3,e)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 by 4 do Auxa[r*q+1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Set_Poly(s0,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; Auxa[r*q+2]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Set_Poly(s1,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+2]:t in [0..q]]; Auxa[r*q+3]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Set_Poly(s2,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+3]:t in [0..q]]; Auxa[r*q+4]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Set_Poly(s3,e)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+4]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; end if; end if; return Exkey, ListeEq; end function; // ********************************************************************** // Fonctions de test du chiffrement Sbox:=function(elt) if elt eq 0 then return F4 ! 0; else return F4 ! elt^(-1); end if; end function; Expandedkey:=function(n,r,c,e,InitKey) ListeSbox:=[]; Exkey:=[InitKey:i in [1..n+1]]; if e eq 4 then if r eq 1 then SboxMat:=Matrix(F,1,1,[0]); for i in [2..n+1] do Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); s0:=Sbox(Auxb[c]); SboxMat[1,1]:=s0; ListeSbox:=ListeSbox cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 do Auxa[q+1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; elif r eq 2 then SboxMat:=Matrix(F,2,1,[0,0]); for i in [2..n+1] do Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); s0:=Sbox(Auxb[2*c]); s1:=Sbox(Auxb[2*c-1]); SboxMat[1,1]:=s0; SboxMat[2,1]:=s1; ListeSbox:=ListeSbox cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]; Auxa[2]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s1)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 by 2 do Auxa[r*q+1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; Auxa[r*q+2]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Eltseq(s1)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+2]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; elif r eq 4 then SboxMat:=Matrix(F,4,1,[0,0,0,0]); for i in [2..n+1] do Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); s0:=Sbox(Auxb[4*c]); s1:=Sbox(Auxb[4*c-1]); s2:=Sbox(Auxb[4*c-2]); s3:=Sbox(Auxb[4*c-3]); SboxMat[1,1]:=s0; SboxMat[2,1]:=s1; SboxMat[3,1]:=s2; SboxMat[4,1]:=s3; ListeSbox:=ListeSbox cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]; Auxa[2]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s1)))[k]*theta^(k-1): k in [1..e]]; Auxa[3]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s2)))[k]*theta^(k-1): k in [1..e]]; Auxa[4]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s3)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 by 4 do Auxa[r*q+1]:=theta^(i-1)+Const4+&+[Eltseq(Lin4*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; Auxa[r*q+2]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Eltseq(s1)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+2]:t in [0..q]]; Auxa[r*q+3]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Eltseq(s2)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+3]:t in [0..q]]; Auxa[r*q+4]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Eltseq(s3)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+4]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; end if; elif e eq 8 then if r eq 1 then SboxMat:=Matrix(F,1,1,[0]); for i in [2..n+1] do Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); s0:=Sbox(Auxb[c]); SboxMat[1,1]:=s0; ListeSbox:=ListeSbox cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 do Auxa[q+1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; elif r eq 2 then SboxMat:=Matrix(F,2,1,[0,0]); for i in [2..n+1] do Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); s0:=Sbox(Auxb[2*c]); s1:=Sbox(Auxb[2*c-1]); SboxMat[1,1]:=s0; SboxMat[2,1]:=s1; ListeSbox:=ListeSbox cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]; Auxa[2]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s1)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 by 2 do Auxa[r*q+1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; Auxa[r*q+2]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Eltseq(s1)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+2]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; elif r eq 4 then SboxMat:=Matrix(F,4,1,[0,0,0,0]); for i in [2..n+1] do Auxa:=Eltseq(Exkey[i]); Auxb:=Eltseq(Exkey[i-1]); s0:=Sbox(Auxb[4*c]); s1:=Sbox(Auxb[4*c-1]); s2:=Sbox(Auxb[4*c-2]); s3:=Sbox(Auxb[4*c-3]); SboxMat[1,1]:=s0; SboxMat[2,1]:=s1; SboxMat[3,1]:=s2; SboxMat[4,1]:=s3; ListeSbox:=ListeSbox cat [SboxMat]; if c eq 1 then Auxa[1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]; Auxa[2]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s1)))[k]*theta^(k-1): k in [1..e]]; Auxa[3]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s2)))[k]*theta^(k-1): k in [1..e]]; Auxa[4]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s3)))[k]*theta^(k-1): k in [1..e]]; Exkey[i]:=Matrix(F,r,c,Auxa); else for q:=0 to c-1 by 4 do Auxa[r*q+1]:=theta^(i-1)+Const8+&+[Eltseq(Lin8*Matrix(F,e,1,Eltseq(s0)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+1]:t in [0..q]]; Auxa[r*q+2]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Eltseq(s1)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+2]:t in [0..q]]; Auxa[r*q+3]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Eltseq(s2)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+3]:t in [0..q]]; Auxa[r*q+4]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Eltseq(s3)))[k]*theta^(k-1): k in [1..e]]+&+[Auxb[r*t+4]:t in [0..q]]; end for; Exkey[i]:=Matrix(F,r,c,Auxa); end if; end for; end if; end if; return Exkey, ListeSbox; end function; SubBytes:=function(n,r,c,e, InputWord) InputWord:=Matrix(F4,r,c,[Sbox(elt): elt in Eltseq(InputWord)]); SboxOut:=InputWord; if e eq 4 then for i in [1..r] do for j in [1..c] do InputWord[i,j]:=Const4+&+[Eltseq(Lin4*Matrix(F,e,1, Eltseq(InputWord[i,j])))[k]*theta^(k-1): k in [1..e]]; end for; end for; elif e eq 8 then for i in [1..r] do for j in [1..c] do InputWord[i,j]:=Const8+&+[Eltseq(Lin8*Matrix(F,e,1, Eltseq(InputWord[i,j])))[k]*theta^(k-1): k in [1..8]]; end for; end for; end if; return [SboxOut, InputWord]; end function; AES:=function(n,r,c,e,nc) Message:=[];ListeState:=[]; ListeSbox:=[]; auxMess:=[0: i in [1..r*c]]; for i in [1..nc] do temp:=auxMess; temp[i]:=1; //Message:=Message cat [Matrix(F4,r,c,temp)]; Message:=Message cat [Matrix(F4,r,c,[Random(F4): i in [1..r*c]])]; end for; InitKey:=Matrix(F4,r,c,[Random(F4): i in [1..r*c]]); ExKey, ListeSboxKey:=Expandedkey(n,r,c,e,InitKey); for j in [1..nc] do // Round 0 State:=Message[j]+ExKey[1]; ListeState:=ListeState cat [State]; // Round 1..n for i in [1..n] do Aux:=SubBytes(n,r,c,e,State); ListeSbox:=ListeSbox cat [Aux[1]]; State:=Aux[2]; if i ne n then State:=ChangeRing(ShiftRows(n,r,c,e, MixColumns(n,r,c,e,State)),F4)+ExKey[i+1]; else State:=ChangeRing(ShiftRows(n,r,c,e,State),F4)+ExKey[n+1]; end if; // InputWord est la sortie du round de chiffrement n, et l'entrée du round n+1 ListeState:=ListeState cat [State]; end for; end for; return Message, ExKey, ListeState, ListeSbox, ListeSboxKey; end function; // ********************************************************************** //test Message, ExKey, ListeState, ListeSbox, ListeSboxKey:=AES(n,r,c,e,nc); /* Message : les clairs utilisée pour générer les nc systeme Exkey : les n+1 clefs ListeState[i] : etat après le round i ListeSbox[i] : valeur de la sortie de la Sbox (juste X->1/X) dans le chiffrement ListeSboxKey[i] : valeur de la sortie de la Sbox (juste X->1/X) dans le cadencement de clef */ ListeEqC, ListeStateSymb, ListeKeySymb:=Gen_Eq_Cipher(n,r,c,e,Message); /* ListeEqC : équations du chiffrement ListeStateSymb[i] : etat (sous forme symbolique) après le round i ListeKeySymb[i] : les n+1 clefs sous forme symbolique */ ListeK, Eq:=Gen_Eq_Key(n,r,c,e); /* Eq:= equation provenant du chiffrement du cdencement de clef */ // Je teste ici si le système que je génère admet bien une "bonne" solution test:=[]; // ********************************************************** for mat in ExKey do for i in [1..r] do for j in [1..c] do auxij:=Eltseq(F4!mat[i,j]); for k in [1..e] do test:=test cat [auxij[k]]; end for; end for; end for; end for; for mat in ListeSboxKey do for i in [1..r] do auxij:=Eltseq(F4!mat[i,1]); for k in [1..e] do test:=test cat [auxij[k]]; end for; end for; end for; for mat in ListeSbox do for i in [1..r] do for j in [1..c] do auxij:=Eltseq(F4!mat[i,j]); for k in [1..e] do test:=test cat [auxij[k]]; end for; end for; end for; end for; // ********************************************************** // equations du Chiffrement SysEqC:=[]; for mat in ListeEqC do for elt in Eltseq(mat) do SysEqC:=SysEqC cat Set_Poly(elt,e); end for; end for; // equations du cadencement des clefs SysEqK:=[]; for mat in Eq do for elt in Eltseq(mat) do SysEqK:=SysEqK cat Set_Poly(elt,e); end for; end for; // equations linéaires var. clef chif//clef cadence // #ListeKeySymb=nc*#ListeK ListeK:=[ListeK[i]-ListeKeySymb[i]: i in [1..#ListeK]]; SysEqKl:=[]; for mat in ListeK do for elt in Eltseq(mat) do SysEqKl:=SysEqKl cat Set_Poly(elt,e); end for; end for; // Equations provenant du chiffré SysEqCi:=[]; //aux:=ChangeRing(ListeState[n+1],F)-ListeStateSymb[n+1] for i in [1..nc] do for elt in Eltseq(ChangeRing(ListeState[i*(n+1)],F)-ListeStateSymb[i*(n+1)]) do SysEqCi:=SysEqCi cat Set_Poly(elt,e); end for; end for; //Systeme AES SysAES:=SysEqC cat SysEqK cat SysEqKl cat SysEqCi cat [F.i^2-F.i: i in [1..(n+1)*r*c*e+n*r*e+nc*n*r*c*e]]; testSys:=[Evaluate(elt,test): elt in SysAES]; zeroSys:=[F4!0: i in [1..#testSys]]; if testSys eq zeroSys then #SysAES; SetVerbose("Faugere", 1); time V:=Variety(Ideal(SysAES)); end if; |
Publications
Jean-Charles Faugère, Christophe Petit, Ludovic Perret, and Guénaël Renault. Improving the Complexity of Index Calculus Algorithms in Elliptic Curves over Binary Fields, Eurocrypt 2012, April 2012 BibTeX
Jean-Charles Faugère, and Ludovic Perret. Cryptanalysis of 2R- schemes, Advances in Cryptology - CRYPTO 2006, Volume 4117 of Lecture Notes in Computer Science, pages 357-372, Springer, August 2006 BibTeX
Jean-Charles Faugère, and Ludovic Perret. Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects, Advances in Cryptology - EUROCRYPT 2006, Volume 4004 of Lecture Notes in Computer Science, pages 30-47, Springer, May 2006 BibTeX
Ludovic Perret. A Fast Cryptanalysis of the Isomorphism of Polynomials with One Secret Problem, Advances in Cryptology - EUROCRYPT 2005, Volume 3494 of Lecture Notes in Computer Science, pages 354-370, Springer-Verlag, January 2005 BibTeX
Ludovic Perret. A Chosen Ciphertext Attack on a Public Key Cryptosystem Based on Lyndon Words, Proceedings of International Workshop on Coding and Cryptography (WCC 2005), pages 235-244, January 2005 BibTeX
Françoise Levy-dit-Vehel, and Ludovic Perret. On Wagner-Magyarik Cryptosystem, Proceedings of International Workshop on Coding and Cryptography (WCC 2005), pages 285-294, January 2005 BibTeX
Françoise Levy-dit-Vehel, and Ludovic Perret. Attacks on Public Key Cryptosystems Based on Free Partially Commutative Monoids and Groups, Progress in Cryptology - INDOCRYPT 2004, Volume 3348 of Lecture Notes in Computer Science, pages 275-289, Springer-Verlag, January 2004 BibTeX
Ludovic Perret. A Geometrical Approach to a Polynomial Equivalence Problem, Proceedings of International Conference on Polynomial System Solving (ICPSS), in honor of Daniel Lazard, pages 30-33, January 2004 BibTeX
Ludovic Perret, and Abdelmajid Bayad. A Differential Approach to a Polynomial Equivalence Problem, Proceedings of IEEE International Symposium on Information Theory (ISIT 2004), January 2004 BibTeX
Françoise Levy-dit-Vehel, and Ludovic Perret. Polynomial Equivalence Problems and Applications to Multivariate Cryptosystems, Progress in Cryptology - INDOCRYPT 2003, Volume 2904 of Lecture Notes in Computer Science, pages 235-251, Springer-Verlag, January 2003 BibTeX
Copyright Notice
(click here to expand/retract)Some material that is available from this page is copyrighted.
IACR Copyright Notice: Permission is granted for a user to display all material at this site, to copy the material onto a single computer, and to make print copies of the material for personal use only. All other rights are retained by the International Association for Cryptologic Research. In particular, any other copying, other redistribution, or any commercial use of the material requires the permission of the publisher, which may be requested by contacting the International Association for Cryptologic Research.
IEEE Copyright Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
ACM Copyright Notice: Copyright © 1999 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page or intial screen of the document. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.
Springer-Verlag LNCS Copyright Notice: The copyright of these contributions has been transferred to Springer-Verlag Berlin Heidelberg New York. The copyright transfer covers the exclusive right to reproduce and distribute the contribution, including reprints, translations, photographic reproductions, microform, electronic form (offline, online), or any other reproductions of similar nature. Online available from Springer-Verlag LNCS series.