II3-Sécurité Informatique

Ce TP de sécurité informatique aborde plusieurs méthodes de chiffrement classiques et modernes, ainsi que des techniques d'analyse cryptographique. Il permet de comprendre le fonctionnement du chiffre de Hill, du RSA, du chiffre de Vigenère, de la fonction de Feistel et d'analyser la vulnérabilité des codes par analyse de fréquence. Pour réaliser ce TP, il est nécessaire de maîtriser les notions de base en cryptographie, en algèbre linéaire et en arithmétique modulaire.

Objectifs

• Appliquer le chiffre de Hill pour coder un message par blocs.
• Comprendre les principes du chiffrement asymétrique RSA et calculer ses clés.
• 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.
• Comprendre la fonction de Feistel et son utilisation dans DES.
• Étudier l'impact des erreurs et des permutations dans les modes de chiffrement par blocs.

Prérequis et installation

• Connaissances en cryptographie de base (chiffrement symétrique et asymétrique).
• Maîtrise des opérations modulo, des matrices et de l'arithmétique modulaire.
• Accès à un environnement de calcul ou programmation pour manipuler les formules et effectuer les calculs (papier, calculatrice, logiciel).

Chiffre de Hill : chiffrement par blocs

Le chiffre de Hill consiste à coder des groupes de m lettres simultanément, ce qui complique les analyses statistiques. Chaque lettre est convertie en un nombre entre 0 et 25 (A=0, B=1, ..., Z=25). Pour m=2, on forme des blocs de deux lettres, puis on applique une transformation linéaire définie par une matrice 2x2 d'entiers.

Pour chaque bloc x = (x1, x2), on calcule :

y1 = a x1 + b x2
y2 = c x1 + d x2

Les résultats y1 et y2 sont ramenés modulo 26 pour obtenir les valeurs z1 et z2, qui sont ensuite reconverties en lettres.

Procédure pour coder le mot "chiffrer" avec m=2, a=3, b=5, c=1, d=2 :

1. Diviser le texte en blocs de 2 lettres : "ch", "if", "fr", "er".
2. Convertir chaque lettre en chiffre : c=2, h=7, i=8, f=5, f=5, r=17, e=4, r=17.
3. Pour chaque bloc (x1, x2), calculer y1 et y2 :
• Bloc "ch" : y1 = 3*2 + 5*7 = 6 + 35 = 41, y2 = 1*2 + 2*7 = 2 + 14 = 16
• Bloc "if" : y1 = 3*8 + 5*5 = 24 + 25 = 49, y2 = 1*8 + 2*5 = 8 + 10 = 18
• Bloc "fr" : y1 = 3*5 + 5*17 = 15 + 85 = 100, y2 = 1*5 + 2*17 = 5 + 34 = 39
• Bloc "er" : y1 = 3*4 + 5*17 = 12 + 85 = 97, y2 = 1*4 + 2*17 = 4 + 34 = 38
4. Calculer les restes modulo 26 :
• 41 mod 26 = 15, 16 mod 26 = 16
• 49 mod 26 = 23, 18 mod 26 = 18
• 100 mod 26 = 22, 39 mod 26 = 13
• 97 mod 26 = 19, 38 mod 26 = 12
5. Convertir les chiffres en lettres :
• 15 = P, 16 = Q
• 23 = X, 18 = S
• 22 = W, 13 = N
• 19 = T, 12 = M
6. Le mot codé est donc : "PQXSWNTM".

Une analyse de fréquence classique est difficile à appliquer ici car le chiffrement agit sur des paires de lettres, ce qui réduit la répétition simple des lettres individuelles et complique la statistique.

Chiffrement asymétrique RSA

Les notations usuelles sont : p, q (deux nombres premiers), n = p × q, φ(n) = (p−1)(q−1), e (exposant public), d (exposant privé).

1. Formules :
• n = p × q
• φ(n) = (p−1)(q−1)
• d est l'inverse multiplicatif de e modulo φ(n), c'est-à-dire que d × e ≡ 1 (mod φ(n))
2. Chiffrement :

c = m^e mod n

3. Déchiffrement :

m = c^d mod n

4. Valeurs secrètes : p, q, φ(n), d
5. Valeurs publiques : n, e

Pour calculer d, on utilise l'algorithme d'Euclide étendu, applicable car e et φ(n) sont premiers entre eux.

Exemple de calcul de d pour p=71, q=131, e=3 :

