La génération de la paire de clés du système cryptographique RSA.

Les principes du système RSA ont déjà été expliqués, mais maintenant il nous faut les implémenter.  D'abord il faut générer un jeu de clés publiques et privés.  L'essentiel consiste à trouver deux grands nombres premiers p et q, et une clé publique e, qui est un nombre premier relatif à Phi(p.q).

Nous avons tous les outils pour mettre cela en place.  Cependant, nous allons d'abord introduire trois fonctions auxiliaires pour rendre la vie plus facile.  La première sert à générer un grand nombre aléatoire.  Nous avons fait quelque chose qui est une mauvaise idée en général: nous avons utilisé le générateur pseudo-aléatoire de la librairie standard C.  C'est une mauvaise idée car ce générateur n'est pas cryptographiquement sûr.  Il faut donc bien comprendre que ce code sert à illustrer, mais n'est pas utilisable pour une vraie application cryptographique, car le générateur de nombres aléatoires ne convient pas.  Dans une vraie application cryptographique, il faut le remplacer, idéalement, par un vrai générateur de nombres aléatoires.  Entrop-X peut vous aider dans ce domaine. 

Nous voulons rappeler: Exemples de code

void randomgen(number* myran)
/* generate a random number in the modular ring */
  {
  number rawran;
  number q;
  int i;

  for (i = 0 ; i < nofdigits ; i++)
    {
      rawran.digit[i] = rand() % basis ; 
    }
  dividenum(&rawran,&modulo,&q,myran);
  } // end randomgen

Comme déjà mentionné, c'est un générateur simpliste, qui ne sert que pour des raisons illustratives.  Il ne faut pas l'utiliser pour une vraie application cryptographique.

La deuxième fonction auxiliaire est une conversion d'un nombre "machine" en un "gros nombre":

void makebig(int small, number* big)
/* convert a machine integer into a big number */
  {
  int i;
  int r;
  int q;
  for (i = 0 ; i < nofdigits ; i++)
    {
    big->digit[i] = 0;
    }
  i = 0;
  q = small;
  do
    {
    r = q % basis;
    q = q / basis;
    big->digit[i] = r;
    i++;
    }
  while (q > 0); 
  } // end makebig

La troisième fonction trouve le premier nombre premier, qui est plus grand qu'un nombre donné:

 void findnextprimerabin(number* x, number* y, int k)
/* using Miller-Rabin's primality test, finds the first prime that follows x */
  {
  number nextone;
  number nextnextone;
  number one;
  number q;
  int r;
  int i;
  for (i = 0 ; i < nofdigits ; i++)
    {
    one.digit[i] = 0;
    }
  one.digit[0] = 1;
  divide2(x,&q,&r);
  if (r == 1)
    {
    // x is uneven, OK
    sumnum(x,&one,&nextone);
    }
  else
    {
    // x is even, we need to add one
    sumnum(x,&one,&nextnextone);
    sumnum(&nextnextone,&one,&nextone);
    }
  do
    {
    sumnum(&nextone,&one,&nextnextone);
    sumnum(&nextnextone,&one,&nextone);
    }
  while (isprimerabin(&nextnextone,k) == 0);
  difnum(&nextone,&one,y);
  } // end findnextprimerabin

Avec ces trois fonctions auxiliaires, nous pouvons finalement construire un générateur de paire de clés RSA:

void rsakeygen(int nbits, number* p1, number* p2, number* n, number* pkey, number* skey)
  {
  number oldmodulo;
  number zero;
  number one;
  number two;
  number allbits;
  number nbitsbig;
  number ran1;
  number ranlim;
  number dummy;
  number dummy2;
  number p1m1;
  number p2m1;
  number phin;
  number gcd;
  int i;

  /* we first test that the number of bits of the keys is less than half the available number of bits in our integers */
  if (nbits > basisbits * (nofdigits - 1) / 2 ) 
    {
    printf("rsakeygen error: nbits too large. \n");
    }

  /* we put the current modulus away and set the modulus to the 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 */
  makebig(nbits,&nbitsbig);
  power(&two,&nbitsbig,&allbits);
  /* we find the first prime p1 */
  do
    {
    randomgen(&ran1);
    dividenum(&ran1,&allbits,&dummy,&ranlim);
    findnextprimerabin(&ranlim,p1,20);
    }
  while (isbigger(p1,&allbits) != -1);
  /* we find the second prime p2 */
  do
    {
    randomgen(&ran1);
    dividenum(&ran1,&allbits,&dummy,&ranlim);
    findnextprimerabin(&ranlim,p2,20);
    }
  while (isbigger(p2,&allbits) != -1);
  timesnum(p1,p2,n);
  difnum(p1,&one,&p1m1);
  difnum(p2,&one,&p2m1);
  timesnum(&p1m1,&p2m1,&phin);
  /* we now find a number e (called pkey) such that gcd(e,phin) = 1 */
  do
    {
    randomgen(&ran1);
    dividenum(&ran1,&phin,&dummy,pkey);
    exteuclid(pkey, &phin, &gcd, &dummy, &dummy2);
    }
  while (isbigger(&gcd,&one) != 0);
  /* finally, we calculate the private key which is the inverse of pkey in the ring modulo phin */
  /* we write phin in the modulus */
  for (i = 0 ; i < nofdigits ; i++)
    {
    modulo.digit[i] = phin.digit[i];
    }
  inversenum(pkey,skey);
  /* we put the original modulo parameter back */
  for (i = 0 ; i < nofdigits ; i++)
    {
    modulo.digit[i] = oldmodulo.digit[i];
    }  
  } // end rsakeygen

