-
Notifications
You must be signed in to change notification settings - Fork 1
/
question14.tex
27 lines (20 loc) · 1.42 KB
/
question14.tex
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
\section{Retrouver la clef sans connaître $R_4$}
Si l'on ne connaît pas le contenu du registre $R_4$, on ne peut pas calculer
les équations linéaires (ni les équations quadratiques) en les $(x_i)_{0\leq i \leq 63}$. \\
En effet sans connaître l'état du registre $R_4$ on ne peut calculer $m$,
ni savoir quels bits des registres $R_1$, $R_2$ et $R_3$ seront mis à jour.\\
La seule façon que nous avons de retrouver $R_4$ est en testant toutes les valeurs possibles (attaque par force brute),
jusqu'à trouver un état qui produit bien la bonne suite chiffrante en sortie, après avoir calculé
les $(x_i)_{0\leq i \leq 63}$ et la clef de chiffrement.\\
L'attaque précédente, en supposant connu le registre $R_4$ avait une complexité en $O(L^²)$
où L est le nombre de monomes apparaissant dans les équations. En effet l'étape la plus coûteuse
de l'attaque est le calcul de la matrice représentant les équations linéarisées.\\
En utilisant le paradoxe des anniversaires on peut espérer trouver le bon $R_4$ au bout de
$2^{17/2}$ essais (on a 17 bits à deviner).
On multiplie donc le temps de l'attaque par $2^{9}$. Sachant que notre implémentation retrouve les bits de la clef
secrète en $\approx 9$ secondes, cela devrait nous prendre environ 1h20 pour retrouver la clef sans connaître $R_4$
\begin{align*}
t & = \frac{2^9 \times 9}{3600}\\
& = 1.28 \mbox{ heures}\\
& = 1 \mbox{ heure et }20\mbox{ minutes}\\
\end{align*}