Sous le capot de l’exponentiation rapide : la mécanique du square-and-multiply

L’exponentiation modulaire

L’exponentiation modulaire est une opération très importante en cryptographie. Elle consiste à calculer de manière « rapide et efficace » la quantité \(x^j\pmod n\), où \(x\), \(j\) et \(n\) sont des nombres entiers. Autrement dit, on cherche à trouver le reste de la division entière de \(x^j\) par \(n\).

Par exemple, \(10^3 \equiv 43\pmod{87}\) car \(1000 = 11\times 87 + 43\).

Cette opération est au cœur de plusieurs systèmes de cryptographie célèbres, comme le cryptosystème à clé publique RSA, ou encore le protocole d’échange de clés de Diffie-Hellman. Dans ces applications, pour garantir la sécurité, les entiers \(x\), \(j\) et \(n\) utilisés sont très grands : ils font généralement au moins 1024 bits (c’est-à-dire plusieurs centaines de chiffres) ref1&2

Les processeurs actuels ne sont pas pourvus d’une unité de calcul permettant de réaliser le calcul direct d’une exponentiation. Ils disposent généralement d’une simple unité de calcul permettant de multiplier ou d’additionner deux entiers. Même si certains langages de programmation disposent d’un opérateur « puissance » (l’opérateur ** en Python par exemple), l’instruction correspondante sera traduite en une série d’instructions utilisant des multiplications. Mais quelle est donc cette série d’instructions ?

Une méthode naïve pour calculer \(x^j \mod n\) consiste à effectuer des multiplications successives : on part de \(x\), puis on calcule \(x^2 = x \times x\), ensuite \(x^3 = x^2 \times x\), et ainsi de suite jusqu’à \(x^j\). Toutefois, lorsque \(j\) est un entier de 1024 bits, cette approche devient rapidement inenvisageable en pratique, car elle est bien trop coûteuse en temps de calcul.

Pour illustrer ce point, considérons une machine équipée d’un processeur cadencé à 4 GHz, c’est-à-dire capable de traiter 4 milliards d’instructions élémentaires par seconde. Une instruction élémentaire correspond généralement à une opération logique sur des données de taille au plus égale à celle d’un registre processeur. Par exemple, sur la plupart des architectures, une opération de type XOR (ou-exclusif) entre deux registres de 64 bits peut être réalisée en un seul cycle d’horloge. En revanche, la multiplication de deux entiers de 64 bits stockés dans des registres nécessite au moins 4 cycles sur les architectures Intel.

Dans notre cas, la complexité s’accroît : à mesure que l’on élève \(x\) à des puissances de plus en plus grandes, la taille des entiers manipulés augmente. Les résultats intermédiaires calculés sont de la forme \(x^i\) mod \(n\), où \(n\) est au moins de l’ordre de \(2^{1024}\), donc il y a peu de chances de pouvoir stocker ceci dans un registre de 64 bits. On dépasse ainsi rapidement les limites des registres classiques, rendant l’utilisation d’un simple opérateur de multiplication impossible. Il faut alors recourir à des algorithmes de multiplication multi-précision, adaptés à des entiers de taille arbitraire (voir à ce sujet l’article « Faire une multiplication plus vite qu’à l’école »).

Par ailleurs, puisqu’on souhaite effectuer un calcul modulo un entier \(n\), il est crucial d’appliquer cette réduction après chaque multiplication afin d’éviter une croissance incontrôlée de la taille des données. En effet, si deux entiers de \(t\) bits sont multipliés, le produit résultant est un entier de \(2t\) bits. Une réduction modulo un entier \(n\) de \(t\) bits permet de revenir à une représentation sur \(t\) bits, ce qui permet de contrôler la taille mémoire occupée par les opérandes.

En résumé, chaque multiplication dans notre contexte est bien plus coûteuse que les quelques cycles d’une multiplication classique sur registres : elle implique des calculs multi-précision suivis d’une réduction modulaire, ce qui alourdit considérablement le coût d’exécution.

