Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Codes secrets et arithmétique modulo n
Article mis en ligne le 20 octobre 2007
dernière modification le 20 septembre 2014

par Laurent Bloch
logo imprimer
Licence : CC by-nd

 Le problème de l’échange de clés de chiffrement

Si Arnaud veut entretenir une correspondance secrète avec Béatrice, ils peuvent convenir de la chiffrer selon un code secret. Pour établir cette convention, ils devront se rencontrer, ce qui peut être impossible, ou se communiquer le code par la poste : dans les deux cas, l’instant de l’échange est celui dont un espion peut profiter pour dérober leur secret et ainsi réduire à néant la sûreté de leurs communications.

Un code secret est généralement fondé sur un texte ou un groupe de nombres, appelé clé de chiffrement, qui sera combinée au texte clair pour produire un texte chiffré, indéchiffrable par qui ne possède pas la clé. Ainsi le problème évoqué à l’alinéa précédent est-il connu comme le problème de l’échange des clés.

Avec l’utilisation de l’ordinateur et des télétransmissions, et la dématérialisation de l’information qu’ils autorisent, le problème se pose différemment.

Au milieu des années 1970 Whitfield Diffie et Martin Hellman cherchaient une méthode pour convenir d’un secret partagé sans le faire circuler entre les participants, en d’autres termes une fonction mathématique telle que les participants puissent échanger des informations dont eux seuls pourraient déduire le secret. Les caractéristiques souhaitées d’une telle fonction sont la relative facilité de calcul dans le sens direct, et la quasi-impossibilité de calculer la fonction réciproque. Ainsi, si s est le secret en clair, F la fonction de chiffrement, c le secret chiffré, D la fonction de déchiffrement, il faut que c = F(s) soit facile à calculer, mais s = D(c) pratiquement impossible à calculer pour tout autre que les participants — au prix de quel stratagème, c’est ce que nous allons voir.

 Fondements mathématiques : arithmétique modulo n

La solution au problème que se posaient Diffie et Hellman repose sur un chapitre de l’arithmétique très utilisé par les informaticiens, l’arithmétique modulaire, soit l’arithmétique fondée sur les classes d’équivalence modulo n.

Considérons l’ensemble des entiers relatifs \mathbb{Z} muni de l’addition et de la multiplication. La division entière de a par b que nous avons apprise à l’école primaire y est définie ainsi :


a \div b \rightarrow a = b \times q + r

q est le quotient et r le reste de la division. Ainsi :


13 \div 3 \rightarrow 13 = 3 \times 4 +1

Intéressons-nous maintenant à tous les nombres qui, divisés par un nombre donné n, par exemple 3, donnent le même reste r. Nous avons déjà trouvé un nombre, 13, pour lequel r =1 ; donnons-en quelques autres :


\begin{array}{rcl}
1 \div 3 & \rightarrow & 3 \times 0 +1 \\
4 \div 3 & \rightarrow & 3 \times 1 +1 \\
7 \div 3 & \rightarrow & 3 \times 2 +1 \\
10 \div 3 & \rightarrow & 3 \times 3 +1 \\
13 \div 3 & \rightarrow & 3 \times 4 +1 \\
16 \div 3 & \rightarrow & 3 \times 5 +1 \\
\end{array}

On dit que ces nombres constituent une classe d’équivalence, et qu’ils sont tous équivalents à 1 mod 3 (prononcer « un modulo trois »), ce qui s’écrit :


\begin{array}{l}
4 \equiv 1 \bmod 3 \\
7 \equiv 1 \bmod 3 \\
\ldots
\end{array}

On construit de la même façon une classe des nombres équivalents à 0 mod 3, qui contient -6, -3, 0, 3, 6, 9, 12, ..., et une classe des nombres équivalents à 2 mod 3, avec -7, -4, -1, 2, 5, 8, 11...

Il y a une différence subtile entre m = n1 mod n2 et le reste r de la division de n1 par n2 : tant que n1 et n2 sont de même signe, et notamment positifs, m=r. Sinon, r est du signe de n1 et m du signe de n2 :


\begin{array}{rcl}
13 \bmod 4 & = & 1 \\
reste(13 \div 4) & =  &1 \\
-13 \bmod 4 & = & 3 \\
reste(-13 \div 4) & =  & -1 \\
13 \bmod -4 & = & -3 \\
reste(13 \div -4) & = & 1 \\
-13 \bmod -4 & = & -1 \\
reste(-13 \div -4) & = & -1 \\
\end{array}

On peut définir une addition modulaire, par exemple ici l’addition mod 3 :


\begin{array}{rcl}
4+7 \pmod{3} & = & (4+7) \bmod 3 \\
        & = & 11 \bmod 3 \\
        & = & 2 \bmod 3 \\
