Introduction

L'échange de clés Diffie-Hellman est un système cryptographique asymétrique qui permet d'établir un secret commun (souvent une clé secrète) en utilsant un canal non sûr.  Ainsi, le système Diffie-Hellman ne permet pas, à première vue, de chiffrer directement un message comme on pourrait s'attendre d'un crypto système, mais peut permettre indirectement d'établir une clé secrète commune qui peut être utilisée après coup par un système cryptographique symétrique.  Le système D-H est historiquement basé sur le groupe multiplicatif d'un champs modulaire.

Il y a des extensions du système original D-H qui permettent de chiffrer des données et de faire des signatures numériques ; il y a aussi des extensions du principe  D-H à d'autres groupes cycliques que le groupe multiplicatif d'un champs modulaire.  Dans cette contribution, nous allons nous limiter à la version historique du groupe multiplicatif d'un champs modulaire et d'un mécanisme de mise en place d'une clé secrète commune.  Même si cela peut paraître limité, il ne faut pas sous-estimer la puissance de l'échange de clé D-H: il permet d'établir une clé secrète à travers un canal non sûr, ce qui était le grand énigme de tous les systèmes cryptographiques symétriques: si vous avez un canal sûr, vous n'avez pas besoin de cryptographie, et si vous n'avez pas de canal sûr, comment alors communiquer la clé secrète ?  D-H est la solution à ce paradoxe.

Nous allons implémenter une version du principe de l'échange de clé D-H dans notre système de gros nombres.

Diffie-Hellman: configuration d'un système

Contrairement à un système cryptographique RSA, où il n'y a pas de convention à faire entre les parties, à part le fait de se mettre d'accord qu'un utilisera le concept RSA, un échange de clés D-H a besoin que les deux parties se mettent d'accord sur une configuration spécifique.  Dans le système standard D-H, cette configuration consiste en un choix d'un champs modulaire (donc, un nombre premier particulier) et un générateur du groupe multiplicatif de ce champs (ou un sous-groupe !).  Cette configuration est entièrement publique et il est tentant de choisir une configuration "connue", qui est publiée.  Cependant, il peuvent y avoir des raisons de trouver une configuration soi-même.  Bien sûr, sur le plan pédagogique, il n'y a pas mieux que de faire soi-même: cela aide la compréhension.  Mais cela aide aussi à être totalement autonome.  Il y a aussi d'autres raisons de choisir sa propre configuration.  Il est maintenant accepté généralement que les configurations D-H communément utilisés, même bien conçus, sont tellement utilisés qu'un investissement dans l'attaque d'un groupe particulier permet de casser la protection de beaucoup de communications et que des agences sponsorisées par des états ont fait exactement cela.  Si vous générez votre propre configuration, il y a plus de possibilités que personne n'a pris la peine d'avoir investi dans l'attaque de ce groupe choisi.  Cela dit, il faut être prudent avec la mise en place d'une configuration D-H, pour deux raisons.  Si nous avons un champs modulaire, cela veut dire que le module est un nombre premier.  Mais le groupe multiplicatif a un élément en moins que le champs, car zéro n'en fait pas parti.  L'ordre du groupe multiplicatif est donc p - 1, ce qui est un nombre pair et ne peut donc être un nombre premier.  Ainsi, il a des diviseurs non-triviaux et pour chaque diviseur, il y a un sous-groupe cyclique.  Si nous choisissons un générateur de façon aléatoire dans le groupe, on peut très bien tomber sur un générateur d'un sous-groupe plutôt qu'un générateur du groupe total.  Ce sous-groupe est alors le vrai groupe, et il peut être relativement petit, bien plus petit que l'ordre du groupe total.    Dans un petit groupe, le problème "impossible" du logarithme discret devient alors abordable, et toute la sécurité du système D-H, qui est basée sur l'impossibilité pratique de trouver un logarithme discret, est mise en cause.  La deuxième raison est que même si on a le bon générateur (donc, du groupe entier), il y a des attaques qui sont rendus plus faciles s'il y a beaucoup de petits sous-groupes.  Il faut donc trouver un nombre premier p, tel que p - 1 n'a pas trop de facteurs relativement petits.  Mais nous savons déjà que p - 1 est un nombre pair.  Donc p - 1 a déjà inévitablement 2 comme diviseur et il y a donc déjà inévitablement un sous-groupe cyclique d'ordre 2.  Mais si nous choisissons un nombre premier aléatoire p, il est essentiellement impossible de trouver les facteurs de p - 1.  Toute la sécurité du système RSA est basée sur cette impossibilité de trouver les facteurs d'un grand nombre comme p - 1.  Donc, choisir un nombre premier au hasard n'est pas la bonne façon de faire.  C'est mieux de construire ce nombre premier.  On fait comme suite:

  1. nous choisissons un grand nombre premier q au hasard
  2. nous calculons p = 2 q  + 1
  3. nous testons si p est un nombre premier ou non. Si non, retour à l'étape 1.

