# 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 })$