La multiplication scalaire et le problème du log discret

L'addition de points, seule, ne fait pas une cryptographie. Ce qui la rend utile, c'est de la répéter — et de constater qu'elle crée une fonction à sens unique, facile à calculer mais quasi impossible à inverser.

Multiplier un point par un entier

Additionner un point P à lui-même plusieurs fois définit la multiplication scalaire. Pour un entier k :

k·P = P + P + P + ... + P     (k fois)

Ainsi 2·P = P + P, 3·P = P + P + P, etc. Le résultat k·P est encore un point de la courbe. L'entier k est un scalaire ; il ne vit pas sur la courbe, c'est un simple nombre.

Le calcul est efficace

À première vue, calculer k·P semble demander k additions — catastrophique si k a 77 chiffres. Mais on procède par doublements successifs, exactement comme l'exponentiation rapide.

Pour calculer 2·P, 4·P, 8·P, ..., il suffit de doubler à chaque étape. On combine ensuite ces puissances de 2 selon l'écriture binaire de k. Exemple pour k = 13 = 8 + 4 + 1 :

On double :   P → 2P → 4P → 8P        (3 doublements)
On additionne : 13·P = 8·P + 4·P + P  (2 additions)

Au lieu de 12 additions, on en fait 5. Pour un k de 256 bits, on passe de 2^256 opérations (impossible) à environ 380 (instantané). Le sens k → k·P est donc parfaitement praticable.

Le sens inverse est infaisable

Voici le point crucial. Un attaquant connaît le point de départ P (public) et le point d'arrivée Q = k·P (public). Peut-il retrouver le scalaire k ? C'est le problème du logarithme discret sur courbe elliptique (en anglais ECDLP, Elliptic Curve Discrete Logarithm Problem). Et personne ne sait le résoudre efficacement.

Il n'existe aucune « division » géométrique qui donnerait k directement. Les meilleures attaques connues doivent parcourir l'espace des possibilités : pour une bonne courbe de 256 bits, de l'ordre de 2^128 opérations — hors de portée de toute machine.

   FACILE (une fraction de milliseconde)
   k, P  ───────────────────────────►  Q = k·P

   INFAISABLE (des milliards de milliards d'années)
   P, Q  ─────────────────X◄───────────  k = ?
              ECDLP : aucun algorithme rapide connu

Une asymétrie familière

On retrouve exactement la logique de RSA : une fonction à sens unique, aisée dans un sens, verrouillée dans l'autre. RSA s'appuie sur la difficulté de factoriser ; les courbes elliptiques s'appuient sur celle de l'ECDLP.

La grande différence est l'efficacité : aucune attaque connue sur l'ECDLP n'est aussi « rapide » que les algorithmes de factorisation modernes utilisés contre RSA. C'est pour cela qu'une clé elliptique peut être bien plus courte à sécurité égale — l'objet du chapitre suivant.

Comme pour RSA, cette difficulté n'est pas démontrée : on constate seulement que personne n'y arrive sur des courbes bien choisies. La sécurité est calculatoire, pas absolue. Le choix des paramètres n'est donc jamais laissé au hasard, il est fixé par des standards éprouvés.

En résumé

• La multiplication scalaire k·P additionne P à lui-même k fois.
• Elle se calcule vite par doublements successifs (comme l'exponentiation rapide).
• Retrouver k à partir de P et k·P est le problème du logarithme discret sur courbe elliptique (ECDLP), réputé infaisable.
• C'est une fonction à sens unique, analogue à la factorisation de RSA, mais plus résistante — d'où des clés plus petites.