Si p est un nombre premier, alors nous connaissons aussi les facteurs de p - 1: ce sont 2 et q.  Comme q est un nombre premier, il n'y en a pas d'autres.  Des nombres premiers de la forme 2 q + 1 sont appelés des nombres premiers sûrs.  (ils sont parfois confondus avec des nombres premiers "forts").

Si nous connaissons les facteurs de l'ordre du groupe multiplicatif, à savoir q et 2, alors nous savons qu'il n'y a que deux sous-groupes cycliques: un d'ordre 2, et un autre d'ordre q.  C'est la meilleure situation imaginable que nous pouvons avoir pour la configuration D-H.  Idéalement notre générateur est un générateur du groupe en entier.  Mais même si nous avons un générateur du groupe d'ordre q, c'est toujours un grand groupe.  Nous pouvons donc choisir au hasard un élément du groupe comme "générateur" ; nous avons alors une chance sur 2 d'avoir un vrai générateur, et une chance sur 2 d'avoir un générateur du sous-groupe.  Ou bien nous pouvons tester si ce nombre, élevé à la puissance q, nous donne 1.  Si c'est le cas, c'est un générateur du sous-groupe, alors il faut en choisir un autre.  Il faudrait aussi, idéalement, tester si ce n'est pas un générateur du sous-groupe d'ordre 2 (donc 1 ou -1).

Si nous avons un grand nombre premier sûr, et nous avons un bon générateur du groupe, alors nous avons une bonne configuration D-H.

Le code suivant fait exactement cela.  Nous voulons rappeler: Exemples de code

