Cryptographie!

Le chiffre ElGamal

  Le chiffre d'El-Gamal est une méthode de cryptographie à clé publique inventée par Taher ElGamal en 1985. Sa sécurité repose, comme le protocole de Diffie et Hellman, sur la difficulté de calculer le logarithme discret. Le destinataire, Bob, possède deux clés :
  • une clé secrète : un entier $s$.
  • une clé publique, qui consiste en un nombre premier $p$, un entier $a$ compris entre 1 et $p-1$, et l'entier $P=a^s\mod p$.
  Si Alice veut envoyer le message $M$ à Bob, $M$ étant un entier compris entre 1 et $p-1$, elle procède de la façon suivante : elle tire au hasard un nombre $k$, et calcule : $$C_1=a^k\mod p\textrm{ et }C_2=MP^k\mod p.$$ Le message chiffré est le couple $(C_1,C_2)$ qu'elle transmet à Bob. A la réception, celui-ci calcule $$R_1=C_1^s\mod p=a^{sk}\mod p=P^k\mod p$$ puis il retrouve $M$ par la formule $$M=C_2R_1^{-1}\mod p=MP^kP^{-k}\mod p.$$   La robustesse de ce système repose sur le fait que, si quelqu'un espionne la conversation d'Alice et Bob, il a en sa possession $a$, $p$, $P=a^s$, $a^k$ et $MP^k$. Pour retrouver $M$, il doit savoir calculer $P^k\mod p$. Ceci impose de trouver $k$ et donc il doit savoir résoudre l'équation suivante (en $k$) $y=a^k\mod p$ pour n'importe quel entier $y$. On appelle ce problème le calcul du logarithme discret modulo p. C'est un problème pour lequel on ne dispose pas d'algorithme rapide.

  Un autre avantage du chiffre d'El-Gamal est qu'il s'agit d'un chiffrement aléatoire (on dit aussi randomisé). En effet, lorsqu'elle veut chiffrer $M$, Alice commence par choisir au hasard un entier $k$. En particulier, si elle envoie deux fois le même message, il n'y a pas de raisons qu'elle choisisse deux fois au hasard le même entier $k$. Ainsi, elle enverra deux messages chiffrés différents pour le même message clair, sans que cela n'influe sur le déchiffrement.

  Le défaut du système d'ElGamal est que le message chiffré est deux fois plus long que le message original. En revanche, le fait d'utiliser un paramètre aléatoire k est un plus en termes de sécurité : le même message M chiffré à 2 moments différents donnera deux messages codés distincts! Ce système est peu utilisé comme méthode directe de cryptographie. En revanche, il est très utilisé dans les procédés de signature électronique, souvent avec des groupes plus compliqués que $(\mathbb Z/p\mathbb Z)^*$, mais dans lesquels il est néanmoins très compliqué de résoudre le problème du logarithme discret.
Consulter aussi