Πρότυπο κρυπτογράφησης εγχώριων δεδομένων. Πρότυπο κρυπτογράφησης εγχώριων δεδομένων Αλγόριθμος κρυπτογραφικής μετατροπής GOST 28147 89

Σύντομη περιγραφή της κρυπτογράφησης

GOST 28147-89 - Σοβιετικό και ρωσικό πρότυπο για συμμετρική κρυπτογράφηση, που εισήχθη το 1990, είναι επίσης ένα πρότυπο CIS. Πλήρες όνομα - "GOST 28147-89 Συστήματα επεξεργασίας πληροφοριών. Κρυπτογραφική προστασία. Αλγόριθμος Κρυπτογραφικού Μετασχηματισμού». Αλγόριθμος κρυπτογράφησης μπλοκ. Όταν χρησιμοποιείται η μέθοδος κρυπτογράφησης με γάμμα, μπορεί να εκτελέσει τις λειτουργίες ενός αλγορίθμου κρυπτογράφησης ροής.

Το GOST 28147-89 είναι ένας κρυπτογράφηση μπλοκ με κλειδί 256 bit και 32 κύκλους μετατροπής, που λειτουργεί με μπλοκ 64 bit. Η βάση του αλγορίθμου κρυπτογράφησης είναι το δίκτυο Feistel. Η βασική λειτουργία κρυπτογράφησης σύμφωνα με το GOST 28147-89 είναι η απλή λειτουργία αντικατάστασης (καθορίζονται επίσης πιο περίπλοκες λειτουργίες - γάμμα, γάμμα με ανατροφοδότησηκαι προσομοιωμένη λειτουργία εισαγωγής).

Πώς λειτουργεί ο αλγόριθμος

Ο αλγόριθμος δεν διαφέρει θεμελιωδώς από τον DES. Περιέχει επίσης κύκλους κρυπτογράφησης (υπάρχουν 32 από αυτούς) σύμφωνα με το σχήμα Feistel (Εικ. 2.9.).

Ρύζι. 2.9. Γύροι κρυπτογράφησης του αλγορίθμου GOST 28147-89.

Για τη δημιουργία δευτερευόντων κλειδιών, το αρχικό κλειδί 256 bit χωρίζεται σε οκτώ μπλοκ 32 bit: k 1 …k 8 . Τα πλήκτρα k 9 ... k 24 είναι μια κυκλική επανάληψη των πλήκτρων k 1 ... k 8 (αριθμημένα από τα λιγότερο σημαντικά bits στα πιο σημαντικά). Τα πλήκτρα k 25 ...k 32 είναι τα πλήκτρα k 1 ...k 8 με αντίστροφη σειρά.

Αφού ολοκληρωθούν και οι 32 γύροι του αλγορίθμου, τα μπλοκ A 33 και B 33 είναι κολλημένα μεταξύ τους (σημειώστε ότι το A 33 γίνεται το πιο σημαντικό bit και το B 33 γίνεται το λιγότερο σημαντικό bit) - το αποτέλεσμα είναι το αποτέλεσμα του αλγορίθμου.

Λειτουργία φά(ΕΝΑ Εγώ ,κ Εγώ) υπολογίζεται ως εξής: A i και K i προστίθενται modulo 2 32 , μετά το αποτέλεσμα χωρίζεται σε οκτώ υποακολουθίες 4 bit, καθεμία από τις οποίες τροφοδοτείται στην είσοδο της δικής της κόμβος πίνακα αντικατάστασης(με αύξουσα σειρά προτεραιότητας bit), καλείται παρακάτω S-block. Ο συνολικός αριθμός των μπλοκ GOST S είναι οκτώ, δηλαδή ο ίδιος με τον αριθμό των υποακολουθιών. Κάθε S-blockαντιπροσωπεύει μια μετάθεση αριθμών από το 0 έως το 15. Η πρώτη υποακολουθία 4-bit πέφτει στην είσοδο του πρώτου S-box, η δεύτερη - στην είσοδο του δεύτερου, κ.λπ. Οι έξοδοι και των οκτώ S-box συνδυάζονται σε μια λέξη 32 bit, τότε ολόκληρη η λέξη μετατοπίζεται κυκλικά προς τα αριστερά (στα πιο σημαντικά bit) κατά 11 bit. Και τα οκτώ S-box μπορεί να είναι διαφορετικά. Στην πραγματικότητα, μπορεί να είναι πρόσθετο βασικό υλικό, αλλά πιο συχνά είναι μια παράμετρος σχήματος που είναι κοινή σε μια συγκεκριμένη ομάδα χρηστών. Το κείμενο του προτύπου υποδεικνύει ότι η παράδοση της πλήρωσης των μονάδων αντικατάστασης (S-blocks) πραγματοποιείται με τον προβλεπόμενο τρόπο, δηλ. προγραμματιστής αλγορίθμων. Η κοινότητα των Ρώσων προγραμματιστών CIPF συμφώνησε για τους κόμβους αντικατάστασης που χρησιμοποιούνται στο Διαδίκτυο.

Η αποκρυπτογράφηση εκτελείται με τον ίδιο τρόπο όπως η κρυπτογράφηση, αλλά η σειρά των δευτερευόντων κλειδιών k i αντιστρέφεται.

Τρόποι λειτουργίας του αλγορίθμου GOST 28147-89

Ο αλγόριθμος GOST 28147-89 έχει τέσσερις τρόπους λειτουργίας.

1. Τρόποςαπλή αντικατάστασηδέχεται δεδομένα ως είσοδο, το μέγεθος των οποίων είναι πολλαπλάσιο των 64 bit. Το αποτέλεσμα της κρυπτογράφησης είναι το κείμενο εισόδου, που μετατρέπεται σε μπλοκ των 64 bit στην περίπτωση κρυπτογράφησης με τον κύκλο "32-3" και στην περίπτωση αποκρυπτογράφησης - με τον κύκλο "32-P".

2. Τρόποςαπολέπισηδέχεται δεδομένα οποιουδήποτε μεγέθους ως είσοδο, καθώς και μια πρόσθετη παράμετρο 64 bit - μήνυμα συγχρονισμού. Κατά τη λειτουργία, το μήνυμα συγχρονισμού μετατρέπεται στον κύκλο "32-Z", το αποτέλεσμα χωρίζεται σε δύο μέρη. Στο πρώτο μέρος προστίθεται modulo 2 32 με σταθερή τιμή 1010101 16 . Εάν το δεύτερο μέρος είναι ίσο με 2 32 -1, τότε η τιμή του δεν αλλάζει, διαφορετικά προστίθεται modulo 2 32 -1 με σταθερή τιμή 1010104 16 . Η τιμή που λαμβάνεται με το συνδυασμό και των δύο τμημάτων που έχουν μετατραπεί, που ονομάζεται γάμμα κρυπτογράφησης, εισέρχεται στον βρόχο "32-3", το αποτέλεσμά της προστίθεται κατά bit modulo 2 με ένα μπλοκ δεδομένων εισόδου 64 bit. Εάν το τελευταίο είναι μικρότερο από 64 bit, τότε τα επιπλέον bit της λαμβανόμενης τιμής απορρίπτονται. Η τιμή που προκύπτει αποστέλλεται στην έξοδο. Εάν εξακολουθούν να υπάρχουν εισερχόμενα δεδομένα, τότε η ενέργεια επαναλαμβάνεται: το μπλοκ που αποτελείται από τμήματα 32 bit μετατρέπεται σε μέρη κ.ο.κ.

3. Τρόποςκλιμάκωση με ανατροφοδότησηδέχεται επίσης δεδομένα οποιουδήποτε μεγέθους και ένα μήνυμα συγχρονισμού ως είσοδο. Το μπλοκ δεδομένων εισόδου προστίθεται κατά bit modulo 2 με το αποτέλεσμα του μετασχηματισμού στον κύκλο "32-3" του μηνύματος συγχρονισμού. Η τιμή που προκύπτει αποστέλλεται στην έξοδο. Η τιμή του μηνύματος συγχρονισμού αντικαθίσταται στην περίπτωση κρυπτογράφησης από το μπλοκ εξόδου και στην περίπτωση αποκρυπτογράφησης - από την είσοδο, δηλαδή κρυπτογραφημένη. Εάν το τελευταίο μπλοκ εισερχόμενων δεδομένων είναι μικρότερο από 64 bit, τότε τα επιπλέον bit του γάμμα (έξοδος του βρόχου "32-3") απορρίπτονται. Εάν εξακολουθούν να υπάρχουν εισερχόμενα δεδομένα, τότε η ενέργεια επαναλαμβάνεται: ο κρυπτογράφηση γάμμα σχηματίζεται από το αποτέλεσμα της κρυπτογράφησης της αντικατασταθείσας τιμής και ούτω καθεξής.

4. Τρόπος παραγωγήςαπομίμηση ένθεταλαμβάνει δεδομένα εισόδου που έχουν μέγεθος τουλάχιστον δύο ολόκληρα μπλοκ 64 bit και επιστρέφει ένα μπλοκ δεδομένων 64 bit, που ονομάζεται πλαστοπροσωπία εισαγωγής. Η προσωρινή τιμή των 64 bit ορίζεται στο 0, στη συνέχεια, ενώ υπάρχουν δεδομένα εισόδου, προστίθεται κατά bit modulo 2 με αποτέλεσμα την εκτέλεση του κύκλου "16-3", η είσοδος του οποίου είναι το μπλοκ δεδομένων εισόδου . Μετά το τέλος της εισαγωγής, η προσωρινή τιμή επιστρέφεται ως αποτέλεσμα.

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

Η κρυπτογράφηση GOST 28147-89 χρησιμοποιεί ένα κλειδί 256 bit και το μέγεθος του χώρου κλειδιού είναι 2256 . Κανένας υπολογιστής γενικής χρήσης που υπάρχει αυτή τη στιγμή δεν μπορεί να μαντέψει ένα κλειδί σε λιγότερο από πολλές εκατοντάδες χρόνια. Το ρωσικό πρότυπο GOST 28147-89 σχεδιάστηκε με μεγάλο περιθώριο και υπερβαίνει το αμερικανικό πρότυπο DES κατά πολλές τάξεις μεγέθους με το πραγματικό μέγεθος κλειδιού του 56 bit και τον όγκο του χώρου πλήκτρων μόνο 2 56 .

Υπάρχουν επίσης επιθέσεις στο πλήρες GOST 28147-89 χωρίς καμία τροποποίηση. Ενας από τους πρώτους ανοιχτά έργα, στο οποίο πραγματοποιήθηκε η ανάλυση του αλγορίθμου, χρησιμοποιεί τις αδυναμίες της διαδικασίας επέκτασης κλειδιού ενός αριθμού γνωστών αλγορίθμων κρυπτογράφησης. Συγκεκριμένα, ο πλήρης αλγόριθμος GOST 28147-89 μπορεί να σπάσει χρησιμοποιώντας διαφορική κρυπτανάλυση σε συνδεδεμένα κλειδιά, αλλά μόνο εάν χρησιμοποιούνται πίνακες ασθενούς αντικατάστασης. Η έκδοση 24 γύρων του αλγορίθμου (η οποία δεν έχει τους πρώτους 8 γύρους) ανοίγει με τον ίδιο τρόπο για όλους τους πίνακες αντικατάστασης, ωστόσο, οι ισχυροί πίνακες αντικατάστασης καθιστούν μια τέτοια επίθεση εντελώς ανέφικτη.

Οι εγχώριοι επιστήμονες A.G. Rostovtsev και E.B. Ο Makhovenko το 2001 πρότεινε μια θεμελιωδώς νέα μέθοδο κρυπτανάλυσης σχηματίζοντας μια αντικειμενική συνάρτηση από ένα γνωστό απλό κείμενο, το κρυπτογραφημένο κείμενο που αντιστοιχεί σε αυτό και την επιθυμητή τιμή κλειδιού και βρίσκοντας το άκρο του που αντιστοιχεί στην πραγματική τιμή του κλειδιού. Βρήκαν επίσης μια μεγάλη κατηγορία αδύναμων πλήκτρων του αλγόριθμου GOST 28147-89, τα οποία σας επιτρέπουν να ανοίξετε τον αλγόριθμο χρησιμοποιώντας μόνο 4 επιλεγμένα απλά κείμενα και τα αντίστοιχα κρυπτογραφημένα κείμενα με αρκετά χαμηλή πολυπλοκότητα.

Το 2004, μια ομάδα ειδικών από την Κορέα πρότεινε μια επίθεση με την οποία, χρησιμοποιώντας διαφορική κρυπτανάλυση σε συσχετισμένα κλειδιά, είναι δυνατό να αποκτηθεί ένα μυστικό κλειδί 12 bit με πιθανότητα 91,7%. Η επίθεση απαιτεί 235 επιλεγμένα απλά κείμενα και 236 λειτουργίες κρυπτογράφησης. Όπως μπορείτε να δείτε, αυτή η επίθεση είναι πρακτικά άχρηστη για το πραγματικό άνοιγμα του αλγορίθμου.

Ο πίνακας αντικατάστασης είναι μακροπρόθεσμο βασικό στοιχείο, ισχύει δηλαδή για πολλά περισσότερα μακροπρόθεσμαπαρά ένα μόνο κλειδί. Υποτίθεται ότι είναι κοινό για όλους τους κόμβους κρυπτογράφησης σε ένα σύστημα κρυπτογραφικής προστασίας. Η ποιότητα αυτού του πίνακα καθορίζει την ποιότητα της κρυπτογράφησης. Με έναν "ισχυρό" πίνακα αντικατάστασης, η ισχύς του κρυπτογράφησης δεν πέφτει κάτω από ένα ορισμένο αποδεκτό όριο, ακόμη και αν αποκαλυφθεί. Αντίθετα, η χρήση ενός "αδύναμου" πίνακα μπορεί να μειώσει την ισχύ του κρυπτογράφησης σε ένα απαράδεκτα χαμηλό όριο. Δεν υπάρχουν πληροφορίες για την ποιότητα του πίνακα των αλλαγών ανοιχτή σφραγίδαΗ Ρωσία δεν έχει δημοσιευτεί, αλλά η ύπαρξη «αδύναμων» πινάκων είναι αναμφισβήτητη - παράδειγμα είναι ο «τετριμμένος» πίνακας αντικατάστασης, σύμφωνα με τον οποίο κάθε τιμή αντικαθίσταται από μόνη της. Σε μια σειρά εργασιών, συνάγεται λανθασμένα το συμπέρασμα ότι οι πίνακες μυστικής αντικατάστασης του αλγόριθμου GOST 28147-89 μπορούν να αποτελούν μέρος του κλειδιού και να αυξήσουν το πραγματικό μήκος του (το οποίο δεν είναι σημαντικό, καθώς ο αλγόριθμος έχει ένα πολύ μεγάλο κλειδί 256-bit ).

Αλγόριθμος κρυπτογράφησης GOST 28147-89. Απλή μέθοδος αντικατάστασης. — Αρχείο WASM.RU

«Όσο είσαι ζωντανός, μην πεθάνεις, κοίτα αυτόν τον κόσμο.
Πολλοί εδώ έχουν νεκρή ψυχή - είναι νεκροί μέσα τους.
Αλλά περπατούν και γελούν, χωρίς να ξέρουν ότι δεν είναι εκεί,
Μη βιάζεσαι τον θάνατό σου», μου είπε.

Άρια, "Εκεί πάνω"

2.1 Δίκτυα Feistel.
2.2 Κρυπτογράφηση μπλοκ GOST 28147-89

3.1 Πληροφορία κλειδί
3.2 Το κύριο βήμα του μετασχηματισμού κρυπτογράφησης

3.3 Βασικοί κύκλοι:“ 32-З” , “ 32-R” .

4.1 Υλοποίηση του κύριου βήματος του μετασχηματισμού κρυπτογράφησης
4.2 Αύξηση της ταχύτητας του αλγορίθμου
5. Απαιτήσεις βασικών πληροφοριών
6. Κατάλογος χρησιμοποιημένης βιβλιογραφίας
7. Ευχαριστώ.

Εισαγωγή.

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

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

Εισαγωγή στους κωδικούς μπλοκ.

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

Η ιστορία της ανάπτυξης των μπλοκ κρυπτογράφησης συνδέεται με τις αρχές της δεκαετίας του '70, όταν η IBM, συνειδητοποιώντας την ανάγκη προστασίας πληροφοριών κατά τη μετάδοση δεδομένων μέσω καναλιών επικοινωνίας υπολογιστή, άρχισε να εφαρμόζει δικό του πρόγραμμα επιστημονική έρευνααφιερωμένο στην προστασία των πληροφοριών σε ηλεκτρονικά δίκτυα, συμπεριλαμβανομένης της κρυπτογραφίας.

Μια ομάδα ερευνητών - προγραμματιστών της εταιρείας IBM, η οποία άρχισε να μελετά συστήματα κρυπτογράφησης με σχήμα συμμετρικού κλειδιού, είχε επικεφαλής τον Δρ. Χορστ Φάιστελ.

2.1 Δίκτυα Feistel

Η αρχιτεκτονική της νέας μεθόδου κρυπτογράφησης που προτάθηκε από τον Feistel στην κλασική βιβλιογραφία ονομάστηκε "Feistel Architecture", αλλά αυτή τη στιγμήστη ρωσική και ξένη βιβλιογραφία, χρησιμοποιείται ένας πιο καθιερωμένος όρος - "δίκτυο Feistel" ή NetWork του Feistel. Ακολούθως, σύμφωνα με αυτή την αρχιτεκτονική, κατασκευάστηκε ο κρυπτογράφηση «Lucifer» - ο οποίος δημοσιεύτηκε αργότερα και προκάλεσε ένα νέο κύμα ενδιαφέροντος για την κρυπτογραφία γενικότερα.

Η ιδέα της αρχιτεκτονικής δικτύου Feistel είναι η εξής: η ροή πληροφοριών εισόδου χωρίζεται σε μπλοκ μεγέθους n bit, όπου το n είναι ένας ζυγός αριθμός. Κάθε μπλοκ χωρίζεται σε δύο μέρη - L και R, στη συνέχεια αυτά τα μέρη τροφοδοτούνται σε έναν επαναληπτικό μπλοκ κρυπτογράφησης, στον οποίο το αποτέλεσμα του j-ου σταδίου καθορίζεται από το αποτέλεσμα του προηγούμενου σταδίου j-1! Αυτό μπορεί να επεξηγηθεί με ένα παράδειγμα:

