Αλγόριθμος κρυπτογράφησης Vigenère

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

Η κρυπτογράφηση Vigenère είναι μια μέθοδος κρυπτογράφησης σε αλφαβητικό κείμενο χρησιμοποιώντας μια σειρά από διαφορετικούς αλγόριθμους κρυπτογράφησης του Καίσαρα με βάση τα γράμματα μιας λέξης-κλειδιού. Είναι μια απλή μορφή της πολυαλφαβιτική υποκατάστασης. Η κρυπτογράφηση Vigenère (γαλλική προφορά: [viʒnɛ ː ʁ]) έχει εφευρεθεί εκ νέου πολλές φορές. Η μέθοδος αρχικά περιγράφεται από τον Giovan Battista Bellaso το 1553 στο βιβλίο του La cifra del. Sig. Giovan Battista Bellaso.

Η κρυπτογράφηση είναι γνωστή, γιατί, ενώ είναι εύκολο να τη κατανοήσουν και να την εφαρμόσουν, φαίνεται συχνά από τους αρχάριους να είναι ακατόρθωτο, αυτό ήταν που κέρδισε την περιγραφή Le Chiffre indéchiffrable (γαλλικά για «την ανεξιχνίαστη κρυπτογράφηση»). Κατά συνέπεια, πολλοί άνθρωποι προσπάθησαν να εφαρμόσουν συστήματα κρυπτογράφησης που είναι ουσιαστικά αλγόριθμοι κρυπτογράφησης Vigenère , μόνο για να τους αποκρυπτογραφήσουν.

AlgorithmV.png

Ιστορική Εξέλιξη[Επεξεργασία | επεξεργασία κώδικα]

Η πρώτη τεκμηριωμένη πολυαλφαβιτική περιγραφή της κρυπτογράφησης διατυπώθηκε από τον Leon Battista Alberti γυρω στο 1467 με ένα δίσκο από μέταλλο που χρησιμοποιείται για κρυπτογράφηση και εναλλαγή μεταξύ των αλφαβήτων κρυπτογράφησης. Το σύστημα του Alberti ενεργοποιείται μόνο με αλφάβητα μετά από αρκετές λέξεις, και οι διακόπτες που υποδεικνύονται από τη σύνταξη της επιστολής του αντίστοιχου αλφαβήτου στο κρυπτογράφημα. Αργότερα, το 1508, o Johannes Trithemius, στο έργο του Poligraphia, εφηύρε το tabula Recta, ένα κρίσιμο συστατικό της κρυπτογράφησης Vigenère. Η κρυπτογράφηση Trithemius, όμως, μόνο με μια προϋπόθεση το προοδευτικό, άκαμπτο και προβλέψιμο σύστημα για την εναλλαγή μεταξύ αλφάβητων κρυπτογράφησης.

Αυτό που είναι τώρα γνωστή ως κρυπτογράφηση Vigenère αρχικά περιγράφεται από τον Giovan Battista Bellaso το 1553 στο βιβλίο του La cifra del. Sig. Giovan Battista Bellaso. Έχτισε από την tabula Recta του Trithemius, αλλά πρόσθεσε ένα επαναλαμβανόμενο "παρασύνθημα" (κλειδί) κρυπτογράφησης για να αλλάξει αλφάβητα με κάθε γράμμα. Επιπροσθέτως, Alberti και Trithemius χρησιμοποίησαν ένα σταθερό μοτίβο αντικαταστάσεων, το σύστημα Bellaso σήμαινε το μοτίβο των αντικαταστάσεων που θα μπορούσε να αλλάξει εύκολα, απλά επιλέγοντας ένα νέο κλειδί. Κλειδιά ήταν συνήθως μεμονωμένες λέξεις ή μικρές φράσεις, που είναι γνωστό ότι τα δύο μέρη εκ των προτέρων, ή να μεταδοθεί "εκτός φράσης" μαζί με το μήνυμα. Για τη μέθοδο Bellaso απαιτείται ισχυρή ασφάλεια μόνο για το κλειδί. Δεδομένου ότι είναι σχετικά εύκολο να εξασφαλίσουν μια σύντομη φράση-κλειδί, ας πούμε από μια προηγούμενη ιδιωτική συνομιλία, το σύστημα Bellaso ήταν πολύ πιο ασφαλής.