• Calculer n = 71 × 131 = 9301
• Calculer φ(n) = (71−1)(131−1) = 70 × 130 = 9100
• Résoudre d × 3 ≡ 1 (mod 9100) avec l'algorithme d'Euclide étendu :

9100 = 3 × 3033 + 1
1 = 9100 − 3 × 3033

On trouve d = 6067 car 6067 × 3 mod 9100 = 1.

Analyse de fréquence et décryptage

On analyse un texte chiffré par la fréquence d'apparition des lettres. Le tableau suivant doit être rempli avec les fréquences observées :

a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z

La fréquence moyenne des lettres en français est : 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, de la plus fréquente à la moins fréquente.

En comparant les fréquences du texte chiffré avec celles du français, on peut proposer une correspondance entre lettres chiffrées et lettres d'origine.

Pour affiner le décryptage, on peut utiliser :

• La reconnaissance de mots fréquents ou caractéristiques.
• L'étude des suites de lettres ou des digrammes.
• La position des lettres dans les mots (début, fin).

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 par blocs complexes ou asymétriques.

Chiffre de Vigenère

Le chiffre de Vigenère utilise une clé répétée pour décaler les lettres du message.

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

Message :  C  E  T  E  X  E  R  C  I  C  E  E  S  T  F  A  C  I  L  E
Clé :       U  N  I  V  E  R  S  I  T  E  U  N  I  V  E  R  S  I  T  E

Pour chaque lettre, additionner les indices modulo 26.

2. Déchiffrez le message "FKUYW CRLX MLHA BVXR" avec la clé "ETUDIANT" :

Message chiffré : F  K  U  Y  W  C  R  L  X  M  L  H  A  B  V  X  R
Clé :             E  T  U  D  I  A  N  T  E  T  U  D  I  A  N  T  E

Pour chaque lettre, soustraire les indices modulo 26.

Fonction de Feistel

La fonction de Feistel transforme deux blocs de texte clair M1 et M2 en deux blocs chiffrés C1 et C2 :

C1 = M1 ⊕ F(M2)
C2 = M2

Pour le déchiffrement :

M2 = C2
M1 = C1 ⊕ F(M2)

Dans le schéma DES, la fonction F est une fonction complexe appliquée sur un bloc, combinée avec une clé.

1. L'expression de la fonction de Feistel F est spécifique au système, mais elle ne doit pas nécessairement être inversible.
2. Le chiffrement et le déchiffrement utilisent la même fonction F, ce qui simplifie la conception.

Plain and Cipher Block Chaining (PCBC)

1. Formule de chiffrement :

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

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

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

3. Effet d'une erreur sur un bloc c_i :

Une erreur dans le bloc c_i affecte le déchiffrement de m_i et m_{i+1}, mais pas des blocs suivants.

4. Effet de l'inversion de deux blocs c_i et c_{i+1} :

Inverser deux blocs perturbe le déchiffrement des blocs concernés et peut corrompre plusieurs blocs suivants, rendant la récupération du message difficile.

Résultats attendus

• Pour le chiffre de Hill, le mot "chiffrer" doit être codé en "PQXSWNTM".
• Pour RSA, la clé privée d calculée pour p=71, q=131, e=3 est d=6067.
• L'analyse de fréquence doit permettre d'identifier les correspondances lettres chiffrées/lettres originales et de déchiffrer le texte donné.
• Le chiffre de Vigenère doit produire un texte chiffré correct avec la clé donnée, et permettre le déchiffrement inverse.
• La fonction de Feistel doit être comprise dans ses expressions de chiffrement et déchiffrement.
• Les effets d'erreurs et permutations dans PCBC doivent être observés selon les explications.

Pièges courants

• Ne pas ramener les valeurs y1, y2 modulo 26 dans le chiffre de Hill, ce qui empêche la conversion en lettres.
• Confondre les clés publiques et privées dans RSA, ce qui compromet la sécurité.
• Oublier que l'algorithme d'Euclide étendu ne s'applique que si e et φ(n) sont premiers entre eux.
• Dans l'analyse de fréquence, ne pas tenir compte des particularités du texte (longueur, ponctuation) peut fausser les résultats.
• Dans le chiffre de Vigenère, mal aligner la clé avec le message entraîne un chiffrement incorrect.
• Pour la fonction de Feistel, penser que F doit être inversible est une erreur : seule la structure globale garantit le déchiffrement.
• En PCBC, ne pas prendre en compte l'effet en cascade des erreurs sur plusieurs blocs peut conduire à des conclusions erronées.