Master Pro Ingenierie Mathematique Cryptographie

Description

Niveau: Supérieur, Master
Master Pro – Ingenierie Mathematique – Cryptographie Cryptanalyse des protocoles a cle secrete CHAPITRE 5. CRYPTANALYSE DES PROTOCOLES A CLE SECRETE

• relations lineaires de dependance de probabilites exceptionnelles entre les bits d'entree et de sortie


• bits de sortie


• cryptanalyse des protocoles


• fonctions lineaires


• texte clair

Informations

• Publié par: cidur
• Nombre de lectures: 56
• Langue: Français

Extrait

MasterPro–Ing´einreeiaMhte´amite–quypCrgrtohiap yrC e natpsylasedeocolprotcl´ees`ae`etesrc

CHAPITRE 5.

CRYPTANALYSE DES PROTOCOLES ` ´ ` A CLE SECRETE

http://math.univ-lyon1.fr/~roblot/masterpro.html

rProasteMhtaMeireine´gnI–toypCre–qutima´e desyrpsecotoselo apgre C hi ptryalan fnsuoiendtffisuoi `acl´esecr`ete Con

Confusion .C’estlefaitquelame´thodedecalculdumessagecrypt´ea` partirdumessageclairdoitˆetresuffisammentcomplexe.C’est-`a-dire qu’il ne doit pas exister de relation simples entre les bits du message clair etlesbitsdumessagecrypt´e.

Enthe´oriedel’information, Shannon de´finitdeuxnotionsquetoutbon cryptosyst`emedoitposse´der:la confusion et la diffusion .

Diffusion .C’estlefaitquunediffe´rence,mˆememinime,entredeux ’ messagesclairsdoitentraınerunetr`esgrandediffe´renceentreles ˆ messagescrypte´s.Ainsi,chaquebitdumessageclairdoitcontribuerau calculdechaquebitdumessagecrypt´e.

Confusion et diffusion

rotocolelysedespce`rte C e`sca´lse dietsiffufuononsino

deg( f 1 , . . . , f m ) ≈ n.

pour 1 ≤ i ≤ m .

deg( f 1 , . . . , f m ) = min(deg f 1 , . . . , deg f m )

o`u deg f i estledegre´delarepre´sentationalg´ebriquede f i , on veut avoir

Soituncryptosyst`emedonn´eparlafonctionbool´eennevectorielle ( f 1 , . . . , f m ) sur { 0 , 1 } n .

Confusion . La confusion correspond au fait que les fonctions f i n’ont pas d’expression “simple”. Si on pose

Diffusion . La diffusion correspond au fait que les bits de sortie, donc les valeurs des f i ,varientdemanie`reimpr´evisiblequandonmodifiel’entre´e. Donc pour tout x ∈ { 0 , 1 } n et tout δ ∈ { 0 , 1 } n avec δ 6 = 0 , on veut avoir Prob  f i ( x ) = f i ( x ⊕ δ )  ≈ 1 / 2

Cryptana ographieeuC–yrtp´hmetaqiriieateMIno–eng´tsaMrPre

Eneffet,unerelationlin´eairenepeutpasˆetrevraiepour tous les messages w sinon le protocole a une faiblesse.

Exercice . Montrer que le protocole de Vigen`ere est lineaire. ´

C’estuneattaque`a texte clair connu contre les protocoles de cryptographie dont la confusion est faible.

Cryptanalyselin´eaire

Ide´e . Trouver des relationslin´eaires ded´ependancede probabilite´s exceptionnelles entrelesbitsd’entr´eeetdesortie.

Texte clair connu . L’attaquant dispose de un ou plusieurs message(s) clair(s)avecle(s)message(s)crypt´e(s)correspondant,touscrypte´savec lamˆemecle.L’attaquantcherchea`retrouver(del’informationsur)lacle´. ´

MsaetPr aerieypCrnataselyn´li a`see´lcrcesete`edesalysocolprot paihotrg tpnaC e yr tima´ethypCre–que´gnI–oraMeirein

Exercice . Soit f unefonctionline´aireboole´ennesur { 0 , 1 } 3 avec f (010) = 0 , f (111) = 1 et f (011) = 0 . Retrouver la fonction f .

Exercice .De´montrercesdeuxre´sultatsetend´eduirelenombrede fonctionsboole´enneslin´eairesetaffines.

D´efinition .Unefonctionbool´eenne f dontlarepre´sentationalg´ebrique estdedegre´ 1 est dite affine . Si, de plus, on a f (0 ... 0) = 0 , on dit que f est line´aire .

Fonctionslin´eaires

f ( x ) = x ∗ v o`u v ∈ { 0 , 1 } n

Fonctionslin´eairesetproduitscalaire .Lesfonctionsline´airesde { 0 , 1 } n sont exactement les fonctions de la forme

f ( x ) = ( x ∗ v ) ⊕ w ou` v ∈ { 0 , 1 } n et w ∈ { 0 , 1 }

Les fonctions affines de { 0 , 1 } n sont exactement les fonctions de la forme

Cr iephraogptry–Ceuqitame´htaMeirenieIng´Pro–steraM ean´esiroitcilsn te`r noF eacl´esectocoles`esedpsorpyatanyl

