La cryptographie : comment l’arithmétique protège nos secrets sur Internet

Problématique

Comment les concepts fondamentaux de l’arithmétique (la congruence, la divisibilité, les nombres premiers et les équations diophantiennes) ont-ils permis de passer du chiffrement symétrique historique au chiffrement asymétrique RSA indispensable à la sécurité d’Internet ?

---

Introduction

Chaque seconde, des millions de données confidentielles (identifiants de connexion, coordonnées bancaires, messages personnels) transitent sur Internet. Sans un système de sécurité inviolable, le commerce électronique, les réseaux sociaux et la communication mondiale s’effondreraient instantanément.

Pourtant, le chiffrement n’est pas né avec Internet : il existe depuis plus de 2 000 ans. Du code de César utilisé par l’armée romaine jusqu’à la célèbre machine Enigma de la Seconde Guerre mondiale, le chiffrement historique reposait sur un principe symétrique : l’expéditeur et le destinataire devaient partager à l’avance une même clé secrète. Ce système pose un problème de taille sur Internet : si deux personnes ne se sont jamais rencontrées physique, comment peuvent-elles s’échanger une clé secrète de manière sécurisée ?

C’est là qu’interviennent les mathématiques modernes. Dans les années 1970, des chercheurs ont utilisé des théories d’arithmétique pure, autrefois jugées sans application pratique, pour inventer le chiffrement asymétrique.

Dès lors, nous pouvons nous poser la question suivante : Comment les concepts fondamentaux de l’arithmétique (la congruence, la divisibilité, les nombres premiers et les équations diophantiennes) ont-ils permis de passer du chiffrement symétrique historique au chiffrement asymétrique RSA indispensable à la sécurité d’Internet ?

Pour y répondre, nous étudierons tout d’abord le chiffrement symétrique à travers le modèle arithmétique du chiffrement affine. Nous détaillerons ensuite le fonctionnement du chiffrement asymétrique RSA reposant sur les propriétés des grands nombres premiers. Enfin, nous aborderons la mise en œuvre de ces protocoles dans la cybersécurité moderne.

---

I. Le chiffrement symétrique et l’arithmétique modulaire : Le chiffrement affine

A. Principes arithmétiques du chiffrement affine

Le chiffrement affine est une méthode de chiffrement symétrique (utilisant la même clé pour coder et décoder) qui repose sur l’arithmétique modulaire. Pour manipuler des concepts mathématiques, on associe d’abord chaque lettre de l’alphabet à un nombre entier compris entre $0$ (A) et $25$ (Z).

Soit :

• $x$ le nombre entier représentant la lettre en clair ($0 \le x \le 25$).
• $y$ le nombre entier représentant la lettre chiffrée ($0 \le y \le 25$).
• La relation de chiffrement est définie par la fonction affine modulaire suivante :

$$y \equiv a \cdot x + b \pmod{26}$$

Où le couple d’entiers $(a\ ; b)$ constitue la clé de chiffrement.

B. La condition d’inversibilité (Théorème de Bézout)

Pour que le message soit déchiffrable de manière unique (sans ambiguïté), la relation de chiffrement doit être une bijection. Il doit être possible d’exprimer $x$ en fonction de $y$ de façon unique. Cela revient à résoudre l’équation :

$$a \cdot x \equiv y - b \pmod{26}$$

D’après les théorèmes d’arithmétique (Bézout et Gauss), cette équation admet une solution unique modulo 26 si et seulement si $a$ est premier avec 26 (c’est-à-dire $\text{PGCD}(a, 26) = 1$). Si cette condition est respectée, il existe un unique entier $a’$ compris entre $1$ et $25$, appelé inverse modulaire de $a$ modulo 26, tel que :

$$a \cdot a’ \equiv 1 \pmod{26}$$

La relation de déchiffrement devient alors :

$$x \equiv a’ \cdot (y - b) \pmod{26}$$

C. Exemple pratique de chiffrement/déchiffrement

Choisissons la clé de chiffrement $(a=9\ ; b=3)$. 9 est bien premier avec 26.

• Chiffrement du mot « BAC » (B=1, A=0, C=2) :

  • Pour B ($x=1$) : $y \equiv 9 \times 1 + 3 = 12 \equiv 12 \pmod{26} \implies$ M
  • Pour A ($x=0$) : $y \equiv 9 \times 0 + 3 = 3 \equiv 3 \pmod{26} \implies$ D
  • Pour C ($x=2$) : $y \equiv 9 \times 2 + 3 = 21 \equiv 21 \pmod{26} \implies$ V Le mot chiffré est « MDV ».

