# 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