diff options
Diffstat (limited to 'CHIFR/TD')
| -rwxr-xr-x | CHIFR/TD/TD1.md | 174 | ||||
| -rwxr-xr-x | CHIFR/TD/TD2.md | 61 | ||||
| -rwxr-xr-x | CHIFR/TD/TD3 - Courbes elliptiques.md | 84 |
3 files changed, 319 insertions, 0 deletions
diff --git a/CHIFR/TD/TD1.md b/CHIFR/TD/TD1.md new file mode 100755 index 0000000..aa1e67b --- /dev/null +++ b/CHIFR/TD/TD1.md @@ -0,0 +1,174 @@ +# 1. Chiffrement historique +## 1-1/ César +### a. +25 +### b. +Non, trop simple à bruteforce +### c. +Non, sensible au bruteforce +## 1-2/ N'importe quelle lettre +### a. +26! +### b. +Suffisant contre bruteforce +### c. +Cassable par analyse fréquentielle +## 1-3/ Sur un octet +### a. +256! +### b. +Suffisant contre bruteforce +### c. +Analyse fréquentielle ne fonctionne plus + +# 2. Chiffrement par blocs +## 2.1 Modes opératoires +### 2-2 ECB +$$ +\begin{align} +Enc &: &\{0,1\}^k& &\times& &\{ 0,1 \}^n &&\longrightarrow& &\{ 0,1 \}^n \\ + && K& &,& &m & &\longmapsto & &Enc_{K}(m) +\end{align} +$$ +#### a. +$$ +\begin{align} +Dec &: &\{0,1\}^k& &\times& &\{ 0,1 \}^n &&\longrightarrow& &\{ 0,1 \}^n \\ + && K& &,& &c & &\longmapsto & &Dec_{K}(c) +\end{align} +$$ +#### b. +N'affecte pas, chiffrement indépendant +#### c. +Oui +### 2-3 OFB +$z_{0}=IV$, et $z_i=Enc_k(z_{i-1})$, $\forall i, 1 \leq i \leq t$ +$c_i=m_i \oplus z_i$, $\forall i, 1 \leq i \leq t$ +Avec $IV \in \{0,1\}^n$ un vecteur d'initialisation tiré aléatoirement +#### a. +$m_{i} = c_{i} \oplus z_{i}$ +### 2-4 CBC +$c_{0}=IV, c_{i}=Enc_{k}(m_{i} \oplus c_{i-1}), \forall i,\, 1 \leq i \leq t$ +#### a. +$m_{i} = Dec_{k}(c_{i}) \oplus c_{i-1}$ +#### b. +Impact sur $m_i$ et $m_{i+1}$ +#### c. +Non lol +### 2-5 PCBC +$c_{-1}=IV,\, c_{0} \oplus m_{o} = IV, c_{i} = Enc_{k}(m_{i} \oplus m_{i-1} \oplus c_{i-1}),\, 1 \leq i \leq t$ +#### a. +## 2.2 Schéma de Feistel +### 2-6 +Soient $f_1 : \{ 0,1 \}^4 \mapsto \{ 0,1 \}^4$ et $f_{2} : \{ 0,1 \}^4 \mapsto \{ 0,1 \}^4$ tels que $\forall a \in \{ 0,1 \}^4$ +$$ +f_{1}(a) := a \oplus 1011 \;et\; f_{2} := \overline{a} \oplus 0101 +$$ +#### a. +$$ +\begin{align} +&\begin{cases} +L_{1} = R_{0} \\ +R_{1} = L_{0} \oplus f_{1}(R_{0}) +\end{cases} \\ +&\begin{cases} +L_{1} = 0011 \\ +R_{1} = 1101 \oplus 1000 +\end{cases} \\ +&\begin{cases} +L_{1} = 0011 \\ +R_{1} = 0101 +\end{cases} \\ +&\begin{cases} +L_{2} = R_{1} = 0101 \\ +R_{2} = L_{1} \oplus f_{2}(R_{1}) +\end{cases} \\ +&\begin{cases} +L_{2} = 0101 \\ +R_{2} = 0011 \oplus 1010 \oplus 0101 +\end{cases} \\ +&\begin{cases} +L_{2} = 0101 \\ +R_{2} = 0011 \oplus 1111 +\end{cases} \\ +&\begin{cases} +L_{2} = 0101 \\ +R_{2} = 1100 +\end{cases} \\ +\end{align} +$$ +Résultat : $L_2R_2 = 01011100$ +#### b. +Soit $M = (L_0,R_0) \in \{ 0,1 \}^4 \times \{ 0,1 \}^4$, on a +$$ +C_{0} = \begin{cases} +L_{2} = L_{0} \oplus f_{1}(R_{0}) \\ +R_{2} = R_{0} \oplus f_{2}(L_{0} \oplus f_{1}(R_{0})) +\end{cases} = \begin{cases} +L_{2} = L_{0} \oplus f_{1}(R_{0}) \\ +R_{2} = R_{0} \oplus f_{2}(L_{2}) +\end{cases} +$$ +#### c. +$$ +C =\begin{cases} +L_{2} = L_{0} \\ +R_{2} = R_{0} +\end{cases} +$$ +Donc : +$$ +\begin{align} +&f_{1}(R_{0}) = 0 \\ +\implies& R_{0} \oplus 1011 = 0000 \\ +\implies& R_{0} = 1011 +\end{align} +$$ +Et +$$ +\begin{align} +&f_{2}(L_{0} \oplus f_{1}(R_{0})) = f_{2}(L_{0}) = 0 \\ +\implies& \overline{L_{0}} \oplus 0101 = 0000 \\ +\implies& \overline{L_{0}} = 0101 \\ +\implies& L_{0} = 1010 +\end{align} +$$ +Donc $C = (1010, 1011)$ + +### 2-7 +$$ +F: \{ 0,1 \}^t \times \{ 0,1 \}^t \longrightarrow \{ 0,1 \}^t +$$ +$$ +K \in \{ 0,1 \}^t, \, M = (L_{0},R_{0}) \in \{ 0,1 \}^t \times \{ 0,1 \}^t,\, C = (L_{2},R_{2}) \in \{ 0,1 \}^t \times \{ 0,1 \}^t +$$ + +#### a/ +$$ +\begin{cases} +L_{1} = R_{0} \\ +R_{1} = L_{0} \oplus F(K,R_{0}) +\end{cases} +$$ +#### b/ +$$ +\begin{cases} +L_{2} = L_{0} \oplus F(K,R_{0}) \\ +R_{2} = R_{0} \oplus F(K,L_{0} \oplus F(K,R_{0})) +\end{cases} +$$ +#### c/ +$$ +M' = (L_{0}',R_{0}) \in \{ 0,1 \}^t \times \{ 0,1 \}^t,\, C = (L_{2}',R_{2}') \in \{ 0,1 \}^t \times \{ 0,1 \}^t +$$ +On a : +$$ +\begin{cases} +L_{2}' = L_{0}' \oplus F(K, R_{0}) \\ +R_{2}' = R_{0} \oplus F(K, L_{0}' \oplus F(K,R_{0})) +\end{cases} +$$ +Donc : +$$ +L_{2} \oplus L_{2}' = L_{0}' \oplus F(K,R_{0}) \oplus L_{0} \oplus F(K,R_{0}) = L_{0} \oplus L_{0}' +$$ diff --git a/CHIFR/TD/TD2.md b/CHIFR/TD/TD2.md new file mode 100755 index 0000000..3708417 --- /dev/null +++ b/CHIFR/TD/TD2.md @@ -0,0 +1,61 @@ +# Factorisation des entiers et logarithme discret +## Background mathématique +### Square & multiply +#### a/ $13^7 \mod{38}$ +$$\begin{align} +13^7 \mod{38}&= 13^{2^0 \times 1} \times 13^{2^1\times 1} \times 13^{2^2\times 1} \\ +&= 13 \times 13^{2} \times 13^4 \\ +&= 13 * 169 \mod{38} \times 13^4 \mod{38}& \\ +&= (13 \times 17) \mod{38} \times 23 \\ +&= (31 \times 23) \mod{38} \\ +&= 29 +\end{align}$$ +#### b/ Complexité +$\mathcal{O}(\log_{2}e)$ +#### c/ Pour s'entraîner + +### 1-2 +#### a/ $11^{187} \mod{31}$ +Petit théorème de Fermat : $11^{30} \equiv 1 \mod{31}$ +Ainsi : +$$ +\begin{align} +&11^{30} \equiv 1 \mod{31} \\ +\Leftrightarrow & 11^{180} \equiv 1 \mod{31} \\ +\Leftrightarrow & 11^{187} \equiv 13 \mod{31} +\end{align} +$$ + +#### b/ Inverse de $5$ dans $\mathbb{Z}/31\mathbb{Z}$ +PTF : $5^{-1} \equiv 5^{29} \mod{31}$ +Or +$$\begin{align} + +5^{29} \mod{31} &= (5^{14} \times 5^{14} \times 5) \mod{31} \\ +&= ((5^7)^4) \times 5 \mod{31} \\ +&= (5^3 \times 5^3 \times 5^3 \times 5^3 \times 5^3 \times 5^3 \times 5^2) \\ +&= 25 +\end{align} +$$ +Ainsi $5^{-1} = 25$ dans $\mathbb{Z}/31\mathbb{Z}$ + +### 1-3 +#### a/ $7 \in \mathbb{Z}/38\mathbb{Z}$ +$$ +\begin{align} +38 &= 5 \times 7 + 3 \\ +7 &= 2 \times 3 + 1 \\ +3 &= 3 \times 1 + 0 +\end{align} +$$ +En remontant : +$$ +\begin{align} +\gcd(38,7) = 1 &= 7 - 2 \times 3 \\ +&= 7 - 2 \times (38 - 5 \times 7) \\ +&= -2 \times 38 + 11 \times 7 +\end{align} +$$ +<u>Conclusion</u> : $7^{-1} = 11 \mod{38}$ +#### b/ $6 \in \mathbb{Z}/28\mathbb{Z}$ +### 1-4 diff --git a/CHIFR/TD/TD3 - Courbes elliptiques.md b/CHIFR/TD/TD3 - Courbes elliptiques.md new file mode 100755 index 0000000..1d965c7 --- /dev/null +++ b/CHIFR/TD/TD3 - Courbes elliptiques.md @@ -0,0 +1,84 @@ +# 1-1 +## a/ +Point $(3,4)$, d'une part $3^2 = 9 = 3$, d'autre part $4^3 + 2 \times 4 + 3 = 1 + 1 + 3 = 5 \neq 3$ donc le point $(3,4)$ n'appartient pas à la courbe $E$. + +## b/ +D'une part $1^2 = 1$, d'autre part $2^3 + 2 \times 2 + 3 = 1 + 4 + 3 = 1$, donc le point $P$ appartient à $E$. + +## c/ +$-P = (2, -1) = (2, 6)$ + +## d/ +$-Q(x_{Q},y_{Q}) = (x_{Q},-y_{Q} \mod{7})$ + +## e/ +$$ +\begin{cases} +m = 3 \times 2^2 + 2 \\ +x = m^2 - 2 - 2 \\ +y = m(2 - x) - 1 +\end{cases} +\begin{cases} +m = 3 \\ +x = 3 \\ +y = 6 +\end{cases} +$$ + +## f/ + +| $x$ | $x^3 + 2x + 3$ | $y^2$ | +| --- | -------------- | ----- | +| 0 | 3 | 0 | +| 1 | 6 | 1 | +| 2 | 1 | 4 | +| 3 | 1 | 2 | +| 4 | 5 | 2 | +| 5 | 5 | 4 | +| 6 | 0 | 1 | + +Ainsi les points sont $(6,0), (2,1), (3,1), (2,6), (3,6)$ + +## g/ +On a $Card(E(\mathbb{F}_{7})) = 5$ +Et $7 + 1 - 2\sqrt{ 7 } \leq 5 \leq 7 + 1 + 2\sqrt{ 7 }$ + +## h/ + +| | (2,1) | (6,0) | (3,1) | (2,6) | (3,6) | +| ----- | ------------- | ------------- | ------------- | ------------- | ------------- | +| (2,1) | (3,6) | (3,1) | (2,6) | $\mathcal{O}$ | (6,0) | +| (6,0) | (3,1) | $\mathcal{O}$ | | | | +| (3,1) | (2,6) | | | | $\mathcal{O}$ | +| (2,6) | $\mathcal{O}$ | | | | | +| (3,6) | (6,0) | | $\mathcal{O}$ | | | +![[{9A046A90-4F8A-4DC6-8F51-12FD72F497A4}.png]] + +# 1-3 +## a/ + +## b/ +$K_{1} = a(K_{b}) = (x_{1},y_{1})$ +$K_{2} = b(K_{a})$ +$K_{b} = bG$ +$K_{a} = aG$ +$K_{1} = abG = bgA = K_{2}$ + +## c/ +$$ +Dec(Enc(m, pk),sk) \equiv \begin{cases} +x_{2}^{-1} c_{1} \mod{p} \\ +y_{2}^{-1} c_{2} \mod{p} +\end{cases} +\equiv \begin{cases} +x_{2}^{-1}x_{1}m_{1} \mod{p} \\ +y_{2}^{-1}y_{1}m_{1} \mod{p} +\end{cases} +$$ +or $K_{1} = K_{2}$ donc $x_{1} = x_{2}$ + +## d/ +À même message et clé on a même chiffré donc déterministe + +## e/ +$K_{2} = bK_{a} = 4(18,21) = 2 \times 2(18,21) = 2(14,17) = (21,9)$ |