Inländischer Datenverschlüsselungsstandard. Nationaler Datenverschlüsselungsstandard Kryptografischer Konvertierungsalgorithmus GOST 28147 89

Kurze Beschreibung der Chiffre

GOST 28147-89 - Sowjetischer und russischer Standard für symmetrische Verschlüsselung, eingeführt 1990, ist auch ein CIS-Standard. Vollständiger Name - „GOST 28147-89 Informationsverarbeitungssysteme. Kryptografischer Schutz. Kryptografischer Transformationsalgorithmus“. Blockverschlüsselungsalgorithmus. Bei Verwendung des Verschlüsselungsverfahrens mit Gamma kann es die Funktionen eines Stromverschlüsselungsalgorithmus ausführen.

GOST 28147-89 ist eine Blockverschlüsselung mit einem 256-Bit-Schlüssel und 32 Konvertierungszyklen, die mit 64-Bit-Blöcken arbeitet. Grundlage des Chiffrieralgorithmus ist das Feistel-Netzwerk. Der grundlegende Verschlüsselungsmodus gemäß GOST 28147-89 ist der einfache Ersetzungsmodus (es werden auch komplexere Modi definiert - Gamma, Gamma mit Rückmeldung und simulierter Einfügemodus).

Wie der Algorithmus funktioniert

Der Algorithmus unterscheidet sich nicht grundlegend von DES. Es enthält auch Verschlüsselungszyklen (es gibt 32 davon) nach dem Feistel-Schema (Abb. 2.9.).

Reis. 2.9. Verschlüsselungsrunden des GOST 28147-89-Algorithmus.

Um Unterschlüssel zu erzeugen, wird der ursprüngliche 256-Bit-Schlüssel in acht 32-Bit-Blöcke unterteilt: k 1 …k 8 . Die Schlüssel k 9 ... k 24 sind eine zyklische Wiederholung der Schlüssel k 1 ... k 8 (nummeriert von den niederwertigsten Bits zu den höchstwertigen). Die Tasten k 25 ... k 32 sind die Tasten k 1 ... k 8 in umgekehrter Reihenfolge.

Nachdem alle 32 Runden des Algorithmus abgeschlossen sind, werden die Blöcke A 33 und B 33 zusammengeklebt (man beachte, dass A 33 das höchstwertige Bit wird und B 33 das niedrigstwertige Bit wird) – das Ergebnis ist das Ergebnis des Algorithmus.

Funktion F(A ich ,K ich) wird wie folgt berechnet: A i und K i werden modulo 2 32 addiert, dann wird das Ergebnis in acht 4-Bit-Teilsequenzen geteilt, von denen jede dem eigenen Eingang zugeführt wird Substitutionstabellenknoten(in aufsteigender Reihenfolge der Bitpriorität), unten genannt S-Block. Die Gesamtzahl der GOST-S-Blöcke ist acht, d. h. gleich der Anzahl der Untersequenzen. Jeden S-Block stellt eine Permutation von Zahlen von 0 bis 15 dar. Die erste 4-Bit-Teilfolge fällt auf den Eingang der ersten S-Box, die zweite auf den Eingang der zweiten usw. Die Ausgänge aller acht S-Boxen werden kombiniert B. ein 32-Bit-Wort, dann wird das ganze Wort zyklisch um 11 Bit nach links (zu den höchstwertigen Bits) verschoben. Alle acht S-Boxen können unterschiedlich sein. Tatsächlich können sie zusätzliches Schlüsselmaterial sein, aber häufiger sind sie ein Schemaparameter, der einer bestimmten Gruppe von Benutzern gemeinsam ist. Aus dem Text der Norm geht hervor, dass die Lieferung der Befüllung von Ersatzeinheiten (S-Blöcken) in der vorgeschriebenen Weise erfolgt, d.h. Algorithmus-Entwickler. Die Gemeinschaft der russischen CIPF-Entwickler einigte sich auf die im Internet verwendeten Ersatzknoten.

Die Entschlüsselung wird auf die gleiche Weise wie die Verschlüsselung durchgeführt, aber die Reihenfolge der Unterschlüssel k i ist umgekehrt.

Betriebsarten des Algorithmus GOST 28147-89

Der GOST 28147-89-Algorithmus hat vier Betriebsmodi.

1. Moduseinfacher Austausch akzeptiert Daten als Eingabe, deren Größe ein Vielfaches von 64 Bit ist. Das Ergebnis der Verschlüsselung ist der Eingangstext, der im Fall der Verschlüsselung mit dem "32-3"-Zyklus und im Fall der Entschlüsselung - mit dem "32-P"-Zyklus in Blöcke von 64 Bit umgewandelt wird.

2. ModusSkalierung akzeptiert Daten beliebiger Größe als Eingabe sowie einen zusätzlichen 64-Bit-Parameter - Nachricht synchronisieren. Während des Betriebs wird die Sync-Nachricht im "32-Z"-Zyklus umgewandelt, das Ergebnis wird in zwei Teile geteilt. Der erste Teil wird modulo 2 32 mit einem konstanten Wert von 1010101 16 addiert. Wenn der zweite Teil gleich 2 32 –1 ist, ändert sich sein Wert nicht, andernfalls wird er modulo 2 32 –1 mit einem konstanten Wert von 1010104 16 addiert. Der Wert, der durch Kombinieren beider konvertierter Teile erhalten wird, wird als Chiffre-Gamma bezeichnet und tritt in die "32-3"-Schleife ein, ihr Ergebnis wird bitweise Modulo 2 mit einem 64-Bit-Block von Eingangsdaten addiert. Wenn letzterer kleiner als 64 Bit ist, werden die zusätzlichen Bits des empfangenen Werts verworfen. Der resultierende Wert wird an den Ausgang gesendet. Wenn noch Daten eintreffen, wird die Aktion wiederholt: Der aus 32-Bit-Teilen bestehende Block wird in Teile umgewandelt und so weiter.

3. ModusSkalierung mit Feedback akzeptiert auch Daten beliebiger Größe und eine Synchronisierungsnachricht als Eingabe. Der Eingangsdatenblock wird bitweise modulo 2 mit dem Ergebnis der Transformation im Zyklus "32-3" der Sync-Nachricht addiert. Der resultierende Wert wird an den Ausgang gesendet. Der Wert der Sync-Nachricht wird im Fall der Verschlüsselung durch den Ausgangsblock und im Fall der Entschlüsselung durch den Eingang ersetzt, d. h. verschlüsselt. Wenn der letzte Block eingehender Daten kleiner als 64 Bit ist, dann werden die zusätzlichen Bits des Gammas (Ausgang der "32-3"-Schleife) verworfen. Wenn noch Daten eingehen, wird die Aktion wiederholt: Die Gamma-Chiffre wird aus dem Ergebnis der Verschlüsselung des ersetzten Werts gebildet und so weiter.

4. Produktionsmodusnachgemachte Einsätze nimmt Eingabedaten, die mindestens zwei volle 64-Bit-Blöcke groß sind, und gibt einen 64-Bit-Datenblock zurück, der als Einfügungsidentitätswechsel bezeichnet wird. Der temporäre 64-Bit-Wert wird auf 0 gesetzt, dann wird er, solange Eingabedaten vorhanden sind, bitweise modulo 2 mit dem Ergebnis der Ausführung des "16-3"-Zyklus addiert, dessen Eingabe der Block von Eingabedaten ist . Nach dem Ende der Eingabe wird als Ergebnis der temporäre Wert zurückgegeben.

Kryptoanalyse der Chiffre

Die GOST 28147-89-Chiffre verwendet einen 256-Bit-Schlüssel und die Größe des Schlüsselraums beträgt 2256 . Kein derzeit existierender Allzweckcomputer kann in weniger als vielen hundert Jahren einen Schlüssel erraten. Der russische Standard GOST 28147-89 wurde mit großem Vorsprung konzipiert und übertrifft mit seiner realen Schlüsselgröße von 56 Bit und dem Volumen des Schlüsselraums von nur 2 56 den amerikanischen DES-Standard um viele Größenordnungen.

Es gibt auch Angriffe auf die Vollrunde GOST 28147-89 ohne Änderungen. Einer der Ersten offene Werke, in dem die Analyse des Algorithmus durchgeführt wurde, nutzt die Schwächen des Schlüsselerweiterungsverfahrens einiger bekannter Verschlüsselungsalgorithmen. Insbesondere der Full-Round-Algorithmus GOST 28147-89 kann durch differenzielle Kryptoanalyse auf verknüpften Schlüsseln gebrochen werden, aber nur, wenn schwache Substitutionstabellen verwendet werden. Die 24-Runden-Version des Algorithmus (der die ersten 8 Runden fehlen) wird auf die gleiche Weise für beliebige Auswechslungstabellen geöffnet, jedoch machen starke Auswechslungstabellen einen solchen Angriff völlig unpraktisch.

Hauswissenschaftler A.G. Rostovtsev und E.B. Makhovenko schlug 2001 eine grundlegend neue Methode der Kryptoanalyse vor, indem er aus einem bekannten Klartext, dem zugehörigen Chiffretext und dem gewünschten Schlüsselwert eine objektive Funktion bildete und ihr Extremum fand, das dem wahren Wert des Schlüssels entspricht. Sie fanden auch eine große Klasse schwacher Schlüssel des GOST 28147-89-Algorithmus, die es Ihnen ermöglichen, den Algorithmus mit nur 4 ausgewählten Klartexten und ihren entsprechenden Chiffretexten mit relativ geringer Komplexität zu öffnen.

Im Jahr 2004 schlug eine Expertengruppe aus Korea einen Angriff vor, bei dem es möglich ist, mit einer Wahrscheinlichkeit von 91,7 % einen 12-Bit-Geheimschlüssel zu erhalten, indem eine differenzielle Kryptoanalyse auf zugehörigen Schlüsseln verwendet wird. Der Angriff erfordert 235 ausgewählte Klartexte und 236 Verschlüsselungsoperationen. Wie Sie sehen können, ist dieser Angriff für die eigentliche Öffnung des Algorithmus praktisch nutzlos.

Die Vertretungstabelle ist ein langfristiges Schlüsselelement, das heißt, sie gilt für viel mehr langfristig als ein einzelner Schlüssel. Es wird angenommen, dass es allen Verschlüsselungsknoten innerhalb eines kryptografischen Schutzsystems gemeinsam ist. Die Qualität dieser Tabelle bestimmt die Qualität der Chiffre. Bei einer "starken" Substitutionstabelle fällt die Stärke der Chiffre nicht unter eine bestimmte akzeptable Grenze, selbst wenn sie offengelegt wird. Umgekehrt kann die Verwendung einer "schwachen" Tabelle die Stärke der Chiffre auf eine unannehmbar niedrige Grenze reduzieren. Keine Angaben zur Qualität der Auswechslungstabelle in offenes Siegel Russland wurde nicht veröffentlicht, aber die Existenz "schwacher" Tabellen steht außer Zweifel - ein Beispiel ist die "triviale" Substitutionstabelle, bei der jeder Wert durch sich selbst ersetzt wird. In einer Reihe von Arbeiten wird fälschlicherweise der Schluss gezogen, dass die geheimen Substitutionstabellen des GOST 28147-89-Algorithmus Teil des Schlüssels sein und seine effektive Länge erhöhen können (was nicht signifikant ist, da der Algorithmus einen sehr großen 256-Bit-Schlüssel hat ).

Verschlüsselungsalgorithmus GOST 28147-89. Einfache Substitutionsmethode. — Archiv WASM.RU

„Während du lebst, stirb nicht, sieh dir diese Welt an.
Viele hier haben eine tote Seele – sie sind innerlich tot.
Aber sie gehen und lachen, ohne zu wissen, dass sie nicht da sind,
Überstürzen Sie Ihren Tod nicht", sagte sie mir.

Arie „Da oben“

2.1 Feistel-Netzwerke.
2.2 Blockchiffre GOST 28147-89

3.1 Schlüsselinformation
3.2 Der Hauptschritt der Krypto-Transformation

3.3 Grundzyklen:“ 32-Z” , “ 32-R” .

4.1 Implementierung des Hauptschritts der Kryptotransformation
4.2 Erhöhung der Geschwindigkeit des Algorithmus
5. Wichtige Informationsanforderungen
6. Verzeichnis der verwendeten Literatur
7. Danke.

Einführung.

Dieses Dokument ist mein Versuch, die Methode zum einfachen Ersetzen des Verschlüsselungsalgorithmus GOST 28147-89 in der einfachsten, aber dennoch technisch versierten Sprache zu beschreiben. Wie gut mir das gelungen ist, wird der Leser nach Lektüre der ersten sechs Punkte beurteilen.

Damit meine Arbeit zu geben mehr Nutzen Ich empfehle, sich mit den Werken der in der Liste der verwendeten Literatur angegebenen Autoren zu bewaffnen. Empfehlenswert ist auch ein Taschenrechner, damit dieser über eine Funktion zur Berechnung der Operation verfügt XOR, Weil Beim Lesen des Artikels wird davon ausgegangen, dass der Leser diesen Verschlüsselungsalgorithmus studieren möchte. Obwohl es sich auch als Nachschlagewerk eignet, habe ich diesen Artikel genau als Tutorial geschrieben.

Einführung in Blockchiffren.

Bevor wir uns mit dem Algorithmus befassen, müssen wir uns mit der Entstehungsgeschichte dieser Art von Verschlüsselung vertraut machen. Der Algorithmus gehört zur Kategorie der Blockchiffren, in deren Architektur die Informationen in eine endliche Anzahl von Blöcken aufgeteilt werden, wobei der letzte natürlich nicht vollständig sein darf. Der Verschlüsselungsprozess findet genau über die vollständigen Blöcke statt, die den Chiffretext bilden. Der letzte Block wird, wenn er unvollständig ist, um etwas ergänzt (ich werde weiter unten auf die Nuancen seiner Hinzufügung eingehen) und wird auf die gleiche Weise wie vollständige Blöcke verschlüsselt. Mit Chiffretext meine ich - das Ergebnis der Aktion der Verschlüsselungsfunktion auf eine bestimmte Datenmenge, die der Benutzer zur Verschlüsselung übermittelt hat. Mit anderen Worten, der Chiffretext ist das Endergebnis der Verschlüsselung.

Die Geschichte der Entwicklung von Blockchiffren ist mit dem Beginn der 70er Jahre verbunden, als IBM die Notwendigkeit erkannte, Informationen bei der Datenübertragung über Computerkommunikationskanäle zu schützen, und mit der Implementierung begann eigenes Programm wissenschaftliche Forschung dem Schutz von Informationen in elektronischen Netzen gewidmet, einschließlich Kryptografie.

Unter der Leitung von Dr. Horst Festel.

2.1 Feistel-Netzwerke

Die Architektur des von Feistel vorgeschlagenen neuen Verschlüsselungsverfahrens wurde in der klassischen Literatur jedoch als „Feistel-Architektur“ bezeichnet dieser Moment In der russischen und ausländischen Literatur wird ein etablierterer Begriff verwendet - "Feistels Netzwerk" oder Feistels Netzwerk. Anschließend wurde gemäß dieser Architektur die "Lucifer"-Chiffre gebaut - die später veröffentlicht wurde und eine neue Welle des Interesses an der Kryptographie im Allgemeinen auslöste.

Die Idee der Feistel-Netzwerkarchitektur ist folgende: Der Eingangsinformationsstrom wird in Blöcke von n Bits Größe aufgeteilt, wobei n eine gerade Zahl ist. Jeder Block wird in zwei Teile geteilt - L und R, dann werden diese Teile in eine iterative Blockchiffre eingespeist, in der das Ergebnis der j-ten Stufe durch das Ergebnis der vorherigen Stufe j-1 bestimmt wird! Dies lässt sich an einem Beispiel veranschaulichen:

Reis. 1

Wobei Funktion A die Hauptaktion der Blockchiffre ist. Es kann eine einfache Aktion sein, wie z. B. eine XOR-Operation, oder es kann ein komplexeres Aussehen haben, eine Folge einer Reihe einfacher Aktionen sein - Modulo-Addition, Linksverschiebung, Elementersetzung usw., insgesamt diese einfache Schritte bilden die sogenannte - der Hauptschritt der Krypto-Transformation.

Es sollte beachtet werden, dass die Schlüsselelemente der Funktion die Lieferung von Schlüsselelementen und die XOR-Operation sind, und wie gut durchdacht die Arbeit dieser Operationen ist, spricht für die kryptografische Stärke der Chiffre als Ganzes.

