Überprüfung

Auswirkung einer typischen Prüfsummenfunktion (der UNIX CKSUM Dienstprogramm)

A Überprüfung ist eine kleine Größe Block von Daten, die aus einem anderen Block von abgeleitet sind Digitale Daten im Sinne Fehler erkennen das könnte während seines eingeführt worden sein Übertragung oder Lagerung. Schecks werden oft verwendet, um dies zu überprüfen Datenintegrität wird aber nicht darauf verlassen, um dies zu überprüfen Datenauthentizität.[1]

Das Verfahren Das generiert diese Prüfsumme heißt a Überprüfungsfunktion oder Prüfsummenalgorithmus. Abhängig von seinen Entwurfszielen gibt ein guter Kontrollsummenalgorithmus in der Regel einen deutlich anderen Wert aus, selbst wenn kleine Änderungen am Eingang vorgenommen wurden.[2] Dies gilt insbesondere für Kryptografische Hash -Funktionen, die verwendet werden können, um viele Datenbeschädigungsfehler zu erkennen und insgesamt zu überprüfen Datenintegrität; Wenn die berechnete Prüfsumme für die aktuellen Dateneingabe mit dem gespeicherten Wert einer zuvor berechneten Prüfsummen übereinstimmt, besteht eine sehr hohe Wahrscheinlichkeit, dass die Daten nicht versehentlich geändert oder beschädigt wurden.

Prüfsummenfunktionen beziehen sich auf Hash Funktionen, Fingerabdrücke, Randomisierungsfunktionen, und Kryptografische Hash -Funktionen. Jedes dieser Konzepte hat jedoch unterschiedliche Anwendungen und damit unterschiedliche Designziele. Beispielsweise kann eine Funktion, die den Beginn einer Zeichenfolge zurückgibt, einen für einige Anwendungen geeigneten Hash bereitstellen, aber niemals eine geeignete Prüfsumme sein. Prüfsummen werden als verwendet als Kryptografische Primitive In größeren Authentifizierungsalgorithmen. Für kryptografische Systeme mit diesen beiden spezifischen Designzielen siehe HMAC.

Ziffern überprüfen und Paritätsbits sind besondere Fälle von Prüfsummen, die für kleine Datenblöcke geeignet sind (wie z. Sozialversicherungsnummern, Bankkonto Zahlen, Computerwörter, Single Bytes, etc.). Etwas Fehlerkorrigierende Codes basieren auf speziellen Prüfsummen, die nicht nur gemeinsame Fehler erkennen, sondern auch ermöglichen, dass die ursprünglichen Daten in bestimmten Fällen wiederhergestellt werden.

Algorithmen

Paritätsbyte oder Paritätswort

Der einfachste Prüfsummenalgorithmus ist der sogenannte Längsschnitt -Paritätsprüfung, was die Daten mit einer festen Zahl in "Wörter" unterteilt n von Bits und berechnet dann die Exklusiv oder (Xor) aus all diesen Wörtern. Das Ergebnis wird der Nachricht als zusätzliches Wort angehängt. Um die Integrität einer Nachricht zu überprüfen, berechnet der Empfänger das exklusive oder alle seiner Wörter, einschließlich der Prüfsumme. Wenn das Ergebnis kein Wort ist, das besteht aus n Nullen, der Empfänger weiß, dass ein Übertragungsfehler aufgetreten ist.[3]

Bei dieser Prüfsumme wird jeder Übertragungsfehler, der ein einzelnes Bit der Nachricht oder eine ungerade Anzahl von Bits dreht, als falsche Prüfsumme erkannt. Ein Fehler, der zwei Bits betrifft, wird jedoch nicht festgestellt, wenn diese Bits in zwei unterschiedlichen Wörtern an derselben Position liegen. Auch der Austausch von zwei oder mehr Wörtern wird nicht erkannt. Wenn die betroffenen Bits zufällig unabhängig ausgewählt werden, ist die Wahrscheinlichkeit, dass ein Zwei-Bit-Fehler unentdeckt ist 1/n.

Summe Komplement

Eine Variante des vorherigen Algorithmen Zwei ergänzt der Gesamtsumme als Prüfsumme. Um eine Nachricht zu validieren, fügt der Empfänger alle Wörter auf die gleiche Weise hinzu, einschließlich der Prüfsumme. Wenn das Ergebnis kein Wort voller Nullen ist, muss ein Fehler aufgetreten sein. Auch diese Variante erkennt jeden Einzelbit-Fehler, aber die promodulare Summe wird in verwendet SAE J1708.[4]