Cependant, afin d’illustrer pourquoi le calcul « naïf » de \(x^j\) modulo \(n\) par multiplications successives n’est pas viable, plaçons-nous dans le cas idéal où l’on dispose d’un processeur capable d’exécuter \(4\) milliards \(= 4\times 10^9\) multiplications modulaires à la seconde entre des entiers de taille quelconque. Considérons un entier \(j\) de 1024 bits, on a donc \(j\geqslant 2^{1023}\). Le calcul naïf de \(x^j\) nécessite \(j-1\) multiplications. Le nombre de secondes nécessaires pour effectuer ce calcul est donc supérieur à \(\frac{2^{1023}-1}{4\times 10^9}\). Ce qui, converti en années, nous indique que ce calcul se terminera dans plus de \(7.13\times 10^{290}\) années ! Or les cartes bancaires actuelles effectuent ce même calcul en quelques micro-secondes.

Chaînes d’additions

L’exponentiation rapide également appelée « square-and-multiply » (qu’on peut traduire par « mettre au carré et multiplier ») est un algorithme classique qui réalise le calcul d’une exponentiation modulaire en au plus \(2(\lfloor \log_2 j\rfloor+1)\) multiplications modulaires. Or, dès que \(j\geqslant 8\) , la quantité \(2(\lfloor \log_2 j\rfloor+1)\) devient de plus en plus petite par rapport à \(j\) lorsque \(j\) augmente (pour vous en convaincre, tracez les droites \(y=x\) et \(y=2(\log_2 x+1)\)). Ainsi pour un entier \(j\) de 1024 bits, il suffira d’au plus 2048 multiplications modulaires afin d’obtenir le résultat, ce qui peut être accompli en quelques micro-secondes sur un ordinateur moderne. L’algorithme repose sur la décomposition en base 2 de l’entier \(j\). Prenons l’exemple de \(j=13\). Sa représentation binaire est :

\[ 13 = \mathbf{1} \times 2^3 + \mathbf{1} \times 2^2 + \mathbf{0} \times 2^1 + \mathbf{1} \times 2^0 = 1101_2. \]

Cela nous permet d’écrire :

\[ x^{13} = (x^{2^3})^\mathbf{1} \times (x^{2^2})^\mathbf{1} \times (x^{2^1})^\mathbf{0} \times (x^{2^0})^\mathbf{1}. \]

Plus généralement, si \(j=\sum_{i=0}^t \mathbf{j_i}2^i\) (avec \(\mathbf{j}_i\in\{0,1\}\)), alors

\[x^j=x^{\sum_{i=0}^t \mathbf{j_i}2^i}=\prod_{i=0}^t (x^{2^i})^{\mathbf{j_i}}\,.\]

Le calcul de ce produit peut être réalisé en \(t+1\) étapes où \(t+1\) est le nombre de chiffres (bits) dans la décomposition en base 2 de \(j\). Ainsi pour l’entier \(j=13\), le calcul de \(x^{13}\) peut se faire en 4 étapes.

Pour déterminer les coefficients \(j_i\) de la décomposition binaire de \(j\), il suffit de procéder à des divisions entières successives de \(j\) par 2. On vérifie si l’entier \(j\) courant est impair, auquel cas \(j_i\) vaut 1. Dans le cas où \(j\) est pair, alors \(j_i\) vaut 0. Par exemple pour \(j=13\), \(j\) est impair, donc \(j_0=1\). La division entière de \(j\) par 2 donne 6 qui est pair donc \(j_1=0\). L’entier 6 divisé par 2 donne 3, donc \(j_2=1\). L’entier 3 divisé par 2 donne 1, donc \(j_3=1\). Finalement l’entier 1 divisé par 2 donne 0 ce qui marque la fin de la décomposition.

Pour calculer le produit des termes permettant d’obtenir \(x^j\) en \(t+1\) étapes, on procède alors de la façon suivante. Supposons qu’à l’étape \(i\) on dispose de la valeur du produit des \(i\) premiers termes du produit final, que nous appellerons produit courant. À l’étape \(i+1\), on multiplie le produit courant par \(x^{2^i}\) uniquement si le coefficient binaire \(j_i\) est égal à 1 (étape « multiply »). Le processus démarre en initialisant à 1 la variable contenant le produit courant.

Ainsi pour le calcul de \(x^{13}\), le produit courant vaut 1 (étape d’initialisation). À l’étape \(1\), étant donné que \(j_0=1\), on met à jour le produit courant en le multipliant par \(x\). À l’étape 2, étant donné que \(j_1=0\), aucune mise à jour n’est effectuée. À l’étape 3, \(j_2=1\), le produit courant est donc multiplié par \(x^4\) et vaut à présent \(x^5\). À l’étape 4, \(j_3=1\), le produit courant est multiplié par \(x^8\). On obtient ainsi \(x^{13}\) qui est le résultat final.

