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

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

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

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

AlgorithmV.png

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

Η πρώτη καλά τεκμηριωμένη περιγραφή της κρυπτογράφησης διατυπώθηκε από τον Leon Battista Alberti γυρω στο 1467 και χρησιμοποιούσε ένα μεταλλικό δίσκο για εναλλαγή μεταξύ των αλφαβήτων κρυπτογράφησης.

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

Αυτό που γνωρίζουμε σήμερα σαν αλγόριθμο κρυπτογράφησης 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 δημοσίευσε την περιγραφή ενός παρόμοιου, βασισμένου επίσης στην απλή κρυπτογράφηση του Καίσαρα, ενώπιον του δικαστηρίου του Ερρίκου Γ της Γαλλίας, το 1586. Αργότερα, τον 19ο αιώνα, η κρυπτογράφηση Bellaso εσφαλμένα αποδόθηκε στον Vigenère. Ο David Kahn, στο βιβλίο του oι Codebreakers εξέφρασε τη λύπη του για τη λάθος αναφορά λέγοντας πως η ιστορία είχε αγνοήσει αυτήν την σημαντική συμβολή και αποδόθηκε στον αλγόριθμο το όνομα του Vigenère παρόλο που δεν είχε τίποτα να κάνει με αυτό.

Η κρυπτογράφηση Vigenère απέκτησε τη φήμη ότι είναι εξαιρετικά ισχυρή. Σημειώνεται ότι ο συγγραφέας και μαθηματικός Τσαρλς Λούτγουϊτζ Ντότζσον (γνωστός ως Λιούις Κάρολ) ονόμασε, το 1868, την κρυπτογράφηση Vigenère άσπαστη, στο δημοσίευμά του «Το Αλφάβητο κρυπτογράφησης» σε ένα περιοδικό για παιδιά. Το 1917, το περιοδικό Scientific American, περιέγραψε την κρυπτογράφηση Vigenère ως "αδύνατη να αποκρυπτογραφηθεί"[1]. Αυτή η φήμη δεν της άξιζε. Είναι γνωστό ότι Τσαρλς Μπάμπατζ είχε σπάσει μια παραλλαγή του αλγόριθμου νωρίτερα από το 1854. Ωστόσο, δεν είχε ακόμα δημοσιευθεί το έργο του Kasiski που έσπασε εντελώς την κρυπτογράφηση και την τεχνική που δημοσιεύθηκε τον 19ο αιώνα. Ακόμη και πριν από αυτό, όμως, κάποιοι εξειδικευμένοι κρυπτογράφοι θα μπορούσαν να σπάσουν την κρυπτογράφηση περιστασιακά, ήδη από τον 16ο αιώνα.

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

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

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

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

α β γ δ ε ζ η θ ι κ λ μ ν ξ ο π ρ σ τ υ φ χ ψ ω
Α Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω
Β Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω Α
Γ Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω Α Β
Δ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω Α Β Γ
Ε Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω Α Β Γ Δ
Ζ Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω Α Β Γ Δ Ε
Η Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω Α Β Γ Δ Ε Ζ
Θ Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω Α Β Γ Δ Ε Ζ Η
Ι Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω Α Β Γ Δ Ε Ζ Η Θ
Κ Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω Α Β Γ Δ Ε Ζ Η Θ Ι
Λ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω Α Β Γ Δ Ε Ζ Η Θ Ι Κ
Μ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ
Ν Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ
Ξ Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν
Ο Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ
Π Π Ρ Σ Τ Υ Φ Χ Ψ Ω Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο
Ρ Ρ Σ Τ Υ Φ Χ Ψ Ω Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π
Σ Σ Τ Υ Φ Χ Ψ Ω Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ
Τ Τ Υ Φ Χ Ψ Ω Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ
Υ Υ Φ Χ Ψ Ω Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ
Φ Φ Χ Ψ Ω Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ
Χ Χ Ψ Ω Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ
Ψ Ψ Ω Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ
Ω Ω Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ

Θα χρησιμοποιήσουμε το διπλανό απλό πίνακα αντικατάστασης για την ελληνική γλώσσα και για άτονα κεφαλαία γράμματα:

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

ΔΕΝΒΡΗΚΑΦΑΓΗΤΟ

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

απλααπλααπλααπ

