II3-Sécurité Informatique

Ce document couvre les notions fondamentales de la sécurité informatique, en particulier la cryptographie, à destination des étudiants en informatique. Il présente plusieurs méthodes de chiffrement classiques et modernes, ainsi que des exercices pratiques pour comprendre leur fonctionnement et leurs vulnérabilités.

Le chiffre de Hill

Le chiffre de Hill, proposé par Lester Hill en 1929, est un algorithme de chiffrement par bloc qui code simultanément des groupes de m lettres, rendant l'analyse statistique plus difficile. Chaque lettre est d'abord convertie en un nombre correspondant à sa position dans l'alphabet (A = 0, B = 1, ..., Z = 25). Ensuite, les blocs de m lettres sont transformés par une combinaison linéaire.

Pour m = 2, le chiffrement s'exprime par :

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

où a, b, c, d sont des entiers. Les résultats y1 et y2 sont ramenés modulo 26 (reste de la division par 26) pour rester dans l'intervalle 0-25 et pouvoir être reconvertis en lettres.

Exemple : Chiffrement du 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 ("ch") : y1 = 3×2 + 5×7 = 6 + 35 = 41
   y2 = 1×2 + 2×7 = 2 + 14 = 16
   Bloc 2 ("if") : y1 = 3×8 + 5×5 = 24 + 25 = 49
   y2 = 1×8 + 2×5 = 8 + 10 = 18
   Bloc 3 ("fr") : y1 = 3×5 + 5×17 = 15 + 85 = 100
   y2 = 1×5 + 2×17 = 5 + 34 = 39
   Bloc 4 ("er") : y1 = 3×4 + 5×17 = 12 + 85 = 97
   y2 = 1×4 + 2×17 = 4 + 34 = 38
4. Calculer les restes modulo 26 (z1, z2) :
   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 nombres en lettres :
   15 = P, 16 = Q
   23 = X, 18 = S
   22 = W, 13 = N
   19 = T, 12 = M

Le mot codé est donc : PQXSWN TM.

Analyse de la sécurité

Une analyse de fréquence simple des lettres est inefficace contre ce chiffrement car les lettres sont codées par blocs et non individuellement. Cela complique la correspondance directe entre lettres chiffrées et lettres d'origine.

Le chiffrement RSA

Le RSA est un algorithme de chiffrement asymétrique basé sur des propriétés mathématiques des nombres premiers.

Définitions des variables

• n = p × q où p et q sont deux nombres premiers secrets.
• φ(n) = (p - 1)(q - 1) est la fonction indicatrice d'Euler.
• d est l'exposant privé, calculé comme l'inverse multiplicatif de e modulo φ(n), c'est-à-dire que d vérifie : d × e ≡ 1 (mod φ(n)).

Formules de chiffrement et déchiffrement

• Chiffrement : c = m^e mod n
• Déchiffrement : 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 avec l'algorithme d'Euclide étendu

L'algorithme d'Euclide étendu permet de calculer l'inverse multiplicatif de e modulo φ(n), donc la clé privée d.

Exemple de calcul de d pour p=71, q=131 et 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 :

9100 = 3 × 3033 + 1
1 = 9100 - 3 × 3033

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

Analyse de fréquence et décryptage

L'analyse de fréquence est une méthode statistique qui consiste à décrypter un texte chiffré en étudiant la fréquence d'apparition des lettres dans la langue d'origine.

Étapes de l'analyse

1. Calculer la fréquence des lettres dans le texte chiffré.
2. Comparer ces fréquences avec celles d'une langue connue (par exemple le français).
3. Établir une correspondance probable entre lettres chiffrées et lettres d'origine.
4. Utiliser des astuces supplémentaires pour affiner la solution, comme l'identification de mots fréquents, de suites de lettres ou de lettres en positions spécifiques.

Exemple d'analyse

Un texte chiffré est donné, et on calcule la fréquence des lettres. En comparant avec la fréquence moyenne en français :

Ordre des lettres du plus fréquent au moins fréquent en français :
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 propose une correspondance entre les lettres chiffrées et les lettres d'origine en fonction des fréquences observées.