Nous spécifions le nombre de bits sur lequel nous voulons générer les nombres premiers ; les clés seront donc à peu près deux fois ce nombre de bits.  Par exemple, si nous spécifions 80 bits, alors nous aurons des nombres premiers d'à peu près 80 bits, et n, e et d seront à peu près de 160 bits.  Ainsi, il faut qu'on teste que le système de gros nombres pourra bien supporter deux fois le nombre de bits spécifiés, car sinon la génération de clés ne pourra pas se faire dans cet anneau numérique.

Nous mettons le module de l'anneau à son maximum, et nous générons le plus gros nombre qui a le nombre spécifié de bits.  En générant un nombre aléatoire et en prenant le reste par division par ce plus gros nombre, nous allons obtenir un nombre aléatoire qui est plus petit que ce nombre maximal.  De ce nombre aléatoire, nous cherchons le premier nombre premier qui est plus grand.  Bien sûr, il est possible que la recherche d'un nombre premier nous fait dépasser la limite supérieure et aura besoin de plus de bits que spécifié ; ainsi il nous faut quand-même tester finalement si le nombre premier ainsi déterminé est bien encore de la bonne taille.  Si ce n'est pas le cas, il faut en générer un autre jusqu'à ce qu'on en trouve un qui est bien de la bonne taille.  Ceci nous donnera donc notre premier nombre premier aléatoire.  En répétant la procédure pour le deuxième nombre premier, nous obtenons les deux nombres premiers p et q (que nous appelons p1 et p2 dans le code).

Maintenant nous pouvons calculer n = p.q et Phi(n) = (p-1).(q-1).

En suite nous devons trouver la clé publique e (qui est appelée pkey dans le code), qui doit être un nombre premier relatif à Phi(n).  Nous générons un nombre aléatoire et nous prenons le reste de sa division par Phi(n), ce qui nous garantit que le nombre est bien inférieur à Phi(n).  Nous testons si ce nombre est bien un nombre premier relatif à Phi(n) ; si ce n'est pas le cas, il faut en générer un autre jusqu'à ce que nous en trouvons un qui est bien un nombre premier relatif à Phi(n).

Pour générer la clé privé, qui n'est rien d'autre que l'inverse multiplicatif de e dans l'anneau modulaire avec module Phi(n), nous mettons le module du système de nombres égal à Phi(n) et nous invoquons simplement l'inversion multiplicative de e.  Ceci nous donne la clé privé d, qui est appelée skey dans le code.

Bien sûr, la vraie clé privée est le couple de nombres premiers p et q, ainsi que le nombre e.  Avec ceux-là, on peut tout calculer.  Mais une fois qu'on a calculé n et d, on peut en fait oublier p et q.  Alors la clé publique est (e,n) et la clé privé est (d,n).  Il est vrai que une fois oubliée la vraie clé privée (p,q,e), il n'est plus possible de déduire la clé publique (e,n) de la clé privée (d,n).  En fait, la paire (e,n) et la paire (d,n) sont symétriques, dans le sens qu'on peut aussi bien prendre (e,n) comme clé privée, et (d,n) comme clé publique autant qu'on prend (e,n) comme clé publique et (d,n) comme clé privée.

Nous voulons encore souligner que notre implémentation de la génération d'une pair de clés RSA est cryptographiquement correcte, sauf pour la source d'entropie.  N'utilisez pas le générateur de nombres pseudo-aléatoires de la librairie C standard pour des applications réelles.

Chiffrement et déchiffrement

