Exercices td arithmetique modulaire et bezout avec solutions
Télécharger PDFSérie 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.
Solution Exercice 1
1. Calculs modulo : 934 + 575 modulo 23 = 14 871 - 397 modulo 19 = 18 296 × 137 modulo 29 = 10
2. PGCD et coefficients de Bézout : PGCD(1234, 832) = 2 Les coefficients de Bézout sont : 89 et -132.
3. Inverses modulo : Inverse de 87 modulo 674 = 31 Inverse de 93 modulo 439 = 325
4. Calculs modulo : 2256 mod 128 = 27 529436 mod 66 = 1 1284096 mod 129 = 1 564549 mod 31 = 5
Exercice 2 : Algorithme d'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 de son chèque. Calculer x et y.
Solution Exercice 2
Équation : 199x - 98y = -5
Solution trouvée : x = 31, y = 63.
Exercice 3 : Chiffrement RSA
Soit p = 3, q = 13, n = p × q = 39 et e = 19.
1. Calculer d tel que e × d ≡ 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 ?
Solution Exercice 3
1. Calcul de d : φ(n) = 24 d = inverse(19) mod 24 = 19.
2. Chiffrement et déchiffrement : C = 219 mod 39 = 11. Déchiffrement : 1119 mod 39 = 2.
3. Message clair : n = 35 = 5 × 7 φ(n) = 24 d = inverse(5) mod 24 = 5. M = 105 mod 35 = 5.
Exercice 4 : De φ(n) à la Factorisation
On considère un module RSA n = p × q, où p et q sont inconnus.
1. Montrer comment la connaissance de φ(n) permet de retrouver la factorisation de n.
2. Soit n = p × q = 851 et φ(n) = 792. Retrouver les facteurs premiers p et q.
Solution Exercice 4
1. Relation entre φ(n) et n : φ(n) = (p - 1)(q - 1) n = p × q On obtient : p2 - p × (φ(n) + n + 1) + n × φ(n) = 0.
2. Factorisation de n = 851 : Équation : p2 - 60p + 851 = 0 Solutions : p = 23, q = 37.
Exercice 5 : Clé Publique RSA (11, 319)
1. Quel est le message correspondant au chiffrement de M = 100 avec cette clé ?
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 ?
Solution Exercice 5
1. Chiffrement de M = 100 : C = 10011 mod 319 = 265.
2. Clé privée d : φ(n) = 280 d = inverse(11) mod 280 = 51.
3. Déchiffrement de C = 133 : M = 13351 mod 319 = 12.
4. Vérification de 625 : Non, car 625 > 319 = n.
Exercice 6 : Signature RSA
1. Calculer N et φ(n) associés aux nombres 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 de m = 100 ?
4. Vérifier que la signature fonctionne.
Solution Exercice 6
1. Calcul de N et φ(n) : N = p × q = 17 × 23 = 391 φ(n) = 16 × 22 = 352.
2. Exposants secrets : e = 13 est valide. d = inverse(13) mod 352 = 325.
3. Signature de m = 100 : S = 100325 mod 391 = 36.
4. Vérification de la signature : 3613 mod 391 = 100.
Exercice 7 : Signature El Gamal
On considère la méthode de signature El Gamal avec p = 467, g = 2, 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.
Solution Exercice 7
1. Validité de p et g : p = 467 est un nombre premier. g = 2 est un générateur car 2233 ≡ 2233 ≢ 1 mod 467.
2. Clé publique y : y = 265 mod 467 = 271.
3. Signature de m = 100 avec k = 213 : k-1 mod (p - 1) = 431 a = 2213 mod 467 = 29 b = (100 - 65 × 29) × 431 mod 466 = 31 Signature : (29, 31).
Exercice 8 : Signature El Gamal sans Hachage
1. Montrer que (r, s) est la signature valide d’un message M = αs.
2. Quelle condition doit vérifier β ?
3. De quelle type d’attaque s’agit-il ?
Solution Exercice 8
1. Signature valide : M = αs.
2. Condition sur β : PGCD(β, p - 1) = 1.
3. Type d’attaque : Attaque sans message, où une signature valide permet d’obtenir un message.
Exercice 9 : Attaques sur la Signature El Gamal
1. Vérifier la validité de la signature de m = 100 avec a = 337, b = 9 (y = 316).
2. Vérifier que PGCD(r × a - t × b, p - 1) = 1 et calculer u = (r × a - t × b)-1 mod (p - 1) pour (r, s, t) = (1, 3, 4).
3. Montrer que (α = 365, β = 319) est la signature d’un message μ.
4. Que dire de la valeur aléatoire k sous-jacente à cette contrefaçon ?
Solution Exercice 9
1. Vérification de la signature : 316337 × 3379 mod 467 = 2100 mod 467.
2. Calcul de u : PGCD(1 × 337 - 4 × 9, 466) = PGCD(301, 466) = 1 u = 301-1 mod 466 = 365.
3. Message μ : μ = αβ mod (p - 1) = 365319 mod 466.
4. Valeur de k : k = α × β-1 mod (p - 1) = 365 × 319-1 mod 466.
FAQ
1. Qu’est-ce que l’arithmétique modulaire ?
L’arithmétique modulaire est une branche des mathématiques qui traite des opérations sur les entiers en utilisant des congruences modulo un nombre donné. Elle est essentielle en cryptographie pour simplifier les calculs et garantir la sécurité.
2. Comment calculer l’inverse d’un nombre modulo n ?
L’inverse d’un nombre a modulo n est un nombre x tel que (a × x) mod n = 1. On utilise l’algorithme d’Euclide étendu pour le déterminer.
3. Pourquoi utiliser des fonctions de hachage dans la signature El Gamal ?
Les fonctions de hachage réduisent la taille des messages avant signature, évitant ainsi les attaques par contrefaçon de messages et améliorant la sécurité du système.