Σχήμα κρυπτογράφησης του αλγορίθμου DES. Αλγόριθμοι κρυπτογράφησης DES και AES

Αυτό που το ANSI αποκαλεί τον αλγόριθμο κρυπτογράφησης δεδομένων DEA (Data Encryption Algorithm), και το ISO τον ονομάζει DEA-1, έχει γίνει παγκόσμιο πρότυπο μέσα σε 20 χρόνια. Στα χρόνια της ύπαρξής του, έχει αντέξει στην επίθεση διαφόρων επιθέσεων και, με ορισμένους περιορισμούς, εξακολουθεί να θεωρείται κρυπτο-ανθεκτικό.

Το DES είναι ένας μπλοκ κρυπτογράφησης που κρυπτογραφεί δεδομένα σε μπλοκ 64-bit. Ένα μπλοκ απλού κειμένου 64 bit εισάγεται στο ένα άκρο του αλγορίθμου και ένα μπλοκ κρυπτογραφημένου κειμένου 64 bit εξάγεται στο άλλο άκρο. Ο DES είναι ένας συμμετρικός αλγόριθμος: ο ίδιος αλγόριθμος και κλειδί χρησιμοποιούνται για κρυπτογράφηση και αποκρυπτογράφηση (εκτός από μικρές διαφορές στη χρήση του κλειδιού). Το μήκος του κλειδιού είναι 56 bit. (Ένα κλειδί αντιπροσωπεύεται συνήθως ως αριθμός 64 bit, αλλά κάθε όγδοο bit χρησιμοποιείται για ισοτιμία και αγνοείται. Τα bit ισοτιμίας είναι τα λιγότερο σημαντικά bit των byte κλειδιού.) Το κλειδί, το οποίο μπορεί να είναι οποιοσδήποτε αριθμός 56 bit , μπορεί να αλλάξει ανά πάσα στιγμή.

Η κρυπτογραφική ισχύς καθορίζεται πλήρως από το κλειδί. Το θεμελιώδες δομικό στοιχείο του DES είναι ο συνδυασμός αντικαταστάσεων και μεταθέσεων. Το DES αποτελείται από 16 κύκλους.

Γενική άποψη του κύκλου μετατροπής:

Εάν τα L i και R i είναι το αριστερό και το δεξί μισό που προκύπτουν από την επανάληψη, το K i είναι το κλειδί 48 bit για τον βρόχο i, και το f είναι μια συνάρτηση που εκτελεί όλες τις αντικαταστάσεις, τις μεταθέσεις και τα XOR στο κλειδί, τότε ένα Ο βρόχος μετατροπής μπορεί να αναπαρασταθεί ως:

Λαμβάνοντας υπόψη την αντικατάσταση F i (*) και τη μετάθεση T (*), ο κύκλος μετασχηματισμού μπορεί να αναπαρασταθεί όπως φαίνεται στο Σχήμα.

Μπορεί να φανεί ότι κάθε κύκλος DES είναι ένας κρυπτογράφηση σύνθεσης με δύο διαδοχικούς μετασχηματισμούς - αντικατάσταση F i (*) και μετάθεση T (*) (με εξαίρεση τον τελευταίο, δέκατο έκτο κύκλο, όπου η μετάθεση παραλείπεται).

Υποκατάσταση:

(L i , R i) = (R i −1 , L i −1) ⊕ f (R i −1 , K)

είναι μια εξέλιξη, αφού

F i (F i (L i −1 , R i −1)) = F i (R i −1 , L i −1) ⊕ (f (R i −1 , K i))) = (R i − 1 , L i −1 ⊕(f (R i −1 , K i)) ⊕ (f (R i −1 , K i))) = (L i −1 , R i −1)

Μια αντικατάσταση

T (L i ′, R i ′) = (R i ′, L i ′),

είναι επίσης μια μετεξέλιξη, αφού

T (T (L i ′, R i ′)) = T (R i ′, L i ′) = L i ′, R i ′

Αν υποδηλώσουμε την αρχική και την τελική μετάθεση ως (IP) και (IP) − 1, τότε ο άμεσος μετασχηματισμός DES (κρυπτογράφηση) υλοποιεί τη συνάρτηση:

DES = (IP) F 1 TF 2 T … F 15 TF 16 (IP) − 1,

και ο αντίστροφος μετασχηματισμός DES (αποκρυπτογράφηση) υλοποιεί τη συνάρτηση:

DES − 1 = (IP) −1 F 16 TF 15 T … F 2 TF 1 (IP).

Έτσι, το DES είναι ένας κρυπτογράφησης Feistel και έχει σχεδιαστεί για να εκπληρώνει τη χρήσιμη ιδιότητα ότι ο ίδιος αλγόριθμος χρησιμοποιείται για κρυπτογράφηση και αποκρυπτογράφηση. Η μόνη διαφορά είναι ότι τα κλειδιά πρέπει να χρησιμοποιούνται με αντίστροφη σειρά.

Δηλαδή, εάν τα κλειδιά K 1, K 2, K 3, ..., K 16 χρησιμοποιήθηκαν κατά την κρυπτογράφηση, τότε τα κλειδιά αποκρυπτογράφησης θα είναι K 16, K 15, K 14, ..., K 1. Ο αλγόριθμος χρησιμοποιεί μόνο τυπικές αριθμητικές και λογικές πράξεις 64-bit, ώστε να μπορεί να εφαρμοστεί εύκολα σε υλικό.

Το DES λειτουργεί σε μπλοκ απλού κειμένου 64 bit. Μετά την αρχική ανακάτεμα, το μπλοκ χωρίζεται σε δεξιό και αριστερό μισό των 32 bit το καθένα. Στη συνέχεια εκτελούνται 16 μετασχηματισμοί (συνάρτηση f) στους οποίους τα δεδομένα συνδυάζονται με το κλειδί. Μετά τον δέκατο έκτο κύκλο, το δεξί και το αριστερό μισό συνδυάζονται και ο αλγόριθμος τελειώνει με μια τελική μετάθεση (το αντίστροφο του αρχικού). Σε κάθε κύκλο (βλ. σχήμα), τα μπιτ πλήκτρων μετατοπίζονται και, στη συνέχεια, επιλέγονται 48 bit από τα 56 bit πλήκτρων. Το δεξί μισό των δεδομένων επεκτείνεται στα 48 bit χρησιμοποιώντας τη μετάθεση επέκτασης, το XOR με τα 48 bit του μετατοπισμένου και μετατεθέντος κλειδιού, περνά μέσα από 8 S-πλαίσια για να σχηματίσει 32 νέα bit και μετατίθεται ξανά. Αυτές οι τέσσερις πράξεις εκτελούνται από τη συνάρτηση f.

Το αποτέλεσμα της f συνδυάζεται στη συνέχεια με το αριστερό μισό χρησιμοποιώντας ένα άλλο XOR. Ως αποτέλεσμα αυτών των ενεργειών, εμφανίζεται ένα νέο δεξί μισό και το παλιό δεξί γίνεται νέο αριστερό μισό. Αυτά τα βήματα επαναλαμβάνονται 16 φορές, με αποτέλεσμα 16 κύκλους DES.

Ρωσικό πρότυπο - GOST 28147-89

Το GOST 28147-89 είναι ένας κρυπτογράφηση μπλοκ με κλειδί 256 bit και 32 κύκλους μετατροπής, που λειτουργεί σε μπλοκ 64 bit. Ο αλγόριθμος κρυπτογράφησης χρησιμοποιεί επίσης ένα πρόσθετο κλειδί, το οποίο συζητείται παρακάτω. Για κρυπτογράφηση, το απλό κείμενο αρχικά χωρίζεται σε αριστερό και δεξί μισό L και R. Στον i-ο κύκλο, χρησιμοποιείται το δευτερεύον κλειδί K i:

L i = R i −1,
R i = L i −1 ⊕ (f (R i −1 , K i)).