Ρύζι. 1

Όπου, η συνάρτηση Α είναι η κύρια ενέργεια του μπλοκ κρυπτογράφησης. Μπορεί να είναι μια απλή ενέργεια, όπως μια λειτουργία XOR, ή μπορεί να έχει μια πιο περίπλοκη εμφάνιση, να είναι μια ακολουθία από έναν αριθμό απλών ενεργειών - προσθήκη modulo, μετατόπιση προς τα αριστερά, αντικατάσταση στοιχείων κ.λπ., συνολικά αυτές απλά βήματααποτελούν το λεγόμενο - το κύριο βήμα του κρυπτομετασχηματισμού.

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

Προκειμένου η ιδέα των δικτύων Feistel να είναι απολύτως σαφής, εξετάστε την απλούστερη περίπτωση που απεικονίζεται στο Σχ. ρύζι. 1, όπου στη συνάρτηση A - θα εκτελεστούν οι πράξεις "mod 2" ("xor"), αλλά αυτό πρωτόζωοπερίπτωση, σε μια πιο σοβαρή κατάσταση, για παράδειγμα, απόκρυψη πληροφοριών εθνικής σημασίας, η λειτουργία Α μπορεί να είναι πιο περίπλοκη (από όσο έχω δει, η λειτουργία Α μπορεί πράγματι να είναι πολύ περίπλοκη):

Αρχικά δεδομένα:

L=1110b, R=0101, K=1111b

Λάβετε ένα κρυπτογραφημένο κείμενο

1. (R + K) mod 2 4 = Smod, Smod = 0100b

2. (Smod + L) mod 2 = Sxor, Sxor = 1010b

3. L=R, R=Sxor

L=0101b, R=1010b

Ας εξηγήσουμε τα βήματά μας:

1. Αυτή η λειτουργία είναι προσθήκη mod 2 4 . Στην πράξη, μια τέτοια πράξη καταλήγει σε μια απλή πρόσθεση, όπου πρέπει να προσθέσουμε δύο αριθμούς και να αγνοήσουμε τη μεταφορά στο 5ο ψηφίο. Επειδή, αν βάλουμε εκθέτες πάνω από τα ψηφία της δυαδικής αναπαράστασης ενός αριθμού, θα υπάρχει ένας δείκτης τεσσάρων πάνω από το πέμπτο ψηφίο, ρίξτε μια ματιά στο παρακάτω σχήμα, το οποίο δείχνει τις ενέργειες της πράξης μας:

Ρύζι. 2

Εδώ έδειξα τους εκθέτες με ένα βέλος, όπως μπορείτε να δείτε, το αποτέλεσμα θα έπρεπε να ήταν 10100, αλλά επειδή η μεταφορά αγνοείται κατά τη λειτουργία mod 2 4, παίρνουμε 0100.

2. Αυτή η λειτουργία στη βιβλιογραφία ονομάζεται mod 2, στη γλώσσα assembly υλοποιείται από την εντολή XOR. Αλλά αυτή περισσότερο σωστό όνομα mod 2 1 . Χωρίς αυτή τη μοναδική λειτουργία, είναι δύσκολο να δημιουργηθεί ένας γρήγορος, εύκολος στην εφαρμογή αλγόριθμος κρυπτογράφησης και, ταυτόχρονα, να είναι αρκετά ανθεκτικός στην κρυπτογράφηση. Η μοναδικότητα αυτής της επέμβασης έγκειται στο γεγονός ότι είναι το αντίστροφο της! Για παράδειγμα, αν ο αριθμός A είναι XOR με τον αριθμό B, το αποτέλεσμα θα είναι C, στο μέλλον αρκεί να XOR εκ νέου οι αριθμοί B και C μαζί για να ληφθεί η προηγούμενη τιμή του A!

Σε αυτή την πράξη, πήραμε το 1010 έχοντας τους αριθμούς 1110 και 0100, για να πάρουμε πίσω το 1110, αρκεί να XOR τους αριθμούς 0100 και 1010 μαζί! Περισσότερες λεπτομέρειες σχετικά με αυτήν τη λειτουργία μπορείτε να βρείτε στο άρθρο, το οποίο είναι ενσωματωμένο στον ιστότοπο. www.wasm.ru, « Στοιχειώδης οδηγός γιαCRC_αλγόριθμοι ανίχνευσης σφαλμάτων» ο συγγραφέας που Ρος Ν. Ουίλιαμς. Υπάρχει μια παράγραφος σε αυτό το έργο - " 5. Δυαδική αριθμητικήεξαιρουμένων των μεταγραφών". Σε αυτό το άρθρο περιγράφεται η λειτουργία xor!Αναφωνώ γιατί σε αυτό το άρθρο αυτή η λειτουργία περιγράφεται με τέτοιο τρόπο που ο αναγνώστης όχι μόνο καταλαβαίνει πώς λειτουργεί αυτή η λειτουργία, αλλά και την ξεκινάει δείτε, ακούστε και αισθανθείτε!

3. Αυτή η ενέργεια είναι απαραίτητη, ώστε κατά την αποκρυπτογράφηση από το κρυπτογραφημένο κείμενο, να μπορείτε να λάβετε τις αρχικές τιμές.

2.2 Μπλοκ κρυπτογράφησης GOST 28147-89

Ο αλγόριθμος κρυπτογράφησης GOST 28147 - 89 ανήκει στην κατηγορία των κρυπτογράφησης μπλοκ που λειτουργούν στην ισορροπημένη αρχιτεκτονική δικτύου Feistel, όπου δύο μέρη του επιλεγμένου μπλοκ πληροφοριών είναι ίσου μεγέθους. Ο αλγόριθμος αναπτύχθηκε στα βάθη του όγδοου τμήματος της KGB, μετατράπηκε τώρα σε FAPSI και καθορίστηκε ως πρότυπο κρυπτογράφησης. Ρωσική Ομοσπονδίατο 1989 επί ΕΣΣΔ.

Για να λειτουργήσει αυτή η μέθοδος του αλγορίθμου, είναι απαραίτητο να σπάσουμε τις πληροφορίες σε μπλοκ μεγέθους 64 bit. Δημιουργήστε ή εισαγάγετε στο σύστημα κρυπτογράφησης τις ακόλουθες βασικές πληροφορίες: κλειδί και πίνακας αντικατάστασης. Η επιλογή του κλειδιού και του πίνακα αντικατάστασης για κρυπτογράφηση θα πρέπει να ληφθεί πολύ σοβαρά υπόψη, γιατί. αυτό είναι το θεμέλιο της ασφάλειας των πληροφοριών σας. Σχετικά με τις απαιτήσεις που επιβάλλονται στο κλειδί και στον πίνακα αντικαταστάσεων, δείτε την παράγραφο "Απαιτήσεις για βασικές πληροφορίες".

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

θεωρητικό ελάχιστο.

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

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

3.1.1. Το κλειδί είναι μια ακολουθία οκτώ στοιχείων των 32 bit το καθένα. Περαιτέρω, θα υποδηλώσουμε το σύμβολο K και τα στοιχεία από τα οποία αποτελείται - k1,k2,k3,k4,k5,k6,k7,k8.

3.1.2 Ο πίνακας αντικατάστασης είναι ένας πίνακας οκτώ σειρών και δεκαέξι στηλών, που στο εξής θα αναφέρεται ως Hij. Κάθε στοιχείο στην τομή της σειράς i και της στήλης j παίρνει 4 bit.

3.2 Το κύριο βήμα του μετασχηματισμού κρυπτογράφησης

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

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

1. Το τμήμα προσθήκης του μπλοκ R προστίθεται στο βασικό στοιχείο K mod 2 32 . Περιέγραψα μια παρόμοια λειτουργία παραπάνω, εδώ το ίδιο πράγμα είναι μόνο ότι ο εκθέτης δεν είναι "4", αλλά "32" - το αποτέλεσμα αυτής της λειτουργίας θα συμβολίζεται με Smod στο μέλλον.
2. Διαιρούμε το προηγουμένως ληφθέν αποτέλεσμα Smod σε τέσσερα στοιχεία bit s7,s6,s5,s4,s3,s2,s1,s0 και το τροφοδοτούμε στη συνάρτηση αντικατάστασης. Η αντικατάσταση είναι η εξής: επιλέγεται το στοιχείο Smod - s i, από την αρχή ξεκινάμε από το χαμηλότερο στοιχείο και το αντικαθιστούμε με την τιμή από τον πίνακα αντικατάστασης για τη σειρά i-row και τη στήλη που υποδεικνύεται από την τιμή του στοιχείου s i . Περνάμε στο στοιχείο s i +1 και κάνουμε το ίδιο και συνεχίζουμε μέχρι να αντικαταστήσουμε την τιμή του τελευταίου στοιχείου Smod - το αποτέλεσμα αυτής της πράξης θα συμβολίζεται ως Ssimple.
3. Σε αυτή τη λειτουργία, η τιμή του Ssimple μετατοπίζεται κυκλικά προς τα αριστερά κατά 11 bit και παίρνουμε Srol.
4. Επιλέγουμε το δεύτερο μέρος του μπλοκ L και προσθέτουμε το mod 2 με το Srol, με αποτέλεσμα να έχουμε Sxor.
5. Σε αυτό το στάδιο, το τμήμα L του μπλοκ γίνεται ίσο με την τιμή του τμήματος R και το τμήμα R με τη σειρά του αρχικοποιείται με το αποτέλεσμα του Sxor και αυτό ολοκληρώνει τη συνάρτηση του κύριου βήματος!

3.3 Βασικοί κύκλοι: “32-Z”, “32-R”.

Για να κρυπτογραφήσετε τις πληροφορίες, είναι απαραίτητο να τις σπάσετε σε μπλοκ μεγέθους 64 bit, φυσικά το τελευταίο μπλοκ μπορεί να είναι μικρότερο από 64 bit. Το γεγονός αυτό είναι η αχίλλειος πτέρνα αυτής της μεθόδου «απλής αντικατάστασης». Δεδομένου ότι η προσθήκη του σε 64 bit είναι μια πολύ σημαντική εργασία για την αύξηση της κρυπτογραφικής ισχύος του κρυπτογραφημένου κειμένου, αυτό το ευαίσθητο μέρος, εάν υπάρχει στη σειρά πληροφοριών, αλλά μπορεί να μην είναι (για παράδειγμα, ένα αρχείο μεγέθους 512 byte !), πρέπει να αντιμετωπίζονται με μεγάλη υπευθυνότητα!

Αφού χωρίσετε τις πληροφορίες σε μπλοκ, θα πρέπει να χωρίσετε το κλειδί σε στοιχεία:

Κ = k1,k2,k3,k4,k5,k6,k7,k8

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

Οι βασικοί κύκλοι σημειώνονται, πώς να το πούμε: n - m. Όπου n είναι ο αριθμός των βασικών βημάτων κρυπτομετασχηματισμού στον βασικό βρόχο και m είναι ο "τύπος" του βασικού βρόχου, δηλ. τι πρόκειται για, κρυπτογράφηση "Z" ή κρυπτογράφηση "R" δεδομένων.

Ο βασικός κύκλος κρυπτογράφησης 32–3 αποτελείται από 32 βασικά κρυπτογραφικά βήματα. Το μπλοκ N και το στοιχείο του κλειδιού K τροφοδοτούνται στη συνάρτηση που υλοποιεί τις ενέργειες του βήματος και το πρώτο βήμα εμφανίζεται με k1, το δεύτερο πάνω από το αποτέλεσμα με το στοιχείο k2 κ.λπ. σύμφωνα με το ακόλουθο σχήμα:

k1,k2,k3,k4,k5,k6,k7,k8,k1,k2,k3,k4,k5,k6,k7,k8,k1,k2,k3,k4,k5,k6,k7,k8k8,k7, k6,k5,k4,k3,k2,k1

Η διαδικασία αποκρυπτογράφησης 32-P προχωρά με παρόμοιο τρόπο, αλλά τα βασικά στοιχεία τροφοδοτούνται με την αντίστροφη σειρά:

k1,k2,k3,k4,k5,k6,k7,k8,k8,k7,k6,k5,k4,k3,k2,k1,k8,k7,k6,k5,k4,k3,k2,k1,k8, k7,k6,k5,k4,k3,k2,k1

Πρακτική.

4.1 Υλοποίηση του κύριου βήματος του μετασχηματισμού κρυπτογράφησης

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

Αρχικά δεδομένα:

Ας πάρουμε ένα μπλοκ πληροφοριών N = 0102030405060708h, εδώ τα μέρη L και R είναι ίσα:

L = 01020304h, R = 05060708h, πάρτε το κλειδί:

K=' ως 28 zw37 q839 7342ui23 8e2t wqm2 ewp1' (αυτοί είναι κωδικοί ASCII, για να δείτε τη δεκαεξαδική αναπαράσταση, μπορείτε να ανοίξετε αυτό το αρχείο σε λειτουργία προβολής σε Συνολικός Διοικητήςπατώντας το πλήκτρο " F3"και μετά το κλειδί" 3 "). Σε αυτό το κλειδί, οι τιμές των στοιχείων θα είναι:

k1 = 'as28', k2 = 'zw37', k3 = 'q839', k4 = '7342'

k5 = 'ui23', k6 = '8e2t', k7 = 'wqm2', k8 = 'ewp1'

Πάρτε επίσης τον ακόλουθο πίνακα αντικατάστασης:

Ρύζι. 3

Εδώ οι σειρές αριθμούνται από το 0 έως το 7, οι στήλες από το 0 έως το F.

Προειδοποίηση:Όλες οι πληροφορίες, συμπεριλαμβανομένου του κλειδιού με τον πίνακα αντικατάστασης, λαμβάνονται ως παράδειγμα για την εξέταση του αλγορίθμου!

Χρησιμοποιώντας τα "Αρχικά δεδομένα", πρέπει να λάβετε το αποτέλεσμα της δράσης του κύριου βήματος του μετασχηματισμού κρυπτογράφησης.

1. Επιλέξτε μέρος R = 05060708h και βασικό στοιχείο k1 = «ως28», σε δεκαεξαδική μορφή το βασικό στοιχείο θα μοιάζει με αυτό: 61733238h. Τώρα κάνουμε τη λειτουργία του αθροίσματος mod 2 32:

Ρύζι. 4

Όπως μπορείτε να δείτε στο σχήμα, δεν μεταφέραμε σε 33 bit σημειωμένα με κόκκινο χρώμα και με τον εκθέτη " 32 ". Και αν είχαμε άλλες τιμές του R και του βασικού στοιχείου, αυτό θα μπορούσε κάλλιστα να συμβεί, και τότε θα το αγνοούσαμε και στο μέλλον θα χρησιμοποιούσαμε μόνο τα κομμάτια που σημειώνονται με κίτρινο χρώμα.

Εκτελώ μια τέτοια λειτουργία με την εντολή assembler Προσθήκη:

; eax=R, ebx='as28'

Το αποτέλεσμα αυτής της λειτουργίας είναι Smod = 66793940h

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

Ρύζι. 5

Προσπάθησα να οπτικοποιήσω τα στοιχεία Smod στο σχήμα, αλλά θα εξηγήσω ούτως ή άλλως:

s0 = 0, s1 = 4, s2 = 9, κ.λπ.

Τώρα, ξεκινώντας από το χαμηλότερο στοιχείο s0, κάνουμε μια αντικατάσταση. Θυμόμαστε την παράγραφο 3.2 Το κύριο βήμα του μετασχηματισμού κρυπτογράφησης» Το i είναι μια γραμμή, το s i είναι μια στήλη, αναζητούμε μια τιμή στη γραμμή μηδέν και στη στήλη μηδέν:

Εικ.6

Άρα η τρέχουσα τιμή του Smod δεν είναι 6679394 0 h και 6679394 5 η.

Προχωράμε στην αντικατάσταση του s1, δηλ. τέσσερις. Χρησιμοποιώντας την πρώτη γραμμή και την τέταρτη στήλη (s1= 4!). Ας δούμε την εικόνα:

Ρύζι. 7

Τώρα η τιμή είναι Smod, όχι 667939 4 5h, 667939 2 5 ώρες. Υποθέτω ότι τώρα ο αλγόριθμος αντικατάστασης είναι σαφής στον αναγνώστη και μπορώ να πω ότι μετά το τελικό αποτέλεσμα του Ssimple θα έχει την ακόλουθη τιμή - 11e10325h.

Θα μιλήσω για το πώς είναι πιο εύκολο να εφαρμοστεί με τη μορφή εντολών assembler αργότερα στην επόμενη παράγραφο, αφού μιλήσω για τον εκτεταμένο πίνακα.

1. Πρέπει να μετατοπίσουμε την προκύπτουσα τιμή Simple 11 bit προς τα αριστερά.

Ρύζι. 8

Όπως μπορείτε να δείτε, αυτή η ενέργεια είναι αρκετά απλή και υλοποιείται από μία εντολή γλώσσας assembly - ρολόκαι το αποτέλεσμα αυτής της λειτουργίας Srol είναι 0819288Fh.

4. Τώρα παραμένει μέρος L του μπλοκ πληροφοριών μας στο XOR με την τιμή Srol. Παίρνω αριθμομηχανή από το w2k sp4 και παίρνω Sxor = 091b2b8bh.

5. Αυτή η ενέργεια είναι τελική και απλώς εκχωρούμε, καθαρίζουμε στο R την τιμή του τμήματος L και αρχικοποιούμε το τμήμα L με την τιμή του Sxor.

Τελικό αποτέλεσμα:

L=091b2b8bh, R=01020304h

4.2 Αύξηση της ταχύτητας του αλγορίθμου

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

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

1. Επιλεγμένο τμήμα του μπλοκ L στον καταχωρητή eax και R στο edx.

2. Αρχικοποιήθηκε στον καταχωρητή esi με τη διεύθυνση του εκτεταμένου κλειδιού, περισσότερα για αυτό παρακάτω.

3. Εκχώρησα την τιμή της διεύθυνσης του εκτεταμένου πίνακα αντικατάστασης στον καταχωρητή ebx, περισσότερα για αυτό παρακάτω

4. Πέρασε τις πληροφορίες των σημείων 1,2, 3 στη συνάρτηση του βασικού κύκλου 32 - Z ή 32 - R, ανάλογα με την περίσταση.

