Compromis Temps-Mémoire Cryptanalytique

Cette thèse analyse les améliorations des Compromis Temps-Mémoire Cryptanalytiques (TMTO), avec un accent sur les tables arc-en-ciel (RT). Elle revisite la phase de précalcul des RT, une étape souvent délaissée, en proposant des avancées notables. Une contribution majeure est la méthode de filtration, qui réduit le temps de précalcul des RT, en particulier celles dites parfaites ou propres, permettant de diminuer ce temps par un facteur de 6 pour des tables quasi-maximales. La thèse explore également la distribution de la phase de précalcul utilisant la méthode de filtration et fournit une comparaison du temps de précalcul des TMTO sur divers environnements. Ce travail révèle que le goulet d'étranglement actuel des TMTO sont les précalculs, et non le temps d’attaque ou la mémoire. Par ailleurs, elle présente deux nouvelles variantes des RT : les tables escaliers descendantes et ascendantes. Ces deux variantes, à couverture et mémoire fixes, surpassent les RT en précalcul et en attaque. Notamment, la première permet de réduire significativement le temps de précalcul par rapport aux RT avec filtration, tandis que la seconde permet un gain significatifs pour les tables quasi-maximales. La thèse conclut que les TMTO doivent être envisagés comme un compromis entre quatre facteurs: temps de précalcul, temps d’attaque, mémoire et couverture, ouvrant la voie à une optimisation future des TMTO.