Ψηφιακό αποτύπωμα δεδομένων

Ψηφιακό αποτύπωμα δεδομένων (αγγλικά: fingerprint) είναι μια σχετικά μικρή ακολουθία (σειρά) ψηφιακών δεδομένων,^[1] δηλαδή μια συμβολοσειρά (string, bytes) ή σειρά δυαδικών ψηφίων (bits), μοναδική για μία σχετικά πολύ μεγαλύτερη ακολουθία ψηφιακών δεδομένων, όπως είναι αυτή που περιέχεται σε ένα αρχείο υπολογιστή ή ακόμη και σε έναν ολόκληρο σκληρό δίσκο. Η ακολουθία αυτή αποτελεί μια «σύνοψη» της μεγαλύτερης (πηγαίας) ακολουθίας δεδομένων και παράγεται από έναν ειδικό αλγόριθμο. Αυτό που χαρακτηρίζει το ψηφιακό αποτύπωμα όσο και την καταλληλότητα του αλγόριθμου είναι η μοναδικότητά του.^[1] Δηλαδή δύο μεγάλες ακολουθίες ψηφιακών δεδομένων που διαφέρουν σε ένα byte ή ακόμα και ένα bit, θα δώσουν μέσω του ίδιου αλγόριθμου διαφορετικό ψηφιακό αποτύπωμα.

Υπάρχει πολύ μικρή έως μεγάλη πιθανότητα - εξαρτάται από το μέγεθος του ψηφιακού αποτυπώματος - ο αλγόριθμος να μην μας δώσει μοναδικό αποτέλεσμα. Σε αυτή την περίπτωση έχουμε σύγκρουση ψηφιακών αποτυπωμάτων (collision).^[1]

Μοιάζει με την ταυτοποίηση ενός ανθρώπου από το δακτυλικό του αποτύπωμα. Στα αγγλικά λέγεται «fingerprint», δηλαδή χρησιμοποιείται η ίδια λέξη τόσο για το ανθρώπινο δακτυλικό αποτύπωμα, όσο και για το ψηφιακό.

Ιδιότητες Επεξεργασία

Στο σχήμα αριστερά (στήλη input) παρουσιάζονται πέντε διαφορετικά αρχεία κειμένου (μπλε) που διαφέρουν λίγο ή πολύ μεταξύ τους.
Υποβάλλονται στον αλγόριθμο αποτυπώματος (fingerprint function, κίτρινο χρώμα), που δημιουργεί το αντίστοιχο αποτύπωμα (δεξιά, κόκκινο χρώμα).
Τα αποτυπώματα παρουσιάζονται σε δεκαεξαδική κωδικοποίηση και είναι των 8-bytes (64-bits), όλα το ίδιο μέγεθος.
Ακόμη και μια μικρή διαφορά στο πηγαίο αρχείο δίνει εντελώς διαφορετικό ψηφιακό αποτύπωμα.

Μοναδικότητα και μέγεθος αποτυπώματος Επεξεργασία

