Κλασικές τεχνικές κρυπτογράφησης

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

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

Λεξιλόγιο

Για να συνεννοούμαστε, ας ξεκαθαρίσουμε μερικούς όρους:

• plaintext: Αυτό που θέλουμε να κρυπτογραφήσουμε
• ciphertext: Η κρυπτογραφημένη έξοδος
• κρυπτογράφηση / encryption: Η διαδικασία μέσω της οποίας το plaintext μετατρέπεται στο ciphertext
• αποκρυπτογράφηση / decryption: Η διαδικασία μέσω της οποίας το ciphertext μετατρέπεται ξανά στο plaintext
• αλγόριθμος κρυπτογράφησης: Η σειρά των βημάτων επεξεργασίας των δεδομένων που μετατρέπουν το plaintext στο ciphertext. Διάφορες παράμετροι που χρησιμοποιούνται από έναν αλγόριθμο κρυπτογράφησης προκύπτουν από ένα μυστικό κλειδί.
• αλγόριθμος αποκρυπτογράφησης: Η σειρά των βημάτων επεξεργασίας των δεδομένων που μετατρέπουν το ciphertext στο plaintext. Συχνά, όταν μιλάμε για αλγόριθμο κρυπτογράφησης, αναφερόμαστε στην πραγματικότητα στο ζεύγος αλγορίθμων κρυπτογράφησης/αποκρυπτογράφησης.
• μυστικό κλειδί/secret key: Το μυστικό κλειδί χρησιμοποιείται για να ορίσει κάποιες ή όλες τις παραμέτρους του αλγόριθμου (απο)κρυπτογράφησης. Σημαντική διάκριση που πρέπει να γίνει εδώ είναι η εξής:
  • Στην κλασική κρυπτογραφία χρησιμοποιείται το ίδιο μυστικό κλειδί τόσο για την κρυπτογράφηση όσο και για την αποκρυπτογράφηση. Για το λόγο αυτό, η κλασική κρυπτογραφία είναι γνωστή και ως συμμετρική κρυπτογραφία ή κρυπτογραφία συμμετρικού κλειδιού.
  • Σε ποιο μοντέρνους κρυπτογραφικούς αλγόριθμους, το κλειδί της κρυπτογράφησης και αυτό της αποκρυπτογράφησης δεν είναι απλά διαφορετικά, άλλα το ένα μάλιστα δεν κρατείται κρυφό αλλά δημοσιεύεται. Τέτοιο αλγόριθμοι εντάσσονται στη κρυπτογραφία δημόσιου κλειδιού.
• key space: Ο συνολικός αριθμός όλων των πιθανών κλειδιών που μπορούν να χρησιμοποιηθούν. Για παράδειγμα, ο αλγόριθμος DES χρησιμοποιεί κλειδί μήκους 56 bit. Επομένως το πλήθος των πιθανών κλειδιών και άρα και το key space του DES είναι 2⁵⁶ που ισούται περίπου με 7,2 * 10¹⁶.

Θεμέλιοι λίθοι των κλασικών τεχνικών κρυπτογράφησης

Οι δύο θεμέλιοι λίθοι των κλασικών τεχνικών κρυπτογράφησης είναι η αντικατάσταση / substitution και η μετατόπιση / αντιμετάθεση / transposition / permutation.

• Η αντικατάσταση αναφέρεται στην αντικατάσταση ενός χαρακτήρα του plaintext από έναν χαρακτήρα του ciphertext.
• H αντιμετάθεση αναφέρεται στη μετατόπιση των χαρακτήρων του plaintext.

Ο αλγόριθμος του Καίσαρα

Ο αλγόριθμος του Καίσαρα αποτελεί ένα από τα παλαιότερα γνωστά παραδείγματα κρυπτογραφικού αλγόριθμου αντικατάστασης. Η μέθοδος έχει πάρει το όνομά της από τον Ιούλιο Καίσαρα, ο οποίος τη χρησιμοποιούσε για την προσωπική του επικοινωνία.

Κάθε χαρακτήρας του plaintext αντικαθίσταται από ένα χαρακτήρα 3 θέσεις πιο κάτω στο αλφάβητο.

 plaintext:   are you ready
 ciphertext:  duh brx uhdgb