Damit die Idee der Feistel-Netzwerke vollständig klar wird, betrachten Sie den einfachsten Fall, der in Abb. Reis. 1, wobei in der Funktion A - die Operationen „mod 2“ („xor“) ausgeführt werden, aber dies Protozoon In einem ernsteren Fall, beispielsweise beim Verbergen von Informationen von nationaler Bedeutung, kann Funktion A komplexer sein (soweit ich gesehen habe, kann Funktion A tatsächlich sehr kompliziert sein):

Ausgangsdaten:

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

Holen Sie sich einen Chiffretext

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

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

3. L=R, R=Sxoder

L=0101b, R=1010b

Lassen Sie uns unsere Schritte erklären:

1. Diese Operation ist Addition mod 2 4 . In der Praxis läuft eine solche Operation auf eine einfache Addition hinaus, bei der wir zwei Zahlen addieren und den Übertrag zur 5. Ziffer ignorieren müssen. Da, wenn wir Exponenten über die Ziffern der binären Darstellung einer Zahl setzen, ein Indikator von vier über der fünften Ziffer steht, sehen Sie sich die folgende Abbildung an, die die Aktionen unserer Operation zeigt:

Reis. 2

Hier habe ich mit einem Pfeil auf die Exponenten gezeigt, wie Sie sehen, hätte das Ergebnis 10100 sein sollen, aber da der Übertrag während der mod 2 4-Operation ignoriert wird, erhalten wir 0100.

2. Diese Operation wird in der Literatur mod 2 genannt, in der Assemblersprache wird sie durch den Befehl implementiert XOR. Aber sie mehr korrekter Name Mod 2 1 . Ohne diese einzigartige Operation ist es kaum möglich, einen schnellen, einfach zu implementierenden Verschlüsselungsalgorithmus zu entwickeln und gleichzeitig ziemlich kryptoresistent zu sein. Die Einzigartigkeit dieser Operation liegt darin, dass sie die Umkehrung ihrer selbst ist! Wenn zum Beispiel die Zahl A mit der Zahl B XOR-verknüpft wird, ist das Ergebnis C, in Zukunft reicht es aus, die Zahlen B und C erneut mit XOR zu verknüpfen, um den vorherigen Wert von A zu erhalten!

Bei dieser Operation haben wir 1010 mit den Nummern 1110 und 0100, um 1110 zurückzubekommen, reicht es aus, die Nummern 0100 und 1010 mit XOR zu verknüpfen! Weitere Details zu diesem Vorgang finden Sie im Artikel, der auf der Website eingebettet ist. www.wasm.ru, « Grundlegende Anleitung zuCRC_Fehlererkennungsalgorithmen» der Autor, der Ross N. Williams. Es gibt einen Absatz in dieser Arbeit - " 5. Binäre Arithmetik ohne Überweisungen". In diesem Artikel wird die Operation beschrieben xoder! Ich rufe aus, weil in diesem Artikel diese Operation so beschrieben wird, dass der Leser nicht nur versteht, wie diese Operation funktioniert, sondern sogar damit beginnt sehen, hören und fühlen!

3. Diese Aktion ist notwendig, damit Sie beim Entschlüsseln aus dem Chiffretext die ursprünglichen Werte erhalten.

2.2 Blockverschlüsselung GOST 28147-89

Der Verschlüsselungsalgorithmus GOST 28147 - 89 gehört zur Kategorie der Blockchiffren, die auf der Feistel-Balanced-Network-Architektur arbeiten, bei der zwei Teile des ausgewählten Informationsblocks gleich groß sind. Der Algorithmus wurde in den Tiefen der achten Abteilung des KGB entwickelt, jetzt in FAPSI umgewandelt und als Verschlüsselungsstandard festgelegt. Russische Föderation 1989 unter der UdSSR.

Damit diese Methode des Algorithmus funktioniert, ist es notwendig, die Informationen in Blöcke mit einer Größe von 64 Bit aufzuteilen. Generieren oder geben Sie die folgenden Schlüsselinformationen in das Verschlüsselungssystem ein: Schlüssel und Substitutionstabelle. Die Wahl des Schlüssels und der Substitutionstabelle für die Verschlüsselung sollte sehr ernst genommen werden, weil. Dies ist die Grundlage für die Sicherheit Ihrer Informationen. Informationen zu den Anforderungen an den Schlüssel und die Substitutionstabelle finden Sie im Abschnitt "Anforderungen an Schlüsselinformationen".

Bei der Betrachtung der Methode werden wir uns nicht darauf konzentrieren, weil. Dieser Artikel wurde, wie ich oben sagte, mit dem Ziel geschrieben, dem Leser beizubringen, wie man Daten mit der einfachen Ersetzungsmethode verschlüsselt dieser Algorithmus Verschlüsselung, aber wir werden dieses Thema definitiv am Ende des Artikels ansprechen.

Theoretisches Minimum.

3.1 Wichtige Informationen

Wie ich oben sagte, sind die folgenden Personen aktiv an der Datenverschlüsselung beteiligt:

3.1.1. Der Schlüssel ist eine Folge von acht Elementen mit jeweils 32 Bit. Außerdem bezeichnen wir das Symbol K und die Elemente, aus denen es besteht - k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Die Substitutionstabelle ist eine Matrix aus acht Zeilen und sechzehn Spalten, im Folgenden als Hij bezeichnet. Jedes Element am Schnittpunkt von Zeile i und Spalte j benötigt 4 Bits.

3.2 Der Hauptschritt der Kryptotransformation

Die Hauptaktion im Verschlüsselungsprozess ist der Hauptschritt der Kryptotransformation. Das ist nichts anderes als eine Aktion, um Daten mit einem bestimmten Algorithmus zu verschlüsseln, nur der von den Entwicklern eingeführte Name war zu umständlich.

Bevor mit der Verschlüsselung begonnen wird, wird der Block in zwei Teile L und R mit jeweils 32 Bit aufgeteilt. Das Schlüsselelement wird ausgewählt und erst dann werden diese beiden Teile des Blocks eingespeist, das Schlüsselelement ist die Substitutionstabelle in die Hauptschrittfunktion, das Ergebnis des Hauptschritts ist eine Iteration des Basiszyklus, die im Abschnitt besprochen wird nächsten Absatz. Der Hauptschritt besteht aus den folgenden Schritten:

1. Der Additionsteil des Blocks R wird zum Schlüsselelement K mod 2 32 addiert. Ich habe oben eine ähnliche Operation beschrieben, hier ist das Gleiche, nur dass der Exponent nicht „4“, sondern „32“ ist - das Ergebnis dieser Operation wird in Zukunft mit Smod bezeichnet.
2. Wir teilen das zuvor erhaltene Ergebnis Smod in vier Bitelemente s7, s6, s5, s4, s3, s2, s1, s0 und speisen es in die Ersetzungsfunktion ein. Die Ersetzung ist wie folgt: Das Element Smod - s i wird ausgewählt, wir beginnen von Anfang an mit dem niedrigsten Element und ersetzen es durch den Wert aus der Substitutionstabelle für die i - Zeile und Spalte, die durch den Wert des Elements s i angegeben sind. Wir gehen zum Element s i +1 über und machen dasselbe und fahren fort, bis wir den Wert des letzten Elements Smod ersetzen – das Ergebnis dieser Operation wird als Ssimple bezeichnet.
3. Bei dieser Operation wird der Wert von Ssimple zyklisch um 11 Bit nach links verschoben und wir erhalten Srol.
4. Wir wählen den zweiten Teil des Blocks L aus und fügen Mod 2 mit Srol hinzu, als Ergebnis haben wir Sxor.
5. In diesem Stadium wird der L-Teil des Blocks gleich dem Wert des R-Teils, und der R-Teil wird wiederum mit dem Ergebnis von Sxor initialisiert, und dies vervollständigt die Hauptschrittfunktion!

3.3 Grundzyklen: „32-Z“, „32-R“.

Um Informationen zu verschlüsseln, ist es notwendig, sie in Blöcke mit einer Größe von 64 Bit aufzuteilen, natürlich kann der letzte Block weniger als 64 Bit umfassen. Diese Tatsache ist die Achillesferse dieser "einfachen Substitutions"-Methode. Da seine Erweiterung auf 64 Bit eine sehr wichtige Aufgabe ist, um die kryptografische Stärke des Chiffretextes zu erhöhen, ist dieser sensible Ort, wenn er in der Informationsmatrix vorhanden ist, aber möglicherweise nicht vorhanden ist (z. B. eine Datei mit einer Größe von 512 Byte !), sollte mit großer Verantwortung behandelt werden!

Nachdem Sie die Informationen in Blöcke aufgeteilt haben, sollten Sie den Schlüssel in Elemente aufteilen:

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

Die Verschlüsselung selbst besteht in der Verwendung sogenannter Basiszyklen. Diese wiederum beinhalten die n-te Anzahl grundlegender Kryptotransformationsschritte.

Grundzyklen sind sozusagen gekennzeichnet: n - m. Wobei n die Anzahl der grundlegenden Kryptotransformationsschritte in der Basisschleife ist und m der "Typ" der Basisschleife ist, d.h. worum geht es, "Z"-Verschlüsselung oder "R"-Verschlüsselung von Daten.

Der grundlegende Verschlüsselungszyklus 32–3 besteht aus 32 grundlegenden kryptographischen Schritten. Der Block N und das Element des Schlüssels K werden in die Funktion eingespeist, die die Aktionen des Schritts implementiert, und der erste Schritt erfolgt mit k1, der zweite über das Ergebnis mit dem Element k2 usw. nach folgendem Schema:

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

Der 32-P-Entschlüsselungsprozess läuft ähnlich ab, aber die Schlüsselelemente werden in umgekehrter Reihenfolge zugeführt:

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

Üben.

4.1 Implementierung des Hauptschritts der Kryptotransformation

Nachdem wir uns mit der Theorie zum Verschlüsseln von Informationen vertraut gemacht haben, ist es an der Zeit zu sehen, wie die Verschlüsselung in der Praxis funktioniert.

Ausgangsdaten:

Nehmen wir einen Informationsblock N = 0102030405060708h, hier sind die Teile L und R gleich:

L = 01020304h, R = 05060708h, nimm den Schlüssel:

K=' als28 zw37 q839 7342ui23 8e2t wqm2 ewp1' (dies sind ASCII-Codes, um die hexadezimale Darstellung zu sehen, können Sie diese Datei im Ansichtsmodus öffnen in Totaler Kommandant Drücken der Taste " F3“ und dann die Taste „ 3 "). In diesem Schlüssel sind die Elementwerte:

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

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

Nehmen Sie auch die folgende Substitutionstabelle:

Reis. 3

Hier sind die Zeilen von 0 bis 7 nummeriert, die Spalten von 0 bis F.

Warnung: Alle Angaben, auch der Schlüssel mit der Substitutionstabelle, sind beispielhaft für die Betrachtung des Algorithmus!

Unter Verwendung der "Anfangsdaten" müssen Sie das Ergebnis der Aktion des Hauptschritts der Kryptotransformation erhalten.

1. Wählen Sie Teil R = 05060708h und Schlüsselelement k1 = „as28“, in hexadezimaler Form sieht das Schlüsselelement so aus: 61733238h. Jetzt führen wir die Operation von Summation mod 2 32 durch:

Reis. 4

Wie Sie in der Abbildung sehen können, haben wir nicht auf 33 Bit übertragen, die rot und mit dem Exponenten " 32 ". Und wenn wir andere Werte von R und dem Schlüsselelement hätten, könnte das durchaus passieren, und dann würden wir das ignorieren und in Zukunft nur noch die gelb markierten Bits verwenden.

Ich führe eine solche Operation mit dem Assembler-Befehl aus hinzufügen:

; eax=R, ebx='as28'

Das Ergebnis dieser Operation ist Smod = 66793940h

2. Jetzt die komplizierteste Operation, aber wenn Sie genau hinsehen, ist sie nicht mehr so ​​​​beängstigend, wie es zunächst scheint. Stellen wir uns Smod in folgender Form vor:

Reis. 5

Ich habe versucht, die Smod-Elemente in der Abbildung zu visualisieren, aber ich erkläre es trotzdem:

s0 = 0, s1 = 4, s2 = 9 usw.

Nun führen wir ausgehend vom niedrigsten Element s0 eine Ersetzung durch. Erinnere dich an den Absatz 3.2 Der Hauptschritt der Krypto-Transformation» i ist eine Zeile, s i ist eine Spalte, wir suchen einen Wert in der Nullzeile und Nullspalte:

Abb.6

Der aktuelle Wert von Smod ist also nicht 6679394 0 h und 6679394 5 H.

Wir fahren fort, s1 zu ersetzen, d.h. vier. Verwenden Sie die erste Zeile und die vierte Spalte (s1= 4!). Schauen wir uns das Bild an:

Reis. 7

Jetzt ist der Wert Smod, nicht 667939 4 5h, 667939 2 5 Std. Ich gehe davon aus, dass der Ersetzungsalgorithmus dem Leser jetzt klar ist, und ich kann sagen, dass das Endergebnis von Ssimple den folgenden Wert haben wird - 11e10325h.

Wie dies am einfachsten in Form von Assembler-Befehlen zu implementieren ist, werde ich später im nächsten Absatz erläutern, nachdem ich über die erweiterte Tabelle gesprochen habe.

1. Wir müssen den resultierenden Ssimple-Wert um 11 Bit nach links verschieben.

Reis. 8

Wie Sie sehen können, ist diese Aktion ziemlich einfach und wird durch einen Assembler-Sprachbefehl implementiert - rollen und das Ergebnis dieser Srol-Operation ist 0819288Fh.

4. Nun bleibt Teil L unseres Informationsblocks zu XOR mit dem Wert Srol. Ich nehme Rechner von w2k sp4 und erhalte Sxor = 091b2b8bh.

5. Diese Aktion ist endgültig und wir weisen einfach R den Wert des L-Teils zu, bereinigen ihn und initialisieren den L-Teil mit dem Wert von Sxor.

Endergebnis:

L=091b2b8bh, R=01020304h

4.2 Erhöhung der Geschwindigkeit des Algorithmus

Lassen Sie uns nun über die Optimierung des Algorithmus für Geschwindigkeit sprechen. Bei der Umsetzung eines Projekts muss man berücksichtigen, dass ein Programm, das öfter mit Registern als mit Speicher arbeitet, am schnellsten arbeitet, und hier ist diese Einschätzung auch sehr wichtig, denn. über einen Informationsblock bis zu 32 Verschlüsselungsschritte!

Als ich den Verschlüsselungsalgorithmus in mein Programm implementiert habe, habe ich Folgendes getan:

1. Ausgewählter Teil des Blocks L im eax-Register und R im edx.

2. Initialisiert in das esi-Register mit der Adresse des erweiterten Schlüssels, mehr dazu weiter unten.

3. Ich habe dem ebx-Register den Wert der Adresse der erweiterten Substitutionstabelle zugewiesen, mehr dazu weiter unten

4. Übergeben Sie die Informationen der Punkte 1,2, 3 an die Funktion des Grundzyklus 32 - Z oder 32 - R, je nach Situation.

Wenn Sie sich das Schema zur Bereitstellung von Schlüsselelementen im Absatz " Grundzyklen: „32-Z“, „32-R““, dann lässt sich unser Schlüssel für den Grundzyklus 32 - Z wie folgt darstellen:

K 32-Z =

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

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

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

Diese. von Anfang an k1,k2,k3,k4,k5,k6,k7,k8 - ‘ as28', 'zw37', 'q839', '7342', 'ui23', '8e2T', 'wqm2', 'ewp1' Diese Sequenz wird dreimal wiederholt. Dann gehen die Elemente in umgekehrter Reihenfolge, dh: k8,k7,k6,k5,k4,k3,k2,k1 - 'ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'.

Ich habe die Elemente im Array in der Reihenfolge, in der sie bedient werden sollen, vorab in 32 - Z angeordnet. Dadurch habe ich den Speicherbedarf pro Taste erhöht, mir aber einige Denkprozesse erspart, die ich nicht benötigte, und die Geschwindigkeit erhöht Algorithmus, um die Speicherzugriffszeit zu reduzieren! Hier habe ich nur den Schlüssel für 32 - Z beschrieben, für den Zyklus 32 - R habe ich dasselbe getan, aber mit einem anderen Schema für die Bereitstellung von Elementen, das ich auch im Abschnitt " Grundzyklen: „32-Z“, „32-R».

Es ist Zeit, die Implementierung der Ersetzungsfunktion zu beschreiben, wie ich oben versprochen habe. Ich konnte nicht früher beschreiben, weil. Dies erfordert die Einführung eines neuen Konzepts - einer erweiterten Substitutionstabelle. Ich kann dir nicht erklären, was es ist. Stattdessen zeige ich es Ihnen, und Sie können selbst formulieren, was es ist - eine erweiterte Substitutionstabelle?

