From 66c3bbfa94d8a41e58adf154be25e6d86fee8e30 Mon Sep 17 00:00:00 2001 From: "martial.simon" Date: Sun, 13 Apr 2025 19:54:19 +0200 Subject: init: initial commit --- CHIFR/Cours/RMD1.md | 88 +++++++++++++++++++++++++++++++++++ CHIFR/Cours/RMD2.md | 132 ++++++++++++++++++++++++++++++++++++++++++++++++++++ CHIFR/Cours/RMD3.md | 41 ++++++++++++++++ CHIFR/Cours/RMD4.md | 39 ++++++++++++++++ 4 files changed, 300 insertions(+) create mode 100755 CHIFR/Cours/RMD1.md create mode 100755 CHIFR/Cours/RMD2.md create mode 100755 CHIFR/Cours/RMD3.md create mode 100755 CHIFR/Cours/RMD4.md (limited to 'CHIFR/Cours') diff --git a/CHIFR/Cours/RMD1.md b/CHIFR/Cours/RMD1.md new file mode 100755 index 0000000..7a02850 --- /dev/null +++ b/CHIFR/Cours/RMD1.md @@ -0,0 +1,88 @@ +# Intro + +- Ch 1 Intro +- Ch 2 Cryptographie symétrique +- Ch 3 & 4 Cryptographie asymétrique + - Diffie-Hellman, RSA, El Gamal + - logarithme discret + - chiffrement et courbes elliptiques + - protocoles hybrides et TLS + - Post-quantique + +# Chapitre 1 + +```handwritten-ink +{ + "versionAtEmbed": "0.3.4", + "filepath": "Ink/Writing/2025.3.5 - 9.26am.writing" +} +``` + - Confidentialité + - Authentification des données + - Intégrité (Checksum) + - Non répudiation (signature électronique) + + **Crypto is everywhere** +## Encryption symétrique + +- Indice de coïncidence +- Principes de Kerckhoffs : + - _Le système doit être matériellement, sinon mathématiquement indéchiffrable._ + - _Il faut qu'il n'exige pas le secret, et qu'il puisse sans inconvénient tomber entre les mains de l'ennemi._ + - _La clef doit pouvoir être communiquée [...]_ +- Enigma (Regarder The Imitation Game) +- **I**nformation **T**echnically **S**ecure +- Chiffrement _parfait_ : Vernam + - Pb 1 : usage unique de la clé + - Pb 2 : clé aussi longue que le message + - Pb 3 : chiffrement optimal dans sa catégorie + +### Chiffrement par blocs + +Blocs de petite taille (_n_, clé de taille _k_) +Utilisés comme **mode d'opération** +- Electronic Codebook (ECB) mode **do not use** (Vernam avec clé trop courte un peu); +- Cipher-Block Chaining (CBC) mode; +- Output Feedback (OFB) mode; +- Counter (CTR) mode; +- ... +#### Block-cypher +#### Two main techniques + +- **Feistel networks** +- **SPN** +#### Structure + +Key scheduler -> blocks (_k_i) + +Première version (IBM) basée sur le **chiffre Lucifer** +**NSA** impliquée (shady) +Standard fédéral aux U.S. novembre 1976 + +____ +#### Feistel diagram + +![[{7AB28281-E4F9-4DAA-860B-973E65165911}.png]] + +#### Origines AES + +- Remplacement de DES +- Triple-DES lent +- US NIST appel en 1997 +- **Rijndael** sélectionné en octobre 2000 +- AES = **SPN** (Substitution-Permutation Network) + +#### Substitution-Permutation Network + +- **Confusion** & **diffusion** +- Substitution et permutation des blocs +- Assez de tours -> chaque bit d'entrée est diffusé dans tout le réseau +- Processus : + - XOR le bloc avec la clé + - SubBytes : + - Boîte-S définie sur $\mathbb{F}_{256}$ + - ShiftRows + - Shift des lignes (0 puis 1 puis 2 shifts...) + - (diffuse sur les lignes) + - MixColumns + - Produit matriciel (diffuse sur les colonnes) \ No newline at end of file diff --git a/CHIFR/Cours/RMD2.md b/CHIFR/Cours/RMD2.md new file mode 100755 index 0000000..6e1b170 --- /dev/null +++ b/CHIFR/Cours/RMD2.md @@ -0,0 +1,132 @@ +# Le problème du logarithme discret +$\rightarrow$ échange de clés Diffie-Hellman & ElGamal + +## Chiffrement à clé publique + +Pas de lien entre $pk$ et $sk$ (et surtout $pk \neq sk$) +Si on chiffre avec la clé privée, on peut tout déchiffrer avec la clé publique : **signature** + ### Flashback STA +Choisir $p$ un nombre premier et $g$ un générateur de $\mathbb{Z}/p\mathbb{Z}$ + +| Alice | Bob | +| -------------------------- | -------------------------- | +| Choisir $a < p$ | Choisir $b < p$ | +| Envoyer $K_a = g^a \mod p$ | Envoyer $K_b = g^b \mod p$ | +| K = $(g^b)^a$ | K = $(g^a)^b$ | +Clé privée : $K = g^{ab} \mod p = g^{ba} \mod p$ +## DLP - Définition + +Soit $g \in (\mathbb{Z}/p\mathbb{Z})^x$ un générateur et $b \in (\mathbb{Z}/p\mathbb{Z})^x$. Le problème du logarithme discret consiste à résoudre l'équation $g^x = b$ avec $x < p$ donc résoudre $$g^x \equiv b \; mod\; p.$$ +Alors l'entier $x = \log_g(b)$ s'appelle le **logarithme discret de $b$ de base $g$**. + +- $\log_g(b_{1}b_{2}) = \log_g(b_1) + \log_g(b_2)$ +- $\log_{g}(b^n) = n\log_{g}(b)$ +## DLP - Attaques + +**Bruteforce** : contré avec un grand nombre premier +Complexité : $\Theta(p)$ +### Algo de Shank +Algorithme de collision : +1. On choisit $n > \sqrt{p}$ +2. Créer les listes : + 1. (baby-steps): $1, g, g^2, ..., g^{n-1}$ + 2. (giant-steps) : $b, bg^{-n}, bg^{-2n}, ...,$ +3. Trouver une collision (même élément dans les 2 listes) : $g^r = bg^{-qn}$ +4. Alors $g^{qn + r} = b$ et $x = qn + r$ + +Ex avec $5^x \equiv 2 \mod 7$: +1. n = 3 +2. $[1, 5, 25]$ et $[2,\, 2*5^{-3},\, 2*5^{-6}] = [2,\,]$ +3. +#### Conclusion sur Shank +Complexité en $\Theta(\sqrt{p}\log(p))$ +# Le problème de la factorisation des entiers +$\rightarrow$ RSA + +## RSA + +**Création de clés** : +1. Choisir premiers $p$ et $q$, calculer $n = pq$ +2. Calculer $\phi(n) = (p - 1)(q-1)$ +3. Choisir $e < \phi(n)$ tel que $\gcd(e,\phi(n)) = 1$ +4. Calculer $d$ tel que $de \equiv 1\; mod\; \phi(n)$ +5. Clé privée : $sk = d$ +6. Clé publique : $pk = (n,e)$ + +Chiffrement par **Alice** : +1. Calculer $c = Enc(pk,m) = m^e \; mod \; n$ +2. Envoyer $c$ + +Déchiffrement par **Bob** : +1. Calculer $Dec(sk,c) = c^d \; mod \; n$ +2. Le message d'origine est $m = c^d$ + +- $n =pq$ avec $p$ et $q$ premiers +- $e \times d \equiv 1 \; mod \; (p-1)(q-1)$ +- Chiffrement $c = m^e$ +- Déchiffrement $m = c^d$ +- $(m^e)^d = (m^d)^e = m$ + +### RSA Scolaire + +- Un même message **m** est toujours chiffré avec le même $c$ (déterministe) +- L'algo est homomorphique : $Enc(m_1, pk) \times Enc(m_2, pk) = Enc(m_1m_2, pk)$ +### Bonnes pratiques + +- grands p et q et pas très proches +- e ne doit pas être très petit (souvent $e = 2^{16} + 1 = 65537$) +- d ne doit pas être très petit + +### $\phi(n) = (p-1)(q-1)$ doit rester secret + +En effet : +$$ +(p-1)(q - 1) = pq -p -q + 1 = n - (p + q) + 1 +$$ +Puisque $n$ est connu on peut calculer $p + q$ et résoudre +$$ +X^2 - (p+q)X + pq = 0 +$$ +Comme +$$ +(X - p)(X - q) = X_{2} - (p + q)X + pq +$$ +les solutions de l'équation sont eactement $p$ et $q$. + +### Algorithme de Fermat + +$\rightarrow$ Choisir p et q suffisamment éloignés +```pcode +Input : n +Output : p, q +x <- floor(sqrt(n)) +z <- x² - n +while not issquare(z) do + x <- x + 1 + z <- x² - n +end while +y <- sqrt(z) +p <- x + y +q <- x - y +``` +### Algorithme $\rho$ de Pollard's + +```pcode +Input : n +Output : $\rho$ +x <- randomint(n) +y <- x +f(x) <- x² + 1 +d <- 1 +while d = 1 do + x <- f(x) + y <- f(f(y)) + d <- gcd(x - y, n) +end while +if d = n then Start again +end if +``` +Ex avec $x_0 = y_0 = 2, f(x) = x^2 + 1$ +x = 26 +y = 458 530 +d = 1 \ No newline at end of file diff --git a/CHIFR/Cours/RMD3.md b/CHIFR/Cours/RMD3.md new file mode 100755 index 0000000..abae348 --- /dev/null +++ b/CHIFR/Cours/RMD3.md @@ -0,0 +1,41 @@ +# Courbes elliptiques +**Une courbe elliptique $\mathcal{C}$ est l'ensemble des points $(x,y)$ avec $(x,y) \in \mathbb{K},\, \mathbb{K}$ un corps, qui vérifient :** +$$ +y^2 = x^3 + ax + b +$$ +**avec $4a^3 + 27b^2 \neq 0$** + +Si $E:y^2=x^3+ax+b$ est une courbe définie sur un corps $\mathbb{K}$ on pose +$$ +E(\mathbb{K}) = \{ (x,y) | y^2 = x^3 + ax + b\} \cup \{ \mathcal{O} \} +$$ +où $\mathcal{O}$ est le point "à l'infini", parfois noté $\infty$. +## Sur $\mathbb{F}_p$ +Ici, $\mathbb{K} = \mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ avec $p > 3$. +Un point est donc sur la courbe si $y^2=x^3+ax+b\; mod\; p$ + +## Formules +![[{596A56BB-4EC1-4A4E-9D79-F957C8D05BB0}.png]] + +## Théorème de Hasse +$$ +p+1 - 2\sqrt{ p } \leq Card(E(\mathbb{F}_{p})) \leq p+1+2\sqrt{ p } +$$ + +## Utilisations +- Signature iMessage (Apple) +- Authentification SSL, TLS, Bitcoin +- IoT (Moins couteux en ressources) +- Systèmes de paiment + +## ElGamal +### Problèmes + +## Logarithme discret +$g^x =b \,mod\, p$ +### Sur une courbe elliptique +Revient à résoudre $xQ = P$ où P,Q sont des points connus dans $E(\mathbb{F}_{p})$ +#### Attaques +- Bruteforce : $\mathcal{O}(p)$ +- Shank : $\mathcal{O}(\sqrt{ p })$ +- $\rho$ de Pollard : $\mathcal{O}(\sqrt{ p })$ diff --git a/CHIFR/Cours/RMD4.md b/CHIFR/Cours/RMD4.md new file mode 100755 index 0000000..29e0ff6 --- /dev/null +++ b/CHIFR/Cours/RMD4.md @@ -0,0 +1,39 @@ +# Codes correcteurs +Redondance = besoin de beaucoup d'espace + +## Mots binaires +Un **mot binaire** de taille $k$ eset un élément de $\mathbb{F}_2^k$ c'est à dire $m = (m_{1},m_{2},\dots,m_{k})$ + +## Distance de Hamming +Nombre de différences entre deux mots binaires + +## Matrice génératrice [m,n] +$M_{m\times n}$ +$\longrightarrow$ ajout d'une colonne de $(1,1,\dots,1)$ pour la distance ($+ = \oplus$) + +## Poids d'un code +Nombre de coordonnées non-nulles $\omega (c) = Card(i | c = (c_{1},c_{2},\dots,c_{n}), c \neq 0)$ + +## Forme systématique de $G$ +Si on peut écrire $G$ comme $G_{k,n} = (I_{k}|A_{k,n-k})$, on dit que le code est **systématique**. +$\implies$ on retrouve le mot en début de code suivi de sa redondance + +## Matrice de parité +On prend $G = (I_{k}|A_{k,n-k})$, soit $H$ sa **matrice de vérification de parité** de taille $(n-k)\times n$, $H = (-A^T|I_{n-k})$ +Dans tous les cas $GH^T=0$ + +## A retenir +- Le code est donc l'**image** de $G$ et le **noyau** de $H$ +- $x \in \mathbb{F}_{2}^n$ est un code $\Leftrightarrow Hx^T = 0$ +- La matrice $H$ permet de déterminer $d : d - 1$ colonnes sont toujours linéairement indépendantes, $d$ colonnes liées. + +# Correction des codes +- message : m +- code : c +- bruit : code modifié $y = c + e$. L'erreur peut être exprimée avec $e \in \mathbb{F}_2^n$ +- décodage : retrouver c à partir de y. + +![[Pasted image 20250408100703.png]] + +## Syndrôme +Soit $y \in \mathbb{F}_2^n$ le vecteur reçu. On appelle **syndrome** de $y$ $s(y) = Hy^T \in \mathbb{F}_{2}^{n-k}$ -- cgit v1.2.3