Όπως πιστεύω, πολλοί γνωρίζουν ότι από το 2007 το Εθνικό Ινστιτούτο Προτύπων και Τεχνολογίας των ΗΠΑ (NIST) διοργανώνει έναν διαγωνισμό για την ανάπτυξη ενός αλγορίθμου κατακερματισμού που θα αντικαταστήσει τον SHA-1 και μια οικογένεια αλγορίθμων SHA-2. Ωστόσο, αυτό το θέμα, για κάποιο λόγο, στερείται προσοχής στον ιστότοπο. Αυτό είναι στην πραγματικότητα που με έφερε κοντά σας. Φέρνω στην προσοχή σας μια σειρά άρθρων σχετικά με τους αλγόριθμους κατακερματισμού. Σε αυτόν τον κύκλο, θα μελετήσουμε μαζί τα βασικά των συναρτήσεων κατακερματισμού, θα εξετάσουμε τους πιο διάσημους αλγόριθμους κατακερματισμού, θα βουτήξουμε στην ατμόσφαιρα του διαγωνισμού SHA-3 και θα εξετάσουμε τους αλγόριθμους που ισχυρίζονται ότι τον κερδίζουν, σίγουρα θα τους δοκιμάσουμε. Επίσης, εάν είναι δυνατόν, θα ληφθούν υπόψη τα ρωσικά πρότυπα κατακερματισμού.
Για τον εαυτό μου
Φοιτητής του Τμήματος Ασφάλειας Πληροφοριών.Σχετικά με το κατακερματισμό
Επί του παρόντος, σχεδόν καμία εφαρμογή κρυπτογραφίας δεν είναι ολοκληρωμένη χωρίς τη χρήση κατακερματισμού.Οι συναρτήσεις κατακερματισμού είναι συναρτήσεις που έχουν σχεδιαστεί για να "συμπιέζουν" ένα αυθαίρετο μήνυμα ή σύνολο δεδομένων, συνήθως γραμμένων στο δυαδικό αλφάβητο, σε κάποιο μοτίβο bit σταθερού μήκους που ονομάζεται συνέλιξη. Οι συναρτήσεις κατακερματισμού έχουν μια ποικιλία εφαρμογών κατά τη διεξαγωγή στατιστικών πειραμάτων, κατά τη δοκιμή λογικών συσκευών, κατά τη δημιουργία αλγορίθμων για γρήγορη αναζήτηση και τον έλεγχο της ακεραιότητας των εγγραφών σε βάσεις δεδομένων. Η κύρια απαίτηση για τις συναρτήσεις κατακερματισμού είναι η ομοιομορφία της κατανομής των τιμών τους με μια τυχαία επιλογή τιμών ορίσματος.
Μια συνάρτηση κατακερματισμού κρυπτογράφησης είναι οποιαδήποτε συνάρτηση κατακερματισμού που είναι κρυπτογραφικά ασφαλής, δηλαδή, ικανοποιεί ορισμένες απαιτήσεις ειδικά για κρυπτογραφικές εφαρμογές. Στην κρυπτογραφία, οι συναρτήσεις κατακερματισμού χρησιμοποιούνται για την επίλυση των ακόλουθων προβλημάτων:
- κατασκευή συστημάτων ελέγχου ακεραιότητας δεδομένων κατά τη μετάδοση ή την αποθήκευση τους,
- έλεγχος ταυτότητας πηγής δεδομένων.
Συνάρτηση κατακερματισμού είναι οποιαδήποτε συνάρτηση h:X -> Y, εύκολα υπολογίσιμο και τέτοιο ώστε για οποιοδήποτε μήνυμα Μέννοια h(M) = H (συνέλιξη)έχει σταθερό μήκος bit. Χ- σύνολο όλων των μηνυμάτων, Υ- σύνολο δυαδικών διανυσμάτων σταθερού μήκους.
Κατά κανόνα, οι συναρτήσεις κατακερματισμού χτίζονται με βάση τις λεγόμενες συναρτήσεις συστολής ενός βήματος y \u003d f (x 1, x 2)δύο μεταβλητές, όπου x 1, x2και y- δυαδικά διανύσματα μήκους Μ, nκαι nαντίστοιχα, και nείναι το μήκος της συνέλιξης και Μ- μήκος μπλοκ μηνυμάτων.
Για να πάρετε την αξία h(M)το μήνυμα αρχικά χωρίζεται σε μπλοκ μήκους Μ(Ταυτόχρονα, εάν το μήκος του μηνύματος δεν είναι πολλαπλάσιο του Μτότε το τελευταίο μπλοκ συμπληρώνεται με κάποιον ειδικό τρόπο στο πλήρες) και μετά στα ληφθέντα μπλοκ M 1 , M 2 ,.., M Nεφαρμόστε την ακόλουθη διαδοχική διαδικασία για τον υπολογισμό της συνέλιξης:
H o \u003d v,
H i = f(M i,H i-1), i = 1,.., N,
h(M) = H N
Εδώ v- κάποια σταθερά, συχνά ονομάζεται διάνυσμα αρχικοποίησης. Βγαίνει έξω
για διάφορους λόγους και μπορεί να είναι μια μυστική σταθερά ή ένα σύνολο τυχαίων δεδομένων (μια επιλογή ημερομηνίας και ώρας, για παράδειγμα).
Με αυτήν την προσέγγιση, οι ιδιότητες της συνάρτησης κατακερματισμού καθορίζονται πλήρως από τις ιδιότητες της συνάρτησης συστολής ενός βήματος.
Υπάρχουν δύο σημαντικοί τύποι κρυπτογραφικών συναρτήσεων κατακερματισμού - με κλειδί και χωρίς κλειδί. Οι συναρτήσεις κατακερματισμού κλειδιών ονομάζονται κωδικοί ελέγχου ταυτότητας μηνυμάτων. Επιτρέπουν τη διασφάλιση χωρίς πρόσθετα μέσα τόσο της ορθότητας της πηγής δεδομένων όσο και της ακεραιότητας των δεδομένων σε συστήματα με αμοιβαία αξιόπιστους χρήστες.
Οι συναρτήσεις κατακερματισμού χωρίς κλειδί ονομάζονται κωδικοί ανίχνευσης σφαλμάτων. Καθιστούν δυνατή με τη βοήθεια πρόσθετων μέσων (κρυπτογράφηση, για παράδειγμα) την εγγύηση της ακεραιότητας των δεδομένων. Αυτές οι συναρτήσεις κατακερματισμού μπορούν να χρησιμοποιηθούν σε συστήματα τόσο με έμπιστους όσο και με μη αξιόπιστους χρήστες.
Σχετικά με τις στατιστικές ιδιότητες και απαιτήσεις
Όπως είπα, η κύρια απαίτηση για τις συναρτήσεις κατακερματισμού είναι η ομοιόμορφη κατανομή των τιμών τους με μια τυχαία επιλογή τιμών ορίσματος. Για κρυπτογραφικές συναρτήσεις κατακερματισμού, είναι επίσης σημαντικό ότι με την παραμικρή αλλαγή στο όρισμα, η τιμή της συνάρτησης αλλάζει πολύ. Αυτό ονομάζεται φαινόμενο χιονοστιβάδας.
Προς την βασικές λειτουργίεςο κατακερματισμός έχει τις ακόλουθες απαιτήσεις:
- η αδυναμία κατασκευής,
- η αδυναμία τροποποίησης.
Η πρώτη απαίτηση σημαίνει ότι είναι πολύ δύσκολο να αντιστοιχίσετε ένα μήνυμα με τη σωστή τιμή διπλώματος. Το δεύτερο είναι η υψηλή πολυπλοκότητα της αντιστοίχισης για ένα δεδομένο μήνυμα με μια γνωστή τιμή διπλώματος άλλου μηνύματος με τη σωστή τιμή διπλώματος.
Οι απαιτήσεις για τις λειτουργίες χωρίς κλειδί είναι:
- μονής κατεύθυνσης,
- αντίσταση σε συγκρούσεις,
- αντίσταση στην εύρεση του δεύτερου πρωτοτύπου.
Η μονοκατευθυντικότητα νοείται ως η υψηλή πολυπλοκότητα της εύρεσης ενός μηνύματος από μια δεδομένη τιμή συνέλιξης. Πρέπει να σημειωθεί ότι στις αυτή τη στιγμήδεν υπάρχουν λειτουργίες κατακερματισμού σε χρήση με αποδεδειγμένη μονόδρομη χρήση.
Η αντίσταση σύγκρουσης νοείται ως η δυσκολία εύρεσης ενός ζεύγους μηνυμάτων με τις ίδιες τιμές διπλώματος. Συνήθως, είναι η εύρεση ενός τρόπου κατασκευής συγκρούσεων από κρυπτοαναλυτές που χρησιμεύει ως το πρώτο σήμα της απαρχαιότητας του αλγορίθμου και της ανάγκης για γρήγορη αντικατάστασή του.
Η αντίσταση στην εύρεση της δεύτερης προεικόνας νοείται ως η δυσκολία εύρεσης ενός δεύτερου μηνύματος με την ίδια τιμή αναδίπλωσης για ένα δεδομένο μήνυμα με μια γνωστή τιμή διπλώματος.
Αυτό ήταν το θεωρητικό μέρος, που θα μας φανεί χρήσιμο στο μέλλον...
Σχετικά με τους δημοφιλείς αλγόριθμους κατακερματισμού
Αλγόριθμοι CRC16/32- άθροισμα ελέγχου (όχι κρυπτογραφική μετατροπή).
Αλγόριθμοι MD2/4/5/6. Είναι δημιούργημα του Ron Rivest, ενός εκ των συγγραφέων του αλγορίθμου RSA.
Ο αλγόριθμος MD5 ήταν κάποτε πολύ δημοφιλής, αλλά οι πρώτες προϋποθέσεις για το hacking εμφανίστηκαν στα τέλη της δεκαετίας του '90 και τώρα η δημοτικότητά του μειώνεται ραγδαία.
Ο αλγόριθμος MD6 είναι ένας πολύ ενδιαφέρων αλγόριθμος από εποικοδομητική άποψη. Προτάθηκε για το διαγωνισμό SHA-3, αλλά, δυστυχώς, οι συγγραφείς δεν κατάφεραν να το φέρουν στο πρότυπο και αυτός ο αλγόριθμος δεν βρίσκεται στη λίστα των υποψηφίων που πέρασαν στον δεύτερο γύρο.
Αλγόριθμοι χάρακα SHAΑλγόριθμοι που χρησιμοποιούνται ευρέως σήμερα. Υπάρχει μια ενεργή μετάβαση από τα πρότυπα έκδοσης SHA-1 σε SHA-2. Το SHA-2 είναι το συλλογικό όνομα για τους αλγόριθμους SHA224, SHA256, SHA384 και SHA512. Τα SHA224 και SHA384 είναι ουσιαστικά ανάλογα των SHA256 και SHA512, αντίστοιχα, μόνο αφού υπολογιστεί η συνέλιξη, ορισμένες από τις πληροφορίες σε αυτήν απορρίπτονται. Θα πρέπει να χρησιμοποιούνται μόνο για τη διασφάλιση της συμβατότητας με παλαιότερα μοντέλα εξοπλισμού.
Ρωσικό πρότυπο - GOST 34.11-94.
Στο επόμενο άρθρο
Επισκόπηση αλγορίθμων MD (MD4, MD5, MD6).
Βιβλιογραφία
A. P. Alferov, Βασικές αρχές της κρυπτογραφίας.
Bruce Schneier, Εφαρμοσμένη Κρυπτογραφία.
Ο κατακερματισμός είναι μια ειδική μέθοδος αντιμετώπισης δεδομένων (κάποιος αλγόριθμος απόστασης) με τα μοναδικά τους κλειδιά ( κλειδί ) για να βρείτε γρήγορα τις πληροφορίες που χρειάζεστε.
ΒΑΣΙΚΕΣ ΕΝΝΟΙΕΣ
Τραπέζι κατακερματισμού
Ένας πίνακας κατακερματισμού είναι ένας κανονικός πίνακας με μια ειδική διεύθυνση που δίνεται από κάποια συνάρτηση (συνάρτηση κατακερματισμού).
συνάρτηση κατακερματισμού
Μια συνάρτηση που μετατρέπει το κλειδί ενός στοιχείου δεδομένων σε κάποιο ευρετήριο σε έναν πίνακα ( πίνακας κατακερματισμού), λέγεται συνάρτηση κατακερματισμού ή συνάρτηση κατακερματισμού :
Εγώ = η (κλειδί );
όπου κλειδί- μετατρέψιμο κλειδί, Εγώ- προκύπτον ευρετήριο πίνακα, π.χ. το κλειδί εμφανίζεται σε ένα σύνολο, για παράδειγμα, ακεραίων αριθμών ( κατακερματισμένες διευθύνσεις ), τα οποία χρησιμοποιούνται αργότερα για πρόσβαση στα δεδομένα.
Ο κατακερματισμός με αυτόν τον τρόπο είναι μια τεχνική που περιλαμβάνει τη χρήση της τιμής ενός κλειδιού για τον προσδιορισμό της θέσης του σε έναν ειδικό πίνακα.
Ωστόσο, η συνάρτηση εξάπλωσης μπορεί αρκετά Οι μοναδικές βασικές τιμές δίνουν την ίδια τιμή θέσης Εγώ στον πίνακα κατακερματισμού. Καλείται η κατάσταση στην οποία δύο ή περισσότερα κλειδιά λαμβάνουν το ίδιο ευρετήριο (διεύθυνση κατακερματισμού). σύγκρουση (σύγκρουση) στον κατακερματισμό. Επομένως, το σχήμα κατακερματισμού πρέπει να περιλαμβάνει αλγόριθμος επίλυσης συγκρούσεων , ορίζοντας τη σειρά των ενεργειών, εάν η θέση Εγώ=η(κλειδί) καταλαμβάνεται ήδη από μια καταχώρηση με διαφορετικό κλειδί.
Υπάρχουν πολλά σχήματα κατακερματισμού που διαφέρουν ως προς τη συνάρτηση κατακερματισμού που χρησιμοποιείται. η(κλειδί) και αλγόριθμους επίλυσης συγκρούσεων.
Η πιο κοινή μέθοδος για τον καθορισμό μιας συνάρτησης κατακερματισμού είναι: μέθοδος διαίρεσης.
Τα αρχικά δεδομένα είναι: - κάποιο ακέραιο κλειδί κλειδίκαι μέγεθος τραπεζιού Μ. Το αποτέλεσμα αυτής της συνάρτησης είναι το υπόλοιπο της διαίρεσης αυτού του κλειδιού με το μέγεθος του πίνακα. Η γενική μορφή μιας τέτοιας συνάρτησης στη γλώσσα προγραμματισμού C/C++:
ενθ η (ενθ κλειδί , ενθ Μ ) {
Για Μ= 10 συνάρτηση κατακερματισμού επιστρέφει το λιγότερο σημαντικό ψηφίο του κλειδιού.
Για m=100, η συνάρτηση κατακερματισμού επιστρέφει τα δύο λιγότερο σημαντικά ψηφία του κλειδιού.
Στα εξεταζόμενα παραδείγματα, η συνάρτηση κατακερματισμού Εγώ=η(κλειδί) ορίζει μόνο τη θέση από την οποία θα αναζητήσετε (ή θα τοποθετήσετε αρχικά στον πίνακα) την καταχώρηση με το κλειδί κλειδί. Στη συνέχεια, πρέπει να χρησιμοποιήσετε κάποιου είδους σχήμα κατακερματισμού (αλγόριθμος).
Σχέδια κατακερματισμού
Στα περισσότερα προβλήματα, δύο ή περισσότερα κλειδιά κατακερματίζονται με τον ίδιο τρόπο, αλλά δεν μπορούν να καταλάβουν το ίδιο κελί στον πίνακα κατακερματισμού. Υπάρχουν δύο πιθανές επιλογές: είτε βρείτε διαφορετική θέση για το νέο κλειδί είτε δημιουργήστε μια ξεχωριστή λίστα για κάθε ευρετήριο κατακερματισμού πίνακα, στην οποία τοποθετούνται όλα τα κλειδιά που αντιστοιχίζονται σε αυτό το ευρετήριο.
Αυτές οι παραλλαγές είναι τα δύο κλασικά σχήματα κατακερματισμού:
κατακερματισμός με ανοιχτή διευθυνσιοδότηση με γραμμική ανίχνευση - γραμμικός καθετήρας Άνοιξε απευθύνοντας.
αλυσιδωτό κατακερματισμό (με λίστες), ή το λεγόμενο πολυδιάστατο κατακερματισμό - αλυσοδένοντας με ξεχωριστός τόπος αγώνων;
Ανοικτή μέθοδος διευθυνσιοδότησης με γραμμική ανίχνευση . Αρχικά, όλα τα κελιά του πίνακα κατακερματισμού, που είναι ένας κανονικός μονοδιάστατος πίνακας, επισημαίνονται ως μη κατειλημμένα. Επομένως, κατά την προσθήκη νέου κλειδιού, ελέγχεται εάν το δεδομένο κελί είναι κατειλημμένο. Εάν το κελί είναι κατειλημμένο, τότε ο αλγόριθμος πραγματοποιεί αναζήτηση σε κύκλο μέχρι να μείνει κενός χώρος ("ανοιχτή διεύθυνση").
Εκείνοι. στοιχεία με ομοιογενή πλήκτρα τοποθετούνται κοντά στο ευρετήριο που προκύπτει.
Στο μέλλον, πραγματοποιώντας μια αναζήτηση, βρείτε πρώτα τη θέση με το κλειδί Εγώστον πίνακα και εάν το κλειδί δεν ταιριάζει, τότε η επόμενη αναζήτηση πραγματοποιείται σύμφωνα με τον αλγόριθμο επίλυσης συγκρούσεων, ξεκινώντας από τη θέση Εγώ. .
Μέθοδος αλυσίδας είναι η κυρίαρχη στρατηγική . Σε αυτήν την περίπτωση Εγώπου λαμβάνεται από την επιλεγμένη συνάρτηση κατακερματισμού η(κλειδί)=Εγώ, αντιμετωπίζεται ως ευρετήριο σε έναν πίνακα κατακερματισμού λιστών, π.χ. κλειδί πρώτα κλειδίη επόμενη καταχώρηση αντιστοιχίζεται στη θέση Εγώ = η(κλειδί) τραπέζια. Εάν η θέση είναι ελεύθερη, τότε το στοιχείο με το κλειδί τοποθετείται σε αυτήν. κλειδί, εάν είναι απασχολημένος, τότε επεξεργάζεται ένας αλγόριθμος επίλυσης διενέξεων, ως αποτέλεσμα του οποίου τέτοια κλειδιά τοποθετούνται σε μια λίστα που ξεκινά από το Εγώ-αυτό το κελί του πίνακα κατακερματισμού. Για παράδειγμα
Ως αποτέλεσμα, έχουμε έναν πίνακα με μια σειρά από συνδεδεμένες λίστες ή δέντρα.
Η διαδικασία συμπλήρωσης (ανάγνωσης) ενός πίνακα κατακερματισμού είναι απλή, αλλά η πρόσβαση στα στοιχεία απαιτεί τις ακόλουθες λειτουργίες:
Υπολογισμός δείκτη Εγώ;
Αναζήτηση στην αντίστοιχη αλυσίδα.
Για να βελτιώσετε την αναζήτηση κατά την προσθήκη ενός νέου στοιχείου, μπορείτε να χρησιμοποιήσετε τον αλγόριθμο εισαγωγής όχι στο τέλος της λίστας, αλλά με παραγγελία, π.χ. προσθήκη στοιχείου σε Σωστό μέρος.
Ένα παράδειγμα εφαρμογής της μεθόδου άμεσης διευθυνσιοδότησης με γραμμική ανίχνευση . Τα αρχικά δεδομένα είναι 7 εγγραφές (για λόγους απλότητας, το τμήμα πληροφοριών αποτελείται μόνο από ακέραια δεδομένα), του δηλωμένου δομικού τύπου:
intkey? // Κλειδί
πληροφορίες; // Πληροφορίες
(59.1), (70.3), (96.5), (81.7), (13.8), (41.2), (79.9); μέγεθος πίνακα κατακερματισμού m=10.
συνάρτηση κατακερματισμού Εγώ=η(δεδομένα) =δεδομένα.κλειδί%δέκα; εκείνοι. υπόλοιπο μετά τη διαίρεση με το 10 - Εγώ.
Με βάση τα αρχικά δεδομένα, συμπληρώνουμε διαδοχικά τον πίνακα κατακερματισμού.
Ο κατακερματισμός των πρώτων πέντε κλειδιών δίνει διάφορα ευρετήρια (διευθύνσεις κατακερματισμού):
Η πρώτη σύγκρουση συμβαίνει μεταξύ των πλήκτρων 81 και 41 - η θέση με το δείκτη 1 καταλαμβάνεται. Επομένως, εξετάζουμε τον πίνακα κατακερματισμού για να βρούμε τον πλησιέστερο ελεύθερο χώρο, σε αυτήν την περίπτωση Εγώ = 2.
Το επόμενο κλειδί 79 δημιουργεί επίσης μια σύγκρουση: η θέση 9 είναι ήδη κατειλημμένη. Η αποτελεσματικότητα του αλγορίθμου πέφτει απότομα, γιατί Χρειάστηκαν 6 δοκιμές (συγκρίσεις) για να βρεθεί μια ελεύθερη θέση, ο δείκτης αποδείχθηκε δωρεάν Εγώ= 4.
Ο συνολικός αριθμός δειγμάτων αυτής της μεθόδου είναι από 1 έως n-1 δείγματα ανά στοιχείο, όπου n είναι το μέγεθος του πίνακα κατακερματισμού.
Εφαρμογή της αλυσιδωτής μεθόδου για το προηγούμενο παράδειγμα. Δηλώνουμε έναν δομικό τύπο για ένα στοιχείο λίστας (μονόδρομο):
intkey? // Κλειδί
πληροφορίες; // Πληροφορίες
zap*Next; // Δείκτης προς επόμενο στοιχείοστη λίστα
Με βάση τα αρχικά δεδομένα, συμπληρώνουμε διαδοχικά τον πίνακα κατακερματισμού προσθέτοντας νέο στοιχείοστο τέλος της λίστας εάν το μέρος έχει ήδη καταληφθεί.
Ο κατακερματισμός των πρώτων πέντε κλειδιών, όπως στην προηγούμενη περίπτωση, δίνει διαφορετικά ευρετήρια (διευθύνσεις κατακερματισμού): 9, 0, 6, 1 και 3.
Όταν συμβεί μια σύγκρουση, το νέο στοιχείο προστίθεται στο τέλος της λίστας. Επομένως, το στοιχείο με το κλειδί 41 τοποθετείται μετά το στοιχείο με το κλειδί 81 και το στοιχείο με το κλειδί 79 τοποθετείται μετά το στοιχείο με το κλειδί 59.
Ατομικές εργασίες
1. Δυαδικά δέντρα.Χρησιμοποιώντας το πρόγραμμα δημιουργίας τυχαίων αριθμών, λάβετε 10 τιμές από το 1 έως το 99 και δημιουργήστε ένα δυαδικό δέντρο.
Κάντε μια παράκαμψη:
1.α Διαδρομή από αριστερά προς τα δεξιά: Αριστερά-Ρίζα-Δεξιά: επισκεφθείτε πρώτα το αριστερό υποδέντρο, μετά τη ρίζα και τέλος το δεξί υποδέντρο.
(Ή αντίστροφα, από δεξιά προς τα αριστερά: Δεξιά-Ρίζα-Αριστερά)
1.β Διέλευση από πάνω προς τα κάτω: Ρίζα-Αριστερά-Δεξιά: επισκεφθείτε τη ρίζα στα υποδέντρα.
1.σε Διέλευση από κάτω προς τα πάνω: Αριστερά-Δεξιά-Ρίζα: επίσκεψη ρίζας μετά από υποδέντρα
Σε μια μεγάλη ποικιλία βιομηχανιών Τεχνολογίες πληροφορικήςβρείτε τις χρήσεις τους συναρτήσεις κατακερματισμού. Έχουν σχεδιαστεί, αφενός, για να απλοποιούν σε μεγάλο βαθμό την ανταλλαγή δεδομένων μεταξύ των χρηστών και την επεξεργασία αρχείων που χρησιμοποιούνται για συγκεκριμένους σκοπούς, αφετέρου για τη βελτιστοποίηση των αλγορίθμων για τη διασφάλιση του ελέγχου πρόσβασης στους αντίστοιχους πόρους. Η συνάρτηση κατακερματισμού είναι μία από τις βασικά όργαναεξασφάλιση προστασίας δεδομένων με κωδικό πρόσβασης, καθώς και οργάνωση της ανταλλαγής εγγράφων που υπογράφονται με χρήση EDS. Υπάρχει ένας μεγάλος αριθμός προτύπων βάσει των οποίων τα αρχεία μπορούν να αποθηκευτούν προσωρινά. Πολλά από αυτά αναπτύσσονται από Ρώσους ειδικούς. Ποιοι είναι οι τύποι συναρτήσεων κατακερματισμού; Ποιοι είναι οι κύριοι μηχανισμοί για την πρακτική εφαρμογή τους;
Τι είναι?
Αρχικά, ας διερευνήσουμε την έννοια της συνάρτησης κατακερματισμού. Αυτός ο όρος είναι συνήθως κατανοητός ως ένας αλγόριθμος για τη μετατροπή μιας ορισμένης ποσότητας πληροφοριών σε μια συντομότερη ακολουθία χαρακτήρων χρησιμοποιώντας μαθηματικές μεθόδους. Η πρακτική σημασία της συνάρτησης κατακερματισμού μπορεί να εντοπιστεί σε διάφορους τομείς. Έτσι, μπορούν να χρησιμοποιηθούν κατά τον έλεγχο της ακεραιότητας αρχείων και προγραμμάτων. Επίσης, οι κρυπτογραφικές συναρτήσεις κατακερματισμού χρησιμοποιούνται σε αλγόριθμους κρυπτογράφησης.
Χαρακτηριστικά
Ας εξετάσουμε τα βασικά χαρακτηριστικά των υπό μελέτη αλγορίθμων. Μεταξύ αυτών:
- η παρουσία εσωτερικών αλγορίθμων για τη μετατροπή δεδομένων του αρχικού μήκους σε μια μικρότερη ακολουθία χαρακτήρων.
- άνοιγμα για κρυπτογραφική επαλήθευση·
- την παρουσία αλγορίθμων που σας επιτρέπουν να κρυπτογραφείτε με ασφάλεια τα αρχικά δεδομένα.
- προσαρμοστικότητα στην αποκρυπτογράφηση με χρήση μικρών υπολογιστική ισχύς.
Άλλες σημαντικές ιδιότητες της συνάρτησης κατακερματισμού περιλαμβάνουν:
- τη δυνατότητα επεξεργασίας αρχικών συστοιχιών δεδομένων αυθαίρετου μήκους·
- δημιουργία κατακερματισμένων μπλοκ σταθερού μήκους.
- κατανέμουν ομοιόμορφα τις τιμές των συναρτήσεων στην έξοδο.
Οι υπό εξέταση αλγόριθμοι υποθέτουν επίσης ευαισθησία στα δεδομένα εισόδου σε επίπεδο 1 bit. Δηλαδή, ακόμα κι αν, σχετικά μιλώντας, αλλάξει τουλάχιστον 1 γράμμα στο έγγραφο προέλευσης, η συνάρτηση κατακερματισμού θα φαίνεται διαφορετική.
Απαιτήσεις για συναρτήσεις κατακερματισμού
Υπάρχει ένας αριθμός απαιτήσεων για λειτουργίες κατακερματισμού που προορίζονται για πρακτική χρήση σε μια συγκεκριμένη περιοχή. Πρώτον, ο αντίστοιχος αλγόριθμος πρέπει να είναι ευαίσθητος σε αλλαγές στην εσωτερική δομή των κατακερματισμένων εγγράφων. Δηλαδή, η συνάρτηση κατακερματισμού θα πρέπει να αναγνωρίζεται όταν πρόκειται για αρχείο κειμένου, μετάθεση παραγράφου, παύλα. Αφενός, το περιεχόμενο του εγγράφου δεν αλλάζει, αφετέρου, η δομή του διορθώνεται και αυτή η διαδικασία πρέπει να αναγνωρίζεται κατά τον κατακερματισμό. Δεύτερον, ο υπό εξέταση αλγόριθμος πρέπει να μετασχηματίσει τα δεδομένα με τέτοιο τρόπο ώστε η αντίστροφη λειτουργία (μετατροπή του κατακερματισμού στο αρχικό έγγραφο) να είναι αδύνατη στην πράξη. Τρίτον, η συνάρτηση κατακερματισμού θα πρέπει να περιλαμβάνει τη χρήση τέτοιων αλγορίθμων που πρακτικά αποκλείουν τη δυνατότητα σχηματισμού της ίδιας ακολουθίας χαρακτήρων με τη μορφή κατακερματισμού, με άλλα λόγια, την εμφάνιση των λεγόμενων συγκρούσεων. Θα εξετάσουμε την ουσία τους λίγο αργότερα.
Οι σημειωμένες απαιτήσεις που πρέπει να πληροί ο αλγόριθμος συνάρτησης κατακερματισμού μπορούν να επιτευχθούν κυρίως με τη χρήση πολύπλοκων μαθηματικών προσεγγίσεων.
Δομή
Ας μελετήσουμε ποια μπορεί να είναι η δομή των εξεταζόμενων συναρτήσεων. Όπως σημειώσαμε παραπάνω, μεταξύ των βασικών απαιτήσεων για τους υπό εξέταση αλγόριθμους είναι η παροχή μονοκατευθυντικής κρυπτογράφησης. Ένα άτομο που έχει μόνο ένα κατακερματισμό στη διάθεσή του δεν θα πρέπει πρακτικά να μπορεί να λάβει το πρωτότυπο έγγραφο με βάση αυτό.
Σε ποια δομή μπορεί να αναπαρασταθεί μια συνάρτηση κατακερματισμού που χρησιμοποιείται για τέτοιους σκοπούς; Ένα παράδειγμα σύνταξής του μπορεί να είναι το εξής: H (hash, δηλαδή, hash) = f (T (κείμενο), H1), όπου H1 είναι ο αλγόριθμος επεξεργασίας κειμένου T. Αυτή η λειτουργίακατακερματίζει το T με τέτοιο τρόπο ώστε χωρίς γνώση του H1 θα είναι πρακτικά αδύνατο να το ανοίξει ως πλήρες αρχείο.
Χρήση συναρτήσεων κατακερματισμού στην πράξη: Λήψη αρχείων
Ας μελετήσουμε τώρα λεπτομερέστερα τις επιλογές για τη χρήση συναρτήσεων κατακερματισμού στην πράξη. Η χρήση κατάλληλων αλγορίθμων μπορεί να χρησιμοποιηθεί κατά τη σύνταξη σεναρίων για τη λήψη αρχείων από διακομιστές Διαδικτύου.
Στις περισσότερες περιπτώσεις, προσδιορίζεται ένα συγκεκριμένο άθροισμα ελέγχου για κάθε αρχείο - αυτός είναι ο κατακερματισμός. Πρέπει να είναι το ίδιο για ένα αντικείμενο που βρίσκεται στον διακομιστή και έχει ληφθεί στον υπολογιστή του χρήστη. Εάν δεν συμβαίνει αυτό, τότε το αρχείο ενδέχεται να μην ανοίξει ή να ξεκινήσει λανθασμένα.
Λειτουργία κατακερματισμού και ψηφιακή υπογραφή
Η χρήση συναρτήσεων κατακερματισμού είναι κοινή για την οργάνωση της ανταλλαγής εγγράφων που περιέχουν ψηφιακή υπογραφή. Σε αυτήν την περίπτωση, το υπογεγραμμένο αρχείο κατακερματίζεται έτσι ώστε ο παραλήπτης του να μπορεί να επαληθεύσει ότι είναι γνήσιο. Αν και η συνάρτηση κατακερματισμού δεν περιλαμβάνεται επίσημα στη δομή ηλεκτρονικό κλειδί, μπορεί να διορθωθεί στη μνήμη flash του υλικού με το οποίο υπογράφονται τα έγγραφα, όπως, για παράδειγμα, το eToken.
Η ηλεκτρονική υπογραφή είναι η κρυπτογράφηση ενός αρχείου χρησιμοποιώντας δημόσια και ιδιωτικά κλειδιά. Δηλαδή, ένα μήνυμα κρυπτογραφημένο με το ιδιωτικό κλειδί επισυνάπτεται στο αρχείο προέλευσης και η ψηφιακή υπογραφή επαληθεύεται μέσω δημόσιο κλειδί. Εάν η συνάρτηση κατακερματισμού και των δύο εγγράφων ταιριάζει, το αρχείο του παραλήπτη αναγνωρίζεται ως αυθεντικό και η υπογραφή του αποστολέα αναγνωρίζεται ως σωστή.
Ο κατακερματισμός, όπως σημειώσαμε παραπάνω, δεν αποτελεί άμεσα στοιχείο του EDS, ωστόσο, σας επιτρέπει να βελτιστοποιήσετε πολύ αποτελεσματικά τους αλγόριθμους για χρήση Ηλεκτρονική Υπογραφή. Έτσι, μόνο ο κατακερματισμός μπορεί να κρυπτογραφηθεί, όχι το ίδιο το έγγραφο. Ως αποτέλεσμα, η ταχύτητα επεξεργασίας αρχείων αυξάνεται σημαντικά, ενώ ταυτόχρονα καθίσταται δυνατή η παροχή πιο αποτελεσματικών μηχανισμών προστασίας EDS, καθώς η έμφαση στις υπολογιστικές λειτουργίες σε αυτήν την περίπτωση δεν θα δοθεί στην επεξεργασία των αρχικών δεδομένων, αλλά στη διασφάλιση της κρυπτογραφική ισχύς της υπογραφής. Η συνάρτηση κατακερματισμού καθιστά επίσης δυνατή την υπογραφή διαφόρων τύπων δεδομένων, όχι μόνο κειμένου.
Έλεγχος κωδικού πρόσβασης
Ένας άλλος πιθανός τομέας εφαρμογής για κατακερματισμό είναι η οργάνωση αλγορίθμων επαλήθευσης κωδικού πρόσβασης που έχουν δημιουργηθεί για να διαφοροποιούν την πρόσβαση σε ορισμένους πόρους αρχείων. Πώς μπορούν ορισμένοι τύποι συναρτήσεων κατακερματισμού να εμπλακούν στην επίλυση τέτοιων προβλημάτων; Πολύ απλό.
Το γεγονός είναι ότι στους περισσότερους διακομιστές, στους οποίους η πρόσβαση υπόκειται σε διαφοροποίηση, οι κωδικοί πρόσβασης αποθηκεύονται με τη μορφή κατακερματισμένων τιμών. Αυτό είναι πολύ λογικό - εάν οι κωδικοί πρόσβασης παρουσιάζονταν στην αρχική τους μορφή κειμένου, οι χάκερ που είχαν πρόσβαση σε αυτούς θα μπορούσαν εύκολα να διαβάσουν τα μυστικά δεδομένα. Με τη σειρά του, με βάση τον κατακερματισμό, δεν είναι εύκολο να υπολογιστεί ο κωδικός πρόσβασης.
Πώς ελέγχεται η πρόσβαση των χρηστών όταν χρησιμοποιούνται οι υπό εξέταση αλγόριθμοι; Ο κωδικός πρόσβασης που εισάγεται από τον χρήστη ελέγχεται σε σχέση με αυτό που έχει καθοριστεί σε μια συνάρτηση κατακερματισμού που είναι αποθηκευμένη στον διακομιστή. Εάν οι τιμές των μπλοκ κειμένου ταιριάζουν, ο χρήστης αποκτά την απαραίτητη πρόσβαση στους πόρους.
Η απλούστερη συνάρτηση κατακερματισμού μπορεί να χρησιμοποιηθεί ως εργαλείο ελέγχου κωδικού πρόσβασης. Αλλά στην πράξη, οι επαγγελματίες πληροφορικής χρησιμοποιούν συχνότερα πολύπλοκους κρυπτογραφικούς αλγόριθμους πολλαπλών σταδίων. Συνήθως, συμπληρώνονται από τη χρήση προτύπων επικοινωνίας ασφαλών καναλιών, έτσι ώστε οι χάκερ να μην μπορούν να εντοπίσουν ή να καταλάβουν τον κωδικό πρόσβασης που μεταδίδεται από τον υπολογιστή του χρήστη στους διακομιστές πριν επαληθευτεί έναντι των κατακερματισμένων μπλοκ κειμένου.
Συγκρούσεις συνάρτησης κατακερματισμού
Στη θεωρία των συναρτήσεων κατακερματισμού, παρέχεται ένα φαινόμενο όπως η σύγκρουση. Ποια είναι η ουσία του; Μια σύγκρουση κατακερματισμού είναι μια κατάσταση κατά την οποία δύο διαφορετικά αρχεία έχουν τον ίδιο κωδικό κατακερματισμού. Αυτό είναι δυνατό εάν το μήκος της ακολουθίας χαρακτήρων στόχου είναι μικρό. Σε αυτήν την περίπτωση, η πιθανότητα αντιστοίχισης κατακερματισμού θα είναι μεγαλύτερη.
Προκειμένου να αποφευχθεί η σύγκρουση, συνιστάται, ειδικότερα, η χρήση ενός διπλού αλγόριθμου που ονομάζεται "κατακερματισμός συνάρτησης κατακερματισμού". Περιλαμβάνει το σχηματισμό ανοιχτού και κλειστού κώδικα. Πολλοί προγραμματιστές για την επίλυση κρίσιμων προβλημάτων συνιστούν τη μη χρήση συναρτήσεων κατακερματισμού σε περιπτώσεις που δεν είναι απαραίτητο και δοκιμάζουν πάντα τους αντίστοιχους αλγόριθμους για την καλύτερη συμβατότητα με ορισμένα κλειδιά.
Ιστορία εμφάνισης
Οι ιδρυτές της θεωρίας των συναρτήσεων κατακερματισμού μπορούν να θεωρηθούν οι ερευνητές Carter, Wegman, Simonson, Bierbrouer. Στις πρώτες εκδόσεις, οι αντίστοιχοι αλγόριθμοι χρησιμοποιήθηκαν ως εργαλεία για τη δημιουργία μοναδικών εικόνων ακολουθιών χαρακτήρων αυθαίρετου μήκους με σκοπό την ταυτοποίηση και την επαλήθευση της αυθεντικότητάς τους. Με τη σειρά του, ο κατακερματισμός, σύμφωνα με τα καθορισμένα κριτήρια, θα πρέπει να έχει μήκος 30-512 bit. Ως ειδικός χρήσιμη ιδιότητακατάλληλες λειτουργίες, εξετάστηκε η καταλληλότητά του για χρήση ως πόρος για γρήγορη αναζήτηση αρχείων ή ταξινόμηση τους.
Δημοφιλή πρότυπα κατακερματισμού
Ας εξετάσουμε τώρα σε ποια δημοφιλή πρότυπα μπορούν να αναπαρασταθούν οι συναρτήσεις κατακερματισμού. Ένα από αυτά είναι το CRC. Αυτός ο αλγόριθμος είναι κυκλικός κώδικας, που ονομάζεται επίσης άθροισμα ελέγχου. Αυτό το πρότυπο χαρακτηρίζεται από απλότητα και ταυτόχρονα ευελιξία - μέσω αυτού μπορείτε να κατακερματίσετε το μεγαλύτερο εύρος δεδομένων. Ο CRC είναι ένας από τους πιο συνηθισμένους μη κρυπτογραφικούς αλγόριθμους.
Με τη σειρά τους, τα πρότυπα MD4 και MD5 χρησιμοποιούνται ευρέως στην κρυπτογράφηση. Ένας άλλος δημοφιλής κρυπτογραφικός αλγόριθμος είναι ο SHA-1. Συγκεκριμένα, χαρακτηρίζεται από ένα μέγεθος κατακερματισμού 160 bit, το οποίο είναι μεγαλύτερο από αυτό του MD5 - αυτό το πρότυπο υποστηρίζει 128 bit. Υπάρχουν ρωσικά πρότυπα που ρυθμίζουν τη χρήση συναρτήσεων κατακερματισμού - GOST R 34.11-94, καθώς και GOST R 34.11-2012 που το αντικατέστησε. Μπορεί να σημειωθεί ότι η τιμή κατακερματισμού που παρέχεται από τους αλγόριθμους που υιοθετήθηκαν στη Ρωσική Ομοσπονδία είναι 256 bit.
Τα εν λόγω πρότυπα μπορούν να ταξινομηθούν με διάφορους τρόπους. Για παράδειγμα, υπάρχουν αυτοί που χρησιμοποιούν μπλοκ και εξειδικευμένους αλγόριθμους. Η απλότητα των υπολογισμών με βάση τα πρότυπα του πρώτου τύπου συνοδεύεται συχνά από τη χαμηλή ταχύτητά τους. Ως εκ τούτου, ως εναλλακτική λύση στους αλγόριθμους μπλοκ, μπορούν να χρησιμοποιηθούν αυτοί που περιλαμβάνουν μικρότερο αριθμό απαραίτητων υπολογιστικών πράξεων. Συνηθίζεται να γίνεται αναφορά σε πρότυπα υψηλής ταχύτητας, ιδίως στα προαναφερθέντα MD4, MD5 και SHA. Ας εξετάσουμε τις ιδιαιτερότητες των ειδικών αλγορίθμων κατακερματισμού στο παράδειγμα του SHA με περισσότερες λεπτομέρειες.
Χαρακτηριστικά του αλγορίθμου SHA
Η χρήση συναρτήσεων κατακερματισμού που βασίζονται στο πρότυπο SHA πραγματοποιείται συχνότερα στον τομέα της ανάπτυξης εργαλείων ψηφιακή υπογραφήΈγγραφα DSA. Όπως σημειώσαμε παραπάνω, Αλγόριθμος SHAυποστηρίζει έναν κατακερματισμό 160 bit (παρέχοντας μια λεγόμενη "πέψη" μιας ακολουθίας χαρακτήρων). Αρχικά, το υπό εξέταση πρότυπο διαιρεί τη συστοιχία δεδομένων σε μπλοκ των 512 bit. Εάν είναι απαραίτητο, εάν το μήκος του τελευταίου μπλοκ δεν φτάσει το καθορισμένο σχήμα, η δομή του αρχείου συμπληρώνεται με 1 και τον απαιτούμενο αριθμό μηδενικών. Επίσης, στο τέλος του αντίστοιχου μπλοκ, εισάγεται ένας κωδικός που καθορίζει τη διάρκεια του μηνύματος. Ο αλγόριθμος που εξετάζουμε περιλαμβάνει 80 λογικές συναρτήσεις, μέσω των οποίων επεξεργάζονται 3 λέξεις, που αναπαρίστανται σε 32 bit. Το πρότυπο SHA προβλέπει επίσης τη χρήση 4 σταθερών.
Σύγκριση αλγορίθμων κατακερματισμού
Ας μελετήσουμε πώς συσχετίζονται οι ιδιότητες των συναρτήσεων κατακερματισμού που σχετίζονται με διαφορετικά πρότυπα, χρησιμοποιώντας το παράδειγμα σύγκρισης των χαρακτηριστικών του ρωσικού προτύπου GOST R 34.11-94 και του αμερικανικού SHA, το οποίο εξετάσαμε παραπάνω. Πρώτα απ 'όλα, πρέπει να σημειωθεί ότι ο αλγόριθμος που αναπτύχθηκε στη Ρωσική Ομοσπονδία περιλαμβάνει την υλοποίηση 4 λειτουργιών κρυπτογράφησης ανά 1 κύκλο. Αυτό αντιστοιχεί σε 128 γύρους. Με τη σειρά του, κατά τη διάρκεια 1 γύρου, όταν χρησιμοποιείται SHA, υποτίθεται ότι υπολογίζονται περίπου 20 εντολές, ενώ υπάρχουν 80 γύροι συνολικά.Έτσι, η χρήση του SHA επιτρέπει την επεξεργασία 512 bit αρχικών δεδομένων μέσα σε 1 κύκλο. Ενώ το ρωσικό πρότυπο είναι ικανό να εκτελεί λειτουργίες σε έναν κύκλο 256 bit δεδομένων.
Τεχνικά χαρακτηριστικά του πιο πρόσφατου ρωσικού αλγορίθμου
Παραπάνω, σημειώσαμε ότι το πρότυπο GOST R 34.11-94 αντικαταστάθηκε από ένα νεότερο - GOST R 34.11-2012 Stribog. Ας εξερευνήσουμε τις ιδιαιτερότητές του με περισσότερες λεπτομέρειες.
Διά μέσου αυτό το πρότυπομπορούν να εφαρμοστούν, όπως στην περίπτωση των αλγορίθμων που συζητήθηκαν παραπάνω, κρυπτογραφικές συναρτήσεις κατακερματισμού. Μπορεί να σημειωθεί ότι το πιο πρόσφατο ρωσικό πρότυπο υποστηρίζει ένα μπλοκ δεδομένων εισόδου σε ποσότητα 512 bit. Τα κύρια πλεονεκτήματα του GOST R 34.11-2012:
- Υψηλό επίπεδο προστασίας έναντι σπασίματος κρυπτογράφων.
- αξιοπιστία, που υποστηρίζεται από τη χρήση αποδεδειγμένων σχεδίων.
- γρήγορος υπολογισμός της συνάρτησης κατακερματισμού, η απουσία μετασχηματισμών στον αλγόριθμο που περιπλέκουν την κατασκευή της συνάρτησης και επιβραδύνουν τον υπολογισμό.
Σημειώθηκαν πλεονεκτήματα του νέου ρωσικού προτύπου κρυπτογραφική κρυπτογράφησησας επιτρέπουν να το χρησιμοποιήσετε στην οργάνωση της ροής εργασιών που πληροί τα πιο αυστηρά κριτήρια, τα οποία ορίζονται στις διατάξεις της κανονιστικής νομοθεσίας.
Ειδικότητα κρυπτογραφικών συναρτήσεων κατακερματισμού
Ας εξετάσουμε λεπτομερέστερα πώς μπορούν να χρησιμοποιηθούν οι τύποι αλγορίθμων που μελετάμε στον τομέα της κρυπτογραφίας. Η βασική απαίτηση για τις αντίστοιχες λειτουργίες είναι η αντίσταση σε συγκρούσεις, την οποία αναφέραμε παραπάνω. Δηλαδή, δεν θα πρέπει να δημιουργούνται διπλότυπες τιμές κατακερματισμού εάν αυτές οι τιμές υπάρχουν ήδη στη δομή του γειτονικού αλγορίθμου. Τα άλλα κριτήρια που αναφέρονται παραπάνω πρέπει επίσης να πληρούνται από κρυπτογραφικές λειτουργίες. Είναι σαφές ότι υπάρχει πάντα κάποια θεωρητική πιθανότητα ανάκαμψης αρχείο προέλευσηςμε βάση έναν κατακερματισμό, ειδικά εάν υπάρχει διαθέσιμο ένα ισχυρό υπολογιστικό εργαλείο. Ωστόσο, αυτό το σενάριο υποτίθεται ότι ελαχιστοποιείται χάρη σε ισχυρούς αλγόριθμους κρυπτογράφησης. Έτσι, θα είναι πολύ δύσκολο να υπολογιστεί μια συνάρτηση κατακερματισμού εάν η υπολογιστική της ισχύς αντιστοιχεί στον τύπο 2^(n/2).
Ένα άλλο σημαντικό κριτήριο για έναν κρυπτογραφικό αλγόριθμο είναι η αλλαγή στον κατακερματισμό σε περίπτωση που διορθωθεί ο αρχικός πίνακας δεδομένων. Παραπάνω, σημειώσαμε ότι τα πρότυπα κρυπτογράφησης θα πρέπει να έχουν ευαισθησία στο επίπεδο του 1 bit. Έτσι, αυτή η ιδιότητα είναι ένας βασικός παράγοντας για τη διασφάλιση αξιόπιστης προστασίας με κωδικό πρόσβασης για την πρόσβαση στα αρχεία.
Επαναληπτικά σχήματα
Ας μελετήσουμε τώρα πώς μπορούν να κατασκευαστούν κρυπτογραφικοί αλγόριθμοι κατακερματισμού. Μεταξύ των πιο κοινών σχημάτων για την επίλυση αυτού του προβλήματος είναι η χρήση ενός επαναληπτικού διαδοχικού μοντέλου. Βασίζεται στη χρήση της λεγόμενης συνάρτησης συστολής, στην οποία ο αριθμός των bit εισόδου είναι σημαντικά μεγαλύτερος από εκείνους που είναι σταθεροί στην έξοδο.
Φυσικά, η συνάρτηση συμπίεσης πρέπει να πληροί τα απαραίτητα κριτήρια κρυπτογραφικής αντοχής. Στο διαδραστικό σχήμα, η πρώτη λειτουργία για την επεξεργασία της ροής δεδομένων εισόδου χωρίζεται σε μπλοκ, το μέγεθος των οποίων υπολογίζεται σε bit. Ο αντίστοιχος αλγόριθμος χρησιμοποιεί επίσης προσωρινές μεταβλητές ενός δεδομένου αριθμού bit. Ως πρώτη τιμή χρησιμοποιείται ένας πολύ γνωστός αριθμός, ενώ τα επόμενα μπλοκ δεδομένων συνδυάζονται με την τιμή της εν λόγω συνάρτησης στην έξοδο. Η τιμή κατακερματισμού γίνεται η έξοδος bit για την τελευταία επανάληψη, η οποία λαμβάνει υπόψη ολόκληρη τη ροή εισόδου, συμπεριλαμβανομένης της πρώτης τιμής. Παρέχεται το λεγόμενο «φαινόμενο χιονοστιβάδας» του κατακερματισμού.
Η κύρια δυσκολία που χαρακτηρίζει τον κατακερματισμό που εφαρμόζεται ως επαναληπτικό σχήμα είναι ότι οι συναρτήσεις κατακερματισμού είναι μερικές φορές δύσκολο να κατασκευαστούν εάν η ροή εισόδου δεν είναι πανομοιότυπη με το μέγεθος του μπλοκ στο οποίο χωρίζεται ο αρχικός πίνακας δεδομένων. Αλλά σε αυτήν την περίπτωση, μπορούν να γραφτούν αλγόριθμοι στο πρότυπο κατακερματισμού, μέσω των οποίων η αρχική ροή μπορεί να επεκταθεί με τον ένα ή τον άλλο τρόπο.
Σε ορισμένες περιπτώσεις, οι λεγόμενοι αλγόριθμοι πολλαπλών περασμάτων ενδέχεται να εμπλέκονται στη διαδικασία επεξεργασίας δεδομένων στο πλαίσιο ενός επαναληπτικού σχήματος. Προτείνουν τη διαμόρφωση ενός ακόμη πιο έντονου «φαινόμενου χιονοστιβάδας». Ένα τέτοιο σενάριο περιλαμβάνει το σχηματισμό επαναλαμβανόμενων συστοιχιών δεδομένων και μόνο στη δεύτερη θέση βρίσκεται η επέκταση.
Αλγόριθμος αποκλεισμού
Η συνάρτηση συμπίεσης μπορεί επίσης να βασίζεται σε έναν αλγόριθμο μπλοκ με τον οποίο εκτελείται η κρυπτογράφηση. Έτσι, για να αυξήσετε το επίπεδο ασφάλειας, μπορείτε να χρησιμοποιήσετε μπλοκ δεδομένων που υπόκεινται σε κατακερματισμό κατά την τρέχουσα επανάληψη, ως κλειδί, και το αποτέλεσμα των λειτουργιών που προέκυψαν κατά την εκτέλεση της συνάρτησης συμπίεσης πριν από αυτήν, ως είσοδο . Ως αποτέλεσμα, η τελευταία επανάληψη θα παρέχει την έξοδο του αλγορίθμου. Η ασφάλεια ενός κατακερματισμού θα συσχετιστεί με την ευρωστία του εμπλεκόμενου αλγορίθμου.
Ωστόσο, όπως σημειώσαμε παραπάνω, λαμβάνοντας υπόψη διαφορετικά είδησυναρτήσεις κατακερματισμού, οι αλγόριθμοι μπλοκ συχνά συνοδεύονται από την ανάγκη χρήσης μεγάλης υπολογιστικής ισχύος. Εάν δεν είναι διαθέσιμα, η ταχύτητα επεξεργασίας αρχείων μπορεί να μην είναι επαρκής για την επίλυση πρακτικών προβλημάτων που σχετίζονται με τη χρήση συναρτήσεων κατακερματισμού. Ταυτόχρονα, η απαιτούμενη κρυπτογραφική ισχύς μπορεί επίσης να πραγματοποιηθεί με έναν μικρό αριθμό λειτουργιών με ροές δεδομένων πηγής, ειδικότερα, οι αλγόριθμοι που εξετάσαμε - MD5, SHA και ρωσικά πρότυπα κρυπτογραφικής κρυπτογράφησης - είναι προσαρμοσμένοι στην επίλυση τέτοιων προβλημάτων.
Τι είναι το hash;Μια συνάρτηση κατακερματισμού είναι ένας μαθηματικός μετασχηματισμός πληροφοριών σε μια σύντομη συμβολοσειρά ορισμένου μήκους.
Γιατί χρειάζεται αυτό;Η ανάλυση συνάρτησης κατακερματισμού χρησιμοποιείται συχνά για τον έλεγχο της ακεραιότητας σημαντικών αρχείων λειτουργικό σύστημα, σημαντικά προγράμματα, σημαντικά δεδομένα. Η παρακολούθηση μπορεί να πραγματοποιηθεί τόσο σε βάση όσο χρειάζεται και σε τακτική βάση.
Πώς γίνεται;Αρχικά, καθορίστε την ακεραιότητα των αρχείων που πρέπει να ελέγχονται. Για κάθε αρχείο, η τιμή του κατακερματισμού του υπολογίζεται σύμφωνα με έναν ειδικό αλγόριθμο και το αποτέλεσμα αποθηκεύεται. Μετά τον απαραίτητο χρόνο, γίνεται ανάλογος υπολογισμός και συγκρίνονται τα αποτελέσματα. Εάν οι τιμές είναι διαφορετικές, τότε οι πληροφορίες που περιέχονται στο αρχείο έχουν αλλάξει.
Ποια χαρακτηριστικά πρέπει να έχει μια συνάρτηση κατακερματισμού;
- πρέπει να μπορεί να εκτελεί μετατροπές δεδομένων αυθαίρετου μήκους σε σταθερό·
- πρέπει να έχει ανοιχτό αλγόριθμο ώστε να μπορεί να διερευνηθεί η κρυπτογραφική του ισχύς.
- θα πρέπει να είναι μονόπλευρη, δηλαδή να μην υπάρχει μαθηματική δυνατότητα προσδιορισμού των αρχικών δεδομένων από το αποτέλεσμα.
- θα πρέπει να «αντιστέκεται» σε συγκρούσεις, δηλαδή να μην παράγει τις ίδιες τιμές για διαφορετικά δεδομένα εισόδου.
- δεν θα πρέπει να απαιτεί μεγάλους υπολογιστικούς πόρους.
- με την παραμικρή αλλαγή στα δεδομένα εισόδου, το αποτέλεσμα θα πρέπει να αλλάξει σημαντικά.
Ποιοι είναι οι δημοφιλείς αλγόριθμοι κατακερματισμού;Οι ακόλουθες συναρτήσεις κατακερματισμού χρησιμοποιούνται αυτήν τη στιγμή:
- Το CRC σημαίνει κυκλικός κωδικός πλεονασμού ή άθροισμα ελέγχου. Ο αλγόριθμος είναι πολύ απλός, έχει μεγάλο αριθμό παραλλαγών ανάλογα με το απαιτούμενο μήκος εξόδου. Δεν είναι κρυπτογραφικό!
- Ο MD 5 είναι ένας πολύ δημοφιλής αλγόριθμος. Σαν αυτόν προηγούμενη έκδοσηΤο MD 4 είναι μια κρυπτογραφική λειτουργία. Το μέγεθος κατακερματισμού είναι 128 bit.
- Το SHA -1 είναι επίσης μια πολύ δημοφιλής συνάρτηση κρυπτογράφησης. Το μέγεθος κατακερματισμού είναι 160 bit.
- Το GOST R 34.11-94 είναι ένα ρωσικό κρυπτογραφικό πρότυπο για τον υπολογισμό μιας συνάρτησης κατακερματισμού. Το μέγεθος κατακερματισμού είναι 256 bit.
Πότε μπορεί ένας διαχειριστής συστήματος να χρησιμοποιήσει αυτούς τους αλγόριθμους;Συχνά, κατά τη λήψη οποιουδήποτε περιεχομένου, όπως προγράμματα από τον ιστότοπο του κατασκευαστή, μουσική, ταινίες ή άλλες πληροφορίες, υπάρχει μια τιμή αθροίσματος ελέγχου που υπολογίζεται χρησιμοποιώντας έναν συγκεκριμένο αλγόριθμο. Για λόγους ασφαλείας, μετά τη λήψη, πρέπει να υπολογίσετε ανεξάρτητα τη συνάρτηση κατακερματισμού και να συγκρίνετε την τιμή με αυτό που υποδεικνύεται στον ιστότοπο ή στο συνημμένο στο αρχείο. Το έχεις κάνει ποτέ αυτό;
Τι είναι πιο βολικό για τον υπολογισμό του κατακερματισμού;Τώρα υπάρχει ένας μεγάλος αριθμός τέτοιων βοηθητικών προγραμμάτων, τόσο επί πληρωμή όσο και δωρεάν. Προσωπικά μου άρεσε το HashTab. Πρώτον, κατά την εγκατάσταση, το βοηθητικό πρόγραμμα ενσωματώνεται ως καρτέλα στις ιδιότητες του αρχείου, δεύτερον, σας επιτρέπει να επιλέξετε μεγάλο αριθμό αλγορίθμων κατακερματισμού και, τρίτον, είναι δωρεάν για ιδιωτική μη εμπορική χρήση.
Τι είναι το ρωσικό;Όπως αναφέρθηκε παραπάνω, στη Ρωσία υπάρχει ένα πρότυπο κατακερματισμού GOST R 34.11-94, το οποίο χρησιμοποιείται ευρέως από πολλούς κατασκευαστές εργαλείων ασφάλειας πληροφοριών. Ένα από αυτά τα εργαλεία είναι το πρόγραμμα στερέωσης και ελέγχου. αρχική κατάσταση πακέτο λογισμικού"ΔΙΟΡΘΩΣΕΤΕ". Αυτό το πρόγραμμα είναι ένα μέσο παρακολούθησης της αποτελεσματικότητας της χρήσης των εγκαταστάσεων ασφάλειας πληροφοριών.
ΕΠΙΔΙΟΡΘΩΣΗ (έκδοση 2.0.1) για Windows 9x/NT/2000/XP
- Υπολογισμός αθροισμάτων ελέγχου δεδομένων αρχείων χρησιμοποιώντας έναν από τους 5 εφαρμοσμένους αλγόριθμους.
- Στερέωση και μετέπειτα έλεγχος της αρχικής κατάστασης του πακέτου λογισμικού.
- Σύγκριση εκδόσεων πακέτων λογισμικού.
- Διόρθωση και έλεγχος καταλόγων.
- Έλεγχος αλλαγών σε καθορισμένα αρχεία (καταλόγους).
- Δημιουργία αναφορών σε μορφές TXT, HTML, SV.
- Το προϊόν διαθέτει πιστοποιητικό FSTEC σύμφωνα με το NDV 3 No. 913 έως την 01 Ιουνίου 2013.
Και τι γίνεται με το ECP;Το αποτέλεσμα του υπολογισμού της συνάρτησης κατακερματισμού, μαζί με το μυστικό κλειδί του χρήστη, εισάγεται στην είσοδο του κρυπτογραφικού αλγορίθμου, όπου υπολογίζεται η ψηφιακή υπογραφή. Αυστηρά μιλώντας, η συνάρτηση κατακερματισμού δεν αποτελεί μέρος του αλγόριθμου EDS, αλλά συχνά αυτό γίνεται επίτηδες, προκειμένου να αποκλειστεί μια επίθεση δημόσιου κλειδιού.
Σήμερα, πολλές εφαρμογές ηλεκτρονικού εμπορίου σάς επιτρέπουν να αποθηκεύετε Το μυστικό κλειδίχρήστη στην ιδιωτική περιοχή του διακριτικού (ruToken, eToken) χωρίς τεχνική σκοπιμότηταεξάγοντας το από εκεί. Το ίδιο το διακριτικό έχει πολύ περιορισμένη περιοχή μνήμης, μετρημένη σε kilobyte. Για να υπογράψετε ένα έγγραφο, δεν υπάρχει τρόπος να μεταφέρετε το έγγραφο στο ίδιο το διακριτικό, αλλά είναι πολύ εύκολο να μεταφέρετε τον κατακερματισμό του εγγράφου στο διακριτικό και να λάβετε ένα EDS στην έξοδο.
Πίνακες κατακερματισμού
Τραπέζι κατακερματισμού(ανακατεμένος πίνακας, πίνακας με υπολογισμένες διευθύνσεις) είναι Λειτουργίες υποστήριξης δυναμικού συνόλουπροσθήκη, αναζήτηση και διαγραφή στοιχείου και χρήση ειδικών μεθόδων απευθύνοντας.
Η κύρια διαφορά μεταξύ των πινάκων και άλλων δυναμικών συνόλων είναι υπολογισμός διεύθυνσης στοιχείουμε βασική τιμή.
Η ιδέα μιας εφαρμογής κατακερματισμού είναι ότι η εργασία με έναν μεγάλο πίνακα περιορίζεται στην εργασία με έναν αριθμό μικρών συνόλων.
Για παράδειγμα, ένα σημειωματάριο. Οι σελίδες του βιβλίου σημειώνονται με γράμματα. Μια σελίδα που σημειώνεται με ένα γράμμα περιέχει επώνυμα που αρχίζουν με αυτό το γράμμα. Ένα μεγάλο σύνολο επωνύμων χωρίζεται σε 28 υποσύνολα. Κατά την αναζήτηση, το βιβλίο ανοίγει αμέσως στο επιθυμητό γράμμα και η αναζήτηση επιταχύνεται.
Στον πίνακα κατακερματισμού προγραμματισμού- αυτό είναι δομήδεδομένα που αποθηκεύουν ζεύγη (κλειδί ή ευρετήριο + τιμή) και με τα οποία εκτελούνται τρεις λειτουργίες: προσθήκη νέου ζεύγους, αναζήτηση και διαγραφή ζεύγους προς κλειδί.
Αναζήτηση σε πίνακες κατακερματισμούπραγματοποιείται σε δύο στάδια:
ο πρώτοςβήμα - υπολογισμός μιας συνάρτησης κατακερματισμού που μετατρέπει κλειδίαναζήτηση σε υπολογιστικό φύλλο διεύθυνση:
δεύτεροςβήμα είναι η διαδικασία επίλυσης διενέξεων κατά την επεξεργασία τέτοιων κλειδιών.
Αν ένα διαφορετικές αξίεςΗ συνάρτηση κατακερματισμού πλήκτρων πίνακα δημιουργεί το ίδιοδιευθύνσεις, λέγεται ότι προκύπτει σύγκρουση(σύγκρουση, σύγκρουση).
Λειτουργίες κατακερματισμού
Ο κύριος σκοπός της συνάρτησης κατακερματισμού είναι να ταιριάζει με διάφορα κλειδιάαν είναι δυνατόν διάφοροςόχι αρνητικό ολόκληροςαριθμοί.
Συνάρτηση κατακερματισμού θεμάτων καλύτερα, πως πιο λιγο πανομοιότυποδημιουργεί αξίες.
Η συνάρτηση κατακερματισμού πρέπει να επιλεγεί με τέτοιο τρόπο ώστε να πληρούνται οι ακόλουθες ιδιότητες:
η συνάρτηση κατακερματισμού ορίζεται στα στοιχεία του συνόλου και παίρνει ακέραιος μη αρνητικόςαξίες;
συνάρτηση κατακερματισμού εύκολο να υπολογιστεί;
η συνάρτηση κατακερματισμού μπορεί να πάρει διάφοροςτιμές από περίπου Το ίδιο πιθανό(ελαχιστοποίηση σύγκρουσης)
στο συγγενείς τιμές επιχειρήματοςη συνάρτηση κατακερματισμού παίρνει μακρινόςαξίες μεταξύ τους.
Για να δημιουργήσετε μια καλή συνάρτηση κατακερματισμού, πρέπει να γνωρίζετε την κατανομή των κλειδιών. Εάν η κατανομή του κλειδιού είναι γνωστή, τότε στην ιδανική περίπτωση, η πυκνότητα του κλειδιού και η κατανομή πυκνότητας τιμής κατακερματισμού θα πρέπει να είναι πανομοιότυπες.
Αφήνω Π ( κλειδί ) - πυκνότητα διανομής βασικών αιτημάτων. Τότε, στην ιδανική περίπτωση, η πυκνότητα κατανομής των αιτημάτων εισαγωγής πίνακα είναι σολ ( H ( κλειδί )) να είναι τέτοια ώστε, κατά μέσο όρο, ο αριθμός των στοιχείων, κατ. ήταν απαραίτητο να περάσει με αλυσίδες από δίδυμα, ήταν ελάχιστο.
Παράδειγμα.
Ας υπάρχει ένα σετ κλειδιά
{0, 1, 4, 5, 6, 7, 8, 9, 15, 20, 30, 40}
και αφήστε το τραπέζι να το επιτρέψει 4 είσοδος.
Μπορείτε να δημιουργήσετε μια συνάρτηση κατακερματισμού:
η(κλειδί) = κλειδί % 4 .
Τότε παίρνετε το εξής διευθύνσειςγια εισροές
{0, 1, 2, 3} πίνακες:
|
η(κλειδί) |
|
Αριθμός εισόδου | ||||
|
Μέγιστο μήκος αλυσίδας | ||||
|
% επιτυχιών | ||||
3 0,5+1,5 0,25+0,5 0,08+1 0,17 ≈ 2,1στοιχείο λίστας.
Παράδειγμαμε διαφορετική συνάρτηση κατακερματισμού.
|
η(κλειδί) |
|
Αριθμός εισόδου | ||||
|
% επιτυχιών |
Κατά μέσο όρο, θα πάρει 4 1,5 0,25 = 1,5στοιχείο λίστας.
Εάν πρόκειται για σύστημα ανάκτησης πληροφοριών, τότε η απόδοση αναζήτησής του θα αυξηθεί κατά περίπου 25%.
Μέθοδοι για την κατασκευή συναρτήσεων κατακερματισμού
Αρθρωτός κατακερματισμός
Μια απλή, αποτελεσματική και ευρέως χρησιμοποιούμενη μέθοδος κατακερματισμού.
Το μέγεθος του τραπεζιού επιλέγεται ως απλόςαριθμοί Μκαι η συνάρτηση κατακερματισμού υπολογίζεται ως υπόλοιπο τμήμα:
η(κλειδί) = κλειδί % Μ
κλειδί– ακέραια αριθμητική τιμή του κλειδιού,
Μ- αριθμός τιμών κατακερματισμού (καταχωρίσεις πίνακα κατακερματισμού).
Μια τέτοια συνάρτηση ονομάζεται αρθρωτόκαι αλλάζει από 0 πριν ( Μ - 1 ).
Αρθρωτή συνάρτηση κατακερματισμού σε C++:
typedefενθHashIndexType;
HashIndexTypeΧασίσι(ενθκλειδί)
{ ΕΠΙΣΤΡΟΦΗκλειδί % Μ; }
Παράδειγμα
κλειδί = {1, 3, 56, 4, 32, 40, 23, 7, 41,13, 6,7}
Αφήνω Μ = 5
η(κλειδί) = {1, 3, 1, 4, 2, 0, 3, 2, 1, 3, 1, 2}
Σημασία έχει η επιλογή Μ.Για να λάβετε μια τυχαία κατανομή κλειδιών, πρέπει να πάρετε απλόςαριθμός.
Πολλαπλασιαστική μέθοδος
Συνάρτηση κατακερματισμού:
h(κλειδί) =
0 < ΕΝΑ < 1 είναι μια σταθερά.
12 mod5 = 2 (υπόλοιπο μετά τη διαίρεση του 12 με το 5).
5,04 mod1= 0,04 (ξεχωρίζεικλασματικό μέρος)
Παράδειγμα
κλειδί = 123456
Μ = 10000
ΕΝΑ = 0,6180339887499 = 0,618…
η(κλειδί) = =
προσθετική μέθοδος
Χρησιμοποιείται για γραμμέςμεταβλητό μήκος (μέγεθος πίνακα Μισούται με 256).
{ HashIndexType h = 0;
ενώ (*str)
h += (*str)++;
ΕΠΙΣΤΡΟΦΗη;
Το μειονέκτημα της προσθετικής μεθόδου είναι ότι δεν διακρίνονται παρόμοιες λέξεις και αναγραμματισμοί, δηλ. η(XY ) = η(ΥΧ )
προσθετική μέθοδος, όπου το κλειδί είναι μια συμβολοσειρά χαρακτήρων. Σε μια συνάρτηση κατακερματισμού, μια συμβολοσειρά μετατρέπεται σε ακέραιο αθροίζοντας όλους τους χαρακτήρες και επιστρέφοντας το υπόλοιπο μετά τη διαίρεση με Μ (συνήθως μέγεθος τραπεζιού Μ = 256).int h(char *key, int m) (int s = 0;while(*key)s += *key++;return s % m;) αλφάβητοκαι ταξί.Αυτή η μέθοδος μπορεί να τροποποιηθεί ελαφρώς, λαμβάνοντας το αποτέλεσμα αθροίζοντας μόνο τους πρώτους και τελευταίους χαρακτήρες της συμβολοσειράς κλειδιού. int h(char *key, int m) (int len · strlen(key), s = 0;if (λεν< 2) // Если длина ключа равна 0 или 1,s = key; // возвратить keyelse s = key + key;return s % m;}В этом случае коллизии будут возникать только в строках, например, αλφάβητοκαι amc.
η συνάρτηση κατακερματισμού παίρνει ένα κλειδί και υπολογίζει τη διεύθυνση στον πίνακα χρησιμοποιώντας το (η διεύθυνση μπορεί να είναι ένα ευρετήριο στον πίνακα στον οποίο είναι συνδεδεμένες οι αλυσίδες), δηλαδή, για παράδειγμα, μπορεί να πάρει τον αριθμό 3 από τη συμβολοσειρά "abcd ", και από τη συμβολοσειρά "efgh" μπορεί να πάρει τον αριθμό 7 και στη συνέχεια η πρώτη δομή της αλυσίδας λαμβάνεται μέσω κατακερματισμού ή μέσω κατακερματισμού η αναζήτηση συνεχίζεται κατά μήκος της αλυσίδας μέχρι να βρεθεί το "abcd" στην αλυσίδα των δομών από το hash , ή το "efgh" βρίσκεται στην αλυσίδα των δομών από τον κατακερματισμό όταν βρεθεί η δομή με "abcd", λαμβάνονται και επιστρέφονται τα υπόλοιπα δεδομένα της ή επιστρέφονται όλα γενικά (η διεύθυνσή της), έτσι ώστε να μπορεί να πάρει τα υπόλοιπα δεδομένα από αυτό, και η αλυσίδα των δομών δημιουργείται επειδή πολλά διαφορετικά κλειδιά, έχουν την ίδια διεύθυνση στον πίνακα, δηλαδή, για παράδειγμα, η συνάρτηση κατακερματισμού για το "abcd" μπορεί να επιστρέψει 3 και για το "zxf9" μπορεί επίσης να επιστρέψει 3, επομένως συνδέονται σε μια αλυσίδα που κρέμεται στον τρίτο δείκτη του συστοιχία........
Ο πίνακας H αποθηκεύει τα ίδια τα ζεύγη κλειδιού-τιμής. Ο αλγόριθμος εισαγωγής στοιχείων ελέγχει τα κελιά του πίνακα H με κάποια σειρά μέχρι να βρεθεί το πρώτο ελεύθερο κελί, στο οποίο θα γραφτεί το νέο στοιχείο.
Ο αλγόριθμος αναζήτησης αναζητά τα κελιά του πίνακα κατακερματισμού με την ίδια σειρά όπως κατά την εισαγωγή, έως ότου βρεθεί είτε ένα στοιχείο με το επιθυμητό κλειδί είτε ένα ελεύθερο κελί (που σημαίνει ότι δεν υπάρχει στοιχείο στον πίνακα κατακερματισμού).
XOR
Χρησιμοποιείται για χορδές μεταβλητού μήκους. Η μέθοδος είναι παρόμοια με την προσθετική μέθοδο, αλλά διακρίνει παρόμοιες λέξεις. Συνίσταται στο γεγονός ότι η πράξη "αποκλειστικά OR" εφαρμόζεται διαδοχικά στα στοιχεία της συμβολοσειράς
typedef ανυπόγραφο char HashIndexType;
ανυπόγραφο char Rand8;
HashIndexType Hash(char *str)
( ανυπόγραφο char h = 0;
ενώ (*str) h = Rand8;
ΕΠΙΣΤΡΟΦΗη; }
Εδώ Ακρα8 – έναν πίνακα 256 τυχαίων αριθμών οκτώ bit.
μέγεθος τραπεζιού<= 65536
typedef ανυπόγραφο σύντομο int HashIndexType;
ανυπόγραφο char Rand8;
HashIndexType Hash(char *str)
( HashIndexType h; ανυπόγραφο char h1, h2;
εάν (*str == 0) επιστρέψει 0;
h1 = *str; h2 = *str + 1; str++;
ενώ (*str)
( h1 = Rand8; h2 = Rand8;
str++; )
h = ((HashIndexType)h1<< 8) | (HashIndexType)h2;
επιστροφή h % HashTableSize )
Παγκόσμιος κατακερματισμός
Υποδηλώνει τυχαίοςεπιλογή μιας συνάρτησης κατακερματισμού από κάποιο σύνολο κατά τη διάρκεια εκπλήρωσηπρογράμματα.
Εάν στη μέθοδο πολλαπλασιασμού να χρησιμοποιηθεί ως ΑΛΛΑακολουθία τυχαίοςτιμές αντί για σταθερό αριθμό, λαμβάνετε μια καθολική συνάρτηση κατακερματισμού.
Ωστόσο, ο χρόνος για τη δημιουργία τυχαίων αριθμών θα είναι επίσης μεγάλο.
Μπορεί να χρησιμοποιηθεί ψευδοτυχαίααριθμοί.
// γεννήτρια ψευδοτυχαίων αριθμών
typedefενθHashIndexType;
HashIndexTypeHash(char*v, intm)
( int h, a = 31415, b = 27183;
for(h = 0;*v != 0; v++, a = a*b % (m - l))
h = (a*h + *v) % m;
επιστροφή (η< 0) ? (h + m) : h;