Algorithmes discrets utilisés en cryptographie asymétrique

Algorithmes discrets utilisés en cryptographie asymétrique

Dans les articles précédents, nous avons déjà parlé de cryptographie asymétrique, qui consiste en une clé publique pour coder un message, et une clé privée pour le décoder. Dans cet article nous allons détailler quelques algorithmes parmi les plus connus :

  • Le chiffrement RSA , qui est basé sur la difficulté de la factorisation des grands entiers.
  • Le chiffrement El Gamal, basé sur la difficulté de résoudre le problème du logarithme discret.
  • Les systèmes sur les courbes elliptiques, basé sur la difficulté de certains calculs sur les courbes elliptiques définies sur le corps des entiers modulaires
  • .

Quelques rappels concernant le célèbre algorithme RSA

Le cryptage RSA a été inventé par Ron Rivest, Adi Shamir et Leonard Adleman en 1977. Il repose sur la factorisation en nombres premiers d’un entier.

Rappelons comment créer une clé :

  1. Choisir 2 entiers p et q premiers, distincts et suffisamment grands (au moins 100 chiffres chacun) et calculer n = pq.
  2. On a φ(n)=(p-1)(q-1) où φ est la fonction indicatrice d’Euler.
  3. Choisir un entier e compris entre 1 et φ(n) tel que e et φ(n) soient premiers entre eux.
  4. Calculer d tel que d*e=1 [φ(n)]

On obtient ainsi la clé publique qui est le couple (n, e) et la clé privée est d.

Si Alice veut coder un message à l’intention de Ben, il suffit qu’elle connaisse la clé publique de Ben. Elle commence par découper le message à envoyer, en morceaux de longueur plus petite que la moitié du nombre de chiffres qui composent n. Puis elle numérise un de ces morceaux en remplaçant chaque lettre par deux chiffres. Ainsi, les morceaux deviennent des grands entiers modulo n puisque leur longueur est inférieure à celle de n.

L’encodage d’un morceau m se fait en calculant b=m^e[n].
Pour décoder ce message, Benoît cherche à récupérer m à partir de b. Il lui suffit de calculer : b^d[n]=(m^e)^d[n]=m car e.d=1 [φ(n)]
Un espion qui voudrait déchiffrer un message crypté ne peut le faire sans posséder la clé secrète d. Il faudrait alors retrouver psi(n) et donc décomposer n en facteurs premiers, qui s’avère être très difficile pour un très grand nombre.

Tout le problème du cryptage RSA revient donc à trouver 2 entiers p et q premiers suffisamment grands.

Utilisation du logarithme discret

Un autre système cryptographique à clé publique est basé sur le logarithme discret.

Algorithme d’Elgamal

Le bloc de message clair est tout d’abord numérisé grâce à des entiers modulo p.
Le bloc de message clair est tout d’abord numérisé grâce à des entiers modulo p.
Alice choisit un grand nombre a[p-1] qui sera sa clé secrète de décodage. Sa clé publique sera g^a[p].
Pour envoyer un message m, Ben choisit k[p] et envoie le couple (K,M) à Alice, avec:
  • K = g^k[p]
  • M = m.g^(a-k) [p]

Lorsque Alice reçoit le message codé de la part de Ben, elle le déchiffre de la manière suivante :

  • Elle calcule d’abord K^(-a)[p]=g^(-ak)[p]
  • Elle calcule ensuite M.g^(-ak)=m.g^(ak).g^(-ak)[p] qui est congru à m modulo p.
Ainsi, si une tierce personne souhaite cryptanalyser ce système, elle doit retrouver la clé a à partir de la clé publique g^a. Ce qui l’amène à résoudre un problème de logarithme discret de type y=a^x pour y et a donnés, ce qui correspond à trouver le logarithme log(a) y. Comme nous sommes dans le cas des entiers modulo un nombre premier (ici p), lorsque les puissances successives a^x parcourent tous les entiers modulo p, x parcourent tous les entiers modulo p-1 (cela découle du théorème d’Euler-Fermat).

Courbes elliptiques

Définition

Une courbe elliptique est un objet géométrique du plan cartésien R². Il s'agit d'un ensemble de points (x,y) de R² vérifiant:

  • y² = x^3 + ax + b
  • 4 a^3 + 27 b² non nul.
Ces courbes ont des propriétés géométriques assez intéressantes :
  • Une courbe elliptique est symétrique par rapport à l'axe des abscisses (trivial en regardant l'équation en y²).
  • Toute droite coupe une courbe elliptique en au plus trois points.

Structure de groupe commutatif (C,+)

Soit C une courbe elliptique donnée par la donnée de a et b. On peut munir cet ensemble d'un opérateur commutatif "+". Si on prend deux points P et Q de la courbe C, on définit la somme P + Q comme le point R, suivant le protocole suivant:

  • On considère D la droite (PQ)
  • Si elle coupe la courbe en un troisième point K, alors R est le symétrique de K par rapport à l'axe des abscisses.
  • Si les points P et Q sont confondus, alors le point résultant s'appelle le double de P, et se localise comme le symétrique du point d'intersection de la courbe et de la tangente à la courbe en P.
    On peut ainsi définir la notion de multiple de P : n*P = P + P + ... + P.
  • Si elle ne coupe pas la courbe en un troisième point (c'est à dire que la droite (PQ) est parallèle à l'axe des ordonnées), alors on définit un point O, dit à l'infini, comme étant le résultat de cette somme.
