Το Πρότυπο Κρυπτογράφησης AES

Εισαγωγικά

Το πρότυπο κρυπτογράφησης AES (Advanced Encryption Standard) περιγράφει μια διαδικασία κρυπτογράφησης ηλεκτρονικής πληροφορίας βασισμένη στην λογική της κωδικοποίησης ομάδων δεδομένων με κάποιο μυστικό κλειδί. Έχει προτυποποιηθεί από το NIST (National Institute of Technology) τον Νοέμβριο του 2001, αντικαθιστώντας το πρότυπο DES (Data Encryption Standard) και πλέον αποτελεί τον προτεινόμενο αλγόριθμο για εφαρμογές κρυπτογράφησης.

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

Προαπαιτούμενα

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

1. Μια εισαγωγή στην κρυπτογράφηση μυστικού κλειδιού

Η κρυπτογράφηση μυστικού κλειδιού (secret key cryptography) βασίζεται στην χρήση μιας μυστικής πληροφορίας που ονομάζεται κλειδί για την κρυπτογράφηση και αποκρυπτογράφηση δεδομένων. Αν κάποιος θέλει να αποστείλει σε έναν τρίτο ένα κωδικοποιημένο μήνυμα, τότε χρησιμοποιεί το μυστικό κλειδί για να κρυπτογραφήσει την πληροφορία (στην ορολογία της κρυπτογραφίας η μη κρυπτογραφημένη πληροφορία αναφέρεται ως plaintext). To αποτέλεσμα της κρυπτογράφησης είναι να προκύψει μια κωδικοποιημένη πληροφορία (που ονομάζεται ciphertext) και η οποία αποστέλεται. Για να μπορέσει κάποιος να ανακτήσει την αρχική πληροφορία, θα πρέπει να γνωρίζει το ίδιο μυστικό κλειδί που χρησιμοποιήθηκε για την κωδικοποίηση της. Επειδή το ίδιο ακριβώς κλειδί χρησιμοποιείται τόσο για την κρυπτογράφηση όσο και αποκρυπτογράφηση των δεδομένων, η διαδικασία κρυπτογράφησης μυστικού κλειδιού ονομάζεται και συμμετρική κρυπτογράφηση (symmetric cipher).

Σχήμα 1. Στην κρυπτογράφηση μυστικού κλειδιού, το ίδιο κλειδί χρησιμοποιείται και για την κρυπτογράφηση και για την αποκρυπτογράφηση των δεδομένων.

Οι τρόποι κρυπτογράφησης μυστικού κλειδιού τυπικά χωρίζονται σε 2 κατηγορίες. Η πρώτη περιλαμβάνει διαδικασίες κρυπτογράφησης που εφαρμόζονται πάνω σε ένα μοναδικό bit (ή byte ή word) και υλοποιούν κάποιο μηχανισμό ανατροφοδότησης έτσι ώστε το κλειδί να αλλάζει συνεχώς. Για αυτό και ονομάζονται κρυπτογράφοι ροής (stream ciphers). Η δεύτερη κατηγορία (κρυπτογράφοι μπλοκ - block ciphers) αποτελείται από αλγορίθμους κρυπτογράφησης που λειτουργούν πάνω σε ομάδες δεδομένων κάθε χρονική στιγμή χρησιμοποιώντας το ίδιο κλειδί για κάθε ομάδα. Έτσι στην γενική περίπτωση, όταν το ίδιο μυστικό κλειδί χρησιμοποιείται, η ίδια ομάδα δεδομένων ενός plaintext θα κρυπτογραφηθεί στο ίδιο ciphertext όταν η κρυπτογράφηση γίνεται με έναν αλγόριθμο κρυπτογράφησης μπλοκ αλλά σε διαφορετικό ciphertext όταν χρησιμοποιηθεί ένας κρυπτογράφος ροής.

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

Electronic Codebook (ECB)
Αυτός ο τρόπος λειτουργίας είναι ο απλούστερος και ο πλέον προφανής. Το μυστικό κλειδί χρησιμοποιείται για την κρυπτογράφηση κάθε μπλοκ δεδομένων του plaintext. Κατά συνέπεια με την χρήση του ίδιου κλειδιού, το ίδιο plaintext μπλοκ θα μετατρέπεται πάντα στο ίδιο ciphertext μπλοκ. Είναι ο πλέον κοινός τρόπος λειτουργίας των κρυπτογράφων μπλοκ γιατί είναι ο απλούστερος και άρα ο πιο εύκολα υλοποιήσιμος και συνάμα ο πιο γρήγορος καθώς δεν χρησιμοποιείται κάποιου είδους ανατροφοδότηση. Μειονέκτημα του είναι ότι είναι ο πιο ευάλωτος τρόπος κρυπτογράφησης σε επιθέσεις τύπου brute-force (ως επίθεση brute-force θεωρείται η προσπάθεια εύρεσης του μυστικού κλειδιού με την εξαντλητική δοκιμή πιθανών κλειδιών).

