La cryptographie et les ordinateurs quantiques

Depuis quelques années on entend de plus en plus parler d’ordinateurs quantiques. L’une des raisons phares de cet intérêt grandissant consiste en les possibilités offertes par ces ordinateurs pour la cryptographie et les effets qu’ils sont susceptibles d’avoir sur la technologie cryptographique actuelle. Le but de ce texte est d’explorer ce second aspect et de montrer, sans rentrer dans les détails du calcul quantique, en quoi les solutions cryptographiques actuelles seraient menacées par l’avènement d’ordinateurs quantiques.

Ce texte est divisé en trois parties dont chacune pourrait intéresser plus ou moins le lecteur selon ses connaissances antérieures et ce qu’il aimerait savoir. Ainsi, la suite de cette introduction vise à expliciter le contenu et le but de chaque partie afin de permettre au lecteur de construire le plan de lecture qui lui convient.

La première partie donne un aperçu de l’état actuel de la cryptographie. Nous y introduisons les deux formes principales de cryptographie : la cryptographie à clé secrète et la cryptographie à clé publique. La cryptographie à clé secrète existe depuis au moins l’Antiquité romaine, mais la cryptographie à clé publique est une invention plus récente qui date des années 1970. Elle exploite l’hypothèse qu’il existerait des fonctions à sens unique, c’est-à-dire de fonctions qui seraient faciles à calculer mais dont la réciproque serait difficile à calculer. Par exemple, l’une des hypothèses derrière le cryptosystème bien connu RSA, que nous présentons brièvement, est que la multiplication de deux entiers est facile, mais l’opération réciproque, à savoir la factorisation d’un produit de deux entiers est difficile.

La deuxième partie présente les résultats mathématiques derrière l’algorithme de Shor, qui permet de factoriser le produit de deux entiers presque aussi facilement que leur multiplication. En effet, depuis que cet algorithme et l’algorithme de Simon ont été découverts dans les années 1990, nous savons que nous pourrons casser les cryptosystèmes à clé publique les plus utilisés de nos jours une fois que les obstacles techniques à la construction d’ordinateurs quantiques de grande taille auront été surmontés. À la fin de cette partie, nous discuterons des stratégies adoptées pour construire des cryptosystèmes résistants aux ordinateurs quantiques.

La troisième partie pourrait intéresser le lecteur curieux des menaces potentielles des ordinateurs quantiques autres que celle présentée dans la deuxième partie. En effet, nous présentons dans cette partie un résultat simple issu des recherches actuelles sur l’impact des ordinateurs quantiques sur la cryptographie à clé secrète.

Ce texte suppose des notions d’arithmétique telles que le PGCD, les groupes et les anneaux, et notamment l’anneau $(\mathbb{Z}/n\mathbb{Z}, +, \times)$ et son groupe multiplicatif (que nous désignerons par $(\mathbb{Z}/n\mathbb{Z})^\times$), des notions de probabilités telles que l’indépendance et les probabilités conditionnelles, ainsi que des notions de complexité algorithmique, en particulier les notations « grand O » et « petit o » utilisées pour donner l’ordre de grandeur du temps d’exécution en fonction de l’entrée.

Cryptographie : un état des lieux

Qu’est-ce que la cryptographie ?

Par définition, le but de la cryptographie est de cacher (grec κρυπτός) ce qui a été écrit (grec γράφειν). Par exemple, une procédure très simple consiste, en n’utilisant que l’alphabet latin à 26 lettres, à décaler chaque lettre de l’alphabet de $k$ places : il s’agit de la plus vieille procédure connue, que l’on appelle aussi chiffrement de César. Ainsi, par exemple, pour $k=1$, il s’agit de remplacer la lettre ’a’ par la lettre ’b’, la lettre ’b’ par la lettre ’c’, ... , la lettre ’z’ par la lettre ’a’. Mathématiquement, nous pouvons voir cela de la manière suivante : tout d’abord, on établit une bijection $f$ entre les 26 lettres de l’alphabet $\mathcal{A}$ et le groupe additif $\mathbb{Z}/26\mathbb{Z}$. Ensuite, la procédure de chiffrement $C_k$, paramétré par $k$, consiste à faire l’opération suivante pour chaque lettre $x$ du message : \begin{align*} C_k &: \mathbb{Z}/26\mathbb{Z} \rightarrow \mathbb{Z}/26\mathbb{Z}\\ & x \mapsto x + k \end{align*} Pour obtenir le texte chiffré en alphabet latin, nous appliquons la fonction $f^{-1}$ à chaque lettre.
Pour déchiffrer un texte chiffré en alphabet latin qui a été chiffré de cette manière, nous appliquons tout d’abord la bijection $f : \mathcal{A} \rightarrow \mathbb{Z}/26\mathbb{Z}$. Ensuite, il est facile de voir que la procédure de déchiffrement $D_k$ est la suivante : \begin{align*} D_k &: \mathbb{Z}/26\mathbb{Z} \rightarrow \mathbb{Z}/26\mathbb{Z}\\ & y \mapsto y - k \end{align*} Le paramètre $k$ qui permet de varier le résultat du chiffrement s’appelle la clé. Il est facile de voir que dans le cas du chiffrement de César, il y a 26 clés possibles. De plus, c’est la même clé qui est utilisée pour le chiffrement et pour le déchiffrement : on parle de cryptographie symétrique. Il existe également des schémas de chiffrement où les clés de chiffrement et de déchiffrement sont différentes : on parle alors de cryptographie asymétrique.

Plus précisément, ce n’est pas tant l’identité ou la différence des clés de chiffrement et de déchiffrement qui fait qu’un cryptosystème est symétrique ou asymétrique, mais la difficulté à déduire la clé de déchiffrement à partir de la clé de chiffrement. Par exemple, nous pouvons remarquer que dans le cas du chiffrement de César, nous aurions pu remplacer $D_k$ par $C_{-k}$ : il s’agit en effet de la même procédure. Autrement dit, nous aurions pu présenter le chiffrement de César avec une seule procédure (addition) pour le chiffrement et le déchiffrement au lieu de deux procédures différentes (addition et soustraction). Mais alors les clés de chiffrement et de déchiffrement ne seraient plus les mêmes. Il serait cependant très facile de les transformer l’une en l’autre.

