# TD 3 : Cryptographie — RSA, Diffie-Hellman et Fonctions de Hachage
## Fiche de Révision et Correction Détaillée

Ce document propose une reformulation claire, structurée et rigoureuse des concepts abordés dans le TD3, divisée entre la théorie (sur papier) et la pratique (sur machine avec OpenSSL/SHA-256).

---

## Partie 1 : Exercices sur Papier

### Exercice 1 — Échauffement Mathématique

Cet exercice pose les bases de l'arithmétique modulaire nécessaires aux cryptosystèmes asymétriques.

1. **Nombres premiers compris entre 1 et 30 :**
   Les nombres qui n'admettent que deux diviseurs distincts (1 et eux-mêmes) sont :
   $$\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29\}$$

2. **Calcul de $\text{pgcd}(20, 9)$ (Algorithme d'Euclide) :**
   * $20 = 2 \times 9 + 2$
   * $9 = 4 \times 2 + 1$
   * $2 = 2 \times 1 + 0$
   * **Résultat :** Le dernier reste non nul est $1$. Ainsi, $\text{pgcd}(20, 9) = 1$. Les nombres 20 et 9 sont dits *premiers entre eux*.

3. **Calcul de $\text{pgcd}(48, 18)$ :**
   * $48 = 2 \times 18 + 12$
   * $18 = 1 \times 12 + 6$
   * $12 = 2 \times 6 + 0$
   * **Résultat :** Le dernier reste non nul est $6$. Ainsi, $\text{pgcd}(48, 18) = 6$.

4. **Recherche de l'inverse multiplicatif de $5 \pmod{14}$ :**
   On cherche un entier $d$ tel que $5 \times d \equiv 1 \pmod{14}$.
   * Par tâtonnement ou application de l'algorithme d'Euclide étendu :
     $5 \times 3 = 15$
     Or, $15 = 1 \times 14 + 1 \equiv 1 \pmod{14}$.
   * **Résultat :** L'inverse de $5$ modulo $14$ est **$3$**.

---

### Exercice 2 — Exponentiation Rapide (Carré-Multiplication)

L'algorithme de carré-multiplication permet de calculer efficacement de grandes puissances modulaires en réduisant le nombre d'opérations.

**Objectif :** Calculer $4^{13} \pmod{21}$.

1. **Décomposition binaire de l'exposant :**
   $13 = 8 + 4 + 1 = (1101)_2$

2. **Calcul des carrés successifs (Étape de mise au carré) :**
   * $4^1 \equiv 4 \pmod{21}$
   * $4^2 = 16 \pmod{21}$
   * $4^4 \equiv (4^2)^2 \equiv 16^2 = 256$
     Or, $256 = 12 \times 21 + 4 \implies 4^4 \equiv 4 \pmod{21}$
   * $4^8 \equiv (4^4)^2 \equiv 4^2 = 16 \pmod{21}$

3. **Combinaison des termes (Étape de multiplication) :**
   On multiplie les puissances correspondant aux bits égaux à $1$ dans la décomposition binaire de $13$ (c'est-à-dire $8, 4 \text{ et } 1$) :
   $$4^{13} = 4^8 \times 4^4 \times 4^1$$
   $$4^{13} \equiv 16 \times 4 \times 4 \pmod{21}$$
   $$4^{13} \equiv 16 \times 16 = 256 \pmod{21}$$
   $$4^{13} \equiv 4 \pmod{21}$$

* **Résultat final :** $4^{13} \pmod{21} = 4$.

---

### Exercice 3 — Chiffrement RSA "à la main"

Application pédagogique du cryptosystème RSA avec de petites valeurs numériques.

1. **Génération des clés :**
   * Choix de deux nombres premiers : $p = 3$ et $q = 11$.
   * Calcul du module de chiffrement : $n = p \times q = 3 \times 11 = 33$.
   * Calcul de l'indicatrice d'Euler : $\phi(n) = (p-1)(q-1) = 2 \times 10 = 20$.
   * Choix de l'exposant public : $e = 3$ (valide car $\text{pgcd}(3, 20) = 1$).
   * Calcul de l'exposant privé $d$ (inverse de $e \pmod{\phi(n)}$) :
     On cherche $d$ tel que $3 \times d \equiv 1 \pmod{20}$.
     Puisque $3 \times 7 = 21 \equiv 1 \pmod{20}$, on obtient **$d = 7$**.

2. **Chiffrement du message $M = 4$ :**
   * Formule : $C = M^e \pmod n$
   * Calcul : $C = 4^3 \pmod{33} = 64 \pmod{33}$
   * Réduction : $64 = 1 \times 33 + 31$
   * **Cryptogramme obtenu :** $C = 31$.

3. **Déchiffrement du cryptogramme $C = 31$ :**
   * Formule : $M = C^d \pmod n$
   * Calcul : $M = 31^7 \pmod{33}$
   * *Astuce de calcul :* $31 \equiv -2 \pmod{33}$
     Donc $31^7 \equiv (-2)^7 = -128 \pmod{33}$
   * Réduction de $-128$ modulo $33$ :
     $-128 = -4 \times 33 + 4$
   * **Message déchiffré :** $M = 4$ (Le message initial est correctement restauré).

4. **Question Bonus — Mécanisme de Signature :**
   Pour signer un document, le processus est inversé : **Alice utilise sa propre clé privée** pour chiffrer l'empreinte du message (générant ainsi la signature). **Bob utilise la clé publique d'Alice** pour vérifier la signature, ce qui garantit l'authenticité et l'intégrité de la source.

---

### Exercice 4 — Échange de clés de Diffie-Hellman & Attaque MITM

#### Round 1 : Échange légitime et honnête
* **Paramètres publics :** Nombre premier $p = 23$, Générateur $g = 5$.
* **Choix des secrets privés :** Alice choisit $a = 3$ ; Bob choisit $b = 4$.
* **Calcul des valeurs publiques à échanger :**
  * **Alice :** $A = g^a \pmod p = 5^3 \pmod{23} = 125 \pmod{23} = 10$
  * **Bob :** $B = g^b \pmod p = 5^4 \pmod{23} = 625 \pmod{23} = 4$
* **Calcul du secret partagé commun ($K$) :**
  * **Alice calcule :** $K = B^a \pmod p = 4^3 \pmod{23} = 64 \pmod{23} = 18$
  * **Bob calcule :** $K = A^b \pmod p = 10^4 \pmod{23} = 10000 \pmod{23} = 18$
* **Conclusion du Round 1 :** Alice et Bob partagent avec succès le même secret : **$K = 18$**.

#### Round 2 : Attaque de l'Homme du Milieu (Man-In-The-Middle - MITM)
Ève s'intercepte au milieu du canal de communication de manière transparente.

1. **Déroulement de l'attaque :**
   * Ève génère deux secrets privés distincts : $e_A$ (pour sa liaison avec Alice) et $e_B$ (pour sa liaison avec Bob).
   * Elle intercepte la clé publique $A$ d'Alice et lui substitue sa propre clé publique $E_A = g^{e_A} \pmod p$ à destination de Bob.
   * Elle fait de même avec la clé $B$ de Bob en lui substituant $E_B = g^{e_B} \pmod p$ à destination d'Alice.
2. **Secrets générés :**
   * Alice calcule une clé partagée avec Ève : $K_{Alice-Eve} = g^{a \cdot e_A} \pmod p$.
   * Bob calcule une clé partagée avec Ève : $K_{Bob-Eve} = g^{b \cdot e_B} \pmod p$.
3. **Alice et Bob ont-ils le même secret ?**
   **Non.** Alice et Bob ont établi des secrets différents, chacun pensant dialoguer de manière sécurisée avec l'autre alors qu'ils dialoguent tous les deux individuellement avec Ève.
4. **Solution contre cette attaque :**
   Il manque un **mécanisme d'authentification** des clés publiques. Pour empêcher le MITM, les clés publiques échangées doivent être signées numériquement (via une infrastructure à clés publiques - PKI ou des certificats) pour prouver l'identité de leur émetteur avant toute dérivation de secret.

---

### Exercice 5 — Analyse d'une fonction de "Mini-Hash"

On étudie une fonction de hachage simplifiée $H$ qui retourne un résultat sur 4 bits (valeurs entières de $0$ à $15$).

1. **Exemples d'empreintes fournies :**
   * $H(\text{"CHAT"}) = 0$
   * $H(\text{"OURS"}) = 9$
   * $H(\text{"CRYPTO"}) = 1$

2. **Mise en évidence d'une collision :**
   Prenons l'exemple de messages réduits à une seule lettre où le hash correspond à la valeur alphabétique modulo 16 :
   * Soit la lettre **"A"** (position 1) : $H(\text{"A"}) = 1 \pmod{16} = 1$.
   * Soit la lettre **"Q"** (position 17) : $H(\text{"Q"}) = 17 \pmod{16} = 1$.
   * **Constat :** $H(\text{"A"}) = H(\text{"Q"}) = 1$. Deux messages différents produisent la même empreinte : il y a collision.

3. **Trois raisons majeures pour lesquelles ce modèle est inutilisable en sécurité :**
   * **Taille de l'espace de sortie dramatiquement faible :** Disposer de seulement 16 valeurs possibles garantit mathématiquement la découverte de collisions quasi-instantanée (principe des tiroirs).
   * **Absence de résistance aux collisions et à l'inversion :** Il est extrêmement facile de forger un message arbitraire pour qu'il corresponde à une empreinte visée (absence de protection contre les attaques de pré-image).
   * **Absence d'effet avalanche :** Une modification minime de l'entrée (ex: changer une lettre) ne produit pas un changement chaotique et imprévisible de la sortie ; la fonction souffre d'une trop grande linéarité.

---

## Partie 2 : Exercices sur Machine (PC)

### Exercice 6 — Vérification d'Intégrité (Le mail de ton ami)

1. **Identification du bon fichier :**
   * Le hash SHA-256 officiel communiqué est : `ece55d55d3b306516d50a4111475d0c3ef3ab75266fe4fd6fc63ef1faff5eadc`.
   * En calculant l'empreinte de `lettre.txt`, on obtient exactement cette valeur. Le fichier `lettre-faux.txt` donne un hash totalement distinct.
   * **Conclusion :** L'ami a bien envoyé le fichier `lettre.txt`.

2. **Scénario d'interception totale par Ève :**
   Si Ève intercepte à la fois le fichier textuel et le canal de transmission du hash, **il devient impossible de détecter la falsification**. Ève peut modifier le contenu du message, recalculer le nouveau hash SHA-256 du texte altéré, et transmettre ce faux couple (fichier modifié + nouveau hash) à la cible. Le destinataire constatera une cohérence parfaite lors de la vérification.

3. **Contre-mesure nécessaire :**
   Le hachage seul ne garantit que l'intégrité face aux erreurs involontaires. Pour se prémunir d'une altération malveillante, il faut adjoindre un mécanisme garantissant **l'authenticité de l'origine**, tel qu'une **signature numérique** ou un code d'authentification de message (HMAC).

---

### Exercice 7 — Analyse du Chiffrement Asymétrique RSA avec OpenSSL

* **Constat de taille :** Le fichier en texte clair `rdv.txt` pèse $27 \text{ octets}$. Une fois chiffré par RSA (clé de 2048 bits) sous le nom `rdv.bin`, sa taille passe à **$256 \text{ octets}$**.
* **Explication technique :** Le chiffrement RSA s'exécute sur des blocs de taille fixe déterminés par la taille de son module $n$. Une clé RSA-2048 produit systématiquement un bloc chiffré de $2048 \text{ bits} = 256 \text{ octets}$, quelle que soit la petitesse du message initial. Le chiffrement asymétrique est donc lourd et inefficace pour les données volumineuses (c'est pourquoi on utilise en pratique le chiffrement hybride).

---

### Exercice 8 — Mécanisme de Signature Numérique

1. **Comportement après altération :**
   Toute modification ultérieure apportée au fichier `rdv.txt` produit irrémédiablement le message d'erreur d'OpenSSL : **`Verification Failure`**.

2. **Pourquoi Ève ne peut-elle pas générer une fausse signature ?**
   Bien qu'Ève puisse librement modifier le contenu textuel du fichier, la génération d'une signature numérique valide requiert impérativement la **clé privée** de l'émetteur légitime (Marc). N'ayant accès qu'à la clé publique, Ève ne dispose pas des éléments mathématiques pour signer son forfait.

3. **Garanties de la signature pour Marc :**
   Si Marc signe électroniquement son courriel, toute modification malveillante opérée par Ève brise la relation mathématique unissant le message, la signature et la clé publique de Marc. L'altération est immédiatement décelée au moment de la vérification. Marc génère sa signature avec sa **clé privée** et distribue librement sa **clé publique** pour la phase de contrôle.

---

### Exercice 9 — Authentification SSH par Défi-Réponse (Challenge-Challenge)

L'authentification par clé SSH repose sur un protocole d'identification asymétrique interactif.

1. **Formalisation des étapes du protocole :**
   * **Étape 3 (Calcul de l'utilisateur/Alice) :** Suite à la réception d'un défi (ou challenge) aléatoire $r$ envoyé par le serveur, Alice utilise sa clé privée pour signer numériquement cette donnée :
     $$S = \text{sign}_{\text{priv}}(r)$$
   * **Étape 5 (Vérification par le serveur) :** Le serveur reçoit la signature $S$ et l'analyse à l'aide de la clé publique d'Alice (préalablement déclarée dans le fichier `authorized_keys`) :
     $$\text{verify}_{\text{pub}}(S, r) \rightarrow \text{\'Emet un verdict (Valid\\'e / Rejet\\'e)}$$
   * **Verdict OpenSSL :** Le terminal renvoie l'état **`Verified OK`** confirmant le succès de la procédure.

2. **Rôle impératif du caractère aléatoire du challenge ($r$) :**
   L'aléa est indispensable pour neutraliser les **attaques par rejeu (Replay Attacks)**. Si le défi restait identique ou devenait prévisible, un espion pourrait intercepter une signature valide $S$ passée et la renvoyer ultérieurement pour s'authentifier avec succès auprès du serveur sans détenir la clé privée.

3. **Deux avantages fondamentaux des clés SSH face aux mots de passe traditionnels :**
   * **Zéro transmission du secret sur le réseau :** La clé privée (le secret d'authentification) réside exclusivement sur la machine locale du client et n'est jamais divulguée sur le canal réseau lors du processus d'identification.
   * **Immunité face aux serveurs compromis :** Si un serveur distant auquel vous vous connectez est corrompu ou contrôlé par un attaquant, ce dernier ne récupère qu'une signature éphémère à usage unique liée à un challenge spécifique. Il n'obtient aucune information lui permettant de découvrir la clé privée du client ou d'usurper son identité sur d'autres serveurs.