Εάν κοιτάξετε το σχέδιο για την παροχή βασικών στοιχείων στην παράγραφο " Βασικοί κύκλοι: "32-Z", "32-R"”, τότε το κλειδί μας για τον βασικό κύκλο 32 - Z μπορεί να αναπαρασταθεί ως εξής:

Κ 32-Ζ =

"as28", "zw37", "q839", "7342", "ui23", "8e2t", "wqm2", "ewp1",

"as28", "zw37", "q839", "7342", "ui23", "8e2t", "wqm2", "ewp1",

"ewp1", "wqm2", "8e2t", "ui23", "7342", "q839", "zw37", "as28"

Εκείνοι. από την αρχή πηγαίνετε k1,k2,k3,k4,k5,k6,k7,k8 - ‘ ως 28', 'zw37', 'q839', '7342', 'ui23', '8ε2τ','wqm2', 'ewp1'Αυτή η σειρά επαναλαμβάνεται τρεις φορές. Στη συνέχεια τα στοιχεία πηγαίνουν με αντίστροφη σειρά, δηλ.: k8,k7,k6,k5,k4,k3,k2,k1 - 'ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'.

Τακτοποίησα εκ των προτέρων τα στοιχεία του πίνακα με τη σειρά που έπρεπε να προβληθούν σε 32 - Z. Έτσι, αύξησα την απαιτούμενη μνήμη ανά κλειδί, αλλά γλίτωσα τον εαυτό μου από κάποιες διαδικασίες σκέψης που δεν χρειαζόμουν και αύξησα την ταχύτητα του αλγόριθμος, για μειώνοντας το χρόνο πρόσβασης στη μνήμη! Εδώ περιέγραψα μόνο το κλειδί για το 32 - Z, για τον κύκλο 32 - R έκανα το ίδιο, αλλά χρησιμοποιώντας ένα διαφορετικό σχήμα για την παροχή στοιχείων, το οποίο περιέγραψα επίσης στην παράγραφο " Βασικοί κύκλοι: “32-Z”, “32-R».

Ήρθε η ώρα να περιγράψουμε την υλοποίηση της λειτουργίας αντικατάστασης, όπως υποσχέθηκα παραπάνω. Δεν μπορούσα να περιγράψω νωρίτερα, γιατί. Αυτό απαιτεί την εισαγωγή μιας νέας ιδέας - ενός εκτεταμένου πίνακα αντικατάστασης. Δεν μπορώ να σας εξηγήσω τι είναι. Αντίθετα, θα σας το δείξω και μπορείτε να διαμορφώσετε μόνοι σας τι είναι - εκτεταμένος πίνακας αντικατάστασης;

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

Για παράδειγμα, έπρεπε να αντικαταστήσουμε τον αριθμό 66793940h. Θα το παρουσιάσω με την εξής μορφή:

Ρύζι. 9

Τώρα αν πάρουμε τα στοιχεία s1,s0, δηλ. χαμηλό byte, τότε το αποτέλεσμα της συνάρτησης αντικατάστασης θα είναι 25 ώρες! Αφού διάβασα το άρθρο του Andrey Vinokurov, το οποίο παρέθεσα στην παράγραφο " Κατάλογος χρησιμοποιημένης βιβλιογραφίας”, στην πραγματικότητα θα διαπιστώσετε ότι αν λάβετε δύο γραμμές, μπορείτε να λάβετε έναν πίνακα που σας επιτρέπει να βρείτε γρήγορα στοιχεία αντικατάστασης χρησιμοποιώντας μια εντολή assembler xlat.Λένε ότι είναι δυνατό με άλλο τρόπο, πιο γρήγορα, αλλά ο Andrey Vinokurov πέρασε περίπου τέσσερα χρόνια ερευνώντας γρήγορους αλγόριθμους για την εφαρμογή του GOST! Δεν νομίζω ότι πρέπει να εφεύρετε ξανά τον τροχό όταν υπάρχει ήδη.

Λοιπόν, σχετικά με τον πίνακα:

Ας πάρουμε τις δύο πρώτες γραμμές, το μηδέν και την πρώτη, και ας δημιουργήσουμε έναν πίνακα 256 byte. Τώρα παρατηρούμε ένα χαρακτηριστικό ότι αν χρειαστεί να μετατρέψετε 00h, τότε το αποτέλεσμα θα είναι 75h (βάσει της Εικ. 3) - βάλτε αυτήν την τιμή στον πίνακα σε μετατόπιση 00h. Παίρνουμε την τιμή 01h, το αποτέλεσμα της συνάρτησης αντικατάστασης είναι 79h, το βάζουμε στον πίνακα με μετατόπιση 01 και ούτω καθεξής μέχρι το 0FFh, που θα μας δώσει 0FCh, το οποίο θα βάλουμε στον πίνακα με μετατόπιση 0FFh. Έτσι, πήραμε έναν εκτεταμένο πίνακα αντικαταστάσεων για την πρώτη ομάδα χορδών: την πρώτη και το μηδέν. Αλλά υπάρχουν ακόμα τρεις ομάδες: η δεύτερη σελίδα 2, σελίδα 3, η τρίτη σελίδα 4, σελίδα 5, η τέταρτη σελίδα 6, σελίδα 7. Με αυτές τις τρεις ομάδες προχωράμε με τον ίδιο τρόπο όπως και με την πρώτη. Το αποτέλεσμα είναι ένας εκτεταμένος πίνακας αντικατάστασης!

Τώρα μπορείτε να εφαρμόσετε έναν αλγόριθμο που θα εκτελέσει την αντικατάσταση. Για να το κάνουμε αυτό, παίρνουμε τους πηγαίους κωδικούς που δημοσίευσε ο Andrey Vinokurov στη σελίδα του, βλ. Βιβλιογραφία».

lea ebx,extented_table_simple

mov eax, [βάλτε τον αριθμό για αντικατάσταση]

προσθέστε ebx,100h ;μεταβείτε στους επόμενους δύο κόμβους

υπο ebx,300h ; ώστε στο μέλλον η ebx να δείχνει στον πίνακα

Τώρα ένα ακόμη χαρακτηριστικό, όχι μόνο αντικαταστήσαμε τις προηγούμενες ενέργειες, αλλά και μετακινήσαμε τον αριθμό κατά 8 bit προς τα αριστερά! Απλώς πρέπει να μετακινήσουμε τον αριθμό άλλα 3 bit προς τα αριστερά:

και παίρνουμε το αποτέλεσμα της επέμβασης rol eax,11!

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

Απαιτήσεις βασικών πληροφοριών.

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

Το κριτήριο για την ισοπιθανή κατανομή των bit μεταξύ των τιμών 1 και 0. Συνήθως, το κριτήριο για την ισοπιθανή κατανομή των bit είναι το κριτήριο του Pearson ("chi-square").

Αυτό σημαίνει το κλειδί, κατ 'αρχήν οποιοσδήποτε αριθμός μπορεί. Δηλαδή κατά το σχηματισμό του επόμενου bit του κλειδιού, η πιθανότητα αρχικοποίησής του κατά ένα ή μηδέν είναι 50/50!

Λάβετε υπόψη ότι το κλειδί έχει οκτώ στοιχεία, το καθένα 32 bit, επομένως υπάρχουν 32 * 8 = 256 bit συνολικά στο κλειδί και τον αριθμό πιθανά κλειδιά 2256! Δεν σου κάνει εντύπωση;

κριτήρια σειράς.

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

Ρύζι. 10

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

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

Τώρα σχετικά με την επιλογή του πίνακα αντικατάστασης:

Τώρα ας μιλήσουμε για το πώς να επιλέξετε το σωστό τραπέζι αντικατάστασης. Η κύρια απαίτηση για την επιλογή πινάκων αντικατάστασης είναι το φαινόμενο της «μη επαναληψιμότητας» στοιχείων, καθένα από τα οποία έχει μέγεθος 4 bit. Όπως είδατε παραπάνω, κάθε σειρά του πίνακα αντικατάστασης αποτελείται από τις τιμές 0h, 1h, 2h, 3h, ..., 0fh. Επομένως, η κύρια απαίτηση είναι κάθε γραμμή να περιέχει τις τιμές 0h, 1h, 2h, ... , 0fh και κάθε τέτοια τιμή σε ένα αντίγραφο. Για παράδειγμα, η σειρά:

1 2 3 4 5 6 7 8 9 A B C D E F

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

Αυτή ήταν μια απαίτηση, το επόμενο κριτήριο λέει ότι - κάθε bit του μπλοκ εξόδου πρέπει να είναι στατιστικά ανεξάρτητο από κάθε bit του μπλοκ εισόδου!

Πώς φαίνεται πιο εύκολο; Και να πώς, για παράδειγμα, επιλέξαμε το στοιχείο s0 = 0Fh, 01111b από τον παραπάνω αριθμό. Η πιθανότητα να αντικαταστήσουμε τώρα το πρώτο bit με ένα ή ένα μηδέν είναι 0,5! Η πιθανότητα αντικατάστασης του δεύτερου, του τρίτου και του τέταρτου bit, κάθε bit, που εξετάζεται χωριστά, με ένα ή μηδενικό είναι επίσης 0,5. Όταν επιλέγουμε s1 = 0Eh, θα αντικαταστήσουμε την πιθανότητα ότι είμαστε ένα bit μηδέν, και αυτό είναι "0". , με μηδέν ή ένα πολύ ίσον - 0,5! Έτσι, σύμφωνα με αυτό το κριτήριο, δεν υπάρχει κανονικότητα μεταξύ της αντικατάστασης μηδενικών bits των στοιχείων s0, s1! Ναι, θα μπορούσατε να αντικαταστήσετε ένα, αλλά θα μπορούσατε να βάλετε και μηδενικά.

Για να αξιολογήσετε τον πίνακα σύμφωνα με αυτό το κριτήριο, μπορείτε να δημιουργήσετε έναν πίνακα συντελεστών συσχέτισης που υπολογίζονται από τον τύπο:

Αν p = 1, τότε η τιμή του bit j στην έξοδο είναι ίση με την τιμή του bit i στην είσοδο για οποιονδήποτε συνδυασμό μπιτ στην είσοδο.

Αν p = -1, τότε η τιμή του bit j στην έξοδο είναι πάντα η αντίστροφη του bit εισόδου i.

Αν p = 0, τότε το bit εξόδου j παίρνει τις τιμές 0 και 1 με ίση πιθανότητα για οποιαδήποτε σταθερή τιμή του bit εισόδου i.

Ας πάρουμε ένα παράδειγμα μίας γραμμής:

Ας το αναλύσουμε σε συστατικά:

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

Παίρνουμε το 0ο bit του 0ου αριθμού (0) στην είσοδο και το 0ο bit του 0ου αριθμού στην έξοδο (1) και εκτελούμε την πράξη 0 XOR 1 = 1.

Παίρνουμε το 0ο bit του 1ου αριθμού (1) στην είσοδο και το 0ο bit του 1ου αριθμού στην έξοδο (1) και εκτελούμε την πράξη 1 XOR 1 = 0.

Παίρνουμε το 0ο bit του 2ου αριθμού (0) στην είσοδο και το 0ο bit του 2ου αριθμού στην έξοδο (0) και εκτελούμε την πράξη 0 XOR 0 = 0.

Παίρνουμε το 0ο bit του 3ου αριθμού (1) στην είσοδο και το 0ο bit του 3ου αριθμού στην έξοδο (1) και εκτελούμε την πράξη 1 XOR 1 = 0.

Αφού εκτελέσουμε διαδοχικά λειτουργίες XOR σε μια τέτοια ακολουθία, μετράμε τον αριθμό όλων των μη μηδενικών τιμών, παίρνουμε την τιμή 6. Επομένως P 00 = 1-(6/2 4-1) = 0,25. Έτσι, αποδείχθηκε ότι η τιμή του bit 0 στην έξοδο είναι ίση με την τιμή του bit 0 στην είσοδο σε 4 περιπτώσεις από τις 16.

Τελικός πίνακας αποδόσεων:

Όπως φαίνεται από τον πίνακα των συντελεστών συσχέτισης, το bit 3 στην είσοδο αντιστρέφεται σε σχέση με το bit 0 στην έξοδο σε 14 περιπτώσεις από τις 16, που είναι 87,5% Αυτό δεν είναι πλέον αποδεκτό για κανονικά συστήματα κρυπτογράφησης. Για αλλαγή, ας πάρουμε ένα άλλο παράδειγμα:

Ο πίνακας των συντελεστών θα είναι ο ακόλουθος (ποιος δεν τεμπελιάζει να υπολογίσει ξανά)

Λοιπόν, τα πράγματα είναι ακόμη χειρότερα σε αυτόν τον πίνακα - τα κομμάτια 1 και 2 της ομάδας παραμένουν αμετάβλητα! Ο κρυπτοαναλυτής έχει ένα μέρος για να γυρίσει. Λαμβάνοντας υπόψη όλες αυτές τις απαιτήσεις, μια απλή απαρίθμηση ("κεφαλή") βρήκε πίνακες μετάθεσης που αντιστοιχούν στην καθορισμένη θεωρία (σήμερα - 1276 συνδυασμοί) Ακολουθούν μερικοί από αυτούς:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Κατάλογος χρησιμοποιημένης βιβλιογραφίας.

1. Άρθρο του Andrey Vinokurov:

Αλγόριθμος κρυπτογράφησης GOST 28147-89, χρήση και εφαρμογή του

για υπολογιστές πλατφόρμες Intel x86.

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

1. Άρθρο του Horst Feistel:

Κρυπτογραφία και Ασφάλεια Υπολογιστών.

(μπορείτε να το βρείτε στην ίδια διεύθυνση με το προηγούμενο άρθρο)

1. Ross N. Williams:

Ένας στοιχειώδης οδηγός για αλγόριθμους ανίχνευσης σφαλμάτων CRC

Δημοσιεύτηκε στον ιστότοπο www.wasm.en.

Ευχαριστώ.

Θα ήθελα να εκφράσω την ευγνωμοσύνη μου σε όλους τους επισκέπτες του φόρουμ www.wasm.ru. Αλλά θα ήθελα να ευχαριστήσω ιδιαίτερα τον ChS, ο οποίος είναι σήμερα γνωστός ως SteelRat, με βοήθησε να καταλάβω πράγματα που πιθανότατα δεν θα καταλάβαινα ποτέ, καθώς και με βοήθησε να γράψω την παράγραφο: Απαιτήσεις βασικών πληροφοριών», το κύριο μέρος αυτής της παραγράφου γράφτηκε από τον ίδιο. Είμαι επίσης βαθιά ευγνώμων στον υπάλληλο του KSTU. ΕΝΑ. Tupolev Anikin Igor Vyacheslavovich και θα ήταν αμαρτία να μην αναφέρουμε τον Chris Kaspersky, για το γεγονός ότι είναι, και τον Volodya / wasm.ru για τις οδηγίες του. Ω, και τον έχω πάρει. Θέλω επίσης να σημειώσω το Sega-Zero / Callipso που έφερε στο μυαλό μου κάποια μαθηματική ζούγκλα.

Αυτό είναι ίσως το μόνο που θα ήθελα να σας πω.

Θα ήμουν ευγνώμων για κριτική ή ερωτήσεις σχετικά με αυτό το άρθρο ή απλώς συμβουλές. Τα στοιχεία επικοινωνίας μου: [email προστατευμένο], ICQ - 337310594.

