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 (4^1, 4^2, 4^4, 4^8 mod 21, puis combinaison) : 4^1 = 4 4^2 = 16 4^4 = 1616 = 256 = 4 mod 21 4^8 = 44 = 16

4^13 = 4^8 * 4^4 * 4^1 = 16 * 4 * 4 = 256 = 4 mod 21

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

• n = 33

• phi = 20

• d = 7

• Chiffrement de M=4 : C = 31

• Dechiffrement de C=31 : etapes du calcul de 31^7 mod 33, puis M = 4 31^1 = 31 31^2 = 961 = 4 mod 33 31^4 = 4*4 = 16 31^7 = 31^4 * 31^2 * 31^1 = 31 * 4 * 16 = 4 mod 33

• Bonus signature : qui signe avec quoi ? Qui verifie avec quoi ?

Alice signe son message en le chiffrant avec sa clé privée, Bob le déchiffre avec la clé publique d'Alice

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

Round 1 — echange honnete (Eve passive)

• a = 3, b = 4
• A = g^a mod p = 10
• B = g^b mod p = 4
• K commun = 18

Round 2 — Eve fait du MITM

• eA = 2, eB = 5
• Ce que Eve envoie a Alice = 2
• Ce que Eve envoie a Bob = 20
• K cote Alice = 8
• K cote Bob = 12
• Eve calcule de son cote : K avec Alice = 8 , K avec Bob = 12
• Alice et Bob ont-ils le meme secret ? Non
• Que manque-t-il dans le protocole pour empecher l'attaque ? Chiffrement asymétrique (clé publique, clé privée)

Exercice 5 — Mini-hash maison

• H("CHAT") = 0
• H("OURS") = 9
• H("CRYPTO") = 1
• Collision trouvee : H("CHIEN") = H("NICHE") = 7
• Trois raisons pour lesquelles cette fonction est inutilisable :
  1. Elle ne prend pas en compte l'ordre des lettres
  2. Il y a trop peu de hash donc les collisions sont très fréquentes
  3. Elle n'encode que des messages avec des lettres (et pas avec des nombres ou symboles)

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 ? Mon ami a envoyé le premier message lettre.txt, celui qui me demande de venir à 14h.
• Si Eve intercepte le mail entier (fichier + hash), peux-tu detecter la fraude ? Non car nous n'avons aucune méthode pour savoir si c'est mon ami qui a envoyé le message
• Qu'est-ce qui manque dans ce protocole pour garantir l'authenticite ? Un système de chiffrement asymétrique pour que l'on puisse signer les messages.

Exercice 7 — RSA avec OpenSSL

• Taille de rdv.bin = 256 octets (comparaison avec rdv.txt) : 27 octets
• Pourquoi cette taille ? Parce que le message a été hash, ce qui lui donne une taille fixe.

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 ? Parce que la signature authentifie l'auteur du message, sans la clé privée de l'auteur elle ne peut pas changer la signature
• Si Marc avait signe son mail (exercice 6), qu'est-ce qui changerait ? L'authenticité de son message serait vérifiée

Exercice 9 — Authentification SSH par challenge

• Etape 3 — ce que calcule Alice : S = N^d mod n
• Etape 5 — ce que verifie le serveur : S^e mod 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) ?
• Deux avantages d'une cle SSH par rapport a un mot de passe :
  1. Attaque par MITM impossible
  2. Bases de données sécurisées (impossibilité de trouver les mots de passes même s'ils fuitent)

Difficultes rencontrees

aucune