Για να είναι ένας αλγόριθμος παραγωγής ψηφιακού αποτυπώματος χρήσιμος στην πράξη πρέπει η πιθανότητα παραγωγής του ίδιου αποτυπώματος (collision) από διαφορετικά αρχεία να είναι σχεδόν μηδενική. Πρέπει κάθε αρχείο να μας δίνει διαφορετικό αποτύπωμα. Για παράδειγμα είναι ικανοποιητική στην πράξη μια πιθανότητα μικρότερη από ${\frac {1}{10^{20}}}$ . Αυτό εξαρτάται από το μέγεθος σε bits (ή bytes) του ψηφιακού αποτυπώματος. Όσο πιο μεγάλο τόσο μικρότερη η πιθανότητα παραγωγής του ίδιου αποτυπώματος. Έτσι αν είναι μεγέθους 1 byte (8 bits) οι δυνατές διαφορετικές τιμές (συνδυασμοί 0 και 1) που μπορεί να πάρει είναι $2^{8}=256.$ Μπορεί να αντιστοιχηθεί μοναδικά με 256 το πολύ πηγαία αρχεία. Πολύ μικρός αριθμός όχι για το «αχανές» Διαδίκτυο, αλλά και για το πιό μικρό σύστημα αρχείων (file system). Παρόμοια αν το μέγεθος του ήταν 4 bytes (32-bits), θα μπορούσε να αντιστοιχίσει $2^{32}=4.294.967.296.$ Ίσως μικρός αριθμός για έναν server. Αν ήταν 8 bytes (64-bits), θα είχαμε $2^{64}=18.446.744.073.709.551.616\thickapprox 10^{19,26}.$ Η πιθανότητα μη μοναδικότητας για αποτύπωμα μεγέθους 8 bytes είναι $\thickapprox {\frac {1}{10^{19,26}}}$ που πλησιάζει την ${\frac {1}{10^{20}}}$ , που θέσαμε προηγουμένως. Ένα αποτύπωμα 16 bytes (128-bits), θα μπορεί να αντιστοιχηθεί με $2^{128}\thickapprox 10^{38,5}$ αρχεία, με πιθανότητα αποτυχίας $\thickapprox {\frac {1}{10^{38,5}}}$ , που είναι πολύ ικανοποιητική.

Γενικά, αν $\nu$ είναι ο αριθμός των ψηφιακών αντικειμένων (π.χ. αρχείων) στα οποία θέλουμε να αποδώσουμε ψηφιακό αποτύπωμα μεγέθους $\kappa \!-\!bits$ μέσω του αλγόριθμου $\lambda$ , θα πρέπει το $\nu$ να είναι πολύ μικρότερο του $2^{\kappa }$ , για να εκμηδενίσουμε την πιθανότητα μη μοναδικότητας (collision).^[1]

Μέγεθος ψηφιακών αντικειμένων Επεξεργασία

Το μέγεθος του ψηφιακού αποτυπώματος είναι πάντα σταθερό $\kappa \!-\!bits$ κατάλληλο για την εφαρμογή που το θέλουμε (π.χ. 128-bits). Το ψηφιακό αντικείμενο (π.χ. αρχείο) μπορεί να είναι οποιουδήποτε μεγέθους και είναι ο σχεδιασμός του αλγόριθμου που θα του αποδώσει αποτύπωμα συγκεκριμένου μήκους ( $\kappa \!-\!bits$ ).

Χρήση Επεξεργασία

Ένα αρχείο μπορεί να έχει μεταβληθεί χωρίς απαραίτητα να έχει μεταβληθεί το μέγεθός του. Το μέγεθός του παραμένει το ίδιο όταν αλλάξει ένα byte, ένα bit, ένας χαρακτήρας κειμένου, κλπ. Ο ευκολότερος τρόπος να εντοπίσουμε ότι μεταβλήθηκε είναι να συγκρίνουμε το τρέχον ψηφιακό αποτύπωμα με ένα προηγούμενο.

Η σύγκριση των «μικρών» ψηφιακών αποτυπωμάτων αρκεί για να αποφανθούμε αν οι «μεγάλες» ποσότητες δεδομένων είναι ίδιες ή διαφορετικές ακόμα και σε ένα bit. Για παράδειγμα, με αυτή τη σύγκριση μπορούμε να γνωρίζουμε αν δύο αρχεία υπολογιστών (ή και ολόκληρο σύστημα αρχείων) είναι ίδια χωρίς να χρειάζεται να συγκρίνουμε τα δεδομένα των αρχείων. Ένας web browser μόνο διαβάζοντας το σχετικά μικρό αποτύπωμα (π.χ. 128-bits) ενός αρχείου σε έναν απομακρυσμένο εξυπηρετητή (server) και συγκρίνοντας το με αυτό που είχε «κατεβάσει» σε κάποιο προγενέστερο χρόνο, αποφασίζει αν χρειάζεται να το «ξανακατεβάσει». Υποτίθεται ότι ο απομακρυσμένος server ανανεώνει τα αποτυπώματα των συγκεκριμένων αρχείων σε τακτά χρονικά διαστήματα.

