Université Grenoble I Cours Mat4216 M1 Année

Laurent Fousse

Description

Niveau: Supérieur, Master, Bac+4
Université Grenoble I Cours Mat4216 M1 Année 2008/2009 Introduction à la cryptologie Examen du 4 septembre 2009, de 14h à 17h, durée 3h. Documents et calculatrices interdits. Rédigez les deux parties sur des feuilles séparées. Justifiez vos réponses — brièvement mais suffisamment. Ce sujet comporte 4 pages. Les paragraphes sont indépendants. Première partie — cours de Laurent Fousse 1. CHIFFREMENT PAR BLOC À LA FEISTEL On considère une fonction F de chiffrement par bloc constituée de 16 fois le tour suivant : L 0 R 0 L 1 R 1 f k où fk est une fonction dépendant de la sous-clef secrète de ronde Sk et du numéro de tour k, et les demi-blocs d'entrée L0, R0 et de sortie L1, R1 ont pour longueur n bits. 1.1. Écrire les sorties L1 et R1 en fonction des entrées L0, R0 et de la fonction fk. 1.2. Montrer comment inverser un tel tour, sans hypothèse sur la fonction fk. Dessiner le diagramme correspondant au déchiffrement. 1.3. En supposant que n = 3, calculer tous les chiffrés possibles pour (L0,R0) = (000,111). 1.4. En supposant que n= 5, le chiffré de (00000,01010) peut-il être (11111,00000) ? 1.5.

• chiffrement par bloc


• ronde


• propriétés de diffusion du chiffrement


• x2 modulo


• polynôme x2


• ronde du déchiffrement


• corps fini


• bloc

Sujets

• Chiffrement par bloc
• Corps fini

Informations

• Publié par: profil-thowyeng-2012
• Publié le: 01 septembre 2009
• Nombre de lectures: 39
• Langue: Français

Extrait

Universit Grenoble I

Cours Mat4216 M1

Anne 2008/2009

Introduction À la cryptologie Examen du 4 septembre 2009, de 14h á 17h, dure 3h.

Documents et calculatrices interdits. RÉdigez les deux parties sur des feuilles sÉparÉes. Justifiez vos rÉponses — briÈvement mais suffisamment. Ce sujet comporte 4 pages. Les paragraphes sont indÉpendants.

PremiÈre partie — cours de Laurent Fousse

1. C HIFFREMENT PAR BLOC â LA F EISTEL On considre une fonctionFde chiffrement par bloc constitue de 16 fois le tour suivant :

oÙf k est une fonction dpendant de la sous-clef secrte de rondeS k et du numro de tour k, et les demi-blocs d’entreL 0 ,R 0 et de sortieL 1 ,R 1 ont pour longueurnbits.

1.1.Ècrire les sortiesL 1 etR 1 en fonction des entresL 0 ,R 0 et de la fonctionf k .

1.2.Montrer comment inverser un tel tour, sans hypothse sur la fonctionf k . Dessiner le diagramme correspondant au dchiffrement.

1.3.En supposant quen=3, calculer tous les chiffrs possibles pour(L 0 ,R 0 ) = (000,111).

1.4.En supposant quen=5, le chiffr de(00000,01010)peut-il tre(11111,00000)?

1.5.En dduire une attaque á clairs et chiffrs connus permettant de distinguer la fonctionFde chiffrement (utilisant 16 tours) d’une fonction alatoire.

page 1/4

Universit Grenoble I

Cours Mat4216 M1

Anne 2008/2009

2. H ACHAGE On considre la fonctionhsuivante : 128 32 h:{0,1{} →0,1} x 1 ||x 2 ||x 3 ||x 4 7→x 1 ⊕g(x 2 ||g(x 3 ||x 4 )) |x 1 |=|x 2 |=|x 3 |=|x 4 |=32 64 32 oÙx||yreprsente la concatnation des blocsxety, etg:{0,1{} →0,1}est une fonction de compression rsistant aux collisions au sens fort (c’est-á-dire qu’il est calcu- 0 00 0 latoirement difficile de trouverx 1 ||x 2 etx||xdistinctstels queg(x 1 ||x 2 ) =g(x||x)). 1 21 2 2.1.La fonctionhest-elle une fonction de hachage ou une fonction de compression? 2.2.Ètant donn un messagex=x 1 ||x 2 ||x 3 ||x 4 , est-il facile de trouver un message 0 00 0 00 x=x||x||x||x6=xtel queh(x) =h(x)? 1 2 3 4 2.3.Est-il facile d’inverser la fonctionh? Si oui, proposer un algorithme qui calcule un messagexpour une entreyavech(x) =y. 3. C HIFFREMENT PAR BLOC â LA AES On considre le chiffrement par bloc «NonAES» oprant sur des blocs de 9 bits (l’tat) que l’on dispose en un carr de 3 sur 3 : a 00 a 01 a 02 a 10 a 11 a 12 a 20 a 21 a 22 Les oprations d’une ronde sont les suivantes : –ShiftRows: la deuxime ligne est dcale cycliquement d’une position vers la droite, et la troisime ligne d’une position vers la gauche. –MixColumns: chaque colonne est vue comme un polynme de degr 2 dansF 2 , les 2 3 coefficients faibles á forts de haut en bas, et multipli parXmoduloX+X+1. Le polynme obtenu est crit dans la colonne correspondante. –AddRoundKey: la clef de ronde, de taille 9 bits, est ajout case par case. 3.1.On choisit comme message clairm= (001010100)et comme clef de rondek= (110001011). Calculer le bloc chiffr correspondant aprs une ronde (on lit le tableau ligne par ligne, de gauche á droite). 3.2.Montrer qu’il est possible de dchiffrer en connaissant la clef, et dcrire une ronde du dchiffrement. 3.3.On essaie de mesurer les proprits de diffusion du chiffrement. Pour cela on simule le chiffrement de deux messages, avec la mme clef, ne diffrant que du premier bit. â partir de combien de rondes compltes est-ce que la diffrence initiale se sera potentiellement propage á tout l’tat? Dtailler. 3.4.Par rapport au vrai AES, et en plus de calculer dans un corps plus petit et sur un tat de seulement 3 sur 3 lments, le chiffrement NonAES n’a pas d’opration SubBytes. Quelle vulnrabilit ce manque introduit-il, et comment l’exploiter sur AES ?