Αν αντιστοιχίσουμε σε κάθε γράμμα του αλφαβήτου έναν ακέραιο που αντιπροσωπεύει τη θέση του γράμματος στο αλφάβητο, η φόρμουλα για αντικαταστήσουμε ένα χαρακτήρα p του plaintext με ένα χαρακτήρα c του ciphertext μπορεί να εκφραστεί ως:

 c = E(3,p) = (p+3) mod 26

όπου το E() αντιπροσωπεύει την κρυπτογράφηση. Ο τελεστής mod επιστρέφει το υπόλοιπο της ακέραιας διαίρεσης του (p+3) με το 26, το πλήθος δηλαδή των γραμμάτων του αλφάβητου. Για να δουλέψει αυτή η εξίσωση πρέπει γίνει αυτή η διαίρεση με το 26 και να κρατιέται το υπόλοιπο, ούτως ώστε η αρίθμηση του αλφάβητου να γίνεται κυκλική, δηλαδή οι χαρακτήρες x, y, z, να κρυπτογραφούνται στους a, b, c αντίστοιχα. Σε αυτό το παράδειγμα δεν κάνουμε διάκριση ανάμεσα σε κεφαλαίους και πεζούς χαρακτήρες.

Μία πιο γενική μορφή αυτού του αλγόριθμου που θα επέτρεπε μεταβλητό βαθμό μετατόπισης των χαρακτήρων θα εκφραζόταν από τη σχέση:

 c = E(k,p) = (p+k) mod 26

H αποκρυπτογράφηση θα εκφραζόταν από τη σχέση:

 p = D(k,c) = (c-k) mod 26

Στις παραπάνω σχέσεις το k είναι το μυστικό κλειδί (προηγουμένως είχαμε τιμή 3).

Ο αλγόριθμος αυτός είναι πάρα πολύ ευάλωτος απέναντι σε πλήθος επιθέσεων αλλά πριν από αυτές, μπορεί να ηττηθεί από την πιο απλή. Θα μπορούσε να δοκιμάσει κανείς να αποκρυπτογραφήσει ένα κρυπτογραφημένο κείμενο με κάθε δυνατό κλειδί, δηλαδή με κάθε δυνατή μετατόπιση που, στην περίπτωση του παραπάνω παραδείγματος, είναι 26 στο πλήθος. Οι πιθανότητες είναι πως στις 25 απόπειρες θα επιστραφεί ένα plaintext που δε βγάζει νόημα, αλλά σε μία από τις δοκιμές θα βρει το σωστό plaintext, κι όλο αυτό σε πολύ σύντομο χρονικό διάστημα.

Μονοαλφαβητικοί αλγόριθμοι κρυπτογράφησης

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

 χαρακτήρες plaintext:             a  b  c  d  e  f  .......
 χαρακτήρες αντικατάστασης:        t  h  i  j  a  b  .......

Άρα ο χαρακτήρας a του plaintext θα αντικατασταθεί από το χαρακτήρα t στο ciphertext, ο b από τον h, ο c από τον i, κοκ.

Στην περίπτωση αυτή, το κλειδί είναι αυτή η ακολουθία των χαρακτήρων αντικατάστασης, αυτός ο τυχαίος συνδυασμός των γραμμάτων του αλφάβητου. Επομένως με κλειδί "thijab.....", το plaintext "acab" θα κρυπτογραφούταν στο ciphertext "tith".

Το πλήθος των διαφορετικών συνδυασμών ή ανακατατάξεων (permutations) των 26 γραμμάτων του αλφάβητου ισούται με 26!. Με άλλα λόγια, υπάρχουν περισσότερες από 4*10²⁶ διαφορετικές ανακατατάξεις των χαρακτήρων του αλφάβητου.

Σημείωση: Το ν! (όπου ν είναι ακέραιος) διαβάζεται "ν παραγοντικό" και ισούται με το γινόμενο όλων των αριθμών από το 1 μέχρι το ν. Δηλαδή 26! = 1*2*3*4*...*24*25*26.

Καθώς κάθε ανακατάταξη αποτελεί και ένα κλειδί, αυτός ο αλγόριθμος έχει key space μεγαλύτερο από 4*10²⁶.