Η συνάρτηση f υλοποιείται ως εξής. Αρχικά, το δεξί μισό και το i-ο δευτερεύον κλειδί προστίθενται modulo 2 32. Το αποτέλεσμα χωρίζεται σε οκτώ υποακολουθίες 4-bit, καθεμία από τις οποίες εισάγεται στο δικό της S-box. Το GOST χρησιμοποιεί οκτώ διαφορετικά S-box, τα πρώτα 4 bit πηγαίνουν στο πρώτο S-box, τα δεύτερα 4 bit στο δεύτερο S-box, κ.λπ. Κάθε S-box είναι μια μετάθεση αριθμών από το 0 έως το 15. Για παράδειγμα, Το S-box μπορεί να μοιάζει με: 7,10,2,4,15,9,0,3,6,12,5,13,1,8,11. Σε αυτήν την περίπτωση, εάν η είσοδος του S-box είναι 0, τότε η έξοδος είναι 7. Εάν η είσοδος είναι 1, η έξοδος είναι 10, κ.λπ. Και τα οκτώ S-box είναι διαφορετικά, είναι στην πραγματικότητα πρόσθετο υλικό κλειδιού. Οι έξοδοι και των οκτώ S-box συνδυάζονται σε μια λέξη 32 bit και, στη συνέχεια, ολόκληρη η λέξη περιστρέφεται αριστερά κατά 11 bit. Τέλος, το αποτέλεσμα γίνεται XOR με το αριστερό μισό για να δημιουργηθεί ένα νέο δεξί μισό, και το δεξί μισό γίνεται το νέο αριστερό μισό. Για τη δημιουργία δευτερευόντων κλειδιών, το αρχικό κλειδί 256 bit χωρίζεται σε οκτώ μπλοκ 32 bit: k 1, k 2, ..., k 8. Κάθε κύκλος χρησιμοποιεί το δικό του δευτερεύον κλειδί. Η αποκρυπτογράφηση εκτελείται με τον ίδιο τρόπο όπως η κρυπτογράφηση, αλλά η σειρά των δευτερευόντων κλειδιών k i αντιστρέφεται. Το πρότυπο δεν προσδιορίζει πώς δημιουργούνται τα S-boxes.

Κύριες διαφορές μεταξύ DES και GOST

Οι κύριες διαφορές μεταξύ DES και GOST είναι οι εξής:

• Το DES χρησιμοποιεί μια πολύπλοκη διαδικασία για τη δημιουργία δευτερευόντων κλειδιών από κλειδιά. Στο GOST αυτή η διαδικασία είναι πολύ απλή.
• στο DES υπάρχει ένα κλειδί 56-bit και στο GOST είναι 256-bit. Εάν προσθέσουμε μυστικές μεταθέσεις των S-box, τότε ο συνολικός όγκος των μυστικών πληροφοριών GOST θα είναι περίπου 610 bit.
• Τα κουτιά DES S έχουν εισόδους και εξόδους 6 bit, ενώ τα κουτιά GOST S έχουν εισόδους και εξόδους 4 bit. Και οι δύο αλγόριθμοι χρησιμοποιούν οκτώ S-box, αλλά το μέγεθος του GOST S-box είναι ίσο με το ένα τέταρτο του μεγέθους του S-box DES.
• Το DES χρησιμοποιεί ακανόνιστες μεταθέσεις που ονομάζονται P-block, ενώ το GOST χρησιμοποιεί μια κυκλική αριστερή μετατόπιση 11 bit.
• στο DES υπάρχουν 16 κύκλοι και στο GOST - 32.

Μια βίαιη επίθεση στο GOST είναι απολύτως μάταιη. Το GOST χρησιμοποιεί ένα κλειδί 256-bit και αν λάβετε υπόψη τα μυστικά κουτιά S, το μήκος του κλειδιού θα είναι ακόμη μεγαλύτερο. Το GOST φαίνεται να είναι πιο ανθεκτικό στη διαφορική και γραμμική κρυπτανάλυση από το DES. Αν και τα τυχαία κουτιά GOST S, δεδομένου ορισμένων επιλογών, δεν εγγυώνται υψηλή κρυπτογραφική αντοχή σε σύγκριση με τα σταθερά κουτιά DES S, η μυστικότητά τους αυξάνει την αντίσταση του GOST στη διαφορική και γραμμική κρυπτανάλυση. Επιπλέον, η αποτελεσματικότητα αυτών των κρυπταναλυτικών μεθόδων εξαρτάται από τον αριθμό των κύκλων μετατροπής - όσο περισσότεροι κύκλοι, τόσο πιο δύσκολη είναι η κρυπτανάλυση. Το GOST χρησιμοποιεί διπλάσιο αριθμό κύκλων από το DES, προκαλώντας πιθανώς την αποτυχία της διαφορικής και γραμμικής κρυπτανάλυσης.

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

Η κύρια διαφορά φαίνεται να είναι η χρήση της κυκλικής μετατόπισης αντί της μετάθεσης στο GOST. Η αναδιάταξη του DES αυξάνει το φαινόμενο χιονοστιβάδας. Στο GOST, η αλλαγή ενός bit εισόδου επηρεάζει ένα S-box ενός κύκλου μετατροπής, το οποίο στη συνέχεια επηρεάζει δύο S-box του επόμενου κύκλου, στη συνέχεια τρία block του επόμενου κύκλου κ.λπ. Χρειάζονται οκτώ κύκλοι προτού η αλλαγή ενός bit εισόδου επηρεάσει κάθε bit της εξόδου. στο DES αυτό απαιτεί μόνο πέντε κύκλους. Ωστόσο, το GOST αποτελείται από 32 κύκλους και το DES μόνο από 16.

Οι προγραμματιστές του GOST προσπάθησαν να επιτύχουν μια ισορροπία μεταξύ κρυπτογραφικής ισχύος και αποτελεσματικότητας. Χρησιμοποιώντας το σχέδιο του Feistel ως βάση, ανέπτυξαν έναν κρυπτογραφικό αλγόριθμο που είναι πιο κατάλληλος για εφαρμογή λογισμικού από το DES. Για να αυξηθεί η κρυπτογραφική ισχύς, εισήχθη ένα πολύ μεγάλο κλειδί και ο αριθμός των κύκλων διπλασιάστηκε. Ωστόσο, το ερώτημα αν οι προσπάθειες των προγραμματιστών στέφθηκαν με τη δημιουργία ενός πιο κρυπτογραφικού αλγορίθμου από τον DES παραμένει ανοιχτό.

Vorobyova E., Lukyanova A.

Σχόλιο: Ένα από τα πιο διάσημα κρυπτογραφικά συστήματα ιδιωτικού κλειδιού είναι το DES – Data Encryption Standard. Αυτό το σύστημα ήταν το πρώτο που έλαβε την κατάσταση ενός κρατικού προτύπου στον τομέα της κρυπτογράφησης δεδομένων. Και παρόλο που το παλιό αμερικανικό πρότυπο DES έχει πλέον χάσει την επίσημη κατάστασή του, αυτός ο αλγόριθμος εξακολουθεί να αξίζει προσοχής κατά τη μελέτη της κρυπτογραφίας. Αυτή η διάλεξη εξηγεί επίσης τι είναι το διπλό DES, μια επίθεση συνάντησης στη μέση και πώς να το μετριάσεις. Αυτή η διάλεξη εξετάζει επίσης εν συντομία το νέο πρότυπο των ΗΠΑ για κρυπτογράφηση μπλοκ, τον αλγόριθμο Rijndael.

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

Βασικές πληροφορίες

Ένα από τα πιο διάσημα κρυπτογραφικά συστήματα ιδιωτικού κλειδιού είναι DES – Πρότυπο κρυπτογράφησης δεδομένων. Αυτό το σύστημα ήταν το πρώτο που έλαβε την κατάσταση ενός κρατικού προτύπου στον τομέα της κρυπτογράφησης δεδομένων. Αναπτύχθηκε από ειδικούς της IBM και τέθηκε σε ισχύ στις ΗΠΑ το 1977. Αλγόριθμος DESχρησιμοποιείται ευρέως για την αποθήκευση και τη μετάδοση δεδομένων μεταξύ διαφόρων συστημάτων υπολογιστών. σε ταχυδρομικά συστήματα, ηλεκτρονικά συστήματα σχεδίασης και ηλεκτρονική ανταλλαγή εμπορικές πληροφορίες. Πρότυπο DESυλοποιήθηκε τόσο σε λογισμικό όσο και σε υλικό. Επιχειρήσεις από διάφορες χώρες έχουν ξεκινήσει μαζική παραγωγή ψηφιακών συσκευών χρησιμοποιώντας DESγια κρυπτογράφηση δεδομένων. Όλες οι συσκευές υποβλήθηκαν σε υποχρεωτική πιστοποίηση για συμμόρφωση με το πρότυπο.

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

