Τρίτη 12 Αυγούστου 2014

Τα Κλειδιά

Πόσα κλειδιά, για την αποκωδικοποίηση ενός κειμένου, χρειάζονται σ’ ένα σύστημα δύο, τριών, τεσσάρων, ..., «n» χρηστών; (Κατ.5/Νο.94)
Πηγή:Μαθηματικοί Κατάσκοποι και Πειρατές της Πληροφορικής, Εκδ. 4π, Σελ. 12

Λύση

Α)Για δύο χρήστες χρειάζεται ένα μόνο κλειδί: C(n,2)=n*(n-1)/2=2*(2-1)/2=2-1=1 Β)Για τρεις χρήστες χρειάζονται τρία κλειδιά: C(n,2)=n*(n-1)/2=3*(3-1)/2=(3*2)/2=3 i)Ένα για την επικοινωνία ανάμεσα στον «Α» και στο «Β». ii) Ένα για την επικοινωνία ανάμεσα στον «Α» και στο «Γ». iii) Ένα για την επικοινωνία ανάμεσα στο «Β» και στο «Γ». Γ)Για τέσσερις χρήστες χρειάζονται έξι κλειδιά: i)Ένα για την επικοινωνία ανάμεσα στον «Α» και στο «Β». ii)Ένα για την επικοινωνία ανάμεσα στον «Α» και στο «Γ». iii)Ένα για την επικοινωνία ανάμεσα στο «A» και στο «Δ». iv) Ένα για την επικοινωνία ανάμεσα στο «Β» και στο «Γ». v) Ένα για την επικοινωνία ανάμεσα στο «Β» και στο «Δ». vi) Ένα για την επικοινωνία ανάμεσα στο «Γ» και στο «Δ». C(n,2)=n*(n-1)/2=4*(4-1)/2=(4*3)/2=2*3=6 Δ)Γενικά:Για «n» χρήστες χρειάζονται:C(n,2)=n*(n-1)/2 κλειδιά. Λύση του Γ. Ριζόπουλου. Κάρλο,δεν ξέρω πού βρήκες αυτό το θέμα, πάντως η ερώτηση δεν είναι σαφώς ορισμένη,ούτε έχει τετριμμένη απάντηση. Η λέξη "σύστημα" θα μπορούσε να σημαίνει χίλια-δυο διαφορετικά πράγματα, για τα οποία έχουν γραφτεί και γράφονται ολόκληρα βιβλία σχετικά με κρυπτογράφηση, δημόσια και ιδιωτικά κλειδιά (Public & Private Keys) και γενικά encryption. Θα επιχειρήσω μια γενική προσέγγιση ,μαντεύοντας και από το σχήμα, τι είναι αυτό που έχει κατά νού μάλλον ο ερωτών. Καταρχάς το πόσα κλειδιά απαιτούνται είναι συνάρτηση του βαθμού ασφαλείας που θέλουμε. Αυτό είναι προφανές. Ένα "σύστημα" θεωρητικά απόρθητο, θα μπορούσε να εξυπηρετηθεί και μέ ένα μόνο δημόσιο κλειδί, το ίδιο για όλους τους χρήστες. Τέτοιο σύστημα βεβαίως στην πράξη δεν υπάρχει, καθότι προϋποθέτει ιδανικές καταστάσεις ασφαλείας. Μιλώντας λοιπόν για one-way hash function κρυπτογραφία (δηλαδή "μίας κατεύθυνσης" πληροφορία)όπου δεν υπάρχει ανάδραση/αναπληροφόρηση (feedback)το θέμα λύνεται τετριμμένα. Για τον άλλο βασικό τύπο της "συμμετρικής κρυπτογράφησης" (Symmetric Cryptography)που είναι μάλλον αυτός που εννοεί ο ερωτών, μπορούμε να πούμε τα εξής: Για πλήρη ασφάλεια πρέπει να υπάρχει ένα ξεχωριστό κλειδί για κάθε ζεύγος χρηστών. Ήτοι για n χρήστες, [n(n-1)]/2 κλειδιά. Ο αριθμός είναι πολύ μεγάλος και η ασφαλής διανομή τόσων κλειδιών,προβληματική. Έτσι, ο συνηθέστερος (για "μέσα" επίπεδα ασφαλείας) τρόπος επικοινωνίας είναι η Public Key Cryptography (Κρυπτογράφηση δημοσίου κλειδιού) ,όπου χρησιμοποιείται ένα διαφορετικό κλειδί για κωδικοποίηση (encrypting) και διαφορετικό για αποκωδικοποίηση(decrypting). o A στέλνει στον Β το public key του και ο Β στον Α το δικό του public key. Ο Α μετά κωδικοποιεί το μύνημά του με το κλειδί του Β και τού το στέλνει, γνωρίζοντας πως μόνο ο Β (ο κάτοχος του ιδιωτικού του -private key κλειδιου)μπορεί να αποδικωποιήσει το μύνημα. Ομοίως και αντιστρόφως από τον Β στον Α. Με αυτόν τον τρόπο επιτυγχάνονται πολλά οφέλη. Τα δημόσια κλειδιά μπορούν να αποθηκευτούν σε βάσεις δεδομένων (databases) έτσι ώστε να μην χρειάζεται να μεταδοθούν (και πιθανώς υποκλαπούν). Επιπροσθέτως λύνεται το πρόβλημα να θέλουμε ν(ν-1)/2 κλειδιά για ν χρήστες ,καθώς τώρα χρειάζονται μόνο 2ν κλειδιά .(ν ιδιωτικά,και ν δημόσια). Δεν μπορώ να το εξηγήσω καλύτερα, και βεβαίως υπάρχουν και άλλα συστήματα ,όπως τα υβριδικά (hybrid cryptosystems) με αρκετά πιο πολύπλοκα μαθηματικά,αλλά δεν είναι του παρόντος. Ενδιαφέροντα πράγματα πάντως, και μπράβο που διάλεξες κάτι πέρα από τα συμβατικά!

