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

Ο αλγόριθμος κρυπτογράφησης Vigenère (Βιζενέρ) (γαλλική προφορά: [[viʒnɛːʁ]]) είναι μία μέθοδος κρυπτογράφησης σε αλφαβητικό κείμενο στο οποίο εφαρμόζονται διαφορετικοί αλγόριθμοι κρυπτογράφησης Καίσαρα με βάση τη θέση των γραμμάτων μιας λέξης ή φράσης κλειδί. Είναι μια απλή μορφή της πολυαλφαβητικής υποκατάστασης.
Η κρυπτογράφηση Vigenère  έχει εφευρεθεί εκ νέου πολλές φορές. Τη μέθοδο αρχικά περιέγραψε ο Giovan Battista Bellaso το 1553.
Ο αλγόριθμος είναι γνωστός, γιατί, ενώ είναι εύκολο να τον κατανοήσει και να τον εφαρμόσει ακόμα και ένας αρχάριος στην κρυπτογράφηση, φαίνεται συχνά να είναι αδύνατη η αποκρυπτογράφηση του κρυπτογραφημένου κειμένου. Αυτός είναι και ο λόγος που κέρδισε την περιγραφή «η κρυπτογράφηση που δεν αποκρυπτογραφείται» (γαλλικά: Le Chiffre indéchiffrable).

Ιστορική Εξέλιξη

Η πρώτη καλά τεκμηριωμένη περιγραφή της κρυπτογράφησης διατυπώθηκε από τον Λεόν Μπαττίστα Αλμπέρτι (Leon Battista Alberti) γύρω στο 1467 και χρησιμοποιούσε ένα μεταλλικό δίσκο για εναλλαγή μεταξύ των αλφαβήτων κρυπτογράφησης. 
Το σύστημα του Αλμπέρτι άλλαζε αλφάβητο κρυπτογράφησης μόνο μετά από έναν αριθμό λέξεων, χρησιμοποιώντας ενδείξεις που αναφέρονταν στη σύνταξη της επιστολής. Αργότερα, το 1508, o Γιοχάννες Τριτέμιους, στο έργο του «Poligraphia», επινόησε τον πίνακα αντικατάστασης (tabula Recta), ένα κρίσιμο στοιχείο της κρυπτογράφησης Vigenère.
Αυτό που γνωρίζουμε σήμερα σαν αλγόριθμο κρυπτογράφησης Βιζενέρ το περιέγραψε αρχικά ο Τζοβάν Μπαττίστα Μπελλάζο (Giovan Battista Bellaso), το 1553, στο βιβλίο του «La cifra del. Sig. Giovan Battista Bellaso». Χρησιμοποίησε τον πίνακα αντικατάστασης (tabula Recta) του Τριτέμιους, αλλά πρόσθεσε ένα επαναλαμβανόμενο "παρασύνθημα" (κλειδί) κρυπτογράφησης ώστε να αλλάζει το αλφάβητο αντικατάστασης σε κάθε γράμμα. Και ενώ οι Αλμπέρτι και Τριτέμιους χρησιμοποίησαν ένα σταθερό μοτίβο αντικαταστάσεων, το σύστημα Μπελλάζο έκανε φανερό ότι η κρυπτογράφηση θα μπορούσε να αλλάξει εύκολα, απλά επιλέγοντας ένα νέο κλειδί. Το κλειδί ήταν συνήθως μεμονωμένες λέξεις ή μικρές φράσεις, που ήταν γνωστές και στα δύο μέρη εκ των προτέρων, ή είχαν μεταδοθεί παράλληλα, μαζί με το μήνυμα. Για τη μέθοδο Μπελλάζο απαιτείται ισχυρή ασφάλεια μόνο για το κλειδί. Δεδομένου ότι είναι σχετικά εύκολο να εξασφαλιστεί μια σύντομη φράση-κλειδί, για παράδειγμα σε μια προηγούμενη ιδιωτική συνομιλία, το σύστημα Μπελλάζο ήταν πολύ πιο ασφαλές. 
Ο  Μπλαιζ ντε Βιζενέρ (Blaise de Vigenère) δημοσίευσε την περιγραφή ενός παρόμοιου, βασισμένου επίσης στην απλή κρυπτογράφηση του Καίσαρα, ενώπιον του δικαστηρίου του Ερρίκου Γ της Γαλλίας, το 1586. Αργότερα, τον 19ο αιώνα, η κρυπτογράφηση Μπελλάζο εσφαλμένα αποδόθηκε στον Βιζενέρ. Ο David Kahn, στο βιβλίο του The Codebreakers εξέφρασε τη λύπη του για τη λάθος αναφορά λέγοντας πως η ιστορία είχε αγνοήσει αυτήν την σημαντική συμβολή και αποδόθηκε στον αλγόριθμο το όνομα του Βιζενέρ παρόλο που δεν είχε τίποτα να κάνει με αυτό. 
Η κρυπτογράφηση Βιζενέρ απέκτησε τη φήμη ότι είναι εξαιρετικά ισχυρή. Σημειώνεται ότι ο συγγραφέας και μαθηματικός Τσαρλς Λούτγουϊτζ Ντότζσον (γνωστός ως Λιούις Κάρολ) ονόμασε, το 1868, την κρυπτογράφηση Βιζενέρ άσπαστη, στο δημοσίευμά του «Το Αλφάβητο κρυπτογράφησης» σε ένα περιοδικό για παιδιά. Το 1917, το περιοδικό Scientific American περιέγραψε την κρυπτογράφηση Vigenère ως "αδύνατη να αποκρυπτογραφηθεί". Αυτή η φήμη δεν της άξιζε. Είναι γνωστό ότι Τσαρλς Μπάμπατζ είχε σπάσει μια παραλλαγή του αλγόριθμου νωρίτερα από το 1854. Ωστόσο, δεν είχε ακόμα δημοσιευθεί το έργο του  Kasiski που έσπασε εντελώς την κρυπτογράφηση και την τεχνική που δημοσιεύθηκε τον 19ο αιώνα. Ακόμη και πριν από αυτό, όμως, κάποιοι εξειδικευμένοι κρυπτογράφοι θα μπορούσαν να σπάσουν την κρυπτογράφηση περιστασιακά, ήδη από τον 16ο αιώνα. 
Η κρυπτογράφηση Βιζενέρ είναι αρκετά απλοϊκή αν χρησιμοποιείται σε συνδυασμό με δίσκους κρυπτογράφησης. Οι ομόσπονδες Πολιτείες της Αμερικής, για παράδειγμα, χρησιμοποιούσαν ένα δίσκο κρυπτογράφησης ορείχαλκου για την εφαρμογή της  κρυπτογράφησης Βιζενέρ  κατά τη διάρκεια του Αμερικανικού Εμφυλίου Πολέμου. Τα μηνύματα της Συνομοσπονδίας δεν ήταν και τόσο ασφαλή και η Ένωση έσπαγε τακτικά τον κώδικά τους. Κατά τη διάρκεια του πολέμου, η ομόσπονδη ηγεσία στηρίχθηκε κυρίως σε τρεις φράσεις κλειδιά, «Manchester Bluff», «Complete Victory» και, όταν ο πόλεμος έφτανε στο τέλος, "Come Retribution".