page 2/4

Universit Grenoble I

Cours Mat4216 M1

Seconde partie — cours de Michael Eisermann

Anne 2008/2009

2 4. R ACINES DE X+1 2 Rappelons que le polynmeX+1 est irrductible surRalors que surCil se dcom- 2 2 pose enX+1= (X−i)(X+i)oÙi=−1. L’objectif de cet exercice est d’tudier la 2 dcomposition deX+1 sur un corps finiF q á lments. 2 4.1.DcomposerX+1 en facteurs irrductibles dansF 2 [X]. × 4.2.Ènoncer l’ordre et la structure du groupeF. q 2 4.3.Supposons qu’il existex∈F q tel quex+1=0. × Quel est l’ordre dexdans le groupeF? q Que conclure pour la valeur deqmodulo 4 ? Ènoncer avec prcision le thorme qui sert ici. 2 4.4.Rciproquement, sous quelle condition surqmodulo 4 le polynmeX+1 admet- il une racine dansF q ?? Justifiez votre rponse. Quel rsultat sert ici 2 Pour conclure, expliciter (tant que possible) la dcomposition deX+1 en facteurs irrductibles dansF q [X]en fonction deq.

5. I SOMORPHISMES ENTRE CORPS FINIS 5.1.Ènoncer (avec prcision mais sans preuve) la classification des corps finis. Dans la suite on travaille sur le corpsF 7 =Z/7Zá 7 lments. 5.2.Les anneaux quotients 2 2 F=F 7 [X]/(X+1)etG=F 7 [X]/(X−1) sont-ils isomorphes ? Justifiez votre rponse. 5.3.Les anneaux quotients 2 2 E=F 7 [X]/(X+X−1)etF=F 7 [X]/(X+1) sont-ils isomorphes ? Justifiez votre rponse. Soitxl’image deXdans le quotientEet soity=ax+boÙa,b∈F 7 . 2 5.4.DansEcalculerysous la formecx+doÙc,d∈F 7 . 2 5.5.Trouvera,b∈F 7 de sorte quey=−1 dansE. 5.6.?En quoi ce calcul permet-il d’expliciter la rponse á la question 5.3

page 3/4

Universit Grenoble I

Cours Mat4216 M1

Anne 2008/2009

6. C ORPS FINIS ET POLYNMES IRRÈDUCTIBLES Soitp≥2 un nombre premier et soitF p =Z/pZle corps áplments. n p 6.1.Ènoncer (sans preuve) la dcomposition du polynmeX−X, oÙn∈N, en facteurs irrductibles unitaires dansF p [X]. 6.2.En dduire une formule rcursive pour le nombrea n des polynmes unitaires irrductibles de degrnsurF p . 6.3.Quel est le comportement asymptotique dea n pourn→∞? (sans preuve)

L’algorithme suivant n’est pas correct :

Algorithme 1Tester l’irrductibilit deP∈F p [X] EntrÉe:un polynmeP∈F p [X]de degrn≥2. Sortie:« irrductible » siPest irrductible, « compos » sinon. pourkde1Ànfaire k p Q←X−X R←pgcd(P,Q) siR6=1alors retourner« compos »fin si fin pour retourner« irrductible »

6.4.Expliciter un exemple oÙ cet algorithme donne la mauvaise rponse. 6.5.Rectifier (lgrement) la mthode pour qu’elle donne toujours la bonne rponse. Justifier ensuite la validit de votre algorithme rectifi. 6.6.Telle qu’elle est crite, la mthode est inefficace. Expliquer pourquoi. 6.7.Amliorer la mthode pour qu’elle soit efficace (tout en restant correcte).

Fin.

page 4/4