blob: abae34819b9b25ce2c75f3abc0e79568c8c52a16 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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 })$
|