Με εκτίμηση, Evil`s Interrupt.

P.S.: Δεν προσπάθησα να ξεπεράσω κανέναν με αυτό το άρθρο. Γράφτηκε με σκοπό να διευκολυνθεί η μελέτη του GOST και αν έχετε δυσκολίες, αυτό δεν σημαίνει ότι φταίω εγώ για αυτό. Να είστε λογικοί και υπομονετικοί, ό,τι καλύτερο για εσάς!

«Όσο είσαι ζωντανός, μην πεθάνεις, κοίτα αυτόν τον κόσμο.
Πολλοί εδώ έχουν νεκρή ψυχή - είναι νεκροί μέσα τους.
Αλλά περπατούν και γελούν, χωρίς να ξέρουν ότι δεν είναι εκεί,
Μη βιάζεσαι τον θάνατό σου», μου είπε.

Άρια, "Εκεί πάνω"

1. Εισαγωγή

1. Εισαγωγή στους κωδικούς μπλοκ

2.1 Δίκτυα Feistel.
2.2 Κρυπτογράφηση μπλοκ GOST 28147-89

1. Θεωρητικό ελάχιστο

3.1 Πληροφορία κλειδί
3.2 Το κύριο βήμα του μετασχηματισμού κρυπτογράφησης

3.3 Βασικοί κύκλοι:“ 32-З” , “ 32-R” .

1. Πρακτική

4.1 Υλοποίηση του κύριου βήματος του μετασχηματισμού κρυπτογράφησης
4.2 Αύξηση της ταχύτητας του αλγορίθμου
5.
6. Κατάλογος χρησιμοποιημένης βιβλιογραφίας
7. Ευχαριστώ.

Εισαγωγή.

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

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

Εισαγωγή στους κωδικούς μπλοκ.

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

Η ιστορία της ανάπτυξης μπλοκ κρυπτογράφησης συνδέεται με τις αρχές της δεκαετίας του '70, όταν η IBM, συνειδητοποιώντας την ανάγκη προστασίας πληροφοριών κατά τη μετάδοση δεδομένων μέσω καναλιών επικοινωνίας υπολογιστή, άρχισε να πραγματοποιεί το δικό της ερευνητικό πρόγραμμα αφιερωμένο στην προστασία των πληροφοριών σε ηλεκτρονικά δίκτυα, συμπεριλαμβανομένης της κρυπτογραφίας.

Μια ομάδα ερευνητών - προγραμματιστών της εταιρείας IBM, η οποία άρχισε να μελετά συστήματα κρυπτογράφησης με σχήμα συμμετρικού κλειδιού, είχε επικεφαλής τον Δρ. Χορστ Φάιστελ.

2.1 Δίκτυα Feistel

Η αρχιτεκτονική της νέας μεθόδου κρυπτογράφησης που πρότεινε ο Feistel στην κλασική λογοτεχνία ονομάστηκε "Feistel Architecture", αλλά αυτή τη στιγμή στη ρωσική και ξένη λογοτεχνία χρησιμοποιείται ένας πιο καθιερωμένος όρος - "δίκτυο Feistel" ή NetWork του Feistel. Στη συνέχεια, σύμφωνα με αυτήν την αρχιτεκτονική, κατασκευάστηκε ο κρυπτογράφησης Lucifer - ο οποίος δημοσιεύτηκε αργότερα και προκάλεσε ένα νέο κύμα ενδιαφέροντος για την κρυπτογραφία γενικότερα.

Η ιδέα της αρχιτεκτονικής δικτύου Feistel είναι η εξής: η ροή πληροφοριών εισόδου χωρίζεται σε μπλοκ μεγέθους n bit, όπου το n είναι ένας ζυγός αριθμός. Κάθε μπλοκ χωρίζεται σε δύο μέρη - L και R, στη συνέχεια αυτά τα μέρη τροφοδοτούνται σε έναν επαναληπτικό μπλοκ κρυπτογράφησης, στον οποίο το αποτέλεσμα του j-ου σταδίου καθορίζεται από το αποτέλεσμα του προηγούμενου σταδίου j-1! Αυτό μπορεί να επεξηγηθεί με ένα παράδειγμα:

Ρύζι. 1

Όπου, η συνάρτηση Α είναι η κύρια ενέργεια του μπλοκ κρυπτογράφησης. Μπορεί να είναι μια απλή ενέργεια, όπως η λειτουργία XOR, ή μπορεί να έχει μια πιο σύνθετη μορφή, να είναι μια ακολουθία από έναν αριθμό απλών ενεργειών - προσθήκη modulo, αριστερή μετατόπιση, αντικατάσταση στοιχείων κ.λπ., συνολικά, αυτές οι απλές ενέργειες αποτελούν το λεγόμενο - το κύριο βήμα του μετασχηματισμού κρυπτογράφησης.

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

Προκειμένου η ιδέα των δικτύων Feistel να είναι απολύτως σαφής, εξετάστε την απλούστερη περίπτωση που απεικονίζεται στο Σχ. ρύζι. 1, όπου στη συνάρτηση A - θα εκτελεστούν οι πράξεις "mod 2" ("xor"), αλλά αυτό πρωτόζωοπερίπτωση, σε μια πιο σοβαρή κατάσταση, για παράδειγμα, απόκρυψη πληροφοριών εθνικής σημασίας, η λειτουργία Α μπορεί να είναι πιο περίπλοκη (από όσο έχω δει, η λειτουργία Α μπορεί πράγματι να είναι πολύ περίπλοκη):

Αρχικά δεδομένα:

L=1110b, R=0101, K=1111b

Λάβετε ένα κρυπτογραφημένο κείμενο

1. (R + K) mod 2 4 = Smod, Smod = 0100b
2. (Smod + L) mod 2 = Sxor, Sxor = 1010b
3. L=R, R=Sxor

L=0101b, R=1010b

Ας εξηγήσουμε τα βήματά μας:

1. Αυτή η λειτουργία είναι προσθήκη mod 2 4 . Στην πράξη, μια τέτοια πράξη καταλήγει σε μια απλή πρόσθεση, όπου πρέπει να προσθέσουμε δύο αριθμούς και να αγνοήσουμε τη μεταφορά στο 5ο ψηφίο. Επειδή, αν βάλουμε εκθέτες πάνω από τα ψηφία της δυαδικής αναπαράστασης ενός αριθμού, θα υπάρχει ένας δείκτης τεσσάρων πάνω από το πέμπτο ψηφίο, ρίξτε μια ματιά στο παρακάτω σχήμα, το οποίο δείχνει τις ενέργειες της πράξης μας:

Ρύζι. 2

Εδώ έδειξα τους εκθέτες με ένα βέλος, όπως μπορείτε να δείτε, το αποτέλεσμα θα έπρεπε να ήταν 10100, αλλά επειδή η μεταφορά αγνοείται κατά τη λειτουργία mod 2 4, παίρνουμε 0100.

1. Αυτή η λειτουργία στη βιβλιογραφία ονομάζεται mod 2, στη γλώσσα συναρμολόγησης υλοποιείται από την εντολή XOR. Αλλά το πιο σωστό όνομά του είναι mod 2 1 . Χωρίς αυτή τη μοναδική λειτουργία, είναι δύσκολο να δημιουργηθεί ένας γρήγορος, εύκολος στην εφαρμογή αλγόριθμος κρυπτογράφησης και, ταυτόχρονα, να είναι αρκετά ανθεκτικός στην κρυπτογράφηση. Η μοναδικότητα αυτής της επέμβασης έγκειται στο γεγονός ότι είναι το αντίστροφο της! Για παράδειγμα, αν ο αριθμός A είναι XOR με τον αριθμό B, το αποτέλεσμα θα είναι C, στο μέλλον αρκεί να XOR εκ νέου οι αριθμοί B και C μαζί για να ληφθεί η προηγούμενη τιμή του A!

Σε αυτή την πράξη, πήραμε το 1010 έχοντας τους αριθμούς 1110 και 0100, για να πάρουμε πίσω το 1110, αρκεί να XOR τους αριθμούς 0100 και 1010 μαζί! Περισσότερες λεπτομέρειες σχετικά με αυτήν τη λειτουργία μπορείτε να βρείτε στο άρθρο, το οποίο είναι ενσωματωμένο στον ιστότοπο. www.wasm.ru, « Στοιχειώδης οδηγός γιαCRC_αλγόριθμοι ανίχνευσης σφαλμάτων» ο συγγραφέας που Ρος Ν. Ουίλιαμς. Υπάρχει μια παράγραφος σε αυτό το έργο - 5. Δυαδική αριθμητική χωρίς φέρει". Σε αυτό το άρθρο περιγράφεται η λειτουργία xor!Αναφωνώ γιατί σε αυτό το άρθρο αυτή η λειτουργία περιγράφεται με τέτοιο τρόπο που ο αναγνώστης όχι μόνο καταλαβαίνει πώς λειτουργεί αυτή η λειτουργία, αλλά και την ξεκινάει δείτε, ακούστε και αισθανθείτε!

1. Αυτή η ενέργεια είναι απαραίτητη, ώστε κατά την αποκρυπτογράφηση από το κρυπτογραφημένο κείμενο, να μπορείτε να λάβετε τις αρχικές τιμές.

2.2 Μπλοκ κρυπτογράφησης GOST 28147-89

Ο αλγόριθμος κρυπτογράφησης GOST 28147 - 89 ανήκει στην κατηγορία των κρυπτογράφησης μπλοκ που λειτουργούν στην ισορροπημένη αρχιτεκτονική δικτύου Feistel, όπου δύο μέρη του επιλεγμένου μπλοκ πληροφοριών είναι ίσου μεγέθους. Ο αλγόριθμος αναπτύχθηκε στα έγκατα του όγδοου τμήματος της KGB, τώρα μετατράπηκε σε FAPSI και κατοχυρώθηκε ως το πρότυπο κρυπτογράφησης της Ρωσικής Ομοσπονδίας το 1989 υπό την ΕΣΣΔ.

Για να λειτουργήσει αυτή η μέθοδος του αλγορίθμου, είναι απαραίτητο να σπάσουμε τις πληροφορίες σε μπλοκ μεγέθους 64 bit. Δημιουργήστε ή εισαγάγετε στο σύστημα κρυπτογράφησης τις ακόλουθες βασικές πληροφορίες: κλειδί και πίνακας αντικατάστασης. Η επιλογή του κλειδιού και του πίνακα αντικατάστασης για κρυπτογράφηση θα πρέπει να ληφθεί πολύ σοβαρά υπόψη, γιατί. αυτό είναι το θεμέλιο της ασφάλειας των πληροφοριών σας. Σχετικά με τις απαιτήσεις που επιβάλλονται στο κλειδί και στον πίνακα αντικαταστάσεων, δείτε την παράγραφο "Απαιτήσεις για βασικές πληροφορίες".

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

θεωρητικό ελάχιστο.

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

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

3.1.1. Το κλειδί είναι μια ακολουθία οκτώ στοιχείων των 32 bit το καθένα. Περαιτέρω, θα υποδηλώσουμε το σύμβολο K και τα στοιχεία από τα οποία αποτελείται - k1,k2,k3,k4,k5,k6,k7,k8.

3.1.2 Ο πίνακας αντικατάστασης είναι ένας πίνακας οκτώ σειρών και δεκαέξι στηλών, που στο εξής θα αναφέρεται ως Hij. Κάθε στοιχείο στην τομή της σειράς i και της στήλης j παίρνει 4 bit.

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

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

1. Το τμήμα προσθήκης του μπλοκ R προστίθεται στο βασικό στοιχείο K mod 2 32 . Περιέγραψα μια παρόμοια λειτουργία παραπάνω, εδώ είναι το ίδιο πράγμα, μόνο ο εκθέτης δεν είναι "4", αλλά "32" - το αποτέλεσμα αυτής της λειτουργίας θα συμβολίζεται με το Smod στο μέλλον.
2. Διαιρούμε το προηγουμένως ληφθέν αποτέλεσμα Smod σε τέσσερα στοιχεία bit s7,s6,s5,s4,s3,s2,s1,s0 και το τροφοδοτούμε στη συνάρτηση αντικατάστασης. Η αντικατάσταση έχει ως εξής: επιλέγεται το στοιχείο Smod - s i, από την αρχή ξεκινάμε από το νεότερο στοιχείο και το αντικαθιστούμε με την τιμή από τον πίνακα αντικαταστάσεων με i - η γραμμή και η στήλη που υποδεικνύονται από την τιμή του στοιχείου s i . Περνάμε στο στοιχείο s i +1 και κάνουμε το ίδιο και συνεχίζουμε μέχρι να αντικαταστήσουμε την τιμή του τελευταίου στοιχείου Smod - το αποτέλεσμα αυτής της πράξης θα συμβολίζεται ως Ssimple.
3. Σε αυτή τη λειτουργία, η τιμή του Ssimple μετατοπίζεται κυκλικά προς τα αριστερά κατά 11 bit και παίρνουμε Srol.
4. Επιλέγουμε το δεύτερο μέρος του μπλοκ L και προσθέτουμε το mod 2 με το Srol, με αποτέλεσμα να έχουμε Sxor.
5. Σε αυτό το στάδιο, το τμήμα L του μπλοκ γίνεται ίσο με την τιμή του τμήματος R και το τμήμα R με τη σειρά του αρχικοποιείται με το αποτέλεσμα του Sxor και αυτό ολοκληρώνει τη συνάρτηση του κύριου βήματος!

3.3 Βασικοί κύκλοι: “32-Z”, “32-R”.

Για να κρυπτογραφήσετε τις πληροφορίες, είναι απαραίτητο να τις σπάσετε σε μπλοκ μεγέθους 64 bit, φυσικά το τελευταίο μπλοκ μπορεί να είναι μικρότερο από 64 bit. Το γεγονός αυτό είναι η αχίλλειος πτέρνα αυτής της μεθόδου «απλής αντικατάστασης». Δεδομένου ότι η προσθήκη του σε 64 bit είναι μια πολύ σημαντική εργασία για την αύξηση της κρυπτογραφικής ισχύος του κρυπτογραφημένου κειμένου, αυτό το ευαίσθητο μέρος, εάν υπάρχει στη σειρά πληροφοριών, αλλά μπορεί να μην είναι (για παράδειγμα, ένα αρχείο μεγέθους 512 byte !), πρέπει να αντιμετωπίζονται με μεγάλη υπευθυνότητα!

Αφού χωρίσετε τις πληροφορίες σε μπλοκ, θα πρέπει να χωρίσετε το κλειδί σε στοιχεία:

Κ = k1,k2,k3,k4,k5,k6,k7,k8

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

Οι βασικοί κύκλοι σημειώνονται, πώς να το πούμε: n - m. Όπου n είναι ο αριθμός των βασικών βημάτων κρυπτομετασχηματισμού στον βασικό βρόχο και m είναι ο "τύπος" του βασικού βρόχου, δηλ. τι πρόκειται για, κρυπτογράφηση "Z" ή κρυπτογράφηση "R" δεδομένων.

Ο βασικός κύκλος κρυπτογράφησης 32–3 αποτελείται από 32 βασικά κρυπτογραφικά βήματα. Το μπλοκ N και το στοιχείο του κλειδιού K τροφοδοτούνται στη συνάρτηση που υλοποιεί τις ενέργειες του βήματος και το πρώτο βήμα εμφανίζεται με k1, το δεύτερο πάνω από το αποτέλεσμα με το στοιχείο k2 κ.λπ. σύμφωνα με το ακόλουθο σχήμα:

k1,k2,k3,k4,k5,k6,k7,k8,k1,k2,k3,k4,k5,k6,k7,k8,k1,k2,k3,k4,k5,k6,k7,k8k8,k7, k6,k5,k4,k3,k2,k1

Η διαδικασία αποκρυπτογράφησης 32-P προχωρά με παρόμοιο τρόπο, αλλά τα βασικά στοιχεία τροφοδοτούνται με την αντίστροφη σειρά:

k1,k2,k3,k4,k5,k6,k7,k8,k8,k7,k6,k5,k4,k3,k2,k1,k8,k7,k6,k5,k4,k3,k2,k1,k8, k7,k6,k5,k4,k3,k2,k1

Πρακτική.

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

Αρχικά δεδομένα:

Ας πάρουμε ένα μπλοκ πληροφοριών N = 0102030405060708h, εδώ τα μέρη L και R είναι ίσα:

L = 01020304h, R = 05060708h, πάρτε το κλειδί:

K=' ως 28 zw37 q839 7342ui23 8e2t wqm2 ewp1' (αυτοί είναι κωδικοί ASCII, για να δείτε τη δεκαεξαδική αναπαράσταση, μπορείτε να ανοίξετε αυτό το αρχείο σε λειτουργία προβολής στο Total Commander πατώντας το κουμπί " F3"και μετά το κλειδί" 3 "). Σε αυτό το κλειδί, οι τιμές των στοιχείων θα είναι:

k1 = 'as28', k2 = 'zw37', k3 = 'q839', k4 = '7342'

k5 = 'ui23', k6 = '8e2t', k7 = 'wqm2', k8 = 'ewp1'

Πάρτε επίσης τον ακόλουθο πίνακα αντικατάστασης:

Ρύζι. 3

Εδώ οι σειρές αριθμούνται από το 0 έως το 7, οι στήλες από το 0 έως το F.

Προειδοποίηση:Όλες οι πληροφορίες, συμπεριλαμβανομένου του κλειδιού με τον πίνακα αντικατάστασης, λαμβάνονται ως παράδειγμα για την εξέταση του αλγορίθμου!

Χρησιμοποιώντας τα "Αρχικά δεδομένα", πρέπει να λάβετε το αποτέλεσμα της δράσης του κύριου βήματος του μετασχηματισμού κρυπτογράφησης.

1. Επιλέγουμε το τμήμα R = 05060708h και το βασικό στοιχείο k1 = ‘as28’, σε δεκαεξαδική μορφή το βασικό στοιχείο θα μοιάζει με αυτό: 61733238h. Τώρα κάνουμε τη λειτουργία του αθροίσματος mod 2 32:

Ρύζι. 4

Όπως μπορείτε να δείτε στο σχήμα, δεν μεταφέραμε σε 33 bit σημειωμένα με κόκκινο χρώμα και με τον εκθέτη " 32 ". Και αν είχαμε άλλες τιμές του R και του βασικού στοιχείου, αυτό θα μπορούσε κάλλιστα να συμβεί, και τότε θα το αγνοούσαμε και στο μέλλον θα χρησιμοποιούσαμε μόνο τα κομμάτια που σημειώνονται με κίτρινο χρώμα.

Εκτελώ μια τέτοια λειτουργία με την εντολή assembler Προσθήκη:

; eax=R, ebx='as28'

Το αποτέλεσμα αυτής της λειτουργίας είναι Smod = 66793940h

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

ΜΟΤΡΟ ΔΕΝ ΑΠΟΘΗΚΕΥΕΤΑΙ

Ρύζι. 5

Προσπάθησα να οπτικοποιήσω τα στοιχεία Smod στο σχήμα, αλλά θα εξηγήσω ούτως ή άλλως:

s0 = 0, s1 = 4, s2 = 9, κ.λπ.

Τώρα, ξεκινώντας από το χαμηλότερο στοιχείο s0, κάνουμε μια αντικατάσταση. Θυμόμαστε την παράγραφο 3.2 Το κύριο βήμα του μετασχηματισμού κρυπτογράφησης» Το i είναι μια γραμμή, το s i είναι μια στήλη, αναζητούμε μια τιμή στη γραμμή μηδέν και στη στήλη μηδέν:

Εικ.6

Άρα η τρέχουσα τιμή του Smod δεν είναι 6679394 0 h και 6679394 5 η.

Προχωράμε στην αντικατάσταση του s1, δηλ. τέσσερις. Χρησιμοποιώντας την πρώτη γραμμή και την τέταρτη στήλη (s1= 4!). Ας δούμε την εικόνα:

Ρύζι. 7

Τώρα η τιμή είναι Smod, όχι 667939 4 5h, 667939 2 5 ώρες. Υποθέτω ότι τώρα ο αλγόριθμος αντικατάστασης είναι σαφής στον αναγνώστη και μπορώ να πω ότι μετά το τελικό αποτέλεσμα του Ssimple θα έχει την ακόλουθη τιμή - 11e10325h.

Θα μιλήσω για το πώς είναι πιο εύκολο να εφαρμοστεί με τη μορφή εντολών assembler αργότερα στην επόμενη παράγραφο, αφού μιλήσω για τον εκτεταμένο πίνακα.

1. Πρέπει να μετατοπίσουμε την προκύπτουσα τιμή Simple 11 bit προς τα αριστερά.

Ρύζι. 8

Όπως μπορείτε να δείτε, αυτή η ενέργεια είναι αρκετά απλή και υλοποιείται από μία εντολή γλώσσας assembly - ρολόκαι το αποτέλεσμα αυτής της λειτουργίας Srol είναι 0819288Fh.

1. Τώρα παραμένει μέρος L του μπλοκ πληροφοριών μας στο XOR με την τιμή Srol. Παίρνω αριθμομηχανή από το w2k sp4 και παίρνω Sxor = 091b2b8bh.
2. Αυτή η ενέργεια είναι τελική και απλώς εκχωρούμε, καθαρίζουμε το R την τιμή του τμήματος L και αρχικοποιούμε το τμήμα L με την τιμή του Sxor.

Τελικό αποτέλεσμα:

L=091b2b8bh, R=01020304h

4.2 Αύξηση της ταχύτητας του αλγορίθμου

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

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

1. Επιλέξτε μέρος του μπλοκ L στον καταχωρητή eax και R σε edx.
2. Αρχικοποιήθηκε στον καταχωρητή esi με τη διεύθυνση του εκτεταμένου κλειδιού, περισσότερα για αυτό παρακάτω.
3. Εκχώρησα την τιμή της διεύθυνσης του εκτεταμένου πίνακα αντικατάστασης στον καταχωρητή ebx, περισσότερα για αυτό παρακάτω
4. Πέρασε τις πληροφορίες των σημείων 1,2, 3 στη συνάρτηση του βασικού κύκλου 32 - Z ή 32 - R, ανάλογα με την περίσταση.

Εάν κοιτάξετε το σχέδιο για την παροχή βασικών στοιχείων στην παράγραφο " Βασικοί κύκλοι: "32-Z", "32-R"”, τότε το κλειδί μας για τον βασικό κύκλο 32 - Z μπορεί να αναπαρασταθεί ως εξής:

Κ 32-Ζ =

"as28", "zw37", "q839", "7342", "ui23", "8e2t", "wqm2", "ewp1",

"as28", "zw37", "q839", "7342", "ui23", "8e2t", "wqm2", "ewp1",

"ewp1", "wqm2", "8e2t", "ui23", "7342", "q839", "zw37", "as28"

Εκείνοι. από την αρχή πηγαίνετε k1,k2,k3,k4,k5,k6,k7,k8 - ‘ ως 28', 'zw37', 'q839', '7342', 'ui23', '8ε2τ','wqm2', 'ewp1'Αυτή η σειρά επαναλαμβάνεται τρεις φορές. Στη συνέχεια τα στοιχεία πηγαίνουν με αντίστροφη σειρά, δηλ.: k8,k7,k6,k5,k4,k3,k2,k1 - 'ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'.

Τακτοποίησα εκ των προτέρων τα στοιχεία του πίνακα με τη σειρά που έπρεπε να προβληθούν σε 32 - Z. Έτσι, αύξησα την απαιτούμενη μνήμη ανά κλειδί, αλλά γλίτωσα τον εαυτό μου από κάποιες διαδικασίες σκέψης που δεν χρειαζόμουν και αύξησα την ταχύτητα του αλγόριθμος, για μειώνοντας το χρόνο πρόσβασης στη μνήμη! Εδώ περιέγραψα μόνο το κλειδί για το 32 - Z, για τον κύκλο 32 - R έκανα το ίδιο, αλλά χρησιμοποιώντας ένα διαφορετικό σχήμα για την παροχή στοιχείων, το οποίο περιέγραψα επίσης στην παράγραφο " Βασικοί κύκλοι: “32-Z”, “32-R».

Ήρθε η ώρα να περιγράψουμε την υλοποίηση της λειτουργίας αντικατάστασης, όπως υποσχέθηκα παραπάνω. Δεν μπορούσα να περιγράψω νωρίτερα, γιατί. Αυτό απαιτεί την εισαγωγή μιας νέας ιδέας - ενός εκτεταμένου πίνακα αντικατάστασης. Δεν μπορώ να σας εξηγήσω τι είναι. Αντίθετα, θα σας το δείξω και μπορείτε να διαμορφώσετε μόνοι σας τι είναι - εκτεταμένος πίνακας αντικατάστασης;

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

Για παράδειγμα, έπρεπε να αντικαταστήσουμε τον αριθμό 66793940h. Θα το παρουσιάσω με την εξής μορφή:

ΜΟΤΡΟ ΔΕΝ ΑΠΟΘΗΚΕΥΕΤΑΙ

Ρύζι. 9

Τώρα αν πάρουμε τα στοιχεία s1,s0, δηλ. χαμηλό byte, τότε το αποτέλεσμα της συνάρτησης αντικατάστασης θα είναι 25 ώρες! Αφού διάβασα το άρθρο του Andrey Vinokurov, το οποίο παρέθεσα στην παράγραφο " Κατάλογος χρησιμοποιημένης βιβλιογραφίας”, στην πραγματικότητα θα διαπιστώσετε ότι αν λάβετε δύο γραμμές, μπορείτε να λάβετε έναν πίνακα που σας επιτρέπει να βρείτε γρήγορα στοιχεία αντικατάστασης χρησιμοποιώντας μια εντολή assembler xlat.Λένε ότι είναι δυνατό με άλλο τρόπο, πιο γρήγορα, αλλά ο Andrey Vinokurov πέρασε περίπου τέσσερα χρόνια ερευνώντας γρήγορους αλγόριθμους για την εφαρμογή του GOST! Δεν νομίζω ότι πρέπει να εφεύρετε ξανά τον τροχό όταν υπάρχει ήδη.

Λοιπόν, σχετικά με τον πίνακα:

Ας πάρουμε τις δύο πρώτες γραμμές, το μηδέν και την πρώτη, και ας δημιουργήσουμε έναν πίνακα 256 byte. Τώρα παρατηρούμε ένα χαρακτηριστικό ότι αν χρειαστεί να μετατρέψετε 00h, τότε το αποτέλεσμα θα είναι 75h (βάσει της Εικ. 3) - βάλτε αυτήν την τιμή στον πίνακα σε μετατόπιση 00h. Παίρνουμε την τιμή 01h, το αποτέλεσμα της συνάρτησης αντικατάστασης είναι 79h, το βάζουμε στον πίνακα με μετατόπιση 01 και ούτω καθεξής μέχρι το 0FFh, που θα μας δώσει 0FCh, το οποίο θα βάλουμε στον πίνακα με μετατόπιση 0FFh. Έτσι, πήραμε έναν εκτεταμένο πίνακα αντικαταστάσεων για την πρώτη ομάδα χορδών: την πρώτη και το μηδέν. Αλλά υπάρχουν ακόμα τρεις ομάδες: η δεύτερη σελίδα 2, σελίδα 3, η τρίτη σελίδα 4, σελίδα 5, η τέταρτη σελίδα 6, σελίδα 7. Με αυτές τις τρεις ομάδες προχωράμε με τον ίδιο τρόπο όπως και με την πρώτη. Το αποτέλεσμα είναι ένας εκτεταμένος πίνακας αντικατάστασης!

Τώρα μπορείτε να εφαρμόσετε έναν αλγόριθμο που θα εκτελέσει την αντικατάσταση. Για να το κάνουμε αυτό, παίρνουμε τους πηγαίους κωδικούς που δημοσίευσε ο Andrey Vinokurov στη σελίδα του, βλ. Βιβλιογραφία».

lea ebx,extented_table_simple

mov eax, [βάλτε τον αριθμό για αντικατάσταση]

προσθέστε ebx,100h ;μεταβείτε στους επόμενους δύο κόμβους

υπο ebx,300h ; ώστε στο μέλλον η ebx να δείχνει στον πίνακα

Τώρα ένα ακόμη χαρακτηριστικό, όχι μόνο αντικαταστήσαμε τις προηγούμενες ενέργειες, αλλά και μετακινήσαμε τον αριθμό κατά 8 bit προς τα αριστερά! Απλώς πρέπει να μετακινήσουμε τον αριθμό άλλα 3 bit προς τα αριστερά:

και παίρνουμε το αποτέλεσμα της επέμβασης rol eax,11!

Δεν μπορώ να προσθέσω τίποτα περισσότερο σχετικά με τη βελτιστοποίηση, το μόνο πράγμα που μπορώ να τονίσω αυτό που είπα παραπάνω είναι η χρήση καταχωρητών πιο συχνά από τις προσβάσεις στη μνήμη. Νομίζω ότι αυτές οι λέξεις είναι μόνο για αρχάριους, οι έμπειροι άνθρωποι το καταλαβαίνουν πολύ καλά χωρίς τα λόγια μου :).

Απαιτήσεις βασικών πληροφοριών.

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

- κριτήριο ισοπιθανής κατανομής bit μεταξύ των τιμών 1 και 0. Συνήθως, το κριτήριο του Pearson ("χι-τετράγωνο") λειτουργεί ως κριτήριο ισοπιθανής κατανομής των bit.

Αυτό σημαίνει το κλειδί, κατ 'αρχήν οποιοσδήποτε αριθμός μπορεί. Δηλαδή κατά το σχηματισμό του επόμενου bit του κλειδιού, η πιθανότητα αρχικοποίησής του κατά ένα ή μηδέν είναι 50/50!

Λάβετε υπόψη ότι το κλειδί έχει οκτώ στοιχεία, το καθένα 32 bit, άρα υπάρχουν 32 * 8 = 256 bit συνολικά στο κλειδί και ο αριθμός των πιθανών πλήκτρων είναι 2 256! Δεν σου κάνει εντύπωση; 🙂

— κριτήριο σειράς.

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

Ρύζι. 10

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

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

Τώρα σχετικά με την επιλογή του πίνακα αντικατάστασης:

Τώρα ας μιλήσουμε για το πώς να επιλέξετε το σωστό τραπέζι αντικατάστασης. Η κύρια απαίτηση για την επιλογή πινάκων αντικατάστασης είναι το φαινόμενο της «μη επαναληψιμότητας» στοιχείων, καθένα από τα οποία έχει μέγεθος 4 bit. Όπως είδατε παραπάνω, κάθε σειρά του πίνακα αντικατάστασης αποτελείται από τις τιμές 0h, 1h, 2h, 3h, ..., 0fh. Επομένως, η κύρια απαίτηση είναι κάθε γραμμή να περιέχει τις τιμές 0h, 1h, 2h, ... , 0fh και κάθε τέτοια τιμή σε ένα αντίγραφο. Για παράδειγμα, η σειρά:

1 2 3 4 5 6 7 8 9 A B C D E F

Πληροί πλήρως αυτήν την απαίτηση, αλλά ακόμα! Δεν συνιστάται να επιλέξετε μια τέτοια ακολουθία ως συμβολοσειρά. Γιατί αν δώσετε μια τιμή στην είσοδο μιας συνάρτησης που βασίζεται σε μια τέτοια συμβολοσειρά, τότε θα έχετε την ίδια τιμή στην έξοδο! Δεν πιστεύεις; Στη συνέχεια, πάρτε τον αριθμό 332DA43Fh και οκτώ τέτοιες γραμμές ως πίνακα αντικατάστασης. Εκτελέστε τη λειτουργία αντικατάστασης και σας διαβεβαιώνω ότι η έξοδος θα είναι ο αριθμός 332DA43Fh! Το ίδιο δηλαδή που υποβάλατε στην εισαγωγή της πράξης! Και αυτό δεν είναι σημάδι καλής μορφής στην κρυπτογράφηση, και ήταν; 🙂

Αυτή ήταν μια απαίτηση, το επόμενο κριτήριο λέει ότι - κάθε bit του μπλοκ εξόδου πρέπει να είναι στατιστικά ανεξάρτητο από κάθε bit του μπλοκ εισόδου!

Πώς φαίνεται πιο εύκολο; Και να πώς, για παράδειγμα, επιλέξαμε το στοιχείο s0 = 0Fh, 01111b από τον παραπάνω αριθμό. Η πιθανότητα να αντικαταστήσουμε τώρα το πρώτο bit με ένα ή ένα μηδέν είναι 0,5! Η πιθανότητα αντικατάστασης του δεύτερου, του τρίτου και του τέταρτου bit, κάθε bit, που εξετάζεται χωριστά, με ένα ή μηδενικό είναι επίσης 0,5. Όταν επιλέγουμε s1 = 0Eh, θα αντικαταστήσουμε την πιθανότητα ότι είμαστε ένα bit μηδέν, και αυτό είναι "0". , με μηδέν ή ένα πολύ ίσον - 0,5! Έτσι, σύμφωνα με αυτό το κριτήριο, δεν υπάρχει κανονικότητα μεταξύ της αντικατάστασης μηδενικών bits των στοιχείων s0, s1! Ναι, θα μπορούσατε να αντικαταστήσετε ένα, αλλά θα μπορούσατε να βάλετε και μηδενικά. 🙂

Για να αξιολογήσετε τον πίνακα σύμφωνα με αυτό το κριτήριο, μπορείτε να δημιουργήσετε έναν πίνακα συντελεστών συσχέτισης που υπολογίζονται από τον τύπο:

— εάν p = 1, τότε η τιμή του bit j στην έξοδο είναι ίση με την τιμή του bit i στην είσοδο για οποιονδήποτε συνδυασμό δυαδικών ψηφίων στην είσοδο.

— εάν p = -1, τότε η τιμή του bit j στην έξοδο είναι πάντα η αντιστροφή του bit εισόδου i.

— εάν p = 0, τότε το bit εξόδου j παίρνει τις τιμές 0 και 1 με ίση πιθανότητα για οποιαδήποτε σταθερή τιμή του bit εισόδου i.

Ας πάρουμε ένα παράδειγμα μίας γραμμής:

ρε	σι	4	1	3	φά	5	9	0	ΕΝΑ	μι	7	6	8	2	ντο

Ας το αναλύσουμε σε συστατικά:

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

- παίρνουμε το 0ο bit του 0ου αριθμού (0) στην είσοδο και το 0ο bit του 0ου αριθμού στην έξοδο (1) εκτελούμε την πράξη 0 XOR 1 = 1.

- παίρνουμε το 0ο bit του 1ου αριθμού (1) στην είσοδο και το 0ο bit του 1ου αριθμού στην έξοδο (1) εκτελούμε την πράξη 1 XOR 1 = 0.

- παίρνουμε το 0ο bit του 2ου αριθμού (0) στην είσοδο και το 0ο bit του 2ου αριθμού στην έξοδο (0) εκτελούμε την πράξη 0 XOR 0 = 0.

- παίρνουμε το 0ο bit του 3ου αριθμού (1) στην είσοδο και το 0ο bit του 3ου αριθμού στην έξοδο (1) εκτελούμε την πράξη 1 XOR 1 = 0.

Αφού εκτελέσουμε διαδοχικά λειτουργίες XOR σε μια τέτοια ακολουθία, μετράμε τον αριθμό όλων των μη μηδενικών τιμών, παίρνουμε την τιμή 6. Επομένως P 00 = 1-(6/2 4-1) = 0,25. Έτσι, αποδείχθηκε ότι η τιμή του bit 0 στην έξοδο είναι ίση με την τιμή του bit 0 στην είσοδο σε 4 περιπτώσεις από τις 16.

Τελικός πίνακας αποδόσεων:

Ο πίνακας των συντελεστών θα είναι ο ακόλουθος (ποιος δεν τεμπελιάζει να υπολογίσει ξανά)

	Είσοδος
Εξοδος		0	1	2	3
	0	-0,25	0,00	0,00	0,00
	1	0,00	1,00	0,00	0,00
	2	0,00	0,00	1,00	0,00
	3	0,00	0,00	0,00	-0,50

Λοιπόν, τα πράγματα είναι ακόμη χειρότερα σε αυτόν τον πίνακα - τα κομμάτια 1 και 2 της ομάδας παραμένουν αμετάβλητα! Ο κρυπτοαναλυτής έχει ένα μέρος για να γυρίσει 🙂 Λαμβάνοντας υπόψη όλες αυτές τις απαιτήσεις, μια απλή απαρίθμηση ("κεφαλή") βρήκε πίνακες μετάθεσης που αντιστοιχούν στην καθορισμένη θεωρία (σήμερα - 1276 συνδυασμοί) Ακολουθούν μερικοί από αυτούς:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Κατάλογος χρησιμοποιημένης βιβλιογραφίας.

1. Άρθρο του Andrey Vinokurov:

Αλγόριθμος κρυπτογράφησης GOST 28147-89, χρήση και εφαρμογή του

για υπολογιστές με πλατφόρμα Intel x86.

(μπορείτε να το βρείτε στη διεύθυνση: http://www.enlight.ru/crypto/frame.htm).

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

1. Άρθρο του Horst Feistel:

Κρυπτογραφία και Ασφάλεια Υπολογιστών.

(μπορείτε να το βρείτε στην ίδια διεύθυνση με το προηγούμενο άρθρο)

1. Ross N. Williams:

Ένας στοιχειώδης οδηγός για αλγόριθμους ανίχνευσης σφαλμάτων CRC

Δημοσιεύτηκε στον ιστότοπο www.wasm.en.

Ευχαριστώ.

Θα ήθελα να εκφράσω την ευγνωμοσύνη μου σε όλους τους επισκέπτες του φόρουμ www.wasm.ru. Αλλά θα ήθελα να ευχαριστήσω ιδιαίτερα τον ChS, ο οποίος είναι σήμερα γνωστός ως SteelRat, με βοήθησε να καταλάβω πράγματα που πιθανότατα δεν θα καταλάβαινα ποτέ, καθώς και με βοήθησε να γράψω την παράγραφο: Απαιτήσεις βασικών πληροφοριών», το κύριο μέρος αυτής της παραγράφου γράφτηκε από τον ίδιο. Είμαι επίσης βαθιά ευγνώμων στον υπάλληλο του KSTU. ΕΝΑ. Tupolev Anikin Igor Vyacheslavovich και θα ήταν αμαρτία να μην αναφέρουμε τον Chris Kaspersky, για το γεγονός ότι είναι, και τον Volodya / wasm.ru για τις οδηγίες του. Α, και έχω πάρει από αυτόν :). Θέλω επίσης να σημειώσω το Sega-Zero / Callipso που έφερε στο μυαλό μου κάποια μαθηματική ζούγκλα.

Αυτό είναι ίσως το μόνο που θα ήθελα να σας πω.

Θα ήμουν ευγνώμων για κριτική ή ερωτήσεις σχετικά με αυτό το άρθρο ή απλώς συμβουλές. Τα στοιχεία επικοινωνίας μου: [email προστατευμένο], ICQ - 337310594.

Με εκτίμηση, Evil`s Interrupt.

