ΕΡΓΑΣΙΑ ΣΤΟ ΜΑΘΗΜΑ : ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ ΣΥΣΤΗΜΑΤΩΝ

Αλγόριθμοι Κρυπτογράφησης Δεδομένων

 

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

α) Αλγόριθμος του Καίσαρα ( Caesar cipher )

β) Αλγόριθμος με κλειδί πίνακα

γ) Αλγόριθμος Vigenere ( Vigenere cipher )

Ας δούμε τώρα πώς υλοποιείται κάθε αλγόριθμος :

1.Κρυπτογράφηση με τον αλγόριθμο του Καίσαρα

Από τις παλιότερες μεθόδους κρυπτογράφησης είναι ο αλγόριθμος του Καίσαρα , όπου αν ένα γράμμα στο αρχικό κείμενο είναι το Νιοστό στο αλφάβητο ,αντικαθίσταται από το ( Ν+Κ )ιοστό γράμμα του αλφαβήτου , όπου Κ είναι ένας σταθερός ακέραιος ( για τον αλγόριθμο του Καίσαρα Κ=3 ).

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

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

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

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

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

Βήμα 3 : Ελέγχουμε αν ο χαρακτήρας είναι ο χαρακτήρας αλλαγής

γραμμής . Αν ναι , τότε γράφουμε στο αρχείο τον ίδιο

χαρακτήρα χωρίς αλλαγή . Αλλιώς πάμε στο Βήμα 4 .

Βήμα 4 : Ελέγχουμε αν ο χαρακτήρας είναι το κενό. Αν είναι

εμφανίζουμε το κενό στην οθόνη και γράφουμε το κενό στο

αρχείο εξόδου.Αλλιώς γράφουμε στο αρχείο και στην οθόνη

τον κωδικοποιημένο χαρακτήρα (χαρακτήρας + (KEY=3)).

Βήμα 5 . Αν βρούμε το τέλος του αρχείου ή το χαρακτήρα τέλους των

αλφαριθμητικών ‘\0’ (αν η εισαγωγή του κειμένου γίνεται

από το πληκτρολόγιο ) σταματάμε. Αλλιώς πάμε στο Βήμα 2.

Παράδειγμα χρήσης του αλγορίθμου Caesar

Έστω ότι θέλουμε να κωδικοποιήσουμε το μήνυμα :

meet me at the park

Με τον αλγόριθμο του Caesar θα γίνει :

phhw ph dw wkh sdun

Γενικά , πάμε 3 νούμερα μπροστά από τον ASCII αριθμό του γράμματος και εμφανίζουμε το χαρακτήρα που βρίσκεται εκεί.

Αυτή η μέθοδος δεν είναι τόσο καλή , καθώς ο αναλυτής πρέπει μόνο να μαντέψει την τιμή του Κ : δοκιμάζοντας κάθε μια από τις 26 επιλογές , είναι σίγουρος ότι θα μπορέσει να διαβάσει το μήνυμα.

 

2. Κρυπτογράφηση με κλειδί πίνακα

Μια πολύ καλύτερη μέθοδος είναι να χρησιμοποιήσουμε ένα γενικό πίνακα που θα ορίζει την αλλαγή που πρέπει να γίνει : για κάθε γράμμα του κειμένου προς κρυπτογράφηση ,ο πίνακας λέει ποιο γράμμα να βάλουμε στο κρυπτογραφημένο κείμενο .Ο πίνακας που θα δίνει τις δικές μας αντιστοιχίες είναι ο παρακάτω (key_arr):

letters = [ a b c d e f g h i j k l m n o p q r s t u v w x y z ! . , ? ]

key_arr = [ k o a p l n j b m e u f s q c t z w d y r i v h x g ? ! * , ]

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

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

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

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

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

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

Βήμα 3 : Αναζητούμε σειριακά το χαρακτήρα στον πίνακα letters.

Αν βρεθεί , γράφουμε στο αρχείο ή στην οθόνη το

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

θέση του πίνακα key_arr. Αλλιώς πάμε στο Βήμα 4 .

Βήμα 4 : Ελέγχουμε αν ο χαρακτήρας είναι η αλλαγή γραμμής ,το

κενό ή αν είναι αριθμός και αντίστοιχα γράφουμε στο αρχείο

εξόδου ή στην οθόνη την αλλαγή γραμμής ,το κενό και αν

είναι αριθμός τον γράφουμε αυξημένο κατά τρία .

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

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

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

 