Η Blaise de Vigenère δημοσίευσε την περιγραφή ενός παρόμοιου, αλλά ισχυρότερη από την κρυπτογράφηση autokey ενώπιον του δικαστηρίου του Ερρίκου Γ της Γαλλίας, το 1586. Αργότερα, τον 19ο αιώνα, η εφεύρεση της κρυπτογράφησης Bellaso ήταν ασύγκριτη από την Vigenère. Ο David Kahn, στο βιβλίο του Codebreakers θρήνησε τη λάθος υπαγωγή λέγοντας ότι «η ιστορία είχε αγνοήσει αυτήν την σημαντική συμβολή και αντί να ονομάζεται μια φθίνουσα και στοιχειώδη κρυπτογράφηση νόμιζε ότι δεν είχε τίποτα να κάνει με αυτό».

Η κρυπτογράφηση Vigenère απέκτησε τη φήμη ότι είναι εξαιρετικά ισχυρή. Σημειώνεται ότι ο συγγραφέας και μαθηματικός Charles Dodgson Lutwidge (Lewis Carroll) ονόμασε από την κρυπτογράφηση Vigenère άθραυστο το 1868 το κομμάτι του "Το Αλφάβητο κρυπτογράφησης" σε ένα περιοδικό για παιδιά. Το 1917, το Scientific American, περιέγραψε την Vigenère κρυπτογράφηση ως "αδύνατο της μετάφρασης». Αυτή η φήμη δεν της άξιζε. Ο Τσαρλς Μπάμπατζ ήταν γνωστό ότι είχε σπάσει μια παραλλαγή του αλγόριθμου νωρίτερα από το 1854. Ωστόσο, δεν είχε δημοσιεύσει το έργο του Kasiski που έσπασε εντελώς την κρυπτογράφηση και την τεχνική που δημοσιεύθηκε τον 19ο αιώνα. Ακόμη και πριν από αυτό, όμως, κάποιοι εξειδικευμένοι κρυπτογράφοι θα μπορούσαν να σπάσουν την κρυπτογράφηση περιστασιακά τον 16ο αιώνα.

Η κρυπτογραφική slide κανόνα χρησιμοποιείται ως βοήθημα για τον υπολογισμό από τον ελβετικό στρατό μεταξύ 1914 και 1940.

Η κρυπτογράφηση Vigenère είναι αρκετά απλό να είναι ένα πεδίο κρυπτογράφησης αν χρησιμοποιείται σε συνδυασμό με δίσκους κρυπτογράφησης. Οι ομόσπονδες Πολιτείες της Αμερικής, για παράδειγμα, χρησιμοποιούσαν ένα δίσκο κρυπτογράφησης ορείχαλκου για την εφαρμογή της κρυπτογράφησης Vigenère κατά τη διάρκεια του Αμερικανικού Εμφυλίου Πολέμου. Τα μηνύματα της συνομοσπονδίας ήταν μακριά από το μυστικό και η Ένωση ράγισε τακτικά τα μηνύματα τους. Κατά τη διάρκεια του πολέμου, η ομόσπονδη ηγεσία στηρίχθηκε κυρίως σε τρεις φράσεις κλειδιά, «Manchester Bluff», «Complete Victory» και, όπως ο πόλεμος ήρθε σε έναν περίβολο, "Come Retribution" . Ο Gilbert Vernam προσπάθησε να επισκευάσει τη σπασμένη κρυπτογράφηση (με τη δημιουργία Vernam-Vigenère κρυπτογράφησης το 1918), αλλά, δεν έχει σημασία τι έκανε, η κρυπτογράφηση ήταν ακόμη ευάλωτη στην κρυπτανάλυση. Το έργο Vernam , ωστόσο, οδήγησε τελικά στην εξέδρα ένα αποδεδειγμένα άθραυστο χρόνο κρυπτογράφησης.

Περιγραφή[Επεξεργασία | επεξεργασία κώδικα]

Σε ένα κρυπτογράφημα Καίσαρα, κάθε γράμμα της αλφαβήτου μετατοπίζεται κατά ένα αριθμό θέσεων, για παράδειγμα, σε ένα κρυπτογράφημα Καίσαρα της αλλαγής 3, το Α θα γίνει D, Β θα γίνει Ε, Y θα γίνει Β και ούτω καθεξής. Η κρυπτογράφηση Vigenère αποτελείται από πολλούς αλγόριθμους κρυπτογράφησης του Καίσαρα σε ακολουθία με διαφορετικές τιμές μετατόπισης.