Μήκος κλειδιού στον αλγόριθμο DESείναι 56 bit. Είναι με αυτό το γεγονός ότι η κύρια διαμάχη σχετικά με την ικανότητα να DESαντιστέκονται σε διάφορες επιθέσεις. Όπως γνωρίζετε, κάθε μπλοκ κρυπτογράφησης με ιδιωτικό κλειδί μπορεί να σπάσει δοκιμάζοντας όλους τους πιθανούς συνδυασμούς πλήκτρων. Με μήκος κλειδιού 56 bit, είναι δυνατά 2 56 διαφορετικά πλήκτρα. Εάν ένας υπολογιστής πραγματοποιήσει αναζήτηση σε 1.000.000 κλειδιά σε ένα δευτερόλεπτο (που είναι περίπου ίσο με 2 20), τότε θα χρειαστούν 2 36 δευτερόλεπτα ή λίγο περισσότερο από δύο χιλιάδες χρόνια για να αναζητήσει και τα 2 56 κλειδιά, κάτι που, φυσικά, είναι απαράδεκτο. επιτιθέμενοι.

Ωστόσο, είναι δυνατά πιο ακριβά και ταχύτερα υπολογιστικά συστήματα από ό Προσωπικός υπολογιστής. Για παράδειγμα, εάν είναι δυνατός ο συνδυασμός ενός εκατομμυρίου επεξεργαστών για παράλληλους υπολογισμούς, τότε ο μέγιστος χρόνος επιλογής κλειδιού μειώνεται σε περίπου 18 ώρες. Αυτός ο χρόνος δεν είναι πολύ μεγάλος και ένας κρυπτοαναλυτής εξοπλισμένος με τόσο ακριβό εξοπλισμό μπορεί εύκολα να σπάσει δεδομένα κρυπτογραφημένα με DES σε εύλογο χρονικό διάστημα.

Ταυτόχρονα, μπορεί να σημειωθεί ότι το σύστημα DESΜπορεί να χρησιμοποιηθεί σε εφαρμογές μικρού έως μεσαίου μεγέθους για την κρυπτογράφηση δεδομένων μικρής αξίας. Για την κρυπτογράφηση δεδομένων εθνικής σημασίας ή σημαντικής εμπορικής αξίας, το σύστημα DESδεν θα πρέπει φυσικά να χρησιμοποιείται προς το παρόν. Το 2001, μετά από έναν ειδικά προκηρυχθεί διαγωνισμό, ένα νέο πρότυπο κρυπτογράφησης μπλοκ υιοθετήθηκε στις Ηνωμένες Πολιτείες, που ονομάζεται AES (Advanced Encryption Standard), το οποίο βασίστηκε στην κρυπτογράφηση Rijndael, που αναπτύχθηκε από Βέλγους ειδικούς. Αυτός ο κρυπτογράφηση συζητείται στο τέλος της διάλεξης.

Βασικές ρυθμίσεις DES: μέγεθος μπλοκ 64 bit, μήκος κλειδιού 56 bit, αριθμός γύρων – 16. DESείναι ένα κλασικό δίκτυο Feishtel με δύο κλάδους. Ο αλγόριθμος μετατρέπει ένα μπλοκ δεδομένων εισόδου 64-bit σε ένα μπλοκ εξόδου 64-bit σε πολλούς γύρους. Πρότυπο DESβασίζεται στη συνδυασμένη χρήση μετάθεσης, αντικατάστασης και γάμμα. Τα κρυπτογραφημένα δεδομένα πρέπει να είναι σε δυαδική μορφή.

Κρυπτογράφηση

Γενική δομή DESφαίνεται στο Σχ. 4.1. Η διαδικασία κρυπτογράφησης κάθε μπλοκ 64-bit ακατέργαστων δεδομένων μπορεί να χωριστεί σε τρία στάδια:

1. αρχική προετοιμασία ενός μπλοκ δεδομένων·
2. 16 γύροι του "κύριου κύκλου"
3. τελική επεξεργασία ενός μπλοκ δεδομένων.

Στο πρώτο στάδιο πραγματοποιείται αρχική μετάθεσηΠηγαίο μπλοκ κειμένου 64 bit, κατά το οποίο τα bit αναδιατάσσονται με συγκεκριμένο τρόπο.

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

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

Ρύζι. 4.1.

Ας ρίξουμε μια πιο προσεκτική ματιά σε όλα τα στάδια της κρυπτογραφικής μετατροπής σύμφωνα με το πρότυπο DES.

Στο πρώτο στάδιο, το μπλοκ δεδομένων πηγής 64-bit υφίσταται μια αρχική μετάθεση. Στη βιβλιογραφία, αυτή η λειτουργία μερικές φορές ονομάζεται "λεύκανση". Κατά την αρχική μετάθεση, τα bit του μπλοκ δεδομένων αναδιατάσσονται με συγκεκριμένο τρόπο. Αυτή η λειτουργία προσθέτει κάποιο «χάος» στο αρχικό μήνυμα, μειώνοντας τη δυνατότητα χρήσης κρυπτανάλυσης χρησιμοποιώντας στατιστικές μεθόδους.

Ταυτόχρονα με την αρχική μετάθεση του μπλοκ δεδομένων, εκτελείται μια αρχική μετάθεση των 56 bit του κλειδιού. Από το Σχ. 4.1. Μπορεί να φανεί ότι σε κάθε έναν από τους γύρους χρησιμοποιείται το αντίστοιχο μερικό κλειδί 48-bit K i. Τα πλήκτρα K i λαμβάνονται χρησιμοποιώντας έναν συγκεκριμένο αλγόριθμο, χρησιμοποιώντας κάθε bit του αρχικού κλειδιού πολλές φορές. Σε κάθε γύρο, το κλειδί 56 bit χωρίζεται σε δύο μισά 28 bit. Τα μισά στη συνέχεια μετατοπίζονται αριστερά ένα ή δύο bit ανάλογα με τον αριθμό του κύκλου. Μετά τη μετατόπιση, τα 48 από τα 56 bit επιλέγονται με συγκεκριμένο τρόπο. Δεδομένου ότι αυτό όχι μόνο επιλέγει ένα υποσύνολο bit, αλλά αλλάζει και τη σειρά τους, αυτή η λειτουργία ονομάζεται "συμπίεση μετάθεσης". Το αποτέλεσμα είναι ένα σύνολο 48 bit. Κατά μέσο όρο, κάθε bit του αρχικού κλειδιού 56 bit χρησιμοποιείται σε 14 από τα 16 δευτερεύοντα κλειδιά, αν και δεν χρησιμοποιούνται όλα τα bit τον ίδιο αριθμό φορές.

Στη συνέχεια, εκτελείται ο κύριος κύκλος μετασχηματισμού, οργανωμένος χρησιμοποιώντας το δίκτυο Feishtel και αποτελείται από 16 πανομοιότυπους γύρους. Σε αυτή την περίπτωση, σε κάθε γύρο (Εικ. 4.2) προκύπτει μια ενδιάμεση τιμή 64-bit, η οποία στη συνέχεια υποβάλλεται σε επεξεργασία στον επόμενο γύρο.

Ρύζι. 4.2.

Ο αριστερός και ο δεξιός κλάδος κάθε ενδιάμεσης τιμής αντιμετωπίζονται ως ξεχωριστές τιμές 32-bit, που συμβολίζονται με L και R .

Πρώτον, η δεξιά πλευρά του μπλοκ R i επεκτείνεται στα 48 bit χρησιμοποιώντας έναν πίνακα που καθορίζει τη μετάθεση συν την επέκταση κατά 16 bit. Αυτή η λειτουργία ταιριάζει με το μέγεθος του δεξιού μισού με το μέγεθος του κλειδιού για την εκτέλεση μιας λειτουργίας XOR. Επιπλέον, με την εκτέλεση αυτής της λειτουργίας, η εξάρτηση όλων των bits του αποτελέσματος από τα bit των δεδομένων πηγής και του κλειδιού αυξάνεται γρηγορότερα (αυτό ονομάζεται "φαινόμενο χιονοστιβάδας"). Όσο ισχυρότερο είναι το φαινόμενο χιονοστιβάδας κατά τη χρήση ενός ή άλλου αλγόριθμου κρυπτογράφησης, τόσο το καλύτερο.

