Σήμερα είδαμε μερικούς απλούς (και ανασφαλείς με τα σημερινά δεδομένα) τρόπους κρυπτογράφησης. Πώς να παίρνουμε δηλ. ένα κείμενο (cleartext) και να το μετατρέπουμε σε ένα άλλο κείμενο (ciphertext) που φαινομενικά δεν έχει καμία σχέση με το πρώτο με μια διαδικασία (κρυπτογράφηση) η οποία χρησιμοποιεί και μια κρυφή παράμετρο, το κλειδί (key, password), παράμετρος που αν μας είναι γνωστή μας επιτρέπει να αντιστρέψουμε την κρυπτογράφηση (αποκρυπτογράφηση) και από το κρυπτογραφημένο κείμενο (ciphertext) να πάρουμε πίσω το αρχικό κείμενο (cleartext). Είναι φανερό ότι αυτή η διαδικασία είναι πολύ χρήσιμη για όλου τους είδους τις επικοινωνίες ή και αποθηκεύσεις ευαίσθητων δεδομένων. Να ξεκαθαρίσουμε όμως ότι οι τεχνικές που θα δείξουμε σήμερα δεν είναι από αυτές που χρησιμοποιούνται πλέον γιατί είναι σχετικό εύκολο να υποκύψουν σε "επίθεση" με υπολογιστή.
Κάθε γράμμα αναπαρίσταται στον υπολογιστή από ένα αριθμό. Για να πάρουμε από ένα γράμμα τον αριθμό του χρησιμοποιούμε τη συνάρτηση ord().
x='a'
ord(x)
Για να πάρουμε από ένα αριθμό το γράμμα το οποίο του αντιστοιχεί χρησμοποιούμε την συνάρτηση chr().
chr(98)
Η αντιστοίχιση αυτή ονομάζεται κώδικας ASCII και μπορείτε να διαβάσετε λίγα πράγματα γι' αυτόν εδώ. Οι αριθμοί που χρησιμοποιούνται για τον κώδικα ASCII είναι οι 0 έως 127.
Παρακάτω τυπώνουμε τους χαρακτήρες που αντιστοιχούν στους αριθμούς 0-127 στη σειρά. Παρατηρείστε ότι κάποιοι δεν τυπώνονται (δεν είναι φτιαγμένοι για να τυπώνοονται, όπως π.χ. ο χαρακτήρας ESC).
for i in range(128):
print chr(i),
Στον κώδικα που ακολουθεί κρυπτογραφούμε το κείμενο που φαίνεται στη μεταβλητή clear με κωδικό (κλειδί) κρυπτογράφησης τον αριθμό 5. Στη μέθοδο αυτή κρυπτογράφησης το κλειδί είναι πάντα ένας αριθμός από 0 έως 127 (με τον αριθμό 0 να δίνει κρυπτογράφημα ίδιο με το αρχικό κείμενο, και άρα το κλειδί 0 δεν πρέπει να χρησιμοποιείται).
Η κρυπτογράφηση εδώ γίνεται γράμμα προς γράμμα. Παίρνουμε δηλ. το κάθε γράμμα του προς κρυπτογράφηση κειμένου και υπολογίζουμε το κρυπτογράφημά του, ανεξάρτητα από το ποια είναι τα άλλα γράμματα του κειμένου ή το σε ποια θέση του κειμένου είναι το γράμμα μας.
Αν το γράμμα μας έχει αριθμό \(x \in \{0, 1, 2, \ldots, 127\}\) και το κλειδί μας είναι ο αριθμός \(k \in \{0, 1, 2, \ldots, 127\}\) τότε το κρυπτογράφημα του γράμματός μας είναι το γράμμα που έχει ως αριθμό τον αριθμό \[ (x+k) \bmod 128. \] Όταν γράφουμε \(x \bmod a\) εννούμε το υπόλοιπο της διαίρεσης του ακεραίου \(x\) δια του θετικού ακεραίου \(a\) και αυτό είναι πάντα ένας ακέραιος από 0 έως \(a-1\). Το σύμβολο αυτό έχει την πολύ χρήσιμη ιδιότητα ότι αντιμετατίθεται με τις πράξεις \(+, -, \times\) (αλλά όχι με τη διαίρεση). Έχουμε δηλ. τις ιδιότητες \[ (x+y) \bmod a = ( (x \bmod a) + (y \bmod a) ) \bmod a, \] \[ (x-y) \bmod a = ( (x \bmod a) - (y \bmod a) ) \bmod a, \] \[ (x\times y) \bmod a = ( (x \bmod a) \times (y \bmod a) ) \bmod a. \] Για παράδειγμα η πρώτη από αυτές σημαίνει ότι αν θέλουμε να πάρουμε το υπόλοιπο διά \(a\) του αθροίσματος δύο αριθμών \(x, y\) τότε αρκεί να πάρουμε τα υπόλοιπα των δύο αυτών αριθμών διά \(a\), τα \(x \bmod a\) και \(y \bmod a\), να τα προσθέσουμε μεταξύ τους και τέλος να πάρουμε το υπόλοιπο διά \(a\) του αθροίσματός τους. Το ίδιο ισχύει και για τις άλλες δύο πράξεις \(-\) και \(\times\).
Οι ιδιότητες αυτές μπορούν να φαίνονται τετριμμένες (είναι πολύ εύκολο να τις αποδείξετε) αλλά είναι πάρα πολύ χρήσιμες γαιτί μας επιτρέπουν, σε κάποιες περιπτώσεις, όταν αναζητούμε πράξεις που το αποτέλεσμά τους είναι μικρό να έχουμε και όλα τα ενδιάμεσα αποτελέσματα μικρά. Π.χ. μπορούμε χρησιμοποιώντας τις ιδιότητες αυτές να δούμε ότι ο αριθμός \(51201^{152321}\) έχει τα δύο του τελευταία ψηφία (υπόλοιπο διά 100) ίσα με 01. Αυτό γιατί \[ 51201^{152321} \bmod 100 = (51201 \bmod 100)^{152321} \bmod 100 = 1^{152321} \bmod 100 = 1. \]
Μπορούμε να φανατστούμε την πρόσθεση mod 128 ως εξής: έχουμε τους αριθμούς 0 έως 127 διατεταγμένους πάνω σε ένα κύκλο με τη σειρά. Το να προσθέσουμε σε ένα από αυτούς τους αριθμούς τον αριθμό \(k \bmod 128\) σημαίνει ότι στρίβουμε τον κύκλο αυτό κατά \(k\) και το αποτέλεσμα της πρόσθεσης αυτής είναι η νέα θέση του αριθμού. Η πιο καλή αναλογία είναι με το πώς προσθέτουμε ώρες στο ρολόϊ, όπου η πρόσθεση γίνεται mod 24. Αν π.χ. τώρα η ώρα είναι 10 το βράδυ, δηλ. 22, τότε μετά από 5 ώρες η ώρα δε θα είναι 27 αλλά 27 mod 14 = 3.
Έτσι μετά την επιλογή του κλειδιού \(k\) η συνάρτηση κρυπτογράφησης ενός γράμματος (αριθμού δηλ. από 0 έως 127) είναι απλά η συνάρτηση \[ f: \{0,1,\ldots,127\} \to \{0,1,\ldots,127\} \] που δίδεται από τον τύπο \[ f(x) = x+k \bmod 128, \] συνάρτηση της οποίας η αντίστροφη (αποκρυπτογράφηση) είναι η \[ f^{-1}(x) = x-k \bmod 128. \]
Στον κώδικα που ακολουθεί υλοποιούμε αυτές τις δύο συναρτήσεις αλλά όχι από το σύνολο \(\{0,1,\ldots,127\}\) στον εαυτό του αλλά από το σύνολο όλων των γραμμάτων που αντιστοιχών σε αυτούς τους αριθμούς στον εαυτό τους. Γι' αυτό πρέπει να χρησιμοποιήσουμε τις συναρτήσεις chr και ord για να πάμε από αριθμό σε γράμμα και αντίστροφα.
Οι συναρτήσεις αυτές είναι γραμμένες παρακάτω (encrypt και decrypt) και παίρνουν η κάθε μία δύο παραμέτρους, το letter που είναι το γράμμα που θέλουμε να κρυπτογραφήσουμε/αποκρυπτογραφήσουμε και το key που είναι το κλειδί που χρησιμοποιείται. Οι δύο συναρτήσεις αυτές είναι πολύ απλές και κάνουν ακριβώς τις πράξεις που είπαμε παραπάνω.
Στην συνέχεια για να κρυπτογραφήσουμε τη λέξη clear σαρώνουμε τη λέξη με ένα for και για κάθε γράμμα της x βρίσκουμε το κρυπτογράφημά του με το y = encrypt(x, key) και το προσθέτουμε στο κρυπτογράφημα της λέξης.
Τυπώνουμε έπειτα την κρυπτογραφημένη λέξη και μετά ακολουθούμε την ίδια διαδικασία για να παράγουμε το αποκρυπτογραφημενο κείμενο στη μεταβλητή decr από το κρυπτογραφημένο κείμενο που βρίσκεται στη μεταβλητή enc. Το αποκρυπτογραφημένο κείμενο τυπώνεται κι αυτό και βλέπουμε ότι είναι ίδιο με το αρχικό.
clear = "Hello World!"
key = 5
def encrypt(letter, key):
"Κρυπτογραφεί ένα γράμμα letter με κλειδί key, έναν αριθμό από 0 έως 127"
return chr( (ord(letter)+key) % 128 )
def decrypt(encletter, key):
"Αποκρυπτογραφεί ένα γράμμα letter με κλειδί key, έναν αριθμό από 0 έως 127"
return chr( (ord(encletter)-key) % 128 )
enc = ""
for x in clear:
y = encrypt(x, key)
enc += y
print "The encrypted text is [{e}], with key={k}".format(e=enc, k=key)
decr = ""
for x in enc:
decr += decrypt(x, key)
print "The decrypted text is [{e}], with key={k}".format(e=decr, k=key)
Στο επόμενο εφαρμόζουμε τη μέθοδο κρυπτογράφησης που είδαμε στα περιεχόμενα ενός ολόκληρου αρχείου κειμένου (alice.txt, κατεβάστε το στον υπολογιστή σας αν θέλετε να τρέξετε αυτό το πρόγραμμα).
Γράφουμε κατ' αρχήν τις δύο νέες συναρτήσεις encstring και decstring οι οποίες καλούν τις δύο προηγούμενες συναρτήσεις encrypt και decrypt για να κρυπτογραφήσουν και αποκρυπτογραφήσουν ένα ολόκληρο string.
Αφού γράψουμε τις δύο αυτές συναρτήσεις ανοίγουμε το αρχείο alice.txt και διαβάζουμε όλες τις γραμμές του, τις κρυπτογραφούμε και τις γράφουμε στο αρχείο encalice.txt. (Αν προσπαθήσετε να δείτε το αρχείο αυτό θα παρατηρήσετε ότι δε φαίνεται πια να έχει καν τη μορφή αρχείου κειμένου, π.χ. δε φαίνεται να έχει γραμμές που αλλάζουν. Αυτό είναι συνέπεια ότι οι χαρακτήρες αλλαγής γραμμής έχουν κι αυτοί αλλάξει με την κρυπτογράφηση.)
Μετά από αυτό ανοίγουμε το αρχείο encalice.txt, διαβάζουμε όλες τις γραμμές του, τις αποκρυπτογραφούμε με το ίδιο κλειδί και τέλος τις γράφουμε στο αρχείο newalice.txt το οποίο είναι ακριβώς το ίδιο με το αρχείο alice.txt από το οποίο ξεκινήσαμε.
key = 5
def encrypt(letter, key):
"Κρυπτογραφεί ένα γράμμα letter με κλειδί key, έναν αριθμό από 0 έως 127"
return chr( (ord(letter)+key) % 128 )
def encstring(s, key):
"Κρυπτογραφεί ένα string s με κλειδί key, έναν αριθμό από 0 έως 127"
t=""
for x in s:
t += encrypt(x, key)
return t
def decrypt(encletter, key):
"Αποκρυπτογραφεί ένα γράμμα letter με κλειδί key, έναν αριθμό από 0 έως 127"
return chr( (ord(encletter)-key) % 128 )
def decstring(s, key):
"Αποκρυπτογραφεί ένα string s με κλειδί key, έναν αριθμό από 0 έως 127"
t=""
for x in s:
t += decrypt(x, key)
return t
# Διαβάζουμε το αρχείο alice.txt
f = open("alice.txt", "r")
lines = f.readlines()
f.close()
# Κρυπτογραφούμε τις γραμμές που διαβάσαμε και τις γράφουμε στο αρχείο encalice.txt
f = open("encalice.txt", "w")
for l in lines:
f.write(encstring(l, key))
f.close()
# Ανοίγουμε ξανά το αρχείο encalice.txt και διαβάζουμε τις γραμμές του
f = open("encalice.txt", "r")
lines = f.readlines()
f.close()
# Αποκρυπτογραφούμε τις γραμμές που διαβάσαμε και τις γράφουμε στο αρχείο newalice.txt
f = open("newalice.txt", "w")
for l in lines:
f.write( decstring(l, key))
f.close()
Ένα μεγάλο μειονέκτημα της προηγούμενης μεθόδου είναι το κρυπτογράφημα ενός γράμματος είναι το ίδιο σε κάθε εμφάνιση του αρχικού γράμματος στο προς κρυπτογράφηση έγγραφο. Αυτό έχει δυο σοβαρές συνέπειες. Πρώτον, είναι εύκολο να βρει κάποιος, ειδικά σε ένα μεγάλο έγγραφο που έχει κρυπτογραφηθεί, το ποιο είναι το κρυπτογράφημα ενός πολύ συχνού γράμματος. Στην Αγγλική γλώσσα για παράδειγμα το γράμμα e είναι κατά πολύ το πιο συχνό γράμμα στα κείμενα, άρα το ίδιο θα ισχύει και για το κρυπτογράφημά του το οποίο εύκολα μπορεί έτσι να βρεθεί. Και δέυτερον, αν κάποιο βρεί ένα ζεύγος γράμματος-κρυπτογραφήματος τότε έχει αυτόματα βρει την τιμή του κλειδιού και άρα μπορεί να "ξεκλειδώσει" ολόκληρο το έγγραφο.
Μια λύση σε αυτό το πρόβλημα είναι σε κάθε βήμα να χρησιμοποιούμε άλλα κλειδί. Όμως θα πρέπει να μην είμαστε αναγκασμένοι να θυμόμαστε και από ένα αλλο κλειδί για κάθε γράμμα του αρχικού μας κειμένου, γιατί αυτό είναι αδύνατο. Θα πρέπει λοιπόν το κλειδί που χρησιμοποιούμε τη χρονική στιγμή \(t\) να είναι δυνατό να υπολογιστεί από το αρχικό μας κλειδί \(k\) και το \(t\). Μια δυνατότητα γι' αυτό είναι τη χρονική στιγμή \(t\) να χρησιμοποιούμε το κλειδί \(t\cdot k \bmod 128\) (μια άλλη λύση θα ήταν π.χ. να χρησιμοποιούμε το κλειδί \(k+t \bmod 128\)).
Τώρα λοιπόν η συνάρτηση κρυπτογράφησης (encrypt) και η συνάρτηση αποκρυπτογράφησης (decrypt) παίρνουν και μια επιπλέον παράμετρο πέρα από το γράμμα και το κλειδί, το χρόνο time.
Όταν καλούμε αυτές τις δύο συναρτήσεις τις καλούμε πάντα με ένα διαρκώς αυξανόμενο t, π.χ.
enc = ""
t = 1
for x in clear:
enc += encrypt(x, key, t)
t += 1Παρατηρείστε ότι τώρα το κρυπτογραφημένο κείμενο είναι μικρότερο από το αρχικό κείμενο "Hello World!". Αυτό μοιάζει περίεργο γιατί η κρυπτογράφηση με αυτή τη μέθοδο είναι μια διαδικασία που για κάθε γράμμα του αρχικού κειμένου μας δίνει ένα γράμμα του κρυπτογραφημένου κειμένου. Και δεν είναι παρά μία οφθαλμαπάτη γιατί απλά κάποιοι από τους 128 χαρακτήρες που είναι δυνατό να εμφανιστούν ως κρυπτογραφήματα πολύ απλά όταν τυπώνονται με τη συνάρτηση print δεν εμφανίζουν τίποτα στην οθόνη.
clear = "Hello World!"
key = 5
def encrypt(letter, key, time):
return chr( (ord(letter)+time*key) % 128 )
def decrypt(encletter, key, time):
return chr( (ord(encletter)-time*key) % 128 )
enc = ""
t = 1
for x in clear:
enc += encrypt(x, key, t)
t += 1
print "The encrypted text is [{e}], with key={k}".format(e=enc, k=key)
t = 1
decr = ""
for x in enc:
decr += decrypt(x, key, t)
t += 1
print "The decrypted text is [{e}], with key={k}".format(e=decr, k=key)
Ένα άλλο μειονέκτημα των δύο προηγούμενων μεθόδων κρυπτογράφησης που είδαμε είναι ότι το σύνολο των δυνατών κλειδιών που υπάρχουν είναι πολύ μικρός, μόλις 128 διαφορετικά κλειδιά υπάρχουν, και άρα μπορεί πολύ εύκολα να βρεθεί το κλειδί κοιτώντας και δοκιμάζοντας όλα τα δυνατά κλειδιά.
Ένας τρόπος να έχουμε πολλά δυνατά κλειδιά είναι τα κλειδιά αυτά να είναι λέξεις. Υπάρχουν πάρα πολλές λέξεις με μήκος, π.χ. 10. Αν υποθέσουμε ότι σε κάθε θέση της λέξης μπορεί να μπει οποιοδήποτε γράμμα του λατινικού αλφαβήτου (μικρό ή κεφαλαίο) και οποιοδήποτε ψηφίο τότε υπάρχουν \((26+26+10)^{10}=839299365868340224\) διαφορετικά κλειδιά μήκους 10.
Στον επόμενο αλγόριθμο κρυπτογράφησης έχουμε ένα κλειδί λέξη (key = "Mihalis9-2015") και θέλουμε να κρυπτογραφήσουμε το μήνυμα
clear = "Hello World!Hello World!Hello World!Hello World!Hello World! "Θα χρησιμοποιήσουμε το κλειδί αυτό για να έχουμε ένα μεταβαλλόμενο κλειδί κρυπτογράφησης για κάθε γράμμα του προς κρυπτογράφηση κειμένου.
Κατ' αρχήν φανταζόμαστε ότι το κλειδί μας έχει το ίδιο μήκος με το κείμενό μας. Στην πραγματικότητα δεν έχει βέβαια αλλά φανταζόμαστε ότι το κλειδί μας επαναλαμβάνεται διαρκώς μέχρι του μήκους του κειμένου:
clear = "Hello World!Hello World!Hello World!Hello World!Hello World! "
key = "Mihalis9-2015Mihalis9-2015Mihalis9-2015Mihalis9-2015Mihalis9-"Δε χρειάζεται να δημιουργήσουμε και να κρατήσουμε στη μνήμη αυτό το νέο κλειδί αλλά απλά κάνουμε την παρατήρηση ότι το \(i\)-οστό γράμμα (το \(i\) αρχίζει να μετράει από το 0 ως συνήθως) του επεκτεταμένου αυτού κλειδιού είναι το γράμμα του αρχικού μας κλειδιού με δείκτη \(i \bmod L\), όπου \(L\) το μήκος του κλειδιού μας.
Το επόμενο βήμα είναι ότι αποφασίζουμε ότι το κλειδί κρυπτογράφησης του \(i\)-οστού γράμματος του κειμένου μας θα είναι το \(i\)-οστό γράμμα του (επεκτεταμένου) κλειδιού μας. Έτσι, για να κρυπτογραφήσουμε ένα γράμμα που βρίσκεται στην \(i\)-οστή θέση του κειμένου παίρνουμε τον αριθμό του (με τη συνάρτηση ord), παίρνουμε τον αριθμό του \(i\)-οστού γράμματος του επεκτεταμένου κλειδιού (πάλι με τη συνάρτηση ord) και τα προσθέτουμε mod 128. Τέλος βρίσκουμε (με τη συνάρτηση chr) το γράμμα που αντιστοιχεί σε αυτό τον αριθμό. Έτσι η νέα μας συνάρτηση κρυπτογράφησης γίνεται:
def encrypt(letter, key, index):
return chr( (ord(letter) + ord(key[index % len(key)])) % 128 )και η συνάρτηση αποκρυπτογράφησης είναι τελείως αντίστοιχη.
Κατά τα άλλα η διαδικασία κρυπτογράφησης/αποκρυπτογράφησης είναι ακριβώς όπως και πριν. Παρατηρείστε ότι και πάλι το μήκος του κρυπτογραφημένου κειμένου δείχνει να είναι μικρότερο από το μήκος του αρχικού κειμένου, αλλά και πάλι αυτό οφείλεται στο ότι κάποιοι από τους χαρακτήρες που υπάρχουν στο κρυπτογραφημένο αλλά όχι στο αρχικό δεν τυπώνονται.
clear = "Hello World!Hello World!Hello World!Hello World!Hello World! "
key = "Mihalis9-2015"
def encrypt(letter, key, index):
return chr( (ord(letter) + ord(key[index % len(key)])) % 128 )
def decrypt(encletter, key, index):
return chr( (ord(encletter) - ord(key[index % len(key)])) % 128 )
enc = ""
i=0
for x in clear:
enc += encrypt(x, key, i)
i += 1
print "The encrypted text is [{e}], with key={k}".format(e=enc, k=key)
decr = ""
i=0
for x in enc:
decr += decrypt(x, key, i)
i += 1
print "The decrypted text is [{e}], with key={k}".format(e=decr, k=key)