Ασφάλεια

Στο παράδειγμά μας βλέπουμε ότι χρησιμοποιήθηκαν μόνο τρία είδη αλφαβητικής μετατόπισης. Μεγαλύτερα κλειδιά μπορεί να χρησιμοποιήσουν και τα 24 πιθανά είδη αλφαβητικής μετατόπισης. Βλέπουμε επίσης ότι το γράμμα Α που υπάρχει δύο φορές στο κείμενό μας, την πρώτη φορά κρυπτογραφήθηκε σαν "Α" και τη δεύτερη σαν "Π". Αυτό βοηθάει εν μέρει στην αποτροπή επίθεσης με βάση τη στατιστική κατανομή των γραμμάτων.
Για το σπάσιμο του κώδικα, αρχικά θα πρέπει να υπολογιστεί το μήκος του κλειδιού. Αυτό είναι δυνατό μόνο αν το κλειδί είναι αρκετά μικρότερο από το κείμενο ώστε να επαναλαμβάνεται τουλάχιστον μία φορά. Αυτή τη στιγμή υπάρχουν μόνο δύο γνωστές μέθοδοι: Ο έλεγχος του Kasiski και ο δείκτης σύμπτωσης.
Ο αλγόριθμος χρησιμοποιείται επίσης στο κρυπτοσύστημα Vernam σε συνδυασμό με σημειωματάρια μιας χρήσης. Το κρυπτοσύστημα αυτό θεωρείται άνευ όρων ασφαλές.

Αποκρυπτογράφηση

Για την αποκρυπτογράφηση των χαρακτήρων που διαβάζουμε από το αρχείο εισόδου, αφαιρούμε από τον κάθε χαρακτήρα τον αριθμό που βρίσκεται στη θέση key_table[i] ,(όπου i ένας μετρητής που αρχίζει από το μηδέν και μηδενίζεται όταν γίνει ίσος με το 6 κι έτσι παίρνουμε τον ASCII του αποκωδικοποιημένου χαρακτήρα.
Παράδειγμα αποκρυπτογράφησης του αλγορίθμου Vigenère
Το μήνυμα είναι το : Η­¦nΘΒΙhΆΒo
και μετά την αποκρυπτογράφηση γίνεται : see you at 6
Έτσι ,αφαιρώντας από το ASCII του Η το key_table[1]=84 παίρνουμε το s . Ανάλογη διαδικασία γίνεται για κάθε γράμμα μέχρι να τελειώσει το αρχείο ή να βρούμε το τέλος του αλφαριθμητικού ,αν η εισαγωγή γίνεται από την οθόνη.