Μετά την εκτέλεση της μετάθεσης επέκτασης, η προκύπτουσα τιμή 48 bit εγγράφεται XOR με το δευτερεύον κλειδί 48 bit K i . Στη συνέχεια, η προκύπτουσα τιμή 48-bit τροφοδοτείται στην είσοδο του μπλοκ αντικατάστασης S (από τα αγγλικά. Υποκατάσταση - αντικατάσταση), αποτέλεσμαπου είναι μια τιμή 32-bit. Η αντικατάσταση εκτελείται σε οκτώ μπλοκ αντικατάστασης ή οκτώ κουτιά S. Όταν εκτελείται, το DES φαίνεται αρκετά περίπλοκο στα χαρτιά, πόσο μάλλον η εφαρμογή λογισμικού του! Αναπτύξτε ένα πρόγραμμα που λειτουργεί σωστά και βέλτιστα, πλήρως σύμφωνα με DES, πιθανώς, μόνο έμπειροι προγραμματιστές μπορούν να το κάνουν. Ορισμένες δυσκολίες προκύπτουν κατά την εφαρμογή λογισμικού, για παράδειγμα, αρχική μετάθεση ή μετάθεση με επέκταση. Αυτές οι δυσκολίες σχετίζονται με αυτό που αρχικά είχε προγραμματιστεί να εφαρμοστεί DESμόνο υλικό. Όλες οι λειτουργίες που χρησιμοποιούνται στο πρότυπο εκτελούνται εύκολα από μονάδες υλικού και δεν προκύπτουν δυσκολίες υλοποίησης. Ωστόσο, λίγο καιρό μετά τη δημοσίευση του προτύπου, οι προγραμματιστές λογισμικού αποφάσισαν να μην παραμείνουν και να αναλάβουν επίσης τη δημιουργία συστημάτων κρυπτογράφησης. Περαιτέρω DESυλοποιήθηκε τόσο σε υλικό όσο και σε λογισμικό.

• Φροντιστήριο

Γεια σας %username%!
Πολλοί άνθρωποι γνωρίζουν ότι ο αλγόριθμος DES θεωρείται από καιρό το προεπιλεγμένο πρότυπο στον τομέα της συμμετρικής κρυπτογράφησης. Η πρώτη επιτυχημένη επίθεση σε αυτόν τον ακαταμάχητο αλγόριθμο δημοσιεύτηκε το 1993, 16 χρόνια μετά την υιοθέτησή του ως πρότυπο. Η μέθοδος, την οποία ο συγγραφέας ονόμασε γραμμική κρυπτανάλυση, παρουσία 2 47 ζευγών απλού/κρυπτογραφικού κειμένου, επιτρέπει σε κάποιον να ανοίξει το μυστικό κλειδί του κρυπτογράφησης DES σε 2 43 πράξεις.
Κάτω από την περικοπή θα προσπαθήσω να περιγράψω συνοπτικά τα κύρια σημεία αυτής της επίθεσης.

Γραμμική κρυπτανάλυση

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

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

Πρώτα απ 'όλα, ο εισβολέας εξετάζει τον κρυπτογράφηση και βρίσκει το λεγόμενο στατιστικό ανάλογο, δηλ. μια εξίσωση της ακόλουθης μορφής, η οποία ισχύει με πιθανότητα P ≠ 1/2 για ένα αυθαίρετο ζεύγος κειμένου δημόσιου/ιδιωτικού και ένα σταθερό κλειδί:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib = K I1 ⊕ K I2 ⊕… ⊕ K Ic (1) ,
όπου P n, C n, K n είναι τα ν-οτά bit του κειμένου, το κρυπτογραφημένο κείμενο και το κλειδί.
Μόλις βρεθεί μια τέτοια εξίσωση, ο εισβολέας μπορεί να ανακτήσει 1 bit βασικών πληροφοριών χρησιμοποιώντας τον ακόλουθο αλγόριθμο

Αλγόριθμος 1
Έστω T ο αριθμός των κειμένων για τα οποία η αριστερή πλευρά της εξίσωσης (1) είναι ίση με 0, τότε
Αν T>N/2, όπου N είναι ο αριθμός των γνωστών απλών κειμένων.
Ας υποθέσουμε ότι K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (όταν P>1/2) ή 1 (όταν P<1/2).
Σε διαφορετική περίπτωση
Ας υποθέσουμε ότι K I1 ⊕ K I2 ⊕… ⊕ K Ic = 1 (όταν P>1/2) ή 0 (όταν P<1/2).
Είναι προφανές ότι η επιτυχία του αλγορίθμου εξαρτάται άμεσα από την τιμή του |P-1/2| και στον αριθμό των διαθέσιμων ζευγών ανοιχτού/κλειστού κειμένου N. Όσο περισσότερο η πιθανότητα P της ισότητας (1) διαφέρει από το 1/2, τόσο λιγότερος αριθμός ανοιχτών κειμένων N χρειάζεται για την επίθεση.

Υπάρχουν δύο προβλήματα που πρέπει να λυθούν για να είναι επιτυχής η επίθεση:

• Πώς να βρείτε μια αποτελεσματική εξίσωση της μορφής (1).
• Πώς να χρησιμοποιήσετε αυτήν την εξίσωση για να λάβετε περισσότερα από ένα bit πληροφοριών σχετικά με το κλειδί.

Ας εξετάσουμε τη λύση σε αυτά τα ζητήματα χρησιμοποιώντας τον κρυπτογράφηση DES ως παράδειγμα.

Περιγραφή του DES

Αλλά πρώτα, ας περιγράψουμε εν συντομία πώς λειτουργεί ο αλγόριθμος. Έχουν ήδη ειπωθεί αρκετά για το DES. Μια πλήρης περιγραφή του κρυπτογράφησης βρίσκεται στη Wikipedia. Ωστόσο, για να εξηγήσουμε περαιτέρω την επίθεση θα χρειαστούμε έναν αριθμό ορισμών που είναι καλύτερα να εισαχθούν εκ των προτέρων.

Έτσι, το DES είναι ένας κρυπτογράφησης μπλοκ που βασίζεται στο δίκτυο Feistel. Ο κρυπτογράφηση έχει μέγεθος μπλοκ 64 bit και μέγεθος κλειδιού 56 bit. Ας εξετάσουμε το σχήμα κρυπτογράφησης του αλγορίθμου DES.

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

1. Αρχική μετάθεση bit. Σε αυτό το στάδιο, τα bit του μπλοκ εισόδου ανακατεύονται με μια συγκεκριμένη σειρά.
2. Μετά από αυτό, τα μικτά bit χωρίζονται σε δύο μισά, τα οποία τροφοδοτούνται στην είσοδο της συνάρτησης Feistel. Για το τυπικό DES, το δίκτυο Feistel περιλαμβάνει 16 γύρους, αλλά υπάρχουν και άλλες παραλλαγές του αλγορίθμου.
3. Τα δύο μπλοκ που ελήφθησαν στον τελευταίο γύρο μετασχηματισμού συνδυάζονται και μια άλλη μετάθεση εκτελείται στο μπλοκ που προκύπτει.

Σε κάθε γύρο του δικτύου Feistel, τα λιγότερο σημαντικά 32 bit του μηνύματος περνούν μέσω της συνάρτησης f:

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

1. Το μπλοκ εισόδου διέρχεται από τη συνάρτηση επέκτασης Ε, η οποία μετατρέπει ένα μπλοκ 32 bit σε μπλοκ 48 bit.
2. Το μπλοκ που προκύπτει προστίθεται στο στρογγυλό κλειδί K i .
3. Το αποτέλεσμα του προηγούμενου βήματος χωρίζεται σε 8 μπλοκ των 6 bit το καθένα.
4. Κάθε ένα από τα ληφθέντα μπλοκ B i διέρχεται από τη συνάρτηση αντικατάστασης S-Box i, η οποία αντικαθιστά την ακολουθία των 6 bit με ένα μπλοκ 4 bit.
5. Το προκύπτον μπλοκ 32 bit διέρχεται μέσω της μετάθεσης P και επιστρέφεται ως αποτέλεσμα της συνάρτησης f.