Cipher Block Chaining (CBC)
Χρησιμοποιώντας την CBC λειτουργία, προστίθεται σε έναν κρυπτογράφο μπλοκ ένας μηχανισμός ανατροφοδότησης. Ο τρόπος αυτός λειτουργίας ορίζει ότι πρωτού να γίνει η κρυπτογράφηση ενός νέου μπλοκ plaintext, γίνεται XOR (αποκλειστικό-Ή) του μπλοκ αυτού και του ciphertext μπλοκ που μόλις πριν έχει παραχθεί. Με τον τρόπο αυτό, 2 ταυτόσημα μπλοκ plaintext δεν κρυπτογραφούνται ποτέ στο ίδιο ciphertext. Σε σχέση με τον ECB προσφέρεται μεγαλύτερη ασφάλεια, με κόστος όμως κυρίως στην ταχύτητα κρυπτογράφησης καθώς για να ξεκινήσει η επεξεργασία ενός μπλοκ plaintext είναι απαραίτητο να έχει ολοκληρωθεί πλήρως η κρυπτογράφηση του προηγούμενου μπλοκ. Αποτρέπεται έτσι η χρήση τεχνικών pipelining (software ή hardware) που μπορούν να επιταχύνουν την διαδικασία.

Cipher Feedback (CFB)
Ο τρόπος αυτός λειτουργίας επιτρέπει σε έναν κρυπτογράφο μπλοκ να συμπεριφερθεί σαν ένας κρυπτογράφος ροής. Αυτό είναι θεμιτό όταν πρέπει να κρυπτογραφούνται δεδομένα που μπορεί να έχουν μέγεθος μικρότερο από ένα μπλοκ. Παράδειγμα τέτοιας εφαρμογής μπορεί να είναι η διαδικασία κρυπτογράφησης ενός terminal session. Περιληπτικά, κατά την CFB λειτουργία χρησιμοποιείται ένας shift καταχωρητής στο μέγεθος του block μέσα στον οποίο τοποθετούνται τα δεδομένα προς κρυπτογράφηση. Όλος ο καταχωρητής κρυπτογραφείται και αυτό που προκύπτει είναι το ciphertext. Η ποσότητα των δεδομένων που μπαίνουν μέσα στον shift καταχωρητή καθορίζεται από την εφαρμογή.

Output Feedback (OFB)
Στόχος και αυτού του τρόπου λειτουργίας των μπλοκ κρυπτογράφων είναι να εξασφαλίσει ότι το ίδιο plaintext μπλοκ δεν μπορεί να παράγει το ίδιο ciphertext μπλοκ. Σε σχέση με το CBC, χρησιμοποιείται και εδώ ένας μηχανισμός ανατροφοδότησης παρόλα αυτά είναι εσωτερικός και ανεξάρτητος από τα plaintext και ciphertext δεδομένα.

Σημαντικοί αλγόριθμοι αυτής της κατηγορίας είναι οι DES (Data Encryption Standard), 3DES, DESX, o AES (Advanced Encryption Standard), οι RC2, RC4, RC5 και IDEA (International Data Encryption Algorithm). Οι αλγόριθμοι της σειράς DES είναι οι πλέον χρησιμοποιούμενοι σήμερα αλγόριθμοι, αν και πλέον αντικαθιστούνται από τον AES. Επινοήθηκαν από την ΙΒΜ την δεκαετία του '70 και υιοθετήθηκαν από το National Bureau of Standards (νυν NIST) των ΗΠΑ. Οι DES αλγόριθμοι χρησιμοποιούν κλειδιά μήκους 56 bits (ο 3DES και ο DESX επεκτείνουν κατάλληλα αυτόν τον αριθμό χρησιμοποιώντας περισσότερα κλειδιά) και επεξεργάζονται μπλοκ των 64 bits. O AES αλγόριθμος είναι το πρότυπο που καθιερώθηκε από το NIST ως διάδοχος του DES και πλέον αποτελεί τον προτεινόμενο αλγόριθμο κρυπτογράφησης για εφαρμογές υψηλής ασφάλειας. Οι αλγόριθμοι RC είναι αλγόριθμοι μεταβλητού κλειδιού από την RSA Security ενώ ο IDEA χρησιμοποιείται στο πρότυπο PGP (Pretty Good Privacy).

2. H Διαδικασία Κρυπτογράφησης AES - Μια ιστορική αναδρομή

