Master Pro Ingenierie Mathematique Cryptographie

Publié par

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


Publié le : vendredi 8 juin 2012
Lecture(s) : 49
Source : math.univ-lyon1.fr
Nombre de pages : 16
Voir plus Voir moins
MasterProIng´einreeiaMhte´amitequypCrgrtohiapyrCenatpsylasedeocolprotcl´ees`ae`etesrc
CHAPITRE 5.
CRYPTANALYSE DES PROTOCOLES ` ´ ` A CLE SECRETE
http://math.univ-lyon1.fr/~roblot/masterpro.html
rProasteMhtaMeireine´gnItoypCrequtima´edesyrpsecotoseloapgreChiptryalanfnsuoiendtisuoi`acl´esecr`eteCon
Confusion .Cestlefaitquelame´thodedecalculdumessagecrypt´ea` partirdumessageclairdoitˆetresusammentcomplexe.Cest-`a-dire qu’il ne doit pas exister de relation simples entre les bits du message clair etlesbitsdumessagecrypt´e.
Enthe´oriedelinformation, Shannon de´nitdeuxnotionsquetoutbon cryptosyst`emedoitposse´der:la confusion et la diffusion .
Diffusion .Cestlefaitquunedie´rence,mˆememinime,entredeux messagesclairsdoitentraınerunetr`esgrandedie´renceentreles ˆ messagescrypte´s.Ainsi,chaquebitdumessageclairdoitcontribuerau calculdechaquebitdumessagecrypt´e.
Confusion et diffusion
rotocolelysedespce`rteCe`sca´lsedietsiufuononsino
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´evisiblequandonmodielentre´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
CryptanaographieeuCyrtp´hmetaqiriieateMInoeng´tsaMrPre
Eneet,unerelationlin´eairenepeutpasˆetrevraiepour tous les messages w sinon le protocole a une faiblesse.
Exercice . Montrer que le protocole de Vigen`ere est lineaire. ´
Cestuneattaque`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 entrelesbitsdentr´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.Lattaquantcherchea`retrouver(delinformationsur)lacle´. ´
MsaetPraerieypCrnataselyn´lia`see´lcrcesete`edesalysocolprotpaihotrgtpnaCeyrtima´ethypCreque´gnIoraMeirein
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´eairesetanes.
D´enition .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
CriephraogptryCeuqitame´htaMeirenieIng´ProsteraMean´esiroitcilsnte`rnoFeacl´esectocoles`esedpsorpyatanyl
En sommant sur tous les x ,end´eduireque d ( f, x v ) = 2 n 1 21 f ˜( v ) Re´sistanceline´aire .Onde´nitlar´esistanceline´airede f par ˜ RL ( f ) = 2 n 1 12 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 ) = 02 ssiin 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´enneane.
e´nieria`eteR´esistancelcolosea`lce´esrcysalanptotpresedrgotpyrCyrCeihpath´eieMaquematiorIetPrinregne´saM
Exercice .Montrerquelare´sistancelin´eaireestinvariantepar transformation affine ,cest-`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.
/n2netsaMngIrorPieerni´eaMhte´amituqerCyptographieCryptlanadesyrpsecotoesolcl`ase´e`ecresde´et´opritePrleniatcnsesial´rreai´e
terPMasonscnctiesourbcurtsnoCofednoit´ecl`aeste`ecrselasydeserptocolotographieCryptane´htitameuqpyrCIro´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´nitunefonctionbool´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´eniepar ( 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 21 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´enition . Soit F une FBV de { 0 , 1 } n dans { 0 , 1 } m ,ond´enitla re´sistancelin´eairede f par
ederiae´oitcnofs´eolbonsecsvneenleelotirssaetMrCeuqitame´htaMieerni´engIrorPserptoconalasydehieCryptyptograpcnatnile´Retsisese´e`ecresolcl`a
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.