\end{array}

On démontre (exercice laissé au lecteur) que l’ensemble des classes d’équivalence modulo n muni de cette relation d’équivalence (réflexive, transitive) et de cette addition qui possède les bonnes propriétés (associative, commutative, existence d’un élément neutre 0 mod n et d’un symétrique pour chaque élément) possède une structure de groupe appelé groupe additif \mathbb{Z}_n</math (prononcé « \mathbb{Z} modulo n »).

On peut aussi faire des multiplications :


\begin{array}{rcl}
4 \times 7 \pmod{3} & = & (4 \times 7) \bmod 3 \\
        & = & 28 \bmod 3 \\
        & = & 1 \bmod 3 \\
\end{array}

Nous pouvons montrer là aussi que la multiplication modulo 3 possède toutes les bonnes propriétés qui font de notre ensemble de classes d’équivalence un groupe pour la multiplication, mais cela n’est vrai que parce que 3 est premier. En effet si nous essayons avec les classes d’équivalence modulo 12, nous aurons des diviseurs de zéro, ce qui détruit la structure de groupe, ce qu’illustre la seconde des expressions suivantes :


\begin{array}{rcl}
4 \times 7 \pmod{12} & = & (4 \times 7) \bmod 12  \\
        & = & 28 \bmod 12 \\
        & = & 4 \bmod 12 \\
\end{array}


\begin{array}{rcl}
4 \times 6 \pmod{12} & = & (4 \times 6) \bmod 12 \\
        & = & 24 \bmod 12 \\
        & = & 0 \bmod 12 \\
\end{array}

Dans la seconde expression, le produit de 4 et 6 est nul, ce qui est très regrettable. Aussi pourrons-nous bien définir un groupe multiplicatif \mathbb{Z}^*_n, qui, si n est premier, aura les mêmes éléments que le groupe additif \mathbb{Z}_n à l’exclusion de 0, alors que si n n’est pas premier il faudra en retrancher les classes correspondant aux diviseurs de n et à leurs multiples :


\begin{array}{lcl}
\mathbb{Z}^*_{3}& = &\{1, 2\} \\
\mathbb{Z}^*_{12}& = &\{1, 5, 7, 11\} \\
\mathbb{Z}^*_{15}& = &\{1, 2, 4, 7, 8, 11, 13, 14\}
\end{array}

Dans ce groupe multiplicatif chaque élément a un inverse (sinon ce ne serait pas un groupe) :


\begin{array}{rcl}
5 \times 5 \bmod 12 & = & 25 \bmod 12 \\
        & = & 1 \bmod 12 \\
7 \times 7 \bmod 12 & = & 49 \bmod 12 \\
        & = & 1 \bmod 12 \\
11 \times 11 \bmod 12 & = & 121 \bmod 12 \\
        & = & 1 \bmod 12 \\
\\
7 \times 13 \bmod 15 & = & 91 \bmod 15 \\
        & = &1 \bmod 15
\end{array}

On note que les calculs sont faciles mais les résultats assez imprévisibles : justement, c’est le but que poursuivent nos deux cryptographes. La fonction y=ax n’est pas monotone. L’exponentielle est définie :


\begin{array}{rcl}
5^3 \bmod 11 & = & 125 \bmod 11 \\
        & = & 4
\end{array}

elle a les mêmes propriétés que dans \mathbb{Z}, notamment :


(a^x)^y = (a^y)^x = a^{x . y}

et en outre si n est premier a^x n’est jamais nul .

 Mise en oeuvre de l’algorithme Diffie-Hellman

Voici maintenant le protocole d’échange de clés de Diffie-Hellman, illustré par un exemple avec de petits nombres pour pouvoir faire les calculs à la main. Martin Hellman en a eu l’inspiration une nuit, mais il est le résultat de leur travail commun, auquel d’ailleurs il faut adjoindre Ralph Merkle. Le protocole repose sur une fonction de la forme K=W^X \bmod P, avec P premier et W < P. Une telle fonction est très facile à calculer, mais la connaissance de K ne permet pas d’en déduire facilement X. Cette fonction est publique, ainsi que les valeurs de W et P. Prenons W=7 et P=11, par exemple.

Le lecteur attentif remarquera que beaucoup d’auteurs utilisent cet exemple numérique. S’il se donne la peine de quelques essais personnels il constatera qu’il y a une bonne raison à cela : les autres valeurs numériques suffisamment petites donnent des résultats corrects mais peu pédagogiques du fait de coïncidences fâcheuses.

  1. Aïcha choisit un nombre qui restera son secret, disons A = 3.
  2. Boris choisit un nombre qui restera son secret, disons B = 6.
  3. Aïcha et Boris veulent échanger la clé secrète, qui est en fait S=W^{B.A} \bmod P, mais ils ne la connaissent pas encore, puisque chacun ne connaît que A ou B, mais pas les deux.
  4. Aïcha applique à A la fonction à sens unique, soit α le résultat :


