Discussion:Cryptosystème de ElGamal

À faire

Cet article devrait montrer plus nettement :

1. que les opérations (multiplications) sont des opérations modulo p. Cela peut être évident pour des spécialistes en mathématiques, mais ça l'est moins si l'on cherche à découvrir et à comprendre.
   Et plus généralement, puisque ElGamal est utilisé principalement en cryptographie informatique,
2. le but des opérations, par exemple commencer par dire que A veut transmettre à B un message m en confidentialité, m sera donc crypté pour l'envoi.
3. les limitations sur la taille de m : comment un texte peut être considéré comme un nombre, et comment le subdiviser éventuellement en plusieurs parties s'il faut qu'il soit plus petit que p, etc..

N'étant pas un spécialiste, je m'attends à ce que les choses soient plus claires. Cordialement, Stefan Michalowski 195.33.70.23 16 novembre 2006 à 16:19 (CET)

Je souscris tout à fait à ces remarques, l'article est trop concis bien que exact. J'ai commencé à contribuer à la partie Crypto de Wikipedia il y a 2 mois seulement et l'avais vu, mais je me suis occupé en priorité d'y assurer l'exactitude et la précision mathématique. Pour l'amélioration de la rédaction, j'ai jugé plus urgent, après revue des 181 (!) articles de crypto existants, de commencer par d'autres. Mais sur ce chantier tous les rédacteurs sont bienvenus...HLenormand 18 novembre 2006 à 19:32 (CET)

J'ai modifié la structure de l'article, prenant un point de vue plus algébriste que travailler juste dans $\mathbb {Z} /p\mathbb {Z}$, vu qu'il n'y a pas plus de difficultés, et qu'il existe des attaques sous-exponentielles sur $\mathbb {Z} _{p}$. Je vais essayer de continuer sur ma lancée (et améliorer la rédaction) sauf s'il y a des personnes refractaires à ces changements. --Fabrice Mouhartem (discuter) 17 avril 2016 à 14:46 (CEST)

Ha, comme je suis un noob de wikipédia, comment fait-on pour rajouter l'indication que l'article est partiellement issue de wikipédia anglais ? --Fabrice Mouhartem (discuter) 17 avril 2016 à 15:34 (CEST)

{{Traduction/Référence}} — bonnes contributions, Ltrlg (discuter), le 17 avril 2016 à 15:52 (CEST)

Cryptanalyse de l'algorithme

Je tiens avant tout à remercier les contributeurs français de wikipédia en matière de crypto! Si la clef publique est {p,g,h} tel que $h=g^{x}$ avec x la clef privée, la cryptanalyse ne revient-elle pas à résoudre une équation à une inconnue? Par exemple une boucle while(h != g^x){x+=1} Se pose alors à moi le problème du domaine de x... Surement pas N non? Mais pas Z non plus car sinon l'égalité n'est pas forcément respectée. Comment diable alors génère-t-on ces h,g et x sans tomber dans la trivialité ! Mon interrogation vous paraitra surement d'une naïveté à toute épreuve mais je me pose néanmoins la question!!! Cha--88.178.24.72 (d) 7 novembre 2009 à 18:55 (CET)

C'est de la bruteforce et c'est dûr à faire. Très dur.

Exemple

Les exemples ont été produit rapidement avec le code sage suivant:

#!/bin/env sage
# SETUP
p=100000007
G=GF(p)
g=G(5)
sk=81996614
pk=g^sk

print 'pk=',pk 

def encrypt(m):
    r = G.random_element()
    print 'r=',r
    c=(g^r, m * pk^r)
    print 'c=',(c[0],c[1])
    return c

c1=encrypt(G(42))
c2=encrypt(G(42))

def decrypt(c):
    m=c[1]/c[0]^sk
    print 'm=',m
    return m

decrypt(c1)
decrypt(c2)

Fabrice Mouhartem (discuter) 21 avril 2016 à 01:22 (CEST)

Rigueur, réduction fausse et pertinence.

Bonjour

D'abord, désolé d'avance pour les éventuelles fautes d'orthographe. Je sais que j'en fais beaucoup, j'espère ne pas en avoir trop laissé traîner...

Je trouve qu'il y a vraiment beaucoup de problèmes de rigueur et de justesse dans cet article. Les notations utilisées sont parfois très maladroites et les explications assez bancales. En particulier dans la section sécurité. Mais le principale problème est que la preuve de sécurité est fausse (voir 5 ci-dessous).

Par ailleurs, je ne suis pas sûr de la pertinence d'expliciter la réduction de la sécurité CPA d'ElGamal vers DDH dans cet article. C'est très compliqué, cela demande beaucoup de formalisme et des notions assez pointu de crypto. D'ailleurs à cause de cela, la réduction présentée utilise des notations vraiment très peu rigoureuses (Pr[DDH] ?). Je ne suis pas sûr qu'un novice en crypto puisse comprendre quoi que ce soit à cette réduction avec si peu de détails, même si on corrigeait les erreurs. Il faudrait au moins préciser que pour démontrer que ElGamal est CPA sous l'hypothèse DDH, on démontre la contraposée, c'est à dire que si ElGamal n'est pas CPA alors l'hypothèse DDH est fausse.

Voici les quelques points les plus importants à corriger (liste non exhaustive).

• 1) La notation = avec un petit triangle au dessus n'est pas usuelle et n'a pas été définie. Idem pour "appartient" indice R.

