CRC-32C Υπολογιστής κατακερματισμού κωδικού

Ο κυκλικός έλεγχος πλεονασμού (CRC) είναι ένας κωδικός ανίχνευσης σφαλμάτων που χρησιμοποιείται συνήθως για τον εντοπισμό τυχαίων αλλαγών σε ανεπεξέργαστα δεδομένα. Αν και δεν είναι τεχνικά κρυπτογραφική συνάρτηση κατακερματισμού, το CRC-32 αναφέρεται συχνά ως κατακερματισμός λόγω της ικανότητάς του να παράγει μια έξοδο σταθερού μεγέθους (32 bit) από είσοδο μεταβλητού μήκους. Η έκδοση που παρουσιάζεται σε αυτήν τη σελίδα είναι η παραλλαγή CRC-32C, η οποία είναι μια νεότερη, πιο «έξυπνη» (καλύτερη ανίχνευση σφαλμάτων) έκδοση που συχνά επιταχύνεται μέσω υλικού σε σύγχρονες CPU (μέσω SSE 4.2).

Πλήρης αποκάλυψη: Δεν έγραψα τη συγκεκριμένη υλοποίηση της συνάρτησης κατακερματισμού που χρησιμοποιείται σε αυτή τη σελίδα. Πρόκειται για μια τυπική συνάρτηση που περιλαμβάνεται στη γλώσσα προγραμματισμού PHP. Έφτιαξα μόνο τη διαδικτυακή διεπαφή για να την κάνω δημόσια διαθέσιμη εδώ για λόγους ευκολίας.

Σχετικά με τον αλγόριθμο κατακερματισμού CRC-32C

Δεν είμαι μαθηματικός, αλλά θα προσπαθήσω να εξηγήσω αυτή τη συνάρτηση κατακερματισμού με μια απλή αναλογία. Σε αντίθεση με πολλές από τις κρυπτογραφικές συναρτήσεις κατακερματισμού, δεν είναι ιδιαίτερα περίπλοκος αλγόριθμος, οπότε μάλλον θα είναι εντάξει ;-)

Φανταστείτε ότι στέλνετε ένα γράμμα ταχυδρομικώς, αλλά ανησυχείτε ότι μπορεί να καταστραφεί πριν φτάσει στον παραλήπτη. Με βάση το περιεχόμενο της επιστολής, υπολογίζετε ένα άθροισμα ελέγχου CRC-32 και το γράφετε στον φάκελο. Όταν ο παραλήπτης λάβει την επιστολή, μπορεί επίσης να υπολογίσει το άθροισμα ελέγχου και να δει αν ταιριάζει με αυτό που γράψατε. Εάν συμβαίνει, το γράμμα δεν έχει καταστραφεί ή αλλαχτεί στην πορεία.

Ο τρόπος με τον οποίο το CRC-32 το κάνει αυτό είναι μια διαδικασία τεσσάρων βημάτων:

Βήμα 1: Προσθέστε λίγο επιπλέον χώρο (γεμίσματος)

• Το CRC προσθέτει λίγο επιπλέον χώρο στο τέλος του μηνύματος (όπως να συσκευάζετε φιστίκια σε ένα κουτί).
• Αυτό το βοηθά να εντοπίζει πιο εύκολα τα σφάλματα.

Βήμα 2: Ο μαγικός χάρακας (Το πολυώνυμο)

• Το CRC-32 χρησιμοποιεί έναν ειδικό «μαγικό χάρακα» για τη μέτρηση των δεδομένων.
  • Σκεφτείτε αυτόν τον χάρακα σαν ένα σχέδιο από εξογκώματα και αυλακώσεις (αυτό είναι το πολυώνυμο, αλλά μην ανησυχείτε για αυτή τη λέξη).
  • Ο πιο συνηθισμένος "χάρακας" για το CRC-32 είναι ένα σταθερό σχέδιο.

Βήμα 3: Ολίσθηση του χάρακα (Διαδικασία διαίρεσης)

• Τώρα το CRC σύρει τον χάρακα κατά μήκος του μηνύματος.
  • Σε κάθε σημείο, ελέγχει εάν τα χτυπήματα και οι αυλακώσεις ευθυγραμμίζονται.
  • Εάν δεν ευθυγραμμιστούν, το CRC σημειώνει (αυτό γίνεται χρησιμοποιώντας απλό XOR, όπως το άνοιγμα ή το κλείσιμο των διακοπτών).
  • Συνεχίζει να γλιστράει και να γυρίζει τους διακόπτες μέχρι να φτάσει στο τέλος.

Βήμα 4: Το τελικό αποτέλεσμα (το άθροισμα ελέγχου)

• Αφού σύρετε τον χάρακα σε ολόκληρο το μήνυμα, θα έχετε έναν μικρό αριθμό (μήκους 32 bit) που αντιπροσωπεύει τα αρχικά δεδομένα.
  • Αυτός ο αριθμός είναι σαν ένα μοναδικό δακτυλικό αποτύπωμα για το μήνυμα.
  • Αυτό είναι το άθροισμα ελέγχου CRC-32.

Η έκδοση που παρουσιάζεται στη σελίδα είναι η παραλλαγή CRC-32C, η οποία θα πρέπει να είναι η προτιμώμενη παραλλαγή, ειδικά εάν χρησιμοποιείτε μια CPU με επιτάχυνση υλικού (SSE 4.2 και νεότερη έκδοση) και δεν χρειάζεστε συμβατότητα με άλλες παραλλαγές.

Έχω αριθμομηχανές και για τις άλλες παραλλαγές:

• CRC-32 Υπολογιστής κατακερματισμού κωδικού
• CRC-32B Υπολογιστής κωδικού κατακερματισμού