Um also zu verstehen, was eine erweiterte Substitutionstabelle ist, brauchen wir eine Substitutionstabelle, ich nehme zum Beispiel die in Abb. 3.

Zum Beispiel mussten wir die Nummer 66793940h ersetzen. Ich werde es in folgender Form darstellen:

Reis. 9

Nehmen wir nun die Elemente s1,s0, d.h. Low Byte, dann ist das Ergebnis der Ersetzungsfunktion 25h! Nachdem ich den Artikel von Andrey Vinokurov gelesen hatte, den ich im Absatz „ Verzeichnis der verwendeten Literatur“, werden Sie tatsächlich feststellen, dass Sie mit zwei Zeilen ein Array erhalten können, mit dem Sie mithilfe eines Assembler-Befehls schnell Ersatzelemente finden können xlat. Sie sagen, dass es auf andere Weise möglich ist, schneller, aber Andrey Vinokurov hat etwa vier Jahre damit verbracht, schnelle Algorithmen für die Implementierung von GOST zu erforschen! Ich finde, man sollte das Rad nicht neu erfinden, wenn es schon existiert.

Also zum Array:

Nehmen wir die ersten beiden Zeilen, null und erste, und erstellen ein Array von 256 Bytes. Jetzt beobachten wir ein Merkmal, dass, wenn Sie 00h umwandeln müssen, das Ergebnis 75h ist (basierend auf Abb. 3) – fügen Sie diesen Wert in das Array bei Offset 00h ein. Wir nehmen den Wert 01h, das Ergebnis der Ersetzungsfunktion ist 79h, fügen ihn in das Array bei Offset 01 ein und so weiter bis 0FFh, was uns 0FCh ergibt, das wir in das Array bei Offset 0FFh einfügen. Wir haben also eine erweiterte Ersetzungstabelle für die erste Gruppe von Zeichenfolgen: die erste und die Null. Aber es gibt immer noch drei Gruppen: die zweite Seite 2, Seite 3, die dritte Seite 4, Seite 5, die vierte Seite 6, Seite 7. Bei diesen drei Gruppen gehen wir genauso vor wie bei der ersten. Das Ergebnis ist eine erweiterte Substitutionstabelle!

Jetzt können Sie einen Algorithmus implementieren, der die Ersetzung durchführt. Dazu nehmen wir die Quellcodes, die Andrey Vinokurov auf seiner Seite gepostet hat, siehe " Literaturverzeichnis».

lea ebx,extented_table_simple

move eax,[Zahl zum Ersetzen setzen]

ebx,100h hinzufügen; zu den nächsten beiden Knoten gehen

sub ebx,300h ; damit in Zukunft ebx auf die Tabelle zeigt

Jetzt noch ein Feature, wir haben nicht nur die bisherigen Aktionen ersetzt, sondern auch die Zahl um 8 Bit nach links verschoben! Wir müssen die Zahl nur um weitere 3 Bits nach links verschieben:

und wir erhalten das Ergebnis der Operation rol eax,11!

Es gibt nichts mehr, was ich zur Optimierung hinzufügen kann, das einzige, was ich betonen kann, was ich oben gesagt habe, ist, Register häufiger als Speicherzugriffe zu verwenden. Ich denke, diese Worte sind nur etwas für Anfänger, erfahrene Leute verstehen das sehr gut ohne meine Worte.

Wichtige Informationsanforderungen.

Wie im Artikel von Andrey Vinokurov angegeben, wird der Schlüssel nach zwei Kriterien ausgewählt:

Das Kriterium für die gleichwahrscheinliche Verteilung von Bits zwischen den Werten 1 und 0. Üblicherweise ist das Kriterium für die gleichwahrscheinliche Verteilung von Bits das Pearson-Kriterium ("Chi-Quadrat").

Das bedeutet, der Schlüssel kann im Prinzip beliebig viele sein. Das heißt, beim Bilden des nächsten Bits des Schlüssels beträgt die Wahrscheinlichkeit seiner Initialisierung durch Eins oder Null 50/50!

Bitte beachten Sie, dass der Schlüssel acht Elemente zu je 32 Bit hat, also insgesamt 32 * 8 = 256 Bit im Schlüssel und in der Zahl sind mögliche Schlüssel 2256! Fällt es dir nicht auf?

Serienkriterien.

Wenn wir uns unseren Schlüssel ansehen, den ich im Absatz " 4.1 Implementierung des Hauptschritts der Kryptotransformation“, dann werden Sie feststellen, dass der folgende Eintrag wahr ist:

Reis. 10

In einem Satz sollte der Wert von k 1 nicht wiederholt werden, nicht in k 2 , nicht in irgendeinem anderen Element des Schlüssels.

Das heißt, der Schlüssel, den wir als Berücksichtigung des Verschlüsselungsalgorithmus ausgewählt haben, erfüllt die beiden obigen Kriterien gut.

Nun zur Auswahl der Substitutionstabelle:

Lassen Sie uns nun darüber sprechen, wie Sie die richtige Substitutionstabelle auswählen. Die Hauptanforderung für die Auswahl von Substitutionstabellen ist das Phänomen der "Nichtwiederholbarkeit" von Elementen, die jeweils 4 Bit groß sind. Wie Sie oben gesehen haben, besteht jede Zeile der Substitutionstabelle aus den Werten 0h, 1h, 2h, 3h, ..., 0fh. Die Hauptanforderung ist also, dass jede Zeile die Werte 0h, 1h, 2h, ... , 0fh und jeden solchen Wert in einer Instanz enthält. Zum Beispiel die Reihenfolge:

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

Erfüllt diesen Anspruch voll und ganz, aber trotzdem! Es wird nicht empfohlen, eine solche Sequenz als Zeichenfolge auszuwählen. Denn wenn Sie am Eingang einer Funktion, die auf einen solchen String angewiesen ist, einen Wert liefern, erhalten Sie am Ausgang denselben Wert! Glauben Sie nicht? Dann nehmen Sie die Nummer 332DA43Fh und acht solche Zeilen als Substitutionstabelle. Führen Sie den Austauschvorgang durch, und ich versichere Ihnen, die Ausgabe wird die Nummer 332DA43Fh sein! Das heißt, das gleiche, das Sie bei der Eingabe der Operation eingereicht haben! Und das ist kein Zeichen guter Form bei der Verschlüsselung, oder?

Das war eine Anforderung, das nächste Kriterium besagt, dass - jedes Bit des Ausgangsblocks statistisch unabhängig von jedem Bit des Eingangsblocks sein muss!

Wie sieht es einfacher aus? Und so haben wir zum Beispiel das Element s0 = 0Fh, 01111b aus der obigen Zahl ausgewählt. Die Wahrscheinlichkeit, dass wir jetzt das erste Bit durch eine Eins oder eine Null ersetzen, ist 0,5! Die Wahrscheinlichkeit, das zweite, dritte und vierte Bit, jedes Bit getrennt betrachtet, durch Einsen oder Nullen zu ersetzen, beträgt ebenfalls 0,5.Wenn wir s1 = 0Eh wählen, ersetzen wir die Wahrscheinlichkeit, dass wir ein Nullbit sind, und dies ist „0“. , durch null oder eins zu gleich - 0,5! Somit gibt es nach diesem Kriterium keine Regelmäßigkeit zwischen dem Ersetzen von Nullbits der Elemente s0, s1! Ja, Sie könnten Einsen ersetzen, aber Sie könnten auch Nullen setzen.

Um die Tabelle nach diesem Kriterium auszuwerten, können Sie eine Tabelle mit Korrelationskoeffizienten erstellen, die nach folgender Formel berechnet werden:

Wenn p = 1, dann ist der Wert von Bit j am Ausgang gleich dem Wert von Bit i am Eingang für jede Kombination von Bits am Eingang;

Wenn p = –1, dann ist der Wert des Bits j am Ausgang immer das Inverse des Eingangsbits i;

Ist p = 0, so nimmt das Ausgangsbit j für jeden festen Wert des Eingangsbits i mit gleicher Wahrscheinlichkeit die Werte 0 und 1 an.

Nehmen wir ein einzeiliges Beispiel:

Zerlegen wir es in Komponenten:

Wir berechnen einen Koeffizienten mit der obigen Formel. Um es einfacher zu verstehen, wie das gemacht wird, erkläre ich es genauer:

Wir nehmen das 0. Bit der 0. Zahl (0) am Eingang und das 0. Bit der 0. Zahl am Ausgang (1) und führen die Operation 0 XOR 1 = 1 durch.

Wir nehmen das 0. Bit der 1. Zahl (1) am Eingang und das 0. Bit der 1. Zahl am Ausgang (1) und führen die Operation 1 XOR 1 = 0 durch.

Wir nehmen das 0. Bit der 2. Zahl (0) am Eingang und das 0. Bit der 2. Zahl am Ausgang (0) und führen die Operation 0 XOR 0 = 0 durch.

Wir nehmen das 0. Bit der 3. Zahl (1) am Eingang und das 0. Bit der 3. Zahl am Ausgang (1) und führen die Operation 1 XOR 1 = 0 durch.

Nachdem wir nacheinander XOR-Operationen in einer solchen Sequenz durchgeführt haben, zählen wir die Anzahl aller Nicht-Null-Werte, wir erhalten den Wert 6. Daher P 00 = 1-(6/2 4-1) = 0,25. Es stellte sich also heraus, dass der Wert von Bit 0 am Ausgang in 4 von 16 Fällen gleich dem Wert von Bit 0 am Eingang ist;

Endgültige Quotentabelle:

Wie aus der Tabelle der Korrelationskoeffizienten ersichtlich ist, ist Bit 3 am Eingang relativ zu Bit 0 am Ausgang in 14 von 16 Fällen invertiert, das sind 87,5 %. Dies ist für normale Verschlüsselungssysteme nicht mehr akzeptabel. Nehmen wir zur Abwechslung mal ein anderes Beispiel:

Die Tabelle der Koeffizienten wird wie folgt aussehen (wer nicht faul ist, neu zu berechnen)

In dieser Tabelle sieht es noch schlimmer aus - die Bits 1 und 2 der Gruppe bleiben unverändert! Der Kryptoanalytiker hat einen Ort, an dem er sich umdrehen kann. Unter Berücksichtigung all dieser Anforderungen hat eine einfache Aufzählung ("frontal") Permutationstabellen gefunden, die der angegebenen Theorie entsprechen (heute - 1276 Kombinationen). Hier sind einige davon:

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

Verzeichnis der verwendeten Literatur.

1. Artikel von Andrey Vinokurov:

Verschlüsselungsalgorithmus GOST 28147-89, seine Verwendung und Implementierung

für Computer Intel-Plattformen x86.

Hier sind die Quellcodes für die Implementierung des Verschlüsselungsalgorithmus.

1. Artikel von Horst Feistel:

Kryptographie und Computersicherheit.

(zu finden unter derselben Adresse wie der vorherige Artikel)

1. Ross N. Williams:

Ein elementarer Leitfaden für CRC-Fehlererkennungsalgorithmen

Auf der Website veröffentlicht www.wasm.en.

Danke.

Ich möchte mich bei allen Besuchern des Forums www.wasm.ru bedanken. Aber ich möchte besonders ChS danken, der derzeit als SteelRat bekannt ist. Er hat mir geholfen, Dinge zu verstehen, die ich wahrscheinlich nie verstehen würde, und mir geholfen, den Absatz zu schreiben: „ Wichtige Informationsanforderungen“, wurde der Hauptteil dieses Absatzes von ihm geschrieben. Auch dem Mitarbeiter der KSTU bin ich zutiefst dankbar. EIN. Tupolev Anikin Igor Vyacheslavovich und es wäre eine Sünde, Chris Kaspersky für die Tatsache, dass er es ist, und Volodya / wasm.ru für seine Anweisungen nicht zu erwähnen. Oh, und ich bekomme von ihm. Ich möchte auch Sega-Zero / Callipso dafür erwähnen, dass sie mir etwas mathematischen Dschungel in den Sinn gebracht haben.

Das ist vielleicht alles, was ich Ihnen sagen möchte.

Für Kritik oder Fragen zu diesem Artikel oder einfach nur Tipps wäre ich dankbar. Meine Kontaktdaten: [E-Mail geschützt], ICQ-337310594.

