Eine zyklische Redundanzprüfung (CRC) ist ein Fehlererkennungscode, der allgemein in Digitalnetzen und Speichergeräten verwendet ist, um zufällige Änderungen zu rohen Daten zu entdecken. Datenblocks, die in diese Systeme eingehen, bekommen einen kurzen Kontrolle-Wert, der beigefügt, auf dem Rest einer polynomischen Abteilung ihres Inhalts gestützt ist; auf der Wiederauffindung wird die Berechnung wiederholt, und Verbesserungshandlung kann gegen die gewagte Datenbestechung genommen werden, wenn die Kontrolle-Werte nicht zusammenpassen.

CRCs sind so genannt, weil die Kontrolle (Datenüberprüfung) Wert eine Überfülle ist (es fügt keine Information zur Nachricht hinzu), und der Algorithmus basiert auf zyklischen Codes. CRCs sind populär, weil sie einfach sind, in der binären Hardware, leicht durchzuführen, mathematisch, und besonders gut im Ermitteln allgemeiner Fehler zu analysieren, die durch das Geräusch in Übertragungskanälen verursacht sind. Weil der Kontrolle-Wert eine feste Länge hat, wird die Funktion, die ihn erzeugt, gelegentlich als eine Kuddelmuddel-Funktion verwendet. Der CRC wurde von W. Wesley Peterson 1961 erfunden; das 32-Bit-Polynom, das in der CRC Funktion von Ethernet und vielen anderen Standards verwendet ist, ist die Arbeit von mehreren Forschern und wurde 1975 veröffentlicht.

Einführung

CRCs basieren auf der Theorie von zyklischen Fehlerkorrekturcodes. Der Gebrauch von systematischen zyklischen Codes, die Nachrichten durch das Hinzufügen eines Kontrolle-Werts der festen Länge zum Zweck der Fehlerentdeckung in Nachrichtennetzen verschlüsseln, wurde zuerst von W. Wesley Peterson 1961 vorgeschlagen.

Zyklische Codes sind nicht nur einfach, den Vorteil durchzuführen aber zu haben, für die Entdeckung von Platzen-Fehlern, aneinander grenzenden Folgen von falschen Datensymbolen in Nachrichten besonders gut angepasst zu werden. Das ist wichtig, weil gesprengte Fehler allgemeine Übertragungsfehler in vielen Nachrichtenkanälen einschließlich magnetischer und optischer Speichergeräte sind. Normalerweise ein N-Bit wird auf einen Datenblock der willkürlichen Länge angewandter CRC jedes einzelne Fehlerplatzen entdecken, das nicht länger ist als n Bit, und wird einen Bruchteil 12 aller längeren Fehlerbrüche entdecken.

Die Spezifizierung eines CRC-Codes verlangt Definition eines so genannten Generator-Polynoms. Dieses Polynom ähnelt dem Teiler in einer polynomischen langen Abteilung, die die Nachricht als die Dividende nimmt, und in dem der Quotient verworfen wird und der Rest das Ergebnis mit der wichtigen Unterscheidung wird, dass die polynomischen Koeffizienten gemäß der tragen weniger Arithmetik eines begrenzten Feldes berechnet werden. Die Länge des Rests ist immer weniger als die Länge des Generator-Polynoms, das deshalb bestimmt, wie lang das Ergebnis sein kann.

In der Praxis haben alle allgemein CRCs verwendet verwenden den begrenzten Feld-GF (2). Das ist das Feld von zwei Elementen, gewöhnlich genannt 0 und 1, bequem Computerarchitektur vergleichend. Der Rest dieses Artikels wird nur diese binären CRCs besprechen, aber die Grundsätze sind allgemeiner.

Das einfachste Fehlerentdeckungssystem, das Paritätsbit, ist tatsächlich ein trivialer 1-Bit-CRC: Es verwendet das Generator-Polynom x+1.

Anwendung

