francebalade.fr Cours de Mathématiques Table des matières Votre avis sur ce site

Algèbre moderne & application à la Cryptographie

Synthèse pédagogique : Des structures abstraites aux protocoles modernes (AES, ECDH)

En algèbre générale, les groupes, anneaux et corps sont des structures fondamentales définies par un ensemble muni d'une ou deux lois de composition interne respectant des axiomes précis. Chacune enrichit la précédente en ajoutant des opérations et des règles de calcul.

1. Hiérarchie des structures algébriques

L'algèbre moderne classe les ensembles en fonction des opérations internes dont ils sont munis et des propriétés qui les régissent.

Groupe $(G, *)$

1 loi interne.
Associativité : $(a*b)*c = a*(b*c)$.
Élément neutre $e$ : $a*e = e*a = a$.
Symétrique $a'$ : $a*a' = a'*a = e$.
Exemple : $(\mathbb{Z}, +)$, ou l'ensemble des points d'une courbe elliptique.

Anneau $(A, +, \times)$

2 lois internes.
$(A, +)$ est un groupe abélien (neutre $0$).
$\times$ est associative et unitaire (neutre $1$).
$\times$ est distributive par rapport à $+$.
Multiplication non nécessairement inversible.
Exemple : $(\mathbb{Z}, +, \times)$, $\mathbb{Z}/n\mathbb{Z}$ (base de RSA).

Corps $(\mathbb{K}, +, \times)$

2 lois internes.
$(A, +, \times)$ est un anneau unitaire commutatif.
Tout élément non nul est inversible : $(\mathbb{K}^*, \times)$ forme un groupe.
Permet les 4 opérations élémentaires ($+, -, \times, /$).
Exemple : $\mathbb{R}$, $\mathbb{C}$, et les corps finis $\mathbb{F}_p$, $\mathbb{F}_{2^8}$.

Leur utilisation concrète :

