Projets étudiants cryptographie et sécurité/Leclaire DeRoland Crypto Quantique

Cryptographie quantique

Auteurs : Juliana Leclaire, Céline de Roland

La cryptographie et la cryptanalyse dans le contexte de l'informatique quantique

Introduction

L'informatique quantique se base sur la superposition de plusieurs états quantiques pour améliorer les capacités de calculs. Ce domaine nous amène à un vrai problème dans le sécurité de l'internet. Car l'informatique quantique, avec ses capacités de calculs va pouvoir casser les algorithmes de chiffrement asymétriques qui sont présents dans le Web. Les chiffrements asymétriques sont utilisés dans le connexions SSL/TLS, les paiements en ligne, etc ... En partie pour ces raisons, il existe différents acteurs qui se penchent sur ce domaine. Notamment, la NSA, Google qui cherche à construire son propre ordinateur quantique. Dans cette page, nous allons nous demander en quoi l'informatique quantique peut changer le Web d'aujourd'hui et comment faire face à cette arrivée ?

Fonctionnement de l'informatique quantique

Qubit

C'est la plus petite unité de stockage de l'information. Etant donné deux états de base $ket{0}$ et $ket{1}$, un qubit non mesuré se trouve dans l'état $\alpha ket{0}+\beta ket{1}$, avec $|\alpha |^{2}+|\beta |^{2}=1$. Lorsqu'on mesure la valeur du qubit, on obtient soit $ket{0}$ soit $ket{1}$. Si j'ai bien compris (PAS SUR), $|\alpha |^{2}$ est la probabilité que la mesure de la valeur du qubit donne $ket{0}$ et $|\beta |^{2}$ est la probabilité que la mesure de la valeur du qubit donne $ket{1}$.

Théorème de non clonage

