FLE : en pratique, on en est où ? Il y a un algo dans Chrome (lequel ? sur quelle base ?), et dans les autres libs cryptos ? Où en est-on du test in the wild ?

Gabriel: Peut-être redéfinir ce dont parle la partie 3 **Algorithmes cryptographiques post-quantiques**
Il me semble que le concours NIST cherche des solutions d'algorithmes classiques, qui s'exécutent sur nos processeurs habituels.
Bref il y a:
- la crypto classique qu'on casse avec des algo classiques
- la crypto classique qu'on casse avec des algo quantiques comme Shor (ce dont vous parlez en partie 2)
- la crypto quantique qui elle, est garantie par des propriétés quantiques, et plus par des propriétés mathématiques
Bref, on peut peut-être ajouter une phrase d'explication pour préciser ce dont vous parlez, sinon c'est super

# Post-Quantum Cryptography
###### Module de CSC - Gaétan Falcand & Thibaut Bellanger

L'avènement d'internet a augmenté sensiblement la quantité de communications informatiques. Ceci a créé un besoin de sécurité face à des utilisateurs malveillants: la cryptographie.

## Le chiffrement aujourd'hui

Aujourd'hui, le chiffrement se base sur des principes mathématiques complexes, dont la résolution est trop longue pour un ordinateur classique actuel. Il existe 3 grands types de problèmes mathématiques :

### Cryptographie sur la factorisation d'entiers

Le problème mathématique de base de la cryptographie, celui qu'on retrouve dans tous les algorithmes est la factorisation d'entiers et plus particulièrement d'entiers premiers. L'idée est simple, prendre n'importe quel entier $n$ et pouvoir le factoriser en plusieurs entier $n_1, n_2$ avec $n_i<n$.

Un exemple de factorisation entière ci-dessous :


Beaucoup d'algorithmes fondateurs se servent de ce principe, on peut notamment citer RSA. Ce problème est utilisé car il est facile de multiplier des entiers entre eux pour créer la clé, il est toutefois beaucoup plus difficile de trouver la paire d'entier qui ont servi pour la factorisation, avec à ce jour aucun algorithme résolvant tous les entiers en un temps polynomial.

### Cryptographie sur le logarithme discret
Un autre problème utilisé en cryptographie est le logarithme discret. Le principe se base sur la génération de paires via le logarithme.
Pour illustrer :
Avec un groupe cyclique $\mathbb{Z}_7$ :
| $3⁰$ | $3¹$ | $3²$ | $3³$ | $3⁴$ | $3⁵$ |
| ---- | ---- | ---- | ---- | ---- | ---- |
| $1$ | $3$ | $2$ | $6$ | $4$ | $5$ |

Ici on a $3² = 9 \mod 7 = 2$

En logarithme discret de base 3:

| $x$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| --------- | --- | --- | --- | --- | --- | --- |
| $log_3 x$ | $0$ | $2$ | $1$ | $4$ | $5$ | $3$ |

Si l'on extrapole avec de plus grands groupes générateurs, on a des paires qui nous sont utiles dans la cryptographie. Ce qui nous intéresse ici est l'asymétrie, en effet si le calcul est simple pour chiffrer, il sera beaucoup plus difficile de déchiffrer.

### Cryptographie sur les courbes elliptiques
Les dernières générations de cryptographies se sont intéressées à la cryptographie via courbe elliptique discrète. Nous n'allons pas détailler précisement le principe, celui-ci étant particulièrement complexe mais l'idée derrière ce dernier est que celui qui veut déchiffrer la clé a une charge de travail bien plus élevée qu'avec la simple factorisation. Ce problème est donc au coeur des dernières avancées, étant utilisé par la NSA ou encore de grands fournisseurs de services internet comme Cloudflare.

## L'arrivée des ordinateurs quantiques

Mais depuis plusieurs années, l'avancée des ordinateurs quantiques pourrait remettre en question les fondations sur lesquels se reposent des algorithmes très utilisés comme RSA. En outre, un algorithme, basé sur l'utilisation d'ordinateurs quantiques suffisamment puissants, permettrait de résoudre les trois classes de problèmes précédentes : c'est l'algorithme de Shor.

### Algorithme de Shor
Inventé en 1994 par le mathématicien Peter Shor, il s'agit d'un algorithme de factorisation en nombres premiers, utilisant le principe des ordinateurs quantiques. L'avantage de cet algorithme est sa résolution en temps polynomial, là où un algorithme avec les ordinateurs actuels résout ce problème en temps sous-exponentiel.