Groupes (l'étude des symétries) :
- Physique théorique et mécanique quantique : les groupes de Lie décrivent les invariances spatio-temporelles et de jauge (modèle standard des particules, spin).
- Chimie moléculaire et cristallographie : classification des molécules et réseaux par leurs groupes d'isométries.
- Théorie de Galois : résolution des équations polynomiales via les permutations de leurs racines.

Anneaux (l'arithmétique et la divisibilité) :
- Cryptographie asymétrique : l'anneau $\mathbb{Z}/n\mathbb{Z}$ est le cœur de l'algorithme RSA (repose sur la difficulté de factorisation dans cet anneau).
- Géométrie algébrique : les anneaux de coordonnées et idéaux traduisent les ensembles de zéros de polynômes en objets algébriques.

Corps (l'analyse, le calcul matriciel et le codage) :
- Algèbre linéaire : tout espace vectoriel repose sur un corps de base (résolution de systèmes linéaires, calcul spectral, traitement d'images).
- Théorie de l'information : les corps finis (corps de Galois) construisent les codes correcteurs d'erreurs (Reed-Solomon pour les QR codes, transmissions satellites, disques optiques).

2. Application des Corps finis d'extension : La S-box de l'AES

L'application des corps finis en cryptographie moderne est le corps de Galois $\mathbb{F}_{2^8}$ (ou $\mathrm{GF}(2^8)$), employé au cœur de l'AES (Advanced Encryption Standard).
Il permet de construire la boîte de substitution (S-box), le composant non linéaire qui protège l'algorithme contre la cryptanalyse différentielle et linéaire.

L'algorithme de chiffrement symétrique standard AES utilise le corps fini $\mathbb{F}_{2^8} \cong \mathbb{F}_2[X] / \langle M(X) \rangle$ pour bâtir sa boîte de substitution non-linéaire (S-box).

Construction algébrique de $\mathbb{F}_{2^8}$Le corps $\mathbb{F}_2 = \mathbb{Z}/2\mathbb{Z} = \{0, 1\}$ dispose des opérations d'addition et multiplication modulo $2$.

Pour construire une extension de degré $8$ contenant $2^8 = 256$ éléments, on procède par quotient d'un anneau de polynômes :

1. Représentation des éléments : chaque octet $(b_7 b_6 \dots b_0)_2$ est identifié à un polynôme de degré inférieur ou égal à $7$ à coefficients dans $\mathbb{F}_2$ :
$$P(X) = b_7 X^7 + b_6 X^6 + \dots + b_1 X + b_0$$

2. Polynôme irréductible : on choisit un polynôme de degré $8$ irréductible sur $\mathbb{F}_2$. L'AES utilise le polynôme de Rijndael :
$$M(X) = X^8 + X^4 + X^3 + X + 1 \quad (\text{noté } \texttt{0x11B} \text{ en hexadécimal})$$

3. Structure de corps : le corps est le quotient $\mathbb{F}_{2^8} \cong \mathbb{F}_2[X] / \langle M(X) \rangle$. Comme $M(X)$ est irréductible, tout élément non nul est premier avec $M(X)$ et admet un inverse unique.

Polynôme irréductible de Rijndael :
$$M(X) = X^8 + X^4 + X^3 + X + 1 \quad (\texttt{0x11B})$$

Fonctionnement des opérations

Addition : Addition des coefficients modulo 2. Équivaut rigoureusement à un XOR binaire bit à bit, sans propagation de retenue.
Multiplication : Multiplication de polynômes classiques suivie d'une réduction par division euclidienne modulo $M(X)$.
Inversion et S-box : Chaque octet est d'abord remplacé par son inverse multiplicatif $x^{-1} \in \mathbb{F}_{2^8}$ (avec $0^{-1}=0$), puis soumis à une transformation affine binaire. Cette opération garantit une non-linéarité maximale contre la cryptanalyse différentielle et linéaire.

Usage direct dans la S-box de l'AES

La boîte de substitution applique à chaque octet $x$ une transformation en deux étapes :
Inversion multiplicative dans $\mathbb{F}_{2^8}$ :L'octet $x$ est remplacé par son inverse $x^{-1}$ dans $\mathbb{F}_{2^8}$ (avec la convention $0^{-1} = 0$). L'inverse se calcule via l'algorithme d'Euclide étendu ou par le petit théorème de Fermat ($x^{-1} = x^{254}$, car le groupe multiplicatif $\mathbb{F}_{2^8}^*$ est d'ordre $255$).
Transformation affine sur $\mathbb{F}_2$ :
L'inverse obtenu est multiplié par une matrice binaire $8 \times 8$ circulante, puis additionné (XOR) au vecteur constant $\texttt{0x63}$.

Pourquoi ce choix mathématique ?

Non-linéarité maximale : l'inversion $x \mapsto x^{-1}$ dans un corps fini possède une complexité algébrique très élevée par rapport aux opérations bit à bit usuelles. Elle élimine toute relation linéaire exploitable entre l'entrée et la sortie.
Résistance aux attaques : elle minimise la probabilité de propagation différentielle et la corrélation linéaire.
Rupture des symétries : la transformation affine finale évite les attaques par interpolation algébrique pure qui exploiteraient la simplicité formelle de l'inverse dans $\mathbb{F}_{2^8}$.

3. Corps premiers et courbes elliptiques (ECC)

En cryptographie asymétrique sur courbes elliptiques, le corps de base est un corps premier $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ où $p$ est un nombre premier de grande taille.

En cryptographie sur courbes elliptiques (ECC), le corps fini premier $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ (où $p$ est un très grand nombre premier) sert de socle arithmétique : toutes les coordonnées des points et les opérations algébriques y sont calculées modulo $p$.
Ce cadre transforme une courbe géométrique continue en un ensemble fini et discret de points utilisable par un ordinateur sans aucune approximation numérique.

De la géométrie continue à l'arithmétique modulaire
Sur un corps premier $\mathbb{F}_p$ avec $p > 3$, une courbe elliptique sous forme de Weierstrass s'écrit :$$y^2 \equiv x^3 + ax + b \pmod p$$avec la condition de non-singularité $4a^3 + 27b^2 \not\equiv 0 \pmod p$ (ce qui garantit que la courbe n'a pas de point double ni de rebroussement).

L'ensemble des points de la courbe, noté $E(\mathbb{F}_p)$, comprend :
- Tous les couples d'entiers $(x, y) \in \{0, \dots, p-1\}^2$ satisfaisant la congruence.
- Un point abstrait supplémentaire appelé point à l'infini (noté $\mathcal{O}$), qui joue le rôle d'élément neutre.

La loi de groupe et le rôle du corps $\mathbb{F}_p$
Sur les nombres réels, additionner deux points $P$ et $Q$ consiste à tracer la sécante passant par $P$ et $Q$, à trouver le troisième point d'intersection avec la courbe, puis à prendre son symétrique par rapport à l'axe horizontal.

Addition de points sur une courbe elliptique. Source : Wikipédia

Dans le corps premier $\mathbb{F}_p$, cette géométrie se traduit par des formules algébriques exactes pour calculer $R(x_R, y_R) = P(x_P, y_P) + Q(x_Q, y_Q)$ :

Calcul de la pente $\lambda$ :

Si $P \neq Q$ : $\lambda \equiv (y_Q - y_P) \times (x_Q - x_P)^{-1} \pmod p$
Si $P = Q$ (doublement) : $\lambda \equiv (3x_P^2 + a) \times (2y_P)^{-1} \pmod p$

Calcul des coordonnées de $R$ :

$x_R \equiv \lambda^2 - x_P - x_Q \pmod p$
$y_R \equiv \lambda(x_P - x_R) - y_P \pmod p$

Le rôle clé du corps : Le calcul de $\lambda$ exige une division. Dans $\mathbb{F}_p$, diviser revient à multiplier par l'inverse modulaire, obtenu efficacement grâce à l'algorithme d'Euclide étendu ou via le petit théorème de Fermat ($z^{-1} \equiv z^{p-2} \pmod p$). La structure de corps garantit que tout dénominateur non nul possède un inverse unique.

Le problème du logarithme discret (ECDLP)
Sur les nombres réels, additionner deux points $P$ et $Q$ consiste à tracer la sécante passant par $P$ et $Q$, à trouver le troisième point d'intersection avec la courbe, puis à prendre son symétrique par rapport à l'axe horizontal.
L'intérêt cryptographique repose sur l'asymétrie de la multiplication scalaire :$$Q = k \cdot P = \underbrace{P + P + \dots + P}_{k \text{ fois}}$$

Sens direct (facile) : Calculer $Q$ à partir de $k$ et $P$ se fait en $O(\log k)$ additions de points via l'algorithme d'exponentiation rapide (double-and-add).
Sens inverse (intraitable) : Retrouver l'entier scalaire $k$ connaissant $P$ et $Q$ est le problème du logarithme discret sur les courbes elliptiques (ECDLP).

Sur un sous-groupe cyclique bien choisi d'ordre premier $n$, il n'existe pas d'algorithme sous-exponentiel équivalent au crible algébrique utilisé contre RSA ou Diffie-Hellman classique. Les meilleures attaques génériques (comme l'algorithme $\rho$ de Pollard) sont en temps exponentiel $O(\sqrt{n})$.

Avantages pratiques et standards actuels

Taille de clé réduite : Une clé privée de $256$ bits sur $\mathbb{F}_p$ offre un niveau de sécurité équivalent à une clé RSA de $3072$ bits, réduisant drastiquement la bande passante et la charge de calcul.
Normes répandues :
- secp256k1 : Utilisée par Bitcoin et Ethereum, avec $p = 2^{256} - 2^{32} - 977$ et l'équation $y^2 \equiv x^3 + 7 \pmod p$.
- NIST P-256 (secp256r1) : Standard des connexions TLS/HTTPS et des passkeys.
- Curve25519 : Courbe de Montgomery définie sur le corps premier pseudo-Mersenne $\mathbb{F}_{2^{255}-19}$, omniprésente dans SSH, Signal et WireGuard.

Équation de Weierstrass sur $\mathbb{F}_p$

L'équation de Weierstrass sert principalement à définir et manipuler de façon standardisée les courbes elliptiques en géométrie algébrique, en théorie des nombres et en informatique.
Un de ses principaux usages est la cryptographie sur les courbes elliptiques (ECC)
Signatures et chiffrement : Les points $(x, y)$ vérifiant cette équation (définis sur un corps fini $\mathbb{F}_p$ ou $\mathbb{F}_{2^m}$), complétés par un point à l'infini, forment un groupe abélien.

Sécurité renforcée : La difficulté à inverser l'addition répétée de points (problème du logarithme discret sur les courbes elliptiques) permet de concevoir des protocoles cryptographiques (ECDSA, Ed25519) offrant le même niveau de sécurité que RSA, mais avec des clés beaucoup plus courtes (256 bits au lieu de 3 072 bits).
C'est le fondement de la sécurité du protocole HTTPS (TLS), des cartes à puce et de la plupart des blockchains.

L'ensemble des points d'une courbe elliptique non singulière est constitué des solutions $(x, y) \in \mathbb{F}_p^2$ vérifiant :

$$y^2 \equiv x^3 + ax + b \pmod p \quad \text{avec } 4a^3 + 27b^2 \not\equiv 0 \pmod p$$

auquel s'ajoute un point à l'infini $\mathcal{O}$, formant un groupe abélien fini sous la loi d'addition sécante-tangente.

Formules d'addition de deux points $P(x_1, y_1)$ et $Q(x_2, y_2)$ :
Pente : $\lambda = \begin{cases} \frac{y_2 - y_1}{x_2 - x_1} \pmod p & \text{si } P \neq Q \\ \frac{3x_1^2 + a}{2y_1} \pmod p & \text{si } P = Q \end{cases}$

Coordonnées du résultat $R = P + Q$ :
$$x_3 = \lambda^2 - x_1 - x_2 \pmod p$$ $$y_3 = \lambda(x_1 - x_3) - y_1 \pmod p$$ Note : Toute division par $D$ est calculée par multiplication par l'inverse modulaire $D^{-1} \pmod p$.

4. Démonstration numérique : Échange Diffie-Hellman (ECDH)

Ce module illustre le calcul pas à pas de l'échange de clés sur la courbe didactique :
$$y^2 \equiv x^3 + 2x + 2 \pmod{17} \quad \text{avec le point générateur } G = (5, 1)$$

Le protocole ECDH (Elliptic Curve Diffie-Hellman) permet à deux interlocuteurs d'établir un secret partagé sur un canal public non sécurisé, sans jamais transmettre ce secret ni leurs clés privées. Son principe repose sur la commutativité de la multiplication scalaire :$$S = d_A \cdot Q_B = d_A \cdot (d_B \cdot G) = d_B \cdot (d_A \cdot G) = d_B \cdot Q_A$$

Le principe général

Paramètres publics : Alice et Bob s'accordent sur un corps $\mathbb{F}_p$, une courbe elliptique $E$ et un point générateur $G$.
Génération des clés :
- Alice choisit un entier secret $d_A$ et publie sa clé publique $Q_A = d_A \cdot G$.
- Bob choisit un entier secret $d_B$ et publie sa clé publique $Q_B = d_B \cdot G$.
- Le point obtenu $S(x_S, y_S)$ est rigoureusement identique. L'abscisse $x_S$ sert ensuite de graine à une fonction de dérivation de clé (KDF) pour chiffrer les échanges en AES.

Exemple numérique pas à pas

Corps fini : $\mathbb{F}_{17}$ ($p = 17$).
Courbe elliptique : $y^2 \equiv x^3 + 2x + 2 \pmod{17}$.
Point de base : $G = (5, 1)$ (vérification : $1^2 \equiv 5^3 + 2(5) + 2 \equiv 137 \equiv 1 \pmod{17}$).

1. Calcul de la clé publique d'Alice ($d_A = 2$)

Pente $\lambda$ de la tangente en $G(5, 1)$ :$$\lambda \equiv \frac{3x^2 + a}{2y} \equiv \frac{3(5^2) + 2}{2(1)} \equiv \frac{77}{2} \pmod{17}$$Or $77 \equiv 9 \pmod{17}$, et l'inverse de $2$ modulo $17$ est $9$ (car $2 \times 9 = 18 \equiv 1$).D'où $\lambda \equiv 9 \times 9 = 81 \equiv 13 \pmod{17}$.
Coordonnées de $Q_A$ :$$x_A \equiv \lambda^2 - 2x \equiv 13^2 - 2(5) \equiv 169 - 10 = 159 \equiv 6 \pmod{17}$$$$y_A \equiv \lambda(x - x_A) - y \equiv 13(5 - 6) - 1 \equiv -14 \equiv 3 \pmod{17}$$
Alice publie $Q_A = (6, 3)$ et garde $d_A = 2$ secret.

2. Calcul de la clé publique de Bob ($d_B = 3$)

Pente $\lambda$ de la droite reliant les deux points :$$\lambda \equiv \frac{y_2 - y_1}{x_2 - x_1} \equiv \frac{1 - 3}{5 - 6} \equiv \frac{-2}{-1} \equiv 2 \pmod{17}$$
Coordonnées de $Q_B$ :$$x_B \equiv \lambda^2 - x_1 - x_2 \equiv 2^2 - 6 - 5 = -7 \equiv 10 \pmod{17}$$$$y_B \equiv \lambda(x_1 - x_B) - y_1 \equiv 2(6 - 10) - 3 = -11 \equiv 6 \pmod{17}$$
Bob publie $Q_B = (10, 6)$ et garde $d_B = 3$ secret.

3. Échange et dérivation du secret $S$

Du côté d'Alice : elle reçoit $Q_B = (10, 6)$ et calcule $S = 2 \cdot Q_B$ (doublement de $(10, 6)$) :$$\lambda \equiv \frac{3(10^2) + 2}{2(6)} \equiv \frac{302}{12} \equiv \frac{13}{12} \pmod{17}$$
L'inverse de $12$ modulo $17$ est $10$ (car $12 \times 10 = 120 = 7 \times 17 + 1$).$\lambda \equiv 13 \times 10 = 130 \equiv 11 \pmod{17}$.$$x_S \equiv 11^2 - 2(10) = 121 - 20 = 101 \equiv 16 \pmod{17}$$
$$y_S \equiv 11(10 - 16) - 6 = -72 \equiv 13 \pmod{17}$$
Alice trouve le point secret $S = (16, 13)$.
Du côté de Bob : il reçoit $Q_A = (6, 3)$ et calcule $S = 3 \cdot Q_A = 2 \cdot (6, 3) + (6, 3)$ :
Le calcul mène exactement au même point $S = (16, 13)$.

Un espion ayant intercepté $G = (5, 1)$, $Q_A = (6, 3)$ et $Q_B = (10, 6)$ ne peut pas calculer $S$ sans résoudre le problème du logarithme discret (ECDLP), infaisable lorsque $p$ compte $256$ bits.

Clé privée Alice ($d_A$) : Clé privée Bob ($d_B$) :

Cliquez sur « Calculer l'échange » pour voir les étapes.