Για την κρυπτογράφηση, ένας πίνακας του αλφάβητου μπορεί να χρησιμοποιηθεί, ως tabula Recta, Vigenère square, ή Vigenère table. Αποτελείται από το αλφάβητο, που αναγράφεται 26 φορές σε διαφορετικές γραμμές, κάθε αλφάβητο μετατοπίζεται κυκλικά προς τα αριστερά σε σχέση με την προηγούμενη αλφάβητο, που αντιστοιχούν στους 26 πιθανούς αλγόριθμους κρυπτογράφησης του Καίσαρα. Σε διάφορα σημεία κατά τη διαδικασία κρυπτογράφησης, η κρυπτογράφηση χρησιμοποιεί διαφορετικό αλφάβητο σε κάθε μια από τις σειρές. Το αλφάβητο που χρησιμοποιείται σε κάθε σημείο εξαρτάται από μια επαναλαμβανόμενη λέξη-κλειδί.

Vigenère.svg.png

Για παράδειγμα, ας υποθέσουμε ότι το κείμενο για κρυπτογράφηση είναι:
ATTACKATDAWN

Το άτομο που στέλνει το μήνυμα επιλέγει μια λέξη-κλειδί και το επαναλαμβάνει μέχρι να ταιριάζει με το μήκος του απλού κειμένου, για παράδειγμα, η λέξη "lemon":
LEMONLEMONLE

Κάθε γραμμή ξεκινά με ένα πλήκτρο του γράμματος. Το υπόλοιπο της σειράς κατέχει τα γράμματα Α έως το Z(σε σειρά μετατόπισης ). Παρά το γεγονός ότι υπάρχουν 26 βασικές, εσείς θα χρησιμοποιήσετε τόσα κλειδιά (διαφορετικά αλφάβητα) όσα και τα μοναδικά γράμματα που υπάρχουν στο κλειδί σειρά, εδώ μόλις 5 κλειδιά {L, E, M, O, N}. Για διαδοχικά γράμματα από ένα μήνυμα, θα πάρουμε τα διαδοχικά γράμματα από τη σειρά κλειδί, και η κρυπτογράφηση για κάθε μήνυμα θα γίνει χρησιμοποιώντας το αντίστοιχο πλήκτρο της γραμμής. Επιλέξτε το επόμενο γράμμα του κλειδιού, πάτε κατά μήκος της στήλης αυτό το γράμμα για να βρείτε την κεφαλίδα της στήλης που ταιριάζει με το μήνυμα του χαρακτήρα , το γράμμα στη διασταύρωση των [key-row ,msg-col] είναι to κρυπτογραφημένο γράμμα.

Για παράδειγμα, το πρώτο γράμμα του plaintext, το Α, σε συνδυασμό με το L, το πρώτο γράμμα του κλειδιού. Έτσι, χρησιμοποιεί τη γραμμή L και τη στήλη Α από τη Vigenère square ,δηλαδή L. Ομοίως, για τo δεύτερo γράμμα της plaintext, το δεύτερο γράμμα του κλειδιού χρησιμοποιείται, το γράμμα στη γραμμή Ε και και στη στήλη Τ είναι το Χ. Το υπόλοιπο plaintext είναι κρυπτογραφημένο με παρόμοιο τρόπο:
Plaintext: ATTACKATDAWN
Key (Κλειδί): LEMONLEMONLE
Ciphertext: LXFOPVEFRNHR

Η αποκρυπτογράφηση γίνεται με τη μετάβαση στη γραμμή του πίνακα που αντιστοιχεί στο κλειδί, βρίσκοντας τη θέση του γράμματος του ciphertext σε αυτή τη σειρά, και στη συνέχεια, χρησιμοποιώντας την ετικέτα της στήλης ως απλό κείμενο. Για παράδειγμα, στη σειρά L (from LEMON), το κρυπτογράφημα L εμφανίζεται στη στήλη Α, η οποία είναι το πρώτο γράμμα του plaintext. Στη συνέχεια πάμε στη γραμμή E (from LEMON), εντοπίστε το κρυπτογράφημα X που βρίσκεται στη στήλη Τ, έτσι το Τ είναι το δεύτερο γράμμα του plaintext.

Αλγόριθμος κρυπτογράφησης Vigenère[Επεξεργασία | επεξεργασία κώδικα]

Στον αλγόριθμο αυτό χρησιμοποιείται ένα μικρό επαναλαμβανόμενο κλειδί για να καθορίσει την τιμή του K για κάθε γράμμα .Σε κάθε βήμα , το γράμμα κλειδί προστίθεται στο γράμμα του κειμένου ώστε να μας δώσουν το κωδικοποιημένο γράμμα. Το κλειδί που χρησιμοποιήσαμε στον αλγόριθμό μας για την κρυπτογράφηση είναι :

