From 147394e7692bdf77f041e4b9bd9ff0daac1ee9c7 Mon Sep 17 00:00:00 2001
From: marcellus <msimon_fr@hotmail.com>
Date: Fri, 6 Jun 2025 12:58:05 +0200
Subject: notes: 2025-06-06 12:58:05 from w11

---
 CHIFR/Cours/Chiffrement post-quantique.md | 54 +++++++++++++++++++++++++++++++
 1 file changed, 54 insertions(+)
 create mode 100644 CHIFR/Cours/Chiffrement post-quantique.md

(limited to 'CHIFR')

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
-- 
cgit v1.2.3