1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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)
|