En sommant sur tous les x ,end´eduireque d ( f, x ∗ v ) = 2 n − 1 − 2 1 f ˜ ( v ) Re´sistanceline´aire .Onde´finitlar´esistanceline´airede f par ˜ RL ( f ) = 2 n − 1 − 1 2 v ∈{ m 0 a , 1 x } n  f ( v ) 

Montrer que, pour tout x ∈ { 0 , 1 } n , on a 1 − ( − 1) f ( x ) ⊕ ( x ∗ v ) =   0 2 s s i in f o ( n x ) = x ∗ v 

Re´sistancelin´eaire Exercice . Soit f unefonctionboole´ennesur { 0 , 1 } n et soit v ∈ { 0 , 1 } n . Montrer que d ( f, x ∗ v ) = 2 n − d ( f, ( x ∗ v ) ⊕ 1)

Exercice . Montrer que RL ( f ) est la distance minimale entre f et une fonctionboole´enneaffine.

e´nieria `ete R´esistancel colosea`lce´esrcysalanptotpresed rgotpyrC yrC eihpath´eieMaque–matiorI–etPrinregne´saM

Exercice .Montrerquelare´sistancelin´eaireestinvariantepar transformation affine ,c’est-`a-dire,sipour w ∈ { 0 , 1 } n , on pose g ( x ) = f ( x ⊕ w ) . Alors, on a RL ( g ) = RL ( f )

Soit f unfonctionbool´eennesur { 0 , 1 } n .

RL ( f ) ≤ 2 n − 1 − 2 n/ 2 − 1

Valeur optimale. Pour n pair, on a

Propri´et´esdelare´sistancelin´eaire

Fonction courbe . Pour n pair,unefonctionboole´enne f sur { 0 , 1 } n est dite courbe si on a

˜  f ( x )  = 2 pour tout x ∈ { 0 , 1 }

Pourunetellefonction,lar´esistancelin´eaireestmaximale.

/n2n etsaMng–IrorPieerni´eaMhte´amituq–erCyptographie Cryptlanadesyrpsecotoesolcl`ase´e`ecr esde´et´opri te Prleniatcnsesial´rreai´e

terPMas onscnctiesourbcurtsnoCofednoit ´ecl`aeste`ecrselasydeserptocolo tographie Cryptan e´htitam–euqpyrC–Iro´engerniMaie

1 Pour x 1 ∈ { 0 , 1 } m , on pose P ( x 1 ) = { y 1 ∈ { 0 , 1 } m tel que π ( y 1 ) = x 1 } . Montrer que f ˜ ( x ) = 2 m X ( − 1) g ( u 2 ) ⊕ ( x 2 ∗ u 2 ) ou` x = x 1 ∙ x 2 u 2 ∈ P ( x 1 ) 2 End´eduireque f est courbe si π est une permutation. 3 End´eduireque f n’est pas courbe si π n’est pas une permutation. 4 Construire une fonction courbe sur { 0 , 1 } 4 .

Soit m un entier positif. 1 Soient x 1 , x 2 , y 1 , y 2 ∈ { 0 , 1 } m . Montrer que ( x 1 ∙ x 2 ) ∗ ( y 1 ∙ y 2 ) = ( x 1 ∗ y 1 ) ⊕ ( x 2 ∗ y 2 ) 2 Soit g unefonctionbool´eennesur { 0 , 1 } m et π une FBV de { 0 , 1 } m dans { 0 , 1 } m .Onde´finitunefonctionbool´eenne f sur { 0 , 1 } 2 m en posant

Exercice. Construction de fonctions courbes

f ( x 1 ∙ x 2 ) = ( x 1 ∗ π ( x 2 )) ⊕ g ( x 2 ) ou` x 1 , x 2 ∈ { 0 , 1 }

m

RL ( F ) ≤ 2 n − 1 − 2 n/ 2 − 1 (pour n pair)

ou v ∗ F estlafonctionbool´eenned´efiniepar ( v ∗ F )( x ) = v ∗ f ( x ) . `

RL F min ( ) = v ∈{ 0 , 1 } m v 6 =0 ... 0

Re´sultat .Onalesproprie´t´essuivantes: ^ RL ( F ) = 2 n − 1 − 2 1 u ∈ m { 0 a , 1 x } n  ( v ∗ f )( u )  v ∈{ 0 , 1 } m \{ 0 ... 0 }

Exercice .Calculerlar´esistancevectorielledelaFBVsuivante F ( a, b, c ) =  ( a ∧ b ) ⊕ ¬ c, ( ¬ a ∧ b ) ∨ ( a ⊕ b ⊕ c ) 

Re´sistancelin´eairedesfonctionsboole´ennesvectorielles

RL ( v ∗ F )

D´efinition . Soit F une FBV de { 0 , 1 } n dans { 0 , 1 } m ,ond´efinitla re´sistancelin´eairede f par

ederiae´oitcnofs´eolbonsecsvneenleelotirs saetMrC–euqitame´htaMieerni´eng–IrorP serptoconalasyde hie Crypt yptograp cnatnile´R et sise se´e`ecresolcl`a