Afin de réaliser ces calculs, il est donc nécessaire de disposer, à chaque étape \(i\), de la valeur de \(x^{2^{i-1}}\). C’est le cas à l’étape 1 puisque l’on connaît la valeur \(x\). À l’étape 2, il suffit donc de calculer \(x\times x\) afin d’obtenir \(x^2\). À l’étape 2, on calcule \(x^2\times x^2\) afin d’obtenir \(x^4\), et ainsi de suite. Plus généralement, si on dispose de la valeur \({x^{2^{i-i}}}\) à l’étape \(i\), à l’étape \(i+1\) on obtient \(x^{2^i}\) en calculant \({x^{2^{i-1}}}\times {x^{2^{i-1}}} = (x^{2^{i-1}})^2\) (étape « square »). En réunissant toutes ces observations, on obtient l’algorithme suivant :

Algorithme 1 square and multiply

Require: \(j \geq 0\) et \(x \neq 0\)
Ensure: \(y = x^j\bmod n\)
1: \(y\leftarrow 1\)
2: while \(j \neq 0\) do
3:       if \(j\) est impair then
4:             \(y \leftarrow y \times x\bmod n\)       (multiply)
5:       end if
6:       \(x \leftarrow x \times x\bmod n\)       (square)
7:       \(j \leftarrow \lfloor j/2\rfloor\)
8: end while
9: return y

Appliquons cet algorithme au calcul de \(x^{15}\) modulo un certain entier \(n\). Les valeurs suivantes seront successivement calculées lors de la mise à jour de \(y\) (en gras) et de \(x\): \(\mathbf x\), \(x^2\), \(\mathbf x^3\), \(x^4\), \(\mathbf x^7\), \(x^{8}\), \(\mathbf x^{15}\), \(x^{16}\). Le résultat est donc obtenu en 8 multiplications.

Cette séquence de calcul fait apparaître la suite \(1\), \(2\), \(3\), \(4\), \(7\), \(8\), \(15\) que l’on appelle chaîne d’additions. Elle possède une propriété remarquable : à partir du deuxième terme, chaque terme peut être obtenu à partir de la somme de 2 termes précédents (éventuellement deux fois le même terme). En effet, posons \(u_0=1\), on a successivement :

\[u_1 = 2 = u_0+u_0,\ u_2 = 3 = u_1+u_0,\ u_3 = 4 = u_1+u_1,\ u_4 = 7 = u_3+u_2,\]

\[u_5 = 8 = u_3+u_3,\ u_6 = 15 = u_5+u_4\,.\]

Ceci nous amène à la définition suivante :

Définition 1. Une chaîne d’additions calculant un entier \(k\) est une séquence croissante \(u_0, u_2, \dots , u_{s}\) d’entiers positifs telle que :

1. \(u_0=1\), \(u_s=k\),
2. pour tout \(i\) compris entre \(1\) et \(s\), \(u_i = u_j+u_t\) avec \(0\leqslant j,t < i\).

On appelle taille de la chaîne la valeur de l’entier \(s\).

La séquence \(1\), \(2\), \(3\), \(6\), \(9\), \(15\) est une autre chaîne d’additions qui permet aussi de calculer \(x^{15}\) en seulement 5 multiplications \(x\rightarrow x^2 \rightarrow x.x^2\rightarrow x^6\rightarrow x^3.x^6\rightarrow x^9.x^6\). Ce nombre de multiplications correspond exactement à la taille de la chaîne.

Le calcul « efficace » de \(x^j\) est donc relié au problème de la recherche de la plus petite chaîne d’additions permettant d’obtenir l’entier \(j\). En toute rigueur, ceci n’est pas entièrement exact. En effet, selon l’architecture sur laquelle le calcul sera réalisé, une élévation au carré peut être moins coûteuse qu’une multiplication. Prenons l’exemple d’une architecture dotée d’une unité de calcul conçue pour multiplier uniquement des entiers de 0 à 9. Imaginons que nous souhaitons étendre cette architecture pour effectuer des multiplications entre des entiers de 10 à 99, en utilisant l’unité de calcul existante. Soient \(a=10a_1+a_0\) et \(b=10b_1+b_0\) deux entiers dans l’intervalle \([10,99]\), où \(a_0\), \(a_1\), \(b_0\), \(b_1\) appartiennent à \([0,9]\). La multiplication de \(a\) par \(b\) peut être réalisée en calculant les produits \(a_0b_0\), \(a_0b_1\), \(a_1b_0\) et \(a_1b_1\) via l’unité de calcul existante. Il est intéressant de noter que le calcul de \(a^2\) nécessite uniquement les produits \(a_0a_0\), \(a_0a_1\) et \(a_1a_1\), représentant ainsi un produit de moins que pour la multiplication générale. Face à cette observation, nous avons deux options pour faire évoluer notre architecture :

