II3-Sécurité Informatique

Ce document couvre des notions fondamentales de la sécurité informatique, plus précisément la cryptographie, à travers plusieurs exercices pratiques. Il s'adresse aux étudiants en informatique souhaitant comprendre et appliquer des algorithmes classiques de chiffrement et de déchiffrement, ainsi que les méthodes d'analyse cryptographique.

Le chiffre de Hill

Le chiffre de Hill, proposé par Lester Hill en 1929, est un algorithme de chiffrement par blocs. Contrairement aux méthodes qui codent lettre par lettre, il chiffre simultanément des groupes de m lettres. Plus m est grand, plus l'analyse statistique devient difficile.

Procédé :

• Chaque lettre est remplacée par son rang dans l'alphabet, en commençant à 0 : A = 0, B = 1, ..., Z = 25.
• Les lettres sont regroupées par blocs de taille m (ici m=2).
• Pour chaque bloc x = (x1, x2), on calcule y = (y1, y2) par :

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

Les coefficients a, b, c, d sont des entiers. Pour que y1 et y2 soient convertibles en lettres, on prend leur reste modulo 26 :

z1 = y1 mod 26
z2 = y2 mod 26

On convertit ensuite z1 et z2 en lettres pour obtenir le message codé.

Exemple : 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 les lettres en chiffres :
• c = 2, h = 7
• i = 8, f = 5
• f = 5, r = 17
• e = 4, r = 17
3. Calculer y1 et y2 pour chaque bloc :
• Bloc 1 (2,7) : y1 = 3*2 + 5*7 = 6 + 35 = 41, y2 = 1*2 + 2*7 = 2 + 14 = 16
• Bloc 2 (8,5) : y1 = 3*8 + 5*5 = 24 + 25 = 49, y2 = 1*8 + 2*5 = 8 + 10 = 18
• Bloc 3 (5,17) : y1 = 3*5 + 5*17 = 15 + 85 = 100, y2 = 1*5 + 2*17 = 5 + 34 = 39
• Bloc 4 (4,17) : y1 = 3*4 + 5*17 = 12 + 85 = 97, y2 = 1*4 + 2*17 = 4 + 34 = 38
4. Calculer les restes modulo 26 :
• Bloc 1 : z1 = 41 mod 26 = 15, z2 = 16 mod 26 = 16
• Bloc 2 : z1 = 49 mod 26 = 23, z2 = 18 mod 26 = 18
• Bloc 3 : z1 = 100 mod 26 = 22, z2 = 39 mod 26 = 13
• Bloc 4 : z1 = 97 mod 26 = 19, z2 = 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 : "PQXSWN TM" (sans espace : "PQXSWNTM").

Analyse de fréquence : Ce code est plus difficile à casser par analyse de fréquence classique car il chiffre des blocs de lettres ensemble, ce qui brouille la correspondance directe entre lettres claires et lettres chiffrées. Les fréquences des lettres individuelles ne sont plus conservées, rendant l'analyse statistique moins efficace.

L'algorithme RSA

Le RSA est un algorithme de chiffrement asymétrique basé sur la factorisation de grands nombres premiers.

Définitions des variables