Όπως αναφέρθηκε παραπάνω, ο αλγόριθμος επιλογής του NIST για κρυπτογράφηση μυστικού κλειδιού ήταν ο DES. Παρόλα αυτά, λόγω της παλαιότητας του αλλά και της αλματώδους ανάπτυξης της υπολογιστικής ισχύος, έγινε εμφανές ότι ένας νέος αλγόριθμος απαιτούνταν. Τον Ιανουάριο του 1997 το NIST ανακοίνωσε ότι αναζητά έναν νέο αλγόριθμο κρυπτογράφησης για τον σχηματισμό ενός νέου προηγμένου προτύπου (AES - Advanced Encryption Standard). Τον Σεπτέμβριο του ίδιου έτους, ανακοινώθηκε η επίσημη διαδικασία πρότασης αλγορίθμων.

Η διαδικασία επιλογής χωρίστηκε σε αρκετούς γύρους με ένα δημόσιο συνέδριο (workshop) στο τέλος κάθε γύρου. Ο πρώτος γύρος ολοκληρώθηκε τον Αύγουστο του 1998, οπότε και επιλέχθηκαν 15 αλγόριθμοι ως υποψήφιοι για το νέο πρότυπο. Η αξιολόγηση των αλγορίθμων στους γύρους που ακολούθησαν αφορούσε τα χαρακτηριστικά τους ως προς την ασφάλεια, το κόστος υλοποίησης και την ταχύτητα (σε s/w και h/w).

Τον Απρίλιο του 1999 (δεύτερος γύρος) ανακοινώθηκε ότι από τους 15 υποψήφιους αλγορίθμους επιλέχθηκαν 5. Οι αλγόριθμοι αυτοί ήταν : MARS (Multiplication, Addition, Rotation and Substitution) από την IBM, Rijndael (από τα αρχικά των δημιουργών του) από τους Βέλγους Joan Daemen και Vincent Rijmen, Serpent από μια ομάδα Βρετανών, Ισραηλινών και Νορβηγών, RC6 από τον Ronald Rivest και TwoFish από τον Bruce Schneier.

H ανάλυση των αλγορίθμων οδήγησε σε λεπτομερή καταγραφή των ιδιοτήτων καθενός. Έτσι, στο τρίτο workshop για τον AES όπου παρουσιάστηκαν τα αποτελέσματα (Απρίλιος 2000), φάνηκε ότι ο πλέον δημοφιλής αλγόριθμος ήταν ο Rijndael. H απόφαση αυτή επισημοποιήθηκε τον Οκτώβριο του 2000 οπότε και το NIST ανακοίνωσε ότι αυτός θα ήταν ο αλγόριθμος για το πρότυπο AES.

Tον Φεβρουάριο του 2001, το NIST εξέδωσε τις draft προδιαγραφές του AES. Ο AES χρησιμοποιεί ένα υποσύνολο των δυνατοτήτων του Rijndael αλγορίθμου και στις επίσημες προδιαγραφές του NIST μια ελαφρώς διαφορετική ονοματολογία έχει επιλεγεί. Το τελικό κείμενο με τις προδιαγραφές του προτύπου εκδόθηκε προς το τέλος του 2001, ως FIPS-PUB-197 (Federal Information Processing Standard Publication).

3. Το Πρότυπο AES

3.1. Γενικά

To πρότυπο AES περιγράφει μια συμμετρική μπλοκ διαδικασία κρυπτογράφησης μυστικού κλειδιού. Το πρότυπο υποστηρίζει την χρήση κλειδιών μήκους 128, 192 και 256 bits. Ανάλογα με το ποιο μήκος κλειδιού χρησιμοποιείται, συνήθως χρησιμοποιείται η συντόμευση AES-128, AES-192 και AES-256 αντίστοιχα. Ανεξάρτητα από το μήκος κλειδιού, ο αλγόριθμος επενεργεί πάνω σε μπλοκ δεδομένων μήκους 128 bits. Η διαδικασία κρυπτογράφησης είναι επαναληπτική. Αυτό σημαίνει ότι σε κάθε μπλοκ δεδομένων γίνεται μια επεξεργασία η οποία επαναλαμβάνεται έναν αριθμό από φορές ανάλογα με το μήκος κλειδιού. Κάθε επανάληψη ονομάζεται γύρος (round). Στον πρώτο γύρο επεξεργασίας ως είσοδος είναι ένα plaintext μπλοκ και το αρχικό κλειδί, ενώ στους γύρους που ακολουθούν ως είσοδος είναι το μπλοκ που έχει προκύψει από τον προηγούμενο γύρο καθώς και ένα κλειδί που έχει παραχθεί από το αρχικό με βάση κάποια διαδικασία που ορίζει ο αλγόριθμος. Το τελικό προϊόν της επεξεργασίας είναι το κρυπτογραφημένο μπλοκ (ciphertext). Το μπλοκ αυτό πρέπει να σημειωθεί ότι έχει ακριβώς το ίδιο μέγεθος (128 bits) με το plaintext μπλοκ.