P.S.: Δεν προσπάθησα να ξεπεράσω κανέναν με αυτό το άρθρο. Γράφτηκε με σκοπό να διευκολυνθεί η μελέτη του GOST και αν έχετε δυσκολίες, αυτό δεν σημαίνει ότι φταίω εγώ για αυτό. Να είστε λογικοί και υπομονετικοί, ό,τι καλύτερο για εσάς!

Ο γνωστός όρος «απόδοση επεξεργαστή» στην κοινωνία είναι μια αντικειμενική, υπολογισμένη παράμετρος που μετριέται σε flops. Ωστόσο, η πλειοψηφία το μετράει σε gigahertz, πιστεύοντας αφελώς ότι πρόκειται για το ίδιο πράγμα. Κανείς δεν γνωρίζει τον όρο "απόδοση κώδικα" και θα εξηγήσω αμέσως γιατί.

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

Πώς μετράται η απόδοση του κώδικα; Εφόσον ήμουν ο πρώτος που μίλησα γι' αυτό, τότε με το δικαίωμα του ανακαλύπτοντος θα το μετρήσω σε κλίμακες RTT.).

Τώρα σοβαρά. Στους σύγχρονους επεξεργαστές, οι κύριοι μετασχηματισμοί είναι λειτουργίες σε αριθμούς 32 bit, όλα τα άλλα είναι, σε γενικές γραμμές, εξωτικά. Επομένως, θα λάβουμε υπόψη το κύριο πράγμα - λειτουργίες με αριθμούς 32-bit. Πόσες λειτουργίες 32 bit πιστεύετε ότι μπορεί να εκτελέσει ταυτόχρονα ο πυρήνας ενός σύγχρονου επεξεργαστή;

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

