Le chiffrement Elgamal: principe

Le chiffrement Elgamal est une technique de chiffrement qui est une suite logique de l'échange de clés Diffie-Hellmann.   Le grand avantage du chiffrement Elgamal est sa grande simplicité, et elle a surtout son utilité quand le texte chiffré à échanger est relativement court.  Le chiffrement Elgamal doit envoyer deux fois la quantité d'entropie dans le message.  

Le principe est le suivant: la personne qui veut envoyer un message secret (disons, Alice) à une autre personne (disons, Bob), demande à Bob d'établir un système D-H, et de lui envoyer une clé publique (permanente), exactement comme dans un établissement de clé commune.  Bob (qui recevra le message) doit seulement générer une seule paire de clés dont il envoie la clé publique à Alice.  Alice peut aussi récupérer une clé publique de Bob qui a été publiée quelque part par Bob.

Par contre, Alice va devoir générer une nouvelle paire clé publique/clé privée pour chaque bloc à chiffrer.  La taille du bloc est déterminé par la taille du nombre premier qui sert comme base dans le système D-H choisi: par exemple, si nous avons un système avec un nombre premier de base de 2048 bits, les blocs peuvent avoir (un peu moins que) 2048 bits.

Pour le bloc Bi, Alice va avoir calculé une clé privée Si et une clé publique Pi.  Elle va calculer la clé commune avec Bob avec sa paire de clés: Ki et elle va chiffrer le bloc i avec cette clé de la façon suivante:

Ci = Bi . Ki mod p

C'est la base du chiffrement Elgamal: on utilise le produit dans le groupe modulaire p (le nombre premier à la base du système D-H) avec la clé commune comme chiffrement.

Alice envoie le bloc chiffré Ci et la clé publique Pi à Bob.  Bob, qui peut calculer la clé commune Ki à base de la clé publique Pi et sa propre clé secrète permanente, va facilement déchiffrer le message en calculant l' inverse de Ki dans le groupe modulaire p:

Bi = Ci . (Ki)-1 mod p

Il y a donc une échange de clés D-H par bloc.  Il est important qu' Alice génère une nouvelle clé éphémère pour chaque bloc, car sinon, on peut résoudre le système pour la clé commune si jamais on connaît le texte en clair d'un des blocs.

Code

Nous rappelons le cadre: Exemples de code

void elgamalencrypt(number* dhprime, number* key, number* cleartext, number* cypher)
/* given a common D-H key and its prime, a cleartext is encrypted with the Elgamal technique */
  {
  number oldmodulo;
  int i;

  /* we put the current modulus away and set the modulus to the D-H value */
  for (i = 0 ; i < nofdigits ; i++)
    {
    oldmodulo.digit[i] = modulo.digit[i];
    modulo.digit[i] = dhprime->digit[i];
    }

  timesnum(key,cleartext,cypher);

  /* we put the original modulo parameter back */
  for (i = 0 ; i < nofdigits ; i++)
    {
    modulo.digit[i] = oldmodulo.digit[i];
    }  
  }  // end elgamalencrypt

Le chiffrement Elgamal consiste simplement en la multiplication du texte en clair par la clé commune (éphémère) dans le groupe modulaire.

Le déchiffrement Elgamal consiste à calculer l'inverse de la clé dans le groupe modulaire, suivi de la multiplication avec le texte chiffré:

void elgamaldecrypt(number* dhprime, number* key, number* cypher, number* cleartext)
/* given a common D-H key and its prime, a cleartext is encrypted with the Elgamal technique */
  {
  number oldmodulo;
  int i;
  number inversekey;

  /* we put the current modulus away and set the modulus to its maximum */
  for (i = 0 ; i < nofdigits ; i++)
    {
    oldmodulo.digit[i] = modulo.digit[i];
    modulo.digit[i] = dhprime->digit[i];
    }
  inversenum(key,&inversekey);
  timesnum(&inversekey,cypher,cleartext);

  /* we put the original modulo parameter back */
  for (i = 0 ; i < nofdigits ; i++)
    {
    modulo.digit[i] = oldmodulo.digit[i];
    }  
  }  // end elgamaldecrypt

/* ----------------------------------------------- */

Tout ceci, bien sûr, après avoir établi un système Diffie-Hellman et l'établissement d'une clé commune.