• p, q : deux nombres premiers distincts.
• n = p × q
• φ(n) = (p - 1)(q - 1) (fonction indicatrice d'Euler)
• e : exposant de chiffrement, choisi tel que 1 < e < φ(n) et gcd(e, φ(n)) = 1
• d : exposant de déchiffrement, inverse modulaire de e modulo φ(n), c’est-à-dire que d × e ≡ 1 mod φ(n)

Formules de chiffrement et déchiffrement

Pour un message m (entier), le chiffrement donne :

c = m^e mod n

Le déchiffrement est :

m = c^d mod n

Clés publiques et privées

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

Calcul de la clé d

La clé d est calculée à l'aide de l'algorithme d'Euclide étendu, qui permet de trouver l'inverse modulaire de e modulo φ(n).

1. L'algorithme est applicable car e et φ(n) sont premiers entre eux (gcd(e, φ(n)) = 1).
2. Correspondance des variables :
• a = e
• b = φ(n)
• x = d (l'inverse modulaire cherché)
3. Exemple : p=71, q=131, e=3
• Calcul de n = 71 × 131 = 9301
• Calcul de φ(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

L'analyse de fréquence est une méthode de cryptanalyse qui consiste à étudier la fréquence d'apparition des caractères dans un texte chiffré pour tenter de retrouver le texte original.

Étude de fréquence sur un texte chiffré

On considère un texte chiffré dont il faut calculer la fréquence des lettres :

Lettre	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
Fréquence

En comparant avec la fréquence moyenne des lettres en français (ordre décroissant : 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), on peut proposer une correspondance entre les lettres chiffrées et les lettres originales.

Astuces pour affiner la solution

• Identifier des mots particuliers fréquents (articles, prépositions).
• Repérer des suites de lettres typiques (comme "tion", "ent").
• Analyser la position des lettres dans les mots (début, fin).

Décryptage du texte

En appliquant ces méthodes, on peut progressivement retrouver le texte original.

Exemples d'algorithmes cassables ou résistants à l'analyse de fréquence

• Algorithme cassable : chiffre de César (monoalphabétique).
• Algorithme résistant : chiffre de Vigenère (polyalphabétique).

Chiffre de Vigenère

Le chiffre de Vigenère est un algorithme de chiffrement polyalphabétique utilisant un mot clé pour chiffrer un message.

Chiffrement

Pour chiffrer un message avec un mot clé, on aligne le mot clé sur le message, puis on additionne les valeurs des lettres modulo 26.

Exemple : chiffrer "CET EXERCICE EST FACILE" avec le mot clé "UNIVERSITE"

1. Convertir les lettres en nombres (A=0,...,Z=25).
2. Aligner le mot clé sur le message (en ignorant les espaces).
3. Pour chaque lettre, calculer :

chiffre = (lettre_message + lettre_clef) mod 26

Déchiffrement

Pour déchiffrer, on soustrait la valeur de la lettre clé :

lettre_message = (lettre_chiffrée - lettre_clef + 26) mod 26

Exemple : déchiffrer "FKUYW CRLX MLHA BVXR" avec le mot clé "ETUDIANT"

On applique la formule de déchiffrement lettre par lettre en alignant le mot clé.

Fonction de Feistel

La fonction de Feistel est une structure utilisée dans de nombreux algorithmes de chiffrement par blocs, notamment DES.

Expression de la fonction de chiffrement

Soient deux blocs de texte clair M1 et M2, la fonction de Feistel produit deux blocs chiffrés C1 et C2 :

C1 = M2
C2 = M1 ⊕ F(M2)

où F est une fonction de chiffrement et ⊕ est l'opération XOR.

Expression de la fonction de déchiffrement

Pour retrouver M1 et M2 à partir de C1 et C2 :

M2 = C1
M1 = C2 ⊕ F(C1)

Fonction de Feistel dans DES

• F est une fonction complexe combinant substitution et permutation.
• Le chiffrement consiste en plusieurs tours appliquant cette fonction.
• Le déchiffrement utilise la même fonction F dans l'ordre inverse.

Inversibilité des fonctions

Les fonctions utilisées dans Feistel n'ont pas besoin d'être inversibles pour permettre le déchiffrement, car la structure Feistel garantit la réversibilité globale.

Plain and Cipher Block Chaining (PCBC)

PCBC est un mode de chiffrement par blocs qui combine le texte clair et le texte chiffré précédents pour chiffrer un bloc.

Formule de chiffrement

Le bloc chiffré c_i est calculé par :

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

avec E_k la fonction de chiffrement avec clé k, m_i le bloc clair courant, m_{i-1} le bloc clair précédent, et c_{i-1} le bloc chiffré précédent.

Formule et schéma de déchiffrement

Le déchiffrement s'effectue par :

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

où D_k est la fonction de déchiffrement.

Effets d'erreurs lors du déchiffrement

• Une erreur sur un bloc c_i affecte le déchiffrement de ce bloc et du suivant.
• L'inversion de deux blocs c_i et c_{i+1} perturbe la déchiffrement des deux blocs correspondants.

Glossaire des termes clés

• Chiffre de Hill : algorithme de chiffrement par blocs utilisant des combinaisons linéaires modulo 26.
• RSA : algorithme de chiffrement asymétrique basé sur la factorisation de grands nombres premiers.
• Analyse de fréquence : méthode de cryptanalyse basée sur la fréquence d'apparition des lettres.
• Chiffre de Vigenère : chiffrement polyalphabétique utilisant un mot clé.
• Fonction de Feistel : structure de chiffrement par blocs utilisée dans DES.
• PCBC : mode de chiffrement par blocs combinant texte clair et texte chiffré précédents.
• Modulo : opération donnant le reste de la division d'un nombre par un autre.
• Algorithme d'Euclide étendu : méthode pour calculer l'inverse modulaire.
• Clé publique : clé accessible à tous pour chiffrer un message.
• Clé privée : clé secrète utilisée pour déchiffrer un message.

Points clés à retenir

• Le chiffre de Hill chiffre des blocs de lettres, rendant l'analyse de fréquence plus difficile.
• RSA repose sur des clés publiques et privées, avec des opérations modulo n.
• L'analyse de fréquence est efficace contre les chiffrements monoalphabétiques mais moins contre les polyalphabétiques.
• Le chiffre de Vigenère utilise un mot clé pour un chiffrement polyalphabétique.
• La structure de Feistel permet un chiffrement réversible sans que la fonction F soit inversible.
• Le mode PCBC propage les erreurs sur plusieurs blocs lors du déchiffrement.