3.2. Είσοδοι, Έξοδοι και Εσωτερική Κατάσταση

Όπως ήδη αναφέρθηκε, ο AES τροφοδοτείται με ακολουθίες από bits των 128 bits (μπλοκ) καθώς και από κλειδιά, που μπορεί να έχουν μέγεθος 128, 192 ή 256 bits. Τα κλειδιά αυτά ονομάζονται κλειδιά κρυπτογράφησης (cipher keys) για να διαχωριστούν από τα κλειδιά που παράγονται κατά την λειτουργία του αλγορίθμου.

H βασική μονάδα επεξεργασίας στον AES είναι το byte. Έτσι τα bits ενός μπλοκ ή ενός κλειδιού χωρίζονται σε ομάδες των 8 για να σχηματιστούν τα bytes. Κάθε byte στον AES αντιστοιχεί σε ένα πολυώνυμο (αριθμητική πεπερασμένων πεδίων - finite field arithmetic). Αν υποθέσουμε ότι τα bits που αποτελούν ένα byte είναι τα {b₇, b₆, b₅, b₄, b₃, b₂, b₁, b₀}, τότε το byte αυτό αναπαριστά το πολυώνυμο :

Έτσι για παράδειγμα το byte {11001101} αντιστοιχεί στο πολυώνυμο x⁷ + x⁶ + x³ + x² + 1.

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

Σχήμα 2. Δεικτοδότηση των bits και bytes.

Όλες οι λειτουργίες που επιτελεί ο αλγόριθμος γίνονται πάνω σε ένα διδιάστατο πίνακα που αποκαλείται Κατάσταση (State). O πίνακας αυτός περιλαμβάνει τέσσερις γραμμές από bytes, με κάθε μία γραμμή να αποτελείται από Nb bytes. O αριθμός που αντιστοιχεί στην ποσότητα Νb υπολογίζεται αν διαιρεθεί το μήκος του μπλοκ με το 32. Εφόσον στον AES υποστηρίζονται μπλοκ μεγέθους μόνο 128 bits, το Nb θα έχει τιμή 4.

To μπλοκ εισόδου περιλαμβάνει 16 bytes, τα οποία δεικτοδοτούνται in₀ έως in₁₅. Το κρυπτογραφημένο μπλοκ εξόδου περιλαμβάνει επίσης 16 bytes που δεικτοδοτούνται ως out₀ έως out₁₅. H State χρησιμοποιεί την μεταβλητή s με δύο δείκτες που δηλώνουν την θέση κάθε byte στον πίνακα. Η πρώτη λοιπόν και τελευταία λειτουργία που μπορεί να υποτεθεί ότι γίνεται στον AES είναι να αντιστοιχηθούν τα bytes εισόδου σε κάποια θέση του πίνακα της State και το αντίστροφο στην έξοδο. Το Σχήμα 3 δείχνει πώς γίνεται αυτό.

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

Σχήμα 3. Αντιστοίχηση bytes εισόδου στην State και από την State στην έξοδο.

Η αντιστοίχηση που περιγράφηκε παραπάνω μπορεί να περιγραφεί μαθηματικά. Η αντιστοίχηση εισόδου στην State περιγράφεται από την σχέση :

Ένας άλλος τρόπος να δει κάποιος τα περιεχόμενα της State είναι σαν 32-bit λέξεις (words) αντί για bytes. Μια 32-bit word περιλαμβάνει τα 4 bytes μιας στήλης, οπότε τα 4 words που αποτελούν την State είναι τα ακόλουθα (δείτε και το Σχήμα 3) :

3.3. Περιγραφή Αλγορίθμου

Όπως αναφέρθηκε στην προηγούμενη ενότητα, το πρότυπο AES ορίζει ότι τα μπλοκ που επεξεργάζεται ο αλγόριθμος έχουν μέγεθος 128 bits και αυτό ορίζεται από την ποσότητα Nb = 4, που συμβολίζει τον αριθμό των 32-bit λέξεων στο μπλοκ. Από την άλλη, τα κλειδιά που χρησιμοποιούνται για την κρυπτογράφηση, μπορούν να έχουν μήκος 128, 192 ή 256 bits. Η μεταβλητή Nk συμβολίζει τον αριθμό των 32-bit λέξεων που μπορεί να περιλαμβάνει ένα κλειδί και κατά συνέπεια μπορεί να πάρει τις τιμές 4, 6 και 8.

