TD3 — RSA, Diffie-Hellman & hachage

Exercices sur papier

Exercice 1 — Echauffement

Nombres premiers entre 1 et 30 : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

pgcd(20, 9) :

20 = 2 * 9 + 2   → pgcd(20, 9) = pgcd(9, 2)
 9 = 4 * 2 + 1   → pgcd(9, 2)  = pgcd(2, 1)
 2 = 2 * 1 + 0   → pgcd(2, 1)  = 1

pgcd(20, 9) = 1 (20 et 9 sont premiers entre eux)

pgcd(48, 18) :

48 = 2 * 18 + 12  → pgcd(48, 18) = pgcd(18, 12)
18 = 1 * 12 + 6   → pgcd(18, 12) = pgcd(12, 6)
12 = 2 *  6 + 0   → pgcd(12, 6)  = 6

pgcd(48, 18) = 6

Inverse de 5 modulo 14 :

d	1	2	3	4	5	6	7	8
5 * d	5	10	15	20	25	30	35	40
mod 14	5	10	1	6	11	2	7	12

→ inverse de 5 mod 14 = 3 (car 5 × 3 = 15 ≡ 1 mod 14)

---

Exercice 2 — Carré-multiplication

Calculer 4^13 mod 21 :

Étape 1 — Décomposition de 13 en binaire : 13 = 8 + 4 + 1 → 1101₂

Étape 2 — Carrés successifs modulo 21 :

calcul	mod 21
4¹	4
4² = 4×4	16
4⁴ = 16²=256	4
4⁸ = 4²=16	16

Étape 3 — Combinaison (13 = 8 + 4 + 1) : 4¹³ = 4⁸ × 4⁴ × 4¹ = 16 × 4 × 4 = 256 ≡ 4 mod 21

→ 4^13 mod 21 = 4

---

Exercice 3 — RSA à la main

Question 1 — Génération des clés (p=3, q=11, e=3) :

a) n = p × q = 3 × 11 = 33

b) φ(n) = (p−1)(q−1) = 2 × 10 = 20

c) Vérification : pgcd(e, φ) = pgcd(3, 20) = 1 ✓ (premiers entre eux)

d) Trouver d tel que e×d ≡ 1 mod φ (table d'essais) :

d	1	2	3	4	5	6	7
3 × d	3	6	9	12	15	18	21
mod 20	3	6	9	12	15	18	1

→ d = 7

e) Clé publique : (e, n) = (3, 33) Clé privée : (d, n) = (7, 33)

Question 2 — Chiffrement de M = 4 :

C = M^e mod n = 4³ mod 33 = 64 mod 33 = 31

Question 3 — Déchiffrement de C = 31 :

d = 7, décomposition : 7 = 4 + 2 + 1 → 111₂

calcul	mod 33
31¹	31
31² = 961	4
31⁴ = 4² = 16	16

31⁷ = 31⁴ × 31² × 31¹ = 16 × 4 × 31 = 1984 mod 33

1984 ÷ 33 = 60 reste 4 → M = 4 ✓

Question 4 (bonus) — Signature :

Alice signe avec sa clé privée (elle seule la possède). Bob vérifie avec la clé publique d'Alice (accessible à tous). Opération : S = M^d_Alice mod n_Alice, vérification : M = S^e_Alice mod n_Alice.

---

Exercice 4 — Diffie-Hellman en trinôme

Paramètres publics : p = 23, g = 5

Round 1 (honnête)

• a = 6, b = 8
• A = g^a mod p = 5^6 mod 23 = 8
• B = g^b mod p = 5^8 mod 23 = 16
• K_Alice = B^a mod p = 16^6 mod 23 = 4
• K_Bob = A^b mod p = 8^8 mod 23 = 4

→ Alice et Bob partagent bien le même secret K = 4 ✓

Round 2 (Eve MITM)

Eve choisit eA = 4, eB = 7