En revanche, un cryptosystème asymétrique est fabriqué à l’aide de procédures qui offrent une bonne garantie que la clé de déchiffrement ne se calcule pas facilement à partir de la clé de chiffrement. C’est pourquoi une autre expression utilisée pour désigner ces cryptosystèmes est cryptosystème à clé publique. En effet, l’asymétrie est une asymétrie d’information : la clé de chiffrement peut être rendue publique sans donner d’informations sur la clé de déchiffrement qui reste ainsi une donnée connue seulement de la personne ou l’entité qui doit déchiffrer le message. Ainsi, n’importe qui peut chiffrer un message, mais seul le destinataire du message peut le déchiffrer. Pour cette raison, on parle aussi de clé publique et clé privée ou clé secrète.

Nous pouvons définir mathématiquement un cryptosystème de la manière suivante :

Définition 1 Un cryptosystème est donné par un ensemble $(\mathbf{P}, $ $\mathbf{S}, $ $\mathbf{CK}, $ $\mathbf{DK}, $ $\mathbf{C}, $ $\mathbf{D})$ où

$\mathbf{P}$	est l’ensemble des messages à chiffrer, appelés aussi textes clairs.
$\mathbf{S}$	est l’ensemble des messages chiffrés, appelés aussi textes chiffrés.
$\mathbf{CK}$	est l’ensemble des clés de chiffrement.
$\mathbf{DK}$	est l’ensemble des clés de déchiffrement.
$\mathbf{C}$	est l’ensemble des fonctions de chiffrement \[C : (ck,x) \in \mathbf{CK} \times \mathbf{P} \mapsto y \in \mathbf{S}.\]
$\mathbf{D}$	est l’ensemble des fonctions de déchiffrement \[D : (dk,y) \in \mathbf{DK} \times \mathbf{S} \mapsto x \in \mathbf{P}.\]

De plus, pour tous $C \in \mathbf{C}$ , $x \in \mathbf{P}$ et $ck \in \mathbf{CK}$, il existe $D \in \mathbf{D}$ et $dk \in \mathbf{DK}$ telles que $D(dk,C(ck,x)) = x$.

La dernière propriété garantit en effet que le système est « complet », c’est-à-dire qu’il y a un moyen de récupérer un message que l’on a chiffré.

Cryptographie à clé publique : RSA

Notons $f : \mathbf{DK} \rightarrow \mathbf{CK}$ la fonction qui fait correspondre à une clé secrète la clé publique correspondante¹ . Ce qui fait qu’un cryptosystème est symétrique ou non est la difficulté comparée de calcul de $f$ et de $f^{-1}$. Si le calcul de $x = f^{-1}(y)$ est, pour la plupart des $y \in \mathbf{CK}$, plus « difficile »$~$que celui de $f(x)$, en termes d’ordre de grandeur du temps de calcul nécessaire, la fonction $f$ est dite à sens unique. Un système cryptographique est asymétrique si $f$ est supposée être à sens unique.

Une subtilité mérite d’être soulignée : l’utilisation jusqu’ici des termes et expressions tels que « hypothèse », « supposé être », etc. vient du fait qu’il n’y a aucune preuve que les fonctions à sens unique existent réellement. Par conséquent, ce qui est à la base de la cryptographie asymétrique est en réalité une conjecture sophistiquée : des années d’efforts n’ont pas permis de trouver une façon rapide d’inverser telle fonction, donc nous pouvons faire l’hypothèse qu’elle est à sens unique.

Le cryptosystème RSA, inventé par Ronald Rivest, Adi Shamir et Leonard Adleman en 1977, est l’un des premiers cryptosystèmes asymétriques et son usage est toujours répandu de nos jours. Dans ce texte, nous allons nous contenter de présenter son fonctionnement et l’intuition des hypothèses sur lesquelles il repose. Pour plus de détails, on renvoie à un autre article de CultureMath.

RSA utilisé par le site d’une banque

Le cryptosystème RSA est défini comme suit :

Les clés publiques et privées sont calculées de la manière suivante : on choisit deux nombres premiers distincts $p$ et $q$ et on calcule $n=pq$, puis on choisit un $e$ tel que $1 \lt e \lt (p-1)(q-1)$ et $\mathrm{PGCD}((p-1)(q-1),e) = 1$. Les clés publiques sont alors les couples $(n,e)$. La clé privée correspondant à cette clé publique est un entier $d$ tel que $1 \lt d \lt (p-1)(q-1)$ et qui vérifie l’équation $ed + k(p-1)(q-1) = 1$ pour un $k \in \mathbb{Z}$.
Les ensembles de textes clairs et de textes chiffrés sont identiques, ils sont donnés par $\mathbb{Z}/n\mathbb{Z} \setminus \{0\}$.
Les fonctions de chiffrement sont les fonctions \[C : ((n,e),x) \in \mathbf{CK} \times \mathbf{P} \mapsto x^e \bmod n.\]
Les fonctions de déchiffrement sont les fonctions \[D : (d,y) \in \mathbf{DK} \times \mathbf{S} \mapsto y^d \bmod n.\]

Quelques remarques sur cette définition :

Premièrement, nous rappelons l’énoncé du théorème de Bézout.

Théorème 1 Deux entiers $a, b \in \mathbb{Z}$ sont co-premiers si et seulement s’il existe $x,y \in \mathbb{Z}$ tels que $ax + by = 1$.

Grâce à ce théorème et l’hypothèse $\operatorname{PGCD}((p-1)(q-1),e) = 1$ sur $e$, l’existence d’une clé privée $d$ correspondant à la clé publique $e$ est garantie.

Deuxièmement, nous rappelons un cas particulier du théorème d’Euler.

