Esatic Année académique 2023-2024
Master 1 Info A et B.
TD cryptographie
Exercice 1 : Cassage d’une clef
En lisant son journal ce matin, Yao a appris qu’une équipe de cryptographe à réussi à casser une clef
de 768 bits. Il trouve cette nouvelle surprenante car sa banque lui garantit que les transactions sur
internet sont absolument sures grâce à l’utilisation de clés de 128 bits. Expliquer cette apparente
contradiction.
Exercice 2 : Perte de clef privée
Kouadio, qui utilise souvent la messagerie sécurisée de son entreprise, vient de perdre sa clef privée,
mais dispose encore de la clef publique correspondante.
1. Peut-il encore envoyer des courriers électroniques chiffrés ? En recevoir ?
2. Peut-il encore signer des courriers électroniques qu’il envoie ? Vérifier les signatures des
courriers électroniques qu’il reçoit ?
3. Que doit-il faire pour être à nouveau capable d’effectuer toutes les opérations mentionnées
ci-dessus ?
Exercice 3 : Algorithme RSA
Cet exercice traite certain détail de l’algorithme RSA.
1. En admettant que 𝑒𝑑 ≡ 1 [𝜑(𝑛)], montrer que la fonction de chiffrement proposées est bien
l’inverse de la fonction de déchiffrement.
2. Détailler la procédure à suivre pour générer un couple (clé publique, clef privée)
3. Chiffrer le message « 21 » avec la clef publique (103,143). Le calcul peut être facilement fait à
la main en remarquant que 214 ≡ 1 [143]
4. Sachant que 𝑛 = 11 × 13, calculer la clef privée associée à la clé publique (103,143)
5. Déchiffrer le message obtenu à la question 3 afin de retrouver le message clair.
6. La taille du module RSA considérée dans cet exercice est artificiellement petite pour faciliter
les calculs. Expliquer pourquoi il est courant en pratique d’utiliser un petit exposant public,
par exemple 𝑒 = 216 + 1.
Exercice 4 : Décryptage d’un message RSA
On souhaite décrypter le message « 997593903573 » qui a été chiffré avec la clef publique
(7,1037594094337)
1. Factoriser 𝑛
2. Calculer la clef privée associée à (7,1037594094337)
3. Calculer le message clair
4. En utilisant le fait que chaque couple de chiffres correspond au code ASCII d’un caractère,
convertir le message clair en une forme intelligible.
Exercice 5 : vulnérabilité RSA
Les exercices 5 et 6 s’intéresse à l’algorithme RSA tel qu’il est présenté dans les livres d’introduction à
la cryptographie : il ne faut jamais l’utiliser tel quel en pratique ! L’algorithme RSA est, sous cette
forme vulnérable à de nombreuses attaques. Pour s’en convaincre, on se propose d’étudier l’une
d’entre elle : montrer que le produit des signatures de deux messages (réalisées avec la même clef
privée) est égal à la signature du produit des deux messages.
Exercice 6: Recherche exhaustive de clefs symétriques
Sachant que la machine spécialisée « DES-Cracker » met en moyenne 4,5 jours pour retrouver par
une recherche exhaustive une clef DES de 56 bits, combien de temps mettrait-elle pour trouver une
clef de 40 bits ? Une clef 3-DES de 112 bits ? Une clef AES de 256 bits ? On admettra ici que cette
machine a besoin du même pour chiffrer un bloc de données avec DES, 3DES et AES (Ce qui n’est pas
le cas en pratique)
Exercice 7 : Fonction de hachage et paradoxe des anniversaires
Fonction de hachage SHA-1 génère des empreintes numériques de 160 bits. On suppose que l’on
décide de créer un certificat numérique pour chaque habitant de la terre (7*10^9 habitants).
1. Calculer la probabilité qu’au moins un certificat possède la même empreinte que le certificat
de Yao
0 × 11c42333 330debe663d722a5f34388c8b88520bb
(En notation hexadécimale), en s’aidant du fait que 1 − 𝑥 ≈ 𝑒 𝑥 pour x proche de 0
2. Calculer la probabilité pour que deux habitants de la planète aient une empreinte identique.