Positiv-abhängig

Die oben beschriebenen einfachen Prüfsummen erkennen einige häufige Fehler nicht, die viele Bits gleichzeitig beeinflussen, z. B. das Ändern der Reihenfolge von Datendatenwörtern oder das Einsetzen oder Löschen von Wörtern mit allen auf Null gesetzten Bits. Die Prüfsummenalgorithmen, die in der Praxis am häufigsten verwendet werden, wie z. Fletchers Prüfsumme, Adler-32, und zyklische Redundanzprüfungen (CRCS) behandeln Sie diese Schwächen, indem Sie nicht nur den Wert jedes Wortes, sondern auch seine Position in der Sequenz berücksichtigen. Diese Funktion erhöht im Allgemeinen die kosten Berechnung der Prüfsumme.

Fuzzy -Prüfsumme

Die Idee der Fuzzy -Prüfsumme wurde zur Erkennung von entwickelt E -Mail -Spam Durch Erstellen von kooperativen Datenbanken aus mehreren ISPs von E -Mails, bei denen vermutet wird, dass sie Spam sind. Der Inhalt eines solchen Spams kann häufig in seinen Details variieren, was normale Überprüfungen unwirksam machen würde. Im Gegensatz dazu reduziert eine "Fuzzy -Prüfsumme" den Körpertext auf sein charakteristisches Minimum und erzeugt dann eine Prüfsumme auf die übliche Weise. Dies erhöht die Wahrscheinlichkeit von leicht unterschiedlichen Spam -E -Mails erheblich, die dieselbe Prüfsumme erzeugen. Die ISP -Spam -Erkennungssoftware, wie z. SpamassassinMit kooperierenden ISPs liefert die Überprüfungen aller E-Mails dem zentralisierten Dienst wie z. DCC. Wenn die Anzahl einer eingereichten Fuzzy -Prüfsumme einen bestimmten Schwellenwert überschreitet, stellt die Datenbank fest, dass dies wahrscheinlich Spam anzeigt. Der ISP -Service -Benutzer generieren in ähnlicher Weise eine Fuzzy -Prüfsumme für jede ihrer E -Mails und fordern den Dienst nach einer Spam -Wahrscheinlichkeit an.[5]

Allgemeine Überlegungen

Eine Nachricht, die ist m Bits Long können als eine Ecke der angesehen werden m-Dimensionales Hypercube. Der Effekt eines Prüfsummenalgorithmus, der eine ergibt n-Bit -Prüfsumme soll jeden abbilden m-bitnachricht an eine Ecke eines größeren Hypercube mit Dimension m + n. Das 2m + n Die Ecken dieses Hypercube stellen alle möglichen empfangenen Nachrichten dar. Die gültigen empfangenen Nachrichten (diejenigen mit der richtigen Überprüfung) umfassen einen kleineren Satz, mit nur 2m Ecken.

Ein Einzelbit-Übertragungsfehler entspricht dann einer Verschiebung von einer gültigen Ecke (der richtigen Nachricht und Überprüfung) zu einem der der m angrenzende Ecken. Ein Fehler, der sich auswirkt k Bits bewegt die Nachricht in eine Ecke, die ist k Schritte aus der richtigen Ecke entfernt.Das Ziel eines guten Prüfsummenalgorithmus ist es, die gültigen Ecken so weit wie möglich voneinander zu verteilen, um die Wahrscheinlichkeit zu erhöhen.

Siehe auch

Hauptthema

Fehler Korrektur

Hash Funktionen

Dateisysteme

  • ZFS- Ein Dateisystem, das automatische Dateiintegritätsprüfung mithilfe von Prüfsummen durchführt

Verwandte konzepte

Verweise

  1. ^ "Definition der Prüfsummen". www.merriam-webster.com. Archiviert vom Original am 2022-03-10. Abgerufen 2022-03-10.
  2. ^ Hoffman, Chris. "Was ist eine Prüfsumme (und warum sollten Sie sich interessieren)?". How-to Geek. Archiviert vom Original am 2022-03-09. Abgerufen 2022-03-10.
  3. ^ Fairhurst, Gorry (2014). "Checksums & Integrity Checks". Archiviert vom Original am 8. April 2022. Abgerufen 11. März, 2022.
  4. ^ "SAE J1708".Kvaser.com.Archiviert von das Original am 11. Dezember 2013.
  5. ^ "Ixhash".Apache. Archiviert vom Original am 31. August 2020. Abgerufen 7. Januar 2020.

Externe Links