Θα περίμενε ίσως κανείς πως ένα τόσο μεγάλο key space θα καθιστούσε αυτό τον αλγόριθμο κρυπτογράφησης πολύ δύσκολο να σπαστεί. Όντως, το πολύ μεγάλο key space αυτού του αλγόριθμου σημαίνει πως ο συνολικός αριθμός των πιθανών κλειδιών που θα έπρεπε να δοκιμαστούν σε μία καθαρή brute-force επίθεση είναι τόσο μεγάλος, που καθιστούν μία τέτοια επίθεση πρακτικά ανέφικτη. Ακόμα κι αν απαιτούταν μονάχα ένα nanosecond (δισεκατομμυριοστό του δευτερολέπτου) για να δοκιμαστεί ένα πιθανό κλειδί, ή ισοδύναμα ακόμα κι αν δοκιμάζονταν ένα δισεκατομμύριο κλειδιά ανά δευτερόλεπτο, θα χρειαζόντουσαν λίγο λιγότερο από 13 δισεκατομμύρια χρόνια για να δοκιμαστούν όλα τα πιθανά κλειδιά. Άρα αποκλείεται μία brute-force επίθεση.

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

Στατιστική επίθεση

Αν κανείς γνωρίζει τη φύση του plaintext, κάθε κρυπτογραφικός αλγόριθμος αντικατάστασης, ανεξαρτήτως του key space, μπορεί πολύ εύκολα να σπαστεί μέσω μίας στατιστικής επίθεσης.

Αν, για παράδειγμα, το plaintext είναι κείμενο γραμμένο στην αγγλική γλώσσα, μία απλή μορφή στατιστικής επίθεσης θα συνίστατο από τον υπολογισμό της κατανομής συχνότητας για μονούς χαρακτήρες, ζεύγη και τριάδες χαρακτήρων στο ciphertext και σύγκριση αυτών με αντίστοιχα στατιστικά της αγγλικής γλώσσας.

Να εξηγήσουμε λίγο το παραπάνω. Ένα plaintext συνήθως δεν είναι μία τυχαία ακολουθία χαρακτήρων χωρίς νόημα. Το plaintext είναι μία πληροφορία, είτε αυτή είναι εκφρασμένη ως γραπτό σε κάποια γλώσσα, είτε είναι ένα αρχείο εικόνας, ήχου ή οτιδήποτε άλλο. Αυτή η πληροφορία στο plaintext έχει κάποια συγκεκριμένη δομή.

Για χάριν απλότητας, ας θεωρήσουμε την περίπτωση όπου το plaintext είναι αγγλικό κείμενο, όπως έχουμε κάνει και στα προηγούμενα παραδείγματα. Ένα κείμενο γραμμένο στην αγγλική γλώσσα δεν αποτελείται από μία τυχαία ακολουθία χαρακτήρων. Η αγγλική γλώσσα έχει μία δομή μέσα από την οποία προκύπτουν κάποια στατιστικά. Για παράδειγμα, σε ένα μέσο αγγλικό κείμενο, ο χαρακτήρας e εμφανίζεται με σχετική συχνότητα 12,7%, ο t με 9,06%, ο a με 8,17%, ενώ ο q με 0,095% και ο z με 0.074%. Αντίστοιχα, σχετικές συχνότητες εμφάνισης μπορούν να υπολογιστούν για ζεύγη ή τριάδες διαδοχικών χαρακτήρων της αγγλικής γλώσσας.

Ας θυμηθούμε τώρα τον μονοαλφαβητικό κρυπτογραφικό αλγόριθμο που είδαμε στην προηγούμενη ενότητα. Είδαμε πως αυτός ο αλγόριθμος δουλεύει αντικαθιστώντας κάθε χαρακτήρα του plaintext με κάποιον τυχαίο χαρακτήρα στο plaintext. Εξηγήσαμε επίσης πως το key space του αλγόριθμου αυτού είναι τόσο μεγάλο που καθιστά ανέφικτη μία brute-force επίθεση. Όμως, οι αντικαταστάσεις που κάνει αυτός ο αλγόριθμος, παρ'ότι αλλάζουν όλους τους χαρακτήρες, δεν αλλάζουν τη δομή αυτών στο ciphertext.

