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

Pour pouvoir parler de l'algorithme de Shor qui est très efficace pour déchiffrer RSA, voici un petit rappel sur le fonctionnement du 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é.