Astuce pour affiner le décryptage

• Rechercher des mots particuliers (articles, pronoms).
• Identifier des suites de lettres typiques (comme "tion", "ent").
• Observer la position des lettres dans les mots (lettre initiale ou finale).

Limites de l'analyse de fréquence

Cette méthode est efficace contre des chiffrements simples comme le chiffre de César ou de Vigenère (avec des clés courtes), mais inefficace contre des chiffrements par bloc ou asymétriques comme RSA ou le chiffre de Hill avec grands blocs.

Le chiffre de Vigenère

Le chiffre de Vigenère est un chiffrement par substitution polyalphabétique utilisant un mot-clé.

Chiffrement

Pour chaque lettre du message, on ajoute la valeur numérique de la lettre correspondante du mot-clé (recyclé si nécessaire), modulo 26.

Exemple : Chiffrement de "CET EXERCICE EST FACILE" avec le mot-clé "UNIVERSITE"

• Convertir les lettres en nombres (A=0,...,Z=25).
• Pour chaque lettre du message m_i et lettre du mot-clé k_i, calculer c_i = (m_i + k_i) mod 26.
• Convertir les nombres c_i en lettres.

Déchiffrement

Pour déchiffrer, on soustrait la valeur numérique du mot-clé :

m_i = (c_i - k_i) mod 26

Exemple : Déchiffrement du message "FKUYW CRLX MLHA BVXR" avec le mot-clé "ETUDIANT"

Appliquer la formule de déchiffrement lettre par lettre pour retrouver le texte original.

La fonction de Feistel

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

Chiffrement

Soient deux blocs de texte en clair M1 et M2, la fonction de Feistel F, alors :

C1 = M1 ⊕ F(M2)
C2 = M2

Déchiffrement

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

M2 = C2
M1 = C1 ⊕ F(C2)

Propriétés

• La fonction F n'a pas besoin d'être inversible pour permettre le déchiffrement.
• Le chiffrement et le déchiffrement utilisent la même fonction F.

Plain and Cipher Block Chaining (PCBC)

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

Formule de chiffrement

Le bloc chiffré c_i est calculé à partir du bloc clair m_i et des blocs précédents :

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

avec E_k la fonction de chiffrement avec clé k, et m_0, c_0 des vecteurs d'initialisation.

Schéma de déchiffrement

Pour déchiffrer :

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

où D_k est la fonction de déchiffrement.

Effets d'erreurs

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

Glossaire des termes clés

• Chiffrement par bloc : méthode de chiffrement qui traite des groupes de lettres simultanément.
• Modulo : opération qui donne le reste de la division d'un nombre par un autre.
• Analyse de fréquence : technique de cryptanalyse basée sur la fréquence d'apparition des lettres.
• RSA : algorithme de chiffrement asymétrique utilisant des clés publiques et privées.
• Fonction indicatrice d'Euler φ(n) : nombre d'entiers inférieurs à n et premiers avec n.
• Algorithme d'Euclide étendu : méthode pour calculer l'inverse multiplicatif modulo d'un nombre.
• Chiffre de Vigenère : chiffrement polyalphabétique utilisant un mot-clé.
• Fonction de Feistel : structure de chiffrement par bloc utilisée dans DES.
• Plain and Cipher Block Chaining (PCBC) : mode de chiffrement par bloc combinant blocs clairs et chiffrés précédents.

Points clés à retenir

• Le chiffre de Hill chiffre par blocs, rendant l'analyse de fréquence simple inefficace.
• RSA repose sur des opérations modulo sur des grands nombres premiers, avec une clé publique et une clé privée.
• L'analyse de fréquence est efficace contre des chiffrements simples mais pas contre des chiffrements par bloc ou asymétriques.
• Le chiffre de Vigenère utilise un mot-clé pour un chiffrement polyalphabétique.
• La fonction de Feistel permet un chiffrement réversible même si la fonction utilisée n'est pas inversible.
• Le mode PCBC propage les erreurs sur plusieurs blocs, ce qui peut être un avantage ou un inconvénient selon le contexte.