### L'ordinateur quantique
Un ordinateur quantique se base sur des principes de la mécanique quantique (comme la superposition ou l'intrication). Ainsi, on ne parle plus de bits (valant 0 ou 1) mais de qubits, valant une proportion de 1 et de 0. On peut représenter cela schématiquement par $a| 0 ⟩ + b| 1 ⟩$, représentant 1 qubit (avec $|a|² + |b|² = 1$). Là ou les qubits prennent sens, c'est lorsque qu'on en utilise plusieurs. Avec 2 qubits, on a la représentation suivante $α| 00 ⟩ + β | 01 ⟩ + γ| 10 ⟩ + δ| 11 ⟩$ (avec $|α|² + |β|² + |γ|² + |δ|² = 1$). Avec 2 qubits, on peut donc représenter 4 états en parallèle, alors qu'un ordinateur classique ne pourrait en représenter qu'un seul des 4 à la fois.
L'utilisation d'un tel ordinateur se fait en faisant converger 1 qubit vers 1 ou 0 (soit une réponse déterministe), par exemple : Est-ce que le 18ème chiffre cette clé privée peut être un 5 (1 étant oui, 0 étant non).

## Algorithmes cryptographiques post-quantiques

Devant l'avancée de ces technologies, la communauté scientifique a décidé de mettre au point des algorithmes résistants au ordinateurs quantiques. Pour en étudier quelques-uns, nous allons nous pencher sur certains finalistes du 3ème round de la compétition organisée par le NIST, visant à la standardisation des algorithmes cryptographiques post-quantiques.
Nous étudierons 3 finalistes (2 pour du chiffrement et 1 pour de la signature), représentant chacun une famille d'algorithmes.

### Classic McEliece

Classic McEliece est un algorithme de la famille _code-based_ (ou codes correcteurs d'erreur). Ce dernier se base sur le rajout d'erreurs dans le message codé, rendant le code incompréhensible. Le moyen de le déchiffrer est de posséder une matrice génératrice (la clé privée), permettant de corriger les erreurs. La clé publique (utilisée pour chiffrer) est alors une version "randomisée" de la clé privée. Une famille de codes efficaces avec une difficulté suffisante est la famille des codes de Goppa. Classic McEliece utilise cette famille.
Les gros avantages de cet algorithme sont les tailles des textes chiffrés. Classic McEliece possède les textes chiffrés les plus courts de tout le 2ème et 3ème round de la compétition. Le gros point noir est la taille de la clé publique. En effet, cette dernière à une taille de 1MB pour le niveau de sécurité maximal. Cette taille empêche toute utilisation dans le cas d'applications nécessitant de nouvelles clés publiques à chaque utilisation.

### Saber

Saber est un algorithme de la famille _lattice-based_ (basée sur un réseau de points euclidiens). Cette famille de cryptographie se base sur un espace vectoriel afin de caractèriser ses points. Le principe de Saber est que les modulo de ses entiers sont des puissances de 2. Ceci permet de réduire la taille de la clé publique ainsi que celle du texte chiffré et de pouvoir faire des opérations sur les bits du modulo.

### Rainbow

Rainbow est un algorithme de la famille des polynômes multivariés. Ces derniers reposent sur la difficulté à résoudre des systèmes polinomiaux à plusieurs variables. Rainbow se base sur le principe de _oil and vinegar signature scheme_ de Jacques Patarin.
Les gros avantages sont la petite taille de la signature et la rapidité de signature et de vérification. Cependant, les clés sont relativements grosses. Il est possible de les compresser, mais au coût de la rapidité de l'algorithme. Malheureusement, l'analyse de sécurité de Rainbow n'est pas considérée comme stable pour le moment.

## Conclusion

Si à l'heure actuelle les ordinateurs quantiques ou traditionnels ne sont pas capables de résoudre et donc briser les algorithmes de clés publiques utilisés à grande échelle, il ne s'agit pas comme on l'a vu de problèmes de complexité mathématiques mais bien de puissance de calcul. En effet, n'importe quel ordinateur pourrait déchiffrer RSA, si on lui laisse le temps (ce qui se compte en plusieurs milliers d'années). Cependant, la menace posée par les ordinateurs quantiques est que la puissance supposée de ceux-ci pourra de manière rapide et facile résoudre les problèmes mathématiques sur lesquels se repose la cryptographie actuelle. Il est donc essentiel de s'y préparer et donc de développer les algorithmes qui sauront répondre aux ordinateurs quantiques (d'où le terme _post-quantique_).
Une nuance que l'on peut apporter est que si cette partie de la cryptographie est menacée par les ordinateurs quantiques, la cryptographie symétrique ainsi que les algorithmes de hash sont eux beaucoup moins inquiétés car il leur suffit d'augmenter la taille pour eviter d'être brisés.

## Sources

+ [A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography](https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/)
+ [Post-Quantum Cryptography: Current state and quantum mitigation](https://www.enisa.europa.eu/publications/post-quantum-cryptography-current-state-and-quantum-mitigation)
+ [Integer Factorization](https://en.wikipedia.org/wiki/Integer_factorization)
+ [Post-Quantum Cryptography](https://en.wikipedia.org/wiki/Post-quantum_cryptography)
+ [Discrete logarithm](https://en.wikipedia.org/wiki/Discrete_logarithm)
+ [Elliptic-curve cryptography](https://en.wikipedia.org/wiki/Discrete_logarithm)
+ [Shor's algorithm](https://en.wikipedia.org/wiki/Shor%27s_algorithm)
+ [Calculateur quantique](https://fr.wikipedia.org/wiki/Calculateur_quantique#Principe_de_fonctionnement_des_calculateurs_quantiques)
+ [SABER: LWR-based KEM](https://www.esat.kuleuven.be/cosic/pqcrypto/saber/)
+ [Lattice-based cryptography](https://en.wikipedia.org/wiki/Lattice-based_cryptography)