Ce théorème, découvert en 1982 par Wootters, Zurek, et Dieks, consiste à dire qu'il est impossible de recopier un qubit à l'identique. La démonstration (par l'absurde) repose sur le fait que pouvoir mettre le qubit B dans le même état que le qubit A implique que le qubit B soit déjà dans le même état que le qubit A. On en déduit qu'il est impossible de faire une opération de type copier/coller en informatique quantique.

Téléportation quantique

La téléportation quantique consiste à transférer l'état du qubit A dans le qubit B. Il s'agit donc cette fois d'une opération de couper/coller. L'intrication quantique se produit lorsque deux qubits sont dépendants l'un de l'autre même s'ils sont éloignés l'un de l'autre. Dans cet état, si on mesure l'un des deux, alors la mesure du deuxième est déterminée. Sans entrer dans la théorie physique sous jacente, nous pouvons dire qu'un canal EPR permet de réaliser cette opération de couper/coller en transmettant une information entre deux ordinateurs quantiques.

Chiffrement à clé publique face à l'informatique quantique

Mise en danger de la sécurité du Web

Les ordinateurs quantiques présentent une rapidité de calculs extrèmement plus rapide que les ordinateurs à base de sillicium. Ces ordinateurs auraient aucune difficulté pour casser les codes de sécurité actuels reposant principalement sur un chiffrement à clé publique. Par définition le chiffrement à clé publique utilise une clé publique pour le chiffrement et une clé privée pour le décodage en se basant sur des grands nombres. Cependant ces grands nombres peuvent être vite retrouvés par des ordinateurs quantiques.

Exemple de chiffrement asymétrique: RSA

Ce chiffrement est couramment utilisé dans la sécurité du Web. RSA repose sur la génération de grands nombres premiers, d'un chiffrement avec une clé publique et d'un déchiffrement avec une clé privée.

• Initialisation :
  • module $N$ (n bits > 2048 de nos jours)
  • $p, q$ : nombres premiers de même taille
  • $N = p * q$
  • $\phi(N) = (p-1) * (q - 1)$
  • $e = pgcd(e, \phi(N)) = 1$
  • Choisir $d$ tel que $ed \cong 1 [\phi(N)]$ et donc $d$ est l'inverse modulaire de $e$ avec $d = e^-1 [\phi(N)]$
  • $pk(n, e), sk(d, p, q)$
• Chiffrement : $c = m^e [N]$
• Déchiffrement : $m = c^d [N]$

La sécurité de RSA repose sur la difficulté à factoriser des grands nombres en nombres premiers. En effet avec $(N, e)$ il faudrait pouvoir retrouver $(d, p, q)$ où $N = p * q$ correspondant à un cassage total. D'après le théorème de factorisation unique tout entier $n \ge 2$ admet une factorisation unique en produit de puissances de nombres entiers. Des algorithmes de factorisation ont été trouvés pour différentes tailles de module $N$ mais pour pallier à ces attaques on augmente la longueur du module. De nos jours pour sécuriser le chiffrement il faut utiliser des modules strictement supérieur à 2048 bits. Cependant avec l'informatique quantique il ne suffira plus d'augmenter la taille du module car la puissance de calcul permettra de casser le chiffrement, peu importe la taille du module.

Exemple de cryptanalyse de RSA avec un ordinateur quantique : algorithme de Peter Shor

$\mathcal{K} = (N,A,P,Q,E)$ avec $N=143$ et $E$ publiques. Le principe utilisé pour factoriser $N$ en un produit $PQ$ est le suivant :

• On vérifie d'abord les cas triviaux :
  • Si $N$ est pair alors $P=2$ et $Q=\frac{N}{2}$
  • Si $N$ est premier alors $P=1$ et $Q=N$
  • Si $N$ est le carré d'un nombre premier $p$ alors $P=p$ et $Q=p$
• On choisit un nombre premier aléatoire $x$.
• Si $x$ n'est pas premier avec $N$, alors $P=x$ et $Q=N/P$. C'est terminé.
• Sinon on cherche (grâce à un ordinateur quantique) la période $r$ de la fonction $f(t) = x^t [N]$. On aura donc $x^r \equiv x^0 \equiv 1 [N]$. (la fonction $f$ est nécessairement périodique car on travaille dans le groupe multiplicatif fini $\mathbb{Z}/N \mathbb{Z}$)
  • Cette recherche de période est une opération difficile pour un ordinateur classique. Il faut en effet calculer les différentes valeurs modulo $N$ de $x^t$ jusqu'à trouver 1.
  • Pour un ordinateur quantique, cette opération est faisable en temps polynomial grâce au principe de superposition quantique. L'idée est de calculer toutes les valeurs de $f(t)$ en même temps et d'extraire ensuite le résultat attendu. Actuellement, des chercheurs ont réussi à créer un prototype capable de factoriser $N=15$ avec l'algorithme de Shor.
• Si $r$ est impair on recommence avec un autre nombre $x$ aléatoire (cela arrive avec une probabilité de $\frac{1}{2}$.
• Si $pqcd(x^{\frac{r}{2}}+1,N) = 1$ alors on recommence avec un autre nombre $x$ aléatoire (On admet que la probabilité d'être dans ce cas est inférieure à $\frac{1}{2}$).
• $N$ divise $x^r - 1 = (x^{\frac{r}{2}}+1)\times(x^{\frac{r}{2}}-1) $
• donc $P = pgcd(x^{\frac{r}{2}}+1,N)$ et $Q = pgcd(x^{\frac{r}{2}}-1,N)$ sont les deux diviseurs non triviaux de $N$
• $A$ n'est pas un grand nombre, on peut donc ensuite le trouver par force brute.\\

Exemple : $N=15$

• Je choisis $x=7$
• En calculant successivement les valeurs de $f$ on trouve $7^{4} \equiv 1 [15]$.
• $r=4$ est pair
• $pgcd(x^{\frac{r}{2}}+1,15) = 5$. Donc $P = 5$
• $Q = pgcd(x^{\frac{r}{2}}-1,15) = 3$