Comment un ordinateur sait-il qu'un fichier n'a pas été modifié ?

Quand tu télécharges un fichier, comment savoir si un seul bit a été corrompu en chemin ? Comme tu n'as en général pas l'original sous la main pour comparer octet par octet, l'ordinateur fait passer le fichier par une fonction de hachage cryptographique, qui réduit n'importe quelle entrée, aussi grande soit-elle, à une empreinte courte et de taille fixe. La même entrée donne toujours la même empreinte, donc deux copies d'un fichier ne correspondent que si leurs empreintes correspondent aussi.

Ce qui rend cette empreinte fiable, c'est qu'un tout petit changement dans l'entrée produit un résultat totalement différent : changer une seule lettre bouleverse complètement l'empreinte. C'est pourquoi certains sites publient l'empreinte d'un fichier téléchargeable : si l'empreinte calculée chez toi ne correspond pas à celle publiée, c'est que quelque chose a changé.

Une fonction de hachage doit aussi résister à la triche. Il doit être difficile de retrouver une entrée à partir d'une empreinte donnée, difficile de trouver une deuxième entrée qui produit la même empreinte qu'une entrée connue, et difficile de trouver deux entrées différentes qui produisent la même empreinte. Les collisions sont les plus faciles à traquer, grâce à une astuce appelée l'attaque des anniversaires : une empreinte censée y résister doit donc être au moins deux fois plus longue qu'une empreinte qui doit seulement résister à l'inversion.

Les fonctions de hachage ne restent pas solides éternellement, et se fier à une vieille fonction est une erreur classique. Avec MD5, autrefois très utilisée, on calcule aujourd'hui des collisions en quelques secondes, et en février 2017 Google a annoncé une collision dans SHA-1, désormais considérée comme cassée. Le même principe à sens unique sert aussi au minage de Bitcoin, où des ordinateurs cherchent des entrées dont l'empreinte atteint une cible pour prouver qu'ils ont fourni le travail.