Exercices td sécurité informatique chiffrement asymétrique r
Télécharger PDFSécurité informatique – Série N°4 : Chiffrement asymétrique et signature numérique
Exercice 1 : Arithmétique modulaire
1. Calculer : 934 + 575 modulo 23, 871 – 397 modulo 19 et 296 × 137 modulo 29.
2. Déterminer le PGCD et les coefficients de Bézout de 1234 et 832.
3. Calculer l’inverse de 87 modulo 674 et de 93 modulo 439.
4. Calculer : 2256 mod 128, 529436 mod 66, 1284096 mod 129, 564549 mod 31.
Exercice 2 : Euclide étendu
Ali donne à sa banque un chèque de x dinars et y centimes. Par erreur, le banquier encaisse y dinars et x centimes, ce qui représente 5 centimes de plus que le double du montant du chèque. Calculer x et y.
Exercice 3 : Chiffrement RSA
Soit p = 3, q = 13, n = pq = 39 et e = 19.
1. Calculer d tel que ed ≡ 1 mod φ(n).
2. Chiffrer le message M = 2 et vérifier le résultat en le déchiffrant.
3. Vous interceptez le cryptogramme c = 10 obtenu par chiffrement RSA avec la clé publique n = 35 et e = 5. Quel est le message clair ?
Exercice 4 : De φ(n) à la factorisation
On considère un module RSA n = pq, où p et q sont les inconnus.
1. Montrer comment la connaissance de φ(n) permet de retrouver la factorisation de n.
2. Soit n = pq = 851 un produit de deux nombres premiers. On sait que φ(n) = 792. Retrouver les deux facteurs premiers p et q de n.
Exercice 5 : Chiffrement RSA
On considère la clé publique RSA (11, 319). Utiliser les résultats suivants :
319 = 11 × 29 ; 1011 mod 319 = 263 ; 263² = 216 × 319 + 265 ; 1333 mod 319 = 12 ; 133² mod 319 = 133 ; 11² mod 280 = 121 ; 11⁴ mod 280 = 81 ; 11⁸ mod 280 = 121 ; 11¹⁶ mod 280 = 81 ; 95 = 64 + 31 ; 81 × 11 mod 280 = 51 ; 81 × 121 mod 280 = 1.
1. Quel est le message correspondant au chiffrement avec cette clé du message M = 100 ?
2. Calculer la clé privée d associée à la clé publique e.
3. Déchiffrer le message C = 133.
4. Le message chiffré 625 peut-il résulter d’un chiffrement avec cette clé publique ?
Exercice 6 : Signature RSA
1. Calculer N et φ(n) associés aux nombres premiers p = 17 et q = 23.
2. Quels sont les exposants secrets de signatures associés aux exposants publics e = 11 et e = 13 ?
3. Quelle est la signature du message m = 100 ?
4. Vérifier que cette signature fonctionne.
Exercice 7 : Signature El Gamal
On considère la méthode de signature El Gamal avec p = 467, g = 2 et x = 65.
1. Justifier la validité du choix de p et g.
2. Calculer la clé publique y = gx mod p.
3. Calculer la signature du message m = 100 en utilisant les valeurs aléatoires k = 64 et k = 213.
Exercice 8 : Signature El Gamal sans hachage
On suppose que le schéma d’El Gamal est utilisé sans fonction de hachage, c’est-à-dire avec s = k-1(m – x × r) mod (p – 1).
1. En posant r = gα × yβ mod p et s = –r × β-1 mod (p – 1), montrer que (r, s) est la signature valide d’un message que l’on calculera.
2. Quelle condition doit vérifier β ?
3. De quelle type d’attaque s’agit-il ?
Exercice 9 : Attaques sur la signature d’El Gamal
On présente une attaque utilisant un message connu. On note p, g les paramètres du système et y la clé publique de Bob (Charlie ne connaît pas x tel que y = gx). Pour les applications numériques, on prendra p = 467 et g = 2.
On suppose que Charlie dispose d’un message m et de sa signature (a, b).
1. Vérifier la validité de la signature de m = 100 avec a = 337 et b = 9 (prendre y = 316).
2. Soit (r, s, t) = (1, 3, 4). Vérifier que PGCD(r × a – t × b, p – 1) = 1 et calculer u = (r × a – t × b)-1 mod (p – 1).
3. Montrer que α = a × gs × t × yu mod p = 365 et β = α × bu mod (p – 1) = 319 est la signature d’un message μ que l’on calculera.
4. Que dire de la valeur aléatoire k sous-jacente à cette contrefaçon ?
FAQ
1. Comment calculer un inverse modulaire ?
Pour trouver l’inverse de a modulo m, utiliser l’algorithme d’Euclide étendu qui permet de déterminer des entiers x et y tels que ax + my = 1. L’inverse est alors x mod m.
2. À quoi sert la fonction d’Euler φ(n) dans le chiffrement RSA ?
La fonction d’Euler φ(n) est utilisée pour calculer la clé privée d, qui est l’inverse de la clé publique e modulo φ(n). Elle permet aussi de factoriser n si elle est connue.
3. Qu’est-ce qu’une signature numérique et comment la vérifier ?
Une signature numérique est une preuve mathématique de l’authenticité et de l’intégrité d’un message. Elle se vérifie en utilisant la clé publique du signataire : si le message chiffré avec la clé privée correspond au message original, la signature est valide.