Un peu d'histoire et beaucoup de mathématiques

Le système cryptographique RSA a été inventé en 1977, et publié en 1978, par trois mathématiciens qui travaillaient alors au MIT : Ronald Rivest, Adi Shamir et Leonard Adleman. Comme vous pouvez le constater, le nom de l’algorithme est simplement tiré des initiales de leurs noms de famille. La grande réussite de leur travail en commun est sans doute due au fait que leurs compétences se complètent.

Rivest est un grand spécialiste de la cryptographie, la discipline qui cherche à protéger les messages d’une lecture inopportune : il est notamment à l’origine de l’algorithme MD5, dont vous avez sans doute entendu parler.

Shamir est au contraire un spécialiste de la cryptanalyse, dont le but est de casser les protections mises en place par la cryptographie : il est notamment connu pour avoir cassé en 1982 le cryptosystème de Merkle-Hellman, un algorithme proche de RSA mais reposant sur une base mathématique un peu différente.

Adleman, quant à lui, représentait le grain de folie du groupe : il travaillait à l’époque sur la bio-informatique, en gros, des ordinateurs utilisant de l’ADN pour faire leurs calculs. Ça vous place le personnage.

Figure : Voici une photo des trois mathématiciens en question.

Le système cryptographique auquel ils ont abouti n’est pas sorti de leur cerveau à partir de rien, telle une Athéna moderne : il repose sur les dernières avancées de l’époque en matière de cryptographie, auxquelles ils ont adjoint un outil mathématique déjà fort ancien. C’est ce que nous allons voir à présent.

Si je vous parle de codes secrets et de messages chiffrés, vous allez penser immédiatement « cryptographie symétrique ».

La formulation vous est, en effet, sans doute inconnue, mais vous connaissez parfaitement le concept. Un système cryptographique est dit symétrique si toute la solidité du chiffrement repose sur un secret — on l’appelle généralement « clé » — qui doit être connu à la fois de l’envoyeur et du récipiendaire.

Par exemple, le chiffre dit « de César » est un système symétrique. Il s’agit de décaler chaque lettre du message d’un certain nombre de rangs dans l’alphabet : avec un décalage de trois rangs, A devient D, B devient E, Z devient C, etc. Ainsi, le message « trololo » devient « wuroror ». Il suffit au récipiendaire de décaler les lettres du message chiffré de trois rangs dans l’autre sens pour retrouver le message d’origine. Et dans l’affaire, la clé n’est autre que le nombre de rangs dont il faut décaler les lettres : cette information doit être connue des seuls interlocuteurs, mais les deux interlocuteurs doivent la connaître.

Petite pause vocabulaire

Il y a des concepts qui reviennent souvent quand on parle de cryptographie, et on a fini par se mettre d’accord sur un vocabulaire commun pour en parler. Afin de pouvoir l’utiliser dans la suite du tutoriel, il me faut vous le présenter.

Un algorithme de chiffrement est un ensemble d’opérations, généralement mathématiques, à effectuer sur le message que l’on veut protéger, afin de le rendre en théorie incompréhensible par ceux auxquels il n’est pas destiné. Il vient toujours avec un algorithme de déchiffrement, qui permet au récipiendaire du message de retrouver le message d’origine. Parfois, ces deux algorithmes sont exactement identiques, comme dans le cas du ROT-13, un cas particulier du chiffre de César.

Tant qu’on y est, le message d’origine, avant toute forme de chiffrement, est appelé message en clair. Une fois qu’un algorithme de chiffrement lui a été appliqué, on l’appelle message chiffré.

Un algorithme de chiffrement/déchiffrement décrit une suite d’opérations qui est la même pour tout le monde. Or, si tout le monde utilise exactement la même méthode pour protéger ses données, tout le monde peut lire les messages des autres, puisque l’algorithme de déchiffrement est le même que pour ses propres messages. C’est pourquoi les algorithmes laissent toujours un tout petit espace pour que l’utilisateur puisse les personnaliser : en gardant secret cet élément de personnalisation, que l’on appelle une (ou des) clé, la protection est assurée. Il s’agit généralement d’un mot ou d’une phrase de passe.

Pour désigner les personnes impliquées dans une opération de chiffrement, on pourrait parler de personne A, personne B, personne C, etc. Mais cette solution serait assez déshumanisée. C’est pourquoi, dans les exemples, on a pris l’habitude de parler d’un couple d’amoureux appelés Alice et Bob, qui tentent de s’écrire sans être dérangés par la vilaine Ève, qui leur veut du mal sans qu’on sache trop pourquoi. Pour ma part, je ferai preuve d’un peu d’originalité, en vous parlant du sympathique Adalbéron, qui désire envoyer quelque missive enflammée à sa douce Brunehaut, sans que le perfide Ébroïn ne vienne y mettre son groin.

Revenons à nos moutons électriques