Ein CRC-ermöglichtes Gerät berechnet einen kurzen, feste Länge binäre Folge, die als der Kontrolle-Wert oder unpassend der CRC für jeden Datenblock bekannt ist, der zu senden oder zu versorgen ist, und hängt es an den Daten an, ein Kennwort bildend. Wenn ein Kennwort erhalten oder, das Gerät gelesen wird entweder seinen Kontrolle-Wert mit ein frisch berechnet vom Datenblock, oder gleichwertig vergleicht, einen CRC auf dem ganzen Kennwort durchführt und den resultierenden Kontrolle-Wert mit einem erwarteten unveränderlichen Rückstand vergleicht. Wenn die Kontrolle-Werte nicht zusammenpassen, dann enthält der Block einen Datenfehler. Das Gerät kann Verbesserungshandlung, wie Lesewiederholung des Blocks nehmen oder dass es bittend, wieder gesandt werden. Sonst, die Daten wird angenommen, fehlerfrei zu sein (obwohl, mit etwas kleiner Wahrscheinlichkeit, es unentdeckte Fehler enthalten kann; das ist die grundsätzliche Natur der Fehlerüberprüfung).

CRCs und Datenintegrität

CRCs werden spezifisch entworfen, um gegen allgemeine Typen von Fehlern auf Nachrichtenkanälen zu schützen, wo sie schnelle und angemessene Versicherung der Integrität von gelieferten Nachrichten zur Verfügung stellen können. Jedoch sind sie nicht passend, um gegen die absichtliche Modifizierung von Daten zu schützen. Erstens, da es keine Beglaubigung gibt, kann ein Angreifer eine Nachricht editieren und den CRC ohne den Ersatz wiederberechnen, der wird entdeckt. Das ist sogar der Fall, wenn der CRC encrypted ist, zu einem der Designfehler des WEP Protokolls führend. Zweitens erlauben die geradlinigen Eigenschaften von CRC-Codes sogar einem Angreifer, eine Nachricht auf solche Art und Weise zu modifizieren, um den Kontrolle-Wert unverändert zu verlassen, und sonst effiziente Wiederberechnung des CRC für Kompaktänderungen zu erlauben. Dennoch wird es noch häufig falsch angenommen, dass, wenn eine Nachricht und sein richtiger Kontrolle-Wert von einem offenen Kanal dann erhalten werden, die Nachricht unterwegs nicht verändert worden sein kann.

Kryptografische Kuddelmuddel-Funktionen, während sie Sicherheit gegen die absichtliche Modifizierung, wenn verwendet, auf diese Weise noch immer nicht zur Verfügung stellen, können stärkeren Fehler zur Verfügung stellen überprüfend, darauf verlassen sie sich auf spezifische Fehlermuster-Annahmen nicht. Jedoch sind sie viel langsamer als CRCs, und werden deshalb allgemein verwendet, um Off-Linedaten, wie Dateien auf Servern oder Datenbanken zu schützen.

Wenn versorgt, neben den Daten schützen CRCs und kryptografische Kuddelmuddel-Funktionen durch sich gegen die absichtliche Modifizierung von Daten nicht. Jede Anwendung, die Schutz gegen solche Angriffe verlangt, muss kryptografische Beglaubigungsmechanismen wie Nachrichtenbeglaubigungscodes verwenden.

Berechnung von CRC

Um ein N-Bit binärer CRC zu schätzen, linieren Sie die Bit, die den Eingang hintereinander vertreten, und stellen Sie (n+1) - Bit-Muster ein, das den Teiler des CRC vertritt (hat ein "Polynom" genannt) unter dem linken Ende der Reihe.

Fangen Sie mit der Nachricht an, verschlüsselt zu werden:

11010011101100

</pre>

Das wird zuerst mit zeroes entsprechend der Bit-Länge n vom CRC ausgepolstert. Hier ist die erste Berechnung, für einen 3-Bit-CRC zu schätzen:

11010011101100 000

Wenn das Eingangsbit über dem leftmost Teiler-Bit 0 ist, tun Sie nichts. Wenn das Eingangsbit über dem leftmost Teiler-Bit 1 ist, ist der Teiler XORed in den Eingang (mit anderen Worten, das Eingangsbit über jedem 1 Bit im Teiler ist toggled). Der Teiler wird dann ein Bit nach rechts ausgewechselt, und der Prozess wird wiederholt, bis der Teiler das rechte Ende der Eingangsreihe erreicht. Hier ist die komplette Berechnung:

11010011101100 000

Seitdem der leftmost Teiler zeroed gebissen hat, hat jeder Eingang es berührt gebissen, wenn dieser Prozess die einzigen Bit in der Eingangsreihe beendet, die Nichtnull sein kann, sind die n Bit am rechten Ende der Reihe. Diese n Bit sind der Rest des Abteilungsschritts, und werden auch der Wert der CRC-Funktion sein (wenn die gewählte CRC Spezifizierung nach etwas Postverarbeitung nicht verlangt).

Die Gültigkeit einer erhaltenen Nachricht kann durch das Durchführen der obengenannten Berechnung wieder dieses Mal mit dem statt zeroes hinzugefügten Kontrolle-Wert leicht nachgeprüft werden. Der Rest sollte Null gleichkommen, wenn es keine feststellbaren Fehler gibt.

11010011101100 100

Mathematik von CRC

Die mathematische Analyse dieses einer Abteilung ähnlichen Prozesses offenbart, wie man einen Teiler aufpickt, der gute Fehlerentdeckungseigenschaften versichert. In dieser Analyse wird von den Ziffern der Bit-Schnuren als die Koeffizienten eines Polynoms in einigen variablen X-Koeffizienten gedacht, die Elemente des begrenzten Feld-GF (2), statt vertrauterer Zahlen sind. Dieses binäre Polynom wird als ein Ring behandelt. Ein Ring, ist lose das Sprechen, eine Reihe von Elementen etwas wie Zahlen, mit einer Operationsähnlichkeitshinzufügung und einer Operationsähnlichkeitsmultiplikation. Diese Operationen besitzen viele der vertrauten arithmetischen Eigenschaften von commutativity, associativity, und distributivity. Ringtheorie ist ein Teil der abstrakten Algebra.

Das Entwerfen CRC Polynome

Die Auswahl am Generator-Polynom ist der wichtigste Teil, den CRC Algorithmus durchzuführen. Das Polynom muss gewählt werden, um die fehlerentdeckenden Fähigkeiten zu maximieren, während man gesamte Kollisionswahrscheinlichkeiten minimiert.

Das wichtigste Attribut des Polynoms ist seine Länge (größter Grad (Hochzahl) +1 irgendwelchen Begriffes im Polynom) wegen seines direkten Einflusses auf die Länge des geschätzten Kontrolle-Werts.

Die meistens verwendeten polynomischen Längen sind:

• 9 Bit (CRC-8)
• 17 Bit (CRC-16)
• 33 Bit (CRC-32)
• 65 Bit (CRC-64)

Das Design des CRC Polynoms hängt von der maximalen Gesamtlänge des Blocks ab, der (Daten + CRC Bit), die gewünschten Fehlerschutzeigenschaften und der Typ von Mitteln zu schützen ist, für den CRC, sowie die gewünschte Leistung durchzuführen. Ein häufiger Irrtum ist, dass die "besten" CRC Polynome entweder aus einem nicht zu vereinfachenden Polynom oder nicht zu vereinfachende polynomische Zeiten der Faktor abgeleitet werden, der zum Code die Fähigkeit hinzufügt, alle Fehler zu entdecken, eine ungerade Zahl von Bit betreffend. In Wirklichkeit sollten alle Faktoren, die oben beschrieben sind, in der Auswahl am Polynom hereingehen. Jedoch kann die Auswahl eines nicht zu nichtvereinfachenden Polynoms auf verpasste Fehler, wegen hinauslaufen, dass der Ring Nullteiler hat.