• Eve envoie EA = g^eA mod p = 5^4 mod 23 = 4 à Alice (se faisant passer pour Bob)
• Eve envoie EB = g^eB mod p = 5^7 mod 23 = 17 à Bob (se faisant passer pour Alice)
• K_Alice = EA^a mod p = 4^6 mod 23 = 2 (secret partagé Alice-Eve)
• K_Bob = EB^b mod p = 17^8 mod 23 = 18 (secret partagé Bob-Eve)
• K_Eve côté Alice = A^eA mod p = 8^4 mod 23 = 2 ✓
• K_Eve côté Bob = B^eB mod p = 16^7 mod 23 = 18 ✓

Alice et Bob ont des secrets différents (2 ≠ 18). Eve possède les deux et peut déchiffrer toutes les communications.

Ce qui manque pour empêcher l'attaque : Un mécanisme d'authentification des clés publiques — typiquement une infrastructure à clés publiques (PKI) avec des certificats signés par une autorité de confiance. Sans ça, rien ne prouve qu'un A reçu vient bien d'Alice et pas d'Eve.

---

Exercice 5 — Mini-hash

H(mot) = (somme des positions des lettres) mod 16, avec A=1, B=2, ..., Z=26.

• H("CHAT") = (3+8+1+20) mod 16 = 32 mod 16 = 0
• H("OURS") = (15+21+18+19) mod 16 = 73 mod 16 = 9
• H("CRYPTO") = (3+18+25+16+20+15) mod 16 = 97 mod 16 = 1

Collision trouvée : H("AAA") = (1+1+1) mod 16 = 3 = H("AAQ") = (1+1+17) mod 16 = 3

Trois raisons pour lesquelles c'est inutilisable :

1. Trop de collisions facilement trouvables : avec seulement 16 valeurs possibles (mod 16), en moyenne 1 mot sur 16 partage le même hash — trivial à exploiter.
2. Pas de résistance à la seconde préimage : connaissant un mot M et son hash H(M), il est trivial de construire un autre mot M' avec H(M') = H(M) en ajoutant/retirant des lettres dont les positions se compensent.
3. Pas d'effet avalanche : changer une seule lettre ne modifie le hash que de la valeur de cette lettre (±1 à ±26 mod 16). Une vraie fonction de hachage doit rendre le hash totalement imprévisible après tout changement, même minime.

---

Exercices sur PC

Exercice 6 — Le mail de ton ami

SHA-256 de lettre.txt     : ece55d55d3b306516d50a4111475d0c3ef3ab75266fe4fd6fc63ef1faff5eadc
SHA-256 de lettre-faux.txt: 90cf10500206ced968d86639d7ee3cc2791bd721e23ed49a0723c0392e322a03
Hash annoncé dans le mail : ece55d55d3b306516d50a4111475d0c3ef3ab75266fe4fd6fc63ef1faff5eadc

Lequel ton ami a-t-il envoyé ? lettre.txt (rendez-vous à 14h00) — son hash correspond exactement au hash annoncé dans le mail.

Si Eve intercepte tout (fichier + hash) : Non, on ne pourrait pas détecter la fraude. Eve peut modifier la pièce jointe ET remplacer le hash dans le corps du mail par celui du fichier modifié. Comme le hash voyage dans le même canal non authentifié, rien ne garantit qu'il provient bien de Marc.

Ce qui manque : Une signature numérique — Marc doit signer le hash avec sa clé privée. Le destinataire peut alors vérifier avec la clé publique de Marc que le hash n'a pas été remplacé par Eve (voir exercice 8).

---

Exercice 7 — RSA avec OpenSSL

# Générer la clé privée RSA 2048 bits
openssl genpkey -algorithm RSA -out priv.pem -pkeyopt rsa_keygen_bits:2048

# Extraire la clé publique
openssl rsa -in priv.pem -pubout -out pub.pem

# Inspecter (n, e, d, p, q)
openssl rsa -in priv.pem -text -noout | head -30

# Chiffrer
echo "Rendez-vous mardi a 14h00." > rdv.txt
openssl pkeyutl -encrypt -pubin -inkey pub.pem -in rdv.txt -out rdv.bin