Théorème 2 Pour tout $p, q, a \in \mathbb{Z}$ tels que $p, q$ sont premiers et distincts et $\operatorname{PGCD}(a,pq) = 1$, on a $a^{(p-1)(q-1)} = 1 \bmod pq$.

Un texte chiffré $y$ s’écrit $y = x^e \bmod n$ pour un texte clair $x \in \mathbf{P}$. Déchiffrer $y$ revient à calculer $y^{d} \bmod n$ c’est-à-dire $x^{ed} \bmod n$. Or, $d$ vérifie par définition $ed + k(p-1)(q-1) = 1$, donc : \begin{align*} x^{ed} &= x^{1 - k(p-1)(q-1)} \bmod n\\ &= x \cdot (x^{(p-1)(q-1)})^{-k} \bmod n\\ &= x \cdot 1^{-k} \bmod n \text{ si $\operatorname{PGCD}(x,n) = 1$}\\ &= x \bmod n \end{align*} Un raisonnement plus complexe permet de montrer que ceci est vérifié même lorsque $\operatorname{PGCD}(x,n) \not = 1$. Ainsi, il est toujours possible de déchiffrer un message chiffré.

Ronald Rivest, Adi Shamir, Leonard Adleman

La cryptographie en pratique

Plusieurs considérations orientent l’utilisation de la cryptographie en pratique.

Une première considération est celle du nombre de clés nécessaires. En effet, supposons qu’il y a $n$ entités qui souhaitent communiquer ensemble. Avec la cryptographie à clé secrète, chaque paire d’entités doit disposer d’une clé pour chiffrer ses communications, d’où la nécessité d’avoir $\binom{n}{2} = \frac{n(n-1)}{2}$ clés au total. Avec la cryptographie à clé publique, la clé publique de chaque entité permet à toutes les autres de communiquer avec elle. Ainsi, il faut un total de $2n$ clés ($n$ clés publiques et $n$ clés secrètes).

Une autre question qui se pose est celle de la rapidité. Les cryptosystèmes symétriques sont beaucoup plus rapides que les asymétriques. En pratique, on privilégie l’utilisation d’un système hybride ² : un cryptosystème asymétrique sert à communiquer les clés d’un cryptosystème symétrique qui sera utilisé par la suite pour les échanges volumineux.

La cryptographie à clé publique face aux ordinateurs quantiques

Dans cette section, nous expliquerons en quoi l’algorithme de Shor met à mal le cryptosystème RSA. Pour ce faire, nous allons commencer par expliciter en quoi la factorisation rapide permettrait de casser le cryptosystème RSA. Ensuite, nous donnerons un aperçu de l’algorithme de Shor en nous concentrant sur les résultats mathématiques qui y sont sous-jacents. Pour finir, nous donnerons l’intuition de ce qui fait la force mais aussi les limites des ordinateurs quantiques et nous ferons le lien avec des notions de complexité algorithmique afin de mettre en évidence les motivations derrière l’introduction de la cryptographie post-quantique.

RSA et factorisation

En général, les attaques contre un cryptosystème peuvent être partagées en deux catégories : les attaques de nature mathématique, qui exploitent des relations mathématiques sous-jacentes, et les attaques d’implémentation, par exemple le fait d’exploiter les processus physiques sous-jacents (consommation d’électricité, etc.) pour retrouver des informations qui devraient en principe rester secrètes, ou bien le fait d’exploiter une faiblesse du codage informatique.

L’algorithme de Shor permet de factoriser rapidement et donc monter une attaque de nature mathématique contre le cryptosystème RSA. Avant de présenter les grandes lignes du fonctionnement de cet algorithme, nous allons donner plus de détails sur le temps de calcul nécessité par RSA et expliciter le rapport qui existe entre la sécurité de ce cryptosystème et le problème de factorisation.

Reprenons les notations introduites un peu avant, et notons $N = \lceil \log_2(n) \rceil $ le nombre de chiffres de $n=pq$ en base 2, c’est-à-dire la base utilisée en informatique (bien évidemment, les raisonnements qui suivent restent valables pour n’importe quelle base). Les fonctions de chiffrement et de déchiffrement sont des élévations à une puissance modulo $n$. Il existe un algorithme d’ exponentiation rapide qui permet de calculer $x^a \bmod n$ à l’aide d’environ $\log_2(a)$ multiplications. La multiplication de deux entiers d’au plus $N$ chiffres peut se faire en environ $N^2$ opérations élémentaires. Or, $x \lt n$, donc $x$ s’écrit avec au plus $N$ chiffres, et il n’est pas très coûteux de ramener le résultat d’une multiplication à un entier $\lt n$ après chaque multiplication. Ainsi, pour chiffrer et déchiffrer lorsque l’on connaît les clés, il faut un nombre d’opérations élémentaires de l’ordre de $\log_2(a)N^2$. Or, $a$ correspond à l’exposant dans le cryptosystème RSA, donc $a \lt (p-1)(q-1)$, et ainsi $\log_2(a) = O(N)$. Finalement, on peut chiffrer et déchiffrer en $O(N^3) = O(\log_2(n)^3)$ opérations élémentaires. Il s’agit d’un ordre de grandeur polynomial en $N$, le nombre de chiffres de $n$ en base 2.

Un vecteur d’attaque possible pour déchiffrer lorsque l’on n’est pas en possession de la clé secrète consiste à factoriser $n=pq$. En effet, une fois que $p$ et $q$ sont connus, la clé secrète $d$ est facile à trouver. Rappelons que celle-ci est, par définition, l’unique entier tel que $0 \lt d \lt (p-1)(q-1)$ et $ed + k(p-1)(q-1) = 1$ pour un certain $k \in \mathbb{Z}$. Or, $e$ est la clé publique et $(p-1)(q-1)$ se calcule facilement si $p$ et $q$ sont connus. Ainsi, trouver $d$ revient à résoudre l’équation de Bézout faisant intervenir $e$ et $(p-1)(q-1)$.

