Cryptographie et sécurité informatique

Ce laboratoire propose une introduction pratique à plusieurs méthodes fondamentales de cryptographie, notamment le chiffre de Hill, l'algorithme RSA, l'analyse de fréquence, le chiffre de Vigenère, la fonction de Feistel et le mode de chiffrement PCBC. Il permet de comprendre les principes mathématiques sous-jacents, d'appliquer les algorithmes de chiffrement et de déchiffrement, ainsi que d'analyser la sécurité de ces méthodes. Pour réaliser ce TP, il est nécessaire de maîtriser les notions de base en algèbre, arithmétique modulaire et statistiques, ainsi que d'avoir accès à un environnement de calcul ou un papier-crayon pour les calculs manuels.

Objectifs

• Coder et décoder un message avec le chiffre de Hill.
• Comprendre et appliquer les formules de l'algorithme RSA.
• Réaliser une analyse de fréquence pour décrypter un texte chiffré.
• Utiliser le chiffre de Vigenère pour chiffrer et déchiffrer un message.
• Exprimer et comprendre la fonction de Feistel et son utilisation dans DES.
• Comprendre le mode de chiffrement Plain and Cipher Block Chaining (PCBC) et ses effets.

Prérequis et installation

• Connaissances en arithmétique modulaire, matrices, et statistiques de fréquence.
• Notions de base sur les algorithmes de chiffrement symétrique et asymétrique.
• Accès à un outil de calcul (calculatrice, logiciel de calcul matriciel ou programmation simple).
• Familiarité avec la notation et les opérations sur les entiers modulo 26.

Chiffre de Hill (Exercice 1)

Le chiffre de Hill permet de chiffrer un message en groupes de m lettres simultanément, ici m=2. Chaque lettre est convertie en nombre selon sa position dans l'alphabet (A=0, B=1, ..., Z=25). Le message est découpé en blocs de 2 lettres, puis chaque bloc est transformé par une matrice 2x2 de coefficients entiers (a=3, b=5, c=1, d=2) via des combinaisons linéaires.

Procédure :

1. Diviser le mot "chiffrer" en blocs de 2 lettres : "ch", "if", "fr", "er".
2. Convertir chaque lettre en nombre : c=2, h=7, i=8, f=5, r=17, e=4.
3. Pour chaque bloc x = (x1, x2), calculer y1 = a*x1 + b*x2 et y2 = c*x1 + d*x2.
4. Calculer z1 = y1 mod 26 et z2 = y2 mod 26.
5. Convertir z1 et z2 en lettres pour obtenir le texte chiffré.

# Exemple pour le premier bloc "ch" (c=2, h=7)
y1 = 3*2 + 5*7 = 6 + 35 = 41
y2 = 1*2 + 2*7 = 2 + 14 = 16
z1 = 41 mod 26 = 15
z2 = 16 mod 26 = 16
Lettres codées : 15 = P, 16 = Q

Répétez pour chaque bloc et concaténez les résultats pour obtenir le mot codé.

Cette méthode rend l'analyse de fréquence lettre par lettre inefficace car elle chiffre des paires de lettres, ce qui complexifie la statistique classique.

Algorithme RSA (Exercice 2)

L'algorithme RSA est un chiffrement asymétrique basé sur des nombres premiers p et q, et leurs propriétés.

1. Définir n = p * q.
2. Calculer φ(n) = (p - 1)(q - 1).
3. Choisir un entier e tel que 1 < e < φ(n) et gcd(e, φ(n)) = 1.
4. Calculer d, l'inverse modulaire de e modulo φ(n), c'est-à-dire d tel que d*e ≡ 1 (mod φ(n)).

Formules de chiffrement et déchiffrement :

Chiffrement : c = m^e mod n
Déchiffrement : m = c^d mod n

Les valeurs secrètes sont p, q, φ(n) et d. Les valeurs publiques sont n et e.

L'algorithme d'Euclide étendu est utilisé pour calculer d. Par exemple, pour p=71, q=131, e=3 :

n = 71 * 131 = 9301
φ(n) = (71 - 1)*(131 - 1) = 70 * 130 = 9100

Calcul de d tel que d*3 ≡ 1 mod 9100
En appliquant l'algorithme d'Euclide étendu, on trouve d = 6067

Analyse de fréquence (Exercice 3)

Cette méthode consiste à décrypter un texte chiffré en analysant la fréquence d'apparition des lettres et en les comparant aux fréquences moyennes dans la langue française.

