Checksum incrementali

Question

Sto cercando un algoritmo di checksum in cui per un grande blocco di dati il ​​checksum è uguale alla somma dei checksum di tutti i blocchi di componenti più piccoli. La maggior parte di ciò che ho trovato proviene da RFC 1624/1141 che forniscono questa funzionalità. Qualcuno ha qualche esperienza con queste tecniche di checksum o simili?

Answer 1

Ho utilizzato solo i checksum Adler/Fletcher che funzionano come descritto.

C'è un bel confronto di implementazioni di hash/checksum di crypto ++ here.

Answer 2

Per rispondere alla domanda di generosità di Amigable Clark Kent, per scopi di identificazione dei file probabilmente si desidera una funzione di hash crittografica, che cerca di garantire che qualsiasi due file dati abbia una probabilità estremamente bassa di produrre lo stesso valore, al contrario di un checksum che viene generalmente utilizzato solo per il rilevamento degli errori e può fornire lo stesso valore per due file molto diversi.

Molte funzioni hash crittografiche, quali MD5 e SHA-1, utilizzare il Merkle–Damgård construction, in cui v'è un calcolo per comprimere un blocco di dati in una dimensione fissa, e quindi combinare che con un valore di dimensione fissa dal blocco precedente (o un vettore di inizializzazione per il primo blocco). Pertanto, sono in grado di lavorare in una modalità di streaming, calcolando in modo incrementale mentre procedono.

Answer 3

Se si tratta solo di combinare rapidamente i checksum dei blocchi più piccoli per ottenere i checksum del messaggio più grande (non necessariamente con una semplice sommatoria), è possibile farlo con un algoritmo di tipo CRC (o simile).

L'algoritmo CRC-32 è semplice come questo:

uint32_t update(uint32_t state, unsigned bit) 
{ 
    if (((state >> 31)^bit) & 1) state = (state << 1)^0x04C11DB7; 
    else       state = (state << 1); 
    return state; 
} 

Matematicamente, lo stato rappresenta un polinomio di sopra del GF2 campo che viene sempre ridotta modulo il polinomio generatore. Dato un nuovo bit b lo stato precedente viene trasformato nel nuovo stato simili

state --> (state * x^1 + b * x^32) mod G 

dove G è il polinomio generatore e l'aggiunta viene effettuata in GF2 (XOR). Questo checksum è lineare, nel senso che si può scrivere il messaggio M come una somma (XOR) di messaggi di A, B, C, ... come questo

10110010 00000000 00000000 = A = a  00000000 00000000 
    00000000 10010001 00000000 = B = 00000000 b  00000000 
    00000000 00000000 11000101 = C = 00000000 00000000 c 
------------------------------------------------------------- 
= 10110010 10010001 11000101 = M = a  b  c 

con le seguenti proprietà

  M =   A +   B +   C 
checksum(M) = checksum(A) + checksum(B) + checksum(C) 

Anche in questo caso, intendo lo + in GF2 che è possibile implementare con uno XOR binario.

Infine, è possibile calcolare checksum(B) basato su checksum(b) e la posizione del sottoblocco b rispetto al B. La parte semplice sta conducendo zeri. Gli zeri iniziali non influenzano affatto il checksum. Quindi checksum(0000xxxx) è lo stesso di checksum(xxxx). Se vuoi calcolare il checksum di un messaggio con zero zeri (a destra -> ultimi zero) dato il checksum del messaggio non inserito, è un po 'più complicato.Ma non è così complicato:

zero_pad(old_check_sum, number_of_zeros) 
    := (old_check_sum * x^{number_of_zeros}  ) mod G 
    = (old_check_sum * (x^{number_of_zeros} mod G)) mod G 

Quindi, ottenere il checksum di un messaggio zeri è solo una questione di moltiplicare il "checksum polinomiale" del messaggio non imbottita con qualche altro polinomio (x^{number_of_zeros} mod G) che dipende solo sul numero di zeri che si desidera aggiungere. Puoi precomputerlo in una tabella o usare l'algoritmo square-and-multiply per calcolare rapidamente questo potere.

Lettura consigliata: Painless Guide to CRC Error Detection Algorithms