TD1: Cryptographie

Ce matériel couvre les notions fondamentales de la cryptographie, destinées aux étudiants en sécurité informatique. Il présente plusieurs algorithmes classiques de chiffrement, leurs principes, 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 qui code des groupes de lettres simultanément plutôt que lettre par lettre. Cette méthode rend les analyses statistiques plus difficiles lorsque la taille des groupes (m) augmente.

On commence par remplacer chaque lettre par son rang dans l'alphabet, en commençant à 0 : A = 0, B = 1, ..., Z = 25. Ensuite, on regroupe ces nombres par blocs de taille m (par exemple m=2).

Pour chaque bloc x = (x1, x2, ..., xm), on calcule le texte codé y = (y1, y2, ..., ym) par une combinaison linéaire :

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

Les coefficients a, b, c, d sont des entiers. Pour que les résultats restent dans l'alphabet, on prend le reste modulo 26 :

z1 = y1 mod 26, z2 = y2 mod 26

On retransforme alors 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 :
   Pour "ch" : y1 = 3*2 + 5*7 = 6 + 35 = 41
   y2 = 1*2 + 2*7 = 2 + 14 = 16
   Pour "if" : y1 = 3*8 + 5*5 = 24 + 25 = 49
   y2 = 1*8 + 2*5 = 8 + 10 = 18
   Pour "fr" : y1 = 3*5 + 5*17 = 15 + 85 = 100
   y2 = 1*5 + 2*17 = 5 + 34 = 39
   Pour "er" : y1 = 3*4 + 5*17 = 12 + 85 = 97
   y2 = 1*4 + 2*17 = 4 + 34 = 38
4. Calculer les restes modulo 26 :
   "ch" : z1 = 41 mod 26 = 15, z2 = 16 mod 26 = 16
   "if" : z1 = 49 mod 26 = 23, z2 = 18 mod 26 = 18
   "fr" : z1 = 100 mod 26 = 22, z2 = 39 mod 26 = 13
   "er" : 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

Le mot codé est donc : PQ XS WN TM

Analyse de fréquence et sécurité

Le chiffre de Hill rend difficile l'analyse de fréquence classique car il chiffre des blocs de lettres simultanément. Ainsi, l'étude statistique des lettres individuelles ne suffit pas pour casser ce code, contrairement aux chiffrements monoalphabétiques simples.

L'algorithme RSA

Le RSA est un algorithme de chiffrement asymétrique reposant sur des nombres premiers et des opérations modulaires.

Définitions des variables

• n = p × q, produit de deux nombres premiers p et q
• φ(n) = (p - 1)(q - 1), fonction indicatrice d'Euler
• d est l'inverse multiplicatif de e modulo φ(n), c'est-à-dire que d × e ≡ 1 (mod φ(n))

Chiffrement et déchiffrement

• Chiffrement : c = m^e mod n, où m est le message clair
• Déchiffrement : m = c^d mod n

Clés secrètes et publiques

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

Calcul de la clé d avec l'algorithme d'Euclide étendu