Mit freundlichen Grüßen, Evil`s Interrupt.

P.S.: Ich habe mit diesem Artikel nicht versucht, irgendjemanden zu übertrumpfen. Es wurde mit der Absicht geschrieben, das Studium von GOST zu erleichtern, und wenn Sie Schwierigkeiten haben, bedeutet dies nicht, dass ich dafür verantwortlich bin. Seien Sie vernünftig und haben Sie Geduld, alles Gute für Sie!

„Während du lebst, stirb nicht, sieh dir diese Welt an.
Viele hier haben eine tote Seele – sie sind innerlich tot.
Aber sie gehen und lachen, ohne zu wissen, dass sie nicht da sind,
Überstürzen Sie Ihren Tod nicht", sagte sie mir.

Arie „Da oben“

1. Einführung

1. Einführung in Blockchiffren

2.1 Feistel-Netzwerke.
2.2 Blockchiffre GOST 28147-89

1. Theoretisches Minimum

3.1 Schlüsselinformation
3.2 Der Hauptschritt der Krypto-Transformation

3.3 Grundzyklen:“ 32-Z” , “ 32-R” .

1. Üben

4.1 Implementierung des Hauptschritts der Kryptotransformation
4.2 Erhöhung der Geschwindigkeit des Algorithmus
5.
6. Verzeichnis der verwendeten Literatur
7. Danke.

Einführung.

Dieses Dokument ist mein Versuch, die Methode zum einfachen Ersetzen des Verschlüsselungsalgorithmus GOST 28147-89 in der einfachsten, aber dennoch technisch versierten Sprache zu beschreiben. Wie gut mir das gelungen ist, wird der Leser nach Lektüre der ersten sechs Punkte beurteilen.

Damit meine Arbeit nützlicher wird, empfehle ich, sich mit den Werken der in der Liste der verwendeten Literatur angegebenen Autoren zu bewaffnen. Empfehlenswert ist auch ein Taschenrechner, damit dieser über eine Funktion zur Berechnung der Operation verfügt XOR, Weil Beim Lesen des Artikels wird davon ausgegangen, dass der Leser diesen Verschlüsselungsalgorithmus studieren möchte. Obwohl es sich auch als Nachschlagewerk eignet, habe ich diesen Artikel genau als Tutorial geschrieben.

Einführung in Blockchiffren.

Bevor wir uns mit dem Algorithmus befassen, müssen wir uns mit der Entstehungsgeschichte dieser Art von Verschlüsselung vertraut machen. Der Algorithmus gehört zur Kategorie der Blockchiffren, in deren Architektur die Informationen in eine endliche Anzahl von Blöcken aufgeteilt werden, wobei der letzte natürlich nicht vollständig sein darf. Der Verschlüsselungsprozess findet genau über die vollständigen Blöcke statt, die den Chiffretext bilden. Der letzte Block wird, wenn er unvollständig ist, um etwas ergänzt (ich werde weiter unten auf die Nuancen seiner Hinzufügung eingehen) und wird auf die gleiche Weise wie vollständige Blöcke verschlüsselt. Mit Chiffretext meine ich - das Ergebnis der Aktion der Verschlüsselungsfunktion auf eine bestimmte Datenmenge, die der Benutzer zur Verschlüsselung übermittelt hat. Mit anderen Worten, der Chiffretext ist das Endergebnis der Verschlüsselung.

Die Geschichte der Entwicklung von Blockchiffren ist mit dem Beginn der 70er Jahre verbunden, als IBM, als es die Notwendigkeit erkannte, Informationen bei der Übertragung von Daten über Computerkommunikationskanäle zu schützen, begann, ein eigenes Forschungsprogramm zum Schutz von Informationen in der Elektronik durchzuführen Netzwerke, einschließlich Kryptografie.

Unter der Leitung von Dr. Horst Festel.

2.1 Feistel-Netzwerke

Die Architektur des von Feistel vorgeschlagenen neuen Verschlüsselungsverfahrens wurde in der klassischen Literatur als "Feistel-Architektur" bezeichnet, aber im Moment wird in der russischen und ausländischen Literatur ein etablierterer Begriff verwendet - "Feistel-Netzwerk" oder Feistel-Netzwerk. Anschließend wurde gemäß dieser Architektur die Luzifer-Chiffre gebaut - die später veröffentlicht wurde und eine neue Welle des Interesses an der Kryptographie im Allgemeinen auslöste.

Die Idee der Feistel-Netzwerkarchitektur ist folgende: Der Eingangsinformationsstrom wird in Blöcke von n Bits Größe aufgeteilt, wobei n eine gerade Zahl ist. Jeder Block wird in zwei Teile geteilt - L und R, dann werden diese Teile in eine iterative Blockchiffre eingespeist, in der das Ergebnis der j-ten Stufe durch das Ergebnis der vorherigen Stufe j-1 bestimmt wird! Dies lässt sich an einem Beispiel veranschaulichen:

Reis. 1

Wobei Funktion A die Hauptaktion der Blockchiffre ist. Es kann eine einfache Aktion sein, wie die XOR-Operation, oder es kann eine komplexere Form haben, eine Folge einer Anzahl einfacher Aktionen sein – Modulo-Addition, Linksverschiebung, Elementersetzung usw., insgesamt diese einfachen Aktionen bilden den sogenannten - den Hauptschritt der Krypto-Transformation.

Es sollte beachtet werden, dass die Schlüsselelemente der Funktion die Lieferung von Schlüsselelementen und die XOR-Operation sind, und wie gut durchdacht die Arbeit dieser Operationen ist, spricht für die kryptografische Stärke der Chiffre als Ganzes.

Damit die Idee der Feistel-Netzwerke vollständig klar wird, betrachten Sie den einfachsten Fall, der in Abb. Reis. 1, wobei in der Funktion A - die Operationen „mod 2“ („xor“) ausgeführt werden, aber dies Protozoon In einem ernsteren Fall, beispielsweise beim Verbergen von Informationen von nationaler Bedeutung, kann Funktion A komplexer sein (soweit ich gesehen habe, kann Funktion A tatsächlich sehr kompliziert sein):

Ausgangsdaten:

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

Holen Sie sich einen Chiffretext

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

Lassen Sie uns unsere Schritte erklären:

1. Diese Operation ist Addition mod 2 4 . In der Praxis läuft eine solche Operation auf eine einfache Addition hinaus, bei der wir zwei Zahlen addieren und den Übertrag zur 5. Ziffer ignorieren müssen. Da, wenn wir Exponenten über die Ziffern der binären Darstellung einer Zahl setzen, ein Indikator von vier über der fünften Ziffer steht, sehen Sie sich die folgende Abbildung an, die die Aktionen unserer Operation zeigt:

Reis. 2

Hier habe ich mit einem Pfeil auf die Exponenten gezeigt, wie Sie sehen, hätte das Ergebnis 10100 sein sollen, aber da der Übertrag während der mod 2 4-Operation ignoriert wird, erhalten wir 0100.

1. Diese Operation wird in der Literatur als mod 2 bezeichnet, in der Assemblersprache wird sie durch den Befehl implementiert XOR. Aber sein korrekterer Name ist mod 2 1 . Ohne diese einzigartige Operation ist es kaum möglich, einen schnellen, einfach zu implementierenden Verschlüsselungsalgorithmus zu entwickeln und gleichzeitig ziemlich kryptoresistent zu sein. Die Einzigartigkeit dieser Operation liegt darin, dass sie die Umkehrung ihrer selbst ist! Wenn zum Beispiel die Zahl A mit der Zahl B XOR-verknüpft wird, ist das Ergebnis C, in Zukunft reicht es aus, die Zahlen B und C erneut mit XOR zu verknüpfen, um den vorherigen Wert von A zu erhalten!

Bei dieser Operation haben wir 1010 mit den Nummern 1110 und 0100, um 1110 zurückzubekommen, reicht es aus, die Nummern 0100 und 1010 mit XOR zu verknüpfen! Weitere Details zu diesem Vorgang finden Sie im Artikel, der auf der Website eingebettet ist. www.wasm.ru, « Grundlegende Anleitung zuCRC_Fehlererkennungsalgorithmen» der Autor, der Ross N. Williams. Es gibt einen Absatz in dieser Arbeit - 5. Binäre Arithmetik ohne Überträge". In diesem Artikel wird die Operation beschrieben xoder! Ich rufe aus, weil in diesem Artikel diese Operation so beschrieben wird, dass der Leser nicht nur versteht, wie diese Operation funktioniert, sondern sogar damit beginnt sehen, hören und fühlen!

1. Diese Aktion ist notwendig, damit Sie beim Entschlüsseln aus dem Chiffretext die ursprünglichen Werte erhalten.

2.2 Blockverschlüsselung GOST 28147-89

Der Verschlüsselungsalgorithmus GOST 28147 - 89 gehört zur Kategorie der Blockchiffren, die auf der Feistel-Balanced-Network-Architektur arbeiten, bei der zwei Teile des ausgewählten Informationsblocks gleich groß sind. Der Algorithmus wurde in den Eingeweiden der achten Abteilung des KGB entwickelt, jetzt in FAPSI umgewandelt, und wurde bereits 1989 unter der UdSSR als Verschlüsselungsstandard der Russischen Föderation verankert.

Damit diese Methode des Algorithmus funktioniert, ist es notwendig, die Informationen in Blöcke mit einer Größe von 64 Bit aufzuteilen. Generieren oder geben Sie die folgenden Schlüsselinformationen in das Verschlüsselungssystem ein: Schlüssel und Substitutionstabelle. Die Wahl des Schlüssels und der Substitutionstabelle für die Verschlüsselung sollte sehr ernst genommen werden, weil. Dies ist die Grundlage für die Sicherheit Ihrer Informationen. Informationen zu den Anforderungen an den Schlüssel und die Substitutionstabelle finden Sie im Abschnitt "Anforderungen an Schlüsselinformationen".

Bei der Betrachtung der Methode werden wir uns nicht darauf konzentrieren, weil. Dieser Artikel wurde, wie ich oben sagte, mit dem Ziel geschrieben, dem Leser beizubringen, wie man Daten verschlüsselt, indem man einfach diesen Verschlüsselungsalgorithmus ersetzt, aber wir werden dieses Thema definitiv am Ende des Artikels ansprechen.

Theoretisches Minimum.

3.1 Wichtige Informationen

Wie ich oben sagte, sind die folgenden Personen aktiv an der Datenverschlüsselung beteiligt:

3.1.1. Der Schlüssel ist eine Folge von acht Elementen mit jeweils 32 Bit. Außerdem bezeichnen wir das Symbol K und die Elemente, aus denen es besteht - k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Die Substitutionstabelle ist eine Matrix aus acht Zeilen und sechzehn Spalten, im Folgenden als Hij bezeichnet. Jedes Element am Schnittpunkt von Zeile i und Spalte j benötigt 4 Bits.

Die Hauptaktion im Verschlüsselungsprozess ist der Hauptschritt der Kryptotransformation. Dies ist nichts weiter als eine Aktion, um Daten nach einem bestimmten Algorithmus zu verschlüsseln, nur der Name, den die Entwickler eingeführt haben, war zu umständlich :).

Bevor mit der Verschlüsselung begonnen wird, wird der Block in zwei Teile L und R mit jeweils 32 Bit aufgeteilt. Das Schlüsselelement wird ausgewählt und erst dann werden diese beiden Teile des Blocks eingespeist, das Schlüsselelement ist die Substitutionstabelle in die Hauptschrittfunktion, das Ergebnis des Hauptschritts ist eine Iteration des Basiszyklus, die im Abschnitt besprochen wird nächsten Absatz. Der Hauptschritt besteht aus den folgenden Schritten:

1. Der Additionsteil des Blocks R wird zum Schlüsselelement K mod 2 32 addiert. Ich habe oben eine ähnliche Operation beschrieben, hier ist es dasselbe, nur der Exponent ist nicht „4“, sondern „32“ - das Ergebnis dieser Operation wird in Zukunft mit Smod bezeichnet.
2. Wir teilen das zuvor erhaltene Ergebnis Smod in vier Bitelemente s7, s6, s5, s4, s3, s2, s1, s0 und speisen es in die Ersetzungsfunktion ein. Die Ersetzung ist wie folgt: Das Element Smod - s i wird ausgewählt, von Anfang an beginnen wir mit dem jüngsten Element und ersetzen es durch den Wert aus der Ersetzungstabelle durch i - die Zeile und Spalte, die durch den Wert des Elements s i angegeben sind . Wir gehen zum Element s i +1 über und machen dasselbe und fahren fort, bis wir den Wert des letzten Elements Smod ersetzen – das Ergebnis dieser Operation wird als Ssimple bezeichnet.
3. Bei dieser Operation wird der Wert von Ssimple zyklisch um 11 Bit nach links verschoben und wir erhalten Srol.
4. Wir wählen den zweiten Teil des Blocks L aus und fügen Mod 2 mit Srol hinzu, als Ergebnis haben wir Sxor.
5. In diesem Stadium wird der L-Teil des Blocks gleich dem Wert des R-Teils, und der R-Teil wird wiederum mit dem Ergebnis von Sxor initialisiert, und dies vervollständigt die Hauptschrittfunktion!

3.3 Grundzyklen: „32-Z“, „32-R“.

Um Informationen zu verschlüsseln, ist es notwendig, sie in Blöcke mit einer Größe von 64 Bit aufzuteilen, natürlich kann der letzte Block weniger als 64 Bit umfassen. Diese Tatsache ist die Achillesferse dieser "einfachen Substitutions"-Methode. Da seine Erweiterung auf 64 Bit eine sehr wichtige Aufgabe ist, um die kryptografische Stärke des Chiffretextes zu erhöhen, ist dieser sensible Ort, wenn er in der Informationsmatrix vorhanden ist, aber möglicherweise nicht vorhanden ist (z. B. eine Datei mit einer Größe von 512 Byte !), sollte mit großer Verantwortung behandelt werden!

Nachdem Sie die Informationen in Blöcke aufgeteilt haben, sollten Sie den Schlüssel in Elemente aufteilen:

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

Die Verschlüsselung selbst besteht in der Verwendung sogenannter Basiszyklen. Diese wiederum beinhalten die n-te Anzahl grundlegender Kryptotransformationsschritte.

Grundzyklen sind sozusagen gekennzeichnet: n - m. Wobei n die Anzahl der grundlegenden Kryptotransformationsschritte in der Basisschleife ist und m der "Typ" der Basisschleife ist, d.h. worum geht es, "Z"-Verschlüsselung oder "R"-Verschlüsselung von Daten.

Der grundlegende Verschlüsselungszyklus 32–3 besteht aus 32 grundlegenden kryptographischen Schritten. Der Block N und das Element des Schlüssels K werden in die Funktion eingespeist, die die Aktionen des Schritts implementiert, und der erste Schritt erfolgt mit k1, der zweite über das Ergebnis mit dem Element k2 usw. nach folgendem Schema:

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

Der 32-P-Entschlüsselungsprozess läuft ähnlich ab, aber die Schlüsselelemente werden in umgekehrter Reihenfolge zugeführt:

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

Üben.

Nachdem wir uns mit der Theorie zum Verschlüsseln von Informationen vertraut gemacht haben, ist es an der Zeit zu sehen, wie die Verschlüsselung in der Praxis funktioniert.

Ausgangsdaten:

Nehmen wir einen Informationsblock N = 0102030405060708h, hier sind die Teile L und R gleich:

L = 01020304h, R = 05060708h, nimm den Schlüssel:

K=' als28 zw37 q839 7342ui23 8e2t wqm2 ewp1' (dies sind ASCII-Codes, um die hexadezimale Darstellung anzuzeigen, können Sie diese Datei im Ansichtsmodus in Total Commander öffnen, indem Sie auf die Schaltfläche " F3“ und dann die Taste „ 3 "). In diesem Schlüssel sind die Elementwerte:

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

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

Nehmen Sie auch die folgende Substitutionstabelle:

Reis. 3

Hier sind die Zeilen von 0 bis 7 nummeriert, die Spalten von 0 bis F.

Warnung: Alle Angaben, auch der Schlüssel mit der Substitutionstabelle, sind beispielhaft für die Betrachtung des Algorithmus!

Unter Verwendung der "Anfangsdaten" müssen Sie das Ergebnis der Aktion des Hauptschritts der Kryptotransformation erhalten.

1. Wir wählen den Teil R = 05060708h und das Schlüsselelement k1 = ‚as28‘, in hexadezimaler Form sieht das Schlüsselelement so aus: 61733238h. Jetzt führen wir die Operation von Summation mod 2 32 durch:

Reis. 4

Wie Sie in der Abbildung sehen können, haben wir nicht auf 33 Bit übertragen, die rot und mit dem Exponenten " 32 ". Und wenn wir andere Werte von R und dem Schlüsselelement hätten, könnte das durchaus passieren, und dann würden wir das ignorieren und in Zukunft nur noch die gelb markierten Bits verwenden.

Ich führe eine solche Operation mit dem Assembler-Befehl aus hinzufügen:

; eax=R, ebx='as28'

Das Ergebnis dieser Operation ist Smod = 66793940h

1. Jetzt die komplizierteste Operation, aber wenn man genau hinschaut, ist sie nicht mehr so ​​beängstigend, wie es zunächst scheint. Stellen wir uns Smod in folgender Form vor:

MUSTER NICHT SPEICHERN

Reis. 5

Ich habe versucht, die Smod-Elemente in der Abbildung zu visualisieren, aber ich erkläre es trotzdem:

s0 = 0, s1 = 4, s2 = 9 usw.

Nun führen wir ausgehend vom niedrigsten Element s0 eine Ersetzung durch. Erinnere dich an den Absatz 3.2 Der Hauptschritt der Krypto-Transformation» i ist eine Zeile, s i ist eine Spalte, wir suchen einen Wert in der Nullzeile und Nullspalte:

Abb.6

Der aktuelle Wert von Smod ist also nicht 6679394 0 h und 6679394 5 H.

Wir fahren fort, s1 zu ersetzen, d.h. vier. Verwenden Sie die erste Zeile und die vierte Spalte (s1= 4!). Schauen wir uns das Bild an:

Reis. 7

Jetzt ist der Wert Smod, nicht 667939 4 5h, 667939 2 5 Std. Ich gehe davon aus, dass der Ersetzungsalgorithmus dem Leser jetzt klar ist, und ich kann sagen, dass das Endergebnis von Ssimple den folgenden Wert haben wird - 11e10325h.

Wie dies am einfachsten in Form von Assembler-Befehlen zu implementieren ist, werde ich später im nächsten Absatz erläutern, nachdem ich über die erweiterte Tabelle gesprochen habe.

1. Wir müssen den resultierenden Ssimple-Wert um 11 Bit nach links verschieben.

Reis. 8

Wie Sie sehen können, ist diese Aktion ziemlich einfach und wird durch einen Assembler-Sprachbefehl implementiert - rollen und das Ergebnis dieser Srol-Operation ist 0819288Fh.

1. Nun bleibt Teil L unseres Informationsblocks zu XOR mit dem Wert Srol. Ich nehme Rechner von w2k sp4 und erhalte Sxor = 091b2b8bh.
2. Diese Aktion ist endgültig und wir weisen einfach R den Wert des L-Teils zu, bereinigen ihn und initialisieren den L-Teil mit dem Wert von Sxor.

Endergebnis:

L=091b2b8bh, R=01020304h

4.2 Erhöhung der Geschwindigkeit des Algorithmus

Lassen Sie uns nun über die Optimierung des Algorithmus für Geschwindigkeit sprechen. Bei der Umsetzung eines Projekts muss man berücksichtigen, dass ein Programm, das öfter mit Registern als mit Speicher arbeitet, am schnellsten arbeitet, und hier ist diese Einschätzung auch sehr wichtig, denn. über einen Informationsblock bis zu 32 Verschlüsselungsschritte!

Als ich den Verschlüsselungsalgorithmus in mein Programm implementiert habe, habe ich Folgendes getan:

1. Wählen Sie einen Teil von Block L in das Register eax und R in edx.
2. Initialisiert in das esi-Register mit der Adresse des erweiterten Schlüssels, mehr dazu weiter unten.
3. Ich habe dem ebx-Register den Wert der Adresse der erweiterten Substitutionstabelle zugewiesen, mehr dazu weiter unten
4. Übergeben Sie die Informationen der Punkte 1,2, 3 an die Funktion des Grundzyklus 32 - Z oder 32 - R, je nach Situation.

Wenn Sie sich das Schema zur Bereitstellung von Schlüsselelementen im Absatz " Grundzyklen: „32-Z“, „32-R““, dann lässt sich unser Schlüssel für den Grundzyklus 32 - Z wie folgt darstellen:

K 32-Z =

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

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

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

Diese. von Anfang an k1,k2,k3,k4,k5,k6,k7,k8 - ‘ as28', 'zw37', 'q839', '7342', 'ui23', '8e2T', 'wqm2', 'ewp1' Diese Sequenz wird dreimal wiederholt. Dann gehen die Elemente in umgekehrter Reihenfolge, dh: k8,k7,k6,k5,k4,k3,k2,k1 - 'ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'.

Ich habe die Elemente im Array in der Reihenfolge, in der sie bedient werden sollen, vorab in 32 - Z angeordnet. Dadurch habe ich den Speicherbedarf pro Taste erhöht, mir aber einige Denkprozesse erspart, die ich nicht benötigte, und die Geschwindigkeit erhöht Algorithmus, um die Speicherzugriffszeit zu reduzieren! Hier habe ich nur den Schlüssel für 32 - Z beschrieben, für den Zyklus 32 - R habe ich dasselbe getan, aber mit einem anderen Schema für die Bereitstellung von Elementen, das ich auch im Abschnitt " Grundzyklen: „32-Z“, „32-R».

Es ist Zeit, die Implementierung der Ersetzungsfunktion zu beschreiben, wie ich oben versprochen habe. Ich konnte nicht früher beschreiben, weil. Dies erfordert die Einführung eines neuen Konzepts - einer erweiterten Substitutionstabelle. Ich kann dir nicht erklären, was es ist. Stattdessen zeige ich es Ihnen, und Sie können selbst formulieren, was es ist - eine erweiterte Substitutionstabelle?

Um also zu verstehen, was eine erweiterte Substitutionstabelle ist, brauchen wir eine Substitutionstabelle, ich nehme zum Beispiel die in Abb. 3.

Zum Beispiel mussten wir die Nummer 66793940h ersetzen. Ich werde es in folgender Form darstellen:

MUSTER NICHT SPEICHERN

Reis. 9

Nehmen wir nun die Elemente s1,s0, d.h. Low Byte, dann ist das Ergebnis der Ersetzungsfunktion 25h! Nachdem ich den Artikel von Andrey Vinokurov gelesen hatte, den ich im Absatz „ Verzeichnis der verwendeten Literatur“, werden Sie tatsächlich feststellen, dass Sie mit zwei Zeilen ein Array erhalten können, mit dem Sie mithilfe eines Assembler-Befehls schnell Ersatzelemente finden können xlat. Sie sagen, dass es auf andere Weise möglich ist, schneller, aber Andrey Vinokurov hat etwa vier Jahre damit verbracht, schnelle Algorithmen für die Implementierung von GOST zu erforschen! Ich finde, man sollte das Rad nicht neu erfinden, wenn es schon existiert.

Also zum Array:

Nehmen wir die ersten beiden Zeilen, null und erste, und erstellen ein Array von 256 Bytes. Jetzt beobachten wir ein Merkmal, dass, wenn Sie 00h umwandeln müssen, das Ergebnis 75h ist (basierend auf Abb. 3) – fügen Sie diesen Wert in das Array bei Offset 00h ein. Wir nehmen den Wert 01h, das Ergebnis der Ersetzungsfunktion ist 79h, fügen ihn in das Array bei Offset 01 ein und so weiter bis 0FFh, was uns 0FCh ergibt, das wir in das Array bei Offset 0FFh einfügen. Wir haben also eine erweiterte Ersetzungstabelle für die erste Gruppe von Zeichenfolgen: die erste und die Null. Aber es gibt immer noch drei Gruppen: die zweite Seite 2, Seite 3, die dritte Seite 4, Seite 5, die vierte Seite 6, Seite 7. Bei diesen drei Gruppen gehen wir genauso vor wie bei der ersten. Das Ergebnis ist eine erweiterte Substitutionstabelle!

Jetzt können Sie einen Algorithmus implementieren, der die Ersetzung durchführt. Dazu nehmen wir die Quellcodes, die Andrey Vinokurov auf seiner Seite gepostet hat, siehe " Literaturverzeichnis».

lea ebx,extented_table_simple

move eax,[Zahl zum Ersetzen setzen]

ebx,100h hinzufügen; zu den nächsten beiden Knoten gehen

sub ebx,300h ; damit in Zukunft ebx auf die Tabelle zeigt

Jetzt noch ein Feature, wir haben nicht nur die bisherigen Aktionen ersetzt, sondern auch die Zahl um 8 Bit nach links verschoben! Wir müssen die Zahl nur um weitere 3 Bits nach links verschieben:

und wir erhalten das Ergebnis der Operation rol eax,11!

Es gibt nichts mehr, was ich zur Optimierung hinzufügen kann, das einzige, was ich betonen kann, was ich oben gesagt habe, ist, Register häufiger als Speicherzugriffe zu verwenden. Ich denke, diese Worte sind nur für Anfänger, erfahrene Leute verstehen das sehr gut ohne meine Worte :).

Wichtige Informationsanforderungen.

Wie im Artikel von Andrey Vinokurov angegeben, wird der Schlüssel nach zwei Kriterien ausgewählt:

- Kriterium der gleichwahrscheinlichen Verteilung von Bits zwischen den Werten 1 und 0. Normalerweise fungiert das Pearson-Kriterium ("Chi-Quadrat") als Kriterium der gleichwahrscheinlichen Verteilung von Bits.

Das bedeutet, der Schlüssel kann im Prinzip beliebig viele sein. Das heißt, beim Bilden des nächsten Bits des Schlüssels beträgt die Wahrscheinlichkeit seiner Initialisierung durch Eins oder Null 50/50!

Bitte beachten Sie, dass der Schlüssel acht Elemente zu je 32 Bit hat, also insgesamt 32 * 8 = 256 Bit im Schlüssel sind und die Anzahl der möglichen Schlüssel 2 256 beträgt! Fällt es dir nicht auf? 🙂

— Serienkriterium.

Wenn wir uns unseren Schlüssel ansehen, den ich im Absatz " 4.1 Implementierung des Hauptschritts der Kryptotransformation“, dann werden Sie feststellen, dass der folgende Eintrag wahr ist:

Reis. 10

In einem Satz sollte der Wert von k 1 nicht wiederholt werden, nicht in k 2 , nicht in irgendeinem anderen Element des Schlüssels.

Das heißt, der Schlüssel, den wir als Berücksichtigung des Verschlüsselungsalgorithmus ausgewählt haben, erfüllt die beiden obigen Kriterien gut.

Nun zur Auswahl der Substitutionstabelle:

Lassen Sie uns nun darüber sprechen, wie Sie die richtige Substitutionstabelle auswählen. Die Hauptanforderung für die Auswahl von Substitutionstabellen ist das Phänomen der "Nichtwiederholbarkeit" von Elementen, die jeweils 4 Bit groß sind. Wie Sie oben gesehen haben, besteht jede Zeile der Substitutionstabelle aus den Werten 0h, 1h, 2h, 3h, ..., 0fh. Die Hauptanforderung ist also, dass jede Zeile die Werte 0h, 1h, 2h, ... , 0fh und jeden solchen Wert in einer Instanz enthält. Zum Beispiel die Reihenfolge:

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

Erfüllt diesen Anspruch voll und ganz, aber trotzdem! Es wird nicht empfohlen, eine solche Sequenz als Zeichenfolge auszuwählen. Denn wenn Sie am Eingang einer Funktion, die auf einen solchen String angewiesen ist, einen Wert liefern, erhalten Sie am Ausgang denselben Wert! Glauben Sie nicht? Dann nehmen Sie die Nummer 332DA43Fh und acht solche Zeilen als Substitutionstabelle. Führen Sie den Austauschvorgang durch, und ich versichere Ihnen, die Ausgabe wird die Nummer 332DA43Fh sein! Das heißt, das gleiche, das Sie bei der Eingabe der Operation eingereicht haben! Und das ist kein Zeichen guter Form bei der Verschlüsselung, oder? 🙂

Das war eine Anforderung, das nächste Kriterium besagt, dass - jedes Bit des Ausgangsblocks statistisch unabhängig von jedem Bit des Eingangsblocks sein muss!

Wie sieht es einfacher aus? Und so haben wir zum Beispiel das Element s0 = 0Fh, 01111b aus der obigen Zahl ausgewählt. Die Wahrscheinlichkeit, dass wir jetzt das erste Bit durch eine Eins oder eine Null ersetzen, ist 0,5! Die Wahrscheinlichkeit, das zweite, dritte und vierte Bit, jedes Bit getrennt betrachtet, durch Einsen oder Nullen zu ersetzen, beträgt ebenfalls 0,5.Wenn wir s1 = 0Eh wählen, ersetzen wir die Wahrscheinlichkeit, dass wir ein Nullbit sind, und dies ist „0“. , durch null oder eins zu gleich - 0,5! Somit gibt es nach diesem Kriterium keine Regelmäßigkeit zwischen dem Ersetzen von Nullbits der Elemente s0, s1! Ja, Sie könnten Einsen ersetzen, aber Sie könnten auch Nullen setzen. 🙂

Um die Tabelle nach diesem Kriterium auszuwerten, können Sie eine Tabelle mit Korrelationskoeffizienten erstellen, die nach folgender Formel berechnet werden:

— wenn p = 1, dann ist der Wert von Bit j am Ausgang gleich dem Wert von Bit i am Eingang für jede Kombination von Bits am Eingang;

— wenn p = -1, dann ist der Wert von Bit j am Ausgang immer die Invertierung des Eingangsbits i;

— wenn p = 0, dann nimmt das Ausgangsbit j für jeden festen Wert des Eingangsbits i mit gleicher Wahrscheinlichkeit die Werte 0 und 1 an.

Nehmen wir ein einzeiliges Beispiel:

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

Zerlegen wir es in Komponenten:

Wir berechnen einen Koeffizienten mit der obigen Formel. Um es einfacher zu verstehen, wie das gemacht wird, erkläre ich es genauer:

- nehmen wir das 0. Bit der 0. Zahl (0) am Eingang und das 0. Bit der 0. Zahl am Ausgang (1) führen wir die Operation 0 XOR 1 = 1 durch.

- wir nehmen das 0. Bit der 1. Zahl (1) am Eingang und das 0. Bit der 1. Zahl am Ausgang (1) wir führen die Operation 1 XOR 1 = 0 durch.

- wir nehmen das 0. Bit der 2. Zahl (0) am Eingang und das 0. Bit der 2. Zahl am Ausgang (0) wir führen die Operation 0 XOR 0 = 0 durch.

- wir nehmen das 0. Bit der 3. Zahl (1) am Eingang und das 0. Bit der 3. Zahl am Ausgang (1) wir führen die Operation 1 XOR 1 = 0 durch.

Nachdem wir nacheinander XOR-Operationen in einer solchen Sequenz durchgeführt haben, zählen wir die Anzahl aller Nicht-Null-Werte, wir erhalten den Wert 6. Daher P 00 = 1-(6/2 4-1) = 0,25. Es stellte sich also heraus, dass der Wert von Bit 0 am Ausgang in 4 von 16 Fällen gleich dem Wert von Bit 0 am Eingang ist;

Endgültige Quotentabelle:

Die Tabelle der Koeffizienten wird wie folgt aussehen (wer nicht faul ist, neu zu berechnen)

	Eingang
Ausfahrt		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

In dieser Tabelle sieht es noch schlimmer aus - die Bits 1 und 2 der Gruppe bleiben unverändert! Der Kryptoanalytiker hat einen Ort, an dem er sich umdrehen kann 🙂 Unter Berücksichtigung all dieser Anforderungen hat eine einfache Aufzählung („frontal“) Permutationstabellen gefunden, die der angegebenen Theorie entsprechen (heute – 1276 Kombinationen). Hier sind einige davon:

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

Verzeichnis der verwendeten Literatur.

1. Artikel von Andrey Vinokurov:

Verschlüsselungsalgorithmus GOST 28147-89, seine Verwendung und Implementierung

für Computer mit Intel x86-Plattform.

(zu finden unter: http://www.enlight.ru/crypto/frame.htm).

Hier sind die Quellcodes für die Implementierung des Verschlüsselungsalgorithmus.

1. Artikel von Horst Feistel:

Kryptographie und Computersicherheit.

(zu finden unter derselben Adresse wie der vorherige Artikel)

1. Ross N. Williams:

Ein elementarer Leitfaden für CRC-Fehlererkennungsalgorithmen

Auf der Website veröffentlicht www.wasm.en.

Danke.

Ich möchte mich bei allen Besuchern des Forums www.wasm.ru bedanken. Aber ich möchte besonders ChS danken, der derzeit als SteelRat bekannt ist. Er hat mir geholfen, Dinge zu verstehen, die ich wahrscheinlich nie verstehen würde, und mir geholfen, den Absatz zu schreiben: „ Wichtige Informationsanforderungen“, wurde der Hauptteil dieses Absatzes von ihm geschrieben. Auch dem Mitarbeiter der KSTU bin ich zutiefst dankbar. EIN. Tupolev Anikin Igor Vyacheslavovich und es wäre eine Sünde, Chris Kaspersky für die Tatsache, dass er es ist, und Volodya / wasm.ru für seine Anweisungen nicht zu erwähnen. Oh, und ich bekomme von ihm :). Ich möchte auch Sega-Zero / Callipso dafür erwähnen, dass sie mir etwas mathematischen Dschungel in den Sinn gebracht haben.

Das ist vielleicht alles, was ich Ihnen sagen möchte.

Für Kritik oder Fragen zu diesem Artikel oder einfach nur Tipps wäre ich dankbar. Meine Kontaktdaten: [E-Mail geschützt], ICQ-337310594.

Mit freundlichen Grüßen, Evil`s Interrupt.

