Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Master 1 M7 Cryptographie Examen partiel du 6 novembre 2007, corrigé. Exercice

Master 1 M7 Cryptographie Examen partiel du 6 novembre 2007, corrigé. Exercice 1 1. Sachant que le message a été chiﬀré par la méthode de Vigenère, en utilisant le mot-clef CRYPTO, quel est le message en clair obtenu en déchiﬀrant le cryptogramme suivant: R R P I B S N U C R K M R K M? p a r t i e l d e c r y p t o 2. Décrivez précisément la méthode que vous avez utilisée , en justiﬁant votre réponse à la question 1. Avec la table: Nous surlignons les 6 lignes C,R,Y,P,T,O. Nous savons que, pour chiﬀrer la première lettre du message en clair inconnu de nous, le chiﬀreur a parcouru la colonne correspondant à cette lettre, jusqu’ à la ligne C et qu’il a pris la lettre dans cette case ; c’était le R. Donc, pour retrouver la lettre inconnue, à partir du R et du C ( première lettre du mot- clef ), nous parcourons la ligne C, jusqu’au R, où nous remontons la colonne, ce qui nous donne la lettre p. Pour la deuxième lettre, il faut trouver cette fois l’intersection de la ligne R ( deuxième lettre du mot-clef ) avec une colonne inconnue qui donne la case R; évidemment, nous trouvons a. Pour la troisième lettre, la recherche de la colonne qui rencontre la ligne Y en P nous donne r. En utilisant successivement toutes les lettres du mot-clef et les 6 premières lettres du cryptogramme, nous trouvons ainsi les 6 premières lettres du message en clair : p a r t i e. Pour la septième lettre, nous reprenons la ligne C, correspondant à la première lettre du mot-clef, nous trouvons la case N, nous remontons la colonne, et nous en déduisons que la septième lettre du message en clair est l. Nous continuons ainsi, pour déchiﬀrer tout le message. En fait, nous pouvons trouver les trois dernières lettres sans calcul, par symétrie de la table. 3. Indiquez brièvement une méthode, sans (ou avec) l’aide de la Tabula Recta, diﬀérente de celle que vous avez utilisée, qui permettrait aussi de trouver la réponse à la question 1. Sans la table : Nous mettons en correspondance les 26 lettres de l’alphabet, de A à Z, avec les éléments de Z/26Z, notés de 0 à 25. Le mot-clef CRYPTO est une chaîne de caractères de longueur 6, qui correspond à la clef (2,17,24,15,19,14) dans (Z/26Z)6. Le texte en clair inconnu a été décomposé en blocs de messages de 6 caractères. Ainsi l’ensemble de déﬁnition de la clef, des messages en clair et des messages chiﬀrés est (Z/26Z)6. En notant e la fonction de chiﬀrement, le premier bloc (x1,x2,x3,x4,x5,x6) du message en clair a éte chiﬀré par e(x1,x2,x3,x4,x5,x6) = (x1 + 2,x2 + 17,x3 + 24,x4 + 15,x5 + 19,x6 + 14) = (y1,y2,y3,y4,y5,y6) = (17,17,15,8,1,18) dans (Z/26Z)6, ce qui a éte converti en chaîne de 6 caractères alphabétiques RRPIBS . Pour déchiﬀrer, nous eﬀectuons la démarche inverse: (1) convertir la chaîne de 6 caractères alphabétiques RRPIBS en un vecteur de (Z/26Z)6, (y1,y2,y3,y4,y5,y6) = (17,17,15,8,1,18) 1 (2) appliquer la fonction, notée d, de déchiﬀrement, déﬁnie par d(y1,y2,y3,y4,y5,y6) = (y1 −2,y2 −17,y3 −24,y4 −15,y5 −19,y6 −14) = (x1,x2,x3,x4,x5,x6), ce qui donne ici (x1,x2,x3,x4,x5,x6) = d(17,17,15,8,1,18) = (15,0,17,19,8,4) dans (Z/26Z)6. (3) convertir (x1,x2,x3,x4,x5,x6) = (15,0,17,19,8,4) en texte clair, ce qui donne: p a r t i e. Nous obtenons ainsi les 6 premières lettres du message en clair, puis nous reprenons l’étape (1), avec de nouvelles valeurs des yi. Exercice 2 On intercepte le message "RT?UMQT):L!!IBSS!!BIJE D" (il y a bien un espace entre E et D). On sait que ce message a été chiﬀré dans un alphabet de 36 lettres identiﬁées à A = 0, B = 1, C = 2,..., Z = 25, ! = 26, espace = 27, ′ = 28, ? = 29, . = 30, ; = 31, (= 32, ) = 33, := 34, ∗= 35, à l’aide d’une matrice 2×2, notée ξ, à coeﬃcients dans Z/36Z. Les blocs de deux lettres sont donc des vecteurs de (Z/36Z)2. On sait que les six dernières lettres du message chiﬀré correspondent à " itu.p" (il y a un espace au début), qui est la signature en clair de notre adversaire. Traduisez matriciellement ces informations et vériﬁez qu’on ne peut pas calculer la matrice ξ−1 de déchiﬀrement directement, mais, qu’en calculant ξ−1 modulo deux entiers bien choisis, on peut en déduire ξ−1 modulo 36 par le lemme chinois. Déchiﬀrez le message. Exercice 3 On note 0,1,2, les éléments du corps F3. Le polynôme Q = X3 + 2X2 + 1 est irréductible sur F3, ce qui nous permet d’identiﬁer le corps ﬁni F27au quotient (F3)[X]/(Q) de l’anneau de polynômes par l’idéal engendré par Q. On note x la classe de X dans ce quotient. On rappelle que F27 ≃F3[x] : tout élément de F27 s’écrit de manière unique comme un polynôme de degré inférieur ou égal à 2 en x et les multiplications dans ce corps se font modulo Q. Vous devez déchiﬀrer le message (K,H) (P,X) (N,K) (H,R) (T,F) (V,Y), où chaque couple de ce cryptogramme cache une lettre à trouver. Le message en clair a été chiﬀré en utilisant un chiﬀrement d’El Gamal sur le corps ﬁni F27, votre clef secrète de déchiﬀrement est l’entier a = 11, la clef publique de chiﬀrement est (x+2) et les 26 lettres de l’alphabet sont en correspondance avec les 26 éléments non nuls du corps, de la manière suivante: A = 1 B = 2 C = x D = x + 1 E = x + 2 F = 2x G = 2x + 1 H = 2x + 2 I = x2 J = x2 + 1 K = x2 + 2 L = x2 + x M = x2 + x + 1 N = x2 + x + 2 O = x2 + 2x P = x2 + 2x + 1 Q = x2 + 2x + 2 R = 2x2 S = 2x2 + 1 T = 2x2 + 2 U = 2x2 + x V = 2x2 + x + 1 W = 2x2 + x + 2 X = 2x2 + 2x Y = 2x2 + 2x + 1 Z = 2x2 + 2x + 2 1. Vériﬁer rapidement que x11 = x + 2. Calculons x3 = −2x2−1 = x2+2, x4 = x3+2x = x2+2x+2, x5 = x3x2 = x4+2x2 = 2x+2, d’où x11 = xx10 = x(x5)2 = x(x2 + 2x + 1) = x3 + 2x2 + x = x + 2. 2 2. Exprimer x12 et x13 comme des polynômes de degré inférieur ou égal à 2 en x. En déduire que x engendre le groupe multiplicatif F∗ 27. F∗ 27 est un groupe multiplicatif cyclique d’ordre 26, l’ordre de x est 1,13 ou 26. Calculons x12 = xx11 = x2 + 2x et x13 = x3 + 2x2 = 2, donc x est d’ordre 26. 3. Expliquer pourquoi, pour trouver l’inverse de (x2 + 2)11, on peut calculer (x2 + 2)15. Parce que 26 est l’ordre du groupe, donc l’ordre de x2 + 2 divise 26 et 15 = 26 −11, donc (x2 + 2)15 = (x2 + 2)26(x2 + 2)−11 = (x2 + 2)−11. 4. Vériﬁer, à l’aide de calculs déjà eﬀectués, que (2x + 2)(x2 + 2)15 = 2x + 1. D’après les calculs précédents, (2x + 2)(x2 + 2)15 = x5(x3)15 = x50 = x24 = (x12)2 = (x2 + 2x)2 = x4 + x3 + x2 = 2x + 1. 5. Décrire le système de chiﬀrement d’El Gamal et le déchiﬀrement que vous devez appliquer, pour justiﬁer que la première lettre du message en clair cherché est un g. D’après les hypothèses, notre clef secrète est l’entier a = 11, et nous avons publié la clef publique de chiﬀrement (x + 2). D’après la question 1), x11 = x + 2, donc, d’après la question 2), notre clef publique est bien de la forme xa, avec x un générateur de F∗ 27. Nous savons que le couple (K,H) correspond à (x2 + 2,2x + 2) = (xk,(Claire)(xa)k), où (Claire) désigne la lettre en clair, masquée par le chiﬀrement d’El Gamal. Pour enlever le masque, nous utlisons notre clef secrète, en multipliant le deuxième terme par le premier terme élevé à la puissance (−a), ou mieux, d’après la question 3), élevé à la puissance 15. Ici, le calcul a déjà été fait question 4), donc (Claire) = 2x + 1, ce qui correspond à la lettre g. 6. Sachant de plus que x14 = 2x, x16 = 2x2 + 1, x19 = x2 + x, x21 = 2x2 + 2x + 1, déchiﬀrer les cinq lettres suivantes et donner le mot de six lettres que vous avez trouvé. (P,X) correspond à (x2 + 2x + 1,2x2 + 2x) = (x10,x6), donc, ici, (Claire) = x6(x10)15 = x156 = (x26)6 = 1, ce qui donne uploads/Litterature/ m7-part-nov-07-corex-1-amp-3.pdf