\begin{array}{rcl}
\alpha & = & W^A \bmod P \\
        & = & 7^3 \bmod 11 \\
        & = & 343 \bmod 11 \\
        & = & 2
\end{array}

  1. Boris applique à B la fonction à sens unique, soit β le résultat :


\begin{array}{rcl}
\beta & = & W^B \bmod P \\
        & = & 7^6 \bmod 11 \\
        & = & 117~;649  \bmod 11 \\
        & = & 4
\end{array}

  1. Aïcha envoie α à Boris, et Boris lui envoie
    β, comme représenté par la figure.
    α et β ne sont pas la clé, ils peuvent être
    connus de la terre entière sans que le secret d’Aïcha et de Boris
    soit divulgué.
  2. Aïcha a reçu β et calcule \beta^A \bmod P (qui est, soit dit en passant, (W^B)^A \bmod P, soit 7^{B . A} \bmod 11, mais elle ne connaît pas B) :


\begin{array}{rcl}
\beta^A \bmod P & = & 4^3 \bmod 11 \\
        & = & 64 \bmod 11 \\
        & = & 9
\end{array}

  1. Boris a reçu α et calcule \alpha^B \bmod P (qui est, soit dit en passant, (W^A)^B \bmod P, soit 7^{A . B} \bmod 11, mais il ne connaît pas A) :


\begin{array}{rcl}
\alpha^B \bmod P & = & 2^6 \bmod 11 \\
        & = &  64 \bmod 11 \\
        & = & 9
\end{array}

Aïcha et Boris obtiennent à la fin de leurs calculs respectifs le même nombre 9 qui n’a jamais été exposé à la vue des indiscrets : c’est la clé S ! N’est-ce pas miraculeux ? Ils ont simplement échangé l’information nécessaire pour calculer la clé, sans divulguer celle-ci.

Supposons que l’abject Jean-Kevin veuille épier les conversations d’Aïcha avec Boris : il pourra intercepter l’échange des messages non chiffrés α et β, à partir desquels il veut calculer S = \alpha^B \bmod P. Il ignore S et B. L’équation à résoudre pour calculer B consiste à calculer la fonction réciproque de la fonction à sens unique :


W^B = \beta \bmod P

Si nous étions dans le monde des nombres réels la solution serait triviale :


B = \frac{\log \beta}{\log W}

Mais, dans le monde des classes d’équivalence modulo n, ce problème dit du logarithme discret n’a pas de solution simple, on ne connaît pas d’algorithme rapide pour le calculer. C’est un sujet de recherche. Le « front » est aujourd’hui à des valeurs de P qui sont des nombres de 450 chiffres binaires. L’algorithme est sûr si P a 512 chiffres binaires.

L’algorithme de Diffie-Hellman est sans doute une découverte majeure, totalement contraire à l’intuition. Il procure à deux acteurs d’un cryptosystème le moyen d’échanger une clé sans la faire circuler sur le réseau. Mais il restait à faire une découverte encore plus stupéfiante, inspirée d’ailleurs par celle que nous venons de décrire : un cryptosystème fondé sur des paires de clés dont l’un des deux éléments, la clé de chiffrement, est publiée dans des annuaires publics !

P.S. :

P.-S. :

Ce texte est une version revue d’un passage de mon livre Systèmes d’exploitation des ordinateurs : histoire, fonctionnement, enjeux, avec l’aimable autorisation des Éditions Vuibert.

Vous pourrez poursuivre vos lectures sur des sujets voisins dans le livre que j’ai écrit avec Christophe Wolfhugel et publié chez Eyrolles, Sécurité informatique — Principes et méthode. Mentionnons aussi le livre de Pierre Wassef, Arithmétique : application aux codes correcteurs et à la cryptographie : Cours & 122 exercices corrigés licence de mathématiques chez Vuibert.

Il convient de mentionner ici ma dette intellectuelle envers Jean-Marc Ehresmann, François Bayen, et les livres de Simon Singh « Histoire des codes secrets » et de Thomas Cormen, Charles Leiserson, Ronald Rivest et Clifford Stein « Introduction à l’algorithmique ».


Forum
Répondre à cet article


pucePlan du site puceContact puceMentions légales puceEspace rédacteurs puce

RSS

2004-2017 © Site WWW de Laurent Bloch - Tous droits réservés
Site réalisé sous SPIP
avec le squelette ESCAL-V3
Version : 3.87.31