TD3 — RSA, Diffie-Hellman & hachage¶
Duree : 2h | Par groupe
Prerequis : CM3 — Cryptographie asymetrique
Rendu : depot Forgejo
Outils : papier-crayon, terminal Linux avec openssl et sha256sum
Objectifs¶
- Maitriser la methode carre-multiplication pour calculer une exponentiation modulaire a la main
- Calculer RSA a la main sur petits entiers (generation, chiffrement, dechiffrement, signature)
- Realiser un echange Diffie-Hellman en trinome, puis observer une attaque MITM
- Comprendre les fonctions de hachage par un mini-hash maison
- Manipuler OpenSSL : RSA, hash, signature, et reagir a une attaque par interception
Plan¶
- Echauffement papier — nombres premiers, pgcd, inverse modulaire
- Methode carre-multiplication — l'outil cle pour RSA a la main
- RSA a la main — chiffrer / dechiffrer / signer
- Diffie-Hellman en trinome — echange honnete + attaque MITM
- Mini-hash maison — sentir les proprietes d'une fonction de hachage
- PC : le mail de ton ami — verifier l'integrite avec SHA-256
- PC : OpenSSL — generer des cles, chiffrer, signer, verifier
- PC : authentification SSH par challenge — la signature comme preuve d'identite
Exercices sur papier¶
A la main
Les exercices 1 a 5 se font sans ordinateur. Les calculs restent volontairement petits.
Exercice 1 — Echauffement : nombres premiers¶
Sous-partie A — Crible
Encercler tous les nombres premiers entre 1 et 30.
Sous-partie B — PGCD par l'algorithme d'Euclide
L'algorithme d'Euclide calcule le PGCD (plus grand commun diviseur) : \(\gcd(a, b) = \gcd(b,\; a \bmod b)\), et on s'arrete quand le reste vaut 0.
Exemple : \(\gcd(35, 14)\) :
A vous : calculer \(\gcd(20, 9)\) et \(\gcd(48, 18)\).
Sous-partie C — Inverse modulaire par essais
L'inverse modulaire de \(a\) modulo \(n\) est l'entier \(d\) tel que \(a \cdot d \equiv 1 \pmod{n}\).
Trouver l'inverse de 3 modulo 20 : on essaie \(d = 1, 2, 3, \ldots\) jusqu'a ce que \(3 \cdot d \bmod 20 = 1\).
| d | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 3 * d | 3 | 6 | 9 | 12 | 15 | 18 | 21 |
| mod 20 | 3 | 6 | 9 | 12 | 15 | 18 | 1 |
→ inverse de 3 mod 20 = 7.
A vous : trouver l'inverse de 5 modulo 14 par la meme methode.
Exercice 2 — Methode carre-multiplication¶
L'objectif : calculer une exponentiation modulaire \(M^e \bmod n\) sans jamais manipuler de grands nombres, grace a la methode dite square-and-multiply (exponentiation rapide).
Idee : on decompose l'exposant en somme de puissances de 2 (sa representation binaire), on calcule les carres successifs modulo \(n\), puis on multiplie les bons termes.
Exemple complet : \(8^7 \bmod 33\)
Etape 1 — Decomposer 7 en binaire :
\(7 = 4 + 2 + 1\) (ou : \(7 = 111_2\) en binaire)
Etape 2 — Calculer les carres successifs toujours modulo 33 :
| calcul | mod 33 | |
|---|---|---|
| \(8^1\) | 8 | 8 |
| \(8^2\) | \(8 \times 8 = 64\) | 31 |
| \(8^4\) | \(31 \times 31 = 961\) | 4 |
Etape 3 — Combiner : \(8^7 = 8^4 \times 8^2 \times 8^1 = 4 \times 31 \times 8 = 992\). Et \(992 \bmod 33 = 2\).
→ \(\boxed{8^7 \bmod 33 = 2}\).
Astuce numerique
A chaque etape, on reduit modulo 33 avant de multiplier. Les nombres ne depassent jamais ~1000.
A vous : calculer \(4^{13} \bmod 21\) par cette methode.
Indices : \(13 = 8 + 4 + 1\) (en binaire \(1101_2\)). Calculer \(4^1\), \(4^2\), \(4^4\), \(4^8\) modulo 21, puis combiner.
Exercice 3 — RSA a la main¶
Donnees : Bob choisit \(p = 3\), \(q = 11\), \(e = 3\).
Question 1 — Generation des cles
Calculer pas a pas :
a) \(n = p \times q = \;?\) b) \(\varphi(n) = (p-1)(q-1) = \;?\) c) Verifier que \(\gcd(e, \varphi(n)) = 1\) d) Trouver \(d\) tel que \(e \cdot d \equiv 1 \pmod{\varphi(n)}\) (table d'essais comme exo 1.C) e) Ecrire la cle publique \((n, e)\) et la cle privee \((n, d)\)
Question 2 — Alice chiffre \(M = 4\)
Alice veut envoyer \(M = 4\) a Bob. Calculer \(C = M^e \bmod n\) :
Question 3 — Bob dechiffre \(C = 31\)
Avec la cle privee \((33, 7)\), calculer \(M = C^d \bmod n = 31^7 \bmod 33\) par carre-multiplication.
Decomposer : \(7 = 4 + 2 + 1\). Remplir le tableau :
| calcul | mod 33 | |
|---|---|---|
| \(31^1\) | 31 | ? |
| \(31^2\) | \(31 \times 31 = ?\) | ? |
| \(31^4\) | \((31^2)^2 = ?\) | ? |
Puis \(31^7 = 31^4 \times 31^2 \times 31^1 = ? \times ? \times ? = \;?\) (mod 33 = ?)
Question 4 (bonus) — Signature
Si Alice voulait signer \(M = 4\) (au lieu de le chiffrer), avec quelle cle le ferait-elle ? Quelle operation doit faire Bob pour verifier la signature ?
Exercice 4 — Diffie-Hellman en trinome¶
Donnees publiques : \(p = 23\), \(g = 5\) (connues de tous, y compris Eve).
A faire a trois : un Alice, un Bob, une Eve.
Round 1 — Echange honnete (Eve passive)
- Alice choisit un secret \(a\) entre 2 et 10. Calcule \(A = g^a \bmod p\) et l'envoie a Bob (Eve ecoute).
- Bob choisit un secret \(b\) entre 2 et 10. Calcule \(B = g^b \bmod p\) et l'envoie a Alice (Eve ecoute).
- Alice calcule \(K = B^a \bmod p\). Bob calcule \(K = A^b \bmod p\). Comparer : meme \(K\) ?
A noter dans le README : les valeurs de \(a\), \(b\), \(A\), \(B\), \(K\).
Astuce de calcul
Tous ces calculs se font par carre-multiplication mod 23 (exo 2). Les nombres restent petits.
Round 2 — Eve fait du MITM
Eve choisit deux secrets \(e_A\) et \(e_B\) entre 2 et 10. Elle se place au milieu :
| Etape | Acteur | Action |
|---|---|---|
| 1 | Alice | envoie \(A = g^a \bmod 23\) → intercepte par Eve |
| 2 | Eve | envoie \(g^{e_A} \bmod 23\) a Alice (en se faisant passer pour Bob) |
| 3 | Bob | envoie \(B = g^b \bmod 23\) → intercepte par Eve |
| 4 | Eve | envoie \(g^{e_B} \bmod 23\) a Bob (en se faisant passer pour Alice) |
| 5 | Alice | calcule \(K_A = (g^{e_A})^a \bmod 23\) |
| 6 | Bob | calcule \(K_B = (g^{e_B})^b \bmod 23\) |
| 7 | Eve | calcule \(K_A = A^{e_A} \bmod 23\) ET \(K_B = B^{e_B} \bmod 23\) |
Verifier : Alice et Bob ont des \(K\) differents. Eve possede les deux et peut tout dechiffrer.
Discussion
Qu'est-ce qui manque dans ce protocole pour empecher l'attaque ?
Exercice 5 — Mini-hash maison¶
On definit une fonction de hachage jouet sur les mots :
Q1 — Calculer
a) H("CHAT") = ?
b) H("OURS") = ?
c) H("CRYPTO") = ?
Q2 — Trouver une collision
Trouver deux mots differents (3 ou 4 lettres) qui ont le meme H. Les ecrire dans le README.
Q3 — Discussion
Citer trois raisons pour lesquelles cette fonction est inutilisable pour la securite :
Exercices sur PC¶
Outils
Ces exercices se font dans un terminal Linux. Tous les outils sont preinstalles : sha256sum, openssl.
Exercice 6 — Le mail de ton ami¶
Le scenario
Tu recois ce mail :
De : marc@example.com Objet : Le rdv de demain Salut ! Voici la lettre avec les details de notre rendez-vous demain. Pour etre sur qu'elle n'a pas ete modifiee en route, voici son SHA-256 :
ece55d55d3b306516d50a4111475d0c3ef3ab75266fe4fd6fc63ef1faff5eadc
Le mail contient en piece jointe deux fichiers : messages/lettre.txt et messages/lettre-faux.txt. Ton client mail t'a separe le second car il provenait d'un message douteux.
Q1 — Verification
Calculer le SHA-256 des deux fichiers :
Q2 — Identification
Lequel des deux fichiers ton ami a-t-il vraiment envoye ? (Comparer avec le hash du mail.)
Q3 — Discussion : risque d'interception
Imagine maintenant que Eve intercepte le mail entier. Elle peut :
- modifier la piece jointe pour qu'elle dise « 16h » au lieu de « 14h »
- remplacer le hash dans le corps du mail par celui du fichier modifie
Pourrais-tu, comme destinataire, detecter la fraude ? Pourquoi ?
Q4 — Que manque-t-il ?
Le hash seul prouve l'integrite (le fichier n'a pas ete altere si on a confiance dans le hash) mais pas l'authenticite (que c'est bien Marc qui a envoye).
➡️ Quel mecanisme cryptographique vu en CM permet de garantir que le hash provient bien de Marc et pas d'Eve ? (reponse : a l'exercice 8)
Exercice 7 — RSA avec OpenSSL¶
Q1 — Generer une cle privee RSA 2048 bits
Q2 — Inspecter la cle
Y reperer n (modulus), e (publicExponent — souvent 65537), d (privateExponent), et p, q (les deux premiers facteurs).
Q3 — Extraire la cle publique
Q4 — Chiffrer / dechiffrer
echo "Rendez-vous mardi a 14h00." > rdv.txt
# Chiffrement avec la cle publique
openssl pkeyutl -encrypt -pubin -inkey pub.pem -in rdv.txt -out rdv.bin
# Dechiffrement avec la cle privee
openssl pkeyutl -decrypt -inkey priv.pem -in rdv.bin
README
Combien d'octets fait rdv.bin ? Comparer avec la taille de rdv.txt. Pourquoi ?
Exercice 8 — Signature numerique (la reponse a la Q4 de l'exo 6)¶
Q1 — Signer le rendez-vous
Q2 — Verifier la signature
→ Le verdict doit etre Verified OK.
Q3 — Tampon : modifier le fichier et re-verifier
→ Que dit openssl cette fois ?
README
Pourquoi Eve, qui a intercepte rdv.txt + rdv.sig, ne peut-elle pas fabriquer une nouvelle signature valide pour la version modifiee ?
Q4 — Synthese
Relier l'exercice 6 (le mail de Marc) et celui-ci : - Si Marc avait signe son mail, Eve aurait-elle pu le modifier sans se faire detecter ? - Combien de cles Marc a-t-il besoin ? Lesquelles partage-t-il avec toi ?
Exercice 9 — Authentification SSH par challenge¶
Quand tu te connectes a un serveur avec ssh user@serveur en utilisant une cle, aucun mot de passe ne traverse jamais le reseau. Le serveur te lance un challenge (un defi cryptographique) que toi seul peux relever : signer un nombre aleatoire avec ta cle privee.
Q1 — Generer une paire de cles SSH
Ca cree deux fichiers : ssh_demo (cle privee, a garder secrete) et ssh_demo.pub (cle publique, a deposer sur le serveur dans ~/.ssh/authorized_keys).
Format : ssh-rsa <cle-publique-en-base64> <commentaire>.
Q2 — Schema papier du protocole
Sur une feuille, dessiner le schema du protocole sous forme de diagramme de sequence. Les conventions :
- Deux acteurs cote a cote, avec une ligne de vie verticale sous chaque nom :
Alice(a gauche),Serveur(a droite). - Chaque message echange = une fleche horizontale entre les deux lignes, avec son contenu ecrit dessus.
- Chaque calcul interne (avant ou apres l'envoi d'un message) = une note a cote de la ligne de vie de l'acteur concerne.
A faire figurer dans le schema :
- l'envoi de l'identite par Alice
- le tirage d'un challenge \(N\) aleatoire par le serveur (note a droite)
- l'envoi de \(N\) a Alice
- le calcul de la signature \(S\) par Alice (note a gauche — preciser la formule avec \(d\))
- l'envoi de \(S\) au serveur
- la verification par le serveur (note a droite — preciser la formule avec \(e\))
- la decision finale (acces accorde ou refuse)
Q3 — Completer le tableau
Alice possede sa cle privee \(d\). Le serveur a sa cle publique \((n, e)\) dans authorized_keys.
| Etape | Acteur | Action |
|---|---|---|
| 1 | Alice | envoie son identite (« je suis alice ») |
| 2 | Serveur | tire un nombre aleatoire \(N\) (le challenge) et l'envoie a Alice |
| 3 | Alice | calcule \(S = \;?\) avec sa cle privee |
| 4 | Alice | envoie \(S\) au serveur |
| 5 | Serveur | verifie : \(?\) puis compare au \(N\) initial |
Completer les etapes 3 et 5.
Indice
L'operation est exactement celle de l'exercice 8 (signature) — mais cette fois, ce n'est pas un fichier qu'on signe, c'est le challenge du serveur.
Q4 — Simuler le challenge avec OpenSSL
On reutilise les cles priv.pem et pub.pem de l'exercice 7. Le serveur tire un challenge aleatoire, Alice le signe, le serveur verifie :
# Le serveur tire un challenge aleatoire (32 octets)
openssl rand -hex 32 > challenge.txt
cat challenge.txt
# Alice signe le challenge avec sa cle privee
openssl dgst -sha256 -sign priv.pem -out challenge.sig challenge.txt
# Le serveur verifie avec la cle publique d'Alice
openssl dgst -sha256 -verify pub.pem -signature challenge.sig challenge.txt
→ Verdict attendu : Verified OK — Alice est authentifiee.
Q5 — Pourquoi un challenge aleatoire ?
Imaginons qu'Eve enregistre tout le trafic reseau d'une session SSH legitime : elle capture challenge.txt et challenge.sig.
- Si le challenge etait toujours le meme, Eve pourrait-elle se faire passer pour Alice a la prochaine connexion ?
- Comme le challenge est aleatoire (different a chaque connexion), que se passe-t-il quand Eve renvoie l'ancienne signature ?
➡️ Ce mecanisme s'appelle la protection contre les attaques par rejeu (replay attack).
Q6 — Comparaison avec un mot de passe
Citer deux avantages concrets de l'authentification par cle SSH par rapport a un mot de passe :
- Avantage 1 : (indice — qu'est-ce qui circule sur le reseau dans chaque cas ?)
- Avantage 2 : (indice — un serveur compromis qui stocke tes credentials, qu'apprend-il dans chaque cas ?)
Fichiers du projet¶
Telecharger le scaffolding (td3-template.zip)
td3/
├── README.md # a remplir
├── messages/
│ ├── lettre.txt # fourni
│ └── lettre-faux.txt # fourni
├── openssl_cmds.sh # scaffolding a completer
└── utils.py # fourni : inverse_modulaire
README a rendre¶
Le scaffolding contient un README.md pre-rempli a completer. Voici sa structure :
# TD3 — RSA, Diffie-Hellman & hachage
## Exercices sur papier
### Exercice 1 — Echauffement
- Premiers entre 1 et 30 : ___
- pgcd(20, 9) = ___
- pgcd(48, 18) = ___
- inverse de 5 mod 14 = ___
### Exercice 2 — Carre-multiplication
- 4^13 mod 21 = ___ (montrer les etapes)
### Exercice 3 — RSA a la main
- n = ___, phi = ___, d = ___
- Chiffrement de M=4 : C = ___
- Dechiffrement de C=31 : M = ___ ✓
- Bonus signature : qui signe avec quoi ? Qui verifie avec quoi ?
### Exercice 4 — Diffie-Hellman en trinome
#### Round 1 (honnete)
- a = ___, b = ___, A = ___, B = ___, K commun = ___
#### Round 2 (Eve MITM)
- eA = ___, eB = ___, K_Alice = ___, K_Bob = ___
- Alice et Bob ont-ils le meme secret ? ___
- Que manque-t-il pour empecher l'attaque ?
### Exercice 5 — Mini-hash
- H("CHAT") = ___ / H("OURS") = ___ / H("CRYPTO") = ___
- Collision trouvee : H("___") = H("___") = ___
- Trois raisons pour lesquelles c'est inutilisable :
## Exercices sur PC
### Exercice 6 — Le mail de ton ami
- SHA-256 de lettre.txt = ___
- SHA-256 de lettre-faux.txt = ___
- Lequel ton ami a-t-il envoye ? ___
- Si Eve intercepte tout (fichier + hash), peux-tu detecter ? Pourquoi ?
- Que manque-t-il ?
### Exercice 7 — RSA avec OpenSSL
- Taille de rdv.bin = ___ octets, comparaison avec rdv.txt :
### Exercice 8 — Signature
- Verdict apres modification de rdv.txt : ___
- Pourquoi Eve ne peut-elle pas fabriquer une nouvelle signature ?
- Si Marc avait signe son mail, qu'est-ce qui changerait ?
### Exercice 9 — Authentification SSH par challenge
- Etape 3 (ce que calcule Alice) : ___
- Etape 5 (ce que verifie le serveur) : ___
- Verdict de la simulation OpenSSL : ___
- Pourquoi le challenge doit-il etre aleatoire ? (replay attack) ___
- Deux avantages d'une cle SSH par rapport a un mot de passe :
1.
2.
## Difficultes rencontrees
(libre)