Compromis espace temps d'une attaque

L'idée: si on a assez d'espace (place disque), on peut faire des précalculs qui réduiront le temps nécessaire à l'exécution de l'attaque. Exemple avec DES:

• Si je connais un texte clair et son équivalent chiffré, je peux essayer chacune des $2^{56}$ clés jusqu'à trouver la bonne. Cela ne nécessite pas de mémoire, mais il me faudra en moyenne $2^{55}$ essais.

• Si je connais un texte clair, je peux précalculer une table des $2^{56}$ couples $(K,y_K)$ tels que $y_K=e_K(x)$ et la trier suivant les $y_K$. Dès que je trouve un texte chiffré $y$, il me suffit de le chercher dans la table (temps négligeable) pour trouver la clé correspondante.

• Si je n'utilise ce système qu'une fois, il n'a aucun intérêt: le temps du précalcul est égal au temps de la recherche exhaustives des clés.

• Par contre, si je sais que je devrai faire cette recherche plusieurs fois, et que le même texte en clair apparaîtra chaque fois quelque part, je peux réutiliser ma table sans calcul supplémentaire.

• Stinson (§3.5) décrit un compromis espace-temps pour lequel le temps nécessaire (précalcul non-compris) est inférieur à une recherche exhaustive, avec un espace nécessaire inférieur à une table de toutes les clés.