Der Vorteil, ein primitives Polynom als der Generator für einen CRC-Code zu wählen, besteht darin, dass der resultierende Code maximale Gesamtblock-Länge hat. Wenn r der Grad des primitiven Generator-Polynoms ist, dann ist die maximale Gesamtblock-Länge, und der verbundene Code ist im Stande, irgendwelche Fehler des einzelnen Bit oder doppelten Bit zu entdecken. Wir können diese Situation verbessern. Wenn wir das Generator-Polynom verwenden, wo ein primitives Polynom des Grads ist, dann ist die maximale Gesamtblock-Länge, und der Code ist im Stande, einzelne, doppelte und dreifache Fehler zu entdecken.

Ein Polynom, das anderen factorizations zulässt, kann dann gewählt werden, um den maximalen ganzen blocklength mit einer gewünschten Fehlerentdeckungsmacht zu erwägen. Die BCH-Codes sind eine starke Klasse solcher Polynome. Sie ordnen die zwei Beispiele oben unter. Unabhängig von den reducibility Eigenschaften eines Generator-Polynoms des Grads r, wenn es "+1" Begriff einschließt, wird der Code im Stande sein, Fehlermuster zu entdecken, die auf ein Fenster von r aneinander grenzenden Bit beschränkt werden. Diese Muster werden "Fehlerbrüche" genannt.

Spezifizierung von CRC

Das Konzept des CRC als ein Fehlererkennungscode wird kompliziert, wenn implementer- oder Standardkomitee es in ein praktisches System verwandelt. Hier sind einige der Komplikationen:

• Manchmal eine Durchführung Präfixe ein festes Bit-Muster zum zu überprüfenden bitstream. Das ist nützlich, als das Abstoppen von Fehlern 0 Bit vor einer Nachricht, eine Modifizierung einfügen könnte, die den Kontrolle-Wert unverändert sonst verlassen würde.
• Manchmal hängt eine Durchführung n 0 Bit (n an die Größe des CRC zu sein), zum zu überprüfenden bitstream, bevor die polynomische Abteilung vorkommt. Das hat die Bequemlichkeit, dass der Rest des ursprünglichen bitstream mit dem angehangenen Kontrolle-Wert genau Null ist, so kann der CRC einfach durch das Durchführen der polynomischen Abteilung auf dem erhaltenen bitstream und das Vergleichen des Rests mit der Null überprüft werden.
• Manchmal eine Durchführung exklusiv-ORs ein festes Bit-Muster in den Rest der polynomischen Abteilung.
• Bit-Ordnung: Einige Schemas sehen das Bit der niedrigen Ordnung jedes Bytes als "zuerst" an, das dann während der polynomischen Abteilung "leftmost" bedeutet, der gegen unser übliches Verstehen "der niedrigen Ordnung" ist. Diese Tagung hat Sinn, wenn Serienhafen-Übertragungen Hardware CRC-eingecheckt werden, weil eine weit verbreitete Serienhafen-Übertragungsvereinbarung Bytes am wenigsten - bedeutendes Bit zuerst übersendet.
• Byte-Ordnung: Mit dem Mehrbyte CRCs kann es zu Ende Verwirrung geben, ob das Byte zuerst übersandt hat (oder im am niedrigsten gerichteten Byte des Gedächtnisses versorgt hat), ist meist - bedeutendes Byte (LSB) oder die meisten - bedeutendes Byte (MSB). Zum Beispiel tauschen CRC ungefähr 16 Bit Schemas die Bytes des Kontrolle-Werts.
• Weglassung des Bit der hohen Ordnung des Teiler-Polynoms: Seitdem die hohe Ordnung gebissen hat, ist immer 1, und seit einem N-Bit muss CRC durch (n+1) - Bit-Teiler definiert werden, der ein N-Bit-Register überflutet, nehmen einige Schriftsteller an, dass es unnötig ist zu erwähnen, dass die hohe Ordnung des Teilers gebissen hat.
• Weglassung des Bit der niedrigen Ordnung des Teiler-Polynoms: Seitdem die niedrige Ordnung gebissen hat, ist immer 1, Autoren wie Philip Koopman vertreten Polynome mit ihrem Bit der hohen Ordnung intakt, aber ohne die niedrige Ordnung hat (oder 1 Begriff) gebissen. Diese Tagung verschlüsselt das Polynom, das mit seinem Grad in einer ganzer Zahl abgeschlossen ist.

