.
Η συνάρτηση κατακερματισμού, είναι μια μαθηματική συνάρτηση που δέχεται ως είσοδο κάποιο δεδομένο τυχαίου μεγέθους και επιστρέφει ένα ακέραιο σταθερού μεγέθους αναπαράστασης. Το μέγεθος αυτό μπορεί να είναι από 32bit μέχρι 256bit ή περισσότερα, ανάλογα με το λόγο χρήσης της συνάρτησης. Οι τιμές που επιστρέφει η συνάρτηση κατακερματισμού ονομάζονται τιμές κατακερματισμού (hash values), κώδικες κατατεμαχισμού (hash codes), αθροίσματα κατακερματισμού (hash sums) ή απλά τιμές κατακερματισμού (hashes).
Η συγκεκριμένη συνάρτηση κατακερματισμού (hash function) αντιστοιχίζει ονόματα-κλειδιά (keys) σε ακέραιους αριθμούς από το 0 μέχρι και 15 (τιμές κατακερματισμού - hashes). Στο συγκεκριμένο παράδειγμα υπάρχει μια σύγκρουση κλειδιών. Το όνομα-κλειδί "John Smith" και "Sandra Dee" έχουν την ίδια τιμή κατακερματισμού.
Οι τιμές αυτές θα πρέπει να είναι διαφορετικές για διαφορετική είσοδο, καθώς η κύρια χρησιμότητα αυτών των συναρτήσεων είναι να ταυτοποιούν τα δεδομένα. Μια εφαρμογή αυτή της ιδιότητας είναι στην υλοποίηση της δομής δεδομένων σύνολο όπου θα πρέπει να αποτρέπεται η προσθήκη στοιχείου που το σύνολο ήδη περιέχει. Σε αυτή την περίπτωση τιμές 32bit αρκούν, εκτός αν το σύνολο μπορεί να φτάσει υπερβολικά μεγάλο μέγεθος. Μια άλλη εφαρμογή είναι στη δημιουργία ψηφιακών υπογραφών όπου χρησιμοποιούνται τιμές κατατεμαχισμού μεγάλου μεγέθους για να ελαχιστοποιηθεί ο κίνδυνος πλαστογράφησής τους.
Μια συνάρτηση κατακερματισμού μπορεί να αντιστοιχίζει δύο ή περισσότερες εισόδους στην ίδια τιμή κατακερματισμού. Στις περισσότερες εφαρμογές είναι επιθυμητή η ελαχιστοποίηση αυτών των συγκρούσεων. Αυτό σημαίνει ότι η συνάρτηση κατακερματισμού θα πρέπει να αντιστοιχίζει κάθε είσοδο σε διαφορετική τιμή κατατεμαχισμού. Ανάλογα με την εφαρμογή χρήσης, η συνάρτηση κατακερματισμού σχεδιάζεται με διαφορετικές προδιαγραφές. Η ιδέα αυτών των συναρτήσεων εμφανίστηκε το 1950 αλλά ακόμη και σήμερα ο σχεδιασμός μιας καλής συνάρτησης κατατεμαχισμού είναι αντικείμενο έρευνας.
Οι συναρτήσεις κατακερματισμού συσχετίζονται (αν και πολλές φορές μπερδεύονται ως έννοιες) με τις συναρτήσεις αθροίσματος ελέγχου (π.χ. ο Κυκλικός Έλεγχος Πλεονασμού), τον υπολογισμό ψηφίου ελέγχου (check digit), δακτυλικά αποτυπώματα (fingerprints) και τους κώδικες ελέγχου λαθών (error correcting codes)..
Εφαρμογές συναρτήσεων κατακερματισμού
Πίνακες κατακερματισμού
Παράδειγμα πίνακα κατακερματισμού Το κάθε όνομα (key) αντιστοιχίζεται σε την βοήθεια της συνάρτησης κατακερματισμού (hash function) σε ένα πίνακα κατακερματισμού (hash table) που δημιουργεί αντιστοιχίσεις σε αριθμούς τηλεφώνων (ευρετήριο κατακερματισμού ).
Οι συναρτήσεις κατακερματισμού κυρίως χρησιμοποιούνται σε πίνακες κατατεμαχισμού (hash tables), για γρήγορη εύρεση εγγραφών σε βάσεις δεδομένων. Για παράδειγμα σε ένα λεξικό έχουμε τις λέξεις-κλειδιά και τους αντίστοιχους ορισμούς-περιγραφές. Η συνάρτηση κατακερματισμού μπορεί να εξυπηρετήσει αντιστοιχώντας τις λέξεις-κλειδιά με τις αντίστοιχες τιμές κατατεμαχισμού (ονομάζεται πίνακας κατακερματισμού - hash table, στην ελληνική βιβλιογραφία αναφέρεται και ως πίνακας κατακερματισμού).
Σε γενικές γραμμές μια συνάρτηση κατακερματισμού μπορεί να αντιστοιχίζει διαφορετικά κλειδιά στην ίδια τιμή κατακερματισμού . Τότε η τιμή κατακερματισμού αντιστοιχίζει σε ένα σύνολο από εγγραφές, αντί για μια μόνο εγγραφή. Σε αυτήν την περίπτωση η/οι εγγραφή/ές που αντιστοιχίζει μια τιμή κατακερματισμού ονομάζεται bucket (μεταφράζεται ως κουβάς ή κάδος και σημαίνει μονάδα αποθήκευσης). Ο πίνακας κατακερματισμού τότε ονομάζεται ευρετήριο κατακερματισμού (hash indices ή bucket indices).
Γενικότερα στην τεχνική του ευρετηρίου κατακερματισμού, η συνάρτηση κατακερματισμού μας δείχνει σε ποιο σημείο μέσα στην βάση βρίσκεται η εγγραφή. Στην πράξη μας δείχνει σε ποιο σημείο θα πρέπει να ξεκινήσουμε για την αναζήτηση.
Αλγόριθμοι συναρτήσεων κατακερματισμού
Συναρτήσεις αθροισμάτων ελέγχου
Έλεγχος ακεραιότητας κατεβασμένων αρχείων π.χ. από το Διαδίκτυο: Σε μεγάλα downloads, μπορούμε συνήθως να κατεβάσουμε και ένα αρχείο αθροίσματος ελέγχου (checksum) που περιέχει μέσα τις τιμές κατατεμαχισμού του μεγάλου αρχείου. Εκτελώντας τη συνάρτηση κατατεμαχισμού στο δικό μας μηχάνημα, μπορούμε να συγκρίνουμε τις συνόψεις: αν είναι ίδιες το αρχείο έχει κατέβει σωστά.
Κρυπτογραφικές συναρτήσεις κατακερματισμού
Κύριο λήμμα: Κρυπτογραφική Συνάρτηση κατακερματισμού
Η κρυπτογραφική συνάρτηση κατατεμαχισμού SHA-1. Εδώ φαίνονται μόνο τα 4 πρώτα bytes (4*8=32bits) σε δεκαεξαδική μορφή της συνάρτησης SHA-1 (η έξοδος της SHA-1 είναι 160bits ή 20bytes).
Οι κρυπτογραφικές συναρτήσεις όπως η SHA-1 παρέχουν εγγύηση ότι η έξοδος για κάθε διαφορετική είσοδο είναι μοναδική σε σύγκριση με τις "χαλαρότερες" συναρτήσεις αθροίσματος ελέγχου ή τις συναρτήσεις δακτυλικών αποτυπωμάτων (fingerprints). Επειδή η έξοδος είναι αυστηρότερα μοναδική, αυτές οι συναρτήσεις πολλές φορές χρησιμοποιούνται και ως γενικής χρήσεως συναρτήσεις κατατεμαχισμού.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