Παράδειγμα για τον αλγόριθμο με κλειδί πίνακα

Ας δούμε πώς θα γίνει το μήνυμα που χρησιμοποιήσαμε στον αλγόριθμο του Καίσαρα με τον αλγόριθμο αυτό.

meet me at the park

Το κωδικοποιημένο μήνυμα θα είναι :

slly sl ky ybl tkwu

Αφού το m βρίσκεται στη 13η θέση του πίνακα letters θα αντικατασταθεί με το s που βρίσκεται στην 13η θέση του πίνακα key_arr. Ανάλογα θα αντικατασταθούν και τα υπόλοιπα γράμματα.

 

Αυτή είναι μια πολύ πιο ισχυρή μέθοδος από τη μέθοδο του Καίσαρα , καθώς ο κρυπταναλυτής θα πρέπει να δοκιμάσει πολλούς περισσότερους πίνακες ( περίπου 27! > 1028 ) για να είναι σίγουρος ότι θα διαβάσει το μήνυμα. Πάντως , αλγόριθμοι “απλής αντικατάστασης” ,όπως αυτός , είναι εύκολο να σπάσουν λόγω της συχνότητας εμφάνισης γραμμάτων της γλώσσας . Για παράδειγμα , αφού το Ε είναι το πιο συχνό γράμμα σε αγγλικά κείμενα , ο κρυπταναλυτής μπορεί να κάνει μια καλή αρχή στο να διαβάσει το μήνυμα με το να ψάχνει για το γράμμα που εμφανίζεται συχνότερα στο κωδικοποιημένο κείμενο και να το αντικαθιστέ με το Ε. Αν κι αυτή μπορεί να μην είναι η σωστή επιλογή ,είναι σαφώς καλύτερο από το να δοκιμάζεις και τα 26 γράμματα στην τύχη .

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

 

  1. Αλγόριθμος κρυπτογράφησης Vigenere

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

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.

Παράδειγμα για τον αλγόριθμο Vigenere

Ας δουμε πώς κωδικοποιείται το μήνυμα

meet me at the park

με τον αλγόριθμο Vigenere :

Α­¦ΒoΐΉhΆΒoΗΌ­aΎ°ΕΏ

 

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

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

 

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

 

Αποκρυπτογράφηση των Αλγορίθμων Κωδικοποίησης Δεδομένων

 

1. Αποκρυπτογράφηση του αλγορίθμου του Καίσαρα

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

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

Ας δούμε πώς θα αποκωδικοποιηθεί το μήνυμα

khoor wkhuh

που είχε κρυπτογραφηθεί με τον αλγόριθμο του Καίσαρα :

hello there

Έτσι ,το k μετατράπηκε σε h ,πήγαμε δηλαδή τρία γράμματα πίσω από το αρχικό γράμμα .Με τον ίδιο τρόπο , παίρνουμε το υπόλοιπο μήνυμα.

 

2. Αποκρυπτογράφηση του αλγορίθμου με κλειδί πίνακα

Για την αποκρυπτογράφηση μηνυμάτων που χρησιμοποίησαν ως κλειδί πίνακα , το μόνο που αλλάζει από τον αλγόριθμο κρυπτογράφησης είναι ότι η αναζήτηση του χαρακτήρα που διαβάσαμε γίνεται στον πίνακα κλειδί key_arr και αν βρεθεί στη θέση I του πίνακα αυτού ,αντικαθίσταται από το letters[I] για να πάρουμε το αποκωδικοποιημένο γράμμα .Επιπλέον ,αν ο χαρακτήρας είναι αριθμός τον αποκωδικοποιούμε αφαιρώντας 3.

 

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

Το κωδικοποιημένο μήνυμα είναι :

jmil sl 8 pcffkwd

και θα γίνει :

give me 5 dollars

Το j βρίσκεται στην έβδομη θέση του key_arr ,επομένως το αποκωδικοποιημένο γράμμα θα είναι το letters[7] ,που είναι το g.

Από το 8 που είναι αριθμός αφαιρούμε 3 και προκύπτει το 5 . Τα υπόλοιπα γράμματα προκύπτουν κατά ανάλογο τρόπο.

 

3. Αποκρυπτογράφηση του αλγορίθμου Vigenere

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

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

Το μήνυμα είναι το :

Η­¦nΘΒΙhΆΒo

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

see you at 6

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

 

Δραγανίδης Αθανάσιος 2/98