TD3 — RSA, Diffie-Hellman & hachage

Exercices sur papier

Exercice 1 — Echauffement

• Premiers entre 1 et 30 : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
• pgcd(20, 9) = 1
• pgcd(48, 18) = 6
• inverse de 5 mod 14 = 3

Exercice 2 — Carré-multiplication

• 4^13 mod 21 = 4

Détail du calcul :

13 en binaire = 1101₂ = 8 + 4 + 1

calcul	mod 21
4^1	4
4^2 = 16	16
4^4 = 16²	4
4^8 = 4²	16

Combinaison : 4^13 = 4^8 × 4^4 × 4^1 = 16 × 4 × 4 = 256 mod 21 = 4

---

Exercice 3 — RSA à la main (p=3, q=11, e=3)

• n = 33
• phi = (3−1)(11−1) = 20
• Vérification gcd(e, phi) : gcd(3, 20) = 1
• d = 7
• Clé publique : (e=3, n=33)
• Clé privée : (d=7, n=33)

C = 4^3 mod 33 = 64 mod 33 = 31

Déchiffrement de C=31 — tableau carré-multiplication (d=7 = 4+2+1) :

calcul	mod 33
31^1	31
31^2 = 961	4
31^4 = 4²= 16	16

31^7 = 31^4 × 31^2 × 31^1 = 16 × 4 × 31 = 1984 mod 33 = 4✓

Bonus — Signature : Alice signe avec sa clé privée (d, n) : S = M^d mod n. Bob vérifie avec la clé publique d'Alice (e, n): M' = S^e mod n, et compare à M.

---

Exercice 4 — Diffie-Hellman en trinôme (p=23, g=5)

Round 1 — échange honnête (Eve passive)

• a = 6, b = 4
• A = g^a mod p = 5^6 mod 23 = 8
• B = g^b mod p = 5^4 mod 23 = 4
• K commun = B^a mod p = A^b mod p = 2

Round 2 — Eve fait du MITM

• eA = 3, eB = 5
• Ce qu'Eve envoie à Alice : EA = g^eA mod p = 5^3 mod 23 = 10
• Ce qu'Eve envoie à Bob : EB = g^eB mod p = 5^5 mod 23 = 20
• K côté Alice = EA^a mod p = 10^6 mod 23 = 6
• K côté Bob = EB^b mod p = 20^4 mod 23 = 12
• Eve calcule de son côté :
  • K avec Alice = A^eA mod p = 8^3 mod 23 = 6
  • K avec Bob = B^eB mod p = 4^5 mod 23 = 12
• Alice et Bob ont-ils le même secret ? Non (Alice croit partager 6 avec Bob, Bob croit partager 12 avec Alice).
• Que manque-t-il ? L'authentification des clés publiques : rien ne prouve à Alice que A vient vraiment de Bob et non d'Eve. Un mécanisme de certificats (PKI) ou de vérification hors-bande est nécessaire.

---

Exercice 5 — Mini-hash maison

• 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("CHAT") = H("LOUP") = 0 (LOUP : 12+15+21+16 = 64, 64 mod 16 = 0)

• Trois raisons pour lesquelles cette fonction est inutilisable :

  1. Plage de sortie trop petite (16 valeurs) : par le paradoxe des anniversaires, une collision est garantie dès 17 mots testés au hasard.
  2. Commutativité : H dépend uniquement de la somme des lettres, donc H("CHAT") = H("TACH") = H("ATCH"). Il est trivial de fabriquer un autre message avec le même hash.
  3. Pas de résistance à la préimage : connaissant h, on construit immédiatement un mot M tel que H(M) = h (ex. h lettres "A" : H("AA...A") = h mod 16).

---

Exercices sur PC

Exercice 6 — Le mail de ton ami

• SHA-256 de messages/lettre.txt = ece55d55d3b306516d50a4111475d0c3ef3ab75266fe4fd6fc63ef1faff5eadc
• SHA-256 de messages/lettre-faux.txt = 90cf10500206ced968d86639d7ee3cc2791bd721e23ed49a0723c0392e322a03
• Lequel ton ami a-t-il vraiment envoyé ? lettre.txt — son hash correspond à celui du mail.
• Si Eve intercepte le mail entier (fichier + hash), peux-tu détecter la fraude ? Non : Eve peut modifier le fichier et remplacer le hash dans le corps du mail par celui du fichier modifié. Le destinataire ne verra aucune différence.
• Qu'est-ce qui manque dans ce protocole pour garantir l'authenticité ? Une signature numérique : Marc doit signer le hash avec sa clé privée. Seule sa clé publique (connue de tous) peut vérifier la signature, ce qui empêche Eve de forger un hash valide sans la clé privée de Marc.

---

Exercice 7 — RSA avec OpenSSL

• Taille de rdv.bin = 256 octets (vs ~28 octets pour rdv.txt)
• Pourquoi cette taille ? RSA chiffre en blocs de la taille du module : avec une clé 2048 bits, chaque opération produit exactement 2048/8 = 256 octets, quelle que soit la taille du message en clair.

---

Exercice 8 — Signature numérique

• Verdict d'openssl dgst -verify sur le fichier original : Verified OK
• Verdict après modification d'1 caractère de rdv.txt : Verification Failure
• Pourquoi Eve ne peut-elle pas fabriquer une nouvelle signature valide pour le fichier modifié ? La signature est S = hash(rdv.txt)^d mod n. Pour recalculer S avec un nouveau hash, il faut d, la clé privée de l'expéditeur. Eve ne la possède pas, et la retrouver à partir de la clé publique reviendrait à factoriser n (problème réputé intraitable pour 2048 bits).
• Si Marc avait signé son mail (exercice 6), qu'est-ce qui changerait ? Eve ne pourrait plus remplacer la pièce jointe sans invalider la signature. Le destinataire détecterait immédiatement la falsification en vérifiant avec la clé publique de Marc.

---

Exercice 9 — Authentification SSH par challenge

• Étape 3 — ce que calcule Alice : S = sign(challenge, clé_privée) = hash(challenge)^d mod n
• Étape 5 — ce que vérifie le serveur : S^e mod n == hash(challenge) avec la clé publique d'Alice, puis compare au challenge envoyé à l'étape 2.
• Verdict de la simulation OpenSSL (openssl dgst -verify sur le challenge) : Verified OK
• Pourquoi le challenge doit-il être aléatoire (protection contre le rejeu) ? Si le challenge était fixe, Eve pourrait enregistrer (challenge, S) d'une session légitime et le rejouer à la prochaine connexion pour se faire passer pour Alice. Un challenge aléatoire différent à chaque connexion rend la signature capturée inutilisable.
• Deux avantages d'une clé SSH par rapport à un mot de passe :
  1. Rien de secret ne transite sur le réseau : seule la signature (calculée localement) est envoyée ; un attaquant qui intercepte le trafic ne peut pas rejouer ou deviner la clé privée.
  2. Immunité au vol de base de données : le serveur ne stocke que la clé publique (non secrète). Même compromis, il ne révèle rien qui permette de se connecter ailleurs ou de retrouver la clé privée.

Difficultés rencontrées