Exercices td cryptographie classique decalage attaque freque
Télécharger PDFCryptographie classique Série 2
Exercice 1
Décalage : Le système le plus ancien est attribué à Jules César. Il consiste en un décalage de l’alphabet (dans le système original, A était remplacé par C, B par D, C par E, …). Voici un texte chiffré obtenu en utilisant la clé L :
FYPYQ LYELO TEUPD LTDOP DAZPX PDFYP YQLYE LOTEY ZYDLT DOPDA ZPDTP D
Retrouver le texte clair.
Solution :
Fonction de chiffrement : y = x + k mod 26
Fonction de déchiffrement : x = y - k mod 26
A : 0, B : 1, C : 2, D : 3, E : 4, F : 5, G : 6, H : 7, I : 8, J : 9, K : 10, L : 11, M : 12, N : 13, O : 14, P : 15, Q : 16, R : 17, S : 18, T : 19, U : 20, V : 21, W : 22, X : 23, Y : 24, Z : 25
F : 5, Y : 24, P : 15, Y : 24, Q : 16, L : 11, Y : 24, E : 4, L : 11, O : 14, T : 19, E : 4, U : 20, P : 15, D : 3, L : 11, T : 19, D : 3, O : 14, P : 15, D : 3, A : 0, Z : 25, P : 15, X : 23, P : 15, D : 3, F : 5, Y : 24, P : 15, Y : 24, Q : 16, L : 11, Y : 24, E : 4, L : 11, O : 14, T : 19, E : 4, Y : 24, Z : 25, Y : 24, D : 3, L : 11, T : 19, D : 3, O : 14, P : 15, D : 3
Solution :
Voici un autre texte chiffré ; on ne connaît pas ici la clé utilisée.
SLUUL TPLZA ZBWWV ZLHCV PYAVB ALXBP WLTLU AZWLJ PHSUL JLZZH PYLWV BYPUA LYJLW ALYSL ZZPNU HBEAY HUZTP Z
Retrouver le texte clair.
Exercice 2
On identifie les lettres avec les entiers A = 0, B = 1, …, Z = 25.
On définit une multiplication * sur les entiers de la manière suivante : pour calculer le produit de deux lettres, on transforme les lettres en entiers, on multiplie ces deux entiers et on réduit le résultat modulo 26, puis on le retransforme en une lettre.
Par exemple, pour le produit de G et Y, on a G = 6 et Y = 24 et 6 * 24 mod 26 = 14, donc G*Y = O.
Le cryptogramme de César multiplicatif consiste à multiplier toutes les lettres du message par une lettre fixée qui sert de clé.
1. Coder en utilisant le cryptogramme de César multiplicatif le message « QUI » avec la clé N. 2. En déduire que certaines clés donnent des messages chiffrés non déchiffrables. Déterminer toutes ces mauvaises clés. 3. Coder le message ci-dessus avec la deuxième clé valide permettant un déchiffrement.
Solution :
1. Coder le message QUI avec f(x) = x * k mod 26 Q (16) donc f(16) = 16 * 13 mod 26 = 0 → A U (20) donc f(20) = 20 * 13 mod 26 = 0 → A I (8) donc f(8) = 8 * 13 mod 26 = 0 → A On déduit que certaines clés K donnent des messages indéchiffrables.
La clé k est une mauvaise clé si PGCD(k, 26) ≠ 1 ou k = 0.
2. La deuxième clé valide est D (3). Q (16) donc f(16) = 16 * 3 mod 26 = 22 → W U (20) donc f(20) = 20 * 3 mod 26 = 8 → I I (8) donc f(8) = 8 * 3 mod 26 = 24 → Y Le message chiffré est WIY.
Exercice 3
Le message suivant, chiffré à l’aide d’un chiffrement affine, est intercepté :
PVQNK DQXXU DRUVZ EXKUN VLLXZ QIVRP FZRPX CXQSG DRXZG XKXHD KSDSX PMDIR GGXKG XQCDQ USRPD QUNVL LXRGX PUIGD QNDAA KVNMX YSVQN GDGDL AXSRX ZPXPA DZEKX PNMXE XZOPV QUNVG GXPPZ KPDUX LAXXU FZDQS NXCZU CRQRG XAKRU PZKPX PHXQV ZO
Trouver la clé de déchiffrement.
Solution :
Chiffrement affine (linéaire) : Y = a * x + b mod 26
(a, b) est la clé de chiffrement.
Fonction de déchiffrement : x = a’ * y + b’ mod 26, où a’ et b’ sont déterminés par :
a * a’ ≡ 1 mod 26 (a’ = a⁻¹)
b’ ≡ -a’ * b mod 26
Première supposition : La lettre X apparaît 28 fois.
E → X : 4 = 23 * a’ + b’ mod 26
S → P : 18 = 15 * a’ + b’ mod 26
Solution :
Deuxième supposition : La lettre X apparaît 29 fois.
E → X : 4 = 23 * a’ + b’ mod 26
A → D : 0 = 3 * a’ + b’ mod 26
Résoudre le système d’équations :
4 = 20 * a’ → 5 * a’ ≡ 1 mod 26 → a’ ≡ 5⁻¹ ≡ 21 mod 26
b’ ≡ -3 * 21 ≡ -63 ≡ 15 mod 26
Donc (a’, b’) = (21, 15) est la clé de déchiffrement.
Fonction de déchiffrement : x = 21 * y + 15 mod 26.
Exercice 4
Chiffrement de Vigenère :
1. Chiffrer avec la clé « crypto » le message « texte secret à décoder ». 2. Pour le même texte en clair, on obtient le message chiffré suivant « BRQKSMZCSPXIQXTCXZR ». Quelle est la clé utilisée ? 3. Même question que (2.) si le message chiffré est « AAABBBCCCDDDEEEFFFG ». Comment appelle-t-on ce chiffrement ?
Solution :
1. Fonction de chiffrement : y = x + k mod 26 La clé : CRYPTO → 2, 17, 24, 15, 19, 14 Message clair : texte secret à décoder → 19, 4, 23, 5, 18, 18, 18, 18, 13, 0, 4, 20, 14, 4, 18 Message chiffré : VVVIXH GTPTMO GMZDWS T
Solution :
2. Message chiffré : BRQKSMZCSPXIQXTCXZR Fonction de déchiffrement : k = y - x mod 26 Message clair : texte secret à décoder → 19, 4, 23, 5, 18, 18, 18, 18, 13, 0, 4, 20, 14, 4, 18 Clé : INTROUVABLE
Solution :
3. Message chiffré : AAABBBCCCDDDEEEFFFG Clé : HWDIXJYALZKDBACR Ce chiffrement est appelé un chiffrement à flot.
Exercice 5
Chiffrement de Hill :
1. Quelle est la formule donnant la matrice inverse lorsque m = 2 ? 2. Calculer la matrice inverse de A = 5 1 12 3. 3. Décrire une méthode permettant d’attaquer le chiffrement de Hill. 4. Application : on dispose des couples ((2, 9), (11, 11)) et ((7, 3), (11, 23)).
Solution :
1. Chiffrement : y = x * K mod 26, K est la clé de chiffrement. Déchiffrement : x = y * K⁻¹ mod 26. Pour m = 2, K⁻¹ = (ad - bc)⁻¹ * [d -b; -c a] mod 26.
Solution :
2. A = 5 1 12 3 A⁻¹ = (3 * 3 - 1 * 12)⁻¹ * [3 -1; -12 5] = (9 - 12)⁻¹ * [3 -1; -12 5] = (-3)⁻¹ * [3 -1; -12 5]. PGCD(-3, 26) = 1, donc -3⁻¹ ≡ 9 mod 26. A⁻¹ = 9 * [3 -1; -12 5] ≡ [1 -9; -4 19] mod 26.
Solution :
3. Pour attaquer le chiffrement de Hill, on utilise des couples (x, y) pour trouver K⁻¹, puis K.
Solution :
4. Application : K⁻¹ = [1 -9; -4 19] mod 26. K = K⁻¹⁻¹ ≡ [8 14; 11 25] mod 26.
Exercice 6
Transposition :
Chiffrer le texte clair « she sells seashells by the seashore » en utilisant la clé 1 2 3 3 5 1 4 5 6 6 4 2.
Puis déchiffrer le message suivant chiffré avec la clé précédente :
CELPLA LQUUIB ETEARS IFCRFH UMEENR AESEGS LINRAC
Solution :
Message clair : shesellsseashellsbytheseashore → 4 5 6 6 4 2
Message chiffré : eelslshsasbhllseetnse
Solution :
Message chiffré : CELPLA LQUUIB ETEARS IFCRFH UMEENR AESEGS LINRAC
Message en clair : LA CLE PUBLIQUE SERT A CHIFFRER UN MESSAGE EN CLAIR
Exercice 7
Transposition : Voici un exemple de procédé de chiffrement.
Soient m, n des entiers strictement positifs. On écrit un message clair ligne par ligne dans un tableau rectangulaire m × n (m lignes et n colonnes). Le texte chiffré est formé des colonnes du tableau.
Par exemple, si m = 3 et n = 4, si l’on chiffre le texte clair « illustration », on a :
I L L U
S T R A
T I O N
Le texte chiffré est alors « ISTLTILROUAN ».
1. Quelle est la clé utilisée dans ce procédé ? 2. Chiffrer le texte « une fonction de chiffrement » en écrivant le message sur 4 lignes et 6 colonnes (éliminer les espaces). 3. Décrire comment peut-on déchiffrer le texte (en ayant la clé). 4. Décrypter le texte chiffré suivant (où l’on a éliminé les espaces et les apostrophes) : « LPTRESDGTCEEEELNMSAT ». 5. Remarquer que si m × n = 25, on trouvera directement le message clair. Déchiffrer donc le message « CNSERHPOUTAOIPOCUDOUURIUS ».
Solution :
1. La clé utilisée dans ce procédé est (n, m) ou n, le nombre de colonnes. 2. Chiffrement : « unefonctiondechiffrement » → 4 lignes, 6 colonnes. Message chiffré : U C E R N T C E E I H M F O I E O N F N D T
Solution :
3. La méthode de déchiffrement consiste à écrire le message chiffré en colonnes (respectant le nombre de lignes) et à le lire par ligne. 4. Décryptage du message chiffré « LPTRESDGTCEEEELNMSAT » avec n = 5, m = 4 : L E T E M P S C E S T D E L A R G E N T Le message en clair est « Le temps c’est de l’argent ».
Solution :
5. Le message « CNSERHPOUTAOIPOCUDOUURIUS » est déchiffré avec m = n = 5 : C H A C U N P O U R S O I D I E U P O U R T O U S Le message en clair est « CHACUN POUR SOI DÉPENSE UNE POUCHE D’ARGENT ».
FAQ
1. Comment fonctionne le chiffrement affine ? Il utilise une fonction linéaire de la forme Y = a * x + b mod 26 pour chiffrer les lettres.
2. Qu’est-ce qu’une mauvaise clé dans le cryptogramme de César multiplicatif ? Une clé k est mauvaise si PGCD(k, 26) ≠ 1 ou si k = 0.
3. Pourquoi le chiffrement de Hill est-il plus sécurisé que le décalage de César ? Le chiffrement de Hill utilise une matrice pour transformer plusieurs lettres à la fois, ce qui rend le déchiffrement plus complexe sans la clé.