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 — Carre-multiplication

• 4^13 mod 21 = 4
• Etapes du calcul :
  • 13 = 8 + 4 + 1
  • 4^1 mod 21 = 4
  • 4^2 = 16 mod 21 = 16
  • 4^4 = 16^2 = 256 mod 21 = 4
  • 4^8 = 4^2 = 16 mod 21 = 16
  • 4^13 = 4^8 × 4^4 × 4^1 = 16 × 4 × 4 = 256
  • 256 mod 21 = 4

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

• n = 33
• phi = 20
• d = 7
• Verification : pgcd(3, 20) = 1 et 3 × 7 = 21 = 1 mod 20
• Cle publique : (33, 3)
• Cle privee : (33, 7)
• Chiffrement de M=4 : C = 4^3 mod 33 = 64 mod 33 = 31
• Dechiffrement de C=31 :
  • 7 = 4 + 2 + 1
  • 31^1 mod 33 = 31
  • 31^2 = 961 mod 33 = 4
  • 31^4 = 4^2 = 16 mod 33 = 16
  • 31^7 = 31^4 × 31^2 × 31^1 = 16 × 4 × 31 = 1984
  • 1984 mod 33 = 4
  • M = 4
• Bonus signature : Alice signe avec sa cle privee. Bob verifie avec la cle publique d'Alice.

Exercice 4 — Diffie-Hellman en trinome (p=23, g=5)

Round 1 — echange honnete (Eve passive)

• a = 6, b = 9
• A = g^a mod p = 5^6 mod 23 = 8
• B = g^b mod p = 5^9 mod 23 = 11
• K commun = 9
• Verification : Alice calcule B^a mod p = 11^6 mod 23 = 9 et Bob calcule A^b mod p = 8^9 mod 23 = 9.

Round 2 — Eve fait du MITM

• eA = 4, eB = 7
• Ce que Eve envoie a Alice = g^eA mod 23 = 5^4 mod 23 = 4
• Ce que Eve envoie a Bob = g^eB mod 23 = 5^7 mod 23 = 17
• K cote Alice = 4^6 mod 23 = 2
• K cote Bob = 17^9 mod 23 = 7
• Eve calcule de son cote : K avec Alice = A^eA mod 23 = 8^4 mod 23 = 2, K avec Bob = B^eB mod 23 = 11^7 mod 23 = 7
• Alice et Bob ont-ils le meme secret ? Non
• Que manque-t-il dans le protocole pour empecher l'attaque ? Il manque une authentification des valeurs echangees, par exemple une signature numerique ou un certificat, pour prouver que la valeur recue vient bien de la bonne personne.

Exercice 5 — Mini-hash maison

• H("CHAT") = 0
• H("OURS") = 9
• H("CRYPTO") = 1
• Collision trouvee : H("ABC") = H("AAD") = 6
• Trois raisons pour lesquelles cette fonction est inutilisable :
  1. Le resultat est trop court, car il n'y a que 16 valeurs possibles.
  2. Les collisions sont tres faciles a trouver.
  3. La fonction est trop simple et previsible, donc on peut fabriquer volontairement un autre message avec le meme hash.

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 envoye ? messages/lettre.txt, car son hash correspond a celui annonce dans le mail.
• Si Eve intercepte le mail entier (fichier + hash), peux-tu detecter la fraude ? Non, pas forcement. Si Eve peut modifier le fichier et aussi remplacer le hash dans le mail, le destinataire verra seulement que le nouveau fichier correspond au nouveau hash.
• Qu'est-ce qui manque dans ce protocole pour garantir l'authenticite ? Il manque une signature numerique, afin de prouver que le hash vient bien de Marc et pas d'Eve.

Exercice 7 — RSA avec OpenSSL

• Taille de rdv.bin = 256 octets, comparaison avec rdv.txt : rdv.txt est beaucoup plus petit.
• Pourquoi cette taille ? La cle RSA fait 2048 bits, donc le resultat chiffre a la taille du module RSA : 2048 bits = 256 octets.

Exercice 8 — Signature numerique

• Verdict d'openssl dgst -verify sur le fichier original : Verified OK
• Verdict apres modification d'1 caractere de rdv.txt : Verification failure
• Pourquoi Eve ne peut-elle pas fabriquer une nouvelle signature valide pour le fichier modifie ? Elle ne possede pas la cle privee. Elle peut modifier le fichier, mais elle ne peut pas produire une signature qui sera acceptee par la cle publique.
• Si Marc avait signe son mail (exercice 6), qu'est-ce qui changerait ? Eve ne pourrait pas modifier le fichier et le hash sans etre detectee, car la signature ne serait plus valide. Marc aurait besoin d'une cle privee pour signer et il partagerait sa cle publique pour verifier.

Exercice 9 — Authentification SSH par challenge

• Etape 3 — ce que calcule Alice : S = N^d mod n, c'est-a-dire la signature du challenge avec sa cle privee.
• Etape 5 — ce que verifie le serveur : il verifie la signature avec la cle publique d'Alice, en controlant que S^e mod n redonne bien le challenge N.
• Verdict de la simulation OpenSSL (openssl dgst -verify sur le challenge) : Verified OK
• Pourquoi le challenge doit-il etre aleatoire (protection contre le rejeu) ? Si le challenge etait toujours le meme, Eve pourrait enregistrer une ancienne signature valide et la renvoyer plus tard pour se faire passer pour Alice. Avec un challenge aleatoire, l'ancienne signature ne correspond plus au nouveau challenge.
• Deux avantages d'une cle SSH par rapport a un mot de passe :
  1. Le mot de passe ne circule jamais sur le reseau : Alice prouve son identite en signant un challenge.
  2. Si le serveur est compromis, il ne stocke que la cle publique, donc l'attaquant ne recupere pas un secret equivalent a un mot de passe.

Difficultes rencontrees

La principale difficulte etait de bien distinguer integrite et authenticite. Un hash seul permet de verifier qu'un fichier correspond a une empreinte, mais il ne prouve pas qui a produit cette empreinte. Pour l'authenticite, il faut une signature numerique ou un mecanisme equivalent.