Έτσι, ένας κώδικας προγράμματος που φορτώνει όλες τις εκτελεστικές συσκευές του επεξεργαστή ταυτόχρονα σε όλο το χρόνο εκτέλεσης του κώδικα θα έχει απόδοση 12 RTT NIS. Ανώτατο όριο! Για να είμαι ειλικρινής, δεν έχω ξαναγράψει τέτοιο κώδικα, αλλά σε αυτό το άρθρο θα προσπαθήσω να κάνω μια προσπάθεια με τον εαυτό μου.

Θα αποδείξω ότι είναι δυνατός ο κώδικας με ταυτόχρονη εκτέλεση δώδεκα λειτουργιών 32 bit

Ο κώδικας προγράμματος που χρησιμοποιεί μία μονάδα εκτέλεσης στον πυρήνα του επεξεργαστή θα έχει φυσικά απόδοση 1 RTT. Προγράμματα που δημιουργούνται από μεταγλωττιστές γλωσσών μπορούν να «καμαρώνουν» για τέτοια απόδοση κώδικα. υψηλό επίπεδοκαι διερμηνείς εικονικές μηχανές. Δεν πρέπει να υποθέσουμε ότι ο δείκτης χρήσης της CPU, που μπορεί να δει κανείς στη διαχείριση εργασιών του λειτουργικού συστήματος, μπορεί να χρησιμεύσει ως αντικειμενικό κριτήριο για την αποτελεσματικότητα του κώδικα. Το φορτίο πυρήνα του επεξεργαστή μπορεί να είναι 100%, αλλά ο κώδικας προγράμματος θα χρησιμοποιεί μία συσκευή εκτέλεσης σε αυτόν (απόδοση 1 RTT). Σε αυτήν την περίπτωση, σε φορτίο 100%, ο πυρήνας του επεξεργαστή θα λειτουργεί στο 1/12 της μέγιστης απόδοσής του. Με άλλα λόγια, όταν η Διαχείριση εργασιών των Windows εμφανίζει τη μέγιστη χρήση της CPU, η πραγματική απόδοσή της μπορεί να ποικίλλει από 1 έως 12 RTT. Βλέποντας στο παράθυρο επιδόσεων 100% φορτίο σε οποιονδήποτε πυρήνα επεξεργαστή, είναι λάθος να υποθέσουμε ότι όλες οι εκτελεστικές συσκευές λειτουργούν σε αυτόν τον πυρήνα, σε καμία περίπτωση!

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

Παραδοσιακή εφαρμογή του GOST 28147-89

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

Η κρυπτογραφική μετατροπή σύμφωνα με το GOST 28147-89 χρησιμοποιείται για κρυπτογράφηση ροής πληροφοριών σε κανάλια επικοινωνίας και σε μονάδες δίσκου.

Επί του παρόντος, η εφαρμογή λογισμικού αυτού του GOST στο RON χρησιμοποιείται ευρέως. ΕΠΕΞΕΡΓΑΣΤΗΣ. Στις γνωστές μεθόδους εφαρμογής GOST, όλες οι μυστικές πληροφορίες (κλειδιά κρυπτογράφησης, μπλοκ αντικατάστασης) τοποθετούνται σε μνήμη τυχαίας προσπέλασης. Αυτό μειώνει την αξιοπιστία της κρυπτογράφησης, καθώς, έχοντας μια ένδειξη RAM, είναι δυνατό να αποκαλυφθούν πλήρως όλα τα μυστικά στοιχεία του μετασχηματισμού κρυπτογράφησης. Επιπλέον, η μέθοδος έχει περιορισμούς ταχύτητας λόγω της θέσης των κύριων αντικειμένων κρυπτομετασχηματισμού στο OP και ατελούς φόρτωσης των εκτελεστικών συσκευών ALU. Οι σύγχρονοι επεξεργαστές, που εφαρμόζουν μια κρυπτοδιαδικασία χρησιμοποιώντας μια πολύ γνωστή μέθοδο, μπορούν να παρέχουν ταχύτητα κρυπτογράφησης 40–60 megabyte ανά δευτερόλεπτο. Και αν πραγματικά το καταλαβαίνετε μέχρι τέλους, τότε ο λόγος για τη χαμηλή απόδοση και την αδύναμη ασφάλεια της μετατροπής κρυπτογράφησης είναι η εφαρμογή λογισμικού του μπλοκ αντικατάστασης. Δείτε την περιγραφή του στο GOST στο σχ. 1.

Σύμφωνα με την ρήτρα 1.2 του GOST, αυτό το μπλοκ υλοποιεί μεταθέσεις τετραδίων (τεσσάρων bit) σε μια λέξη 32 bit, αλλά η αρχιτεκτονική του επεξεργαστή x86 / 64 και το σύνολο εντολών του δεν είναι ικανά να χειριστούν αποτελεσματικά τετραδικές.

Για την εφαρμογή λογισμικού του μπλοκ αντικατάστασης χρησιμοποιούνται ειδικοί πίνακες στη μνήμη RAM, οι οποίοι προετοιμάζονται στο στάδιο της αρχικοποίησης της κρυπτολειτουργίας. Αυτοί οι πίνακες συνδυάζουν τους κόμβους αντικατάστασης γειτονικών τετραδίων σε πίνακες byte 8 × 8 bit, επομένως υπάρχουν τέσσερις πίνακες 256 byte στη μνήμη RAM.

Σε πιο προηγμένες υλοποιήσεις, αυτοί οι πίνακες έχουν μέγεθος 1024 byte (256 λέξεις των τεσσάρων byte). Αυτό γίνεται για να εφαρμοστεί στους πίνακες μια πρόσθετη κυκλική μετατόπιση κατά 11 θέσεις της λέξης 32-bit που λαμβάνεται ως αποτέλεσμα της αντικατάστασης (η επόμενη λειτουργία του αλγορίθμου μετατροπής σύμφωνα με το GOST). Ένα παράδειγμα εφαρμογής του GOST σύμφωνα με αυτή τη μέθοδοφαίνεται στο παράρτημα 1 (στο δίσκο).

Οι πληροφορίες του μπλοκ αντικατάστασης είναι ένα μυστικό συστατικό της κρυπτολειτουργίας (όπως διατυπώνεται στο GOST, βλ. Εικ. 2).

Η τοποθέτηση αυτών των πινάκων με τα κλειδιά του μπλοκ αντικατάστασης στο OP έρχεται σε αντίθεση με τις απαιτήσεις του GOST (άρθρο 1.7), καθώς οι μυστικές πληροφορίες καθίστανται διαθέσιμες σε προγράμματα τρίτωνεργασία σε εγκατάσταση υπολογιστή. Το FSB, το οποίο πιστοποιεί επίσης εφαρμογές κρυπτογράφησης λογισμικού σύμφωνα με το GOST, εξετάζει αυτήν την παραβίαση, για να το θέσω ήπια, συγκαταβατικά. Εάν για να τοποθετήσετε κλειδιά στο OP, το FSB εξακολουθεί να απαιτεί ένα "φύλλο συκής" - κάλυψη των πλήκτρων με τη λειτουργία XOR, τότε δεν απαιτείται τίποτα για τα μπλοκ αντικατάστασης στο OP, αποθηκεύονται σε καθαρό κείμενο.

Εν ολίγοις, το FSB παραλείπει τέτοιες εφαρμογές λογισμικού της κρυπτοδιαδικασίας, παρά την προφανή μείωση της ισχύος μιας τέτοιας λύσης και την άμεση παραβίαση των δικών του απαιτήσεων σύμφωνα με το GOST (ρήτρα 1.7). Και αυτό παρά τις γνωστές μεθόδους διάσπασης κρυπτογράφησης μέσω της αφαίρεσης μιας χωματερής μνήμης ...

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

Αλλά αρκετά από τους στίχους, είναι σημαντικό στο πλαίσιο του θέματος που εξετάζουμε ότι αυτός ο κώδικας προγράμματος έχει απόδοση 1 RTT-shku. Τώρα ας γράψουμε έναν κώδικα με απόδοση 2 RTT.

Πολυνηματική εφαρμογή του GOST 28147-89

Ο μόνος τρόπος για να επιταχυνθούν οι κρυπτοδιαδικασίες στον γνωστό αλγόριθμο είναι η εισαγωγή του multithreading. Το νόημα μιας τέτοιας αλλαγής στην υλοποίηση του αλγορίθμου είναι ο υπολογισμός πολλών μπλοκ δεδομένων ταυτόχρονα ταυτόχρονα.

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

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

Οι σύγχρονοι επεξεργαστές περιλαμβάνουν τουλάχιστον δύο, ακόμη και τρεις έως έξι αριθμητικές λογικές μονάδες. Αυτά τα ALU (FPU, αριθμητικές μονάδες διευθύνσεων κ.λπ.) μπορούν να λειτουργούν ανεξάρτητα το ένα από το άλλο, η μόνη προϋπόθεση για την παράλληλη λειτουργία τους είναι τα μη επικαλυπτόμενα αντικείμενα λογισμικού στα οποία λειτουργούν. Με άλλα λόγια, σε εντολές που εκτελούν ταυτόχρονα την ALU, οι διευθύνσεις μνήμης και οι αριθμοί καταχωρητών πρέπει να είναι διαφορετικοί. Ή, δεν πρέπει να εκτελούνται λειτουργίες εγγραφής σε κοινούς καταχωρητές και διευθύνσεις μνήμης στις οποίες έχουν πρόσβαση διάφορες εκτελεστικές συσκευές του επεξεργαστή.

Η φόρτωση της εργασίας όλων των ALU ελέγχεται από ένα ειδικό μπλοκ υλικού μέσα στον πυρήνα του επεξεργαστή - τον προγραμματιστή, ο οποίος κοιτάζει μέσω του εκτελέσιμου κώδικα προς τα εμπρός, σε βάθος 32–64 byte. Εάν ο προγραμματιστής βρει εντολές που μπορούν να εκτελεστούν στην ALU χωρίς διενέξεις, τότε τις εκτελεί ταυτόχρονα σε διαφορετικές μονάδες εκτέλεσης. Σε αυτήν την περίπτωση, ο μετρητής των εκτελεσμένων εντολών δείχνει την εκτελέσιμη εντολή (υπάρχουν αρκετές από αυτές σε ένα τέτοιο σχήμα), μετά την οποία έχουν ήδη εκτελεστεί όλες οι εντολές.

Οι περισσότερες ακολουθίες προγραμμάτων που δημιουργούνται αυτόματα (από μεταγλωττιστές) δεν μπορούν να φορτώσουν όλες τις ALU και τις FPU που βρίσκονται στον πυρήνα του επεξεργαστή. Σε αυτήν την περίπτωση, το υλικό του επεξεργαστή είναι αδρανές, γεγονός που μειώνει σημαντικά την απόδοση που προκύπτει. Οι προγραμματιστές επεξεργαστών το κατανοούν αυτό και εισάγουν λειτουργίες για την αύξηση της συχνότητας πυρήνα όταν ο εξοπλισμός δεν χρησιμοποιείται πλήρως. Τα συστήματα υπερσυναλλαγών είναι επίσης σχεδιασμένα για αυτό και θα χρησιμοποιήσω αυτό το σύστημα για να «πιέσω» τον κωδικό στο μέγιστο στο μέλλον.

Οι μεταγλωττιστές, ακόμη και οι πιο βελτιστοποιημένοι, και ακόμη περισσότερο - οι μηχανές εικονικών μηχανών, δεν μπορούν να δημιουργήσουν βελτιστοποιημένο κώδικα όσον αφορά την ταχύτητα. Μόνο ένας προγραμματιστής με γνώσεις μηχανικής μπορεί να γράψει τέτοιο βελτιστοποιημένο κώδικα και το εργαλείο για τη γραφή του είναι αποκλειστικά το assembler.

Μια χαρακτηριστική απεικόνιση της δυνατότητας εκτέλεσης πολλών ανεξάρτητων νημάτων προγράμματος σε έναν πυρήνα επεξεργαστή είναι η υλοποίηση GOST, η οποία εκτελείται σε δύο νήματα σε έναν μόνο πυρήνα επεξεργαστή. Η ιδέα του κώδικα είναι απλή: υπάρχουν δύο μπλοκ δεδομένων για κρυπτογράφηση/αποκρυπτογράφηση, αλλά ένας πυρήνας επεξεργαστή που θα εκτελέσει τη μετατροπή. Είναι δυνατό να πραγματοποιηθεί ο μετασχηματισμός για αυτά τα δύο μπλοκ δεδομένων διαδοχικά, και αυτό έχει γίνει μέχρι τώρα. Στην περίπτωση αυτή, ο χρόνος που απαιτείται για την εκτέλεση των μετασχηματισμών διπλασιάζεται.

Αλλά μπορείτε να κάνετε διαφορετικά: εναλλακτικές εντολές που σχετίζονται με την επεξεργασία διαφορετικών μπλοκ δεδομένων. Γραφικά, αυτές οι επιλογές φαίνονται στο Σχ. 3.

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

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

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

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

Η μέθοδος παράλληλης κρυπτογράφησης εφαρμόζεται αποτελεσματικά μόνο για τη λειτουργία του επεξεργαστή 64-bit, αφού σε αυτή τη λειτουργία υπάρχει επαρκής ποσότητα RON (έως και 16 τεμάχια!). Ένα παράδειγμα εφαρμογής του GOST σύμφωνα με αυτήν τη μέθοδο παρουσιάζεται στο Παράρτημα 2 (στο δίσκο).

Είναι σαφές ότι αυτή η εφαρμογή GOST έχει απόδοση κώδικα 2 RTT. Τώρα ας δούμε πώς αυτό επηρεάζει τον χρόνο εκτέλεσης.

Ο κύκλος κρυπτογράφησης για μία ροή (Παράρτημα 1) είναι 352 κύκλοι και κατά τη διάρκεια αυτού του χρόνου υπολογίζονται 8 byte δεδομένων, για μια υλοποίηση δύο ροών του GOST (Παράρτημα 2) απαιτούνται 416 κύκλοι επεξεργαστή, αλλά υπολογίζονται 16 byte. Έτσι, η ταχύτητα μετατροπής που προκύπτει αυξάνεται από 80 σε 144 megabyte για έναν επεξεργαστή 3,6 GHz.

Λαμβάνεται μια ενδιαφέρουσα εικόνα: ο κώδικας περιέχει ακριβώς διπλάσιες οδηγίες και διαρκεί μόνο 15% περισσότερο, αλλά νομίζω ότι οι αναγνώστες έχουν ήδη καταλάβει τον λόγο για αυτό το φαινόμενο ...

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

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

Χρήση καταχωρητών SSE και εντολών AVX σύγχρονων επεξεργαστών για την εφαρμογή του GOST 28147-89

Οι σύγχρονοι επεξεργαστές αρχιτεκτονικής x86/64 περιλαμβάνουν ένα σύνολο καταχωρητών SSE 16 byte και εξειδικευμένους FPU (τουλάχιστον δύο) για την εκτέλεση διαφόρων λειτουργιών σε αυτούς τους καταχωρητές. Είναι δυνατή η εφαρμογή GOST σε αυτόν τον εξοπλισμό και σε αυτήν την περίπτωση, οι κόμβοι αντικατάστασης μπορούν να τοποθετηθούν όχι με τη μορφή πινάκων στη μνήμη RAM, αλλά απευθείας σε αποκλειστικούς καταχωρητές SSE.

Σε ένα μητρώο SSE, μπορείτε να τοποθετήσετε δύο πίνακες των 16 σειρών ταυτόχρονα. Έτσι, τέσσερις καταχωρητές SSE θα φιλοξενήσουν πλήρως όλους τους πίνακες αντικατάστασης. Η μόνη προϋπόθεση για μια τέτοια τοποθέτηση είναι η απαίτηση παρεμβολής, σύμφωνα με την οποία οι τετράδες του ίδιου byte πρέπει να τοποθετούνται σε διαφορετικούς καταχωρητές SSE. Επιπλέον, συνιστάται η τοποθέτηση των χαμηλών και υψηλών τετραδίων των byte εισόδου, αντίστοιχα, στα χαμηλά και υψηλά τετράδια των καταχωρητών SSE.

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

Ένα διάγραμμα ενός από τις πιθανές τοποθετήσεις κόμβων αντικατάστασης σε καταχωρητές SSE φαίνεται στο σχήμα. 4.

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

• Ο πυρήνας του επεξεργαστή έχει τεθεί σε λειτουργία κεντρικού υπολογιστή hypervisor και το μπλοκ διακοπής (APIC) έχει απενεργοποιηθεί αναγκαστικά. Σε αυτήν την περίπτωση, ο πυρήνας του επεξεργαστή είναι πλήρως απομονωμένος από το λειτουργικό σύστημα και τις εφαρμογές που εκτελούνται στην υπολογιστική εγκατάσταση.
• Η φόρτωση των καταχωρητών SSE και η απομόνωση του υπολογιστικού πυρήνα εκτελούνται πριν από την έναρξη του λειτουργικού συστήματος· είναι βέλτιστο να εκτελούνται αυτές οι διαδικασίες από την αξιόπιστη μονάδα εκκίνησης (TDM).
• Τα προγράμματα κρυπτοδιαδικασιών σύμφωνα με το GOST τοποθετούνται στην περιοχή μη τροποποιήσιμης μνήμης της υπολογιστικής μονάδας (είτε BIOS είτε μνήμη flash MDZ).

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