P.S.: Ich habe mit diesem Artikel nicht versucht, irgendjemanden zu übertrumpfen. Es wurde mit der Absicht geschrieben, das Studium von GOST zu erleichtern, und wenn Sie Schwierigkeiten haben, bedeutet dies nicht, dass ich dafür verantwortlich bin. Seien Sie vernünftig und haben Sie Geduld, alles Gute für Sie!

Der in der Gesellschaft bekannte Begriff „Prozessorleistung“ ist eine objektive, berechnete Größe, die in Flops gemessen wird. Die Mehrheit misst es jedoch in Gigahertz und glaubt naiv, dass dies dasselbe ist. Niemand kennt den Begriff „Code-Performance“, und ich werde gleich erklären, warum.

Der Grund ist, dass ich erst vor kurzem darauf gekommen bin und noch niemandem davon erzählt habe. Die Codeleistung hat jedoch ebenso wie die Prozessorleistung objektive Eigenschaften, die gemessen werden können. In diesem Artikel geht es speziell um die Leistung des vom Prozessorkern ausgeführten Codes.

Wie wird die Codeleistung gemessen? Da ich der erste war, der darüber gesprochen hat, werde ich es nach dem Recht des Entdeckers in RTT-Skalen messen;).

Jetzt ernsthaft. In modernen Prozessoren sind die Haupttransformationen Operationen mit 32-Bit-Zahlen, alles andere ist im Großen und Ganzen exotisch. Daher werden wir die Hauptsache berücksichtigen - Operationen mit 32-Bit-Zahlen. Was glauben Sie, wie viele 32-Bit-Operationen der Kern eines modernen Prozessors gleichzeitig ausführen kann?

Der Student wird antworten – eins, sein Lehrer wird denken und sagen, dass vier, der Profi – dass es bisher nur zwölf Operationen gibt.

Ein Programmcode, der alle ausführenden Einheiten des Prozessors während der gesamten Codeausführungszeit gleichzeitig lädt, hat also eine Leistung von 12 RTT NIS. Maximal! Um ehrlich zu sein, habe ich noch nie zuvor einen solchen Code geschrieben, aber in diesem Artikel werde ich versuchen, mir die Mühe zu machen.

Ich werde beweisen, dass Code mit gleichzeitiger Ausführung von zwölf 32-Bit-Operationen möglich ist

Der Programmcode, der eine Ausführungseinheit im Prozessorkern verwendet, wird natürlich eine Leistung von 1 RTT haben. Von Sprachcompilern erzeugte Programme können sich einer solchen Codeleistung "rühmen". hohes Level, und Dolmetscher virtuelle Maschinen. Es sollte nicht davon ausgegangen werden, dass die CPU-Auslastungsanzeige, die im Task-Manager des Betriebssystems zu sehen ist, als objektives Kriterium für die Wirksamkeit des Codes dienen kann. Die Auslastung des Prozessorkerns kann 100 % betragen, aber der Programmcode verwendet darin ein Ausführungsgerät (Performance 1 RTT). In diesem Fall arbeitet der Prozessorkern bei 100 % Last mit 1/12 seiner maximalen Leistung. Mit anderen Worten, wenn der Windows Task-Manager die maximale CPU-Auslastung anzeigt, kann seine tatsächliche Leistung zwischen 1 und 12 RTT variieren. Wenn man im Leistungsfenster 100% Auslastung auf irgendeinem Prozessorkern sieht, ist es auf keinen Fall falsch anzunehmen, dass alle ausführenden Geräte in diesem Kern arbeiten!