Or, malgré des efforts intenses, les meilleurs algorithmes de factorisation sur ordinateur classique nécessitent un nombre non polynomial d’opérations élémentaires. Plus précisément, ils nécessitent un nombre sous-exponentiel d’opérations élémentaires, c’est-à-dire, pour simplifier un peu, un nombre d’opérations en $2^{o(N)}$. Le point important est que le rapport entre le nombre d’opérations pour factoriser, $F(N)$, et le nombre d’opérations pour chiffrer avec RSA, $C(N)$, vérifie $\underset{N \rightarrow \infty}{\lim} \frac{C(N)}{F(N)} = 0$. En d’autres termes, plus $N$ est grand, plus l’écart entre ces deux temps de calcul est grand, et à partir d’une certaine valeur de $N$, nous serons dans une situation où le temps pour chiffrer $C(N)$ reste raisonnable mais $F(N)$ représente des millions d’années, par exemple. C’est pour cette raison que RSA représentait un très bon choix de cryptosystème à clé publique jusqu’à la découverte de l’algorithme de Shor.

Algorithme de Shor

L’algorithme de Shor, découvert en 1994 par Peter Shor, permet de trouver un diviseur $d$ d’un nombre $n$ à $N$ chiffres dans une base donnée, par exemple en base 2, en temps $O(N^3)$. Cet algorithme s’appuie fortement sur les résultats clés suivants :

Lemme 1 Soient $x \in \mathbb{Z}, n \in \mathbb{N}$ tels que $x^2 = 1 \bmod n$ et $x \not = \pm 1 \bmod n$. Alors $\operatorname{PGCD}(x \pm 1,n)$ est un diviseur non trivial de $n$.

Avant d’énoncer le résultat suivant, on rappelle que l’ordre d’un élément $a$ de $(\mathbb{Z}/n\mathbb{Z})^\times$ est défini comme étant le plus petit entier $r>1$ tel que $a^r = 1$.

Proposition 1 Soient $a \in \mathbb{Z}, n \in \mathbb{N}$ tels que $\operatorname{PGCD}(a,n)=1$.

Soit $r$ l’ordre de la classe d’équivalence de $a$ dans $(\mathbb{Z}/n\mathbb{Z})^\times$.

Alors, si $r$ est pair et $a^{r/2} \not = \pm 1 \bmod n$, $\operatorname{PGCD}(a^{r/2} \pm 1,n)$ est un diviseur non trivial de $n$.

Proposition 2 Soient $p,q \in \mathbb{N}$ premiers et distincts, $p,q>2$ et soit $n=pq$. Soit $a$ pris uniformément au hasard dans $(\mathbb{Z}/n\mathbb{Z})^\times$ et soit $r$ l’ordre de $a$. Alors $r$ est pair et $a^{r/2} \not = \pm 1 \bmod n$ avec une probabilité supérieure à 3/8.

Cette proposition est intéressante pour la raison suivante : elle garantit que l’on peut trouver un $a$ vérifiant la propriété « $r$ est pair et $a^{r/2} \not = \pm 1 \bmod n$ » rapidement. En effet, la proposition dit que pour un $a$ tiré au hasard, cette propriété est vérifiée avec une probabilité supérieure à une constante. Par conséquent, si l’on tire plusieurs valeurs de $a$ de façon indépendante, l’une d’entre elle vérifiera sûrement cette propriété au bout d’un nombre borné de tirages.

Nous allons donner une preuve de cette proposition dans le cas qui nous intéresse, c’est-à-dire $n=pq$ avec $p$ et $q$ premiers, distincts et impairs. Cette preuve repose sur quelques résultats d’arithmétique dont le théorème des restes chinois . Nous rappelons ces résultats que nous admettons.

Théorème 3 Soient $m, n \in \mathbb{N}$ tels que $\operatorname{PGCD}(m,n) = 1$. Alors l’application \begin{align*} f : \mathbb{Z}/mn\mathbb{Z} &\rightarrow \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}\\ a &\mapsto (a \bmod m, a \bmod n) \end{align*} est un isomorphisme d’anneaux.

En particulier, cet isomorphisme d’anneaux induit un isomorphisme des groupes multiplicatifs $(\mathbb{Z}/mn\mathbb{Z})^\times$ et $(\mathbb{Z}/m\mathbb{Z})^\times \times (\mathbb{Z}/n\mathbb{Z})^\times$.

Lemme 2 Soit $p \in \mathbb{N}$ premier, $p>2$. Alors au moins la moitié des éléments de $(\mathbb{Z}/p\mathbb{Z})^\times$ sont d’ordre pair.

Nous admettons ce lemme par souci de concision : en effet, bien que sa preuve ne soit pas très complexe, elle fait appel à plusieurs résultats d’arithmétique autres que ceux déjà mentionnés. Nous soulignons seulement une conséquence de ce lemme qui nous servira dans la preuve de la Proposition 2 : si un élément $x \in (\mathbb{Z}/p\mathbb{Z})^\times$ est choisi uniformément au hasard, son ordre sera pair avec probabilité au moins $1/2$.

Lemme 3 Soit $p \in \mathbb{N}$ premier. Si $x \in \mathbb{Z}$ est tel que $x^2 = 1 \bmod p$, alors $x = \pm 1 \bmod p$.

Ce lemme est facile à vérifier à l’aide un raisonnement similaire à celui employé dans la preuve du Lemme 1.

