Les calculs quantiques dans la cryptologie

Auteurs : Estopinan Raphaël et Rafik Abdellatif

La cryptologie est un art très ancien né dans l'antiquité mais c'est que depuis les années 1970 et l'arrivée du numérique que des recherches ont été effectuées pour pouvoir protéger les donner et ainsi chiffrer ces dernières. Ainsi plusieurs algorithmes ont été conçus et sont pour la plupart suffisamment performants pour que un "hacker" ne puisse récupérer les données circulant sur les réseaux. Cependant, nous verrons que, avec l'arrivée des ordinateurs quantiques et leur puissance de calcul incomparable avec les ordinateurs classiques, la plupart de ces algorithmes sont devenus inefficaces. Nous verrons ainsi dans ce cours comment la méthode de chiffrement RSA peut être facilement déjouée avec les algorithmes créés pour les ordinateurs quantiques et en particulier l'algorithme de Shor.

Le calcul quantique, son histoire ...

C'est en 1982 que le physicien et chercheur Richard Feynman a eu l'idée de créer des machines basées sur les lois de la mécanique quantique en remplaçant celles de la physique classique.

En 1985, David Deutsch reprenant les recherches de M. Feynman développa une machine quantique de Turing qui exposa toute la puissance de calcul des machines quantiques et expliqua que les portes quantiques pourraient fonctionner de la même manière que les portes logiques binaires des ordinateurs classiques.

Enfin, c'est en 2009 que l'Université de Yale créa le premier processeur quantique qui comportaient deux qubits composés chacun d'un milliard d’atomes d’aluminium.

Représentation des données : Qubit

Etats de base :

Nos ordinateurs classiques sont basés sur des transistors qui travaillent sur des données binaires (0 ou 1) qu'on appelle bit. L'ordinateur quantique, lui, est une machine basée sur les lois de la mécanique quantiques, c'est à dire le comportement des particules au niveau subatomique.

