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 mod 21 = 4.
• 4^2 = 16, donc 4^2 mod 21 = 16.
• 4^4 = 16^2 = 256, et 256 mod 21 = 4.
• 4^8 = 4^2 = 16, donc 4^8 mod 21 = 16.
• Comme 13 = 8 + 4 + 1 -> 4^13 = 4^8 × 4^4 × 4^1.
• -> 4^13 mod 21 = 16 × 4 × 4 mod 21 = 256 mod 21 = 4.

Exercice 3 — RSA a la main

• n = 33
• phi = 20
• d = 7
• Chiffrement de M=4 : C = 31
• Dechiffrement de C=31 : etapes du calcul de 31^7 mod 33 -> M = 4
• Bonus signature : qui signe avec quoi ? Qui verifie avec quoi ? Alice signe avec sa cle privee. Bob verifie la signature avec la cle publique d'Alice.

Exercice 4 — Diffie-Hellman en trinome

Round 1 (honnete)

• a = 3, b = 9
• A = g^a mod p = 10
• B = g^b mod p = 11
• K commun = 20

Round 2 (Eve MITM)

• eA = 3, eB = 9
• K_Alice = 11
• K_Bob = 19
• Alice et Bob ont-ils le meme secret ? Non, Alice obtient 11 et Bob obtient 19.
• Que manque-t-il pour empecher l'attaque ? Il manque une authentification. Alice et Bob doivent verifier que les valeurs recues viennent vraiment l'un de l'autre, par exemple avec une signature numerique ou un certificat.

Exercice 5 — Mini-hash maison

• H("CHAT") = 0
• H("OURS") = 9
• H("CRYPTO") = 1
• Collision trouvee : H("IEA") = H("HCD") = 6
• Trois raisons pour lesquelles cette fonction est inutilisable :
  1. Que 16 valeurs possibles -> collisions sont tres frequentes.
  2. Collisions sont faciles a fabriquer -> il suffit de garder la meme somme de lettres.
  3. Ordre des lettres pas pris en compte -> plusieurs mots ou permutations peuvent donner le meme hash.

Exercices sur PC

Exercice 6 — Le mail de ton ami

• SHA-256 de lettre.txt = ece55d55d3b306516d50a4111475d0c3ef3ab75266fe4fd6fc63ef1faff5eadc
• SHA-256 de lettre-faux.txt = 90cf10500206ced968d86639d7ee3cc2791bd721e23ed49a0723c0392e322a03
• Lequel ton ami a-t-il envoye ? lettre.txt -> son SHA-256 correspond au hash donne dans le mail.
• Si Eve intercepte le mail entier (fichier + hash), peux-tu detecter la fraude ?Pourquoi? Non. Si Eve peut modifier a la fois le fichier et le hash dans le mail, le destinataire ne peut pas detecter la fraude avec un simple hash, car le hash modifie correspondra au fichier modifie.
• Que manque-t-il ? Il manque une signature numerique. Marc devrait signer le hash ou le fichier avec sa cle privee, et le destinataire verifierait avec la cle publique de Marc.

Exercice 7 — RSA avec OpenSSL

• Taille de rdv.bin = 256 octets : rdv.txt = 27 octets.
• Pourquoi cette taille ? rdv.bin fait 256 octets car la cle RSA utilisee fait 2048 bits -> 2048 bits = 256 octets. Avec RSA, le bloc chiffre a la taille du module n

Exercice 8 — Signature numerique

• 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 ? Eve ne peut pas fabriquer une nouvelle signature valide car elle ne possede pas la cle privee de Marc. Elle peut modifier le fichier, mais elle ne peut pas produire une signature correcte pour ce nouveau contenu. La cle publique permet seulement de verifier une signature, pas d'en creer une.
• Si Marc avait signe son mail (exercice 6), qu'est-ce qui changerait ? Eve ne pourrait pas modifier le mail sans se faire detecter. En modifiant la piece jointe ou le hash, la signature ne correspondrait plus. Le destinataire pourrait verifier avec la cle publique de Marc que le message vient bien de lui et qu'il n'a pas ete modifie.

Exercice 9 — Authentification SSH par challenge

• Etape 3 (ce que calcule Alice) : S = N^d mod n
• Etape 5 (ce que verifie le serveur) : le serveur calcule S^e mod n, puis compare le resultat avec le challenge N initial.
• Verdict de la simulation OpenSSL : Verified OK
• Pourquoi le challenge doit-il etre aleatoire ? (replay attack) Le challenge doit etre aleatoire pour empecher Eve de reutiliser une ancienne signature capturee. Si le challenge etait toujours le meme, Eve pourrait rejouer l'ancien couple challenge/signature. Comme le challenge change a chaque connexion, une ancienne signature ne correspond plus au nouveau challenge.
• Deux avantages d'une cle SSH par rapport a un mot de passe :
  1. La cle privee ne circule jamais sur le reseau : Alice envoie seulement une signature du challenge.
  2. Le serveur ne stocke que la cle publique. Si le serveur est compromis, l'attaquant ne recupere pas la cle privee d'Alice.

Difficultes rencontrees