Scribd Logo
Importer

Bienvenue sur Scribd !

  • 118 vues

    TD8 Corrige

    Transféré par

    ismail oualid

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    TD8 Corrige

    Transféré par

    ismail oualid
    118 vues1 page

    Titre original

    TD8 Corrige (1)

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    118 vues1 page

    TD8 Corrige

    Transféré par

    ismail oualid

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    Vous êtes sur la page 1sur 1

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

    TD El-Gamal : preuves de sécurité et difficulté du logarithme discret (corrigé)

    Vous pouvez vous servir de Python pour effectuer les calculs de ce TD. Nous vous fournissons des classes
    pour faire les calculs modulo p dans le fichier 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 suffisent.

    + hq/2 = (g q/2 )x mod 2 donne ici 30 = 301 mod p.


    hq/3 = (g q/3 )x mod 3 donne ici 5 = 252 mod p.
    hq/5 = (g q/5 )x mod 5 donne ici 1 = 160 mod p.
    Donc h = g x 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.

    + (g 6·i )0≤i<6 = (1, 27, 26, 36, 10, 11) et (h/g j )0≤j<6 = (6, 3, 20, 10, 5, 21) donc on a g 6·4 = h/g 3 et h = g 27 .

    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 = g 2i |0 ≤ i < q le sous-groupe des carrés, qui est d’ordre q
    premier. Nous choisirons le générateur g 0 = 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 0 ∈ G et que g −1 ∈ G pour tout


    g, g 0 ∈ G.

    + 1 = g 2·0 ∈ G, g 2i · g 2j = g 2((i+j) mod q) ∈ G et (g 2i )−1 = g 2(q−i) .

    3. Supposons que Bob choissise la clé secrète 37. Donnez la clé publique de Bob.
    + h = g 037 = 76 mod 167.

    4. Alice souhaite envoyer le message m = 65 mod 167 ∈ G à Bob. Donnez le chiffré correspondant à
    l’aléa y = 71.
    + (c1 , c2 ) = (g y , hy ∗ m) = (132 mod 167, 44 mod 167).

    5. Déchiffrez le message chiffré c reçu par Bob en indiquant toutes les étapes du calcul.
    + m = c2 /cx1 = 65 mod 167.

    Vous aimerez peut-être aussi