void diffiesetup(int nbits, number* dhprime, number* dhgen)
/* this procedure generates a Diffie-Hellman setup */
  {
  number oldmodulo;
  number zero;
  number one;
  number two;
  number nbitsbig;
  number allbits;
  number ran1;
  number dummy;
  number ranlim;
  number firstprime;
  number firstprime2;
  number test;
  int i;

  /* 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] = basis - 1;
    zero.digit[i] = 0;
    one.digit[i] = 0;
    two.digit[i] = 0;
    }
  one.digit[0] = 1;
  two.digit[0] = 2;
  /* we calculate the highest possible number in agreement with our number of bits (minus 1) */
  makebig(nbits-1,&nbitsbig);
  power(&two,&nbitsbig,&allbits);
  /* we try to find a strong prime, that is a prime number which is equal to 2*q + 1
     where q is also a prime number */
  do
    {
    /* we find the prime firstprime */
    do
      {
      randomgen(&ran1);
      dividenum(&ran1,&allbits,&dummy,&ranlim);
      findnextprimerabin(&ranlim,&firstprime,10);
      }
    while (isbigger(&firstprime,&allbits) != -1);
    //printf("got a first prime \n");
    //printnum(&firstprime);
    /* now, we repeat, such that 2*firstprime + 1 is also a prime: dhprime */
    timesnum(&firstprime,&two,&firstprime2);
    sumnum(&firstprime2,&one,dhprime);
    }
  while (isprimerabin(dhprime,10) == 0);
  /* we now put our Diffie-Hellman strong prime as a modulus */
  for (i = 0 ; i < nofdigits ; i++)
    {
    modulo.digit[i] = dhprime->digit[i];
    }
  /* we find the generator dhgen and test whether it is a primitive root */
  do
    {
    randomgen(&ran1);
    // note that at this point, firstprime2 is dhprime minus 1
    dividenum(&ran1,&firstprime2,&dummy,dhgen);
    power(dhgen,&firstprime,&test);
    }
  while (isbigger(&test,&one) == 0 || isbigger(dhgen,&zero) == 0);
  /* we now have a dhprime which is a strong prime, and

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

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

Le fait d'être le maître de la configuration fait que, une fois les principes bien compris, nous sommes libres de toute information extérieure.  Mais nous pouvons aussi utiliser des configurations D-H publiées.

Génération d'une pair de clés Diffie-Hellman

La configuration étant publique, il n'y a pas besoin, dans la génération de cette configuration, d'avoir un générateur de nombres aléatoires sûr sur le plan cryptographique.  C'est une autre histoire pour la paire de clés.  Nous mettons le lecteur en garde que le code présenté utilises le générateur de nombres aléatoires de la librairie standard C, qui n'est pas sûr du tout, et que son usage n'est que à des fins d'illustration.  N'utilisez pas une pair de clés dans une vraie application avec ce générateur !

La génération de clés en soi dans le système D-H est assez simple: la clé secrète est un nombre aléatoire dans le groupe, et la clé publique est le générateur de la configuration élevé à la puissance de la clé secrète.

void diffiekeypair(number* dhprime, number* dhgen, number* pkey, number* skey)
/* This routine generates a key pair if a given Diffie-Hellman setup is specified */
  {
  number oldmodulo;
  number ran1;
  number dummy;
  number one;
  number dhprimem1;
  int i;  

  /* 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];
    one.digit[i] = 0;
    }
  one.digit[0] = 1;
  difnum(dhprime,&one,&dhprimem1);
  do
    {
    randomgen(&ran1);
    dividenum(&ran1,&dhprimem1,&dummy,skey);
    }
  while (isbigger(skey,&one) != 1);
  power(dhgen,skey,pkey);

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

Le code parle pour lui-même.

La génération de la clé commune

Si deux utilisateurs du système D-H veulent établir une clé commune secrète à travers un canal non sûr, ils doivent se transmettre la configuration à utiliser (s'ils utilisent un logiciel commun, cela peut être implicite, mais il faut bien qu'il y ait un dialogue d'une façon ou d'une autre).  Ils s'échangent alors leurs clés publics mutuels (obtenus dans la configuration convenue).  En utilisant la clé publique de l'autre parti, et sa propre clé secrète, une clé secrète commune peut alors être calculée, sans nécessité de communiquer quelque chose de façon sûre.  C'est ce que fait le morceau de code suivant.  Les noms des variables sont inspirés par le point de vue de l'utilisateur B:
 

void diffiecommon(number* dhprime,number* pkeyA, number* skeyB, number* comkey)
/* given one's own private key, and the other party's public key 
the common secret key is found within a given DH setup */
  {
  number oldmodulo;
  int i;

  /* 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];
    }

  power(pkeyA,skeyB,comkey);

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

 

Commentaires

La simplicité conceptuelle de l'échange de clés Diffie-Hellman dans sa forme classique a des conséquences similaires que la simplicité du crypto système RSA: ce n'est pas difficile d’implémenter à partir de rien, avec seulement la connaissance conceptuelle de son fonctionnement.  Ainsi, ce genre de cryptographie sera toujours sortie de la boîte de Pandore et il n'y a pas moyen d'empêcher les gens de l'utiliser, comme il n'y a pas un besoin d'un "logiciel commun" à distribuer, dont la distribution centralisée pourrait être mise à mal par des autorités voulant éradiquer une cryptographie sûre.

Cela dit, la forme classique de l'échange de clés Diffie-Hellman a besoin de clés très large (au moins 1024 bits, et si on veut avoir une sécurité sérieuse, plus que 2048 bits), et c'est donc un système intensif en calcul.  En plus, contrairement au système RSA qui est un crypto système complet, dans sa version classique, le système Diffie-Hellman permet seulement aux personnes d' établir une clé commune secrète, mais maintenant il faut encore utiliser cette clé pour communiquer ou faire autre chose.

Il y a deux façons de voir le système D-H.  Une vision est que c'est une façon générale d'avoir des clés publiques parmi beaucoup de gens, tel que chaque pair d'individus peut avoir sa propre clé secrète.  Cela implique que tout le monde utilise la même configuration D-H, mais cela a l'avantage d'avoir une distribution de clés publiques connue généralement.  L'autre vision est qu'il faut utiliser le système D-H comme un moyen temporaire entre deux parties pour établir une clé secrète commune pour une seule communication quand ils n'avaient pas la possibilité de s'échanger cette clé de façon sûre.  Dans ce cas, un des deux partis prend l'initiative de commencer la conversation, en proposant une configuration D-H (donc un nombre premier sûr et un générateur), avec une clé publique.  L'autre parti peut alors prendre cette configuration, générer une pair de clés, et renvoyer sa clé publique.  Alors, les deux parties ont maintenant une clé secrète commune, qu'ils peuvent ensuite utiliser pour communiquer avec un système cryptographique symétrique.  C'est dans cette forme que le système D-H n'a besoin d'aucun logiciel commun ou autre convention.