Problèmes mathématiques difficiles

Portail > Fondamentaux

La sécurité de la cryptographie asymétrique ne repose pas sur le secret de l'algorithme, mais sur des problèmes mathématiques faciles à calculer dans un sens et infaisables dans l'autre (fonctions à sens unique avec trappe). Trois familles fondent les algorithmes courants.

Le principe de la trappe

Une fonction à sens unique avec trappe est facile à évaluer, difficile à inverser — sauf si l'on connaît une information secrète (la « trappe », c'est-à-dire la clé privée). La clé publique permet le sens facile ; seule la clé privée donne accès au sens inverse.

1. Factorisation des entiers

Multiplier deux grands nombres premiers est facile ; retrouver ces facteurs à partir du produit est infaisable pour des tailles suffisantes. C'est le fondement de RSA.

2. Logarithme discret

Dans un groupe modulaire, calculer y = gx mod p est facile ; retrouver x à partir de y, g, p (le « logarithme discret ») est infaisable. C'est le fondement de Diffie-Hellman, ElGamal et DSA.

3. Logarithme discret sur courbes elliptiques (ECDLP)

Le même problème de log discret, transposé au groupe des points d'une courbe elliptique, est encore plus difficile à taille de clé égale. Conséquence : des clés bien plus courtes pour une sécurité équivalente. C'est le fondement d'ECDH, ECDSA et EdDSA.

Correspondance problème ↔ algorithmes

Problème difficile	Algorithmes
Factorisation	RSA
Logarithme discret (modulaire)	Diffie-Hellman, ElGamal, DSA
Log discret sur courbes elliptiques (ECDLP)	ECDH, ECDSA, EdDSA

Pourquoi l'ECC permet des clés plus courtes

Les meilleures attaques connues contre la factorisation et le log discret modulaire sont sous-exponentielles (algorithmes de crible), ce qui oblige à de grandes clés. Contre l'ECDLP, les meilleures attaques restent exponentielles, d'où une sécurité équivalente avec des clés bien plus petites (Tailles de clés et équivalences de sécurité).

La faille quantique

Ces trois problèmes sont difficiles pour un ordinateur classique, mais l'algorithme de Shor les résout efficacement sur un ordinateur quantique : factorisation et logarithme discret (modulaire et elliptique) tomberaient ensemble. C'est pourquoi RSA, DH et ECC sont tous menacés, et que la transition se fait vers d'autres problèmes (Cryptographie asymétrique et post-quantique).

Points clés à retenir

• L'asymétrique repose sur des problèmes faciles dans un sens, infaisables dans l'autre (trappe = clé privée).
• Trois familles : factorisation (RSA), log discret (DH/ElGamal/DSA), ECDLP (ECDH/ECDSA/EdDSA).
• L'ECDLP étant plus dur, l'ECC offre la même sécurité avec des clés plus courtes.
• Shor casse les trois → enjeu post-quantique.

Voir aussi

• RSA
• Diffie-Hellman et ECDH
• Tailles de clés et équivalences de sécurité
• Cryptographie asymétrique et post-quantique