Ανάλογα με το μήκος κλειδιού που θα επιλεχθεί για την κρυπτογράφηση, ο αλγόριθμος ορίζει έναν αριθμό από γύρους επεξεργασίας που απαιτούνται για την ολοκλήρωση της. Η μεταβλητή Nr χρησιμοποιείται για να δηλώσει το πλήθος των γύρων. Αν χρησιμοποιηθεί μήκος κλειδιού 128 bits τότε απαιτούνται 10 γύροι επεξεργασίας. Για μήκη κλειδιού ίσα με 192 και 256 bits απαιτούνται αντίστοιχα 12 και 14 γύροι.

Να σημειωθεί ότι οι παραπάνω συνδυασμοί μήκους μπλοκ, μήκους κλειδιού και γύρων επεξεργασίας είναι αυτοί που ορίζονται αυστηρά στο πρότυπο AES. Ο αλγόριθμος κρυπτογράφησης Rijndael στον οποίο βασίζεται ο AES δίνει την δυνατότητα πραγματοποίησης περισσότερων συνδυασμών. Έτσι, καταλαβαίνει κανείς ότι ο AES ουσιαστικά ορίζει ένα υποσύνολο του αλγορίθμου Rijndael.

Τόσο κατά την διάρκεια της διαδικασίας κρυπτογράφησης όσο και αποκρυπτογράφησης, κάθε γύρος επεξεργασίας αποτελείται από μια σειρά μετασχηματισμών σε επίπεδο byte. Για την ακρίβεια, χρησιμοποιούνται 4 τύποι μετασχηματισμών :

1. ένας μετασχηματισμός αντικατάστασης bytes χρησιμοποιώντας κάποιον σχετικό πίνακα αντικατάστασης
2. ένας μηχανισμός ολίσθησης των bytes της State κατά διαφορετικά offsets
3. μια διαδικασία ανάμειξης των bytes της State
4. μια πρόσθεση ενός κλειδιού στην State

3.3.1. O Αλγόριθμος Κρυπτογράφησης

Στην αρχή της διαδικασίας κρυπτογράφησης ένα μπλοκ εισόδου (plaintext) αντιγράφεται στην State. Μετά από έναν αρχικό γύρο πρόσθεσης κλειδιού, ακολουθούν 10, 12 ή 14 γύροι επεξεργασίας, με τον τελευταίο γύρο να διαφέρει από τους υπόλοιπους. Η τελική State αντιγράφεται στην έξοδο και η επεξεργασία για το συγκεκριμένο block ολοκληρώνεται (παραγωγή του ciphertext μπλοκ).

Το μυστικό κλειδί κρυπτογράφησης που χρησιμοποιείται σαν είσοδος στον αλγόριθμο είναι το κλειδί που προστίθεται στο μπλοκ εισόδου πριν αρχίσει η επεξεργασία. Σε καθέναν από τους γύρους επεξεργασίας, όπως αναφέρθηκε παραπάνω, υπάρχει μια φάση κατά την οποία προστίθεται στο μπλοκ και ένα κλειδί. Το κλειδί που προστίθεται στις περιπτώσεις αυτές, δεν είναι το αρχικό μυστικό κλειδί αλλά κάποιο που έχει προκύψει με μια συγκεκριμένη διαδικασία από το μυστικό κλειδί και είναι διαφορετικό για κάθε γύρο. Για τον λόγο αυτό, τα κλειδιά αυτά ονομάζονται round keys. Η διαδικασία με την οποία προκύπτουν τα round κλειδιά ονομάζεται Επέκταση Κλειδιού και θα αναλυθεί σε επόμενη ενότητα.

Αυτό που πρέπει να διευκρινιστεί είναι η έννοια της πρόσθεσης στον AES αλγόριθμο. Σε προηγούμενη ενότητα έχει αναφερθεί ότι τα bytes της πληροφορίας κατά την επεξεργασία τους λαμβάνονται ως πολυώνυμα. Έτσι, η πράξη της πρόσθεσης είναι ουσιαστικά μια διαδικασία πρόσθεσης πολυωνύμων. H πρόσθεση μεταξύ πολυωνύμων πραγματοποιείται με την πρόσθεση των συντελεστών των αντίστοιχων όρων (δυνάμεων) των πολυωνύμων. Η πρόσθεση γίνεται modulo-2, δηλαδή μέσω μιας XOR πράξης. Να υπενθυμηθεί ότι η XOR πράξη μεταξύ δύο bits (συμβολίζεται με ) έχει τον εξής πίνακα αληθείας : 0 0 = 0 0 1 = 1 1 0 = 1 1 1 = 0