D’après le théorème des restes chinois, choisir un $a \in (\mathbb{Z}/n\mathbb{Z})^\times$ uniformément au hasard revient à choisir de façon uniforme et indépendante un élément de $(\mathbb{Z}/p\mathbb{Z})^\times$ et un élément de $(\mathbb{Z}/q\mathbb{Z})^\times$. On note $a_p := a \bmod p$ et $a_q := a \bmod q$. Soient $r, r_p, r_q \in \mathbb{N}$ les ordres respectivement de $a$ dans $(\mathbb{Z}/n\mathbb{Z})^\times$, $a_p$ dans $(\mathbb{Z}/p\mathbb{Z})^\times$ et $a_q$ dans $(\mathbb{Z}/q\mathbb{Z})^\times$. On considère l’égalité $a^r = 1$ dans $(\mathbb{Z}/n\mathbb{Z})^\times$. En appliquant l’isomorphisme du théorème des restes chinois des deux côtés du signe égal, nous obtenons $(a_p^r, a_q^r) = (1,1)$ dans $(\mathbb{Z}/p\mathbb{Z})^\times \times (\mathbb{Z}/q\mathbb{Z})^\times$ (puisqu’un morphisme de groupes multiplicatifs envoie l’élément neutre de l’un sur l’élément neutre de l’autre). Ainsi $a_p^r = 1 \bmod p$. Par conséquent, l’ordre de $a$ dans $(\mathbb{Z}/p\mathbb{Z})^\times$, c’est-à-dire $r_p$, divise $r$. Le même raisonnement vaut pour $r_q$. Par conséquent, $r$ est pair si $r_p$ est pair et/ou $r_q$ est pair, autrement dit si $r_p$ et $r_q$ ne sont pas tous les deux impairs à la fois. D’où \begin{align*} \mathbb{P}(r \text{ est pair}) &\geq \mathbb{P}(r_p \text{ est pair ou } r_q \text{ est pair})\\ &\geq 1 - \mathbb{P}(r_p \text{ est impair et } r_q \text{ est impair})\\ &\geq 1 - \mathbb{P}(r_p \text{ est impair}) \mathbb{P}(r_q \text{ est impair}) \end{align*}

La dernière ligne résulte du fait que $a_p$ et $a_q$ sont choisis indépendamment par hypothèse, par conséquent la parité de $r_p$ est indépendante de celle de $r_q$ aussi.

Or, le Lemme 2 entraîne que $\mathbb{P}(r_p$ est pair$) \geq 1/2$, donc $\mathbb{P}(r_p$ est impair$) \leq 1/2$. Il en est de même pour $r_q$, donc $\mathbb{P}(r_p$ est impair$)\mathbb{P}(r_q$ est impair$) \leq 1/4$. Ainsi, en reprenant nos calculs ci-dessus \begin{align*} \mathbb{P}(r \text{ est pair}) &\geq 1 - \mathbb{P}(r_p \text{ est impair}) \mathbb{P}(r_q \text{ est impair})\\ &\geq 1 - 1/4 \end{align*}

D’où $\mathbb{P}(r$ est pair$) \geq 3/4$. Ensuite, supposons que $r$ est pair. Alors on a $a_p^{r} = 1 \bmod p$ et $a_q^{r} = 1 \bmod q$, donc $a_p^{r/2} = \pm 1 \bmod p$ et $a_q^{r/2} = \pm 1 \bmod q$ d’après le Lemme 3, ou quatre configurations en tout. Par le théorème des restes chinois, seulement deux de ces configurations correspondent aux deux cas $a^{r/2} = \pm 1 \bmod n$, donc $a^{r/2} \not = \pm 1 \bmod n$ dans les deux autres cas. Donc cela arrive avec probabilité $1/2$ pour $a_p$ et $a_q$ choisis indépendamment et uniformément au hasard.

Ainsi, on a $\mathbb{P}(r$ est pair$) \geq 3/4$ et $\mathbb{P}(a^{r/2} \not = \pm 1 \bmod n \mid r$ est pair$) = 1/2$, d’où \begin{align*} \mathbb{P}(r \text{ est pair et } a^{r/2} \not = \pm 1\bmod n) &= \mathbb{P}(a^{r/2} \not = \pm 1 \bmod n \mid r \text{ est pair})\mathbb{P}(r \text{ est pair})\\ &\geq 3/4 \cdot 1/2\\ &\geq 3/8 \end{align*}

Ainsi, si nous disposons de $a$ et de $r$ vérifiant ces propriétés (c’est-à-dire, tels que $r$ est pair, $a^r = 1 \bmod n$ et $a^{r/2} \not = \pm 1 \bmod n$), alors $a^{r/2} \pm 1 \bmod n$ et $\operatorname{PGCD}(a^{r/2} \pm 1 \bmod n,n)$ se calculent rapidement et nous donnent accès à un diviseur non trivial de $n$³. Dans le cas qui nous intéresse, $n=pq$. Ainsi, un diviseur non trivial de $n$ est soit $p$, soit $q$ et dès lors le tour est joué : nous avons réussi à factoriser $n$. Le souci, c’est qu’il n’existe aucun algorithme classique pour calculer $r$ rapidement. Or, le problème de trouver $r$ peut se formuler comme un problème de recherche de période :

Problème 1 (Recherche de période) Étant donné une fonction $f : \mathbb{N} \rightarrow \{1, \ldots , n\}$ avec la garantie qu’il existe $r$ tel que $f(x+r) = f(x)$, trouver $r$.

Plus précisément, considérons la fonction $f_a : t \mapsto a^t \bmod n$ pour un $a$ co-premier avec $n$. Le théorème d’Euler, dont nous avons vu un cas particulier plus tôt, garantit l’existence d’un $r$ tel que $a^r = 1 \bmod n$ (même si ce $r$ peut ne pas être le plus petit entier possible vérifiant cette égalité). Par conséquent, $a^{r+t} = a^{t} \bmod n$. Autrement dit, $r$ vérifie $f(t) = f(t+r)$. Ainsi, nous pouvons voir le problème de trouver $r$ comme un problème de recherche de période.

Les problèmes de type recherche de période admettent des algorithmes quantiques efficaces. Le premier algorithme qui résout un problème de ce type est l’algorithme de Simon, qui date de 1994. Il a été une inspiration pour l’algorithme de Shor dont nous allons maintenant détailler les étapes.

[label=] Choisir un $a \lt n$ au hasard.
Calculer $\operatorname{PGCD}(a,n)$. Si $\operatorname{PGCD}(a,n) \not = 1$, on a trouvé un facteur de $n$, sinon passer à l’étape suivante.