Pour faire une analogie avec le monde physique, Adalbéron utilise un système symétrique lorsqu’il enferme sa missive dans un coffre solide, fermé par un lourd cadenas. Il ne lui reste plus qu’à envoyer le coffre à Brunehaut, qui l’ouvrira avec son propre exemplaire de la clef, et Ébroïn se trouvera bien embêté.

Il y a juste une faille. Énorme. C’est qu’il faut faire parvenir la clé à Brunehaut. Évidemment, dans le cas d’un vrai couple d’amoureux, les deux tourtereaux se remettent la clé au cours d’un quelconque rendez-vous où ils peuvent se voir physiquement. Mais dans la vraie vie, une telle solution n’est pas toujours possible : connaissez-vous personnellement le directeur du service informatique de votre site de vente en ligne préféré ? Non, bien sûr. Alors comment peut-il vous faire parvenir la clé à utiliser pour chiffrer votre numéro de carte bancaire, sans qu’un individu mal intentionné ne l’intercepte ?

C’est tout un problème.

Et une solution a finalement été trouvée en 1976 par Whitfield Diffie et Martin Hellman : c’est ce que l’on appelle la cryptographie asymétrique. Le principe est double.

Tout d’abord, il n’existe pas une clé, mais deux. La première est appelée clé privée, parce qu’elle ne doit être diffusée à personne, pas même à son interlocuteur. La seconde est la clé publique, parce que tout le monde peut la connaître : ce n’est pas gênant et même plutôt recommandé. Toute la subtilité réside dans le fait que la clé publique peut être facilement générée à partir de la clé privée, mais que la clé privée est presque impossible à retrouver à partir de la clé publique.

Pour reprendre l’analogie du coffre-fort, dans un système asymétrique, Brunehaut ne donne pas une clé à Adalbéron, elle lui donne un cadenas ouvert dont elle seule a la clé. Adalbéron met sa lettre dans un coffre, le ferme à l’aide du cadenas fourni par Brunehaut et, à ce stade, même lui ne peut plus ouvrir le coffre pour accéder à la lettre : seule Brunehaut le peut. Ainsi, plus besoin de transmettre une clé, Brunehaut la garde près d’elle. Et Ébroïn peut bien intercepter le coffre ouvert : la lettre ne s’y trouve pas encore.

Ensuite, l’algorithme de chiffrement lui-même consiste à appliquer une fonction mathématique d’un genre particulier, appelée fonction à sens unique et porte dérobée. Il s’agit d’une fonction dont il est facile de calculer l’image d’un antécédent donné, mais très difficile de calculer l’antécédent d’une image donnée, sauf si l’on possède une certaine information qui permet d’appliquer une nouvelle fonction à l’image, dont le résultat sera l’antécédent.

Je sais. Désolé. C’était le seul moyen de rester général dans mon explication. Car, vous vous en doutez sûrement, une fonction qui remplit ces conditions, cela ne se trouve pas sous le sabot d’un cheval. D’ailleurs, lorsque Diffie et Hellman ont présenté pour la première fois le concept de cryptographie asymétrique, il ne savaient pas encore comment le mettre en pratique.

C’est là qu’interviennent Rivest, Shamir et Adleman. Ils sont les premiers à avoir proposé un cas particulier viable de la théorie générale exposée ci-dessus, qui utilise des concepts mathématiques bien connus et maîtrisés.

Nombres premiers

Le premier de ces concepts qu’il nous faut aborder est celui de primalité. Il est très ancien, puisqu’on en trouve les premières traces certaines dans les Éléments d’Euclide, un traité de mathématiques grecques du IV^e siècle avant notre ère.

Euclide ne travaillait guère qu’avec des entiers (dont l’ensemble est noté $\mathbb Z$). Aussi, la division euclidienne ne donne-t-elle pas de résultat à virgule, mais un quotient entier et éventuellement un reste, entier aussi. Par exemple, 5 divisé par 2, ne donne par 2,5 mais un quotient 2 et un reste 1. Formellement, la division euclidienne se représente ainsi, avec $q$ représentant le quotient et $r$ le reste ($r < b$, sinon ça n’a aucun intérêt).

$\frac {a}{b} \Rightarrow a = b \cdot q + r$

Lorsque le reste est nul, on dit que $a$ est divisible par $b$, ce qui se note $b \ | \ a$ (et qui, pour plus de commodité, se prononce « $b$ divise $a$ »). L’ensemble des nombres entiers, positifs ou négatifs, par lesquels un entier $a$ est divisible est appelé l’ensemble des diviseurs de $a$, et il se note $\mathcal D(a)$. Par exemple, $\mathcal D(10) = \{-10, -5, -2, -1, 1, 2, 5, 10\}$.

