Fonction de compression

En cryptographie, une fonction de compression est une fonction à sens unique qui prend une entrée de M bits et produit à sa sortie une séquence de N bits avec N strictement inférieur à M. On doit ce terme à Ralph Merkle et Ivan Damgård qui l'ont utilisé dans le cadre de la construction de Merkle-Damgård. La sortie est ainsi « compressée » (à perte d'où le terme « sens unique ») puisque plus courte que l'entrée. Il est difficile de retrouver l'entrée si l'on connaît uniquement la sortie.

Une fonction de compression unidirectionnelle typique, habituellement utilisée dans la construction Merkle-Damgård

Une telle transformation est utilisée dans les fonctions de hachage : on découpe pour cela le message en blocs sur lesquels est appliquée à plusieurs reprises la fonction de compression. De plus, plusieurs entrées sont possibles pour la même sortie, cette recherche de collision dans la fonction de compression permet de mener des attaques sur la fonction de hachage.

• Portail de la cryptologie