Algoritmo di funzione hash 8 byte leggero

Ho bisogno di estrarre un digest 8 byte da una stringa di lunghezza variabile, quindi sto cercando un algoritmo che implementerò in c/C++. Che farà parte di una procedura di firma digitale su un microcontrollore, quindi deve essere:Algoritmo di funzione hash 8 byte leggero

scrivibile in poche righe di codice, dal momento che il firmware deve essere mantenuto il meno possibile;
basso consumo di risorse, specialmente ram (preferibilmente inferiore a 100 byte);
abbastanza forte che la modifica di un singolo carattere in qualsiasi punto della stringa cambierebbe il riassunto complessivo.

Ho dato un'occhiata agli algoritmi esistenti come crc64 ma sembrano essere troppo pesanti per la mia piattaforma.

fonte

2012-11-10 etuardu

Ci sono molte funzioni di hash disponibili (e facilmente reperibili). Quali funzioni esistenti hanno guardato "vicino" all'obiettivo desiderato e perché? Se non erano accettabili, perché? Ci sono una serie di buoni risultati/lettura per una semplice "funzione hash C" - onestamente, solo il 3 ° requisito postato sembra di qualsiasi interesse. Inoltre, poiché è stato menzionato il CRC, l'obiettivo è un [generale] * hash * o un * checksum *? –

Forse questo può essere utile: http://en.wikipedia.org/wiki/List_of_hash_functions Forse controlla anche sphlib ma per chiarire qualcosa 8 byte provocheranno collisioni quindi il punto 3 dei tuoi requisiti non può essere soddisfatto da QUALSIASI hashing algoritmo almeno non per tutte le stringhe e 8 byte è piuttosto basso. –

@pst: ho preso in considerazione alcune delle funzioni di hash esistenti che forniscono un output a 64 bit, ma per esempio il crc64 ha bisogno di molto più di 100 byte di ram. Come ho affermato nella domanda, l'obiettivo è ottenere un digest di messaggi, quindi una funzione di crittografia sarebbe meglio. Tuttavia, ho bisogno che sia leggero più che forte, quindi ho preso in considerazione anche altre funzioni di hash. – etuardu

Come AndrewTomazos-Fathomling detto, è impossibile fare un hash sicuro in 64 bit, quindi se questo è vostra intenzione, allora il mio consiglio è STOP, prendi un libro e leggi l'hashing crittograficamente sicuro.

Se non si prevede di utilizzare questo come un hash sicuro e non si cura di collisioni o attacchi, la risposta che ha dato funziona perfettamente e si possono modificare i primi P1 e P2 secondo necessità. Ti darò un'altra alternativa che ti permette di fare hashing con tag e mescolare di più le cose.

// Disclaimer: I make no claims about the quality of this particular hash - it's 
// certainly not a cryptographically secure hash, nor should it *ever* be 
// construed as such. 

unsigned long long quickhash64(const char *str, unsigned long long mix = 0) 
{ // set 'mix' to some value other than zero if you want a tagged hash   
    const unsigned long long mulp = 2654435789; 

    mix ^= 104395301; 

    while(*str) 
     mix += (*str++ * mulp)^(mix >> 23); 

    return mix^(mix << 37); 
}

fonte

2012-11-10 21:40:24

Mi è piaciuto molto di più perché mantiene la sensibilità contro tutti i caratteri della stringa, mentre altri che utilizzano i turni perderanno l'influenza dei primi caratteri della stringa dopo determinate lunghezze. A proposito, vedo che potrebbe essere abbreviato come, ad esempio, 'uint64_t mix, mulp = 2654435789; while (* str) mix^= mulp ** str ++; '. – etuardu

Non è possibile eseguire un hash sicuro in 64 bit. Anche SHA-1 a 160 bit è considerato teoricamente rotto. Dovresti usare SHA2-256 se ti interessa davvero la firma digitale sicura. Se non si cura di sicurezza e desidera solo una funzione di hash che evita le collisioni non contraddittorio basta usare il seguente, è bene:

constexpr uint64 P1 = 7; 
constexpr uint64 P2 = 31; 

uint64 hash = P1; 
for (const char* p = s; *p != 0; p++) { 
    hash = hash * P2 + *p; 
}

fonte

2012-11-10 19:12:45

+1, anche se 'strlen' non è un nome di variabile grande in un programma C. :-P – ruakh

Grazie per la tua risposta, anche se questo non ha veramente soddisfatto il mio terzo punto: 'mystring1' =>' 10000786a32ed', 'mystring2' =>' 10000786a32ee'.Avrei bisogno di qualcosa che possa "propagare" un po 'di più il cambiamento di un singolo personaggio attraverso l'hash. – etuardu

Vuoi ciò che viene chiamato "effetto valanga", ma chiediti perché lo vuoi. Ha davvero senso solo nel contesto dell'hashing sicuro, e con solo 64 bit non sarà mai sicuro contro un attacco di forza bruta. È possibile ottenere più bit ruotati utilizzando due numeri primi più grandi per P1 e P2, ma come ho detto non ha senso. –

Ecco una versione modificata di una versione a 32 bit ho trovato nella mia vecchi file sorgente

static unsigned long long llhash(const char *str) 
{ 
    unsigned long long hash = 5381; 
    int c; 

    while (c = *str++) 
     hash = ((hash << 5) + hash) + c; 

    return hash; 
}

Ma l'hashing causerà sempre collisioni. Ovviamente alcuni algoritmi sono migliori di altri.

Edit: ho trovato la fonte della versione a 32 bit: http://www.cse.yorku.ca/~oz/hash.html

fonte

2012-11-10 19:17:49

Algoritmo di funzione hash 8 byte leggero

risposta

Problemi correlati