Euclide, en son temps, avait déjà remarqué que certains nombres entiers ne faisaient rien comme tout le monde : en effet, ils n’ont que deux diviseurs positifs, 1 et eux-mêmes. On les appelle des nombres premiers. Par exemple, 2, 3, 5, 7, 11, ou encore 53 et 97 sont des nombres premiers. Mais pas 1. Ben non, il n’a pas deux diviseurs positifs, il n’en a qu’un. Et ces nombres premiers sont un des plus grands mystères des mathématiques, qui n’en finissent plus de donner du travail aux mathématiciens depuis plus de deux mille ans qu’on connaît leur existence : la conjecture d’Erdős-Straus, énoncée en 1948, n’a toujours pas été démontrée ni invalidée parce que certains cas particuliers impliquant des nombres premiers résistent encore et toujours. Et ce n’est qu’un exemple parmi tant d’autres : il existe une infinité de nombres premiers, et chacun d’entre eux a sa propre manière de nous casser les pieds.

Cependant, ces nombres premiers sont également à l’origine d’outils mathématiques très intéressants. L’exemple le plus simple, déjà connu d’Euclide, est la décomposition en facteurs premiers : tout nombre entier, s’il n’est pas lui-même premier, est le produit de la multiplication de deux ou plus nombres premiers. Par exemple, $10 = 2 \times 5$, ou encore, $199121 = 13 \times 17^2 \times 53$. Et ce qui est encore mieux, c’est que cette décomposition est unique : il n’existe qu’une seule liste de facteurs premiers qui permette, en les multipliant, d’obtenir un entier donné.

Congruences

Soient trois entiers $a$, $b$ et $n$, ce dernier étant différent de 0. On dit que $a$ est congru à $b$ modulo $n$, ce qui s’écrit $a \equiv b \ [n]$, lorsque le reste de la division euclidienne de $a$ par $n$ est le même que celui de la division euclidienne de $b$ par $n$ : $17 \equiv 13 \ [4]$, puisque $17 = 4 \times 4 + 1$ et $13 = 3 \times 4 + 1$.

Souvent, on s’intéresse surtout au plus petit $b$ avec lequel $a$ est congru modulo $n$ : dans notre exemple, il s’agissait de $1$. Par abus de langage, on dira que $a$ modulo $n$ (noté $a [n]$) est égal à ce plus petit $b$ possible : $17 [4] = 1$.

Il existe quelques propriétés intéressantes avec les congruences, dont trois nous seront utiles par la suite.

$\forall k \in \mathbb N, a \equiv b \ [n] \Rightarrow k \cdot a \equiv k \cdot b \ [n]$

$\forall k \in \mathbb N, a \equiv b \ [n] \Rightarrow a^k \equiv b^k \ [n]$

$a \equiv b \ [n] \Leftrightarrow n \ | \ a - b$

Nombres premiers entre eux

Prenons deux entiers, $a$ et $b$. Pour chacun d’entre eux, il est possible d’établir l’ensemble de leurs diviseurs $\mathcal D(a)$ et $\mathcal D(b)$. Ces deux ensembles peuvent avoir des éléments en commun : c’est l’ensemble des diviseurs communs à $a$ et à $b$, que l’on note $\mathcal D(a, b)$. Par exemple, $\mathcal D(10) = \{-10, -5, -2, -1, 1, 2, 5, 10\}$ et $\mathcal D(15) = \{-15, -5, -3, -1, 1, 3, 5, 15\}$, donc $\mathcal D(10, 15) = \{-5, -1, 1, 5\}$.

On appelle plus grand diviseur commun à $a$ et à $b$ ou $pgcd(a, b)$ le plus grand des éléments de $\mathcal D(a, b)$. Et lorsque le PGCD de deux nombres vaut $1$, on dit que ces deux nombres sont premiers entre eux.

Il existe un moyen simple de déterminer le PGCD de deux nombres : on le nomme algorithme d’Euclide, parce que là encore, c’est le mathématicien grec qui l’a exposé le premier. Il repose sur le résultat suivant.

$pgcd(a, b) = pgcd(b, a[b])$

L’algorithme consiste à appliquer cette formule récursivement jusqu’à ce que $a[b] = 0$. Par exemple, pour $42$ et $30$, les itérations successives de l’algorithme sont les suivantes.

$pgcd(42, 30) = pgcd(30, 12) \text{ puisque } 42 = 1 \times 30 + 12$

$pgcd(30, 12) = pgcd(12, 6) \text{ puisque } 30 = 2 \times 12 + 6$

$pgcd(12, 6) = pgcd(6, 0) \text{ puisque } 12 = 2 \times 6$

$\text{Donc } pgcd(42, 30) = 6$

C’est aussi simple que cela.

Petit théorème de Fermat

On termine avec ce petit théorème, indispensable pour comprendre pourquoi l’algorithme RSA fonctionne bel et bien. Il a été exposé par le mathématicien français Pierre de Fermat en 1640 mais ne sera réellement démontré qu’en 1743 par Leonhard Euler, puis à nouveau d’une manière plus simple par Friedrich Gauss en 1801. Il est relativement simple.

Soient un nombre premier $p$ et un entier $a$ non divisible par $p$.

$a^{p-1} \equiv 1 \ [p]$

En outre, les trois formulations suivantes sont parfaitement équivalentes et parfois plus pratiques d’utilisation.

$p \ | \ a^{p-1} - 1$

$p \ | \ a^p - a$

$a^p \equiv a \ [p]$