Das einzige Kriterium für die indirekte Bewertung des Betriebs eines Prozessorkerns mit maximale Performance kann der Stromverbrauch und damit die Geräuschentwicklung des Kühlers sein. Nun, wenn der Kühler laut ist, dann ja - die Last ist auf das Maximum gegangen. Es ist jedoch an der Zeit, mit allgemeinen Konzepten abzuschließen und zur harten Praxis überzugehen.

Traditionelle Implementierung von GOST 28147-89

Ich bin kein Profi auf dem Gebiet Informationssicherheit, aber immer noch mit dem Thema Verschlüsselung vertraut. Es waren meine Gespräche mit einem professionellen Kryptografen, den ich sehr schätze, die mich dazu inspirierten, mich speziell mit der symmetrischen Stream-Verschlüsselung zu befassen. Und nachdem ich dieses Thema aufgegriffen hatte, versuchte ich, es gut zu machen, und zwar nicht nur gut, sondern auch schnell, indem ich die maximale Anzahl von Operationen pro Zeiteinheit durchführte. Das heißt, ich stand vor der Aufgabe, den Programmcode mit dem maximalen RTT-Wert zu schreiben.

Die kryptografische Konvertierung nach GOST 28147-89 wird zur Streaming-Verschlüsselung von Informationen in Kommunikationskanälen und auf Laufwerken verwendet.

Derzeit ist die Softwareimplementierung dieses GOST auf RON weit verbreitet. Zentralprozessor. Bei den bekannten Verfahren zur Implementierung von GOST werden alle geheimen Informationen (Verschlüsselungsschlüssel, Ersatzblöcke) eingefügt Arbeitsspeicher. Dies verringert die Zuverlässigkeit der Verschlüsselung, da es mit einem RAM-Dump möglich ist, alle geheimen Elemente der Kryptotransformation vollständig aufzudecken. Außerdem weist das Verfahren Geschwindigkeitsbeschränkungen aufgrund der Position der Hauptobjekte der Kryptotransformation im OP und des unvollständigen Ladens der ALU-Ausführungsvorrichtungen auf. Moderne Prozessoren, die ein Kryptoverfahren mit einem bekannten Verfahren implementieren, können eine Verschlüsselungsgeschwindigkeit von 40–60 Megabyte pro Sekunde bereitstellen. Und wenn Sie es wirklich bis zum Ende verstehen, dann ist der Grund für die geringe Performance und schwache Sicherheit der Krypto-Konvertierung die Software-Implementierung des Substitutionsblocks. Siehe seine Beschreibung in GOST in Abb. 1.

Gemäß Abschnitt 1.2 von GOST implementiert dieser Block Tetraden-Permutationen (vier Bits) in einem 32-Bit-Wort, aber die x86/64-Prozessorarchitektur und ihr Befehlssatz sind nicht in der Lage, Tetraden effektiv zu manipulieren.

Für die Softwareimplementierung des Substitutionsblocks werden spezielle Tabellen im RAM verwendet, die in der Phase der Initialisierung der Kryptofunktion vorbereitet werden. Diese Tabellen kombinieren die Substitutionsknoten benachbarter Tetraden in 8 × 8-Bit-Byte-Tabellen, sodass im RAM vier 256-Byte-Tabellen vorhanden sind.

In fortgeschritteneren Implementierungen haben diese Tabellen eine Größe von 1024 Bytes (256 Wörter von vier Bytes). Dies geschieht, um in den Tabellen eine zusätzliche zyklische Verschiebung um 11 Positionen des 32-Bit-Wortes zu implementieren, das als Ergebnis der Substitution (der nächsten Operation des Konvertierungsalgorithmus gemäß GOST) erhalten wird. Ein Beispiel für die Umsetzung von GOST gem diese Methode siehe Anhang 1 (auf Diskette).

Die Information des Substitutionsblocks ist ein geheimer Bestandteil der Kryptofunktion (wie sie in GOST formuliert ist, siehe Abb. 2).

Die Platzierung dieser Tabellen mit den Schlüsseln des Substitutionsblocks im OP widerspricht den Anforderungen von GOST (Abschnitt 1.7), da geheime Informationen verfügbar werden Programme von Drittanbietern Arbeiten an einer Computerinstallation. Der FSB, der auch Softwareimplementierungen von Verschlüsselungen nach GOST zertifiziert, sieht diesen Verstoß, gelinde gesagt, herablassend. Wenn der FSB zum Platzieren von Schlüsseln im OP immer noch ein „Feigenblatt“ benötigt – das Maskieren der Schlüssel mit der XOR-Operation, dann ist nichts für Ersatzblöcke im OP erforderlich, sie werden im Klartext gespeichert.

Kurz gesagt, der FSB überspringt solche Softwareimplementierungen des Kryptoverfahrens trotz der offensichtlichen Verringerung der Stärke einer solchen Lösung und einer direkten Verletzung seiner eigenen Anforderungen gemäß GOST (Klausel 1.7). Und dies trotz der bekannten Methoden zum Brechen von Chiffren durch das Entfernen eines Speicherauszugs ...

Wir werden etwas später auf das Problem der Speicherung von Schlüsseln und Ersatzblöcken in den internen Registern des Prozessors zurückkommen (es gibt eine schöne und schnelle Lösung), aber im Moment werden wir nur Verschlüsselungsschlüssel in MMX-Registern speichern, das ist zuverlässiger.

Aber genug der Texte, wichtig im Rahmen des betrachteten Themas ist, dass dieser Programmcode eine Performance von 1 RTT-shku hat. Lassen Sie uns nun einen Code mit einer Leistung von 2 RTTs schreiben.

Multithread-Implementierung von GOST 28147-89

Die einzige Möglichkeit, die Kryptoverfahren in dem bekannten Algorithmus zu beschleunigen, ist die Einführung von Multithreading. Der Sinn einer solchen Änderung in der Implementierung des Algorithmus besteht darin, mehrere Datenblöcke gleichzeitig parallel zu berechnen.

Die meisten Programmierer meinen mit paralleler Verarbeitung nur die Arbeit mehrerer Prozessorkerne, synchronisiert durch Interrupts und Semaphoren im Speicher.

Es gibt jedoch noch eine weitere Variante der parallelen Datenverarbeitung auf einem einzigen Prozessorkern. Lassen Sie mich diese nicht offensichtliche Idee erklären.

Moderne Prozessoren enthalten mindestens zwei und sogar drei bis sechs Arithmetik-Logik-Einheiten. Diese ALUs (FPUs, Adressarithmetikeinheiten usw.) können unabhängig voneinander arbeiten, die einzige Bedingung für ihren parallelen Betrieb sind nicht überlappende Softwareobjekte, auf denen sie arbeiten. Mit anderen Worten, in Befehlen, die gleichzeitig die ALU ausführen, müssen die Speicheradressen und Registernummern unterschiedlich sein. Oder es sollten keine Schreiboperationen an gemeinsamen Registern und Speicheradressen durchgeführt werden, auf die durch verschiedene ausführende Einheiten des Prozessors zugegriffen wird.

Das Laden der Arbeit aller ALUs wird von einem speziellen Hardwareblock im Prozessorkern gesteuert - dem Scheduler, der den ausführbaren Code bis zu einer Tiefe von 32-64 Bytes durchschaut. Wenn der Scheduler Befehle findet, die auf der ALU ohne Konflikte ausgeführt werden können, führt er sie gleichzeitig auf verschiedenen Ausführungseinheiten aus. In diesem Fall zeigt der Zähler der ausgeführten Befehle auf den ausführbaren Befehl (in einem solchen Schema gibt es mehrere davon), wonach alle Befehle bereits ausgeführt wurden.

Die meisten automatisch (von Compilern) generierten Programmabläufe können nicht alle ALUs und FPUs laden, die sich im Prozessorkern befinden. In diesem Fall befindet sich die Prozessorhardware im Leerlauf, was die resultierende Leistung erheblich reduziert. Prozessorentwickler verstehen dies und führen Modi ein, um die Kernfrequenz zu erhöhen, wenn das Gerät nicht voll ausgelastet ist. Darauf sind auch Hypertradingsysteme ausgelegt, und ich werde dieses System nutzen, um den Code in Zukunft maximal zu „pressen“.

Compiler, selbst die am besten optimierten, und noch mehr - Engines virtueller Maschinen, können keinen optimierten Code in Bezug auf die Leistung generieren. Nur ein Programmierer mit Ingenieurswissen kann einen solchen optimierten Code schreiben, und das Werkzeug zum Schreiben ist ausschließlich Assembler.

Ein charakteristisches Beispiel für die Möglichkeit, mehrere unabhängige Programm-Threads auf einem Prozessorkern auszuführen, ist die GOST-Implementierung, die in zwei Threads auf einem einzigen Prozessorkern ausgeführt wird. Die Idee des Codes ist einfach: Es gibt zwei Datenblöcke für die Verschlüsselung/Entschlüsselung, aber einen Prozessorkern, der die Konvertierung durchführt. Es ist möglich, die Transformation für diese beiden Datenblöcke sequentiell durchzuführen, und dies wurde bisher getan. In diesem Fall wird die zum Durchführen der Transformationen benötigte Zeit verdoppelt.

Aber Sie können auch anders: alternative Befehle, die sich auf die Verarbeitung verschiedener Datenblöcke beziehen. Grafisch sind diese Optionen in Abb. 3.

In der Abbildung zeigt das obere Beispiel die übliche Reihenfolge, in der zwei unabhängige Datenblöcke verarbeitet werden. Zuerst wird der erste Block verarbeitet, dann fährt der Prozessor mit der Verarbeitung des zweiten Blocks fort. Die resultierende Zeit ist natürlich gleich der doppelten Zeit, die benötigt wird, um einen Block zu verarbeiten, und die Ausführungseinheiten des Prozessorkerns werden nicht vollständig belastet.

Das Folgende zeigt ein Beispiel mit verschachtelten Befehlen aus verschiedenen Verarbeitungs-Threads. In diesem Fall werden Befehle, die sich auf verschiedene Datenblöcke beziehen, verschachtelt. Der Scheduler wählt voneinander unabhängige Befehle aus und leitet sie zur Ausführung an ALU1 und ALU2 weiter. Die Gruppierung von Befehlen des ersten und zweiten Threads auf diesen ALUs wird automatisch ausgeführt, da der Operationsalgorithmus des Planers eine Gruppierung von Befehlen mit Getriebe gemäß gemeinsamen Daten auf derselben Ausführungsvorrichtung umfasst.

Damit ein solcher Programmcode ohne ALU-Leerlaufzeit arbeiten kann, ist es erforderlich, dass jeder Programm-Thread mit seinem eigenen Satz von Registern arbeitet. Der Cache in diesem Schema wird zu einem Engpass (er hat nur zwei Datenausgabeports), also speichern wir die Schlüssel in MMX-Registern. Da in diesem Fall die Ersetzungs- (und Verschiebungs-) Knoten im Speicher schreibgeschützt sind, können sie von beiden Programm-Threads gemeinsam genutzt werden.

Dies ist natürlich eine sehr vereinfachte Erklärung des Prinzips der parallelen Ausführung von Programm-Threads auf einem einzelnen Kern, in Wirklichkeit ist alles viel komplizierter. In der Praxis müssen die Pipeline-Architektur der Ausführungseinheiten, Einschränkungen beim gleichzeitigen Zugriff auf den Cache und den Block der RON-Register, das Vorhandensein von Adressarithmetikknoten, Schaltern und vielem mehr berücksichtigt werden ... Das ist also a Thema für Profis, die sich an den Fingern einer Hand abzählen lassen.

Das parallele Verschlüsselungsverfahren wird effektiv nur für den 64-Bit-Prozessor-Betriebsmodus implementiert, da in diesem Modus eine ausreichende Menge an RON vorhanden ist (bis zu 16 Stück!). Ein Beispiel für die Implementierung von GOST gemäß dieser Methode ist in Anhang 2 (auf Diskette) gezeigt.

Es ist klar, dass diese GOST-Implementierung eine Codeleistung von 2 RTTs hat. Sehen wir uns nun an, wie sich dies auf die Ausführungszeit auswirkt.

Der Verschlüsselungszyklus für einen Strom (Anhang 1) beträgt 352 Zyklen, und während dieser Zeit werden 8 Byte Daten berechnet, für eine Zweistrom-Implementierung von GOST (Anhang 2) werden 416 Prozessorzyklen benötigt, aber 16 Byte werden berechnet. Somit erhöht sich die resultierende Konvertierungsgeschwindigkeit von 80 auf 144 Megabyte für einen 3,6-GHz-Prozessor.

Es ergibt sich ein interessantes Bild: Der Code enthält genau doppelt so viele Anweisungen, und es dauert nur 15 % länger, aber ich denke, die Leser haben den Grund für dieses Phänomen bereits verstanden ...

Theoretisch sollte der Code aus dem zweiten Beispiel in der gleichen Anzahl von Zyklen ausgeführt werden wie der Code aus dem ersten Beispiel, aber der Scheduler-Knoten wird entwickelt, obwohl Ingenieure von Intel, sondern auch Menschen, und wir sind alle weit davon entfernt, perfekt zu sein. Es besteht also die Möglichkeit, die Wirksamkeit ihrer Erstellung zu bewerten. Dieser Code funktioniert auch auf einem AMD-Prozessor, und Sie können die Ergebnisse vergleichen.

Wenn mir das jemand nicht glauben mag, dann sind für solche Ungläubigen Testprogramme mit Taktzählern auf der Diskette enthalten. Programme ein Quellcodes, natürlich in Assembler, also gibt es die Möglichkeit, meine Worte zu überprüfen und gleichzeitig einige Tricks des professionellen Codierens zu sehen.

Verwendung von SSE-Registern und AVX-Befehlen moderner Prozessoren zur Implementierung von GOST 28147-89

Prozessoren mit moderner x86/64-Architektur enthalten einen Satz von 16-Byte-SSE-Registern und spezialisierte FPUs (mindestens zwei), um verschiedene Operationen an diesen Registern auszuführen. Es ist möglich, GOST auf diesem Gerät zu implementieren, und in diesem Fall können Ersatzknoten nicht in Form von Tabellen im RAM, sondern direkt in dedizierten SSE-Registern platziert werden.

Auf einem SSE-Register können Sie gleichzeitig zwei Tabellen mit 16 Zeilen platzieren. Somit nehmen vier SSE-Register vollständig alle Ersetzungstabellen auf. Die einzige Bedingung für eine solche Platzierung ist die Verschachtelungsanforderung, wonach Tetraden desselben Bytes in verschiedenen SSE-Registern platziert werden müssen. Außerdem ist es ratsam, die Low- und High-Tetraden der Eingangsbytes jeweils in die Low- und High-Tetraden der SSE-Register zu legen.

Diese Anforderungen werden durch die Optimierung für den vorhandenen Satz von AVX-Befehlen bestimmt. Somit enthält jedes Byte des SSE-Registers zwei Tetraden, die unterschiedlichen Bytes des Eingangsregisters des Substitutionsblocks entsprechen, während die Position des Bytes im SSE-Register eindeutig dem Index in der Ersetzungstabelle des Substitutionsblocks entspricht.

Ein Diagramm einer der möglichen Platzierungen von Ersatzknoten auf SSE-Registern ist in Abb. 2 gezeigt. 4.

Das Platzieren geheimer Informationen von Substitutionsknoten in SSE-Registern erhöht die Sicherheit des Kryptoverfahrens, aber eine vollständige Isolierung dieser geheimen Informationen ist unter den folgenden Bedingungen möglich:

• Der Prozessorkern wurde in den Hypervisor-Host-Modus versetzt und der Interrupt-Block (APIC) zwangsweise deaktiviert. In diesem Fall ist der Prozessorkern vollständig von dem Betriebssystem und den Anwendungen isoliert, die auf der Computerinstallation ausgeführt werden.
• Das Laden von SSE-Registern und das Isolieren des Rechenkerns wird vor dem Start des Betriebssystems durchgeführt; es ist optimal, diese Prozeduren vom Trusted Boot Module (TDM) auszuführen.
• Programme von Kryptoverfahren nach GOST werden im nicht modifizierbaren Speicherbereich der Recheneinheit (entweder BIOS oder Flash-Speicher MDZ) abgelegt.

