Inkrementelle Prüfsummen

Question

Ich suche nach einem Prüfsummenalgorithmus, bei dem die Prüfsumme für einen großen Datenblock der Summe der Prüfsummen aller kleineren Bausteine ​​entspricht. Das meiste, was ich gefunden habe, stammt von RFCs 1624/1141, die diese Funktionalität bereitstellen. Hat jemand irgendwelche Erfahrungen mit diesen Prüfsummen oder ähnlichen Techniken?

Answer 1

Ich habe nur Adler/Fletcher Prüfsummen verwendet, die wie beschrieben funktionieren.

Es gibt einen schönen Vergleich von crypto ++ Hash/Checksum-Implementierungen here.

Answer 2

Um die Kopfgeldfrage von Amigable Clark Kent zu beantworten, möchten Sie wahrscheinlich eine kryptografische Hash-Funktion, die garantiert, dass zwei gegebene Dateien eine extrem niedrige Wahrscheinlichkeit haben, den gleichen Wert zu erzeugen, im Gegensatz zu einer Prüfsumme wird im Allgemeinen nur zur Fehlererkennung verwendet und kann denselben Wert für zwei sehr unterschiedliche Dateien bereitstellen.

Viele kryptographischen Hash-Funktionen, wie MD5 und SHA-1, verwenden, um die Merkle–Damgård construction, in denen es eine Berechnung einen Block von Daten in eine festgelegte Größe zu komprimieren, und dann verbinden, dass mit einem festen Größe Wert aus dem vorangehenden Block (oder ein Initialisierungsvektor für den ersten Block). So können sie im Streaming-Modus arbeiten und inkrementell rechnen.

Answer 3

Wenn es nur darum geht, die Prüfsummen der kleineren Blöcke schnell zu kombinieren, um zu den Prüfsummen der größeren Nachricht zu gelangen (nicht notwendigerweise durch eine einfache Summierung), können Sie dies mit einem CRC-ähnlichen (oder ähnlichen) Algorithmus tun.

Der CRC-32-Algorithmus ist so einfach wie diese:

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

Mathematisch stellt der Staat ein Polynom über das Feld GF2, die immer Modulo der Generatorpolynom reduziert wird. Bei einem neuen Bit b der alte Zustand in den neuen Zustand überführt wird, wie diese

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

wobei G das Generatorpolynom und zusätzlich wird in GF2 (xor) durchgeführt. Diese Prüfsumme ist linear in dem Sinne, dass Sie die Nachricht M als Summe schreiben können (xor) von Nachrichten A, B, C, ... wie diese

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 

mit den folgenden Eigenschaften

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

Ich meine wieder die + in GF2, die Sie mit einem binären XOR implementieren können.

Schließlich ist es möglich checksum(B) basierend auf checksum(b) und die Position des Subblocks b relativ zu B zu berechnen. Der einfache Teil ist führende Nullen. Führende Nullen beeinflussen die Prüfsumme überhaupt nicht. So ist checksum(0000xxxx) das gleiche wie checksum(xxxx). Wenn Sie die Prüfsumme einer zero-padded (nach rechts -> nachgestellte Nullen) Nachricht mit der Prüfsumme der nicht aufgefüllten Nachricht berechnen möchten, ist es etwas komplizierter.Aber nicht so kompliziert:

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 

So bekommen die Prüfsumme einer Null-gepolsterte Nachricht ist nur eine Frage der „Prüfsumme Polynom“ Multiplizieren der unwattierter Nachricht mit einem anderen Polynom (x^{number_of_zeros} mod G), die nur abhängig auf die Anzahl der Nullen, die Sie hinzufügen möchten. Sie könnten dies in einer Tabelle vorberechnen oder den Quadrat-und-Multiplikation-Algorithmus verwenden, um diese Leistung schnell zu berechnen.

nachlesen: Painless Guide to CRC Error Detection Algorithms