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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
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
|