Αν δηλαδή κάποιος γνωρίζει τη φύση του plaintext (αγγλικό κείμενο) και υπολογίσει τη συχνότητα με την οποία εμφανίζεται κάθε χαρακτήρας (και ζεύγη ή τριάδες) στο ciphertext, μπορεί να συγκρίνει με τα αντίστοιχα στατιστικά της αγγλικής γλώσσας και να συμπεράνει με ποιον τρόπο τα γράμματα του plaintext αντιστοιχίζονται σε αυτά του ciphertext και άρα πολύ εύκολα να σπάσει τον αλγόριθμο.

Ο αλγόριθμος κρυπτογράφησης Playfair

Όπως είδαμε παραπάνω, με αντικατάσταση ενός γράμματος τη φορά, κρίσιμη πληροφορία για τη δομή του plaintext διαρρέει στο ciphertext και αυτό μπορεί να χρησιμοποιηθεί από μία στατιστική επίθεση. Η λογική του Playfair είναι να αντικαθιστά περισσότερα γράμματα τη φορά με σκοπό να καταστρέψει τη δομή αυτή.

Στον αλγόριθμο Playfair, πρώτα επιλέγουμε ένα κλειδί. Στη συνέχεια εισάγουμε τους χαρακτήρες του κλειδιού αυτού σε έναν πίνακα 5x5 ξεκινώντας από το πάνω αριστερό κελί. Στη συνέχεια γεμίζουμε τα υπόλοιπα κελιά με τα υπόλοιπα γράμματα του αλφάβητου (που δεν περιέχονται στο κλειδί) με αλφαβητική σειρά. Οι χαρακτήρες i και j μπαίνουν στο ίδιο κελί. Έστω για παράδειγμα ότι το κλειδί μας είναι το "smythework". Ο πίνακας που προκύπτει είναι ο εξής:

S	M	Y	T	H
E	W	O	R	K
A	B	C	D	F
G	I/J	L	N	P
Q	U	V	X	Z

Η αντικατάσταση χαρακτήρων του plaintext στο ciphertext γίνεται εδώ ανά ζεύγη χαρακτήρων. Οι κανόνες αντικατάστασης είναι εξής:

