# 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)