[Powered by Google Translate] [Vigenere Cipher] [Nate Hardison - Πανεπιστήμιο του Χάρβαρντ] [Αυτό είναι CS50. - CS50.TV] Γνωρίστε Alice. Alice έχει ένα φλερτ με τον Bob. Ευτυχώς για την Alice, ο Bob έχει, επίσης, τα μάτια γι 'αυτήν. Δυστυχώς για τους εκκολαπτόμενους ρομαντισμό τους, όχι μόνο οι γονείς της Αλίκης αποδοκιμάζουν Bob, αλλά ο καλύτερος φίλος της Αλίκης, Evelyn, έχει ένα μυστικό φλερτ με τον Bob εγωιστικά και θέλει να τους κρατήσει χώρια με κάθε κόστος. Για να στείλετε μυστικά μηνύματα ο ένας στον άλλο ότι οι γονείς της Alice δεν μπορεί να καταλάβει, 

Alice και ο Bob έχουν χρησιμοποιήσει μια Caesar cipher, το οποίο λειτουργεί με τη μετατόπιση του αλφάβητο από ένα ορισμένο αριθμό γραμμάτων ως έναν τρόπο για να δημιουργήσει ένα νέο αλφάβητο. Κάθε γράμμα στο αρχικό αλφάβητο τότε αντικατασταθεί από αντίστοιχη επιστολή του μετατοπίστηκε στο νέο αλφάβητο. Αγαπημένος αριθμός της Αλίκης είναι 3, το οποίο Bob ξέρει, έτσι που χρησιμοποιεί 3 ως κλειδί της. Όταν αλλάζει το αγγλικό αλφάβητο με 3 γράμματα, Καθίσταται Δ Α, Β γίνεται Ε, C γίνεται F, και ούτω καθεξής. 

Όταν παίρνει στο άκρο της αλφαβήτου - με τα γράμματα Χ, Υ, και Ζ - τυλίγει γύρω ακριβώς πίσω στην αρχή του αλφαβήτου X και υποκατάστατα με Α, Β Υ με, και Z με C. Έτσι, όταν Alice πηγαίνει για την κρυπτογράφηση μυστικό μήνυμα της στον Bob, δηλαδή "μου Συνάντηση στο πάρκο σε έντεκα," κάνει ακριβώς τις κατάλληλες αντικαταστάσεις. Μ γίνεται P, E γίνεται H, και ούτω καθεξής μέχρι της μη κρυπτογραφημένο μήνυμα απλού κειμένου μετατρέπεται σε κρυπτογραφημένο κείμενο κρυπτογραφημένο: "Phhw ph dw WKH sdun dw hohyhq dp" σίγουρα δεν είναι το πιο ρομαντικό ήχο, Alice, αλλά πιστεύω ότι αυτό θα κάνει. 

Alice δίνει το μήνυμα για να Evelyn να παραδώσει στο σπίτι του Bob. Αλλά Evelyn παίρνει αντ 'αυτού πίσω στο δωμάτιό της και προσπαθεί να σπάσει τον κώδικα. Ένα από τα πρώτα πράγματα που Evelyn ανακοινώσεις είναι ότι το γράμμα H εμφανίζεται 7 φορές στο μήνυμα, πολλές φορές περισσότερο από ό, τι οποιαδήποτε άλλη επιστολή. Γνωρίζοντας ότι το γράμμα Ε είναι η πιο κοινή στην αγγλική γλώσσα, συμβαίνουν σχεδόν 13% του χρόνου, Evelyn εικασίες ότι η H έχει αντικατασταθεί Ε, προκειμένου να καταστεί το μυστικό μήνυμα και προσπαθεί χρησιμοποιώντας ένα κλειδί 3 να το αποκρυπτογραφήσει. 

Μέσα σε λίγα λεπτά, Evelyn υπολογίζει τα σχέδια της Alice και κακία καλεί τους γονείς της Αλίκης. Αν Alice και ο Bob λαμβάνονται CS50, θα έχει λάβει γνώση αυτής συχνότητας-ανάλυση επίθεση στο Caesar cipher, η οποία επιτρέπει να μπορεί να σπάσει αρκετά γρήγορα. Θα πρέπει επίσης να γνωρίζει ότι το κρυπτογράφημα είναι εύκολα υπόκειται σε επίθεση brute-force, σύμφωνα με την οποία θα μπορούσε να Evelyn έχουν δοκιμάσει όλες τις πιθανές 25 πλήκτρα, ή μεταβολές της αγγλικής αλφαβήτου, για να αποκρυπτογραφήσει το μήνυμα. Γιατί 25 πλήκτρα και όχι 26; 

