Le « problème du logarithme discret » en cryptographie

Piste noire Le 14 mars 2015  - Ecrit par  Christophe Delaunay Voir les commentaires (3)

Une approche du problème du logarithme discret pour les enseignants.

Prérequis

  • Nombres premiers ;
  • algorithme d’Euclide, pgcd ;
  • congruences et anneau $\mathbb{Z}/n\mathbb{Z}$.

Introduction

Étymologiquement, le mot cryptographie provient du grec : kruptos (caché) et graphein (écrire). Le cryptographe essaie donc de mettre en place
des systèmes cryptographiques, ou cryptosystèmes, fiables pour chiffrer (ou sécuriser) des messages circulant dans un réseau
de communication. De son côté, le cryptanalyste tente de disséquer le système utilisé afin de trouver des failles et d’obtenir une information
à partir du message codé, appelé cryptogramme. Cryptographie et cryptanalyse font tous deux partie du domaine général qu’est la cryptologie :
la science du secret (voir aussi ici).

On se place dans la situation suivante : deux personnes, habituellement dénommées Alice et Bob, échangent des informations via
un réseau et un intrus, Charlie ou Eve, espionne les transmissions. Dans ce contexte, les quatre buts principaux de la cryptographie sont :

  • la confidentialité : les textes codés et envoyés par Alice et Bob ne doivent pas être compris par Charlie ;
  • l’authentification : Bob doit pouvoir être sûr que l’auteur du message est bien Alice et non une autre personne ;
  • l’intégrité : le message d’Alice reçu par Bob n’a pas pu être modifié par Charlie lors de la transmission ;
  • la non-répudiation : Alice ne peut pas nier être l’auteur et avoir envoyé son message une fois que celui-ci est transmis.

À ces quatre buts s’ajoutent quelques autres comme, par exemple, jouer à pile ou face au téléphone.

Il y a deux grandes familles de cryptographie : la cryptographie à clef secrète (ou symétrique) et la cryptographie à clef publique (ou asymétrique).

Cryptographie à clef secrète

Le principe de la cryptographie à clef secrète est probablement le principe le plus naturel auquel on pense lorsqu’on envisage de cacher une information :
l’émetteur et le récepteur partagent un secret commun qui permet de chiffrer et de déchiffrer un texte. Les opérations pour le codage et pour le décodage sont
alors essentiellement les mêmes, d’où le qualificatif « symétrique » pour de tels cryptosystèmes.

Exemples  :

  • Dans un chiffrement à la César, on effectue un décalage constant des lettres du message. En simplifiant, il s’agit de travailler
    dans ${\mathbb{Z}}/26{\mathbb{Z}}$ en identifiant la lettre « A » à $\overline{1}$, « B » à $\overline{2}$, etc. La clef secrète est alors un élément, $\overline{s}\in {\mathbb{Z}}/26{\mathbb{Z}}$.
    Coder consiste à ajouter $\overline{s}$ à chacune des lettres du message alors que soustraire
    $\overline{s}$ à chaque lettre du message codé est l’opération de décodage.
  • Pour le chiffrement à la Vigenère, on réalise des décalages sur des blocs du message. La clef secrète est
    alors un mot de $\ell$ lettres de l’alphabet ${\mathbb{Z}}/26{\mathbb{Z}}$, $\overline{s_1}\,\overline{s_2}\cdots \overline{s_\ell}$. On partage le message à coder en
    blocs de $\ell$ lettres et pour chacun d’eux, on ajoute $\overline{s_1}$ à la première lettre, $\overline{s_2}$ à la deuxième, etc. En particulier, un
    chiffrement à la Vigenère avec un mot d’une seule lettre (i.e. $\ell =1$) est un chiffrement à la César. Le chiffrement à la Vigenère ou à la César
    ne perturbent pas suffisamment la structure du langage et une analyse statistique permet de retrouver facilement la clef et de casser tous les
    systèmes de ce type.
  • La machine Enigma était le cryptosystème utilisé par les Allemands lors de la seconde guerre mondiale. Certaines circonstances favorables
    (erreurs d’utilisation, vol