init: initial commit

1 files changed, 132 insertions, 0 deletions

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