Université Grenoble I Cours Mat4216 M1 Année
4
pages
Français
Documents
2009
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
4
pages
Français
Documents
2009
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
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.
Voir
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
Universit Grenoble I
Cours Mat4216 M1
Anne 2008/2009
Introduction À la cryptologie Examen du 4 septembre 2009, de 14h á 17h, dure 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 â LAFEISTEL On considre une fonctionFde chiffrement par bloc constitue de 16 fois le tour suivant :
oÙfkest une fonction dpendant de la sous-clef secrte de rondeSket du numro de tour k, et les demi-blocs d’entreL0,R0et de sortieL1,R1ont pour longueurnbits.
1.1.Ècrire les sortiesL1etR1en fonction des entresL0,R0et de la fonctionfk.
1.2.Montrer comment inverser un tel tour, sans hypothse sur la fonctionfk. Dessiner le diagramme correspondant au dchiffrement.
1.3.En supposant quen=3, calculer tous les chiffrs possibles pour(L0,R0) = (000,111).
1.4.En supposant quen=5, le chiffr de(00000,01010)peut-il tre(11111,00000)?
1.5.En dduire une attaque á clairs et chiffrs connus permettant de distinguer la fonctionFde chiffrement (utilisant 16 tours) d’une fonction alatoire.
page 1/4
Universit Grenoble I
Cours Mat4216 M1
Anne 2008/2009
2. HACHAGE On considre la fonctionhsuivante : 128 32 h:{0,1{} →0,1} x1||x2||x3||x47→x1⊕g(x2||g(x3||x4)) |x1|=|x2|=|x3|=|x4|=32 64 32 oÙx||yreprsente la concatnation des blocsxety, etg:{0,1{} →0,1}est une fonction de compression rsistant aux collisions au sens fort (c’est-á-dire qu’il est calcu-0 00 0 latoirement difficile de trouverx1||x2etx||xdistinctstels queg(x1||x2) =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=x1||x2||x3||x4, 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 entreyavech(x) =y. 3. CHIFFREMENT PAR BLOC â LAAES On considre le chiffrement par bloc «NonAES» oprant sur des blocs de 9 bits (l’tat) que l’on dispose en un carr de 3 sur 3 : a00a01a02 a10a11a12 a20a21a22 Les oprations d’une ronde sont les suivantes : –ShiftRows: la deuxime ligne est dcale cycliquement d’une position vers la droite, et la troisime ligne d’une position vers la gauche. –MixColumns: chaque colonne est vue comme un polynme de degr 2 dansF2, les 2 3 coefficients faibles á forts de haut en bas, et multipli parXmoduloX+X+1. Le polynme 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 aprs une ronde (on lit le tableau ligne par ligne, de gauche á droite). 3.2.Montrer qu’il est possible de dchiffrer en connaissant la clef, et dcrire une ronde du dchiffrement. 3.3.On essaie de mesurer les proprits de diffusion du chiffrement. Pour cela on simule le chiffrement de deux messages, avec la mme clef, ne diffrant que du premier bit. â partir de combien de rondes compltes est-ce que la diffrence initiale se sera potentiellement propage á tout l’tat? Dtailler. 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 lments, le chiffrement NonAES n’a pas d’opration SubBytes. Quelle vulnrabilit 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
Anne 2008/2009
2 4. RACINES DEX+1 2 Rappelons que le polynmeX+1 est irrductible surRalors que surCil se dcom-2 2 pose enX+1= (X−i)(X+i)oÙi=−1. L’objectif de cet exercice est d’tudier la 2 dcomposition deX+1 sur un corps finiFqá lments. 2 4.1.DcomposerX+1 en facteurs irrductibles dansF2[X]. × 4.2.Ènoncer l’ordre et la structure du groupeF. q 2 4.3.Supposons qu’il existex∈Fqtel quex+1=0. × Quel est l’ordre dexdans le groupeF? q Que conclure pour la valeur deqmodulo 4 ? Ènoncer avec prcision le thorme qui sert ici. 2 4.4.Rciproquement, sous quelle condition surqmodulo 4 le polynmeX+1 admet-il une racine dansFq?? Justifiez votre rponse. Quel rsultat sert ici 2 Pour conclure, expliciter (tant que possible) la dcomposition deX+1 en facteurs irrductibles dansFq[X]en fonction deq.
5. ISOMORPHISMES ENTRE CORPS FINIS 5.1.Ènoncer (avec prcision mais sans preuve) la classification des corps finis. Dans la suite on travaille sur le corpsF7=Z/7Zá 7 lments. 5.2.Les anneaux quotients 2 2 F=F7[X]/(X+1)etG=F7[X]/(X−1) sont-ils isomorphes ? Justifiez votre rponse. 5.3.Les anneaux quotients 2 2 E=F7[X]/(X+X−1)etF=F7[X]/(X+1) sont-ils isomorphes ? Justifiez votre rponse. Soitxl’image deXdans le quotientEet soity=ax+boÙa,b∈F7. 2 5.4.DansEcalculerysous la formecx+doÙc,d∈F7. 2 5.5.Trouvera,b∈F7de sorte quey=−1 dansE. 5.6.?En quoi ce calcul permet-il d’expliciter la rponse á la question 5.3
page 3/4
Universit Grenoble I
Cours Mat4216 M1
Anne 2008/2009
6. CORPS FINIS ET POLYNMES IRRÈDUCTIBLES Soitp≥2 un nombre premier et soitFp=Z/pZle corps áplments. n p 6.1.Ènoncer (sans preuve) la dcomposition du polynmeX−X, oÙn∈N, en facteurs irrductibles unitaires dansFp[X]. 6.2.En dduire une formule rcursive pour le nombreandes polynmes unitaires irrductibles de degrnsurFp. 6.3.Quel est le comportement asymptotique deanpourn→∞? (sans preuve)
L’algorithme suivant n’est pas correct :
Algorithme 1Tester l’irrductibilit deP∈Fp[X] EntrÉe:un polynmeP∈Fp[X]de degrn≥2. Sortie:« irrductible » siPest irrductible, « compos » sinon. pourkde1Ànfaire k p Q←X−X R←pgcd(P,Q) siR6=1alors retourner« compos »fin si fin pour retourner« irrductible »
6.4.Expliciter un exemple oÙ cet algorithme donne la mauvaise rponse. 6.5.Rectifier (lgrement) la mthode pour qu’elle donne toujours la bonne rponse. Justifier ensuite la validit de votre algorithme rectifi. 6.6.Telle qu’elle est crite, la mthode est inefficace. Expliquer pourquoi. 6.7.Amliorer la mthode pour qu’elle soit efficace (tout en restant correcte).
Fin.
page 4/4