Για αποτελεσματική δειγματοληψία από τους καταχωρητές SSE των τετραδίων, χρησιμοποιούνται οι διακόπτες byte πολλαπλών εισόδων που είναι διαθέσιμοι στις μονάδες FPU. Αυτοί οι διακόπτες επιτρέπουν μεταφορές από οποιοδήποτε byte της πηγής σε οποιοδήποτε byte του προορισμού, από ευρετήρια που βρίσκονται σε έναν ειδικό καταχωρητή ευρετηρίου SSE. Επιπλέον, η μεταφορά εκτελείται παράλληλα και για τα 16 byte του SSE-register-receiver.

Έχοντας κόμβους αποθήκευσης αντικατάστασης σε καταχωρητές SSE και διακόπτη πολλαπλών εισόδων σε μονάδες FPU, είναι δυνατό να οργανωθεί ο ακόλουθος μετασχηματισμός στη μονάδα υποκατάστασης (Εικ. 5).

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

• Δημιουργήστε ένα κατάλληλο σχέδιο τσιπ, αλλά αυτό είναι φανταστικό για εμάς.
• Ο επαναπρογραμματισμός του μικροκώδικα και η δημιουργία της δικής σας εντολής επεξεργαστή για την υλοποίηση αυτής της λειτουργίας σε υπάρχοντες επεξεργαστές δεν είναι πλέον φαντασία, αλλά, δυστυχώς, δεν είναι ρεαλιστικό στις τρέχουσες συνθήκες.
• Γράψτε ένα πρόγραμμα χρησιμοποιώντας τις επίσημες εντολές AVX. Η επιλογή, αν και όχι πολύ αποτελεσματική, αλλά μπορούμε να την εφαρμόσουμε «εδώ και τώρα». Αυτό λοιπόν θα κάνουμε στη συνέχεια.

Οι διακόπτες ελέγχονται από μια ειδική εντολή τριών διευθύνσεων AVX VPSHUFB. Ο πρώτος του τελεστής είναι ο δέκτης πληροφοριών από τους διακόπτες, ο δεύτερος είναι η πηγή στην οποία συνδέονται οι είσοδοι των διακοπτών. Ο τρίτος τελεστής είναι ένας καταχωρητής ελέγχου για διακόπτες, κάθε byte του οποίου σχετίζεται με έναν αντίστοιχο διακόπτη. η τιμή σε αυτό καθορίζει τον αριθμό της κατεύθυνσης από την οποία ο διακόπτης διαβάζει πληροφορίες. Για περιγραφή αυτής της εντολής από την επίσημη τεκμηρίωση της Intel, βλ. 5. Στο σχ. Το σχήμα 6 δείχνει τη λειτουργία αυτής της εντολής - εμφανίζονται μόνο οι μισοί από τους καταχωρητές SSE, για το δεύτερο μισό όλα είναι παρόμοια.

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

Γράφτηκε ένα πρόγραμμα με μια επιλογή φορητών υπολογιστών μέσω διακοπτών FPU, αλλά δεν το έβαλα καν στην εφαρμογή - είναι πολύ φτωχό. Το να έχεις καταχωρητή 128 bit και να χρησιμοποιείς μόνο 32 bit σε αυτό είναι αντιεπαγγελματικό.

Όπως λένε, «Το φινίρισμα μας είναι ο ορίζοντας», οπότε στύψτε το έτσι... θα το πατήσουμε και θα το βάλουμε σε σακούλες!

Δεν πρόκειται για παιχνίδι με λέξεις, αλλά για μια σκληρή πραγματικότητα FPU - οι καταχωρητές SSE μπορούν να χωριστούν σε ίσα μέρη και οι ίδιοι μετασχηματισμοί μπορούν να πραγματοποιηθούν σε αυτά τα μέρη με μία εντολή. Για να το καταλάβει αυτό ο επεξεργαστής, υπάρχει ένα μαγικό γράμμα "P" - ένα πακέτο που τοποθετείται πριν από την εντολή μνημονικό, και όχι λιγότερο τα μαγικά γράμματα "Q", "D", "W", "B", το οποίο τοποθετούνται στο τέλος και δηλώνουν, σε ποια μέρη χωρίζονται οι καταχωρητές SSE σε αυτήν την εντολή.

Ενδιαφερόμαστε για λειτουργία παρτίδαςμε μια ανάλυση του καταχωρητή SSE σε τέσσερα μπλοκ 32-bit. Κατά συνέπεια, όλες οι εντολές θα έχουν το πρόθεμα "P" και θα τερματίζονται με το σύμβολο "D". Αυτό καθιστά δυνατή την παράλληλη επεξεργασία τεσσάρων μπλοκ των 32 bit με μία εντολή επεξεργαστή, δηλαδή τον υπολογισμό τεσσάρων μπλοκ δεδομένων παράλληλα.

Το πρόγραμμα που υλοποιεί αυτή τη μέθοδο είναι διαθέσιμο στο Παράρτημα 3, υπάρχουν όλες οι επεξηγήσεις.

Ωστόσο, πατήστε so press! Οι σύγχρονοι επεξεργαστές έχουν τουλάχιστον δύο FPU και μπορούν να χρησιμοποιηθούν δύο ανεξάρτητες ροές εντολών για την πλήρη φόρτωσή τους. Εάν παρεμβάλετε σωστά εντολές από ανεξάρτητες ροές, τότε μπορείτε να φορτώσετε πλήρως και τις δύο FPU και να λάβετε οκτώ παράλληλες επεξεργασμένες ροές δεδομένων ταυτόχρονα. Ένα τέτοιο πρόγραμμα γράφτηκε και μπορείτε να το δείτε στο Παράρτημα 4, αλλά πρέπει να κοιτάξετε προσεκτικά - μπορείτε να τρελαθείτε. Αυτό ονομάζεται, "ο κώδικας δεν είναι για όλους ...".

Τιμή έκδοσης

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

Για τέσσερα νήματα, επιτεύχθηκε ταχύτητα εκτέλεσης 472 κύκλων επεξεργαστή. Έτσι, για έναν επεξεργαστή με συχνότητα 3,6 GHz, ένα νήμα θεωρείται με ταχύτητα 59 megabyte ανά δευτερόλεπτο, και τέσσερα thread, αντίστοιχα, με ταχύτητα 236 megabyte ανά δευτερόλεπτο.

Για οκτώ νήματα, επιτεύχθηκε ταχύτητα εκτέλεσης 580 κύκλων επεξεργαστή. Έτσι, για έναν επεξεργαστή 3,6 GHz, ένα νήμα θεωρείται με ταχύτητα 49 megabyte ανά δευτερόλεπτο και οκτώ νήματα με ταχύτητα 392 megabyte ανά δευτερόλεπτο.

Όπως μπορεί να παρατηρήσει ο αναγνώστης, ο κώδικας στο παράδειγμα #3 έχει απόδοση 4 RTT, ενώ ο κώδικας στο παράδειγμα #4 έχει απόδοση 8 RTT. Σε αυτά τα παραδείγματα, στους καταχωρητές SSE, τα μοτίβα είναι τα ίδια όπως όταν χρησιμοποιείται το RON, μόνο ο προγραμματιστής έχει μειώσει την απόδοσή του. Τώρα παρέχει 20% αύξηση στη διάρκεια για 2 φορές αύξηση στο μήκος του κώδικα.

Επιπλέον, αυτά τα αποτελέσματα ελήφθησαν χρησιμοποιώντας τις καθολικές εντολές AVX που είναι διαθέσιμες και στις δύο Επεξεργαστές Intel, και σε επεξεργαστές AMD. Εάν κάνετε βελτιστοποίηση για έναν επεξεργαστή AMD, το αποτέλεσμα θα είναι πολύ καλύτερο. Ακούγεται αντίθετη τάση, αλλά είναι αλήθεια, και να γιατί: Επεξεργαστές AMDέχουν ένα επιπλέον σύνολο οδηγιών, τη λεγόμενη επέκταση XOP, και σε αυτό επιπλέον σετυπάρχουν εντολές που απλοποιούν πολύ την εφαρμογή του αλγορίθμου GOST.

Αυτό αναφέρεται στις εντολές της λογικής μετατόπισης πακέτων των byte και της κυκλικής μετατόπισης πακέτων διπλών λέξεων. Τα παραδείγματα που δίνονται στα Παραρτήματα 3 και 4 χρησιμοποιούν ακολουθίες καθολικών εντολών που υλοποιούν τον απαραίτητο μετασχηματισμό: στην πρώτη περίπτωση, μία "επιπλέον" εντολή και στην άλλη περίπτωση, τέσσερις επιπλέον εντολές ταυτόχρονα. Υπάρχουν λοιπόν αποθέματα βελτιστοποίησης και μάλιστα σημαντικά.

Αν μιλάμε για περαιτέρω βελτιστοποίηση, αξίζει να θυμάστε την παρουσία καταχωρητών 256-bit (μητρώων YMM), χρησιμοποιώντας τους οποίους μπορείτε θεωρητικά να διπλασιάσετε την ταχύτητα των υπολογισμών. Αλλά προς το παρόν, αυτό είναι μόνο μια προοπτική, προς το παρόν, οι επεξεργαστές επιβραδύνουν πολύ κατά την εκτέλεση εντολών 256 bit (οι FPU έχουν πλάτος διαδρομής 128 bit). Πειράματα έδειξαν ότι στους σύγχρονους επεξεργαστές, η καταμέτρηση 16 νημάτων στους καταχωρητές YMM δεν δίνει κανένα κέρδος. Αλλά αυτό είναι μόνο προς το παρόν, σε νέα μοντέλα επεξεργαστών, η ταχύτητα των εντολών 256-bit θα αυξηθεί αναμφίβολα και, στη συνέχεια, η χρήση 16 παράλληλων νημάτων θα γίνει σκόπιμη και θα οδηγήσει σε ακόμη μεγαλύτερη αύξηση της ταχύτητας της κρυπτοδιαδικασίας.

Θεωρητικά, μπορείτε να υπολογίζετε σε ταχύτητα 600-700 megabyte ανά δευτερόλεπτο εάν ο επεξεργαστής έχει δύο FPU με πλάτος διαδρομής εργασίας 256 bit το καθένα. Σε αυτή την περίπτωση, μπορούμε να μιλήσουμε για τη σύνταξη κώδικα με απόδοση 16 RTT, και αυτό δεν είναι φαντασία, αλλά για το εγγύς μέλλον.

μικτή λειτουργία

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

Δεν μπορείτε να υπολογίζετε σε αύξηση 50% εδώ, το σημείο συμφόρησης είναι η μνήμη cache όπου αποθηκεύονται οι τεχνολογικές μάσκες, αλλά μπορείτε ακόμα να πάρετε μια αύξηση 100 επιπλέον megabyte. Αυτή η επιλογή δεν αναφέρεται στα παραρτήματα (οι μακροεντολές είναι ίδιες με αυτές που χρησιμοποιούνται στον κωδικό 8 RTT), αλλά είναι διαθέσιμη στο Αρχεια προγραμματος. Αν λοιπόν κάποιος δεν πιστεύει στη δυνατότητα κρυπτογράφησης με ταχύτητα 500 megabyte ανά δευτερόλεπτο σε έναν μόνο πυρήνα επεξεργαστή, ας τρέξει τα δοκιμαστικά αρχεία. Υπάρχουν και κείμενα με σχόλια για να μην πιστεύει κανείς ότι είμαι πονηρός.

Αυτή η εστίαση είναι δυνατή μόνο σε επεξεργαστές Intel, η AMD έχει μόνο δύο FPU ανά δύο μονάδες επεξεργαστή (ανάλογα με τη λειτουργία υπερ-διαπραγμάτευσης). Αλλά υπάρχουν τέσσερις ακόμη ALU, οι οποίες είναι αμαρτία να μην χρησιμοποιηθούν.

Μπορείτε να οδηγήσετε τις μονάδες επεξεργαστή του Bulldozer σε μια λειτουργία παρόμοια με τη λειτουργία υπερσυναλλαγών, αλλά να εκτελέσετε τη μετατροπή σε RON σε διαφορετικές μονάδες σε ένα νήμα και σε καταχωρητές SSE σε άλλο νήμα και να λάβετε το ίδιο 12 RTT. Δεν έχω δοκιμάσει αυτήν την επιλογή, αλλά νομίζω ότι ο κωδικός στο 12 RTT θα λειτουργεί πιο αποτελεσματικά στην AMD. Όσοι επιθυμούν μπορούν να δοκιμάσουν, τα δοκιμαστικά προγράμματα μπορούν να προσαρμοστούν ώστε να δουλεύουν στις "Μπουλντόζες" αρκετά εύκολα.

Ποιος το χρειάζεται;

Μια σοβαρή ερώτηση, αλλά με μια απλή απάντηση - όλοι τη χρειάζονται. Σύντομα θα καθίσουμε όλοι στα σύννεφα, θα αποθηκεύσουμε και δεδομένα και προγράμματα εκεί, και εκεί, ω, πώς θέλετε να εξοπλίσετε τη δική σας, ιδιωτική γωνιά. Για να γίνει αυτό, θα πρέπει να κρυπτογραφήσετε την κυκλοφορία και η ταχύτητα μετατροπής κρυπτογράφησης θα είναι ο κύριος καθοριστικός παράγοντας για την άνετη εργασία στο cloud. Η επιλογή μας για τον αλγόριθμο κρυπτογράφησης είναι μικρή - είτε GOST είτε AES.

Επιπλέον, παραδόξως, η κρυπτογράφηση του αλγόριθμου AES που είναι ενσωματωμένη στους επεξεργαστές αποδεικνύεται πολύ πιο αργή, οι δοκιμές δείχνουν ταχύτητα 100-150 megabyte ανά δευτερόλεπτο, και αυτό συμβαίνει με την εφαρμογή υλικού του αλγορίθμου! Το πρόβλημα έγκειται στην μέτρηση ενός νήματος και στο μπλοκ αντικατάστασης, το οποίο λειτουργεί σε byte (πίνακας 256 σειρών). Έτσι το GOST αποδεικνύεται πιο αποτελεσματικό στην εφαρμογή στην αρχιτεκτονική x86 / 64, ποιος θα πίστευε ...

Αυτό συμβαίνει εάν μιλάμε για το επιτυγχανόμενο επίπεδο ταχύτητας κρυπτογράφησης. Και αν έχουμε κατά νου τις θεωρητικές βελτιώσεις στον τομέα της βελτίωσης της αποτελεσματικότητας του κώδικα, τότε πιθανότατα κανείς δεν το χρειάζεται. Δεν υπάρχουν πρακτικά ειδικοί του επιπέδου 3-6 RTT, οι μεταγλωττιστές γενικά παράγουν κώδικα στο επίπεδο 1-2,5 RTT και η πλειοψηφία των προγραμματιστών δεν γνωρίζει assembler, και αν γνωρίζουν την ορθογραφία του, δεν καταλαβαίνουν τη συσκευή ενός σύγχρονος επεξεργαστής. Και χωρίς αυτή τη γνώση, τι είναι assembler, τι είναι κάποιο είδος SI-sharp - δεν έχει σημασία.

Αλλά δεν είναι όλα τόσο λυπηρά: στην «κατώτατη γραμμή» μετά από μια εβδομάδα άγρυπνων νυχτών υπάρχει ένας νέος αλγόριθμος για την εφαρμογή του GOST, ο οποίος είναι αμαρτία να μην κατοχυρωθεί με δίπλωμα ευρεσιτεχνίας. Και οι αιτήσεις για διπλώματα ευρεσιτεχνίας (έως και τρεις) έχουν ήδη συνταχθεί και κατατεθεί, οπότε κύριοι, επιχειρηματίες, παρατάξτε - γυναίκες και παιδιά έχουν έκπτωση.

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

Περιγραφή του αλγορίθμου

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

Ο αλγόριθμος GOST 28147-89 κρυπτογραφεί πληροφορίες σε μπλοκ των 64 bit, τα οποία χωρίζονται σε δύο υπομπλοκ των 32 bit (N1 και N2). Το υπομπλοκ N1 επεξεργάζεται με συγκεκριμένο τρόπο, μετά τον οποίο προστίθεται η αξία του

με την τιμή υπομπλοκ N2 (η προσθήκη εκτελείται modulo 2), στη συνέχεια τα υπομπλοκ ανταλλάσσονται. Ένας τέτοιος μετασχηματισμός εκτελείται για έναν ορισμένο αριθμό γύρων: 16 ή 32, ανάλογα με τον τρόπο λειτουργίας του αλγορίθμου (που περιγράφεται παρακάτω). Σε κάθε γύρο εκτελούνται οι ακόλουθες λειτουργίες:

1. Επικάλυψη κλειδιού. Το περιεχόμενο του υπομπλοκ /VI προστίθεται modulo 2 32 στο τμήμα Kx του κλειδιού.

Το κλειδί κρυπτογράφησης του αλγορίθμου GOST 28147-89 έχει διάσταση 256 bit και το Kx είναι το τμήμα 32 bit του, δηλαδή ένα κλειδί κρυπτογράφησης 256 bit αναπαρίσταται ως συνένωση δευτερευόντων κλειδιών 32 bit (Εικ. 3.2):

SH ATI, AG2, Yu, AG4, K5, Kb, K7.

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

Ρύζι. 3.1. Σχέδιο του αλγορίθμου GOST 28147-

Ρύζι. 3.2. Κλειδί κρυπτογράφησης του αλγορίθμου GOST 28147-89

2. Αντικατάσταση πίνακα. Μετά την επικάλυψη του κλειδιού, το υπομπλοκ /VI χωρίζεται σε 8 μέρη των 4 bit, η τιμή καθενός από τα οποία αντικαθίσταται ξεχωριστά σύμφωνα με τον πίνακα αντικατάστασης για αυτό το τμήμα του υπομπλοκ. Οι αντικαταστάσεις πινάκων (Substitution box, S-box) χρησιμοποιούνται συχνά σε σύγχρονους αλγόριθμους κρυπτογράφησης, επομένως αξίζει να τις εξετάσουμε με περισσότερες λεπτομέρειες.

