Οι γραμμές έχουν τη μορφή «ALGORITHM value» ακολουθούμενη από γραμμή παραμέτρων με εσοχή, ώστε ένα αντιγραμμένο αποτέλεσμα να δηλώνει πάντα ποιο σύνολο παραμέτρων το παρήγαγε.
CRC — έλεγχος κυκλικής πλεονασματικότητας, από την αρχή
Σε μία πρόταση: ένα CRC αντιμετωπίζει τα δεδομένα ως έναν τεράστιο δυαδικό αριθμό, τον διαιρεί με έναν σταθερό αριθμό «γεννήτορα» χρησιμοποιώντας XOR αντί για αφαίρεση και αναφέρει το υπόλοιπο — ένα συμπαγές αποτύπωμα που αλλάζει δραστικά ακόμη και όταν αναστρέφεται ένα bit της εισόδου, γι' αυτό κάθε τι, από αρχεία PNG μέχρι καλώδια Modbus, το φέρει.
Τι είναι πραγματικά ένα CRC
Η εικόνα της διαίρεσης. Τοποθέτηση των byte σε μία μακριά δυαδική σειρά ως έναν αριθμό. Επιλέγεται ένας διαιρέτης — το πολυώνυμο, π.χ. 0x04C11DB7 για το CRC-32. Εκτελείται δυαδική διαίρεση μακράς μορφής όπου η «αφαίρεση» είναι η πράξη XOR: όποτε το πρώτο bit του τρέχοντος υπολοίπου είναι 1, γίνεται XOR με τον διαιρέτη, μετατοπίζεται αριστερά και επαναλαμβάνεται. Μετά τη διέλευση ολόκληρου του μηνύματος, ό,τι μένει στον καταχωρητή είναι το CRC. Κανένα κλειδί, καμία πίνακα στον ορισμό — μόνο διαίρεση με υπόλοιπο.
Οι πέντε παράμετροι. Δύο συστήματα μπορεί να λένε και τα δύο «CRC-32» και να διαφωνούν, επειδή το όνομα από μόνο του δεν καθορίζει τίποτα. Η πλήρης συνταγή χρειάζεται πέντε τιμές: poly (ο διαιρέτης), init (με τι ξεκινά ο καταχωρητής — τα μηδενικά αφήνουν τα αρχικά μηδενικά byte να εξαφανιστούν, τα μονάδες όχι), refin/refout (αν κάθε byte εισόδου — και ο τελικός καταχωρητής — αντιστρέφεται ως προς τα bit, κατάλοιπο των σειριακών υλικών που έστελναν πρώτα το λιγότερο σημαντικό bit), και xorout (τελική μάσκα XOR, ώστε μια σειρά από τελικά μηδενικά να αλλάζει ακόμη την απάντηση). Η σελίδα εκτυπώνει και τις πέντε δίπλα σε κάθε αποτέλεσμα ακριβώς για αυτόν τον λόγο.
Γιατί ανιχνεύει σφάλματα. Ένας καλά επιλεγμένος διαιρέτης κάνει το υπόλοιπο ενός μηνύματος και το υπόλοιπο του ίδιου μηνύματος με λίγα αναστραμμένα bit να διαφέρουν με συντριπτική πιθανότητα: ένα καλό CRC-32 πιάνει όλα τα σφάλματα 1 και 2 bit, όλους τους περιττούς αριθμούς σφαλμάτων bit και κάθε έκρηξη έως 32 διαδοχικών αλλοιωμένων bit — εγγυημένα, όχι πιθανοτικά. Η εγγύηση αφορά την τυχαία αλλοίωση, και αυτό καθιστά τα CRC το σωστό εργαλείο για θορυβώδη καλώδια και αναξιόπιστους δίσκους.
Τι δεν είναι ένα CRC
Όχι κρυπτογραφικό hash. Δεν υπάρχει μυστικό και δεν υπάρχει μονοδρομικότητα: όποιος γνωρίζει τις παραμέτρους μπορεί να πλαστογραφήσει μήνυμα με οποιοδήποτε CRC θέλει, σε χιλιοστά του δευτερολέπτου, προσθέτοντας τέσσερα διορθωτικά byte. Το CRC ανιχνεύει ατυχήματα, ποτέ αντιπάλους. Για λήψεις που επαληθεύονται έναντι αγνώστων, οι υπογραφές έχουν σημασία — βλ. τη Γεννήτρια κατακερματισμού (MD5/SHA/BLAKE2) αντί γι' αυτό. Η σελίδα εξηγεί επίσης γιατί τα MD5 και SHA-1 έχουν αποσυρθεί σε εχθρικά περιβάλλοντα, ενώ το SHA-256 παραμένει.
Όχι κώδικας διόρθωσης σφαλμάτων. Ένα CRC δείχνει ότι κάτι άλλαξε, όχι τι άλλαξε. Η επιδιόρθωση σφαλμάτων εν κινήσει είναι δουλειά κωδίκων όπως οι Reed–Solomon ή Hamming, που αποθηκεύουν σκόπιμα πλεονάζουσα δομή την οποία ένας αποκωδικοποιητής μπορεί να αντιστρέψει.
Ούτε συμπίεση ούτε κρυπτογράφηση. Το υπόλοιπο είναι μερικά byte ανεξαρτήτως μεγέθους εισόδου, και από αυτό δεν μπορεί να ανακτηθεί η είσοδος — αλλά, σε αντίθεση με ένα κρυπτογραφικό hash, αυτό οφείλεται απλώς στο ότι απορρίφθηκε πληροφορία, όχι στο ότι η αντιστροφή είναι δύσκολη.
Οι οικογένειες αυτής της σελίδας
Τα τετράδυμα του CRC-32. Τέσσερις από τις εγγραφές αυτής της σελίδας μοιράζονται το πολυώνυμο 0x04C11DB7 και παράγουν ακόμη διαφορετικές τιμές: το ISO-HDLC (αντεστραμμένο, init/xorout όλα μονάδες) είναι «το» CRC-32 των zlib, gzip, PNG και ZIP· το BZIP2 είναι η ίδια μαθηματική χωρίς αντιστροφή· το MPEG-2 είναι το BZIP2 χωρίς τελικό XOR· το POSIX ξεκινά από το μηδέν και είναι η βάση της εντολής cksum (που επιπλέον προσθέτει το μήκος του αρχείου στη διαίρεση, οπότε το cksum ενός αρχείου και το CRC-32/POSIX των ίδιων byte διαφέρουν). Το CRC-32C (Castagnoli, πολυώνυμο 0x1EDC6F41) είναι το πέμπτο αδέλφι: διαφορετικό πολυώνυμο επιλεγμένο για καλύτερη απόδοση ανίχνευσης σφαλμάτων, και αυτό που οι σύγχρονες CPU x86 και ARM μπορούν να υπολογίσουν με ταχύτητα μνήμης με μία εντολή.
Το τετράδυμο του CRC-64. Το XZ χρησιμοποιεί το πολυώνυμο ECMA-182 σε αντεστραμμένη μορφή με init και xorout όλα μονάδες· το ίδιο το ECMA-182 είναι το μη αντεστραμμένο αρχικό με μηδενικό init από το πρότυπο ταινίας DLT-1· το GO-ISO είναι το crc64.ISO της Go, με μικρό πολυώνυμο 0x1B, αντεστραμμένο ακόμη· το REDIS χρησιμοποιεί πολυώνυμο επιλεγμένο για καλή αλλαγή συνδυασμού στην ανάθεση θέσεων κατακερματισμού. Τα εξήντα τέσσερα bit είναι το μέγεθος όπου τα CRC αρχίζουν να χρησιμοποιούνται ως συναρτήσεις κατακερματισμού (κατανομή σε κάδους) και όχι ως καθαρά checksums.
Το Adler-32 είναι το ξένο: δεν είναι καθόλου διαίρεση. Αθροίζει τα byte (A, ξεκινώντας από 1) και αθροίζει τα αθροίσματα (B), και τα δύο modulo 65521, και συνενώνει τα δύο αθροίσματα των 16 bit. Είναι ταχύτερο από το CRC-32 σε λογισμικό, και το zlib το χρησιμοποιεί για ροές deflate — αλλά για σύντομες εισόδους (κάτω από μερικές εκατοντάδες byte) το άθροισμα μεταφέρει πολύ λίγη πληροφορία, ακριβώς γι' αυτό το zlib επιστρέφει στο CRC-32 για μικρά μπλοκ.
Το CRC-8 και το CRC-16 επιβιώνουν όπου τα byte είναι ακριβά: το CRC-8/CCITT (πολυώνυμο 0x07) προστατεύει μεμονωμένα byte επικεφαλίδας σε πρωτόκολλα SMBus και κινητής ραδιοεπικοινωνίας· το CRC-16/CCITT-FALSE φυλάσσει μπλοκ έξυπνων καρτών· το CRC-16/MODBUS είναι το checksum κάθε πλαισίου Modbus RTU σε εργοστασιακούς χώρους σε όλο τον κόσμο.
Πού χρησιμοποιείται το καθένα
| Σύνολο παραμέτρων | Βρίσκεται σε |
|---|
| CRC-32/ISO-HDLC | zlib, gzip, PNG, ZIP, Ethernet (FCS), πολλές μορφές αρχειοθέτησης |
| CRC-32C | iSCSI, ext4, btrfs, ZFS, εντολή υλικού CRC32C των SSE4.2/ARMv8 |
| CRC-32/BZIP2 | Ροή αρχείου .bz2 |
| CRC-32/MPEG-2 | Ροές μεταφοράς MPEG-2 |
| CRC-32/POSIX & cksum | Έξοδος εντολής POSIX cksum (cksum file.txt) |
| CRC-16/MODBUS | Πλαίσια Modbus RTU (βιομηχανικά PLC, μετρητές, inverters) |
| CRC-16/CCITT-FALSE | έξυπνες κάρτες, σύνδεσμοι συγγενείς με X.25, ορισμένα πρωτόκολλα GPS |
| CRC-8/CCITT | SMBus (byte PEC), επικεφαλίδες κινητής ραδιοεπικοινωνίας |
| CRC-64/XZ | Έλεγχοι ακεραιότητας κοντέινερ .xz |
| CRC-64/ECMA-182 | ECMA-182 / πρότυπο ταινίας DLT-1 |
| CRC-64/GO-ISO | Τυπική βιβλιοθήκη Go crc64.ISO |
| CRC-64/REDIS | Ανάθεση θέσεων κατακερματισμού στο cluster Redis |
| Adler-32 | Ροές zlib (deflate), άλλα περιβάλλοντα γρήγορου checksum |
Ο πίνακας αναφοράς — check(«123456789»)
Η σύμβαση του καταλόγου CRC είναι να δημοσιεύεται το αποτέλεσμα για τη συμβολοσειρά ASCII 123456789 (9 byte). Κάθε τιμή παρακάτω αναπαράγεται σε αυτή τη σελίδα: με πληκτρολόγηση του 123456789 στο πλαίσιο Κείμενο, επιλογή του αλγορίθμου και εκτέλεση του Υπολογισμός.
| Σύνολο παραμέτρων | Πλάτος | Τιμή ελέγχου (hex) |
|---|
| CRC-8/CCITT | 8 | 0xf4 |
| CRC-16/CCITT-FALSE | 16 | 0x29b1 |
| CRC-16/MODBUS | 16 | 0x4b37 |
| CRC-32/ISO-HDLC | 32 | 0xcbf43926 |
| CRC-32C | 32 | 0xe3069283 |
| CRC-32/BZIP2 | 32 | 0xfc891918 |
| CRC-32/MPEG-2 | 32 | 0x0376e6e7 |
| CRC-32/POSIX | 32 | 0x765e7680 |
| cksum (POSIX command) | 32 | 0x377a6011 |
| CRC-64/XZ | 64 | 0x995dc9bbdf1939fa |
| CRC-64/ECMA-182 | 64 | 0x6c40df5f0b497347 |
| CRC-64/GO-ISO | 64 | 0xb90956c775a41001 |
| CRC-64/REDIS | 64 | 0xe9c6d914c4b8d9ca |
| Adler-32 | 32 | 0x091e01de |
Πηγές: κάθε τιμή διασταυρώθηκε με ανεξάρτητη bitwise υλοποίηση αναφοράς και, όπου υπάρχει, με τη βιβλιοθήκη του συστήματος που περιλαμβάνει τον αλγόριθμο (zlib για CRC-32 και Adler-32· ο κατάλογος CRC του Greg Cook για τα υπόλοιπα).
Συνηθισμένα λάθη
- «CRC-32» χωρίς παραμέτρους. Μεταξύ των ISO-HDLC, BZIP2, MPEG-2, POSIX και CRC-32C, πέντε διαφορετικές τιμές κυκλοφορούν με το ίδιο όνομα. Να καταγράφονται πάντα τα poly/init/refin/refout/xorout μαζί με το αποτέλεσμα — αυτή η σελίδα τα εκτυπώνει για λογαριασμό του χρήστη.
- Σύγκριση του CRC-32 αρχείου με την έξοδο
cksum. Διαφορετικοί αλγόριθμοι: το cksum προσθέτει το μήκος και χρησιμοποιεί διαφορετικό init. Οι αριθμοί δεν θα ταιριάξουν, και τα δύο είναι «σωστά».
- Εμπιστοσύνη στο CRC ενάντια στην παραποίηση. Η πλαστογράφηση ενός ταιριαστού CRC είναι κλασική άσκηση (διόρθωση των τελευταίων 4 byte). Όταν ο άλλος αποδέκτης μπορεί να είναι εχθρικός, χρησιμοποιείται κλειδωμένος MAC (HMAC) ή υπογραφή.
- Αναμονή για αλλαγή συνδυασμού (avalanche). Το CRC είναι γραμμικό: σχετικά μηνύματα δίνουν σχετικά CRC. Κατάλληλο για θόρυβο, λάθος για κατακερματισμό — αν χρειάζεται κατανομή σε κάδους, το CRC-64 ή ένα πραγματικό hash είναι ασφαλέστερο από το CRC-32.
- Κείμενο σε hex έναντι byte. Η συμβολοσειρά
"123456789" (9 byte ASCII, 31 32 33 34 35 36 37 38 39) και ο αριθμός 0x123456789 είναι διαφορετικές είσοδοι με διαφορετικά CRC. Χρησιμοποιείται η καρτέλα Δεκαεξαδικά byte όταν τα πηγαία δεδομένα είναι πραγματικά δυαδικά.
Συχνές ερωτήσεις
Γιατί το CRC-32 δεν ταιριάζει με αυτό του αρχείου ZIP; Το CRC-32 του ZIP είναι ISO-HDLC πάνω στα ασυμπίεστα δεδομένα. Να βεβαιωνόμαστε ότι κατακερματίστηκαν τα ίδια byte (όχι η συμπιεσμένη ροή), η ίδια λειτουργία (Κείμενο ή Hex) και το ίδιο σύνολο παραμέτρων — η γραμμή παραμέτρων που εκτυπώνεται κάτω από κάθε αποτέλεσμα υπάρχει για να γίνεται ο έλεγχος αμέσως.
Ποιο είναι καλύτερο, το CRC-32C ή το CRC-32; Για την ανίχνευση τυχαίων σφαλμάτων και τα δύο πιάνουν όλα τα εκρήξεις έως 32 bit· το CRC-32C αποδίδει καλύτερα σε ορισμένα μοτίβα σφαλμάτων και είναι αυτό με εντολές CPU — ουσιαστικά δωρεάν στις ταχύτητες gigabit. Ο λόγος που επιβιώνει το CRC-32/ISO-HDLC είναι η συμβατότητα: τριάντα χρόνια αρχείων το μιλούν.
Είναι το CRC-64 ισχυρότερο από το CRC-32; Ανιχνεύει μεγαλύτερες εκρήξεις (έως 64 bit) και συγκρούεται πολύ λιγότερο όταν χρησιμοποιείται για κατανομή σε κάδους, αλλά είναι εξίσου πλαστογραφήσιμο — το πλάτος αγοράζει εγγυήσεις ανίχνευσης, όχι ασφάλεια.
Μπορεί ένα CRC να αντιστραφεί για να αποκαλυφθεί η είσοδος; Όχι — άπειρες είσοδοι μοιράζονται ένα CRC. Αλλά, σε αντίθεση με ένα κρυπτογραφικό hash, ένας επιτιθέμενος μπορεί να κατασκευάσει είσοδο με οποιοδήποτε CRC επιλέξει, και σε αυτή την έννοια δεν είναι καθόλου μονόδρομο.
