TD3 — RSA, Diffie-Hellman & hachage

Exercice 1 — Échauffement

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

13 en binaire = 1101 = 8 + 4 + 1

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

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 = 3 × 11 = 33 phi = 2 × 10 = 20 d = 7 (car 3 × 7 = 21 ≡ 1 mod 20) clé publique : (n=33, e=3) clé privée : (n=33, d=7)

Chiffrement de M=4 : C = 4^3 mod 33 = 64 mod 33 = 31

Déchiffrement de C=31 : 31^1 = 31 31^2 = 961 mod 33 = 4 31^4 = 4² mod 33 = 16 31^7 = 31^4 × 31^2 × 31^1 = 16 × 4 × 31 mod 33 = 4

Bonus signature : Alice signe avec sa clé privée d, Bob vérifie avec la clé publique e d'Alice.

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

Round 1 — échange honnête

a = 3, b = 4 A = 5^3 mod 23 = 10 B = 5^4 mod 23 = 4 K_Alice = 4^3 mod 23 = 18 K_Bob = 10^4 mod 23 = 18 Secret commun K = 18

Round 2 — attaque MITM (eA=2, eB=5)

Eve envoie EA = 5^2 mod 23 = 2 à Alice (à la place de B) Eve envoie EB = 5^5 mod 23 = 20 à Bob (à la place de A) K_Alice = 2^3 mod 23 = 8 K_Bob = 20^4 mod 23 = 12 Eve calcule K_Eve_A = 10^2 mod 23 = 8 et K_Eve_B = 4^5 mod 23 = 12

Alice et Bob n'ont pas le même secret (8 ≠ 12). Eve possède les deux et peut tout déchiffrer.

Ce qui manque : un mécanisme d'authentification des parties (certificats, signatures) pour s'assurer qu'on parle bien à Alice ou Bob et non à un intermédiaire.

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 : H("CHIEN") = H("NICHE") = 7 (39 mod 16 = 7 dans les deux cas)

Trois raisons pour lesquelles cette fonction est inutilisable :

1. Elle ignore l'ordre des lettres : deux anagrammes produisent le même hash.
2. L'espace de sortie est trop petit (16 valeurs) : les collisions sont quasi-garanties.
3. Elle n'est pas à sens unique : à partir d'un hash, construire un mot valide est trivial.

Exercice 6 — Le mail de ton ami

SHA-256 de lettre.txt = ece55d55d3b306516d50a4111475d0c3ef3ab75266fe4fd6fc63ef1faff5eadc SHA-256 de lettre-faux.txt = 90cf10500206ced968d86639d7ee3cc2791bd721e23ed49a0723c0392e322a03

Mon ami a envoyé lettre.txt (hash correspondant, rendez-vous à 14h).

Si Eve intercepte le mail entier, non : elle peut modifier la pièce jointe et remplacer le hash dans le corps du mail en même temps. Le destinataire ne voit qu'un hash cohérent avec le fichier reçu.

Ce qui manque : Marc devrait signer numériquement son hash avec sa clé privée. On pourrait alors vérifier avec sa clé publique que le contenu vient bien de lui.

Exercice 7 — RSA avec OpenSSL

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

rdv.bin fait toujours 256 octets car le chiffré RSA a la taille du module n (2048 bits = 256 octets), quelle que soit la taille du message d'origine. C'est une propriété intrinsèque de RSA.

Exercice 8 — Signature numérique

Verdict sur le fichier original : Verified OK Verdict après modification : Verification Failure

Eve ne peut pas fabriquer une nouvelle signature car elle ne possède que la clé publique. La signature se calcule avec la clé privée, qu'elle n'a pas.

Si Marc avait signé son mail, Eve n'aurait pas pu modifier la pièce jointe sans invalider la signature. Marc n'a besoin que d'une paire de clés : il garde sa clé privée et partage sa clé publique.

Exercice 9 — Authentification SSH par challenge

Étape 3 — Alice calcule : S = c^d mod n (signature du challenge avec sa clé privée) Étape 5 — Le serveur vérifie : S^e mod n == c (avec la clé publique d'Alice)

Verdict de la simulation OpenSSL : Verified OK

Pourquoi le challenge doit être aléatoire : si le challenge était fixe, Eve pourrait enregistrer une paire (challenge, signature) légitime et la rejouer à la prochaine connexion. Avec un challenge aléatoire, la signature capturée est inutilisable car le prochain challenge sera différent. C'est la protection contre les attaques par rejeu (replay attack).

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

1. Rien de secret ne circule sur le réseau : seule la signature d'un challenge transite, pas la clé privée.
2. Un serveur compromis n'apprend rien : il ne stocke que la clé publique, inutilisable sans la clé privée.

Difficultés rencontrées

Aucune.