Κάθε στήλη περιέχει τον αλγόριθμο αντικατάστασης του Καίσαρα για ένα γράμμα της λέξης κλειδί.

Παρά το γεγονός ότι υπάρχουν εικοσιτέσσερις στήλες θα χρησιμοποιήσουμε μόνο τις στήλες που έχουν σαν κεφαλίδα τα γράμματα της λέξης κλειδί. Επομένως θα χρησιμοποιήσουμε μόνο τις τρεις στήλες αφού το κλειδί περιέχει δύο φορές το γράμμα άλφα. Για το πρώτο γράμμα του μηνύματος θα χρησιμοποιήσουμε τη στήλη του "α" δηλαδή την πρώτη στήλη. Όπως βλέπουμε στη στήλη αυτή κάθε γράμμα αντιστοιχεί στο ακριβώς όμοιό του. Επομένως το πρώτο γράμμα θα είναι το ίδιο (δηλαδή το "Δ"). Για το δεύτερο γράμμα του μηνύματος θα χρησιμοποιήσουμε τη στήλη που αντιστοιχεί στο "π". Επομένως το "Ε" που είναι το δεύτερο γράμμα του μηνύματος θα γίνει "Υ".

Κρυπτογραφημένο μήνυμα: ΔΥΨΒΡΧΥΑΦΠΝΗΤΖ

Η αποκρυπτογράφηση γίνεται γράμμα-γράμμα. Για το πρώτο γράμμα πηγαίνουμε στη στήλη του πίνακα που αντιστοιχεί στο πρώτο γράμμα της λέξης κλειδί. Βρίσκουμε στη στήλη αυτή το πρώτο γράμμα του κρυπτογραφημένου μηνύματος ("Δ") που είναι το ίδιο ουσιαστικά. Πηγαίνουμε στη στήλη που έχει το δεύτερο γράμμα του κλειδιού (στήλη "π"). Βρίσκουμε στη στήλη αυτή το δεύτερο γράμμα του κρυπτογραφημένου μηνύματος (Υ) και βλέπουμε ότι αντιστοιχεί στο "Ε".

Ασφάλεια[Επεξεργασία | επεξεργασία κώδικα]

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

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

Ο αλγόριθμος χρησιμοποιείται επίσης στο κρυπτοσύστημα Vernam σε συνδυασμό με σημειωματάρια μιας χρήσης. Το κρυπτοσύστημα αυτό θεωρείται άνευ όρων ασφαλές.[2]

Αλγοριθμική περιγραφή[Επεξεργασία | επεξεργασία κώδικα]

Κρυπτογράφηση[Επεξεργασία | επεξεργασία κώδικα]

Στον αλγόριθμο αυτό χρησιμοποιείται ένα μικρό επαναλαμβανόμενο κλειδί για να καθορίσει την τιμή του 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.Ανάλογα κωδικοποιείται και το υπόλοιπο μήνυμα.


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

Αποκρυπτογράφηση[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

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

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

Σημειώσεις[Επεξεργασία | επεξεργασία κώδικα]

  1. State of the Art in Applied Cryptography: Course on Computer Security and Industrial Cryptograph Leuven Belgium, June 1997 Revised Lectures
  2. Τεχνικές Κρυπτογραφίας & Κρυπτανάλυσης σελ.88-

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

  • Βασίλειος Α. Κάτος, Γεώργιος Χρ. Στεφανίδης, επιμ. (2003) (στα Ελληνικά). Τεχνικές Κρυπτογραφίας & Κρυπτανάλυσης. Θεσσαλονίκη: Ζυγός. ISBN 960-8065-40-2. 
  • Knudsen, Lars R. (1998). «Block Ciphers—a survey». Στο: Bart Preneel and Vincent Rijmen. State of the Art in Applied Cryptography: Course on Computer Security and Industrial Cryptograph Leuven Belgium, June 1997 Revised Lectures. Berlin ; London: Springer. σελ. 29. ISBN 3-540-65474-7. 
  • http://www.it.uom.gr/project/ergac/Cryptografisi/ERGASIA_C.htm
  • Mendelsohn, Charles J. (1940). "Blaise De Vigenère and The "Chiffre Carre"," Proceedings of the American Philosophical Society 82, no. 2