Cryptosystème ElGamal
Notions de sécurité
Cryptosystème ElGamal
Anca Nitulescu
[Link]@[Link]
Ecole Normale Supérieure, Paris
Cours 4
1/16 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Cryptosystème ElGamal • Déscription
Notions de sécurité • Echange de clé Diffe-Hellman
Protocole ElGamal
ElGamal - Génération des clés
KG(`) = (pk, sk)
Soit un premier p et le groupe cyclique Z?p
Soit g ∈ Z?p un élément d’ordre q, un diviseur de (p − 1).
Soit une clé secrète sk = x.
Soit y = gx (mod p).
clé publique clé secrète
p et g : paramètres publiques sk = x
pk = y = gx : clé publique exposant sécret
2/16 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Cryptosystème ElGamal • Déscription
Notions de sécurité • Echange de clé Diffe-Hellman
Protocole ElGamal
ElGamal - Chiffrement
E(pk = y , M) = (C , D)
Pour un aléa r on calcule une paire (C , D) (le chiffré de M)
C = g r (mod p)
D = M · y r (mod p)
ElGamal - Déchiffrement
D(sk = x, (C , D)) = D · C −x (mod p).
3/16 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Cryptosystème ElGamal • Déscription
Notions de sécurité • Echange de clé Diffe-Hellman
Protocole ElGamal
ElGamal - Chiffrement
E(pk = y , M) = (C , D)
Pour un aléa r on calcule une paire (C , D) (le chiffré de M)
C = g r (mod p)
D = M · y r (mod p)
ElGamal - Déchiffrement
D(sk = x, (C , D)) = D · C −x (mod p).
Vérification
D · C −x = M y r (g r )−x = M (g x )r (g r )−x = M (mod p)
3/16 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Cryptosystème ElGamal • Déscription
Notions de sécurité • Echange de clé Diffe-Hellman
Emploi de ElGamal
Avantages
Tous les utilisateurs peuvent utiliser le même groupe Z?p et le
même g
Possibilité de techniques d’exponentiation rapide
Chiffrement randomisé nativement
Meilleure sécurité basique
Inconvénients
Augmentation de la taille du chiffré
Deux fois plus lent que RSA
4/16 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Cryptosystème ElGamal • Déscription
Notions de sécurité • Echange de clé Diffe-Hellman
Efficacité de ElGamal
ElGamal - coût
Le coût est celui de deux exponentiations modulaires :
El Gamal est 2 fois plus lent que RSA.
La taille des données chiffrées représente 2 fois celle des
données en clair.
5/16 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Cryptosystème ElGamal • Déscription
Notions de sécurité • Echange de clé Diffe-Hellman
Propriétés multiplicatives
ElGamal -Attaque à chiffré choisi
Si (C , D) est un chiffré de M, pour tout A, le couple (C , A · D)
chiffre A · M :
C = g r (mod p)
A · D = A · M · y r (mod p)
6/16 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Cryptosystème ElGamal • Déscription
Notions de sécurité • Echange de clé Diffe-Hellman
Attaques ElGamal
ElGamal avec le même aléa
Ne jamais utiliser deux fois le même aléa !
Si M1 et M2 sont chiffrés avec le même aléa r , alors :
(C1 , D1 ) = (g r , y r M1 ) (mod p)
(C2 , D2 ) = (g r , y r M2 ) (mod p)
d’où : M1 D1
=
M2 D2
7/16 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Cryptosystème ElGamal • Déscription
Notions de sécurité • Echange de clé Diffe-Hellman
Problème difficile
Logarithme discret (DLOG)
Définition Soit G un groupe multiplicatif,
g ∈ G et y ∈ hg i :
logg (y ) = x où g x = y
8/16 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Cryptosystème ElGamal • Déscription
Notions de sécurité • Echange de clé Diffe-Hellman
Difficulté de ElGamal
Réduction
La recherche de la clé privée x à partir de la
clé publique y = g x est équivalente au
problème du logarithme discret (DLOG).
ElGamal se réduit au logarithme
discret !
9/16 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Cryptosystème ElGamal • Déscription
Notions de sécurité • Echange de clé Diffe-Hellman
Réduction de ElGamal
En pratique
Si le problème du logarithme est résolu polynomialement, alors
El Gamal sera cassé.
Le contraire est peut-être faux !
Rien ne prouve qu’il n’est pas cassable par un autre moyen.
Le log discret est la seule méthode connue pour casser ElGamal.
10/16 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Cryptosystème ElGamal • Déscription
Notions de sécurité • Echange de clé Diffe-Hellman
Echange de clé
clé commune g xy
11/16 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Cryptosystème ElGamal • Déscription
Notions de sécurité • Echange de clé Diffe-Hellman
Autres problèmes difficiles
Soit G un groupe multiplicatif cyclique, G = hg i :
Calculer Diffie-Hellman (CDH)
Etant donnés g , A = g a et B = g b ,
Calculer C = CDH(A, B) = g ab
Décider si Diffie-Hellman (DDH)
Etant donnés
g , A = g a , B = g b et C = g c dans G
Décider si C = g ab
12/16 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Cryptosystème ElGamal • Déscription
Notions de sécurité • Echange de clé Diffe-Hellman
Réduction de Diffie-Hellman
Attaquer Diffie-Hellman
Si le problème CDH est résolu, alors l’attaquant peut calculer
une clé Diffie-Hellman
Si le problème DDH est résolu, alors l’attaquant peut
distinguer entre une clé valide et une clé fausse
13/16 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Cryptosystème ElGamal
• Fonctions à sens unique
Notions de sécurité
Fonctions à sens unique
14/16 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Cryptosystème ElGamal
• Fonctions à sens unique
Notions de sécurité
Problèmes difficiles
Soit G un groupe multiplicatif cyclique, G = hg i :
Logarithme discret (DLOG)
Etant donnés g ∈ G et X = g x ,
Calculer logg (X ) = x
Calculer Diffie-Hellman (CDH)
Etant donnés g , A = g a et B = g b ,
Calculer C = CDH(A, B) = g ab
Décider si Diffie-Hellman (DDH)
Etant donnés g , A = g a , B = g b et C = g c dans G
Décider si C = g ab
15/16 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Cryptosystème ElGamal
• Fonctions à sens unique
Notions de sécurité
Hiérarchie
CDH < DLOG
DLOG Etant donnés g , A = g a et B = g b ,
on calcule b =DLOG(B)
on trouve C = Ab = g ab
CDH
DDH < CDH
Etant donnés g , A = g a , B = g b et
DDH C = gc
on calcule CDH(A, B) = g ab
on compare avec C
16/16 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