L’algorithme d’Euclide, qui consiste à répéter la division euclidienne de deux nombres, puis du plus petit nombre et le reste de la division jusqu’à tomber sur un reste égal à 1, permet de calculer le PGCD de $a$ et de $n$ en $O(\log_2(n)^2) = O(N^2)$ opérations élémentaires.
Calculer une période $r$ de la fonction $f_a : t \in \mathbb{N} \mapsto a^t \bmod n$.

Il s’agit de l’étape qui est calculable très rapidement en temps $O(N^3)$ avec un ordinateur quantique.
Si $r$ est impair ou $a^{r/2} = \pm 1 \bmod n$, revenir à (1).

La Proposition 2 garantit que cette étape sera franchie après avoir testé un nombre constant et peu élevé de valeurs de $a$.
Calculer $\operatorname{PGCD}(a^{r/2} \pm 1 \bmod n,n)$.

Encore une fois, ce calcul s’effectue en temps $O(N^2)$ en utilisant l’algorithme d’Euclide. De plus, la Proposition 1 garantit que le résultat du calcul est un diviseur non trivial de $n$.

Peter Shor

Les particularités du calcul quantique

Comme nous l’avons vu, l’algorithme de Shor ne résout pas le problème de la factorisation de façon « magique ». Il exploite des propriétés de la factorisation qui permettent de la ramener à un autre problème qui est celui de la recherche de période. Autrement dit, il exploite le fait que le problème soit doté d’une structure, qu’il ne s’agisse pas de la simple recherche d’un élément. Le but de cette section est de mettre en évidence ce qui rend le calcul quantique capable de ce type d’exploit mais pas de tout.

La fameuse expérience de pensée du chat de Schrödinger met en évidence le caractère paradoxal d’une propriété des états quantiques qui est celle de la superposition. Du point de vue mathématique, cette propriété n’a rien d’étonnant : l’évolution d’un système quantique dans le temps est régie par l’équation de Schrödinger qui est une équation différentielle linéaire, donc toute combinaison linéaire de ses solutions est également solution. Cela signifie que si un atome radioactif a la possibilité d’être soit intact, soit désintégré, il a également la possibilité d’être une combinaison des deux. Ceci est déjà loin d’être conforme à l’intuition. Or, si la vie ou la mort d’un chat dans une boîte hermétique dépend de l’état de l’atome, alors le chat aussi peut être dans un état qui est une combinaison de la mort et de la vie, ce qui est complètement contre-intuitif. Or, une autre propriété des états quantiques est que toute perturbation, en particulier toute mesure les modifie : ainsi, en ouvrant la boîte, nous verrons un chat qui est soit vivant, soit mort.

L’expérience de pensée du chat de Schrödinger est souvent utilisé pour illustrer les nombreuses interprétations de la mécanique quantique. Nous l’avons évoquée afin de mettre en évidence l’asymétrie entre le contenu en information et l’accès à cette information qui fait la force mais aussi les limites du calcul quantique. En effet, si l’unité d’information classique est le bit qui peut valoir 0 ou 1, l’unité d’information quantique est le qubit, qui peut être dans l’état 0, 1 ou toute combinaison linéaire des deux : il peut contenir jusqu’à 2 unités d’information classique. De plus, $n$ bits classiques ensemble peuvent être dans un seul état parmi $2^n$ états possibles, c’est-à-dire contenir seulement $n$ unités d’information, tandis que $n$ qubits peuvent être dans n’importe quelle combinaison de ces $2^n$ états, autrement dit contenir jusqu’à $2^n$ unités d’information classique. Néanmoins, tout comme nous ne pouvons pas observer un chat ni vivant, ni mort, mais dans un état combiné, nous ne pouvons pas accéder à la totalité de ces $2^n$ unités d’information. Tout comme l’un des deux états « mort » ou « vivant » de l’état combiné du chat est détruit lorsque la boîte est ouverte, la part d’information qui ne correspond pas au résultat d’une mesure est détruite. Ceci explique pourquoi le calcul quantique permet de simplifier considérablement la résolution de problèmes ayant une certaine structure alors qu’elle n’est pas d’une utilité considérable pour les problèmes de recherche sans structure sous-jacente importante : en effet, on peut se servir de la superposition qui offre un certain degré de parallélisme pour concentrer une propriété structurale donnée de sorte qu’elle ressorte en mesurant, mais cet avantage est perdu dès lors que l’on ne cherche pas tant une propriété structurale qu’un élément particulier, car chaque accès à l’information détruit le parallélisme de cette information.

Erwin Schrödinger

Cryptographie post-quantique

Un problème ouvert en informatique théorique est le fameux problème « $\mathbf{P} = \mathbf{NP}~?$ ». Pour dire les choses simplement, un problème appartient à la classe $\mathbf{P}$ s’il admet une procédure de résolution dont le temps de calcul est polynomial, et un problème appartient à la classe $\mathbf{NP}$ s’il admet une procédure de vérification d’une solution donnée ayant un temps de calcul polynomial. Ce problème est lié mais non identique à celui de l’existence des fonctions à sens unique : en effet, il suffit que quelques instances d’un problème soient faciles à vérifier mais a priori difficiles à résoudre pour le placer dans la classe $\mathbf{NP}$, mais le problème reste facile à résoudre en moyenne. Par conséquent, il ne donne pas lieu à une fonction à sens unique.

L’algorithme de Shor exploite le fait que l’on puisse ramener le problème de factorisation à un problème de recherche de période. Autrement dit, on peut comparer ces deux problèmes en termes de leur difficulté de résolution : si on arrive à trouver la période, on arrivera à factoriser sans grande difficulté supplémentaire. La résolution du problème de recherche de période est donc au moins aussi difficile que le problème de factorisation. Plus généralement, on peut comparer n’importe quel ensemble de problèmes de ce point de vue : il est ainsi possible d’établir une hiérarchie des problèmes en termes de leurs difficultés de résolution respectives. En procédant ainsi avec la classe $\mathbf{NP}$, la hiérarchie résultante a la particularité qu’il existe une sorte de plafond, c’est-à-dire qu’il existe un ensemble de problèmes de la classe $\mathbf{NP}$, dits les problèmes $\mathbf{NP}$-complets, qui sont au moins aussi difficiles que tous les autres problèmes de la classe $\mathbf{NP}$.