1. Compter la fréquence d'apparition de chaque lettre dans le texte chiffré donné.
2. Comparer avec la fréquence moyenne des lettres en français, classées de la plus fréquente à la moins fréquente : E, A, I, S, T, N, R, U, L, O, D, M, P, C, V, Q, G, B, F, J, H, Z, X, Y, K, W.
3. Proposer une correspondance entre les lettres chiffrées et les lettres d'origine.
4. Utiliser des astuces telles que la reconnaissance de mots fréquents, de suites de lettres typiques, ou la position des lettres dans les mots pour affiner la solution.
5. Décrypter le texte en remplaçant les lettres chiffrées par les lettres d'origine déduites.

Cette méthode permet de casser des chiffrements simples comme le chiffre de César ou le chiffre de Vigenère avec une clé courte, mais elle est inefficace contre des chiffrements polyalphabétiques complexes ou des chiffrements utilisant des substitutions polyalphabétiques avec des clés longues.

Chiffre de Vigenère (Exercice 4)

Le chiffre de Vigenère utilise une clé répétée pour chiffrer un message par décalage des lettres.

1. Pour chiffrer le message "CET EXERCICE EST FACILE" avec la clé "UNIVERSITE" :

Procédure :
- Convertir chaque lettre du message et de la clé en nombres (A=0,...,Z=25).
- Additionner modulo 26 la valeur de la lettre du message et celle de la lettre de la clé correspondante.
- Convertir le résultat en lettre.

2. Pour déchiffrer le message "FKUYW CRLX MLHA BVXR" avec la clé "ETUDIANT" :

Procédure :
- Convertir chaque lettre du message chiffré et de la clé en nombres.
- Soustraire modulo 26 la valeur de la lettre de la clé de celle du message chiffré.
- Convertir le résultat en lettre.

Fonction de Feistel (Exercice 5)

La fonction de Feistel est un schéma de chiffrement qui divise le texte en deux blocs M1 et M2 et produit deux blocs chiffrés C1 et C2.

1. Expression du chiffrement :

C1 = M2
C2 = M1 XOR F(M2)

2. Expression du déchiffrement :

M2 = C1
M1 = C2 XOR F(C1)

Dans le schéma DES, la fonction F est une fonction complexe appliquée au bloc droit, combinée avec la clé de sous-bloc. Elle n'a pas besoin d'être inversible pour permettre le déchiffrement, car la structure Feistel garantit que le déchiffrement est possible en inversant simplement l'ordre des opérations et en réappliquant F.

Mode de chiffrement PCBC (Exercice 6)

Le mode Plain and Cipher Block Chaining (PCBC) est un mode de chiffrement par blocs qui combine chaque bloc de texte clair avec le bloc chiffré précédent et le bloc clair précédent avant chiffrement.

1. Formule de chiffrement :

c_i = E_k (m_i XOR m_{i-1} XOR c_{i-1})

2. Formule et schéma de déchiffrement :

m_i = D_k (c_i) XOR m_{i-1} XOR c_{i-1}

3. Effets d'erreurs :
• Une erreur dans un bloc chiffré c_i affecte le déchiffrement du bloc m_i et du bloc suivant m_{i+1}.
• L'inversion de deux blocs c_i et c_{i+1} perturbe la déchiffrement correct des blocs correspondants, rendant le texte déchiffré incorrect à ces positions.

Résultats attendus

• Pour le chiffre de Hill, un message codé correct est obtenu en respectant les calculs modulo 26 pour chaque bloc.
• Pour RSA, la clé privée d calculée doit satisfaire d*e ≡ 1 mod φ(n), par exemple d=6067 pour p=71, q=131, e=3.
• L'analyse de fréquence doit permettre d'identifier une correspondance plausible entre lettres chiffrées et lettres d'origine, facilitant le déchiffrement du texte donné.
• Le chiffre de Vigenère doit produire un message chiffré cohérent avec la clé et permettre un déchiffrement exact avec la même clé.
• La fonction de Feistel doit montrer que le déchiffrement est possible sans inversion de la fonction F.
• Le mode PCBC doit illustrer la propagation des erreurs sur plusieurs blocs lors du déchiffrement.

Pièges courants

• Ne pas appliquer le modulo 26 après les calculs dans le chiffre de Hill, ce qui fausse le résultat.
• Confondre les clés publiques et privées dans RSA, notamment divulguer p ou q par erreur.
• Mal calculer l'inverse modulaire d dans RSA, en oubliant que d*e doit être congru à 1 modulo φ(n).
• Dans l'analyse de fréquence, ne pas tenir compte des particularités du texte ou des mots fréquents, ce qui peut induire en erreur.
• Pour le chiffre de Vigenère, ne pas répéter correctement la clé ou ne pas appliquer le modulo 26.
• Dans la fonction de Feistel, penser que F doit être inversible, alors que ce n'est pas nécessaire.
• Dans PCBC, ne pas comprendre que les erreurs se propagent sur plusieurs blocs, ce qui complique la correction d'erreurs.