diff options
Diffstat (limited to 'CHIFR')
| -rw-r--r-- | CHIFR/Cours/Chiffrement post-quantique.md | 54 |
1 files changed, 54 insertions, 0 deletions
diff --git a/CHIFR/Cours/Chiffrement post-quantique.md b/CHIFR/Cours/Chiffrement post-quantique.md new file mode 100644 index 0000000..8984255 --- /dev/null +++ b/CHIFR/Cours/Chiffrement post-quantique.md @@ -0,0 +1,54 @@ +# Les algos jusqu'ici + +| Algorithme | Problème | +| ----------- | -------------------------------------------------------------------- | +| RSA | Factorisation des entiers | +| El Gamal | Logarithme discret | +| McEliece | Algorithme de décodage compliqué | +| Kyber, NTRU | Vecteur le plus proche/court, problème 'module learning with errors' | + +## module LWE: module learning with errors +ajout d'erreurs et d'un modulo $\rightarrow$ post-quantique + +| Algorithme | Modèle | Message | +| ------------------- | ------ | --------------------- | +| RSA | Z/nZ | entier entre 0 et n-1 | +| El Gamal classique | | | +| El Gamal elliptique | | | +| McEliece | | | +| Kyber, NTRU | | | + +# Kyber +Calculs dans $R_{p,n} = \mathbb{Z}/p\mathbb{Z}[X]/(X^n+1)$, messages **m** sont des polynômes, avec des coefs 0 ou 1 +## Anneau quotient $\mathbb{Z}/p\mathbb{Z}[X]/(X^n+1)$ +Soit $a \in R_{p,n}$, +$a = a_{n-1}X^{n-1}+\dots+a_{2}X^2 + a_{1}X + a_{0}, a_{i} \in \mathbb{Z}/p \mathbb{Z}$ +Si $b \in R_{p,n}$ alors: +- $a+b$ se fait coeff par coeff dans $\mathbb{Z}/p \mathbb{Z}$. +- $a \cdot b$: On peut calculer $a\cdot b$ dans $\mathbb{Z}/p \mathbb{Z}[X]$ et prendre le reste dans la division par $X^n+1$ ou utiliser que $X^n+1=0$, donc $X^n=-1, X^{n+1} = -X$ +**Exemple**: +$$ +\begin{align} +(X^3+2X+1) \cdot (3X^3+4X^2+2) &= 2X^2 + 16X + 2X^3 + 0 \times 4X^3 + 4X + 3X^3 + 4X^2 + 2 \\ +&= X^2 + 3 +\end{align} +$$ +## Compression de $\mathbb{Z}/p \mathbb{Z}$ +$Compress(x) = \lceil \frac{x}{\frac{p}{2}} \rfloor mod 2$ +$Compress_{17}(x) = \lceil \frac{2x}{17} \rfloor mod 2$ + +# Le cryptosystème Kyber +Rappel LWE : $As + e = t$ +- KeyGen: + - On choisit des polynômes $a,s,e \in R_{p,n}$ tels que $s$ et $e$ on des petits coefficients + - On calcule $t= a\cdot s + e$ + - Clé publique pk = (a,t) et clé privée sk = s +- Encryption: + - Message m + - On choisit des polynomes $r,e_{1},e_{2} \in R_{p,n}$ à petits coeffs + - On calcule : + - $u = a \cdot r + e_1$ et $v = t \cdot r + e_2 + \lceil \frac{p}{2} \rfloor \cdot m$ + - $c = Enc(m,pk) = (u,v)$ +- Decryption: + - $m' = v - su$ + - $m = Compress(m')$ (sur chaque coefficient)
\ No newline at end of file |