6 σχόλια:

RIZOPOULOS GEORGIOS είπε...

Κάρλο,δεν ξέρω πού βρήκες αυτό το θέμα, πάντως η ερώτηση δεν είναι σαφώς ορισμένη,ούτε έχει τετριμμένη απάντηση. Η λέξη "σύστημα" θα μπορούσε να σημαίνει χίλια-δυο διαφορετικά πράγματα, για τα οποία έχουν γραφτεί και γράφονται ολόκληρα βιβλία σχετικά με κρυπτογράφηση, δημόσια και ιδιωτικά κλειδιά (Public & Private Keys) και γενικά encryption.
Θα επιχειρήσω μια γενική προσέγγιση ,μαντεύοντας και από το σχήμα, τι είναι αυτό που έχει κατά νού μάλλον ο ερωτών.
Καταρχάς το πόσα κλειδιά απαιτούνται είναι συνάρτηση του βαθμού ασφαλείας που θέλουμε. Αυτό είναι προφανές. Ένα "σύστημα" θεωρητικά απόρθητο, θα μπορούσε να εξυπηρετηθεί και μέ ένα μόνο δημόσιο κλειδί, το ίδιο για όλους τους χρήστες. Τέτοιο σύστημα βεβαίως στην πράξη δεν υπάρχει, καθότι προϋποθέτει ιδανικές καταστάσεις ασφαλείας.
Μιλώντας λοιπόν για one-way hash function κρυπτογραφία (δηλαδή "μίας κατεύθυνσης" πληροφορία)όπου δεν υπάρχει ανάδραση/αναπληροφόρηση (feedback)το θέμα λύνεται τετριμμένα.
Για τον άλλο βασικό τύπο της "συμμετρικής κρυπτογράφησης" (Symmetric Cryptography)που είναι μάλλον αυτός που εννοεί ο ερωτών, μπορούμε να πούμε τα εξής:
Για πλήρη ασφάλεια πρέπει να υπάρχει ένα ξεχωριστό κλειδί για κάθε ζεύγος χρηστών. Ήτοι για n χρήστες, [n(n-1)]/2 κλειδιά.
Ο αριθμός είναι πολύ μεγάλος και η ασφαλής διανομή τόσων κλειδιών,προβληματική.
Έτσι, ο συνηθέστερος (για "μέσα" επίπεδα ασφαλείας) τρόπος επικοινωνίας είναι η Public Key Cryptography (Κρυπτογράφηση δημοσίου κλειδιού) ,όπου χρησιμοποιείται ένα διαφορετικό κλειδί για κωδικοποίηση (encrypting) και διαφορετικό για αποκωδικοποίηση(decrypting).
o A στέλνει στον Β το public key του και ο Β στον Α το δικό του public key. Ο Α μετά κωδικοποιεί το μύνημά του με το κλειδί του Β και τού το στέλνει, γνωρίζοντας πως μόνο ο Β (ο κάτοχος του ιδιωτικού του -private key κλειδιου)μπορεί να αποδικωποιήσει το μύνημα. Ομοίως και αντιστρόφως από τον Β στον Α. Με αυτόν τον τρόπο επιτυγχάνονται πολλά οφέλη.
Τα δημόσια κλειδιά μπορούν να αποθηκευτούν σε βάσεις δεδομένων (databases) έτσι ώστε να μην χρειάζεται να μεταδοθούν (και πιθανώς υποκλαπούν).
Επιπροσθέτως λύνεται το πρόβλημα να θέλουμε ν(ν-1)/2 κλειδιά για ν χρήστες ,καθώς τώρα χρειάζονται μόνο 2ν κλειδιά .(ν ιδιωτικά,και ν δημόσια).
Δεν μπορώ να το εξηγήσω καλύτερα, και βεβαίως υπάρχουν και άλλα συστήματα ,όπως τα υβριδικά (hybrid cryptosystems) με αρκετά πιο πολύπλοκα μαθηματικά,αλλά δεν είναι του παρόντος.
Ενδιαφέροντα πράγματα πάντως, και μπράβο που διάλεξες κάτι πέρα από τα συμβατικά!

Papaveri είπε...

@Γ. Ριζόπουλος
Γιώργο όταν αναρτήσω τη λύση θα γράψω και τη πηγή που το βρήκα. Υπάρχει ένας τύπος που καθορίζει πόσα κλειδιά απαιτούνται.

RIZOPOULOS GEORGIOS είπε...

Eννοείς διαφορετικός τύπος απ'αυτούς που έγραψα;

Papaveri είπε...

@Γ. Ριζόπουλος
Ναι, διαφορετικός.

Papaveri είπε...

@Γ. Ριζόπουλος
Γιώργο δεν ισχύει το σχόλιο που έκανα για διαφορετικό τύπο, διότι όταν διάβασα το σχόλιό σου δεν μπόρεσα να το διαβάσω μέχρι τέλος. Οπότε πολύ σωστά έλυσες το γρίφο. Συγχαρητήρια!!

Papaveri είπε...

@Γ. Ριζόπουλος
Σ' ευχαριστώ για τα καλά σου λόγια. Αυτή η αναγνώρισεη μου δίνει κουράγιο για να παρουσιαζω ποιοτικα αναβαθμισμένους γρίφους.

 

Papaveri48 © 2010

PSD to Blogger Templates by OOruc & PSDTheme by PSDThemes