Bien que le crypto système RSA est un système asymétrique - c'était en fait historiquement le premier système cryptographique asymétrique adopté largement et le premier système qui à permis le monde d'accéder à la cryptographie asymétrique - sa structure est totalement symétrique.  La seule différence entre "public" et "privé", est le choix d'appeler une clé la clé publique (e,n) et l'autre clé, la clé privée.  L'algorithme de chiffrement et de déchiffrement est le même.  Il dépend de quelle clé on applique.  La longueur du message est donnée par la longueur de n, donc c'est essentiellement la longueur de clé.  Il y a une fluctuation dans la longueur du message possible car n est finalement un nombre aléatoire.  Comme le message doit se tenir dans l'anneau modulaire à module n, sa longueur est donc limitée par celle de n.  Par exemple, si les nombres premiers p et q sont des nombres "1024 bit", alors n ne sera pas beaucoup plus petit que 22048.  Si nous prenons un message de, disons, 2000 bits, cela marchera pour la plupart des clés: il faut que n soit plus grand que 22000 ce qui n'est pas le cas seulement dans un cas sur 248

void rsacrypt(number* cleartext,number* pkey, number* n, number* cyphertext)
/* this procedure uses an existing public key to do RSA encryption */
/* it is also the procedure to decrypt: one puts the private key in, and the cypher text */
  {
  number oldmodulo;
  int i;

  /* we put the current modulus away and set the modulus to n */
  for (i = 0 ; i < nofdigits ; i++)
    {
    oldmodulo.digit[i] = modulo.digit[i];
    modulo.digit[i] = n->digit[i];
    }
  power(cleartext,pkey,cyphertext);
    /* we put the original modulo parameter back */
  for (i = 0 ; i < nofdigits ; i++)
    {
    modulo.digit[i] = oldmodulo.digit[i];
    }  
  }

Le code va de soi.  Nous mettons comme module, le nombre n, et alors le chiffrement ou le déchiffrement est simplement une exponentiation.  Les noms des variables sont logiques pour le cas du "chiffrement", mais pour le déchiffrement, il faut échanger "cleartext" et "cyphertext", et remplacer "pkey" par "skey".

La signature numérique RSA

La symétrie entre chiffrement et déchiffrement dans le système RSA et l'interchangeabilité de la clé publique et privée qui en suit, font que le système RSA est particulièrement bien adapté aux signatures numériques.  Effectivement, en mode "chiffrement", la clé publique (e,n) sert à faire le chiffrement, et la clé privée (d,n) à faire le déchiffrement.  Mais si on échange les rôles, (d,n) sert à chiffrer, et (e,n) sert à déchiffrer.  Ainsi, quelque chose qui est chiffrée par (d,n) peut être déchiffrée par (e,n), mais ne peut pas être produite par (e,n).  C'est exactement ce qu'il faut pour une signature numérique: seulement le propriétaire de la clé privée, (d,n), peut "chiffrer" c.a.d. signer, un message, mais tout le monde peut le déchiffrer avec la clé publique et donc vérifier que c'était bien chiffré avec (d,n).  Si la vérification du déchiffrement marche, c'est que le chiffrement a été fait avec (d,n), et seulement son propriétaire a pu faire cela.  C'est donc bien une signature produite par ce propriétaire, et personne d'autre.

Commentaires

Le système cryptographique RSA est historiquement le premier système cryptographique asymétrique connue publiquement, et il est toujours robuste et utilisé.  Le seul problème avec RSA est qu'il faut des longueurs de clé très importantes car il existe des techniques de factorisation en nombres premiers relativement efficaces.  Des clés de 1024 bits sont un minimum (donc des nombres premiers de 512 bits), et il est avisé d'utiliser des clés de 2048 bits ou d'avantage si on veut une sécurité solide.  Ainsi, c'est un système qui demande beaucoup de puissance de calcul, et prend de la place.  Les systèmes asymétriques basées sur les courbes elliptiques sont maintenant souvent préférés sur RSA pour des raisons de vitesse et de longueurs de clé.

Cependant, le système RSA est important dans le sens suivant: c'est un système conceptuellement simple, comme nous l'avons démontré ici.  Quand les principes sont compris, il n'est pas difficile de l'implémenter.  Ainsi, il devient essentiellement impossible d'interdire la cryptographie sûre et efficace.  On peut ré-écrire un code RSA en un rien de temps sans besoin de quoi que ce soit.  Aucune convention ne doit être implémentée.  Deux nombres, (e et n) sont la clé publique et c'est tout ce dont on a besoin pour communiquer sûrement.  Il ne faut pas distribuer un logiciel.  On peut le faire chez soi, à la maison.  Les exemples de code ici sur entrop-x sont suffisants pour pouvoir communiquer sûrement.  La simplicité du système RSA implique donc que la cryptographie asymétrique est maintenant sortie de la boîte de Pandore pour toujours.  Le niveau de sécurité peut être augmenté à volonté en augmentant le nombre de bits.  Cela augmentera l'effort de calcul nécessaire, mais comme le principe est simple, ce calcul peut être fait sur n'importe quel ordinateur.

Comme nous avons dit, le système RSA est lourd sur le plan de la consommation de ressources et sur ce plan, il y a maintenant de plus en plus de succès d'autres systèmes.