Αν κάθε βασικός μετασχηματισμός του AES αναπαρασταθεί από μια συνάρτηση που επενεργεί στην State, τότε ο αλγόριθμος κρυπτογράφησης μπορεί να περιγραφεί από τον ψευδοκώδικα που παρουσιάζεται στο Σχήμα 4. Οι συναρτήσεις αυτές αναφέρονται ως SubBytes(), ShiftRows(), MixColumns() και AddRoundKey() και αντιστοιχούν (με αυτήν την σειρά) στους μετασχηματισμούς 1 έως 4 όπως αναφέρθηκαν παραπάνω.

Σχήμα 4. Ο ψευδοκώδικας για την διαδικασία κρυπτογράφησης. Να σημειωθεί ότι το array w χρησιμοποιείται για να δηλώσει την συλλογή των round keys που παράγονται από την διαδικασία επέκτασης κλειδιού.

3.3.1.1. O Μετασχηματισμός SubBytes

Ο μετασχηματισμός SubBytes αποτελεί μια μη γραμμική αντικατάσταση των bytes της State με την χρήση ενός πίνακα αντικατάστασης (S-Box). Οι τιμές του πίνακα αυτού (που είναι αντιστρέψιμος) υπολογίζονται με την σύνθεση των δύο ακόλουθων μετασχηματισμών :

1. παίρνοντας τον πολλαπλασιαστικό αντίστροφο στο πεπερασμένο πεδίο GF(2⁸) - με το στοιχείο {00} να αντιστοιχίζεται στον εαυτό του
2. εφαρμόζοντας τον ακόλουθο μετασχηματισμό (στο GF(2)) :
   
   για 0 &le i < 8 , όπου b_i είναι το i-οστό bit του byte, και c_i είναι το i-οστό bit του byte c με την τιμή {63} or {01100011}.

Ο πίνακας S-Box τυπικά δεν υπολογίζεται κατά την διαδικασία της κρυπτογράφησης, αλλά οι τιμές του έχουν προϋπολογιστεί. Στο Σχήμα 5 που ακολουθεί παρατίθενται οι τιμές του πίνακα S-Box όπως τις παρουσιάζει το NIST στο επίσημο έγγραφο για τον AES. Για όσους από τους αναγνώστες δεν είναι εξοικιωμένοι με την γραφή αριθμών στο δεκαεξαδικό σύστημα, να σημειωθεί ότι ένας αριθμός στο δεκαεξαδικό σύστημα χρειάζεται 4 bits για να αναπαρασταθεί. Κατά συνέπεια, ένα byte αναπαρίσταται από 2 δεκαεξαδικά ψηφία χωρίζοντας το σε 2 ομάδες των 4 bits. Έτσι η γραμμή x του πίνακα αναφέρεται στα πρώτα 4 bits του byte και η στήλη y στα επόμενα 4.




Σχήμα 5. O πίνακας αντικατάστασης S-Box.

Εφόσον αναφέρθηκε ο θεωρητικός τρόπος με τον οποίο προκύπτει ο πίνακας S-Box, καλό θα ήταν να διευκρινιστεί τι σημαίνει πολλαπλασιασμός στο GF(28). Είναι ο πολλαπλασιασμός μεταξύ πολυωνύμων modulo ένα irreducible πολυώνυμο βαθμού 8. Irreducible ονομάζεται ένα πολυώνυμο αν διαιρείται μονάχα από τον εαυτό του και την μονάδα. Το πολυώνυμο που έχει επιλεχθεί για το AES είναι το : Η modulo πράξη εξασφαλίζει ότι το πολυώνυμο που θα προκύψει θα είναι ένα δυαδικό πολυώνυμο βαθμού μικρότερου του 8, άρα θα μπορεί να αναπαρασταθεί από ένα byte. Να σημειωθεί ότι το ουδέτερο στοιχείο της πράξης είναι το {01} και ότι το σύμβολο που χρησιμοποιείται για να διακρίνει την πράξη αυτή από έναν κοινό αριθμητικό πολλαπλασιασμό είναι το .


3.3.1.2. O Μετασχηματισμός ShiftRows

Ο μετασχηματισμός αυτός επιβάλει την κυκλική ολίσθηση των bytes των γραμμών της State. Η πρώτη γραμμή παραμένει ανέπαφη, ενώ στις υπόλοιπες τα bytes ολισθαίνουν με διαφορετικό offset. Το Σχήμα 6 παρουσιάζει ενδεικτικά πώς γίνεται ο μετασχηματισμός αυτός.

