WikiMath

Le chiffrement d'El Gamal

Introduction (Wikipedia)

L'algorithme ElGamal est un algorithme de cryptographie asymétrique basé sur les logarithmes discrets. Il a été créé par Taher Elgamal.

Cet algorithme est utilisé par le logiciel libre GNU Privacy Guard, de récentes versions de PGP, et d'autres systèmes de chiffrement, et n'a jamais été sous la protection d'un brevet contrairement à RSA.

Il peut être utilisé pour le chiffrement et la signature électronique. L'algorithme DSA du NIST est basé sur ElGamal.

Le protocole

Il est facile de transformer la technique d'échange de clé selon Diffie et Hellman, en un système de cryptographie à clé publique : c'est la méthode d'El Gamal.

Voici comment Bob peut envoyer un message chiffré à Alice (avec la clé publique d'Alice)...

Publication de la clé publique d'Alice

• Alice trouve $p$ et $g$, respectivement un nombre premier et une racine primitive modulo $p$.
• Alice choisit $a$ dans $\{0, ..., p-2\}$, et calcule $A = g^a%p$.
• Alice rend publique $(p, g, A)$.

Chiffrement par Bob

• Bob récupère $(p, g, A)$.
• Bob choisit $b$ dans $\{0, ..., p-2\}$, et calcule $B = g^b%p$.
• Bob chiffre le message $m$ en le cryptogramme $c = \left( A^b \times m \right) %p$.
• Bob envoie $(B, c)$.

Déchiffrement par Alice

Alice déchiffre $c$ pour obtenir $m$, de la façon suivante : $m = \left( B^{p-1-a} \times c \right) %p$

Démonstration

En effet, on a : $B^{p-1-a} c \equiv g^{b(p-1-a)}g^{ab}m \equiv g^{b(p-1)}m \equiv m % p$ car $g^{p-1} = 1 %p$ : valable pour toute racine primitive modulo $p$.

Petit bémol

Notons que, pour transmettre le message $m$, qu'il a chiffré en $c$, Bob est conduit à transmettre le couple ($B$,$c$), message approximativement deux fois plus long que $m$.

Réalisation

Choix d'un nombre premier p

Plusieurs possibilités pour obtenir un nombre premier :

• On peut chercher un grand nombre premier sur internet.
• On peut utiliser une méthode déjà programmée en python (isprime de sympy, ou is_prime de rsa)
• On peut encore utiliser le crible d'Eratosthène.
• Ou encore, les tests de Wilson, ou de Fermat, rappelés dans le TP sur les nombres premiers ici.
• Mieux : on peut jouer dans la cour des grands, en implémentant un des algorithmes suivants :
  • le test de Miller-Rabin
  • le test de Solovay-Strassen
  • le test de Lucas-Lehmer, par exemple pour les nombres de Mersenne.

Recherche d'une racine primitive modulo p

On peut, déjà, chercher des valeurs déjà calculées sur Internet.

On peut aussi ne pas être fin : tester chacune des valeurs de 2 à $p-1$, jusqu'à obtenir une racine primitive (voir le précédent TP, pour savoir de quoi il s'agit).

On peut encore utiliser cette méthode...

1. Premièrement, calculer $\phi(p) = p-1$ (la valeur de l'indicatrice d'Euler).
2. Puis, déterminer les différents facteurs premiers de $\phi(p)$, soit $p_1,...,p_k$.
3. Enfin, pour chaque élément $m$ de $\mathbb{Z}_p^\times$, calculer

$ m^{\phi(p)/p_i} % p$ pour $i=1, \ldots, k$, en utilisant l'exponentiation rapide.

Dès que nous trouvons un nombre $m$ pour lequel ces $k$ valeurs sont toutes différentes de 1, nous stoppons : $m$ est une racine primitive.

Pour obtenir les facteurs premiers de $n$, on pourra par exemple utiliser le bout de code suivant :

  >>> def facteur(n):
  ...     if n==1:
  ...         return set([])
  ...     else:
  ...         for k in range(2,n+1):
  ...             if n%k == 0:
  ...                 L = facteur(n/k)
  ...                 return L.union([k])
  ... 
  >>> list(facteur(100))
  [2, 5]

Troisième étape : réalisation du El Gamal

Voici, ci-dessous, les fonctions nécessaires à El Gamal.

Génération des clés

Tout d'abord, la fonction qui, à partir du nombre premier $p$, de la racine primitive $g$, et de l'entier $a$ choisi dans $\{1, ..., p-1\}$ renvoie le couple clé publique, clé privée ($= a$)...

  >>> def cles(p,g,a):
  ...     A = g**a%p
  ...     publique = (p,g,A)
  ...     prive = a
  ...     return (publique, prive)
  ... 

Alice doit utiliser cette fonction pour générer sa clé publique $A$, à envoyer à Bob : ce dernier l'utilisera pour envoyer un message chiffré à Alice.

Si Alice souhaite envoyer un message chiffré à Bob, ce dernier devra lui-aussi faire appel à la fonction cles pour envoyer une clé publique à Alice.

Chiffrement

Passons au chiffrement :

  >>> def chiffre(message, publique, b):
  ...     (p,g,A) = publique
  ...     B = g**b%p
  ...     c = message*A**b%p
  ...     return (B, c)
  ... 

Ci-dessus, message est le nombre à chiffrer, avec la clé publique publique, et la clé privée b choisie.

Déchiffrement

Il reste à déchiffrer :

  >>> def dechiffre(cryptogramme, publique, prive):
  ...     (p,g,A), a = publique, prive
  ...     (B,c) = cryptogramme
  ...     return B**(p-1-a)*c%p
  ... 

Travaux pratiques

Programmez le chiffrement d'El Gamal au complet.

On proposera à l'utilisateur de générer la clé, de chiffrer un texte ou de le déchiffrer.