Το μεγαλύτερο ενδιαφέρον για εμάς από την άποψη της κρυπτανάλυσης κρυπτογράφησης είναι τα μπλοκ S, σχεδιασμένα να κρύβουν τη σύνδεση μεταξύ των δεδομένων εισόδου και εξόδου της συνάρτησης f. Για να επιτεθούμε με επιτυχία στο DES, θα κατασκευάσουμε πρώτα στατιστικά ανάλογα για καθένα από τα S-box και στη συνέχεια θα τα επεκτείνουμε σε ολόκληρο τον κρυπτογράφηση.

Ανάλυση μπλοκ S

Κάθε S-box παίρνει μια ακολουθία 6-bit ως είσοδο και για κάθε τέτοια ακολουθία επιστρέφεται μια σταθερή τιμή 4-bit. Εκείνοι. υπάρχουν συνολικά 64 επιλογές εισόδου και εξόδου. Το καθήκον μας είναι να δείξουμε τη σχέση μεταξύ των δεδομένων εισόδου και εξόδου των μπλοκ S. Για παράδειγμα, για το τρίτο πλαίσιο S του κρυπτογράφησης DES, το 3ο bit της ακολουθίας εισόδου είναι ίσο με το 3ο bit της ακολουθίας εξόδου σε 38 από τις 64 περιπτώσεις, επομένως, βρήκαμε το ακόλουθο στατιστικό ανάλογο για το τρίτο S -κουτί:
S 3 (x) = x, το οποίο εκπληρώνεται με πιθανότητα P=38/64.
Και οι δύο πλευρές της εξίσωσης αντιπροσωπεύουν 1 bit πληροφορίας. Επομένως, εάν η αριστερή και η δεξιά πλευρά ήταν ανεξάρτητες μεταξύ τους, η εξίσωση θα έπρεπε να ικανοποιηθεί με πιθανότητα 1/2. Έτσι, μόλις δείξαμε τη σχέση μεταξύ της εισόδου και της εξόδου του 3ου S-box του αλγορίθμου DES.

Ας εξετάσουμε πώς μπορούμε να βρούμε ένα στατιστικό ανάλογο του S-box στη γενική περίπτωση.

Για ένα S-box S a , 1 ≤ α ≤ 63 και 1 ≤ β ≤ 15, η τιμή NS a (α, β) περιγράφει πόσες φορές από τα 64 πιθανά μπιτ εισόδου XOR S a που υπερτίθενται στα α bit είναι ίση με τα bit εξόδου XOR που υπερτίθενται στα bit α β, δηλαδή:
όπου το σύμβολο είναι λογικό ΚΑΙ.
Οι τιμές των α και β για τις οποίες το NS a (α, β) διαφέρει περισσότερο από το 32 περιγράφουν το πιο αποτελεσματικό στατιστικό ανάλογο του S-box S a .

Το πιο αποτελεσματικό ανάλογο βρέθηκε στο 5ο S-box του κρυπτογράφησης DES για α = 16 και β = 15 NS 5 (16, 15) = 12. Αυτό σημαίνει ότι ισχύει η ακόλουθη εξίσωση: Z=Y ⊕ Y ⊕ Y ⊕ Y, όπου Z είναι η ακολουθία εισόδου του S-box και Y είναι η ακολουθία εξόδου.
Ή λαμβάνοντας υπόψη το γεγονός ότι στον αλγόριθμο DES, πριν την είσοδο στο S-box, τα δεδομένα προστίθενται modulo 2 με ένα στρογγυλό κλειδί, π.χ. Z = X ⊕ K παίρνουμε
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, όπου X και Y είναι τα δεδομένα εισόδου και εξόδου της συνάρτησης f χωρίς να λαμβάνονται υπόψη οι μεταθέσεις.
Η εξίσωση που προκύπτει εκτελείται σε όλους τους γύρους του αλγορίθμου DES με την ίδια πιθανότητα P=12/64.
Ο παρακάτω πίνακας δείχνει μια λίστα αποτελεσματικών, δηλ. έχοντας τη μεγαλύτερη απόκλιση από το P=1/2, στατιστικά ανάλογα για κάθε s-block του αλγορίθμου DES.

Κατασκευή στατιστικών αναλόγων για πολλαπλούς γύρους DES

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

Ας χρησιμοποιήσουμε ένα αποτελεσματικό στατιστικό ανάλογο του 5ου s-box για να υπολογίσουμε ορισμένα bits της τιμής X(2).
Γνωρίζουμε ότι με πιθανότητα 12/64 η ισότητα ισχύει στη συνάρτηση f X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K,όπου το X είναι το δεύτερο bit εισόδου του 5ου S-box, είναι ουσιαστικά το 26ο bit της ακολουθίας που λαμβάνεται μετά την επέκταση των bit εισόδου. Αναλύοντας τη συνάρτηση επέκτασης, μπορούμε να διαπιστώσουμε ότι το 26ο bit αντικαθίσταται από το 17ο bit της ακολουθίας X(1).
Ομοίως, τα Y,..., Y είναι ουσιαστικά το 17ο, 18ο, 19ο και 20ο bit της ακολουθίας που ελήφθη πριν από τη μετάθεση P. Εξετάζοντας τη μετάθεση P, διαπιστώνουμε ότι τα bit Y,..., Y είναι στην πραγματικότητα bit Y (1), Υ(1), Υ(1), Υ(1).
Το bit κλειδιού K που εμπλέκεται στις εξισώσεις είναι το 26ο bit του πρώτου κύκλου δευτερεύοντος κλειδιού K1 και στη συνέχεια το στατιστικό ανάλογο παίρνει την ακόλουθη μορφή:
X(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y1 ⊕ Y(1) = K1.
Ως εκ τούτου, X(1) ⊕ K1 = Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1)(2) με πιθανότητα P=12/64.
Γνωρίζοντας 3, 8, 14, 25 bit της ακολουθίας Y(1), μπορείτε να βρείτε 3, 8, 14, 25 bit της ακολουθίας X(2):
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1)ή λαμβάνοντας υπόψη την εξίσωση (2)
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 (3) με πιθανότητα 12/64.

Ας βρούμε μια παρόμοια έκφραση χρησιμοποιώντας τον τελευταίο γύρο. Αυτή τη φορά έχουμε την εξίσωση
X(3) ⊕ K3 = Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3).
Επειδή
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
το καταλαβαίνουμε
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3(4) με πιθανότητα 12/64.

Εξισώνοντας τις δεξιές πλευρές των εξισώσεων (3) και (4) παίρνουμε
CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3 = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1με πιθανότητα (12/64) 2 +(1-12/64) 2 .
Λαμβάνοντας υπόψη το γεγονός ότι X(1) = PR και X(3) = CR λαμβάνουμε ένα στατιστικό ανάλογο
СL ⊕ CR ⊕ PL ⊕ PR = K1 ⊕ K3 (5) ,
που εκτελείται με πιθανότητα (12/64) 2 + (1-12/64) 2 =0,7.
Το στατιστικό ανάλογο που περιγράφεται παραπάνω μπορεί να αναπαρασταθεί γραφικά ως εξής (τα bit στο σχήμα αριθμούνται από δεξιά προς τα αριστερά και ξεκινούν από το μηδέν):

Όλα τα bit στην αριστερή πλευρά της εξίσωσης είναι γνωστά στον εισβολέα, επομένως μπορεί να εφαρμόσει τον Αλγόριθμο 1 και να ανακαλύψει την τιμή του K1 ⊕ K3. Ας δείξουμε πώς, χρησιμοποιώντας αυτό το στατιστικό ανάλογο, μπορείτε να ανοίξετε όχι 1, αλλά 12 bit του κλειδιού κρυπτογράφησης K.

Γνωστή επίθεση απλού κειμένου στο DES

Ας παρουσιάσουμε μια μέθοδο με την οποία μπορείτε να επεκτείνετε την επίθεση και να αποκτήσετε αμέσως 6 bit του πρώτου γύρου σύνδεσης.
Κατά τη σύνθεση της εξίσωσης (5), λάβαμε υπόψη το γεγονός ότι δεν γνωρίζουμε την τιμή του F1(PR, K1). Ως εκ τούτου, χρησιμοποιήσαμε το στατιστικό του ανάλογο K1 ⊕ PR.
Ας επιστρέψουμε την τιμή F1(PR, K1) αντί της έκφρασης K1 ⊕ PR και λάβουμε την ακόλουθη εξίσωση:
СL ⊕ CR ⊕ PL ⊕ F1(PR, K1) = K3 (6) , που θα εκτελεστεί με πιθανότητα 12/64. Η πιθανότητα άλλαξε αφού αφήσαμε μόνο το στατιστικό ανάλογο από τον τρίτο γύρο, όλες οι άλλες τιμές είναι σταθερές.