• Déchiffrement : Trouvons l’inverse modulaire de $9$ modulo $26$. On cherche $a’$ tel que $9a’ \equiv 1 \pmod{26}$. Puisque $9 \times 3 = 27 \equiv 1 \pmod{26}$, l’inverse modulaire est $a’ = 3$. La formule de déchiffrement est donc : $$x \equiv 3 \cdot (y - 3) \pmod{26}$$ Déchiffrons le « M » ($y=12$) : $$x \equiv 3 \times (12 - 3) = 3 \times 9 = 27 \equiv 1 \pmod{26}$$ On retrouve bien $x=1$ (la lettre B).

---

II. Le chiffrement asymétrique : Le protocole RSA

A. Le concept de clés publique/privée

Pour éviter le problème de l’échange de la clé secrète, le protocole RSA (inventé en 1977 par Rivest, Shamir et Adleman) utilise deux clés différentes :

• Une clé publique $(N, e)$, diffusée à tout le monde, permettant à n’importe qui de chiffrer un message.
• Une clé privée $d$, gardée secrète par le destinataire, qui est la seule clé capable de déchiffrer le message.

B. Algorithme arithmétique de génération des clés

1. On choisit deux grands nombres premiers distincts $p$ et $q$.
2. On calcule le produit $N = p \cdot q$. Ce nombre $N$ sert de module pour les calculs.
3. On calcule la valeur de l’indicateur d’Euler $\phi(N) = (p-1)(q-1)$.
4. On choisit un entier naturel $e$ premier avec $\phi(N)$ tel que $1 < e < \phi(N)$. Le couple $(N, e)$ constitue la clé publique.
5. On calcule l’unique entier $d$ tel que $e \cdot d \equiv 1 \pmod{\phi(N)}$. Cet entier $d$ est la clé privée. L’existence de $d$ est garantie par le théorème de Bézout puisque $\text{PGCD}(e, \phi(N)) = 1$.

C. Algorithme de chiffrement et déchiffrement

Soit $M$ un message traduit sous forme d’un nombre entier ($0 \le M < N$).

• Chiffrement par l’expéditeur : $$C \equiv M^e \pmod N$$
• Déchiffrement par le destinataire : $$M’ \equiv C^d \pmod N$$

La démonstration que le déchiffrement fonctionne ($M’ = M$) repose sur le petit théorème de Fermat. Comme $e \cdot d \equiv 1 \pmod{\phi(N)}$, il existe un entier $k$ tel que $e \cdot d = 1 + k(p-1)(q-1)$. On a alors :

$$M’ \equiv (M^e)^d \equiv M^{ed} \equiv M^{1 + k(p-1)(q-1)} \pmod N$$

D’après le petit théorème de Fermat, si $M$ n’est pas un multiple du nombre premier $p$ : $$M^{p-1} \equiv 1 \pmod p \implies (M^{p-1})^{k(q-1)} \equiv 1 \pmod p \implies M^{ed} \equiv M \pmod p$$ Par symétrie, on montre également que $M^{ed} \equiv M \pmod q$. Comme $p$ et $q$ sont premiers entre eux, le théorème de Gauss permet d’affirmer que : $$M^{ed} \equiv M \pmod{p \cdot q} \implies M^{ed} \equiv M \pmod N$$ Le destinataire retrouve donc rigoureusement le message d’origine $M$.

---

III. La cybersécurité moderne : L’hybridation des protocoles

A. La complexité algorithmique comme bouclier

La sécurité du RSA repose entièrement sur la difficulté de la factorisation. Un pirate informatique connaît le module public $N$. S’il parvenait à retrouver les facteurs $p$ et $q$, il pourrait calculer $(p-1)(q-1)$, puis retrouver la clé privée $d$.

Cependant, alors que multiplier deux nombres premiers est instantané pour un ordinateur, l’opération inverse (retrouver les facteurs premiers à partir de leur produit $N$) est un problème informatique extrêmement difficile. Avec des nombres premiers $p$ et $q$ d’environ 300 chiffres chacun (clé RSA de 2048 bits), la factorisation de $N$ nécessiterait des milliards d’années de calcul avec les superordinateurs actuels.

B. Le protocole hybride (SSL/TLS - HTTPS)

Malgré sa robustesse, le chiffrement asymétrique RSA présente un inconvénient : il demande d’importants calculs de puissances modulaires, ce qui le rend trop lent pour chiffrer de gros volumes de données en temps réel. Pour sécuriser le web (le protocole HTTPS), on utilise une méthode hybride :

1. Au début de la connexion, le client et le serveur utilisent le chiffrement asymétrique RSA uniquement pour s’échanger une clé secrète temporaire de manière sécurisée.
2. Une fois cette clé partagée, ils basculent sur un protocole symétrique (comme l’AES), beaucoup plus rapide, pour chiffrer l’ensemble de leurs échanges avec cette clé.

---

Conclusion

En définitive, l’arithmétique modulaire, autrefois perçue comme une branche purement théorique des mathématiques, s’est imposée comme le gardien de notre vie numérique. Du chiffrement affine basé sur de simples congruences au protocole asymétrique RSA exploitant les propriétés des grands nombres premiers, c’est la rigueur des démonstrations mathématiques qui garantit l’inviolabilité de nos secrets.