Diese Komplikationen bedeuten, dass es drei allgemeine Weisen gibt, ein Polynom als eine ganze Zahl auszudrücken: Die ersten zwei, die Spiegelimages in der Dualzahl sind, sind die im Code gefundenen Konstanten; das dritte ist die in den Zeitungen von Koopman gefundene Zahl. In jedem Fall wird ein Begriff weggelassen. So kann das Polynom als abgeschrieben werden:

• 0x3 = 0b0011, (der MSB-erste Code) vertretend
• 0xC = 0b1100, (der LSB-erste Code) vertretend
• 0x9 = 0b1001, (Notation von Koopman) vertretend

Im Tisch unten werden sie als gezeigt:

Allgemein verwendeter und standardisierter CRCs

Zahlreiche Varianten von zyklischen Redundanzprüfungen sind in technische Standards vereinigt worden. Keineswegs tut einen Algorithmus oder einen jedes Grads, passen jedem Zweck an; Koopman und Chakrabarty empfehlen, ein Polynom gemäß den Anwendungsvoraussetzungen und dem erwarteten Vertrieb von Nachrichtenlängen auszuwählen. Die Zahl von verschiedenem CRCs im Gebrauch hat Entwickler, eine Situation verwirrt, die sich Autoren bemüht haben zu richten. Es gibt drei Polynome hat für CRC-12, sechzehn widerstreitende Definitionen von CRC-16 und sechs von CRC-32 berichtet.

Die allgemein angewandten Polynome sind nicht die effizientesten möglichen. Zwischen 1993 und 2004, Koopman, haben Castagnoli und andere den Raum von Polynomen bis zu 16 Bit, und 24 und 32 Bit überblickt, Beispiele findend, die viel bessere Leistung (in Bezug auf die Entfernung von Hamming für eine gegebene Nachrichtengröße) haben als die Polynome von früheren Protokollen und das Veröffentlichen des besten von diesen mit dem Ziel, die Fehlerentdeckungskapazität von zukünftigen Standards zu verbessern. Insbesondere iSCSI und SCTP haben eines der Ergebnisse dieser Forschung, der CRC-32C (Castagnoli) Polynom angenommen.

Das Design des 32-Bit-Polynoms, das meistens durch Standardkörper, CRC-32-IEEE verwendet ist, war das Ergebnis einer gemeinsamen Anstrengung um das Laboratorium von Rom und die Luftwaffe Elektronische Systemabteilung durch Joseph Hammond, James Brown und Shyan-Shiang Liu vom Institut von Georgia für die Technologie und Kenneth Brayer von MITRE Corporation. Der frühste bekannte Anschein des 32-Bit-Polynoms war in ihren 1975-Veröffentlichungen: Technischer Bericht 2956 von Brayer für die MITRA, veröffentlicht im Januar und veröffentlicht für öffentliche Verbreitung durch DTIC im August, und Hammond, Brown und den Bericht von Liu für das Laboratorium von Rom, veröffentlicht im Mai. Beide Berichte haben Beiträge von der anderen Mannschaft enthalten. Im Dezember 1975 haben Brayer und Hammond ihre Arbeit in einer Zeitung auf der IEEE Nationalen Fernmeldekonferenz präsentiert: Der IEEE CRC-32 Polynom ist das Erzeugen-Polynom von einem Code von Hamming und wurde für seine Fehlerentdeckungsleistung ausgewählt. Trotzdem vergleicht der Castagnoli CRC-32C Polynom, das in iSCSI oder SCTP verwendet ist, seine Leistung auf Nachrichten von 58-Bit-Bis131kbits, und überbietet es in mehreren Größe-Reihen einschließlich der zwei allgemeinsten Größen des Internetpakets. Der ITU-T G.hn Standard verwendet auch CRC-32C, um Fehler in der Nutzlast zu entdecken (obwohl es CRC-16-CCITT für PHY Kopfbälle verwendet).