# Déchiffrer
openssl pkeyutl -decrypt -inkey priv.pem -in rdv.bin

Taille de rdv.txt : 27 octets Taille de rdv.bin : 256 octets

Pourquoi ? RSA 2048 bits produit toujours un chiffré de taille fixe égale à la taille de la clé : 2048 bits = 256 octets, quelle que soit la taille du message d'entrée. C'est une propriété fondamentale du chiffrement asymétrique : le chiffré ne révèle pas la longueur du message original.

---

Exercice 8 — Signature numérique

# Signer
openssl dgst -sha256 -sign priv.pem -out rdv.sig rdv.txt
# Vérifier
openssl dgst -sha256 -verify pub.pem -signature rdv.sig rdv.txt
# → Verified OK

# Modifier et re-vérifier
sed -i 's/14h00/16h00/' rdv.txt
openssl dgst -sha256 -verify pub.pem -signature rdv.sig rdv.txt
# → Verification failure

Verdict après modification : Verification failure

Pourquoi Eve ne peut pas fabriquer une nouvelle signature valide ? La signature est calculée avec la clé privée du signataire. Eve ne possède que la clé publique — elle peut vérifier des signatures mais pas en créer. Fabriquer une signature valide sans la clé privée est computationnellement impossible avec RSA 2048 bits.

Si Marc avait signé son mail : Eve aurait pu modifier la pièce jointe, mais la signature du hash original n'aurait plus été valide pour le fichier modifié. Le destinataire aurait détecté la fraude en vérifiant la signature avec la clé publique de Marc.

Marc a besoin de 2 clés : sa clé privée (gardée secrète) et sa clé publique (partagée avec tous ses correspondants). Il partage uniquement la clé publique.

---

Exercice 9 — Authentification SSH par challenge

Étape 3 — Ce que calcule Alice : Alice calcule la signature σ = Sign(r, priv_Alice) = r^d mod n (chiffrement du challenge r avec sa clé privée).

Étape 5 — Ce que vérifie le serveur : Le serveur calcule r' = Verify(σ, pub_Alice) = σ^e mod n et vérifie que r' == r (le challenge initial).

# Simulation OpenSSL
openssl rand -hex 32 > challenge.txt
openssl dgst -sha256 -sign priv.pem -out challenge.sig challenge.txt
openssl dgst -sha256 -verify pub.pem -signature challenge.sig challenge.txt

Verdict de la simulation : Verified OK

Pourquoi le challenge doit-il être aléatoire (protection contre le rejeu) ? Si le challenge était toujours le même, Eve pourrait enregistrer une paire (challenge, signature) lors d'une connexion légitime et la rejouer plus tard pour s'authentifier à la place d'Alice. Comme le challenge est aléatoire et différent à chaque connexion, l'ancienne signature ne correspond plus au nouveau challenge — l'attaque par rejeu est impossible.

Deux avantages d'une clé SSH par rapport à un mot de passe :

1. Rien de secret ne circule sur le réseau : avec un mot de passe, celui-ci (ou son hash) transite et peut être intercepté. Avec SSH par clé, seule la signature d'un challenge aléatoire circule — elle ne permet pas de retrouver la clé privée.
2. Un serveur compromis n'apprend rien d'utile : un serveur malveillant qui stocke les credentials ne récupère que la clé publique (déjà connue de tous), contre un mot de passe réutilisable sur d'autres services.

---

Difficultés rencontrées

• Le calcul RSA à la main (déchiffrement 31^7 mod 33) nécessite de bien appliquer la méthode carré-multiplication étape par étape pour ne pas manipuler de grands nombres.
• Dans l'attaque MITM Diffie-Hellman, il faut bien distinguer les deux secrets d'Eve (eA et eB) et les deux clés partagées qu'elle établit (une avec Alice, une avec Bob).
• Le mini-hash mod 16 produit H("CHAT") = 0 : un hash nul n'est pas une erreur, c'est simplement une collision sur 0 facilement trouvable (ex: H("P") = 16 mod 16 = 0 aussi).