Το ψηφιακό αποτύπωμα εγγράφου χρησιμοποιείται με κάποιες παραλλαγές στον εντοπισμό εγγράφων στο Διαδίκτυο που αποτελούν πιστά αντίγραφα ή μοιάζουν με έγγραφα που καλύπτονται από πνευματικά δικαιώματα. Εφαρμόζεται σε οποιοδήποτε αρχείο, όπως αυτά των πολυμέσων (φωτογραφιών, βίντεο, κλπ).^[2]^[3]

Μεταβολή στα αποτυπώματα σταθερών αρχείων συστήματος μαρτυρά λανθασμένη ή κακόβουλη ενέργεια.

Από την αλλαγή του αποτυπώματος τους, διακρίνουμε τα αρχεία του πηγαίου κώδικα (sources) που πρέπει να μεταγλωττιστούν (compilation) σε μια πλατφόρμα ανάπτυξης λογισμικού.

Ο αλγόριθμος του ψηφιακού αποτυπώματος μπορεί να είναι ή να μοιάζει με συνάρτηση κατακερματισμού (hash function) ή κρυπτογραφική συνάρτηση κατακερματισμού (cryptographic hash function). Αν ο σκοπός του δεν αφορά θέματα ασφαλείας μπορεί να είναι απλούστερος στην υλοποίηση του και γρηγορότερος στο έργο του.

Διευκρίνιση Επεξεργασία

Ο όρος «ψηφιακό αποτύπωμα δεδομένων», είναι διαφορετικός από τον «ψηφιακό αποτύπωμα συσκευών ή web browsers», ο οποίος αναφέρεται στις πληροφορίες που συλλέγονται από ιστοσελίδες και serves, για την ταυτότητα του χρήστη, όταν αυτός χρησιμοποιεί το Διαδίκτυο.

Παραπομπές Επεξεργασία

↑ ^1,0 ^1,1 ^1,2 ^1,3 Broder Z. Andrei, (1993), βλ. πηγές, σελ. 1 του pdf
↑ (Αγγλικά) Sergey Brin, James Davis, Hector Garcia-Molina, (1995). «Copy Detection Mechanisms for Digital Documents Αρχειοθετήθηκε 2016-08-18 στο Wayback Machine.». In: ACM International Conference on Management of Data (SIGMOD 1995), May 22-25, 1995, San Jose, California, από stanford.edu. 18/08/2016. Ανακτήθηκε 11/01/2019.
↑ (Αγγλικά) Broder Z. Andrei, (Spring 2013) «On the resemblance and containment of documents» από princeton.edu. Αρχειοθετήθηκε 15/12/2018. Ανακτήθηκε 11/01/2019.

Πηγές Επεξεργασία

(Αγγλικά) Broder Z. Andrei, (1993) «Some applications of Rabin's fingerprinting method. In Sequences II: Methods in Communications, Security, and Computer Science», pages 143--152. Springer-Verlag, 1993, από princeton.edu. Αρχειοθετήθηκε 11/01/2019. Ανακτήθηκε 11/01/2019.

[:0-1] 1,0 ^1,1 ^1,2 ^1,3 Broder Z. Andrei, (1993), βλ. πηγές, σελ. 1 του pdf

[2] (Αγγλικά) Sergey Brin, James Davis, Hector Garcia-Molina, (1995). «Copy Detection Mechanisms for Digital Documents Αρχειοθετήθηκε 2016-08-18 στο Wayback Machine.». In: ACM International Conference on Management of Data (SIGMOD 1995), May 22-25, 1995, San Jose, California, από stanford.edu. 18/08/2016. Ανακτήθηκε 11/01/2019.

[3] (Αγγλικά) Broder Z. Andrei, (Spring 2013) «On the resemblance and containment of documents» από princeton.edu. Αρχειοθετήθηκε 15/12/2018. Ανακτήθηκε 11/01/2019.

[1]

[2]

[3]