TD3

Exercice 1

Definitions :

1. Une fonction de hachage $H$ est pre-image resistant si étant donnée $y$, c’est difficile de trouver $x$ tel que $H(x)=y$.
2. Elle est second pre-image resistant si étant donnée $x$, c’est difficile de trouver $x^{\prime }$ tel que $H(x)=H(x^{\prime })$ et $x\ne x^{\prime }$.
3. Elle est collision resistant si c’est difficile de trouver $x$ et $x^{\prime }$ tel que $H(x)=H(x^{\prime })$.

Preuve par contradiction que 3 implique 2 : on suppose que H n’est pas second pre-image resistant, on choisi a et on fait l’attaque contre SPR pour trouver b où H(a) = H(b), on repète jusqu’à ce qu’on réussit. on dit que c’est un montant de travail faisable par notre assomption que H n’est pas SPR. La pair (a, b) qu’on trouve est une attaque contre le collision resistance.

Preuve par contradiction que 2 implique 1 : On suppose que H n’est pas pre-image résistant. On choisit un a et on calcule H(a) et on utilise l’attaque sur PR pour calculer un a’ où H(a’) = b. On a une bonne chance pour que a’ != a. Donc, on peut utiliser a’ comme une attaque contre SPR.

Exercice 2

1. $|C|=n\times (l+1)$ (+1 car on a aussi la taille de $c_0$)
2. $c_i={ϵ}_{k-1}(m_i\oplus c_{i-1})$ $m_i={ϵ}_k(c_i)\oplus c_{i-1}$
3. $|c^{\prime }|=n\times l+r$
4. Chiffrement : $c_{l-1}={ϵ}_k(m_{l-1}\oplus c_{l-2})=c_l^{\prime }||P$ $c_{l-1}^{\prime }={ϵ}_k(m_l^{\prime }\oplus (c_l^{\prime }||P))$ et $m_l^{\prime }=m_l||o^{n-r}$ Déchiffrement : ${ϵ}_k^{\prime }(c_{l-1}^{\prime })=m_l^{\prime }\oplus (c_{l^{\prime }}||P)$ et on a déjà $c_l^{\prime }$ $c_{l-1}={ϵ}_k(m_{l-1}\oplus c_{l-2})=c_l^{\prime }||P$ ${ϵ}_k^{-1}(c_l^{\prime }||P)=m_{l-1\oplus c_{l-2}}$ et on a $c_{l-2}$ Donc on peut récupérer $m_{l-1}$

Exercice 3

$|m|=l\times n$ $h(m)$ est donnée par $h_0=IV$ (initial vector) $h_1=f(h_0,m_1)=E(m_1,h_0)\oplus h_0$ $h_i=f(h_{i+1},m_i)=E(m_i,h_{i-1})\oplus h_{i-1}$ $h_l=f(h_{l+1},m_l)=E(m_l,h_{l-1})\oplus h_{l-1}$

1. Comment avoir $f(h,m)=h$ ? Si $E(m,h)=0$

2. On calcule $h^{\prime }=E^{-1}(m,0)$ C’est à dire $E(m,h^{\prime })=0$ $f(h^{\prime },m)=E(m,h^{\prime })\oplus h^{\prime }=h^{\prime }$

   Étant donnée h, on doit trouver m. On doit utiliser le brut force. Supposant que E est un block cipher idéal, alors le chiffrement avec k nous donne une valeur dans la permutation de taille de $2^n$. on doit essayer $S^n$ valeurs de clé pour trouver le fixed point.

3. On veut trouver $(h,m,m^{\prime })$ tel que $H_h(m)=H_h(m^{\prime })$. Ici, h est le initialization vector. La premiere étape est de trouver un fixed point. On choisi m et on calcul le fixed point comme la question 2, alors on a h tel que $f(h,m)=h$. On a $h_0=h$ et $m_1=m$. Comme $f(h,m)=h$alors $h_1=h$. On veut trouver un $m_2$ qui nous donne $h_2=h$. $h_2=f(h_1,m_2)=E(m_2,h_1)\oplus h_1$ donc on veut un $m_2$ où $E(m_2,h_1)=0$ alors on peut choisir $m_2=m$ et donc $m^{\prime }=m||m$.

Exercice 4

$E_K(P)=C\iff E_{\bar{K}}(\bar{P})=\bar{C}$

Exercice 5