Η αντικατάσταση πίνακα χρησιμοποιείται με αυτόν τον τρόπο: ένα μπλοκ δεδομένων συγκεκριμένης διάστασης (στην περίπτωση αυτή, 4-bit) τροφοδοτείται στην είσοδο, η αριθμητική αναπαράσταση του οποίου καθορίζει τον αριθμό της τιμής εξόδου. Για παράδειγμα, έχουμε ένα S-box της ακόλουθης μορφής:

4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.

Αφήστε το μπλοκ 4-bit "0100" να έρθει στην είσοδο, δηλαδή η τιμή είναι 4. Σύμφωνα με τον πίνακα, η τιμή εξόδου θα είναι 15, δηλ. "1111" (το 0 αντικαθίσταται από 4, το 1 αντικαθίσταται από 11, η τιμή του 2 δεν αλλάζει κ.λπ.).

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

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

3. Δυφική ​​κυκλική αριστερή μετατόπιση κατά 11 bit.

Τρόποι αλγορίθμων

Ο αλγόριθμος GOST 28147-89 έχει 4 τρόπους λειτουργίας:

□ απλή λειτουργία αντικατάστασης.

□ λειτουργία γάμμα.

Λειτουργία gaming P με ανατροφοδότηση.

□ τρόπος παραγωγής απομίμησης εξαρτημάτων.

Αυτοί οι τρόποι λειτουργίας είναι κάπως διαφορετικοί από τους γενικά αποδεκτούς (που περιγράφονται στην Ενότητα 1.4), επομένως αξίζει να τους εξετάσετε λεπτομερέστερα.

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

Εύκολη λειτουργία εναλλαγής

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

□ KO, Kl, K2, K3, K4, K5, Kb, AG7, KO, ATI, κ.λπ. - στους γύρους 1 έως 24.

□ K1, Kb, K5, K4, K3, K2, K\, KO - στους γύρους 25 έως 32.

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

□ KO, K\, K2, KZ, K4, K5, Kb, KP - στους γύρους 1 έως 8.

□ KP, Kb, K5, K4, K3, K2, K\, KO, K1, Kb, κ.λπ. - στους γύρους 9 έως 32.

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

Λειτουργία γάμμα

Στη λειτουργία γάμμα (Εικ. 3.3), κάθε μπλοκ του απλού κειμένου προστίθεται bit-bit modulo 2 στο μπλοκ γάμμα της κρυπτογράφησης με μέγεθος 64 bit. Το γάμμα κρυπτογράφησης είναι μια ειδική ακολουθία που δημιουργείται χρησιμοποιώντας τους μετασχηματισμούς που περιγράφονται παραπάνω ως εξής:

1. Στους καταχωρητές N1 και N2, γράφεται η αρχική τους πλήρωση - μια τιμή 64 bit, που ονομάζεται "μήνυμα συγχρονισμού" (ένα μήνυμα συγχρονισμού, στην πραγματικότητα, είναι ένα ανάλογο του διανύσματος αρχικοποίησης στις λειτουργίες CBC, CFB και OFB ).

2. Τα περιεχόμενα των καταχωρητών /VI και N2 (σε αυτήν την περίπτωση, μηνύματα συγχρονισμού) κρυπτογραφούνται στη λειτουργία απλής αντικατάστασης.

3. Τα περιεχόμενα του N1 προστίθενται modulo (2 32 - 1) με τη σταθερά CI = 2 24 + 2 16 + 2 8 + 4 , το αποτέλεσμα της πρόσθεσης γράφεται στον καταχωρητή /VI.

4. Το περιεχόμενο του N2 προστίθεται modulo 2 με τη σταθερά C2 = 2 24 + 2 16 + 2 8 +1, το αποτέλεσμα της πρόσθεσης γράφεται στον καταχωρητή N2.

5. Τα περιεχόμενα των καταχωρητών /VI και N2 εξάγονται ως μπλοκ γάμμα κρυπτογράφησης 64-bit (δηλαδή, σε αυτήν την περίπτωση, τα /VI και N2 αποτελούν το πρώτο μπλοκ γάμμα).

6. Εάν χρειάζεται το επόμενο μπλοκ γάμμα (δηλαδή, η κρυπτογράφηση ή η αποκρυπτογράφηση πρέπει να συνεχιστεί), επιστρέψτε στο βήμα 2.

Για την αποκρυπτογράφηση, δημιουργείται ένα γάμμα με τον ίδιο τρόπο και, στη συνέχεια, η λειτουργία XOR εφαρμόζεται ξανά στο κρυπτογραφημένο κείμενο και τα bit γάμμα.

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

Στις περισσότερες υλοποιήσεις του αλγορίθμου GOST 28147-89, το μήνυμα συγχρονισμού δεν είναι μυστικό στοιχείο, αλλά το μήνυμα συγχρονισμού μπορεί να είναι τόσο μυστικό όσο το κλειδί κρυπτογράφησης. Σε αυτήν την περίπτωση, μπορούμε να θεωρήσουμε ότι το ενεργό μήκος του κλειδιού αλγορίθμου (256 bit) αυξάνεται κατά άλλα 64 bit του μηνύματος συγχρονισμού, το οποίο μπορεί να θεωρηθεί ως ένα επιπλέον βασικό στοιχείο.

Λειτουργία γάμα ανατροφοδότησης

Στη λειτουργία γάμμα ανάδρασης, ξεκινώντας από το 2ο μπλοκ, οι καταχωρητές /VI και L/2 γεμίζονται όχι με το προηγούμενο μπλοκ γάμμα, αλλά με το αποτέλεσμα της κρυπτογράφησης του προηγούμενου μπλοκ απλού κειμένου (Εικ. 3.4). Το πρώτο μπλοκ σε αυτή τη λειτουργία δημιουργείται με τον ίδιο ακριβώς τρόπο όπως το προηγούμενο.

Ρύζι. 3.4. Δημιουργία του γάμμα κρυπτογράφησης στη λειτουργία γάμμα με ανατροφοδότηση

Λειτουργία δημιουργίας μιμητή

Η πλαστή είναι ένα κρυπτογραφικό άθροισμα ελέγχου που υπολογίζεται χρησιμοποιώντας ένα κλειδί κρυπτογράφησης και έχει σχεδιαστεί για να ελέγχει την ακεραιότητα των μηνυμάτων. Για τον υπολογισμό του, υπάρχει μια ειδική λειτουργία του αλγορίθμου GOST 28147-89.

Η δημιουργία του προθέματος απομίμησης εκτελείται ως εξής:

1. Το πρώτο μπλοκ πληροφοριών 64 bit, για το οποίο υπολογίζεται ο μιμητής, γράφεται στους καταχωρητές N1 και N2 και κρυπτογραφείται στη μειωμένη λειτουργία απλής αντικατάστασης, στην οποία εκτελούνται οι πρώτοι 16 γύροι από τους 32.

2. Το αποτέλεσμα που προκύπτει αθροίζεται modulo 2 με το επόμενο μπλοκ πληροφοριών, αποθηκεύοντας το αποτέλεσμα σε N1 και N2.

3. Τα M και N2 κρυπτογραφούνται ξανά στη μειωμένη λειτουργία απλής αντικατάστασης και ούτω καθεξής μέχρι το τελευταίο μπλοκ πληροφοριών.

Ένα πρόθεμα θεωρείται ότι είναι το περιεχόμενο 64-bit που προκύπτει από τους καταχωρητές N1 και N2 ή μέρος αυτών. Τις περισσότερες φορές, χρησιμοποιείται ένα πρόθεμα απομίμησης 32 bit, δηλαδή το ήμισυ των περιεχομένων των καταχωρητών. Αυτό είναι αρκετό, γιατί, όπως κάθε άθροισμα ελέγχου, το πρόθεμα απομίμησης προορίζεται κυρίως για την προστασία από τυχαία παραμόρφωση των πληροφοριών. Για την προστασία από σκόπιμη τροποποίηση δεδομένων, χρησιμοποιούνται άλλες κρυπτογραφικές μέθοδοι - κυρίως ηλεκτρονικές ψηφιακή υπογραφή(βλ. ενότητα 1.1).

Το πρόθεμα απομίμησης χρησιμοποιείται ως εξής:

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

2. Μετά την αποκωδικοποίηση, το πρόθεμα απομίμησης υπολογίζεται ξανά και συγκρίνεται με αυτό που αποστέλλεται.

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

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

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

Κρυπτογραφική ισχύς του αλγορίθμου

Το 1994, η περιγραφή του αλγορίθμου GOST 28147-89 μεταφράστηκε στα αγγλικά και δημοσιεύτηκε. Μετά από αυτό άρχισαν να εμφανίζονται τα αποτελέσματα της ανάλυσής του από ξένους ειδικούς. Ωστόσο, δεν βρέθηκαν επιθέσεις που να πλησιάζουν πρακτικά για σημαντικό χρονικό διάστημα.

□ μεγάλο μήκος κλειδιού - 256 bit. Μαζί με το μυστικό μήνυμα συγχρονισμού, το πραγματικό μήκος του κλειδιού αυξάνεται στα 320 bit.

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

Εξετάστε τα αποτελέσματα της κρυπτανάλυσης του αλγορίθμου GOST 28147-89.

Ανάλυση πινάκων αντικατάστασης

Δεδομένου ότι οι πίνακες αντικατάστασης δεν δίνονται στο πρότυπο, ένας αριθμός εργασιών (για παράδειγμα, στο) υποδηλώνει ότι ένας "αρμόδιος οργανισμός" μπορεί να εκδίδει και "καλούς" και "κακούς" πίνακες αντικατάστασης. Ωστόσο, ο διάσημος ειδικός Bruce Schneier αποκαλεί τέτοιες υποθέσεις «φήμες». Είναι σαφές ότι η κρυπτογραφική ισχύς του αλγορίθμου εξαρτάται σε μεγάλο βαθμό από τις ιδιότητες των πινάκων αντικατάστασης που χρησιμοποιούνται, αντίστοιχα, υπάρχουν ασθενείς πίνακες αντικατάστασης (δείτε παραπάνω για παράδειγμα), η χρήση των οποίων μπορεί να απλοποιήσει την επίθεση του αλγορίθμου. Ωστόσο, η δυνατότητα χρήσης διαφορετικών πινάκων αντικατάστασης φαίνεται να είναι μια πολύ αξιόλογη ιδέα, που υποστηρίζεται από τα ακόλουθα δύο γεγονότα από την ιστορία του προτύπου κρυπτογράφησης DES (βλ. Ενότητα 3.15 για λεπτομέρειες):

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

□ Έχουν γίνει προσπάθειες ενίσχυσης του DES έναντι της γραμμικής και διαφορικής κρυπτανάλυσης χρησιμοποιώντας ισχυρότερους πίνακες αντικατάστασης. Τέτοιοι πίνακες, που είναι όντως πιο σταθεροί, έχουν προταθεί, για παράδειγμα, στον αλγόριθμο s 5 DES. αλλά, δυστυχώς, ήταν αδύνατο να αντικατασταθεί το DES με το s 5 DES, καθώς οι πίνακες αντικατάστασης ορίζονται αυστηρά στο πρότυπο, αντίστοιχα, οι υλοποιήσεις του αλγορίθμου πιθανότατα δεν υποστηρίζουν τη δυνατότητα αλλαγής πινάκων σε άλλους.

Σε μια σειρά εργασιών (για παράδειγμα, και ) συμπεραίνεται λανθασμένα ότι οι πίνακες μυστικής αντικατάστασης του αλγορίθμου GOST 28147-89 μπορούν να αποτελούν μέρος του κλειδιού και να αυξήσουν το πραγματικό μήκος του (το οποίο δεν είναι σημαντικό, καθώς ο αλγόριθμος έχει πολύ μεγάλο κλειδί 256-bit). Ωστόσο, η εργασία αποδεικνύει ότι οι πίνακες μυστικής αντικατάστασης μπορούν να υπολογιστούν χρησιμοποιώντας την ακόλουθη επίθεση, η οποία μπορεί να εφαρμοστεί πρακτικά:

1. Ορίστε το κλειδί null και αναζητήστε το "null vector", δηλαδή την τιμή z = /(0), όπου /() είναι η στρογγυλή συνάρτηση του αλγορίθμου. Αυτό το στάδιο απαιτεί περίπου 2 λειτουργίες κρυπτογράφησης.

2. Χρησιμοποιώντας το μηδενικό διάνυσμα, υπολογίζονται οι τιμές των πινάκων αντικατάστασης, οι οποίες δεν χρειάζονται περισσότερες από 2 11 πράξεις.

Τροποποιήσεις αλγορίθμων και ανάλυσή τους

Στην εργασία, πραγματοποιήθηκε μια κρυπτανάλυση των τροποποιήσεων του αλγορίθμου GOST 28147-89:

□ τον αλγόριθμο GOST-H, στον οποίο, σε σχέση με τον αρχικό αλγόριθμο, αλλάζει η σειρά χρήσης των δευτερευόντων κλειδιών, δηλαδή, σε γύρους από την 25η έως την 32η δευτερεύουσα κλείδα χρησιμοποιούνται με άμεση σειρά, δηλαδή με τον ίδιο τρόπο όπως στην προηγούμενη γύροι του αλγορίθμου ;

□ Ένας αλγόριθμος GOST® 20 γύρων που χρησιμοποιεί XOR αντί για modulo 2 32 για επικάλυψη κλειδιού.

Με βάση τα αποτελέσματα της ανάλυσης, συνήχθη το συμπέρασμα ότι το GOST-H και το GOST© είναι πιο αδύναμα από τον αρχικό αλγόριθμο GOST 28147-89, καθώς και τα δύο έχουν κατηγορίες αδύναμων κλειδιών. Αξίζει να σημειωθεί ότι όσον αφορά την κρυπτανάλυση GOST©, το έργο επαναλαμβάνει λέξη προς λέξη την ενότητα για την κρυπτανάλυση του αλγορίθμου GOST 28147-89, που δημοσιεύτηκε το 2000 σε γνωστό έργο (χωρίς καμία αναφορά στο πρωτότυπο). Αυτό θέτει υπό αμφισβήτηση τον επαγγελματισμό των συγγραφέων του έργου και των άλλων αποτελεσμάτων του.

Μια πολύ ενδιαφέρουσα τροποποίηση του αλγορίθμου προτείνεται στην εργασία: οι πίνακες S \ ... Ss πρέπει απαραίτητα να είναι διαφορετικοί. σε κάθε γύρο του αλγορίθμου, πρέπει να μετατεθούν σύμφωνα με έναν συγκεκριμένο νόμο. Αυτή η μετάθεση μπορεί να εξαρτάται από το κλειδί κρυπτογράφησης ή μπορεί να είναι μυστική (δηλαδή, να αποτελεί μέρος ενός μεγαλύτερου κλειδιού κρυπτογράφησης από το αρχικό κλειδί 256-bit). Και οι δύο αυτές επιλογές, σύμφωνα με τους συγγραφείς τους, αυξάνουν σημαντικά την αντίσταση του αλγορίθμου έναντι της γραμμικής και της διαφορικής κρυπτανάλυσης.

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

Πλήρης Στρογγυλή Ανάλυση Αλγορίθμων

Υπάρχουν επίσης επιθέσεις στο πλήρες GOST 28147-89 χωρίς καμία τροποποίηση. Μία από τις πρώτες ανοιχτές εργασίες στις οποίες πραγματοποιήθηκε η ανάλυση του αλγορίθμου, μια πολύ γνωστή εργασία, είναι αφιερωμένη σε επιθέσεις που εκμεταλλεύονται αδυναμίες στη διαδικασία επέκτασης κλειδιού ενός αριθμού γνωστών αλγορίθμων κρυπτογράφησης. Συγκεκριμένα, ο πλήρης αλγόριθμος GOST 28147-89 μπορεί να σπάσει χρησιμοποιώντας διαφορική κρυπτανάλυση σε συνδεδεμένα κλειδιά, αλλά μόνο εάν χρησιμοποιούνται πίνακες ασθενούς αντικατάστασης. Η έκδοση 24 γύρων του αλγορίθμου (η οποία δεν έχει τους πρώτους 8 γύρους) ανοίγει με τον ίδιο τρόπο για όλους τους πίνακες αντικατάστασης, αλλά οι ισχυροί πίνακες αντικατάστασης (για παράδειγμα, δίνονται στο ) καθιστούν μια τέτοια επίθεση απολύτως μη πρακτική.

Οι εγχώριοι επιστήμονες A. G. Rostovtsev και E. B. Makhovenko το 2001 πρότειναν μια θεμελιωδώς νέα μέθοδο κρυπτανάλυσης (σύμφωνα με τους συγγραφείς, είναι σημαντικά πιο αποτελεσματική από τη γραμμική και διαφορική κρυπτανάλυση) διαμορφώνοντας μια αντικειμενική συνάρτηση από ένα γνωστό απλό κείμενο που αντιστοιχεί σε αυτό κρυπτοκείμενο και την επιθυμητή τιμή του κλειδιού και βρίσκοντας το άκρο του που αντιστοιχεί στην πραγματική τιμή του κλειδιού. Βρήκαν επίσης μια μεγάλη κατηγορία αδύναμων πλήκτρων του αλγόριθμου GOST 28147-89, τα οποία σας επιτρέπουν να ανοίξετε τον αλγόριθμο χρησιμοποιώντας μόνο 4 επιλεγμένα απλά κείμενα και τα αντίστοιχα κρυπτογραφημένα κείμενα με αρκετά χαμηλή πολυπλοκότητα. Η κρυπτανάλυση του αλγορίθμου συνεχίζεται στην εργασία.

Το 2004, μια ομάδα ειδικών από την Κορέα πρότεινε μια επίθεση με την οποία, χρησιμοποιώντας διαφορική κρυπτανάλυση σε συσχετισμένα κλειδιά, είναι δυνατό να ληφθούν με πιθανότητα 91,7% 12 bit ενός μυστικού κλειδιού. Η επίθεση απαιτεί 235 επιλεγμένα απλά κείμενα και 236 λειτουργίες κρυπτογράφησης. Όπως φαίνεται, αυτή η επίθεση, είναι πρακτικά άχρηστο για το πραγματικό άνοιγμα του αλγορίθμου.