De plus, le problème de factorisation est conjecturé être dans la classe $\mathbf{NP}$ sans être $\mathbf{NP}$-complet. Un autre problème utilisé dans les cryptosystèmes à clé publique actuels est le problème du logarithme discret, qui partagerait cette caractéristique d’être dans la classe $\mathbf{NP}$ sans être $\mathbf{NP}$-complet, et il est également formulable comme un problème de recherche de période. À l’instar de la factorisation que nous avons étudiée plus haut, ces problèmes ont des algorithmes de résolution inefficaces (typiquement sous-exponentiels) avec un ordinateur classique, mais deviennent résolubles en temps polynomial avec un ordinateur quantique. Ainsi, on parle d’amélioration quantique exponentielle pour ces problèmes, puisque le meilleur algorithme classique a un temps de calcul qui est une fonction exponentielle de celui du meilleur algorithme quantique.

C’est aussi pourquoi les efforts pour construire des cryptosystèmes résistants aux ordinateurs quantiques privilégient les problèmes $\mathbf{NP}$-complets : il y a peu de risque que ces problèmes présentent une autre structure que celle d’un problème de recherche (bien sûr, cela ne signifie pas qu’il soit facile ou judicieux d’utiliser n’importe quel problème $\mathbf{NP}$-complet pour construire un cryptosystème). En effet, dans ce cas l’amélioration quantique est au plus polynomiale, c’est-à-dire que le temps de calcul du meilleur algorithme classique est une fonction polynomiale du temps de calcul du meilleur algorithme quantique. Par exemple, la recherche dans un ensemble de taille $n$ a un temps de calcul en $O(n)$ en algorithmique classique et en $O(\sqrt{n})$ en algorithmique quantique avec l’algorithme de Grover : on parle d’amélioration quadratique.

Lov Grover

La cryptographie symétrique face aux ordinateurs quantiques

Le chiffrement par bloc

Nous avons vu que ce qui rendait la cryptographie asymétrique envisageable était l’hypothèse de l’existence de fonctions à sens unique, qui garantissaient que la clé secrète (de déchiffrement) était difficile à calculer à partir de la clé publique (de chiffrement). Dans les cryptosystèmes symétriques, où il y a une seule clé, secrète, pour chiffrer et déchiffrer, le but est avant tout de bâtir un système de chiffrement où le texte chiffré ne donne aucune information sur le texte clair, même lorsque, comme le dit un adage, « l’adversaire connaît le système », c’est-à-dire dans une situation où la seule donnée inconnue de l’adversaire est la clé. En d’autres termes, la sécurité du système n’est pas liée à la difficulté d’un problème algorithmique. Ainsi, pour trouver la clé, il n’y a pas, a priori, de meilleure solution que de la chercher, ce qui laisse croire qu’une amélioration quantique serait au plus polynomiale, ce qui n’est pas dramatique.

Or, un célèbre résultat prouvé par Claude Shannon en 1949 montre que la sécurité parfaite ou inconditionnelle, c’est-à-dire l’absence de dépendance statistique entre un texte chiffré et le texte clair correspondant en l’absence de la clé, n’est possible que si la clé est au moins aussi longue que le texte à chiffrer. De plus, il faudrait utiliser une nouvelle clé pour chaque nouveau message à chiffrer sous peine de révéler des informations.

Il va sans dire que cela n’est pas envisageable en pratique. Une deuxième solution qui a été adoptée en pratique consiste à prendre une clé de taille fixe et raisonnablement petite et découper le message en blocs de même taille et chiffrer les blocs un par un. Pour cette raison, on parle de chiffrement par bloc. Il est immédiat à partir du résultat de Shannon qu’un tel système de chiffrement n’a pas la propriété de sécurité inconditionnelle. En pratique, on opte pour la propriété que pour casser le système il faudrait beaucoup de temps et de ressources, par exemple l’ensemble des ordinateurs d’un grand pays et des millions d’années.

L’étude approfondie de l’impact des ordinateurs quantiques sur la cryptographie symétrique en est toujours à ses prémices. En effet, ce n’est que depuis les années 2010 que des recherches ont été menées sur les problèmes de type recherche de période, dont nous avons vu qu’ils admettent une amélioration quantique exponentielle du temps de calcul. Nous allons présenter une des premières attaques quantiques de type recherche de période menée sur un schéma de chiffrement par bloc (c’est-à-dire, un schéma pour chiffrer un seul bloc), le schéma d’Even-Mansour [3]. Ce schéma est intéressant avant tout pour des raisons théoriques, cependant une version « itérée » de ce schéma a des ressemblances avec AES, qui est le standard actuel en cryptographie symétrique. Ainsi, contrairement à l’attaque par l’algorithme de Shor sur le cryptosystème RSA, qui présente un réel danger, l’attaque que nous allons présenter a plutôt le statut d’une preuve de concept qui a le mérite d’être simple à comprendre. De plus, cette attaque fait l’hypothèse supplémentaire que le schéma en question est en réalité implémenté tel quel sur un ordinateur quantique.

Un exemple : Even-Mansour

Dans cette section, nous supposerons que le texte, la clé, ... sont donnés sous forme d’une chaîne de bits. Le symbole $\oplus$ représente la disjonction exclusive (le « ou » exclusif). Pour comprendre la suite de cette section, il suffit de connaître les propriétés suivantes de la disjonction exclusive :

