Quel algorithme de somme de contrôle devrais-je utiliser?
je construis un système qui doit être capable de trouver si blobs d'octets ont été mis à jour . Plutôt que de stocker le blob entier (ils peuvent être jusqu'à 5MBs), je pense que je devrais calculer un checksum de celui-ci, stocker ceci et calculer le même checksum un peu plus tard, pour voir si le blog a été mis à jour.
le but est de minimiser les éléments suivants (dans cet ordre):
- taille de la somme de contrôle
- temps de calcul
- Probabilité de collisions (2 checksums identiques se produisant même si le contenu a été modifié).
il est acceptable que notre système n'ait pas de collision supérieure à 1/1 000 000. La préoccupation n'est pas la sécurité, mais simplement la détection des mises à jour/erreurs, de sorte que les rares collisions sont acceptables. (C'est pourquoi je l'ai mis en dernier dans les choses à minimiser).
aussi, nous ne pouvons pas modifier les taches de le texte nous-mêmes.
bien sûr, md5 , crc ou sha1 viennent à l'esprit, et si je voulais une solution rapide, j'irais pour elle. Cependant, plus qu'une solution rapide, je suis à la recherche de ce qui pourrait être une comparaison des différentes méthodes ainsi que les avantages et les inconvénients .
2 réponses
je vous suggère de jeter un oeil à cette SORTE de page , CRC vs MD5/SHA1.
La vitesse et les collisions sont discutées dans cet autre fil .
Et comme toujours Wikipedia est votre ami.
si je devais choisir, Il ya une question importante à répondre: voulez - vous que, dans tous les cas, il n'y a pas de collision - ou, au moins, que la probabilité est si faible qu'il est-ce que la Lune risque de heurter la terre dans les 5 minutes?
si oui, choisissez la famille SHA.
Dans votre cas, je changerais la façon dont le contrôle de mise à jour est fait.
Par exemple, un numéro incrémentiel pourrait être associé au blob, et être envoyé à la place du hachage , le demande de mise à jour serait nécessaire si le nombre est différent de l'autre côté. La probabilité de collision dans ce cas va de ~10^-18 à ~0 (essentiellement 0 + bug probability )...
Modifier à la suite de commentaires
a trouvé cet algorithme, Alder-32, qui est bon pour les messages longs (MB) avec un CRC de 32 bits, i.e. environ ~1/10^9 (MD5 est de 128 bits de long).
Il est rapide à calculer.
Adler-32 . Il y a un échantillon de come (lien) En bas.
Blake2 est la fonction de hachage la plus rapide que vous pouvez utiliser et qui est principalement adoptée:
BLAKE2 est non seulement plus rapide que les autres bonnes fonctions de hachage, il est encore plus rapide que MD5 ou SHA-1 Source
vainqueur du concours SHA-3 était l'algorithme de Keccak mais n'a pas encore une implémentation populaire n'est pas adopté par défaut dans les distributions GNU/Linux. Au lieu de cela, Blake2 qui était un concours SHA-3 candidat est plus rapide que Keccak et fait partie de GNU coreutils . Ainsi, sur votre distribution GNU / Linux, vous pouvez utiliser b2sum pour utiliser L'algorithme de hachage Blake2.