Λοιπόν, προσπαθήστε μετατόπιση κάθε γράμμα κατά 26 θέσεις, και θα δείτε γιατί. Εν πάση περιπτώσει, μια brute-force επίθεση θα έχουν λάβει Evelyn λίγο περισσότερο αλλά όχι αρκετά για να την κρατήσει από την παρεμπόδιση Alice και του Bob σχέδια, ειδικά αν Evelyn έχει την βοήθεια ενός υπολογιστή η οποία θα μπορούσε να σχίσει μέσω όλων των 25 περιπτώσεις μέσα σε μια στιγμή. Έτσι, αυτό το πρόβλημα μαστίζει επίσης άλλοι που χρησιμοποίησαν το Caesar cipher, και ως εκ τούτου οι άνθρωποι άρχισαν να πειραματίζονται με πιο πολύπλοκες ciphers αντικατάστασης που χρησιμοποιούν πολλαπλές τιμές μετατόπιση αντί για ένα. Ένα από τα πιο γνωστά-από αυτά ονομάζεται Vigenere κρυπτογράφημα. Πώς μπορούμε να πάρουμε πολλές τιμές στροφή; Λοιπόν, αντί να χρησιμοποιεί ένα αριθμό ως το κλειδί, χρησιμοποιούμε μια λέξη για το κλειδί. Θα χρησιμοποιήσουμε κάθε γράμμα στο πλήκτρο για να δημιουργήσει έναν αριθμό, και το αποτέλεσμα είναι ότι θα έχουμε πολλά Caesar cipher-κλειδιά στυλ για τη μετατόπιση γραμμάτων. 

Ας δούμε πώς αυτό λειτουργεί με την κρυπτογράφηση μήνυμα της Alice στον Bob: Γνωρίστε μου στο πάρκο σε έντεκα Εγώ, προσωπικά, πιστεύω μπέικον είναι νόστιμο, οπότε ας το χρησιμοποιήσουμε αυτό ως το κλειδί. Αν πάρουμε το μήνυμα σε κρυπτογραφημένη, τη μορφή του απλού κειμένου, βλέπουμε ότι είναι 25 γράμματα. Μπέικον έχει μόνο 5 γράμματα, έτσι πρέπει να επαναλάβετε 5 φορές ώστε να το προσαρμόσετε το μήκος του απλού κειμένου. 

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

Εμείς πάμε για να το κάνετε αυτό, χρησιμοποιώντας τη θέση του κάθε γράμματος των βασικών μας - μπέικον - το Α έως το Ω αλφάβητο. Επειδή είμαστε επιστήμονες ηλεκτρονικών υπολογιστών, θα ήθελα να αρχίσει να μετρά στο μηδέν αντί για 1, έτσι θα πάμε να πούμε ότι η θέση του πρώτου γράμματος του μπέικον - Β - είναι στη θέση 1 στο μηδενικό-δείκτη στο αλφάβητο Α Ζ, Δεν 2, καθώς και η θέση του Α είναι μηδέν, δεν 1. Χρησιμοποιώντας αυτόν τον αλγόριθμο, μπορούμε να βρούμε τις τιμές μετατόπισης για κάθε γράμμα. 

Για να κρυπτογραφήσετε το απλό κείμενο και να δημιουργήσει κρυπτογραφημένο κείμενο, Ας στραφούμε απλά κάθε γράμμα του απλού κειμένου από το συγκεκριμένο ποσό, όπως ακριβώς κάνουμε με την κρυπτογράφησης του Καίσαρα, τη συσκευασία από το Ω στο Α πίσω αν είναι απαραίτητο. Μ παίρνει μετατοπιστεί κατά 1 θέση για να γίνει N. Το πρώτο Ε δεν μετακινείται καθόλου, αλλά τη δεύτερη στροφή E με 2 θέσεις έως το G και Τ με 14 θέσεις για να H. Αν δουλεύουμε με το απλό κείμενο, καταλήγουμε με, "Zf Negh av HUF pcfx bt gzrwep ουγκιά" Και πάλι, δεν είναι πολύ ρομαντικό άκουσμα, αλλά σίγουρα αινιγματικός. Αν η Alice και ο Bob γνώριζε Vigenere κρυπτογράφησης, Θα τους ήταν ασφαλή από τα αδιάκριτα βλέμματα του Evelyn; Ποια είναι η γνώμη σας; Θα θέλατε να συνδεθείτε στο λογαριασμό σας αν η τράπεζά σας αποφάσισε να χρησιμοποιήσει 