Néanmoins, la recherche ne s’arrête pas. L’avènement futur de l’ordinateur quantique (équipé de l’algorithme de Shor, capable de factoriser les nombres géants très rapidement) pourrait menacer la sécurité du RSA. C’est pourquoi les mathématiciens développent déjà la « cryptographie post-quantique », s’appuyant sur d’autres structures algébriques pour protéger les secrets de demain.

---

Questions potentielles du jury

1. Pourquoi la valeur de $a$ dans la clé du chiffrement affine $y \equiv ax+b \pmod{26}$ ne doit-elle pas être paire ?

Pour que le chiffrement affine fonctionne sans ambiguïté, la valeur de $a$ doit être première avec 26. Les diviseurs de $26$ sont $1$, $2$, $13$ et $26$. Si $a$ est un nombre pair, il admet $2$ comme diviseur. Par conséquent, il partage un diviseur commun avec $26$ ($\text{PGCD}(a, 26) \ge 2$), ce qui signifie qu’il n’est pas premier avec 26. Si $a$ était pair, plusieurs lettres différentes en clair donneraient la même lettre chiffrée (perte de la bijection), rendant le déchiffrement impossible. Par exemple, si $a=2, b=0$ :

• Pour A ($x=0$) : $y \equiv 2 \times 0 \equiv 0 \pmod{26} \implies$ A
• Pour N ($x=13$) : $y \equiv 2 \times 13 = 26 \equiv 0 \pmod{26} \implies$ A Les lettres A et N se chiffreraient toutes les deux en A, ce qui crée une ambiguïté.

2. Comment utilise-t-on l’algorithme d’Euclide pour prouver que deux nombres sont premiers entre eux ?

L’algorithme d’Euclide repose sur une succession de divisions euclidiennes. Pour déterminer le PGCD de deux nombres, on divise le plus grand par le plus petit, puis on recommence en divisant le diviseur par le reste obtenu, jusqu’à obtenir un reste nul. Le PGCD est le dernier reste non nul. Si ce dernier reste non nul est égal à $1$, les deux nombres sont premiers entre eux. Par exemple, pour montrer que $9$ et $26$ sont premiers entre eux :

• $26 = 9 \times 2 + 8$ (le reste est $8$)
• $9 = 8 \times 1 + 1$ (le reste est $1$)
• $8 = 1 \times 8 + 0$ (le reste est $0$) Le dernier reste non nul est $1$, donc $\text{PGCD}(26, 9) = 1$, ce qui prouve qu’ils sont premiers entre eux.

3. Quelle est la différence fondamentale entre la cryptographie symétrique et asymétrique ?

• La cryptographie symétrique utilise une seule et unique clé secrète, partagée entre l’émetteur et le récepteur, servant à la fois à chiffrer et à déchiffrer. Elle est très rapide mais pose le problème de la transmission sécurisée de cette clé.
• La cryptographie asymétrique utilise une paire de clés mathématiquement liées : une clé publique (accessible à tous, servant uniquement à chiffrer) et une clé privée (gardée secrète, servant uniquement à déchiffrer). Elle permet de communiquer de manière sécurisée sans avoir à partager de secret au préalable.

4. Qu’est-ce que le petit théorème de Fermat et comment s’applique-t-il aux nombres premiers ?

Le petit théorème de Fermat énonce que si $p$ est un nombre premier et $a$ un entier naturel non divisible par $p$, alors : $$a^{p-1} \equiv 1 \pmod p$$ Sous une forme plus générale (qui s’applique à tous les entiers $a$, y compris les multiples de $p$), le théorème s’écrit : $$a^p \equiv a \pmod p$$ Dans le système RSA, ce théorème est le fondement de la démonstration qui prouve que l’action de déchiffrement ($C^d \pmod N$) redonne bien le message initial $M$, en démontrant cette congruence successivement modulo $p$ et modulo $q$.

5. Qu’est-ce que l’algorithme d’activation ou de factorisation ? Pourquoi est-ce « difficile » pour un ordinateur ?

Multiplier deux grands nombres premiers $p$ et $q$ pour obtenir $N$ demande un nombre très faible d’opérations élémentaires (de complexité quadratique par rapport au nombre de chiffres). En revanche, retrouver $p$ et $q$ à partir de $N$ (la factorisation) requiert de tester des diviseurs potentiels. Il n’existe aucun algorithme classique capable de factoriser un nombre en temps « polynomial » (c’est-à-dire rapide). Les meilleurs algorithmes classiques actuels (comme le crible généralisé sur les corps de nombres) ont une complexité sous-exponentielle. Pour un nombre de 617 chiffres (RSA-2048), le nombre de calculs nécessaires dépasse les capacités de calcul cumulées de tous les ordinateurs de la Terre sur des milliers d’années.