key_table = [ 84 , 72 , 65 , 78 , 79 , 83 ] = [ ‘T’ , ‘H’ , ‘A’ , ‘N’ , ‘O’ , ‘S’]

Τα βήματα για την υλοποίηση του αλγορίθμου είναι τα ακόλουθα :

Βήμα 1 : Εισάγουμε το όνομα του αρχείου που θα επεξεργαστούμε

καθώς και του αρχείου αποθήκευσης ή το κείμενο προς

κρυπτογράφηση , αν η έξοδος γίνεται στην οθόνη και

αρχικοποιούμε το μετρητή i=0.

Βήμα 2 : Διαβάζουμε έναν χαρακτήρα ch είτε από το αρχείο είτε από

το αποθηκευμένο κείμενο που δώσαμε με το πληκτρολόγιο.

Βήμα 3 : Προσθέτουμε στον χαρακτήρα ch που διαβάσαμε τον

αντίστοιχο αριθμό που βρίσκεται στη θεση key_table[i] και

παίρνουμε έτσι το κωδικοποιημένο γράμμα , το οποίο είτε

γράφουμε στο αρχείο εξόδου είτε εμφανίζουμε στην οθόνη .

Βήμα 4 : Αυξάνουμε το μετρητή i κατά ένα .Αν ο μετρητής είναι ίσος

με 6 τον μηδενίζουμε ,αφού θέλουμε να επαναλαμβάνεται

το κλειδί.

Βήμα 5 : Αν έχουμε φτάσει στο τέλος του αρχείου ή αν βρήκαμε το

χαρακτήρα τέλους των αλφαριθμητικών ‘\0’ ,σταματάμε .

Αλλιώς πάμε στο Βήμα 2.

Παράδειγμα για τον αλγόριθμο Vigenère

Ας δουμε πώς κωδικοποιείται το μήνυμα: meet me at the park

με τον αλγόριθμο Vigenère : Α­¦ΒoΐΉhΆΒoΗΌ­aΎ°ΕΏ


Στον αριθμό ASCII κάθε γράμματος προστίθεται ο αριθμός της θέσης του πίνακα-κλειδιού που τους αντιστοιχεί και το αποτέλεσμα είναι ένας νέος αριθμός ASCII που δείχνει ποιος χαρακτήρας θα εμφανιστεί.

Έτσι ,το m έχει ASCII 109 και του αντιστοιχεί η πρώτη θέση του πίνακα key_table ,δηλαδή το 84 .Επομένως ,το κωδικοποιημένο γράμμα είναι ο αριθμός ASCII 193.Ανάλογα κωδικοποιείται και το υπόλοιπο μήνυμα.


Βέβαια , δεν αρκεί μόνο να μπορείς να κρυπτογραφείς ένα κείμενο , χρειάζεται να μπορείς να το επαναφέρεις στην αρχική του μορφή ώστε να μπορεί να διαβαστεί από το δέκτη .Διαφορετικά , δε θα μπορέσουμε να επικοινωνήσουμε σωστά και η κωδικοποιημένη πληροφορία θα χαθεί . Για το λόγο αυτό ,παραθέτουμε στη συνέχεια τους αλγορίθμους αποκρυπτογράφησης των τριών παραπάνω αλγορίθμων κωδικοποίησης .

Αποκρυπτογράφηση του αλγορίθμου Vigenère[Επεξεργασία | επεξεργασία κώδικα]

Για την αποκρυπτογράφηση των χαρακτήρων που διαβάζουμε από το αρχείο εισόδου, αφαιρούμε από τον κάθε χαρακτήρα τον αριθμό που βρίσκεται στη θέση key_table[i] ,(όπου i ένας μετρητής που αρχίζει από το μηδέν και μηδενίζεται όταν γίνει ίσος με το 6 κι έτσι παίρνουμε τον ASCII του αποκωδικοποιημένου χαρακτήρα.

Παράδειγμα αποκρυπτογράφησης του αλγορίθμου Vigenère

Το μήνυμα είναι το : Η­¦nΘΒΙhΆΒo

και μετά την αποκρυπτογράφηση γίνεται : see you at 6

Έτσι ,αφαιρώντας από το ASCII του Η το key_table[1]=84 παίρνουμε το s . Ανάλογη διαδικασία γίνεται για κάθε γράμμα μέχρι να τελειώσει το αρχείο ή να βρούμε το τέλος του αλφαριθμητικού ,αν η εισαγωγή γίνεται από την οθόνη.

Βιβλιογραφία[Επεξεργασία | επεξεργασία κώδικα]