1. Αν δύο χαρακτήρες του plaintext ανήκουν στην ίδια σειρά του πίνακα, αντικαθιστώνται από τα γράμματα που βρίσκονται στα δεξιά τους στην ίδια σειρά (στα δεξιά του τελευταίου χαρακτήρα μίας σειράς θεωρούμε ότι βρίσκεται ο πρώτος χαρακτήρας της ίδιας σειράς. Για παράδειγμα το ζεύγος χαρακτήρων "bf" του plaintext θα αντικατασταθεί από το ζεύγος "ca" στο ciphertext.
2. Αν δύο χαρακτήρες του plaintext ανήκουν στην ίδια στήλη του πίνακα, αντικαθιστώνται από τα γράμματα που βρίσκονται από κάτω τους στην ίδια στήλη (κάτω από τον τελευταίο χαρακτήρα μίας στήλης θεωρούμε ότι βρίσκεται ο πρώτος χαρακτήρας της ίδιας στήλης. Για παράδειγμα το ζεύγος χαρακτήρων "ol" του plaintext θα αντικατασταθεί από το ζεύγος "cv" στο ciphertext.
3. Αν οι δύο χαρακτήρες δε βρίσκονται σε κοινή σειρά ή στήλη, τότε ο κάθε χαρακτήρας αντικαθίσταται από αυτόν που βρίσκεται στην ίδια σειρά αλλά και στην ίδια στήλη με τον άλλο χαρακτήρα. Θεωρούμε για παράδειγμα το ζεύγος χαρακτήρων "gf" του plaintext. Το "g" βρίσκεται στην τέταρτη σειρά και πρώτη στήλη, το "f" στην τρίτη σειρά και πέμπτη στήλη. Άρα αντικαθιστούμε το "g" με τον χαρακτήρα που βρίσκεται στην ίδια σειρά με το "g" και ίδια στήλη με το "f", δηλαδή με το "p". Αντίστοιχα, αντικαθιστούμε το "f" με τον χαρακτήρα που βρίσκεται στην ίδια σειρά με το "f" και ίδια στήλη με το "g", δηλαδή με το "a". Άρα το ζεύγος "gf" του plaintext αντικαθίσταται από το ζεύγος "pa" στο ciphertext.

Για να δουλέψει ο αλγόριθμος, το κλειδί δεν πρέπει να περιέχει τον ίδιο χαρακτήρα δύο φορές. Επίσης, δεν πρέπει στο plaintext να υπάρχουν δύο ίδιοι διαδοχικοί χαρακτήρες. Αν υπάρχουν, πρέπει είτε ο ένας να διαγραφεί, είτε να εισαχθεί ένας άλλος χαρακτήρας ανάμεσα στους δύο όμοιους.

Ο κρυπτογραφικός αλγόριθμος Playfair χρησιμοποιούταν από τον βρετανικό στρατό κατά τη διάρκεια του 1ου Π.Π. και από τις Η.Π.Α. και τις συμμαχικές δυνάμεις στο 2ο Π.Π. και για πολλές δεκαετίες θεωρούταν άσπαστος. Αποδείχτηκε ωστόσο πως και αυτός ο αλγόριθμος μπορεί εύκολα να σπάσει. Όπως θα περιμέναμε, ο αλγόριθμος αλλάζει μεν τις συχνότητες εμφάνισης μεμονωμένων χαρακτήρων (και ζευγών και τριάδων), αλλά δυστυχώς όχι επαρκώς. Παραμένει σημαντική πληροφορία σχετικά με τη δομή στο ciphertext που σε συνδυασμό με μία στατιστική επίθεση, καθιστά αρκετά εύκολο να μαντέψει κανείς το κλειδί. Επιπλέον, την κρυπτανάλυση του playfair βοηθά το γεγονός πως ένα ζεύγος γραμμάτων και το αντίστροφό του θα κρυπτογραφηθούν με αντίστοιχο τρόπο (αν το AB->XY, τότε το BA->YX).

Πολυαλφαβητικοί αλγόριθμοι κρυπτογράφησης: Ο αλγόριθμος Vigenere

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

Στον κρυπτογραφικό αλγόριθμο Vigenere πρέπει αρχικά να "ευθυγραμμίσουμε" το κλειδί με το plaintext. Αν το κλειδί είναι πιο μικρό από το plaintext, επαναλαμβάνουμε το κλειδί για να έχουν ίδιο μήκος. Τώρα θεωρούμε ότι κάθε χαρακτήρας του κλειδιού κρυπτογράφησης αντιπροσωπεύει έναν αλγόριθμο μετατόπισης (αλγόριθμος του Καίσαρα), όπου η μετατόπιση καθορίζεται από το χαρακτήρα του κλειδιού. Αυτό γίνεται ευκολότερα κατανοητό με τη βοήθεια του παρακάτω πίνακα.

χαρακτήρας κλειδιού	χαρακτήρες plaintext
	a	b	c	d	...........
	χαρακτήρες αντικατάστασης
a	A	B	C	D	...........
b	B	C	D	E	...........
c	C	D	E	F	...........
d	D	E	F	G	...........
e	E	F	G	H	...........
.	.	.	.	.	...........
.	.	.	.	.	...........
z	Z	A	B	C	...........

Ας υποθέσουμε τώρα ότι θέλουμε να κρυπτογραφήσουμε το μήνυμα "can you meet me at midnight i have the goods" χρησιμοποιώντας το κλειδί "abracadabra":

 key:           abracadabraabracadabraabracadabraab
 plaintext:     canyoumeetmeatmidnightihavethegoods
 ciphertext:    CBEYQUPEFKMEBK.....................

Η μετατόπιση που υφίσταται ο κάθε χαρακτήρας του plaintext εξαρτάται από τον αντίστοιχο χαρακτήρα του κλειδιού, όπως φαίνεται στον προηγούμενο πίνακα.

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

Πηγές

Το άρθρο αυτό βασίζεται σε μεγάλο βαθμό στο κείμενο Classical Encryption Techniques [1]