Όπως μπορεί να παρατηρηθεί από το Σχήμα 4, η δεύτερη γραμμή ολισθαίνει αριστερά κατά μία θέση με αποτέλεσμα το πρώτο byte της γραμμής να βρεθεί τελευταίο (κυκλική ολίσθηση). Με αντίστοιχο τρόπο ολισθαίνουν και οι γραμμές 3 και 4 αλλά κατά 2 και 3 θέσεις αντίστοιχα.




Σχήμα 6. Ο μετασχηματισμός ShiftRows ολισθαίνει κυκλικά προς τα αριστερά τις τρεις τελευταίες γραμμές του State.


3.3.1.3. O Μετασχηματισμός ΜixColumns

Ο μετασχηματισμός αυτός εφαρμόζεται στις στήλες της State. Η κάθε στήλη θεωρείται σαν πολυώνυμο τρίτης τάξης με συντελεστές τις τιμές των bytes της στήλης.




Τα πολυώνυμα πολλαπλασιάζονται modulo (x⁴ + 1) με ένα καθορισμένο πολυώνυμο που δίνεται από την σχέση :




Η διαδικασία αυτή του υπολογισμού της αρχικής πράξης , όπου με συμβολίζεται ο modulo πολλαπλασιασμός μετασχηματίζεται τελικά στις εξής σχέσεις :




για 0 &le c < Nb


3.3.1.4. O Μετασχηματισμός AddRoundKey

Ο μετασχηματισμός αυτός επιβάλει την πρόσθεση της τιμής της ποσότητας round key στα bytes των στηλών του πίνακα State. Επειδή κάθε τιμή του round key αποτελείται από Nb λέξεις, επιλέγεται κάθε φορά η επιθυμητή λέξη. Η πράξη αυτή υλοποιείται σαν απλή XOR πράξη ανάμεσα στα bits των ποσοτήτων (bitwise XOR). Η πράξη αυτή μεταφράζεται μαθηματικά στην εξής σχέση:




για 0 &le c < Nb


3.3.2. Επέκταση Κλειδιού

Η διαδικασία επέκτασης του κλειδιού (Key Expansion) δέχεται ως είσοδο τo αρχικό μυστικό κλειδί (cipher key K), μήκους Nb λέξεων, και παράγει μια ακολουθία κλειδιών. Παράγονται συνολικά από αυτή την διαδικασία Nb(Nr+1) λέξεις καθώς σε κάθε έναν από τους Nr γύρους επεξεργασίας απαιτούνται Nb λέξεις από δεδομένα κλειδιού. Το τελικό key schedule αποτελείται από έναν γραμμικό πίνακα w_i με 0 &le i < Nb(Nr+1) που περιέχει λέξεις των τεσσάρων bytes. Στο Σχήμα 7 παρατίθεται σε μορφή ψευδοκώδικα, η διαδικασία επέκτασης κλειδιού.




Σχήμα 7. Ο ψευδοκώδικας της διαδικασίας επέκτασης κλειδιού.

Η διαδικασία SubWord εκτελεί ουσιαστικά την ίδια διαδικασία με την συνάρτηση SubByte μόνο που αυτή την φορά προσδιορίζεται η αντίστοιχη τιμή μιας ολόκληρης λέξης, δηλαδή 4 bytes, μέσω του πίνακα S-box. Είναι, τελικά, σαν να εκτελείται διαδοχικά 4 φορές η συνάρτηση SubByte().

Η συνάρτηση RotWord() δέχεται ως είσοδο μια λέξη και ολισθαίνει κυκλικά τα bytes που την αποτελούν. Αν για παράδειγμα, δοθεί σαν είσοδος μια λέξη [a0,a1,a2,a3] τότε σαν έξοδο έχουμε την λέξη [a1,a2,a3,a0].

