J'ai besoin d'extraire un digère de 8 octets d'une chaîne de longueur variable, donc je recherche un tel algorithme que je vais implémenter en C / C ++. Cela fera partie d'une procédure de signature numérique sur un microcontrôleur, il doit donc être:
J'ai examiné des algorithmes existants tels que CRC64, mais ils semblent être trop lourds pour ma plate-forme.
4 Réponses :
Il n'y a aucune chance de faire un hachage sécurisé dans 64 bits. Même SHA-1 à 160 bits est considéré comme théoriquement brisé. Vous devez utiliser SHA2-256 si vous vous souciez vraiment de la signature numérique sécurisée. Si vous ne vous souciez pas de la sécurité et que vous voulez juste une fonction de hachage qui évite les collisions non contradictoires, utilisez simplement ce qui suit, c'est bien:
constexpr uint64 P1 = 7;
constexpr uint64 P2 = 31;
uint64 hash = P1;
for (const char* p = s; *p != 0; p++) {
hash = hash * P2 + *p;
}
+1, bien que strylen n'est pas un excellent nom de variable dans un programme C. :-P
Merci pour votre réponse, bien que cela ne remplisse pas vraiment mon troisième point: mystring1 => 10000786a32ed , mystring2 => 10000786A32e . J'aurais besoin de quelque chose qui peut "propager" un peu plus le caractère unique change dans le hachage.
Vous voulez ce qu'on appelle l'appel "Effet Avalanche", mais demandez-vous pourquoi vous voulez cela. Cela n'a vraiment aucun sens dans le contexte de la hachage sécurisée, et avec seulement 64bits, il ne sera jamais sécurisé contre une attaque de force brute. Vous pouvez obtenir des bits plus retournés en utilisant deux grands nombres premiers pour P1 et P2, mais comme je l'ai dit, il n'y a pas de point.
Pourquoi, exactement, avez-vous besoin de modifications pour avalanche plus rapidement? Comme @ @ Andrewtomazos-Fathomling a dit, il commence à sonner comme si vous voulez faire "Sécuriser hachage", mais avec seulement 64 bits, il ne va tout simplement pas fonctionner.
Voici une version modifiée d'une version 32 bits que j'ai trouvée dans mes anciens fichiers source mais le hachage entraînera toujours des collisions. Bien sûr, certains algorithmes sont meilleurs que d'autres.
As Andrewtomazos-Fathomling dit, il est impossible de faire un hachage sécurisé dans 64 bits, donc si c'est votre intention, mon conseil est Stop , ramasser un livre et lisez sur le hachage cryptographiquement. Si vous ne prévoyez pas d'utiliser cela comme un hachage sécurisé et que vous ne vous souciez pas des collisions ou des attaques, la réponse qu'il vous a donné fonctionne bien et vous pouvez modifier les nombres premiers P1 et P2 si nécessaire. Je vais vous donner une autre alternative qui vous permettra de faire des hachages marqués et de mélanger des choses plus.
J'ai mieux aimé celui-ci, car il conserve la sensibilité contre tous les caractères de la chaîne, d'autres qui utilisaient des changements perdent l'influence des premiers caractères de la chaîne après certaines longueurs. Au fait, je vois que cela pourrait être raccourci, par exemple, uint64_t mélange, mulp = 2654435789; tandis que (* str) mix ^ = mulp ** str ++; .
J'avais exactement la même exigence, et je me suis installé pour FNV-1A , après avoir rejeté SIP Hash ( Mise en œuvre par Bloomberg ici ) . J'ai trouvé une implémentation FNV ici: < p> https://github.com/foonathan/string_id/blob/master/ hash.hpp qui est: Il apparaît qu'il est en boucle à l'aide de la récursion de la queue. Et la condition d'arrêt est le licence est null octet.
(boost utilise hash_range qui est hash_comminant chaque élément de chaîne je suppose.)
Il existe de nombreuses fonctions de hachage disponibles (et facilement trouvées). Quelle (s) fonction (s) existante (s) ressemblait à "près de" l'objectif souhaité et pourquoi? S'ils n'étaient pas acceptables, pourquoi? Il existe un certain nombre de bons résultats / de bons résultats pour une simple "fonction de hachage de hachage C" - honnêtement, seule la 3ème exigence postait des looks d'un intérêt. De plus, étant donné que CRC a été mentionné, est l'objectif [général] hash ou a checksum ?
Peut-être que cela peut être utile: en.wikipedia.org/wiki/list_of_hash_functions peut-être consulter SPHLIB comme Eh bien, mais pour clarifier quelque chose, 8 octets entraîneront des collisions, le point 3 de vos exigences ne peut être rempli par aucun algorithme de hachage au moins pas pour toutes les chaînes et 8 octets est assez faible.
@pst: J'ai pris en compte certaines des fonctions de hachage existantes qui donnent une sortie 64 bits, mais par exemple, le CRC64 a besoin de plus de 100 octets de RAM. Comme je l'ai dit dans la question, l'objectif est d'obtenir un message de digère. Une fonction cryptographique serait donc meilleure. Néanmoins, j'en ai besoin pour être léger plus que fort, alors j'ai pris en compte d'autres fonctions de hasch aussi.