Έχουμε ήδη καθορίσει παραπάνω ότι η τιμή του F1(PR, K1) επηρεάζεται από τα bit εισόδου του 5ου S-box, δηλαδή τα μπιτ κλειδιών K1 και τα bit του μπλοκ PR. Ας δείξουμε πώς, έχοντας μόνο ένα σύνολο ανοιχτών/κλειστών κειμένων, μπορείτε να επαναφέρετε την τιμή του K1. Για να γίνει αυτό, θα χρησιμοποιήσουμε τον Αλγόριθμο 2.

Αλγόριθμος 2
Έστω N ο αριθμός των ανοιχτών/κλειστών ζευγών κειμένου που ήταν γνωστά πριν από την επίθεση. Στη συνέχεια, για να ανοίξετε το κλειδί, πρέπει να ακολουθήσετε τα παρακάτω βήματα.
Για (i=0; i<64; i++) do
{
Για(j=0; j {
αν(СL j ⊕ CR j ⊕ PL j ⊕ F1(PR j , i)=0) τότε
T i =T i +1
}
}
Ως πιθανή ακολουθία K1, λαμβάνεται μια τιμή i έτσι ώστε η έκφραση |T i -N/2| έχει τη μέγιστη τιμή.

Δεδομένου επαρκούς αριθμού γνωστών απλών κειμένων, ο αλγόριθμος θα έχει μεγάλη πιθανότητα να επιστρέψει τη σωστή τιμή των έξι bit του πρώτου κύκλου δευτερεύοντος κλειδιού K1. Αυτό εξηγείται από το γεγονός ότι εάν η μεταβλητή i δεν είναι ίση με K1, τότε η τιμή της συνάρτησης F1(PR j, K) θα είναι τυχαία και ο αριθμός των εξισώσεων για μια τέτοια τιμή του i για την οποία η αριστερή πλευρά είναι ίσο με μηδέν θα τείνει σε Ν/2. Εάν το δευτερεύον κλειδί μαντευτεί σωστά, η αριστερή πλευρά θα είναι ίση με το σταθερό bit K3 με πιθανότητα 12/64. Εκείνοι. θα υπάρχει σημαντική απόκλιση από το Ν/2.

Έχοντας λάβει 6 bit του δευτερεύοντος κλειδιού K1, μπορείτε ομοίως να ανοίξετε 6 bit του δευτερεύοντος κλειδιού K3. Το μόνο που χρειάζεται να κάνετε είναι να αντικαταστήσετε το C με το P και το K1 με το K3 στην εξίσωση (6):
PL ⊕ PR ⊕ CL ⊕ F3(CR, K3) = K1.
Ο αλγόριθμος 2 θα επιστρέψει τη σωστή τιμή K3 επειδή η διαδικασία αποκρυπτογράφησης του αλγόριθμου DES είναι πανομοιότυπη με τη διαδικασία κρυπτογράφησης, απλώς η ακολουθία κλειδιών αντιστρέφεται. Έτσι στον πρώτο γύρο αποκρυπτογράφησης χρησιμοποιείται το κλειδί K3 και στον τελευταίο γύρο χρησιμοποιείται το κλειδί K1.

Έχοντας λάβει 6 bit δευτερευόντων κλειδιών K1 και K3, ο εισβολέας ανακτά 12 bit του κοινού κλειδιού του κρυπτογράφησης K, επειδή Τα στρογγυλά πλήκτρα είναι η συνήθης μετάθεση του κλειδιού K. Ο αριθμός των απλών κειμένων που απαιτούνται για μια επιτυχημένη επίθεση εξαρτάται από την πιθανότητα του στατιστικού αναλόγου. Για να σπάσετε ένα κλειδί DES 3-στρογγυλών 12 bit, αρκούν 100 δημόσια/ιδιωτικά ζεύγη κειμένου. Για να σπάσετε 12 bit ενός κλειδιού DES 16 στρογγυλών, θα απαιτηθούν περίπου 2 44 ζεύγη κειμένων. Τα υπόλοιπα 44 bit του κλειδιού ανοίγουν χρησιμοποιώντας κανονική ωμή δύναμη.

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

Μέχρι σήμερα, ο DES είναι ο πιο κοινός αλγόριθμος που χρησιμοποιείται σε εμπορικά συστήματα ασφάλειας πληροφοριών. Επιπλέον, η εφαρμογή του αλγορίθμου DES σε τέτοια συστήματα γίνεται ένδειξη καλής μορφής.

Τα κύρια πλεονεκτήματα του αλγορίθμου DES:

· Χρησιμοποιείται μόνο ένα κλειδί με μήκος 56 bit.

· Έχοντας κρυπτογραφήσει ένα μήνυμα χρησιμοποιώντας ένα πακέτο, μπορείτε να χρησιμοποιήσετε οποιοδήποτε άλλο για να το αποκρυπτογραφήσετε.

· Η σχετική απλότητα του αλγορίθμου εξασφαλίζει υψηλή ταχύτητα επεξεργασίας πληροφοριών.

· επαρκώς υψηλή σταθερότητα του αλγορίθμου.

Το DES κρυπτογραφεί μπλοκ δεδομένων 64-bit χρησιμοποιώντας ένα κλειδί 56-bit. Η αποκρυπτογράφηση στο DES είναι η αντίστροφη λειτουργία της κρυπτογράφησης και πραγματοποιείται με την επανάληψη των πράξεων κρυπτογράφησης με αντίστροφη σειρά (παρά το προφανές, αυτό δεν γίνεται πάντα. Αργότερα θα δούμε κρυπτογράφηση στους οποίους η κρυπτογράφηση και η αποκρυπτογράφηση εκτελούνται χρησιμοποιώντας διαφορετικούς αλγόριθμους) .

Η διαδικασία κρυπτογράφησης αποτελείται από μια αρχική μετάθεση των bit ενός μπλοκ 64-bit, δεκαέξι κύκλους κρυπτογράφησης και, τέλος, μια αντίστροφη μετάθεση bit (Εικόνα 1).

Θα πρέπει αμέσως να σημειωθεί ότι ΟΛΟΙ οι πίνακες που δίνονται σε αυτό το άρθρο είναι ΠΡΟΤΥΠΟΙ και επομένως θα πρέπει να συμπεριληφθούν στην εφαρμογή του αλγόριθμου χωρίς αλλαγές. Όλες οι μεταθέσεις και οι κωδικοί στους πίνακες επιλέγονται από τους προγραμματιστές με τέτοιο τρόπο ώστε η διαδικασία αποκρυπτογράφησης να γίνεται όσο το δυνατόν πιο δύσκολη επιλέγοντας ένα κλειδί. Η δομή του αλγορίθμου DES φαίνεται στο Σχ. 2.

Ρύζι. 2.

Αφήστε το επόμενο μπλοκ T 8 byte να διαβαστεί από το αρχείο, το οποίο μετασχηματίζεται χρησιμοποιώντας την αρχική μήτρα μετάθεσης IP (Πίνακας 1) ως εξής: το bit 58 του μπλοκ T γίνεται bit 1, το bit 50 γίνεται bit 2, κ.λπ. έχει ως αποτέλεσμα : T(0) = IP(T).

Η προκύπτουσα ακολουθία δυαδικών ψηφίων T(0) χωρίζεται σε δύο ακολουθίες των 32 bit η καθεμία: L(0) - αριστερά ή bit υψηλής τάξης, R(0) - δεξιά ή bit χαμηλής τάξης.

Πίνακας 1: Πίνακας αρχικής μετάθεσης IP

58 50 42 34 26 18 10 02

60 52 44 36 28 20 12 04

62 54 46 38 30 22 14 06

64 56 48 40 32 24 16 08

57 49 41 33 25 17 09 01

59 51 43 35 27 19 11 03

61 53 45 37 29 21 13 05

63 55 47 39 31 23 15 07

Στη συνέχεια πραγματοποιείται κρυπτογράφηση, που αποτελείται από 16 επαναλήψεις. Το αποτέλεσμα της i-ης επανάληψης περιγράφεται με τους ακόλουθους τύπους:

R(i) = L (i-1) xor f (R(i-1), K(i)),

όπου xor είναι η λειτουργία ΑΠΟΚΛΕΙΣΤΙΚΟ Ή.

Η συνάρτηση f ονομάζεται συνάρτηση κρυπτογράφησης. Τα ορίσματά του είναι η ακολουθία 32 bit R(i-1), που λήφθηκε κατά την επανάληψη (i-1) και το κλειδί 48 bit K(i), το οποίο είναι το αποτέλεσμα της μετατροπής του κλειδιού 64 bit K. Αναλυτικά, η συνάρτηση κρυπτογράφησης και ο αλγόριθμος για τη λήψη των κλειδιών K(i) περιγράφονται παρακάτω.

Στη 16η επανάληψη, λαμβάνονται οι αλληλουχίες R(16) και L(16) (χωρίς μετάθεση), οι οποίες συνενώνονται σε μια ακολουθία 64-bit R(16) L(16).

Στη συνέχεια, οι θέσεις bit αυτής της ακολουθίας αναδιατάσσονται σύμφωνα με τον πίνακα IP -1 (Πίνακας 2).

Πίνακας 2: Πίνακας αντίστροφης μετάθεσης IP -1

40 08 48 16 56 24 64 32

39 07 47 15 55 23 63 31

38 06 46 14 54 22 62 30

37 05 45 13 53 21 61 29

36 04 44 12 52 20 60 28

35 03 43 11 51 19 59 27

34 02 42 10 50 18 58 26

33 01 41 09 49 17 57 25

Οι πίνακες IP -1 και IP σχετίζονται ως εξής: η τιμή του 1ου στοιχείου του πίνακα IP -1 είναι 40 και η τιμή του 40ου στοιχείου του πίνακα IP είναι 1, η τιμή του 2ου Το στοιχείο του πίνακα IP -1 είναι 8 και η τιμή του 8ου στοιχείου πίνακα IP είναι ίση με 2, κ.λπ.

Η διαδικασία αποκρυπτογράφησης δεδομένων είναι αντίστροφη από τη διαδικασία κρυπτογράφησης. Όλα τα βήματα πρέπει να εκτελούνται με αντίστροφη σειρά. Αυτό σημαίνει ότι τα αποκρυπτογραφημένα δεδομένα αναδιατάσσονται πρώτα σύμφωνα με τη μήτρα IP-1 και στη συνέχεια εκτελούνται οι ίδιες ενέργειες στην ακολουθία των bits R(16) L(16) όπως στη διαδικασία κρυπτογράφησης, αλλά με αντίστροφη σειρά.

Η επαναληπτική διαδικασία αποκρυπτογράφησης μπορεί να περιγραφεί με τους ακόλουθους τύπους:

R (i-1) = L(i), i = 1, 2,…, 16;

L (i-1) = R(i) xor f (L(i), K(i)), i = 1, 2,…, 16.

Στη 16η επανάληψη, λαμβάνονται οι αλληλουχίες L(0) και R(0), οι οποίες συνδέονται σε μια ακολουθία 64-bit L(0) R(0).

Στη συνέχεια, οι θέσεις bit αυτής της ακολουθίας αναδιατάσσονται σύμφωνα με τον πίνακα IP. Το αποτέλεσμα μιας τέτοιας μετάθεσης είναι η αρχική ακολουθία 64-bit.

Τώρα εξετάστε τη συνάρτηση κρυπτογράφησης f (R(i-1), K(i)). Φαίνεται σχηματικά στο Σχ. 3.

Ρύζι. 3.

Για τον υπολογισμό της τιμής της συνάρτησης f, χρησιμοποιούνται οι ακόλουθες συναρτήσεις πίνακα:

E - επέκταση μιας ακολουθίας 32-bit σε 48-bit,

S1, S2,…, S8 - μετατροπή μπλοκ 6 bit σε 4 bit,

P - μετάθεση bit σε ακολουθία 32 bit.

Η συνάρτηση επέκτασης Ε καθορίζεται από τον πίνακα. 3. Σύμφωνα με αυτόν τον πίνακα, τα πρώτα 3 bit του E (R(i-1)) είναι τα bit 32, 1 και 2 και τα τελευταία είναι τα 31, 32 και 1.

Πίνακας 3: Συνάρτηση επέκτασης Ε

32 01 02 03 04 05

04 05 06 07 08 09

08 09 10 11 12 13

12 13 14 15 16 17

16 17 18 19 20 21

20 21 22 23 24 25

24 25 26 27 28 29

28 29 30 31 32 01

Το αποτέλεσμα της συνάρτησης Ε (R(i-1)) είναι μια ακολουθία 48 bit που προστίθεται modulo 2 (λειτουργία xor) με το κλειδί 48 bit K(i). Η προκύπτουσα ακολουθία 48 bit χωρίζεται σε οκτώ μπλοκ 6 bit B(1) B(2) B(3) B(4) B(5) B(6) B(7) B(8). Αυτό είναι:

E (R(i-1)) xor K(i) = B(1) B(2)… B(8).

Οι συναρτήσεις S1, S2,…, S8 ορίζονται στον πίνακα. 4.

Πίνακας 4

Στο τραπέζι 4. Απαιτείται πρόσθετη διευκρίνιση. Έστω ότι η είσοδος της συνάρτησης μήτρας Sj είναι ένα μπλοκ 6 bit B(j) = b1b2b3b4b5b6, τότε ο αριθμός δύο bit b1b6 υποδεικνύει τον αριθμό σειράς του πίνακα και b2b3b4b5 τον αριθμό της στήλης. Το αποτέλεσμα του Sj (B(j)) θα είναι ένα στοιχείο 4-bit που βρίσκεται στη διασταύρωση της καθορισμένης γραμμής και στήλης.

Για παράδειγμα, B(1)=011011. Τότε το S1 (B(1)) βρίσκεται στην τομή της σειράς 1 και της στήλης 13. Στη στήλη 13 της σειράς 1 η τιμή είναι 5. Αυτό σημαίνει S1 (011011)=0101.

Εφαρμόζοντας τη λειτουργία επιλογής σε καθένα από τα μπλοκ 6 bit B(1), B(2),…, B(8), λαμβάνουμε μια ακολουθία 32 bit S1 (B(1)) S2 (B(2)) S3 (B( 3))... S8 (B(8)).

Τέλος, για να ληφθεί το αποτέλεσμα της συνάρτησης κρυπτογράφησης, τα bit αυτής της ακολουθίας πρέπει να αναδιαταχθούν. Για το σκοπό αυτό χρησιμοποιείται η συνάρτηση μετάθεσης P (Πίνακας 5). Στην ακολουθία εισόδου, τα bit αναδιατάσσονται έτσι ώστε το bit 16 να γίνεται bit 1, το bit 7 να γίνεται bit 2 και ούτω καθεξής.

Πίνακας 5: Συνάρτηση μετάθεσης P

Ετσι,

f (R(i-1), K(i)) = P (S1 (B(1)),… S8 (B(8)))

Για να ολοκληρωθεί η περιγραφή του αλγόριθμου κρυπτογράφησης δεδομένων, μένει να παρουσιαστεί ο αλγόριθμος για τη λήψη κλειδιών 48-bit K(i), i=1...16. Σε κάθε επανάληψη, χρησιμοποιείται μια νέα τιμή κλειδιού K(i), η οποία υπολογίζεται από το αρχικό κλειδί K. Το K είναι ένα μπλοκ 64-bit με οκτώ bit ισοτιμίας που βρίσκονται στις θέσεις 8,16,24,32,40,48, 56. 64.

Για να αφαιρέσετε τα bits ελέγχου και να αναδιατάξετε τα υπόλοιπα, χρησιμοποιείται η συνάρτηση G της αρχικής προετοιμασίας κλειδιού (Πίνακας 6).

Πίνακας 6

Πίνακας G αρχικής προετοιμασίας κλειδιού

57 49 41 33 25 17 09

01 58 50 42 34 26 18

10 02 59 51 43 35 27

19 11 03 60 52 44 36

63 55 47 39 31 23 15

07 62 54 46 38 30 22

14 06 61 53 45 37 29

21 13 05 28 20 12 04

Το αποτέλεσμα του μετασχηματισμού G(K) χωρίζεται σε δύο μπλοκ 28-bit C(0) και D(0), και το C(0) θα αποτελείται από τα bit 57, 49, ..., 44, 36 του κλειδιού Τα K και D(0) θα αποτελούνται από bit 63, 55,…, 12, 4 πλήκτρα K. Μετά τον προσδιορισμό των C(0) και D(0), C(i) και D(i), i=1… 16, καθορίζονται αναδρομικά. Για να το κάνετε αυτό, εφαρμόστε μια κυκλική μετατόπιση προς τα αριστερά κατά ένα ή δύο bit, ανάλογα με τον αριθμό επανάληψης, όπως φαίνεται στον πίνακα. 7.

Πίνακας 7. Μετατόπιση πίνακα για υπολογισμό κλειδιού

Αριθμός επανάληψης	Shift (bits)

Η τιμή που προκύπτει "αναμιγνύεται" και πάλι σύμφωνα με τον πίνακα H (Πίνακας 8).

Πίνακας 8: Πίνακας ολοκλήρωσης κλειδιού H

14 17 11 24 01 05

03 28 15 06 21 10

23 19 12 04 26 08

16 07 27 20 13 02

41 52 31 37 47 55

30 40 51 45 33 48

44 49 39 56 34 53

46 42 50 36 29 32

Το κλειδί K(i) θα αποτελείται από τα bit 14, 17,…, 29, 32 της ακολουθίας C(i) D(i). Ετσι:

K(i) = H (C(i) D(i))

Το μπλοκ διάγραμμα του αλγόριθμου υπολογισμού κλειδιού φαίνεται στο Σχ. 4.

Ρύζι. 4.

Η επαναφορά του αρχικού κειμένου πραγματοποιείται χρησιμοποιώντας αυτόν τον αλγόριθμο, αλλά πρώτα χρησιμοποιείτε το πλήκτρο K(15), μετά K(14) και ούτω καθεξής. Τώρα θα πρέπει να καταλάβετε γιατί ο συγγραφέας συνιστά επίμονα τη χρήση των δεδομένων πινάκων. Εάν κάνετε απατεώνες, μπορεί να καταλήξετε με έναν πολύ μυστικό κωδικό, αλλά δεν θα μπορείτε να τον σπάσετε μόνοι σας!

συμμετρικά πλήκτρα.

Η προτεινόμενη τροποποίηση του έργου από την IBM, που ονομάζεται Lucifer, υιοθετήθηκε ως DES. Οι DES δημοσιεύτηκαν σε προσχέδιο στο Ομοσπονδιακό Μητρώοτον Μάρτιο του 1975 ως Ομοσπονδιακό Πρότυπο Επεξεργασίας Πληροφοριών (FIPS – Ομοσπονδιακό Πρότυπο Επεξεργασίας Πληροφοριών).

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

Υποψιάζονταν ότι κάποιο μέρος της δομής (S-boxes) μπορεί να έχει μια κρυφή κερκόπορτα που θα επέτρεπε την αποκρυπτογράφηση των μηνυμάτων χωρίς το κλειδί. Οι σχεδιαστές της IBM ανέφεραν στη συνέχεια ότι η εσωτερική δομή είχε τροποποιηθεί για να αποτραπεί η κρυπτανάλυση.

Το DES τελικά δημοσιεύτηκε ως FIPS 46 στο Federal Register τον Ιανουάριο του 1977. Ωστόσο, το FIPS έχει δηλώσει το DES ως πρότυπο για χρήση σε ανεπίσημες εφαρμογές. Το DES ήταν το πιο ευρέως χρησιμοποιούμενο μπλοκ κρυπτογράφησης συμμετρικά πλήκτρα, ξεκινώντας από τη δημοσίευσή του. Το NIST πρότεινε αργότερα ένα νέο πρότυπο (FIPS 46-3) που συνιστά τη χρήση τριπλού DES (τριπλού κρυπτογράφησης DES) για μελλοντικές εφαρμογές. Όπως θα δούμε αργότερα στις διαλέξεις 9-10, το νεότερο πρότυπο AES αναμένεται να αντικαταστήσει το DES.

Γενικές προμήθειες

Όπως φαίνεται στο Σχ. 8.1. DES - κρυπτογράφηση μπλοκ.

Ρύζι. 8.1.

Από την πλευρά της κρυπτογράφησης, το DES παίρνει απλό κείμενο 64 bit και παράγει κρυπτογραφημένο κείμενο 64 bit. Από την πλευρά της αποκρυπτογράφησης, το DES παίρνει ένα κρυπτογραφημένο κείμενο 64 bit και παράγει ένα απλό κείμενο 64 bit. Και οι δύο πλευρές χρησιμοποιούν το ίδιο κλειδί 56-bit για κρυπτογράφηση και αποκρυπτογράφηση.

8.2. Δομή DES

Ας δούμε πρώτα την κρυπτογράφηση και μετά την αποκρυπτογράφηση. Η διαδικασία κρυπτογράφησης αποτελείται από δύο μεταθέσεις (P-blocks) - που ονομάζονται μεταθέσεις έναρξης και λήξης - και δεκαέξι γύρους Feistel. Κάθε γύρος χρησιμοποιεί ένα διαφορετικό κλειδί 48-bit που δημιουργείται. Ο αλγόριθμος παραγωγής θα συζητηθεί αργότερα σε αυτή τη διάλεξη. Το σχήμα 8.2 δείχνει τα στοιχεία ενός κρυπτογράφησης DES στην πλευρά της κρυπτογράφησης.

Μεταθέσεις έναρξης και λήξης

Το σχήμα 8.3 δείχνει τις αρχικές και τελικές μεταθέσεις (P-blocks). Κάθε μια από τις μεταθέσεις παίρνει μια είσοδο 64-bit και αναδιατάσσει τα στοιχεία της σύμφωνα με έναν δεδομένο κανόνα. Έχουμε δείξει μόνο έναν μικρό αριθμό θυρών εισόδου και αντίστοιχων θυρών εξόδου. Αυτές οι μεταθέσεις είναι άμεσες μεταθέσεις χωρίς κλειδιά, οι οποίες είναι αντίστροφες μεταξύ τους. Για παράδειγμα, στην αρχική μετάθεση, το 58ο bit της εισόδου πηγαίνει στο πρώτο bit της εξόδου. Ομοίως, στην τελική μετάθεση, το πρώτο bit εισόδου πηγαίνει στο 58ο bit εξόδου. Με άλλα λόγια, εάν δεν υπάρχει γύρος μεταξύ αυτών των δύο μεταθέσεων, το 58ο bit που παρέχεται στην είσοδο της αρχικής συσκευής μετάθεσης θα παραδοθεί στην 58η έξοδο από την τελική μετάθεση.

Ρύζι. 8.2.

Ρύζι. 8.3.

Οι κανόνες μετάθεσης για αυτό το πλαίσιο P φαίνονται στον Πίνακα 8.1. Ο πίνακας μπορεί να αναπαρασταθεί ως πίνακας 64 στοιχείων. Σημειώστε ότι συζητήσαμε την εργασία με τον πίνακα, η τιμή κάθε στοιχείου καθορίζει τον αριθμό της θύρας εισόδου και ο σειριακός αριθμός (ευρετήριο) του στοιχείου καθορίζει τον αριθμό της θύρας εξόδου.

Πίνακας 8.1. Πίνακας αρχικών και τελικών μεταθέσεων

Αρχικές μεταθέσεις								Πεπερασμένες μεταθέσεις
58	50	42	34	26	18	10	02	40	08	48	16	56	24	64	32
60	52	44	36	28	20	12	04	39	07	47	15	55	23	63	31
62	54	46	38	30	22	14	06	38	06	46	14	54	22	62	30
64	56	48	40	32	24	16	08	37	05	45	13	53	21	61	29
57	49	41	33	25	17	09	01	36	04	44	12	52	20	60	28
59	51	43	35	27	19	11	03	35	03	43	11	51	19	59	27
61	53	45	37	29	21	13	05	34	02	42	10	50	18	58	26
63	55	47	39	31	23	15	07	33	01	41	09	49	17	57	25

Αυτές οι δύο μεταθέσεις δεν έχουν καμία σημασία για την κρυπτογραφία