Vigenere κρυπτογράφησης για την κρυπτογράφηση της επικοινωνίας σας με τον κωδικό σας ως κλειδί σας; Αν ήμουν στη θέση σου, δεν θα ήθελα. Και ενώ η Evelyn θα μπορούσε να κρατήσει απασχολημένο για αρκετό καιρό Alice και ο Bob να πληρούν τους προς τα πάνω, δεν αξίζει τον κόπο για την Alice και ο Bob στην τύχη του. Vigenere cipher είναι σχετικά εύκολο να σπάσει, αν γνωρίζετε το μήκος του κλειδιού γιατί τότε μπορεί να θεραπεύσει το κρυπτογραφημένο κείμενο κρυπτογραφημένο ως το γινόμενο των λίγων συνυφασμένη αλγόριθμους κρυπτογράφησης του Καίσαρα. 

Η εύρεση του μήκους του κλειδιού δεν είναι τρομερά δύσκολο, είτε. Αν το αρχικό απλού κειμένου μήνυμα είναι αρκετά μεγάλο χρονικό διάστημα ότι ορισμένες λέξεις εμφανίζονται πολλές φορές, τελικά θα δείτε επανάληψη καλλιέργεια μέχρι το κρυπτογραφημένο κείμενο κρυπτογράφησης, όπως σε αυτό το παράδειγμα, όπου θα δείτε MONCY εμφανίζονται δύο φορές. Επιπλέον, μπορείτε να εκτελέσετε μια brute-force επίθεση με τον αλγόριθμο. Αυτό έχει λάβει σημαντικά μεγαλύτερη από ό, τι μια επίθεση brute-force με τον αλγόριθμο του Καίσαρα, οποία μπορεί να γίνει σχεδόν ακαριαία με έναν υπολογιστή αφού αντί για 25 περιπτώσεις, για να ελέγξετε έχεις 26 ⁿ - 1 δυνατότητες, όπου n είναι το μήκος του άγνωστου κλειδιού. 

Αυτό συμβαίνει επειδή κάθε γράμμα στο πλήκτρο θα μπορούσε να είναι οποιοδήποτε από τα 26 γράμματα, Α έως το Ζ, και ένα έξυπνο άτομο θα προσπαθήσει να χρησιμοποιήσει ένα κλειδί που δεν μπορεί να βρεθεί σε ένα λεξικό, πράγμα που σημαίνει ότι θα έπρεπε να δοκιμάσει όλα τα περίεργα συνδυασμούς γραμμάτων, όπως ZXXXFF, και όχι μόνο ένα ζευγάρι εκατό χιλιάδες λέξεις στο λεξικό. Το μείον 1 έρχεται στο μαθηματικά γιατί δεν θα θέλετε να χρησιμοποιήσετε ένα κλειδί με ένα μόνο είναι, αφού με μηδενικό δείκτη αλφαβήτου μας που θα σας δώσει το ίδιο αποτέλεσμα ως χρήση κρυπτογράφησης του Καίσαρα με ένα κλειδί από το μηδέν. Τέλος πάντων, 26 ​​ⁿ - 1 έχει πάρει μεγάλες μάλλον γρήγορα, αλλά ενώ σίγουρα δεν θα θέλατε να δοκιμάσετε το σπάσιμο ενός cipher με το χέρι με αυτόν τον τρόπο, αυτό είναι σίγουρα εφικτό με έναν υπολογιστή. Ευτυχώς για την Alice και ο Bob, και για ηλεκτρονικές τραπεζικές συναλλαγές, κρυπτογράφους έχουν αναπτύξει πιο ασφαλείς τρόπους για την κρυπτογράφηση μυστικό μηνύματα από τα αδιάκριτα βλέμματα. 

Ωστόσο, αυτό είναι ένα θέμα για μια άλλη φορά. Το όνομά μου είναι Nate Hardison. Αυτό είναι CS50.