Τέλος, το διάνυσμα Rcon[i] (Round constant word array) περιέχει τις τιμές που δίνονται από την σχέση [x^i-1,{00,{00},{00}] με τις τιμές του i να ξεκινούν από 1 και όχι 0.


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

Οι μετασχηματισμοί της διαδικασίας κρυπτογράφησης (όπως περιγράφηκαν στην ενότητα 3.3.1.) μπορούν να αντιστραφούν και να τοποθετηθούν σε αντίστροφη σειρά ώστε να παραχθεί μια διαδικασία που θα αποκρυπτογραφεί ένα ciphertext του AES. Έτσι όπως και κατά την κρυπτογράφηση, υπάρχουν τέσσερις διακριτοί μετασχηματισμοί που επενεργούν πάνω στην State κατά την αποκρυπτογράφηση, οι InvShiftRows, InvSubBytes, InvMixColumns και AddRoundKey.

Στο Σχήμα 8 παρουσιάζεται ο ψευδοκώδικας που περιγράφει την διαδικασία αποκρυπτογράφησης. Να σημειωθεί ότι το array w που εμφανίζεται είναι το ίδιο ακριβώς array με τα κλειδιά (cipher και round) που χρησιμοποιήθηκε και κατά την κρυπτογράφηση. Η διαδικασία παραγωγής των κλειδιών είναι ταυτόσημη με αυτή που περιγράφηκε στην ενότητα 3.3.2.




Σχήμα 8. O ψευδικώδικας της διαδικασίας αποκρυπτογράφησης.


3.3.3.1. O Μετασχηματισμός InvShiftRows

O μετασχηματισμός InvShiftRows είναι ο αντίστροφος του ShiftRows της διαδικασίας κρυπτογράφησης. Τα bytes στις τελευταίες τρεις γραμμές της State ολισθαίνουν κατά διαφορετικά offests, με αντίθετη φορά από ότι στην ShiftRows διαδικασία. Στο Σχήμα 9 παρουσιάζεται ο ακριβής μηχανισμός.




Σχήμα 9. O μετασχηματισμός InvShiftRows.


3.3.3.2. O Μετασχηματισμός InvSubBytes

O μετασχηματισμός αυτός, όπως δηλώνει και το όνομα του, είναι ο αντίστροφος του μετασχηματισμού αντικατάστασης bytes της κρυπτογράφησης. Έτσι, στην περίπτωση αυτή, αντί για το S-Box πίνακα χρησιμοποιείται ο αντίστροφος του (inverse S-Box), ο οποίος και παρουσιάζεται στο Σχήμα 10.




Σχήμα 10. Ο πίνακας inverse S-Box.


3.3.3.3. O Μετασχηματισμός InvMixColumns

Είναι ο αντίστροφος του μετασχηματισμού MixColumns. Όπως και ο ΜixColumns εφαρμόζεται πάνω στις στήλες της State, θεωρώντας κάθε μία από αυτές ένα πολυώνυμο τεσσάρων όρων. Κάθε στήλη, θεωρείται πολυώνυμο του GF(2⁸) και πολλαπλασιάζεται modulo x⁴ + 1 με ένα καθορισμένο πολυώνυμο a^-1(x) :



Σαν αποτέλεσμα του παραπάνω πολλαπλασιασμού, τα 4 bytes σε μια στήλη αντικαθίστανται από τα ακόλουθα bytes :




3.3.3.4. O Αντίστροφος Μετασχηματισμός AddRoundKey

Εφόσον ο μετασχηματισμός αυτός είναι μια απλή XOR πράξη, είναι από μόνος του αντιστρέψιμος και κατά συνέπεια είναι ταυτόσημος με τον μετασχηματισμό που περιγράφηκε στην ενότητα 3.3.1.4.




          ΠΗΓΕΣ.

1. FIPS. Advanced Encryption Standard (AES). FIPS PUB-197, April 2, 2001
To κείμενο αυτό είναι η πλήρης και επίσημη προδιαγραφή του αλγορίθμου όπως διατίθεται από το NIST. Εκτός από την περιγραφή του αλγορίθμου, στις σελίδες του κειμένου θα βρείτε πλήρες μαθηματικό υπόβαθρο για όλες τις λειτουργίες του αλγορίθμου, παρατηρήσεις για την υλοποίηση του, καθώς και παραδείγματα με αποτελέσματα που μπορείτε να χρησιμοποιήσετε αν θέλετε να διαπιστώσετε ότι μια δική σας υλοποίηση λειτουργεί σωστά.
2. AES Lounge
H σελίδα αυτή περιλαμβάνει μια αναφορά στο σύνολο σχεδόν όλης της ερευνητικής δουλειάς γύρω από τον AES. Περιλαμβάνονται links προς όλα τα επίσημα έγγραφα, καθώς και οι τίτλοι όλων (σχεδόν) των δημοσιευμένων papers που σχετίζονται με διάφορες πλευρές του αλγορίθμου, όπως h/w και s/w υλοποιήσεις, ανάλυση για επιθέσεις και αδυναμίες κτλ.
3. An Overview of Cryptography
Στην σελίδα αυτή θα βρείτε χρήσιμες πληροφορίες όχι μόνο για τον AES, αλλά για την σύγχρονη κρυπτογραφία γενικότερα. Είναι εξαιρετικά ενδιαφέρουσα, παρέχει πολλά links και είναι μια πάρα πολύ καλή εισαγωγή για κάποιον νέο στο αντικείμενο.
4. A. Menezes, P. van Oorschot and S. Vanstone. Handbook of Applied Cryptography, CRC Press, 1996