• Implémenter une unité de calcul qui réalise n’importe quel produit \(ab\), indépendamment des valeurs de \(a\) et \(b\), au coût de quatre multiplications élémentaires.
• Ajouter deux nouvelles unités de calcul, l’une dédiée à la multiplication de deux entiers distincts et l’autre au calcul du carré d’un entier, qui nécessiterait une multiplication élémentaire de moins.

Ces améliorations permettent de choisir entre une généralisation complète à un coût légèrement supérieur ou une spécialisation qui optimise les ressources pour des opérations spécifiques.

On pourra donc ainsi, dans certains cas, préférer utiliser une chaîne un peu plus longue si celle-ci permet d’effectuer de nombreuses élévations au carré.

Le terme chaîne d’additions semble avoir été introduit en 1937 dans un article de Scholz ref4. Cependant, cette notion de suite d’entiers, permettant de décrire comment réaliser le calcul d’une exponentiation, apparaît dès 1894 dans le tome 1 de « L’intermédiaire des Mathématiciens », page 163, sous la dénomination de série ou échelle génératrice. Une étude détaillée sur ce sujet peut être trouvée dans ref2. Il est important de noter qu’il n’existe aucun algorithme efficace capable de calculer une chaîne d’additions de taille minimale pour un entier \(n\), ni même de déterminer cette taille. (L’algorithme consistant à énumérer toutes les chaînes de longueur 1 pour savoir si elles conviennent, puis toutes les chaînes de longueur 2 si ce n’est pas le cas, puis toutes les chaînes de longueur 3 etc. fonctionne mais est loin d’être efficace.) Toutefois, plusieurs méthodes permettent de construire des « chaînes courtes » qui se rapprochent de la solution optimale.

Lors de l’utilisation d’une chaîne d’additions pour calculer \(x^j\), il est parfois nécessaire de stocker plusieurs valeurs intermédiaires. Prenons par exemple le calcul de \(x^{20}\) à partir de la chaîne \(1\), \(2\), \(4\), \(5\), \(7\), \(9\), \(13\), \(20\). Lors de l’étape du calcul de \(x^{9}\), il est nécessaire de disposer non seulement de la valeur courante (\(x^9\)), mais aussi de variables auxiliaires contenant les résultats intermédiaires \(x^4\) et \(x^7\), ces derniers étant indispensables pour les étapes de calcul suivantes (\(x^{13}\) et \(x^{20}\)).

La chaîne d’additions générée par l’algorithme square and multiply présente l’avantage de n’exiger que deux variables pour réaliser les différentes étapes du calcul. Ceci est important dans des contextes tels que l’Internet des Objets (IoT), où les dispositifs connectés disposent souvent de capacités de mémoire réduites. Cette économie de ressources permet d’implémenter des opérations cryptographiques complexes, même sur des appareils avec des contraintes matérielles strictes. Cependant, cet algorithme a un inconvénient majeur dans le domaine de la cryptographie : il est irrégulier. En fonction de la valeur courante de \(j\), l’algorithme effectue soit une simple élévation au carré, soit une multiplication suivie d’une élévation au carré. Si l’on observe la consommation d’énergie du processeur pendant l’exécution de cet algorithme, cette irrégularité révèle si une ou deux opérations ont été effectuées. Dans le cadre de l’algorithme RSA, lors du déchiffrement d’un message, la valeur \(j\) correspond à la clé de déchiffrement. Ainsi, les variations de la consommation d’énergie pendant le déchiffrement peuvent permettre à un attaquant de retrouver la valeur complète de \(j\) (indication : utilisez la décomposition en base 2 de \(j\)). Ainsi dans le cadre de la cryptographie, la recherche d’une chaîne d’addition courte pour optimiser le temps de calcul n’est pas le seul critère à prendre en compte, encore faut-il que l’algorithme de calcul associé soit régulier.