Die Einhaltung dieser Anforderungen gewährleistet vollständige Isolation und Unveränderlichkeit Programmcode Kryptoverfahren und die darin verwendeten geheimen Informationen.

Für ein effektives Abtasten aus den SSE-Registern von Tetraden werden die in den FPU-Einheiten verfügbaren Mehreingangs-Byte-Schalter verwendet. Diese Schalter ermöglichen Übertragungen von jedem Byte der Quelle zu jedem Byte des Ziels durch Indizes, die sich in einem speziellen SSE-Indexregister befinden. Außerdem wird die Übertragung parallel für alle 16 Bytes des SSE-Registerempfängers durchgeführt.

Mit Substitutionsspeicherknoten auf SSE-Registern und einem Multi-Input-Switch in FPU-Einheiten ist es möglich, die folgende Transformation in der Substitutionseinheit zu organisieren (Fig. 5).

Bei diesem Schema stellt das Eingangsregister in jeder Tetrade die Adresse für den entsprechenden Schalter ein, der Informationen von den Ersatzknotentreibern über den Datenbus an das Ausgangsregister überträgt. Ein solches Schema kann auf drei Arten organisiert werden:

• Erstellen Sie ein geeignetes Chipdesign, aber das ist fantastisch für uns.
• Das Neuprogrammieren des Mikrocodes und das Erstellen eigener Prozessoranweisungen zum Implementieren dieser Funktion auf vorhandenen Prozessoren ist keine Fantasie mehr, aber leider unter den gegenwärtigen Bedingungen unrealistisch.
• Schreiben Sie ein Programm mit den offiziellen AVX-Befehlen. Die Option ist zwar nicht sehr effektiv, aber wir können sie „hier und jetzt“ umsetzen. Das werden wir also als nächstes tun.

Die Schalter werden durch einen speziellen Drei-Adressen-Befehl AVX VPSHUFB gesteuert. Sein erster Operand ist der Empfänger von Informationen von den Schaltern, der zweite ist die Quelle, mit der die Eingänge der Schalter verbunden sind. Der dritte Operand ist ein Steuerregister für Schalter, von denen jedes Byte einem entsprechenden Schalter zugeordnet ist; der darin enthaltene Wert gibt die Nummer der Richtung an, aus der der Schalter Informationen liest. Eine Beschreibung dieses Befehls aus der offiziellen Intel-Dokumentation finden Sie in Abb. 5. In Abb. Abbildung 6 zeigt die Funktionsweise dieses Befehls – nur die Hälfte der SSE-Register wird angezeigt, für die zweite Hälfte ist alles ähnlich.

Der Schalter verwendet nur die niederwertigsten vier Bits, um die Schaltrichtung zu bestimmen, das letzte Bit in jedem Byte wird verwendet, um das entsprechende Empfängerbyte auf Null zu zwingen, aber diese Schalterfunktion wird in unserem Fall noch nicht benötigt.

Ein Programm mit einer Auswahl von Notebooks über FPU-Schalter wurde geschrieben, aber ich habe es nicht einmal in die Anwendung eingefügt - es ist zu schlecht. Ein 128-Bit-Register zu haben und nur 32 Bit darin zu verwenden, ist unprofessionell.

Wie sie sagen: „Unser Ziel ist der Horizont“, also pressen Sie es so aus ... wir pressen es und packen es in Säcke!

Dies ist kein Wortspiel, sondern eine harte FPU-Realität - SSE-Register können in gleiche Teile geteilt werden und dieselben Transformationen können an diesen Teilen mit einem Befehl durchgeführt werden. Damit der Prozessor dies versteht, gibt es einen magischen Buchstaben "P" - ein Paket, das vor der Befehlsmnemonik platziert wird, und nicht weniger magische Buchstaben "Q", "D", "W", "B". werden ans Ende gesetzt und geben an, in welche Teile die SSE-Register in diesem Befehl aufgeteilt sind.

Wir sind interessiert an Batch-Modus mit einer Aufteilung des SSE-Registers in vier 32-Bit-Blöcke; dementsprechend wird allen Befehlen ein „P“ vorangestellt und ein „D“-Symbol abgeschlossen. Dadurch ist es möglich, mit einem Prozessorbefehl vier Blöcke zu je 32 Bit parallel zu verarbeiten, also vier Datenblöcke parallel zu berechnen.

Das Programm, das diese Methode implementiert, ist in Anhang 3 verfügbar, dort sind alle Erklärungen.

Aber drücke so drücke! Moderne Prozessoren haben mindestens zwei FPUs, und zwei unabhängige Befehlsströme können verwendet werden, um sie vollständig zu laden. Wenn Sie Befehle aus unabhängigen Streams korrekt verschachteln, können Sie beide FPUs vollständig laden und erhalten acht parallel verarbeitete Datenströme auf einmal. Ein solches Programm wurde geschrieben, und Sie können es in Anhang 4 sehen, aber Sie müssen genau hinsehen - Sie können verrückt werden. Das nennt man "der Kodex ist nicht jedermanns Sache ...".

Ausgabepreis

Die Verwendung von SSE-Registern zum Speichern von Ersatzknoten ist verständlich - es gibt eine gewisse Garantie für die Isolierung geheimer Informationen, aber die Bedeutung der Berechnung der Kryptofunktion selbst auf der FPU ist nicht offensichtlich. Daher wurden Messungen der Ausführungszeit von Standardverfahren nach dem direkten Ersatzverfahren gemäß GOST für vier und acht Streams durchgeführt.

Für vier Threads wurde eine Ausführungsgeschwindigkeit von 472 Prozessorzyklen erhalten. Somit wird bei einem Prozessor mit einer Frequenz von 3,6 GHz ein Thread mit einer Geschwindigkeit von 59 Megabyte pro Sekunde bzw. vier Threads mit einer Geschwindigkeit von 236 Megabyte pro Sekunde betrachtet.

Für acht Threads wurde eine Ausführungsgeschwindigkeit von 580 Prozessorzyklen erhalten. So wird bei einem 3,6-GHz-Prozessor ein Thread mit einer Geschwindigkeit von 49 Megabyte pro Sekunde und acht Threads mit einer Geschwindigkeit von 392 Megabyte pro Sekunde betrachtet.

Wie der Leser vielleicht bemerkt, hat der Code in Beispiel #3 einen Durchsatz von 4 RTT, während der Code in Beispiel #4 einen Durchsatz von 8 RTT hat. In diesen Beispielen sind die Muster auf SSE-Registern die gleichen wie bei der Verwendung von RON, nur der Scheduler hat seine Effizienz reduziert. Es bietet jetzt eine 20 % längere Dauer bei einer 2-fachen Erhöhung der Codelänge.

Darüber hinaus wurden diese Ergebnisse mit den universellen AVX-Befehlen erzielt, die sowohl in verfügbar sind Intel-Prozessoren, und in AMD-Prozessoren. Wenn Sie für einen AMD-Prozessor optimieren, wird das Ergebnis viel besser sein. Klingt gegen den Trend, ist aber dennoch wahr, und hier ist der Grund: AMD-Prozessoren haben einen zusätzlichen Befehlssatz, die sogenannte XOP-Erweiterung, und in dieser zusätzlicher Satz Es gibt Befehle, die die Implementierung des GOST-Algorithmus erheblich vereinfachen.

Dies bezieht sich auf die Befehle der logischen Paketverschiebung von Bytes und der zyklischen Paketverschiebung von Doppelworten. Die in den Anhängen 3 und 4 angegebenen Beispiele verwenden Sequenzen universeller Befehle, die die notwendige Transformation implementieren: im ersten Fall ein "zusätzlicher" Befehl und im anderen Fall vier zusätzliche Befehle auf einmal. Optimierungsreserven sind also vorhanden, und zwar beträchtliche.

Wenn wir über eine weitere Optimierung sprechen, sollten Sie sich an das Vorhandensein von 256-Bit-Registern (YMM-Registern) erinnern, mit denen Sie die Berechnungsgeschwindigkeit theoretisch verdoppeln können. Aber das ist vorerst nur eine Aussicht, im Moment verlangsamen Prozessoren stark, wenn sie 256-Bit-Befehle ausführen (FPUs haben eine Pfadbreite von 128 Bit). Experimente haben gezeigt, dass bei modernen Prozessoren eine Anzahl von 16 Threads in YMM-Registern keinen Gewinn ergibt. Aber das ist nur jetzt, bei neuen Prozessormodellen wird die Geschwindigkeit von 256-Bit-Befehlen zweifellos erhöht, und dann wird die Verwendung von 16 parallelen Threads sinnvoll und führt zu einer noch stärkeren Geschwindigkeitssteigerung des Kryptoverfahrens.

Theoretisch kann man mit einer Geschwindigkeit von 600-700 Megabyte pro Sekunde rechnen, wenn der Prozessor über zwei FPUs mit einer Arbeitspfadbreite von jeweils 256 Bit verfügt. In diesem Fall können wir davon sprechen, Code mit einer Effizienz von 16 RTT zu schreiben, und das ist keine Fantasie, sondern die nahe Zukunft.

Mischform

Auch hier stellt sich die Frage nach der Anzahl der Register, sie reichen nicht aus, um einen solchen Algorithmus zu fördern. Aber der Hypertrading-Modus wird uns helfen. Der Prozessorkern verfügt über einen zweiten Registersatz, der im logischen Prozessormodus verfügbar ist. Daher führen wir denselben Code gleichzeitig auf zwei logischen Prozessoren aus. In diesem Modus haben wir natürlich keine weiteren Executive-Geräte, aber aufgrund des Wechsels können wir eine volle Ladung aller Executive-Geräte erhalten.

Sie können hier nicht mit einer Steigerung von 50 % rechnen, der Engpass ist der Cache-Speicher, in dem technologische Masken gespeichert werden, aber Sie können immer noch eine Steigerung von 100 zusätzlichen Megabyte erzielen. Diese Option ist nicht in den Anhängen aufgeführt (die Makros sind die gleichen wie die im 8 RTT-Code verwendeten), aber sie ist in verfügbar Programmdateien. Wer also nicht an die Möglichkeit einer Verschlüsselung mit einer Geschwindigkeit von 500 Megabyte pro Sekunde auf einem einzigen Prozessorkern glaubt, soll die Testdateien laufen lassen. Es gibt auch Texte mit Kommentaren, damit niemand denkt, ich sei schlau.

Diese Fokussierung ist nur auf Intel-Prozessoren möglich, AMD hat nur zwei FPUs pro zwei Prozessormodule (analog zum Hyper-Trading-Modus). Aber es gibt noch vier weitere ALUs, die nicht zu verwenden eine Sünde sind.

Sie können die Prozessormodule des Bulldozers in einen ähnlichen Modus wie den Hyperhandelsmodus treiben, aber die Konvertierung in RON auf verschiedenen Modulen in einem Thread und in SSE-Register in einem anderen Thread ausführen und die gleichen 12 RTT erhalten. Ich habe diese Option nicht getestet, aber ich denke, dass der Code in 12 RTT auf AMD effizienter funktionieren wird. Wer will, kann es ausprobieren, Testprogramme lassen sich ganz einfach an die „Bulldozer“ anpassen.

Wer braucht es?

Eine ernsthafte Frage, aber mit einer einfachen Antwort - jeder braucht sie. Bald werden wir uns alle auf die Wolken setzen, wir werden dort sowohl Daten als auch Programme speichern, und dort, oh, wie Sie Ihre eigene, private Ecke ausstatten möchten. Dazu müssen Sie den Datenverkehr verschlüsseln, und die Geschwindigkeit der Kryptokonvertierung wird der Hauptfaktor für ein komfortables Arbeiten in der Cloud sein. Unsere Auswahl an Verschlüsselungsalgorithmen ist gering - entweder GOST oder AES.

Außerdem stellt sich seltsamerweise heraus, dass die in die Prozessoren integrierte AES-Algorithmus-Verschlüsselung viel langsamer ist, Tests zeigen eine Geschwindigkeit von 100-150 Megabyte pro Sekunde, und das bei der Hardware-Implementierung des Algorithmus! Das Problem liegt in der Singlethread-Zählung und dem Ersetzungsblock, der mit Bytes (einer Tabelle mit 256 Zeilen) arbeitet. So erweist sich GOST in der Implementierung auf der x86/64-Architektur als effizienter, wer hätte das gedacht ...

Dies ist, wenn wir über die erreichte Verschlüsselungsgeschwindigkeit sprechen. Und wenn wir die theoretischen Verfeinerungen im Bereich der Verbesserung der Effizienz des Codes im Auge behalten, dann braucht es höchstwahrscheinlich niemand. Es gibt praktisch keine Spezialisten für Level 3–6 RTT, Compiler generieren im Allgemeinen Code auf Level 1–2.5 RTT, und die Mehrheit der Programmierer kennt Assembler nicht, und wenn sie seine Schreibweise kennen, verstehen sie das Gerät von a nicht moderner Prozessor. Und ohne dieses Wissen, was ist Assembler, was ist eine Art SI-Sharp - es spielt keine Rolle.

Aber nicht alles ist so traurig: Unter dem Strich steht nach einer Woche schlafloser Nächte ein neuer Algorithmus für die Implementierung von GOST, der nicht patentiert werden sollte. Und Patentanmeldungen (bis zu drei) wurden bereits erstellt und eingereicht, also, Herren, Geschäftsleute, Schlange stehen - Frauen und Kinder haben einen Rabatt.

Dieser Algorithmus ist zwingend für die Verwendung als Verschlüsselungsalgorithmus in Regierungsorganisationen RF und eine Reihe von kommerziellen.

Beschreibung des Algorithmus

Das Schema des Algorithmus ist in Abb. 1 dargestellt. 3.1. Wie Sie sehen können, ist das Schema dieses Algorithmus ziemlich einfach, was seine Software- oder Hardwareimplementierung eindeutig vereinfacht.

Der Algorithmus GOST 28147-89 verschlüsselt Informationen in Blöcken von 64 Bit, die in zwei Unterblöcke von 32 Bit (N1 und N2) unterteilt sind. Unterblock N1 wird auf eine bestimmte Weise verarbeitet, wonach sein Wert hinzugefügt wird

mit dem Teilblockwert N2 (Addition erfolgt modulo 2), dann werden die Teilblöcke vertauscht. Eine solche Transformation wird für eine bestimmte Anzahl von Runden durchgeführt: 16 oder 32, je nach Betriebsmodus des Algorithmus (unten beschrieben). Die folgenden Operationen werden in jeder Runde durchgeführt:

1. Tastenauflage. Der Inhalt des Unterblocks /VI wird modulo 2 32 zum Kx-Teil des Schlüssels hinzugefügt.

Der Verschlüsselungsschlüssel des GOST 28147-89-Algorithmus hat eine Dimension von 256 Bit, und Kx ist sein 32-Bit-Teil, d. h. ein 256-Bit-Verschlüsselungsschlüssel wird als Verkettung von 32-Bit-Unterschlüsseln dargestellt (Abb. 3.2):

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

Bei der Verschlüsselung wird je nach Rundenzahl und Arbeitsweise des Algorithmus einer dieser Unterschlüssel verwendet.

Reis. 3.1. Schema des Algorithmus GOST 28147-

Reis. 3.2. Verschlüsselungsschlüssel des GOST 28147-89-Algorithmus

2. Tabellarische Ersetzung. Nach dem Überlagern des Schlüssels wird der /VI-Unterblock in 8 Teile von 4 Bits unterteilt, deren Wert einzeln gemäß der Ersetzungstabelle für diesen Teil des Unterblocks ersetzt wird. Tabellenersetzungen (Ersetzungsbox, S-Box) werden häufig in modernen Verschlüsselungsalgorithmen verwendet, daher lohnt es sich, sie genauer zu betrachten.

Die Tabellenersetzung wird auf diese Weise verwendet: Dem Eingang wird ein Datenblock einer bestimmten Dimension (in diesem Fall 4 Bit) zugeführt, dessen numerische Darstellung die Nummer des Ausgangswerts bestimmt. Zum Beispiel haben wir eine S-Box der folgenden Form:

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

Lassen Sie den 4-Bit-Block „0100“ an den Eingang kommen, d. h. der Wert ist 4. Laut Tabelle ist der Ausgangswert 15, d. h. „1111“ (0 wird durch 4 ersetzt, 1 wird durch 11 ersetzt, der Wert von 2 wird nicht verändert usw.).