On obtient ainsi pour (C,+) une structure de groupe commutatif dont le le point O correspond à l'élément neutre.

Évidemment, dans ca cas, il est facile de calculer les coordonnées de la somme de deux points, connaissant les coordonnées des deux points en question. Il suffit de calculer les coordonnées de l'intersection de la droite passant par les deux points et de la courbe. Puis en prenant l'opposé de l'ordonnée obtenue, on obtient les coordonnées de la somme des deux points.

Ces calculs sont généralisables à d'autres structures de corps, et notamment les corps finis, ce qui nous intéresse ici pour la génération de clés.

Généralisation à d'autres corps

On rappelle que si on a un corps (K, +, x) commutatif, alors la caractéristique de K correspond au plus petit entier positif non nul tel que n*1K = 1K + 1K + ... + 1K = 0K.

Jusque là, nous avons travaillé avec R qui est un corps de caractéristique nulle (car l'entier n n'existe pas).
On peut généraliser la notion de courbe elliptique à des corps de caractéristique strictement plus grande que 3.
On peut démontrer que la caractéristique d'un corps est toujours soit nulle, soit un nombre premier, ce qui va naturellement nous amener à travailler dans les corps (Z/pZ, +, x) avec p premier.



Protocole d'échange de clés et transmission de messages par courbe elliptique

Comme cité ci-dessus, nous travaillons désormais avec :

  • un nombre p premier
  • les courbes elliptiques discrètes (modulo p) qui sont des ensembles de points (x,y) de [0, p-1]² tels que y² soit congru à x^3 + ax + b modulo p.

La structure de groupe commutatif (Cp,+) d'une courbe elliptique modulo p est bien sûre conservée, l'addition de deux points est définie de la même manière, ainsi que le multiple d'un point.

Comment font alors nos chers Alice et Ben pour s'échanger les clés?

Ils utilisent un procédé dit de Diffie et Hellman, c'est à dire qu'ils ne se les communiquent pas directement.

  • Alice et Ben se mettent d'accord publiquement sur une courbe elliptique discrète, c'est à dire par la donnée de a, b et le nombre premier p qui définira la courbe elliptique sur le corps fini Z/pZ.
  • Ils se mettent d'accord également sur le choix d'un point P sur cette courbe.
  • Alice choisit, secrètement, un entier kA, et Ben un entier kB.
  • Alice envoie donc à Ben le point kA*P, et Ben envoie à Alice le point kB*P. Ils peuvent donc tous les deux calculer le point kA*kB*P, par commutativité du groupe (C,+). Il s'agit d'un point de la courbe, qui sera leur clé secrète.

En quoi cette méthode est-elle sûre?

En effet, si quelqu'un a intercepté la partie publique du protocole, alors cet espion aura accès à la courbe elliptique discrète, au point P, ainsi qu'aux points kA*P et kB*P. Mais c'est là que l'utilisation des courbes elliptiques montre sa puissance, car pour trouver le point kA*kB*P, il "suffit" apparemment de calculer kA (ou kB).
Mais calculer kA, connaissant P et kA*P, s'appelle résoudre le logarithme discret sur la courbe elliptique discrète, qui est plus complexe que résoudre le logarithme discret dans (Z/pZ)\{0}, vu la structure compliquée des courbes elliptiques.

D'accord, mais comment font Alice et Ben pour communiquer désormais?

Le message à transmettre doit être codé par une suite de points de la courbe elliptique. On suppose que ceci a été fait en amont du protocole d'échange de clés. Une fois ceci fait, voilà comment se fait la communication:

  • On suppose qu'Alice veuille envoyer le point M à Ben.
  • Alice choisit alors secrètement un nombre d , et envoie à Ben le couple de points (d*P, M+d*kB*P)
  • Ben, qui ne connait ni d, ni M, multiplie d*P par kB, et retranche ce résultat à M+d*kB*P, ce qui donne M.

Encore une fois, si notre espion a intercepté le couple de points, il lui faut connaitre kB pour récupérer M, ce qui revient à résoudre le logarithme discret.

Comparaison avec RSA

RSA est actuellement l'algorithme de cryptage le plus utilisé aujourd'hui.

Mais on constate une différence de complexité pour résoudre le problème de cryptanalyse, c'est à dire décrypter l'information du point de vue de l'espion. On estime que pour un même niveau de sécurité qui nécessite d'utiliser une taille de clés de 1024 bits pour le système RSA, le système par courbe elliptique nécessite une taille de clés de 160 bits.
Mais il faut bien avoir conscience que trouver une courbe elliptique, et trouver un système de codage d'un message clair par des points de cette courbe n'est pas une chose aisée.
Pour plus d'informations sur les courbes elliptiques discrètes, notamment en matière de complexité, de calcul du nombre de points d'une courbe elliptique discrète, vous pouvez voir le lien suivant .

Comments