• 2)négligeable n'est pas défini.

• 3) Dans la réduction, qu'est-ce que m_i ?? Il manque sans doute la partie ou l'adversaire CPA retourne deux clairs choisis (m_0,m_1).

• 4) "On n'a plus qu'à répondre « DDH » si jamais notre adversaire réussis, et « Aléa » dans le cas contraire." Je pense que répondre "DDH" n'a pas vraiment de sens. DDH veut dire "Décisional Diffie Helleman", c'est le problème de décision. À la rigueur, répondre "DH" pour "triplet de Diffie Helleman" aurait plus de sens.

Pourquoi ne pas répondre "c=ab" ou "c!=ab" tout simplement?

• 5) La réduction est fausse. Dès la première ligne:

>En supposant qu'on ait un adversaire contre la sécurité sémantique du chiffrement El Gamal qui gagne avec une probabilité non négligeable ε.

Si on prend ε=1/2 (ce qui est non négligeable), on a l'avantage de l'adversaire qui répond i=0 ou i=1 de façon aléatoire... Va-t-on prouver alors qu'avec un adversaire qui répond 0 ou 1 au hasard, on peut casser DDH?

En réalité, c'est l'avantage de l'adversaire qui doit être non négligeable. En notant cet avantage ε, la probabilité de victoire de l'adversaire est 1/2 +- ε (où +- veut dire "plus ou moins").

C'est la même erreur dans la partie analyse. Pr[W]>= ε/4 ne permet aucune conclusion, car au mieux, ε/4=1/4, donc Pr[W] peut être égal à 1/2 >= ε/4. Dans ce cas "la réduction" ne fait pas mieux qu'un algorithme qui répond "c=ab" ou "c!=ab" au hasard.

Pour corriger cette réduction, je vous renvoie à l'ouvrage "Introduction to Modern Cryptography" par J. Katz et Y. Lindell. ;)

Plus sérieusement, en utilisant les notations de l'article, si on considère que l'adversaire contre le CPA gagne avec une proba 1/2+-ε, on a:

Pr[W] = Pr[W|DDH]Pr[DDH] + Pr[W|Alea]Pr[Alea]

     = (1/2+-ε).1/2 + 1/2.1/2 
     = 1/4 + 1/4 +- ε/2
     = 1/2 +- ε/2

Et donc "la réduction gagne" avec l'avantage suivant:

|Pr[W]-1/2| = ε/2

Qui est non-négligeable.

L'auteur de cette section pourrait il prendre en compte mes remarques? J'espère avoir été assez clair dans mes explications. Encore une fois, je pense que le détail de cette preuve de sécurité n'a pas sa place dans cet article.

--Zombigorneau (discuter) 6 mars 2017 à 17:34 (CET)

Bonjour  Zombigorneau,

 

Merci pour les remarques sur la rigueur de la preuve et j'ai pris en compte certaines de celles-ci. :-)

 

C'est en effet une de mes premières contributions depuis que je me suis remis à WP (si ce n'est la première depuis 4 ans ?), et ça s'en ressent dans plusieurs parties de l'article, en partie dues au fait que ma manière de contribuer consiste à regarder les pages de cryptographie assez succinctes et rajouter du contenu par dessus soit en me fondant sur des ouvrages de références (le Katz et Lindell), soit sur des articles fondateurs/des survols. Partir de pages préexistantes fait que je n'ose pas nécessairement remodifier complètement les notations préexistantes (c'est ce qui me gêne par exemple dans l'article Guillou-Quisquater, où la notation $J_{A}$ pour un certificat publique me semble étrange… mais passons.

 

Pour le reste, la notation $\triangleq$ est assez standard en mathématique pour une définition, elle ne l'est pas moins que $:=$ par exemple, qui est plus utilisée en informatique. Pour la notation $\in _{R}$, elle l'est moins, et je l'ai remplacée par $\hookleftarrow$, surtout que pour dire « tirer dans », la notation $\in _{R}$ n'est pas adaptée. Elle reste en revanche dans la démonstration, qui est désormais cachée, parce qu'elle y fait du sens, et parce que la démonstration étant cachée, elle est destinée à un public averti.

 

J'ai par ailleurs rajouté les liens vers les notions « pointues » manquantes, comme avantage (qui n'existe pas encore à cette date) et négligeable, pour référence.

 

Tes explications étaient claires, merci encore pour tes remarques, ça fait plaisir de voir que des gens lisent ce genre d'articles, je l'avais trouvé dans cet état: Cryptosystème de ElGamal.

Fabrice Mouhartem (discuter) 14 avril 2017 à 18:03 (CEST)

Je suis plutôt à l'aise en arithmétique mais je suis plutôt débutant en crypto. J'avoue difficilement comprendre cet article, dont la version anglaise me semble paradoxalement plus accessible.

• Le cas pratique gagnerait à être illustré avant le cadre théorique.
• Le schéma qui accompagne la figure utilise des variables qui ne sont pas mentionnées dans le paragraphe attenant.
• Je ne comprends ni ne connais la notation \mathsf{sk} \triangleq x \hookleftarrow U(\mathbb{Z}_q^*). Vous remerciant par avance pour les aménagements que vous pourriez en tirer.

92.188.102.26 (discuter) 7 avril 2024 à 20:33 (CEST)