Wie Sie sehen können, ist das Schema des Algorithmus sehr einfach, was bedeutet, dass die größte Last der Datenverschlüsselung auf die Ersatztabellen fällt. Leider hat der Algorithmus die Eigenschaft, dass es „schwache“ Substitutionstabellen gibt, anhand derer der Algorithmus durch kryptoanalytische Methoden aufgedeckt werden kann. Zu den schwachen gehört beispielsweise eine Tabelle, bei der die Ausgabe gleich der Eingabe ist:

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

3. Bitweise zyklische Linksverschiebung um 11 Bit.

Algorithmus-Modi

Der GOST 28147-89-Algorithmus hat 4 Betriebsmodi:

□ einfacher Ersatzmodus;

□ Gamma-Modus;

P Spielmodus mit Feedback;

□ Herstellungsweise von imitierten Anbauteilen.

Diese Modi unterscheiden sich etwas von den allgemein akzeptierten (in Abschnitt 1.4 beschriebenen), daher lohnt es sich, sie genauer zu betrachten.

Diese Modi haben unterschiedliche Zwecke, verwenden jedoch die gleiche oben beschriebene Verschlüsselungsumwandlung.

Einfacher Swap-Modus

Im einfachen Ersetzungsmodus werden die oben beschriebenen 32 Runden einfach durchgeführt, um jeden 64-Bit-Informationsblock zu verschlüsseln. 32-Bit-Unterschlüssel werden in der folgenden Reihenfolge verwendet:

□ KO, Kl, K2, K3, K4, K5, Kb, AG7, KO, ATI usw. - in den Runden 1 bis 24;

□ K1, Kb, K5, K4, K3, K2, K\, KO - in den Runden 25 bis 32.

Die Entschlüsselung im einfachen Ersetzungsmodus erfolgt auf genau die gleiche Weise, jedoch mit einer etwas anderen Reihenfolge der Verwendung von Unterschlüsseln:

□ KO, K\, K2, KZ, K4, K5, Kb, KP - in den Runden 1 bis 8;

□ KP, Kb, K5, K4, K3, K2, K\, KO, K1, Kb usw. - in den Runden 9 bis 32.

Ähnlich wie beim Standard-ECB-Modus wird der einfache Ersetzungsmodus aufgrund der separaten Verschlüsselung von Blöcken dringend nicht zum Verschlüsseln der eigentlichen Daten empfohlen; Es sollte nur verwendet werden, um andere Verschlüsselungsschlüssel in Mehrschlüsselschemata zu verschlüsseln.

Gamma-Modus

Im Gamma-Modus (Abb. 3.3) wird jeder Block des Klartextes bitweise modulo 2 an den Gamma-Block der Chiffre mit einer Größe von 64 Bit angehängt. Die Chiffre Gamma ist eine spezielle Sequenz, die mit den oben beschriebenen Transformationen wie folgt erzeugt wird:

1. In die Register N1 und N2 wird ihre anfängliche Füllung geschrieben - ein 64-Bit-Wert, der als "Sync-Nachricht" bezeichnet wird (eine Sync-Nachricht ist tatsächlich ein Analogon des Initialisierungsvektors in den Modi CBC, CFB und OFB). ).

2. Die Inhalte der /VI- und N2-Register (in diesem Fall Synchronisationsnachrichten) werden im einfachen Ersetzungsmodus verschlüsselt.

3. Der Inhalt von N1 wird modulo (2 32 - 1) mit der Konstanten CI = 2 24 + 2 16 + 2 8 + 4 addiert, das Ergebnis der Addition wird in das /VI-Register geschrieben.

4. Der Inhalt von N2 wird modulo 2 mit der Konstanten C2 = 2 24 + 2 16 + 2 8 +1 addiert, das Ergebnis der Addition wird in Register N2 geschrieben.

5. Die Inhalte der /VI- und N2-Register werden als 64-Bit-Verschlüsselungs-Gammablock ausgegeben (dh in diesem Fall bilden /VI und N2 den ersten Gammablock).

6. Wenn der nächste Gammablock benötigt wird (d. h. die Verschlüsselung oder Entschlüsselung fortgesetzt werden muss), kehren Sie zu Schritt 2 zurück.

Zur Entschlüsselung wird auf die gleiche Weise ein Gamma erzeugt, dann wird die XOR-Operation erneut auf den Chiffretext und die Gamma-Bits angewendet.

Um dasselbe Verschlüsselungs-Gamma zu generieren, muss der Benutzer, der das Kryptogramm entschlüsselt, denselben Schlüssel und denselben Synchronisierungsnachrichtenwert haben, die zum Verschlüsseln der Informationen verwendet wurden. Andernfalls können Sie den Originaltext nicht aus dem verschlüsselten erhalten.

In den meisten Implementierungen des GOST 28147-89-Algorithmus ist die Synchronisierungsnachricht kein geheimes Element, aber die Synchronisierungsnachricht kann so geheim sein wie der Verschlüsselungsschlüssel. In diesem Fall können wir davon ausgehen, dass die effektive Länge des Algorithmusschlüssels (256 Bit) um weitere 64 Bit der Sync-Nachricht erhöht wird, die als zusätzliches Schlüsselelement betrachtet werden können.

Feedback-Gamma-Modus

Im Feedback-Gamma-Modus werden ab dem 2. Block die Register /VI und L/2 nicht mit dem vorherigen Gamma-Block gefüllt, sondern mit dem Verschlüsselungsergebnis des vorherigen Klartext-Blocks (Abb. 3.4). Der erste Block in diesem Modus wird genau wie der vorherige generiert.

Reis. 3.4. Generierung der Chiffre Gamma im Gamma-Modus mit Rückkopplung

Imitationsgenerierungsmodus

Ein Spoof ist eine kryptografische Prüfsumme, die mithilfe eines Verschlüsselungsschlüssels berechnet wird und dazu bestimmt ist, die Integrität von Nachrichten zu überprüfen. Um es zu berechnen, gibt es einen speziellen Modus des GOST 28147-89-Algorithmus.

Die Generierung des Imitationspräfixes wird wie folgt durchgeführt:

1. Der erste 64-Bit-Informationsblock, für den der Impersonator berechnet wird, wird in die Register N1 und N2 geschrieben und im reduzierten einfachen Ersetzungsmodus verschlüsselt, in dem die ersten 16 Runden von 32 durchgeführt werden.

2. Das erhaltene Ergebnis wird modulo 2 mit dem nächsten Informationsblock summiert, wobei das Ergebnis in N1 und N2 gespeichert wird.

3. M und N2 werden wieder im reduzierten Modus des einfachen Ersetzens verschlüsselt, und so weiter bis zum letzten Informationsblock.

Als Präfix wird der resultierende 64-Bit-Inhalt der Register N1 und N2 oder ein Teil davon angesehen. Am häufigsten wird ein 32-Bit-Imitationspräfix verwendet, dh die Hälfte des Inhalts der Register. Das reicht aus, denn wie jede Prüfsumme soll das Imitationspräfix in erster Linie vor versehentlichem Verfälschen von Informationen schützen. Zum Schutz vor vorsätzlicher Veränderung von Daten werden andere kryptografische Verfahren eingesetzt – in erster Linie elektronische Digitale Unterschrift(siehe Abschnitt 1.1).

Das Nachahmungspräfix wird wie folgt verwendet:

1. Beim Verschlüsseln von Informationen wird der Klartext-Imitator berechnet und zusammen mit dem Chiffretext gesendet.

2. Nach der Decodierung wird das Imitationspräfix erneut berechnet und mit dem gesendeten verglichen.

3. Wenn die berechneten und gesendeten Imitationspräfixe nicht übereinstimmen, wurde der Chiffretext während der Übertragung verzerrt oder es wurden falsche Schlüssel bei der Entschlüsselung verwendet.

Das Imitationspräfix ist besonders nützlich, um die korrekte Entschlüsselung von Schlüsselinformationen bei der Verwendung von Mehrschlüsselschemata zu überprüfen.

Das Imitationspräfix ist ein Analogon des MAC-Nachrichtenauthentifizierungscodes, der im CBC-Modus berechnet wird. der Unterschied besteht darin, dass die Präfixberechnung keine Sync-Nachricht verwendet, während die MAC-Berechnung einen Initialisierungsvektor verwendet.

Kryptographische Stärke des Algorithmus

1994 wurde die Beschreibung des Algorithmus GOST 28147-89 ins Englische übersetzt und veröffentlicht; danach begannen die Ergebnisse seiner von ausländischen Experten durchgeführten Analysen zu erscheinen; Es wurden jedoch über einen längeren Zeitraum keine Angriffe gefunden, die sich einem praktikablen näherten.

□ große Schlüssellänge – 256 Bit; zusammen mit der geheimen Sync-Nachricht erhöht sich die effektive Schlüssellänge auf 320 Bit;

□ 32 Verwandlungsrunden; Bereits nach 8 Runden ist der volle Effekt der Streuung der Eingangsdaten erreicht: Die Änderung eines Bits des Klartextblocks wirkt sich auf alle Bits des Chiffretextblocks aus und umgekehrt, d.h. es gibt einen mehrfachen Sicherheitsabstand.

Betrachten Sie die Ergebnisse der Kryptoanalyse des GOST 28147-89-Algorithmus.

Analyse von Substitutionstabellen

Da in der Norm keine Substitutionstabellen angegeben sind, legen einige Arbeiten (z. B. in) nahe, dass eine „zuständige Organisation“ sowohl „gute“ als auch „schlechte“ Substitutionstabellen herausgeben kann. Der berühmte Experte Bruce Schneier nennt solche Annahmen jedoch "Gerüchte". Es ist klar, dass die kryptografische Stärke des Algorithmus stark von den Eigenschaften der verwendeten Substitutionstabellen abhängt bzw. es gibt schwache Substitutionstabellen (siehe oben für ein Beispiel), deren Verwendung den Angriff des Algorithmus vereinfachen kann. Dennoch scheint die Möglichkeit, verschiedene Substitutionstabellen zu verwenden, eine sehr lohnende Idee zu sein, die durch die folgenden zwei Fakten aus der Geschichte des DES-Verschlüsselungsstandards gestützt wird (siehe Abschnitt 3.15 für Details):

□ Angriffe, die sowohl die lineare als auch die differenzielle Kryptoanalyse des DES-Algorithmus verwenden, verwenden spezifische Merkmale von Substitutionstabellen; bei Verwendung anderer Tabellen muss die Kryptoanalyse von vorne beginnen;

□ Es wurden Versuche unternommen, DES gegenüber linearer und differentieller Kryptoanalyse zu stärken, indem stärkere Substitutionstabellen verwendet wurden; solche Tabellen, die in der Tat stabiler sind, wurden beispielsweise im S5-DES-Algorithmus vorgeschlagen; aber leider war es unmöglich, DES durch s 5 DES zu ersetzen, da die Ersatztabellen fest im Standard definiert sind bzw. die Implementierungen des Algorithmus wahrscheinlich nicht die Möglichkeit unterstützen, Tabellen auf andere zu ändern.

In einer Reihe von Arbeiten (z. B. , und ) wird fälschlicherweise geschlussfolgert, dass die geheimen Substitutionstabellen des Algorithmus GOST 28147-89 Teil des Schlüssels sein und seine effektive Länge erhöhen können (was nicht von Bedeutung ist, da der Algorithmus einen hat sehr großer 256-Bit-Schlüssel). Die Arbeit beweist jedoch, dass die geheimen Substitutionstabellen mit folgendem, praktisch anwendbarem Angriff berechnet werden können:

1. Setzen Sie den Nullschlüssel und suchen Sie nach dem „Nullvektor“, also dem Wert z = /(0), wobei /() die Rundungsfunktion des Algorithmus ist. Diese Phase dauert etwa 2 Verschlüsselungsvorgänge.

2. Mit dem Nullvektor werden die Werte der Substitutionstabellen berechnet, was nicht mehr als 2 11 Operationen dauert.

Algorithmusmodifikationen und ihre Analyse

In der Arbeit wurde eine Kryptoanalyse von Modifikationen des GOST 28147-89-Algorithmus durchgeführt:

□ der GOST-H-Algorithmus, bei dem relativ zum ursprünglichen Algorithmus die Reihenfolge der Verwendung von Unterschlüsseln geändert wird, nämlich in Runden vom 25. bis zum 32. Unterschlüssel werden in direkter Reihenfolge verwendet, d.h. auf die gleiche Weise wie im vorherigen Runden des Algorithmus ;

□ Ein 20-Runden-GOST®-Algorithmus, der XOR anstelle von Modulo 2 32 für die Tastenüberlagerung verwendet.

Basierend auf den Ergebnissen der Analyse wurde der Schluss gezogen, dass GOST-H und GOST© schwächer als der ursprüngliche Algorithmus GOST 28147-89 sind, da beide Klassen schwacher Schlüssel haben. Es ist erwähnenswert, dass die Arbeit in Bezug auf die GOST©-Kryptanalyse Wort für Wort den Abschnitt über die Kryptoanalyse des Algorithmus GOST 28147-89 wiederholt, der im Jahr 2000 in einem bekannten Werk veröffentlicht wurde (ohne Bezugnahme auf das Original). Dies stellt die Professionalität der Autoren der Arbeit und ihrer anderen Ergebnisse in Frage.

Eine sehr interessante Modifikation des Algorithmus wird in der Arbeit vorgeschlagen: Die Tabellen S \ ... Ss müssen notwendigerweise unterschiedlich sein; in jeder Runde des Algorithmus müssen sie nach einem bestimmten Gesetz permutiert werden. Diese Permutation kann vom Verschlüsselungsschlüssel abhängen oder geheim sein (d. h. Teil eines größeren Verschlüsselungsschlüssels als der ursprüngliche 256-Bit-Schlüssel sein). Beide Optionen erhöhen laut ihren Autoren die Resistenz des Algorithmus gegenüber linearer und differentieller Kryptoanalyse erheblich.

Und eine weitere Modifikation in Bezug auf Substitutionstabellen ist in der Arbeit angegeben, in der eines der möglichen Verfahren zum Berechnen von Substitutionstabellen basierend auf dem Verschlüsselungsschlüssel analysiert wird. Die Autoren der Arbeit kamen zu dem Schluss, dass eine solche Abhängigkeit den Algorithmus schwächt, da sie zum Vorhandensein schwacher Schlüssel und zu einigen potenziellen Schwachstellen des Algorithmus führt.

Vollständige Algorithmusanalyse

Es gibt auch Angriffe auf die Vollrunde GOST 28147-89 ohne Änderungen. Eine der ersten offenen Arbeiten, in denen die Analyse des Algorithmus durchgeführt wurde, eine bekannte Arbeit, widmet sich Angriffen, die Schwachstellen im Schlüsselerweiterungsverfahren einiger bekannter Verschlüsselungsalgorithmen ausnutzen. Insbesondere der Full-Round-Algorithmus GOST 28147-89 kann durch differenzielle Kryptoanalyse auf verknüpften Schlüsseln gebrochen werden, aber nur, wenn schwache Substitutionstabellen verwendet werden. Die 24-Runden-Version des Algorithmus (der die ersten 8 Runden fehlen) wird auf die gleiche Weise für alle Substitutionstabellen geöffnet, aber starke Substitutionstabellen (z. B. in angegeben) machen einen solchen Angriff absolut unpraktisch.

Die einheimischen Wissenschaftler A. G. Rostovtsev und E. B. Makhovenko haben 2001 eine grundlegend neue Methode der Kryptoanalyse vorgeschlagen (laut den Autoren ist sie wesentlich effektiver als die lineare und differenzielle Kryptoanalyse), indem sie aus einem bekannten Klartext, der ihr entspricht, eine objektive Funktion bilden Chiffretext und der gewünschte Wert des Schlüssels und Finden seines Extremums, das dem wahren Wert des Schlüssels entspricht. Sie fanden auch eine große Klasse schwacher Schlüssel des GOST 28147-89-Algorithmus, die es Ihnen ermöglichen, den Algorithmus mit nur 4 ausgewählten Klartexten und ihren entsprechenden Chiffretexten mit relativ geringer Komplexität zu öffnen. Die Kryptoanalyse des Algorithmus wird in der Arbeit fortgesetzt.

Im Jahr 2004 schlug eine Expertengruppe aus Korea einen Angriff vor, bei dem es möglich ist, mit einer Wahrscheinlichkeit von 91,7 % 12 Bit eines geheimen Schlüssels durch differenzielle Kryptoanalyse auf zugehörige Schlüssel zu erhalten. Der Angriff erfordert 235 ausgewählte Klartexte und 236 Verschlüsselungsoperationen. Wie gesehen, dieser Angriff, ist für die eigentliche Öffnung des Algorithmus praktisch nutzlos.