L'algorithme d'Euclide étendu permet de calculer d tel que d × e ≡ 1 (mod φ(n)). Il est applicable car e et φ(n) sont premiers entre eux (c'est une condition du RSA).

Exemple de calcul de d

Pour 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 :

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

Donc d = -3033 mod 9100 = 9100 - 3033 = 6067

La clé privée est donc 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 lettres dans un texte chiffré pour tenter de retrouver le message original.

Étude de fréquence sur un texte chiffré

Un texte chiffré est donné :

qrznva, qrf y'nhor, n y'urher bh oynapuvg yn pnzcntar,
wr cnegvenv. ibvf-gh, wr fnvf dhr gh z'nggraqf.
w'venv cne yn sberg, w'venv cne yn zbagntar.
wr ar chvf qrzrhere ybva qr gbv cyhf ybatgrzcf.

wr znepurenv yrf lrhk svkrf fhe zrf crafrrf,
fnaf evra ibve nh qrubef, fnaf ragraqer nhpha oehvg,
frhy, vapbaah, yr qbf pbheor, yrf znvaf pebvfrrf,
gevfgr, rg yr wbhe cbhe zbv fren pbzzr yn ahvg.

wr ar ertneqrenv av y'be qh fbve dhv gbzor,
av yrf ibvyrf nh ybva qrfpraqnag iref unesyrhe,
rg dhnaq w'neevirenv, wr zrggenv fhe gn gbzor
ha obhdhrg qr ubhk ireg rg qr oehlrer ra syrhe.

Étapes de l'analyse

1. Calculer la fréquence d'apparition de chaque lettre dans ce texte.
2. Comparer ces fréquences avec celles moyennes 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

3. Proposer une correspondance entre les lettres chiffrées et les lettres originales en se basant sur les fréquences.
4. Utiliser des astuces pour affiner la solution, comme repérer des mots fréquents, des suites de lettres ou des lettres en position particulière.
5. Décrypter le texte.

Exemples d'astuces pour affiner l'analyse

• Identifier les mots courts fréquents (ex. "le", "la", "et").
• Repérer les répétitions de lettres ou de groupes de lettres.
• Analyser les lettres en début ou fin de mots.

Limites de l'analyse de fréquence

• Cette méthode permet de casser les chiffrements monoalphabétiques simples.
• Elle est inefficace contre des chiffrements polyalphabétiques ou utilisant des blocs comme le chiffre de Hill.

Le chiffre de Vigenère

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

Chiffrement

Pour chiffrer un message avec un mot-clé, on répète ce mot-clé autant que nécessaire, puis on additionne les positions des lettres du message et du mot-clé modulo 26.

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

• Convertir les lettres en chiffres (A=0,...,Z=25).
• Aligner le mot-clé répété sous le message.
• Additionner modulo 26 chaque paire lettre/message et lettre/mot-clé.
• Convertir le résultat en lettres.

Déchiffrement

Pour déchiffrer, on soustrait les positions modulo 26.

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

On applique la soustraction modulo 26 entre chaque lettre chiffrée et la lettre correspondante du mot-clé répété.

La fonction de Feistel

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

Chiffrement

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

C1 = M1 ⊕ F(M2)
C2 = M2

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

Déchiffrement

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

M2 = C2
M1 = C1 ⊕ F(C2)

Fonction de Feistel dans DES

• La fonction F combine plusieurs opérations non inversibles.
• Le chiffrement et le déchiffrement utilisent la même fonction F.
• Les fonctions utilisées n'ont pas besoin d'être inversibles pour déchiffrer grâce à la structure Feistel.

Plain and Cipher Block Chaining (PCBC)

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

Formules

• Chiffrement : ci = E_k (mi ⊕ ci-1 ⊕ mi-1)
• Déchiffrement : mi = D_k (ci) ⊕ ci-1 ⊕ mi-1

Effets d'erreurs lors du déchiffrement

• Une erreur dans un bloc ci affecte le déchiffrement de ce bloc et du suivant.
• L'inversion de deux blocs ci et ci+1 perturbe le déchiffrement de ces blocs et des suivants.

Glossaire des termes clés

• Chiffrement : Transformation d'un message clair en un message codé (chiffré) pour le rendre illisible sans clé.
• Déchiffrement : Processus inverse du chiffrement pour retrouver le message original.
• 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 dans un texte.
• Chiffre de Vigenère : Chiffrement polyalphabétique utilisant un mot-clé pour coder un message.
• Fonction de Feistel : Structure de chiffrement par blocs permettant un chiffrement et déchiffrement efficaces même avec des fonctions non inversibles.
• PCBC (Plain and Cipher Block Chaining) : Mode de chiffrement par blocs combinant les blocs précédents de texte clair et chiffré.
• 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 multiplicatif d'un entier modulo un autre.

Points clés à retenir

• Le chiffre de Hill chiffre des groupes de lettres simultanément, rendant l'analyse de fréquence classique inefficace.
• RSA repose sur des opérations modulaires et la difficulté de factoriser de grands nombres.
• L'analyse de fréquence est efficace contre les chiffrements monoalphabétiques mais pas contre les chiffrements par blocs ou polyalphabétiques.
• Le chiffre de Vigenère utilise un mot-clé pour un chiffrement polyalphabétique, plus résistant à l'analyse de fréquence.
• La fonction de Feistel permet un chiffrement symétrique où la fonction utilisée n'a pas besoin d'être inversible.
• Le mode PCBC propage les erreurs sur plusieurs blocs lors du déchiffrement.