Ainsi, la représentation des données pour l’ordinateur quantique est appelé le Qubit. Le Qubit est composé de deux états (niveaux d'énergie) de bases : l'état fondamentale ∣0〉et l'état excité ∣1〉(prononcés Ket 0 et Ket 1). Ces deux états sont représenter sur l'atome par le déplacement d'un electron du spin 0 au spin 1 causé par un rayonnement (cf schéma ci-dessous).

Etat de superposition

En plus des deux états de bases, le qubit dispose d'un troisième état appelé superposition. Cet état est caractérisé par : les deux états de bases simultanément (en même temps).
Ainsi nous pouvons représenter cet état par l'équation suivante : $|\Psi >=\alpha |0>+\beta |1>$ avec ${\sqrt {|\alpha |^{2}+|\beta |^{2}}}=1$.
$\alpha$ et $\beta$ sont des nombres complexes représentant la probabilité respective d'être dans l'état |0> ou dans l'état |1>.

Exemple :
Nous savons que un registre de n Qubit peut représenter les nombres de 0 à n²-1 simultanément. Donc pour un registre de 3 Qubits nous auront 8 états possibles par Qubit.
Une superposition également pondérée de tout les états possibles serait donc désignée par l'équation : $|\Psi >={\frac {1}{\sqrt {8}}}|000>+{\frac {1}{\sqrt {8}}}|001>+...+{\frac {1}{\sqrt {8}}}|111>$.

Intrication quantique

L'Intrication quantique est un phénomène quantique dans lequel deux particules (ou groupe de particules) forment un système lié et présentent des états quantiques dépendant l'un de l'autre et cela quelque soit la distance qui les sépare. En d'autres termes, si l'un des atomes est affecté alors l'atome lié avec lui sera lui aussi affecté.

Chiffrement RSA

Rappel algorithme

L'algorithme de Shor étant très efficace pour déchiffrer l'algorithme RSA, nous allons tout d'abord faire un rappel sur le chiffrement RSA :

Par rapport au schéma ci-dessus nous avons :

• le module de chiffrement $n$ qui est le produit de deux nombres premiers $p$ et $q$.
• $ab\equiv 1(mod(p-1)(q-1)$.
• $n$ et $b$ sont la partie publique de la clé.
• $p$,$q$ et $a$ sont la partie privée de la clé.

Attaques RSA

Plusieurs attaques pour RSA existent mais ne fonctionnent qu'avec des conditions particulières ou prennent trop de temps :

• L'attaque de Wiener qui nécessite d'avoir $a<{\frac {n{\frac {1}{4}}}{3}}$ et $q<p<2q$
• L'attaque de Hastad qui ne fonctionne qu'avec l'exposant b petit
• L'attaque par chronométrage (timing attacks)
• L'algorithme de Pollard
• L’algorithme de Dixon

Un autre type d'attaque serait l'attaque par "force brute". Déchiffrer RSA de cette manière nécessite la factorisation du nombre $n$ avec le produit initial des nombres $p$ et $q$. Or, avec les algorithmes classiques le temps que prend cette factorisation croit de façon exponentielle avec la longueur de la clé.

Puissance des calculateurs quantiques

Pour factoriser un nombre N de 300 chiffres, le meilleur algorithme effectue environ $10^{26}$ opérations. Or, un ordinateur classique a ses performances de l'ordre de 100 teraflops ($10^{14}$ opérations). Il faudra donc environ $10^{12}$ pour factoriser le nombre N ce qui correspond à 30 000 ans !. Or, avec l'algorithme de Shor et un calculateur quantique, il suffira de 10 secondes pour factoriser ce nombre.

L'algorithme de Shor

L'algorithme de Shor, nommé en l'honneur de son créateur Peter Shor, montre en principe qu'un ordinateur quantique est capable de factoriser de très grands nombres entiers en temps polynomiale : $O((log(N))^{3})$ et avec un espace faible : $O(log(N))$.
Cet algorithme dépend de 3 points :

• l'arithmétique modulaire
• le parallélisme quantique
• la transformée de Fourier quantique

Périodicité dans l'algorithme

Pour l'algorithme de Shor nous aurons besoin d'utiliser la fonction $F(a)=x^{a}mod(n)$ qui est une fonction périodique. Exemple
Prenons n = 15 et x = 7. Avec la fonction ci-dessus nous obtenons :
$7^{0}mod(15)=1$
$7^{1}mod(15)=7$
$7^{2}mod(15)=4$
$7^{3}mod(15)=13$
$7^{4}mod(15)=1$

Les différentes étapes de l'algorithme de Shor

Rappelons que cet algorithme est utilisé pour factoriser un grand entier N. Nous choisirons n = 15 à titre d'exemple.

Analyse

1. Prendre un entier $q=2^{L}$ tel que $N^{2}<q<2N^{2}$
2. Prendre un entier aléatoire $x<N$ tel que $PGCD(x,N)=1$
3. Création de deux registres quantiques (intriqués)

• Input register : qubits représentant q-1
  
• Output register : qubit représentant N-1
  

4. Chargement du registre d'entrée avec une superposition de pondération égale de tous les entiers de 0 à q-1
5. Chargement du registre de sortie avec des zéros.
A ce moment, l'état général du système est : ${\frac {1}{\sqrt {q}}}\sum _{a=0}^{q-1}|In,Out>$
Remarque: La virgule indique ici que les registres sont intriqués.

Arithmétique modulaire

6. Appliquez la transformation $F(a)=x^{a}mod(n)$ à chaque nombre du registre d'entrée et enregistrer le résultat de chaque calculs dans le registre de sortie.

Remarque: Nous utilisons ici des nombres décimaux uniquement pour des raisons de simplicité

Réduction en superposition

7. Nous pouvons à présent prendre une mesure sur le registre de sortie. Cela réduira la superposition pour ne représenter qu'un des résultats de la transformation. Appelons cette valeur c.
Ainsi, notre registre de sortie se réduira pour représenter l'un des éléments suivants : |1>, |4>, |7> ou|13>. Nous choisirons par exemple |1>.

Intrication quantique

Puisque les deux registres sont intriqués, la mesure du registre de sortie aura pour effet de réduire partiellement le registre d'entrée en une superposition égale à chaque état compris entre 0 et q-1 ayant donné Out (la valeur du registre de sortie réduit). Ainsi comme le registre est réduit à |1> le registre d'entrée sera lui réduit partiellement à : ${\frac {1}{\sqrt {64}}}|0>+{\frac {1}{\sqrt {64}}}|4>+{\frac {1}{\sqrt {64}}}|8>+{\frac {1}{\sqrt {64}}}|12>+...$
La probabilité dans ce cas est de 64 étant donné que le registre est en superposition égale (0,4,8,12,..,252).

Transformée de Fourier Quantique

8. Nous appliquons maintenant la transformation de Fourier Quantique sur le registre d'entrée partiellement réduit. La transformée de Fourier a pour effet de prendre un état ∣a〉 et de le transformer en un état donné par : $|In>={\frac {1}{\sqrt {q}}}\sum _{k=0}^{q-1}|Out>*e^{2\pi i{\frac {aOut}{q}}}$
Donc, l'état final du registre d'entrée après la transformation de Fourier Quantique est : ${\frac {1}{\sqrt {64}}}\sum _{a\in A}|In>,|1>$
Remarque : A est l'ensemble de toutes les valeurs où 7a mod 15 a donné ∣1〉. Dans notre cas, A = {0, 4, 8,…, 252}
Ainsi on aura comme résultat final (avec la valeur du registre d'entrée |In> détaillée au dessus) : ${\frac {1}{\sqrt {64}}}\sum _{a\in A}({\frac {1}{\sqrt {q}}}\sum _{k=0}^{q-1}|Out>*e^{2\pi i{\frac {aOut}{q}}}),|1>$

La transformée de Fourier Quantique atteindra essentiellement les amplitudes de probabilité avec des multiples de q/4 (256/4 = 64 pour notre cas) ce qui donnera comme possibilités : ∣0〉, ∣64〉, ∣128〉, ∣192〉, …
Nous n’avons donc plus une superposition égale d’états, les amplitudes de probabilité des états ci-dessus sont maintenant supérieures à celles des autres états de notre registre. Nous mesurons le registre et celui-ci s’effondrera avec une probabilité élevée à l’un de ces multiples de 64, appelons cette valeur p.
Avec notre connaissance de q et p, il existe des méthodes de calcul de la période (une méthode est l’expansion en fraction continue du rapport entre q et p.)

9. Les facteurs de N peuvent être déterminés en prenant le plus grand commun diviseur de N en ce qui concerne :
${\begin{Bmatrix}a_{1}&b_{1}\\a_{2}&b_{2}\end{Bmatrix}}$