Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

HMIN331m – Calcul formel, codes et cryptographie (2020 – 2021) Romain Lebreton

HMIN331m – Calcul formel, codes et cryptographie (2020 – 2021) Romain Lebreton TD El-Gamal : preuves de sécurité et diﬃculté du logarithme discret (corrigé) Vous pouvez vous servir de Python pour eﬀectuer les calculs de ce TD. Nous vous fournissons des classes pour faire les calculs modulo p dans le ﬁchier TD7-ZpZ.py sur Moodle. Exercice 1. Un exemple pour Pohlig-Hellman Considérons le problème du logarithme discret dans (Z/pZ⋆) pour p = 31, qui est un groupe d’ordre ϕ(p) = p −1 = 30 = 5 · 3 · 2 engendré par g = 3. Simulez l’algorithme de Pohlig-Hellman pour réduire le calcul du logarithme discret de h = 26 à des logarithmes discrets dans des plus petits groupes. Détaillez les calculs, sauf ceux des logarithmes discrets dans les plus petits groupes où les résultats suﬃsent. hq/2 = (gq/2)x mod 2 donne ici 30 = 301 mod p. hq/3 = (gq/3)x mod 3 donne ici 5 = 252 mod p. hq/5 = (gq/5)x mod 5 donne ici 1 = 160 mod p. Donc h = gx avec x = 5. Exercice 2. Un exemple de Baby-Step/Giant-Step Considérez le problème du logarithme discret dans (Z/pZ⋆) pour p = 37, qui est un groupe engendré par g = 2. Simulez l’exécution de l’algorithme de Baby-Step/Giant-Step pour l’entrée h = 6. (g6·i)0≤i<6 = (1, 27, 26, 36, 10, 11) et (h/gj)0≤j<6 = (6, 3, 20, 10, 5, 21) donc on a g6·4 = h/g3 et h = g27. Exercice 3. Un exemple de El-Gamal dans G ⊊Z/pZ⋆ Soient q = 83 et p = 2q + 1 premier et considérons le groupe multiplicatif (Z/pZ⋆). Comme le cardinal de ce groupe n’est pas premier et que c’était l’une des recommandations du cours, nous allons considérer un sous-groupe G de (Z/pZ⋆). Posons G = g2i|0 ≤i < q le sous-groupe des carrés, qui est d’ordre q premier. Nous choisirons le générateur g′ = 4 mod 167 pour G. 1. Rappelez pourquoi on souhaite que l’ordre du groupe soit premier. Sinon Pohlig-Hellman permet de calculer le logarithme discret plus rapidement. 2. Expliquez pourquoi G est un groupe, c’est-à-dire que 1 ∈G, g · g′ ∈G et que g−1 ∈G pour tout g, g′ ∈G. 1 = g2·0 ∈G, g2i · g2j = g2((i+j) mod q) ∈G et (g2i)−1 = g2(q−i). 3. Supposons que Bob choissise la clé secrète 37. Donnez la clé publique de Bob. h = g′37 = 76 mod 167. 4. Alice souhaite envoyer le message m = 65 mod 167 ∈G à Bob. Donnez le chiﬀré correspondant à l’aléa y = 71. (c1, c2) = (gy, hy ∗m) = (132 mod 167, 44 mod 167). 5. Déchiﬀrez le message chiﬀré c reçu par Bob en indiquant toutes les étapes du calcul. m = c2/cx 1 = 65 mod 167. 1 uploads/s3/ td8-corrige 1 .pdf