Elle est commutative et associative.
$x \oplus x = 0$.
$0 \oplus x = x \oplus 0 = x$.
Le schéma d’Even-Mansour est donné comme suit :
L’ensemble des textes clairs $\mathbf{P}$ et des textes chiffrés $\mathbf{S}$ sont l’ensemble des chaînes binaires de longueur $n$, où $n$ est un entier pair. $\mathbf{P} = \mathbf{S} =\{0,1\}^n$.
L’ensemble des clés $\mathbf{CK} = \mathbf{DK}$ est également $\{0,1\}^n$. Chaque clé se décompose comme suit : $k = k_1k_2$ où $k_1$ et $k_2$ sont de même longueur $n/2$.
Les fonctions de chiffrement sont les fonctions $C : (k, x) \in \mathbf{CK} \times \mathbf{P} \mapsto P(x \oplus k_1) \oplus k_2$, où $P : \{0,1\}^n \rightarrow \{0,1\}^n$ est une permutation.
Les fonctions de déchiffrement sont les fonctions $D : (k, y) \in \mathbf{DK} \times \mathbf{S} \mapsto P^{-1}(y \oplus k_2) \oplus k_1$, où $P^{-1} : \{0,1\}^n \rightarrow \{0,1\}^n$ est l’inverse de la permutation $P$.

On vérifie aisément qu’en déchiffrant un message chiffré on tombe sur le message original. En effet, pour $y = P(x \oplus k_1) \oplus k_2$, on a

\begin{align*} D(k,y) &= P^{-1}(y \oplus k_2) \oplus k_1\\ &= P^{-1}(P(x \oplus k_1) \oplus k_2 \oplus k_2) \oplus k_1\\ &= P^{-1}(P(x \oplus k_1) \oplus 0) \oplus k_1\\ &= P^{-1}(P(x \oplus k_1)) \oplus k_1\\ &= (x \oplus k_1) \oplus k_1\\ &= x \oplus 0\\ &= x \end{align*}

Nous rappelons ce qu’est un problème de recherche de période en adaptant les notations avant de montrer comment on peut associer un tel problème au schéma d’Even-Mansour.

Problème 2 (Recherche de période) Étant donné une fonction $f : \{0,1\}^n \rightarrow \{0,1\}^n$ avec la garantie qu’il existe $r$ tel que $f(x \oplus r) = f(x)$, trouver $r$.

Supposons qu’un adversaire dispose d’un ordinateur quantique capable de calculer $f(x) = C(k,x) \oplus P(x)$ en prenant en entrée un texte clair $x$. Il y a une nuance dans cette affirmation, mais rien de contradictoire. En effet, d’après les hypothèses, l’adversaire ne connaît ni le bon message, ni la bonne clé, mais il connaît le système, c’est-à-dire qu’il connaît la permutation $P$ qui est utilisée. Il peut également calculer $C(k,x)$ sans connaître $k$, par exemple en s’emparant de l’ordinateur qui fait ce calcul d’une façon ou d’une autre. Le point délicat est que cet ordinateur doit alors être un ordinateur quantique, ce qui n’est pas si étonnant si l’on fait l’hypothèse d’une substitution progressive des ordinateurs quantiques aux ordinateurs classiques.

Or, on vérifie par un simple calcul que $k_1$ est une période de la fonction $f$ :

\begin{align*} f(x \oplus k_1) &= P(x \oplus k_1 \oplus k_1) \oplus k_2 \oplus P(x \oplus k_1)\\ &= P(x \oplus 0) \oplus k_2 \oplus P(x \oplus k_1)\\ &= P(x) \oplus k_2 \oplus P(x \oplus k_1)\\ &= P(x \oplus k_1) \oplus k_2 \oplus P(x)\\ &= f(x) \end{align*}

Une fois que nous avons réussi à récupérer $k_1$ à l’aide de l’ordinateur quantique, $k_2$ est facile à récupérer : $k_2 = C(k,x) \oplus P(x \oplus k_1)$. En effet :

\begin{align*} C(k,x) \oplus P(x \oplus k_1) &= P(x \oplus k_1) \oplus k_2 \oplus P(x \oplus k_1)\\ &= P(x \oplus k_1) \oplus P(x \oplus k_1) \oplus k_2 \\ &= 0 \oplus k_2\\ &= k_2 \end{align*}

Remerciements

L'auteure tient à remercier les membres du groupe CultureMath-IREM de Bordeaux pour leurs remarques et suggestions.

Ce document a été adapté de $ \LaTeX $ en utilisant H^EV^EA et des macros CultureMath développées par Robert Cabane (membre du groupe CM-IREM Bordeaux).

Références

[1]: S. Aaronson, Shor, I’ll do it https://www.scottaaronson.com/blog/?p=208, 2007.
[2]: M. Bellare and S. Goldwasser, Lecture Notes on Cryptography, 2008.
https://cseweb.ucsd.edu/~mihir/papers/gb.pdf
[3]: H. Kuwakado and M. Morii, Security on the quantum-type Even-Mansour cipher, ISITA, (2012), p. 312–316.
[4]: P. W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, 26 (1997), p. 1484–1509.
[5]: S. Singh, L’Histoire des codes secrets, J.-C. Lattès, 1999. Trad. Catherine Coqueret.
[6]: U. Vazirani, CS294-2: Quantum Computation, 2004.
https://people.eecs.berkeley.edu/~vazirani/f04quantum/quantum.html

1: Dorénavant, jusqu’à ce qu’il soit de nouveau question de cryptographie à clé secrète, nous écrirons « clé publique » pour « clé de chiffrement », et « clé secrète » pour « clé de déchiffrement », car ces expressions sont synonymes dans le cadre de la cryptographie à clé publique.
2: Quelques exemples d’un tel système hybride en pratique : le protocole HTTPS, primordial par exemple pour les sites de vente en ligne; ou encore le logiciel GPG que l’on peut utiliser pour chiffrer ses mails.
3: En effet, $\operatorname{PGCD}(a^{r/2} \pm 1 \bmod n,n)$ n’est autre que $\operatorname{PGCD}(a^{r/2} \pm 1,n)$ qui est un diviseur non-trivial de $n$ d’après la Proposition 1. Cela découle de la propriété $\operatorname{PGCD}(x,y) = \operatorname{PGCD}(x-y,y)$ pour $x, y \in \mathbb{Z}$ qui nous permet de substituer à $a^{r/2} \pm 1$ le plus petit représentant de sa classe d’équivalence $\bmod n$ qui n’est autre que le reste de sa division euclidienne par $n$ ou encore $a^{r/2} \pm 1 \bmod n$.