Der Tisch verzeichnet unten nur die Polynome der verschiedenen Algorithmen im Gebrauch. Schwankungen eines besonderen Protokolls können Vorinversion, Postinversion und umgekehrtes Bit auferlegen, wie beschrieben, oben bestellend. Zum Beispiel verwenden die CRC32, die sowohl in Gzip als auch in Bzip2 verwendet sind, dasselbe Polynom, aber Bzip2 verwendet umgekehrte Bit-Einrichtung, während Gzip nicht tut.

CRCs in Eigentumsprotokollen könnte einen nichttrivialen Anfangswert und endgültigen XOR für die Verfinsterung verwenden, aber das fügt kryptografische Kraft zum Algorithmus nicht hinzu. Ein unbekannter Fehlererkennungscode kann als ein CRC, und als solch völlig rückkonstruiert von seinen Produktionskennwörtern charakterisiert werden.

Siehe auch

• Berechnung von CRC
• Fehler, der Code korrigiert
• Zyklischer Code
• Überfülle-Kontrolle
• Liste von Kontrollsumme-Algorithmen
• Gleichheit
• Informationssicherheit
• Einfache Dateiüberprüfung
• cksum
• Kopfball-Fehlerkorrektur
• Adler-32
• Die Kontrollsumme des Pfeilmachers
• Mathematik von CRCs

Links

• MathPages - Zyklische Redundanzprüfungen: Übersicht mit einer Erklärung der Fehlerentdeckung von verschiedenen Polynomen.
• Reinigen Sie C ++ CRC32 Quellcode; OS und Bibliothek unabhängiger
• Der CRC Pitstop - nach Hause Eines Schmerzlosen Handbuches zu CRC Fehlerentdeckungsalgorithmen
• Schwarz, R. (1994-02) Schneller CRC32 in der Software; Algorithmus 4 wird in Linux und dem Schwirren des Info-Schwirrens verwendet, und aufgehen.
• Kounavis, M. und Beere, F. (2005). Eine Systematische Annäherung an das Gebäude Hoher Leistung, softwarebasiert, CRC Generatoren, Slicing-4 und slicing-8 Algorithmen
• pycrc - ein freier C/C ++ Quellcodegenerator für verschiedene CRC Algorithmen
• CRC32: Eine Kontrollsumme für eine Datei, C ++ Durchführung durch Brian Friesen erzeugend
• Der CRC ++ Projektdurchführung in C ++, der Schablone-Klassen verwendet, um sich mit verschiedener Bit-Ordnung zu befassen
• 'CRC-Analyse mit Bitfilters.
• Zyklische Redundanzprüfung: Theorie, Praxis, Hardware und Software mit der Betonung auf CRC-32. Ein Beispielkapitel von Henry S. Warren dem Jüngeren. Das Entzücken des Hackers.
• CRCs Code für CRC-32 und CRC-16 Berechnung im GRUNDLEGENDEN, 6502, Z80, PDP-11, 6809, 80x86, ARM und C.
• Rücktechnik ein CRC Algorithmus
• Übertreffen Sie Spreadsheet-Berechnung von CRC-16 IBM für modbus