Schieberegister mit Rückmeldung. Lineares Schieberegister mit Rückkopplungsverlauf von Schieberegistern

Feedback-Schieberegister ( FSR ) besteht aus zwei Teilen: Schieberegister Und Feedback-Funktionen .

Ein Schieberegister (Fehler: Referenzquelle nicht gefunden) ist eine Folge von Bits. Wenn ein Bit abgerufen werden muss, werden alle Bits des Schieberegisters um 1 Position nach rechts verschoben. Das neue Bit ganz links ist der Wert der Rückkopplungsfunktion aus den verbleibenden Bits des Registers. Zeitraum Das Schieberegister gibt die Länge der resultierenden Sequenz an, bevor sie sich zu wiederholen beginnt.

Die einfachste Art von Feedback-Schieberegister ist lineares Schieberegister mit Rückmeldung (LFSR – Links Rückmeldung Schicht Registrieren) (Fehler! Verweisquelle konnte nicht gefunden werden). Die Rückmeldung ist einfach eine XOR-Verknüpfung einiger p Bits Register wird die Liste dieser Bits aufgerufen Tippsequenz.

N-bit LFSR kann in einem von sein 2 N -1 interne Zustände. Das bedeutet, dass ein solches Register theoretisch eine Pseudozufallsfolge mit einem Punkt erzeugen kann 2 N -1 Bits Die Anzahl der internen Zustände und die Periode sind gleich, da das Füllen des Registers mit Nullen dazu führt, dass es eine endlose Folge von Nullen erzeugt, was absolut nutzlos ist. Nur bei bestimmten Klopfsequenzen durchläuft das LFSR alle 2 N -1 interne Zustände. Diese LFSRs werden aufgerufen LFSRmit maximaler Laufzeit.

Damit ein bestimmtes LFSR eine maximale Periode hat, wird ein Polynom aus der Abgriffsequenz und der Konstante gebildet 1 muss primitiv modulo sein 2 .

Die Berechnung der Primitivität eines Polynoms ist ein ziemlich komplexes mathematisches Problem. Daher gibt es vorgefertigte Tabellen, die die Anzahl der Abgriffsequenzen anzeigen, die für die maximale Periodendauer des Generators sorgen. Für ein 32-Bit-Schieberegister finden Sie beispielsweise den folgenden Eintrag: (32,7,5,3,2,1,0) . Das bedeutet, dass Sie zum Generieren eines neuen Bits das zweiunddreißigste, siebte, fünfte, dritte, zweite und erste Bit mithilfe der XOR-Funktion summieren müssen.

Der Code für ein solches LFSR in C++ würde wie folgt aussehen:

// Jeder Wert außer Null

ShiftRegister = ((((ShiftRegister >> 31)

^ (Schichtregister >> 6)

^ (Schichtregister >> 4)

^ (ShiftRegister >> 2)

^ (ShiftRegister >> 1)

^ Schichtregister)

& 0x00000001)<<31)

| (ShiftRegister >> 1);

return ShiftRegister & 0x00000001;

Softwareimplementierungen von LFSR sind recht langsam und arbeiten schneller, wenn sie in Assembler statt in C geschrieben sind. Eine Lösung besteht darin, 16 LFSRs parallel zu verwenden (oder 32, abhängig von der Wortlänge in der spezifischen Computerarchitektur). Dieses Schema verwendet ein Array von Wörtern, deren Größe der Länge des LFSR entspricht, und jede Worteinheit im Array verweist auf ihr eigenes LFSR. Vorausgesetzt, dass die gleichen Tap-Sequenznummern verwendet werden, kann dies zu einem spürbaren Leistungsgewinn führen.

MIT Auch die Rückkopplungsschaltung kann modifiziert werden. In diesem Fall verfügt der Generator nicht über eine größere kryptografische Stärke, lässt sich aber einfacher in Software implementieren. Anstatt das Bit ganz links der Abgriffsequenz zu verwenden, um das neue Bit ganz links zu generieren, verknüpft es jedes Bit der Abgriffsequenz mit der Ausgabe des Generators XOR und ersetzt es durch das Ergebnis dieser Aktion, dann wird das Ergebnis des Generators zum neuen Bit ganz links (Fehler: Referenzquelle nicht gefunden).

Diese Modifikation wird aufgerufen Galois-Konfiguration. In C sieht es so aus:

static unsigned long ShiftRegister = 1;

void seeds_LFSR (vorzeichenloser langer Seed)

ShiftRegister = Startwert;

int Galua_LFSR (void)

if (ShiftRegister & 0x00000001) (

ShiftRegister = (ShiftRegister ^ mask >> 1) | 0x8000000;

ShiftRegister >>= 1;

Der Vorteil besteht darin, dass alle XORs in einem Vorgang ausgeführt werden. Diese Schaltung kann auch parallelisiert werden.

LFSRs selbst sind gute Pseudozufallssequenzgeneratoren, weisen jedoch einige unerwünschte nichtzufällige Eigenschaften auf. Aufeinanderfolgende Bits sind linear und daher für die Verschlüsselung unbrauchbar. Für LFSR-Längen N Der interne Zustand repräsentiert den vorherigen N Generatorausgangsbits. Auch wenn das Feedbackmuster geheim gehalten wird, kann es dadurch bestimmt werden 2 N Ausgangsbits des Generators mithilfe spezieller Algorithmen. Darüber hinaus sind große Zufallszahlen, die mithilfe aufeinanderfolgender Bits dieser Sequenz generiert werden, stark korreliert und für einige Arten von Anwendungen nicht zufällig. Dennoch werden LFSRs häufig zur Erstellung von Verschlüsselungsalgorithmen verwendet. Zu diesem Zweck werden mehrere LFSRs verwendet, meist mit unterschiedlichen Längen und Tap-Sequenznummern. Der Schlüssel ist der Ausgangszustand der Register. Jedes Mal, wenn ein neues Bit benötigt wird, werden alle Register verschoben. Diese Operation wird aufgerufen stempeln. Das Ausgabebit ist eine vorzugsweise nichtlineare Funktion einiger LFSR-Bits. Diese Funktion wird aufgerufen kombinieren, und der Generator als Ganzes – Kombinationsgenerator. Viele dieser Generatoren sind immer noch sicher.

Ministerium für Bildung und Wissenschaft

RUSSISCHE STAATLICHE SOZIALUNIVERSITÄT

FAKULTÄT FÜR INFORMATIONSTECHNOLOGIE

ABTEILUNG FÜR INFORMATIONSSCHUTZ

Kryptografische Methoden und Mittel zur Gewährleistung der Informationssicherheit

Kursarbeit

"R Schieberegister mit linearer Rückkopplung als Pseudozufallszahlengeneratoren“

Vollendet:

Student im dritten Jahr

Gruppe KZOI-D-3

Larionov I.P.

Geprüft:

Assoc. Baranova E.K.

Moskau 2011
INHALT

Einführung ……………………………..…………………………………….3

1. Theoretische Grundlagen der Arbeit…………………………………………4
   1. Allgemeine Informationen zu Feedback-Schieberegistern............4
      1. Über Stream-Chiffren basierend auf RgSsLOS………………….………10
      2. Zur linearen Komplexität der generierten Pseudozufallsfolge RgCsLOC………………………………….……12
      3. Zur Korrelationsunabhängigkeit der generierten Folge von Pseudozufallszahlen PrCsLOC………..….13
      4. Über andere Methoden zum Öffnen der generierten Folge von Pseudozufallszahlen PrCsLOC……………………………………………………..14
2. Softwareimplementierung von PrCsLOS als Pseudozufallssequenzgenerator….…………………………….15
   1. Verallgemeinertes Diagramm des Algorithmus…………………………………...15
   2. Beschreibung der Softwaremodule und Schnittstelle.……………….16
   3. Benutzerhinweise………………………………………...20

Abschluss ………………………………………………………………22

Referenzliste………………………………………………….....23

Anhang A ….………………………………………………………..24

EINFÜHRUNG

Der Zweck dieser Arbeit besteht darin, eine Softwareanwendung zu entwickeln, die den Betrieb eines Pseudozufallszahlengenerators unter Verwendung von Schieberegistern mit Rückkopplung implementiert. Die Entwicklung dieser Anwendung mit grafischer Oberfläche erfolgt in der Sprache C++ für Windows-Betriebssysteme.

Mit der Entwicklung der Kryptographie im 20. Jahrhundert standen Kryptographen vor der Aufgabe, Verschlüsselungsgeräte und -maschinen zu entwickeln, die Nachrichten schnell und zuverlässig ver- und entschlüsseln konnten. Diese Anforderung wurde von den damals bereits offenen symmetrischen Verschlüsselungssystemen erfüllt, deren Schwachpunkt jedoch die starke Abhängigkeit vom Schlüssel und dessen Geheimhaltung war. Die bequemste Klasse von Chiffren, die für diesen Zweck verwendet werden könnten, sind Gamma-Chiffren. Es entstand das Problem, dass beim Entschlüsseln einer Nachricht ein Gamma erzeugt wurde, das nicht erkannt werden konnte. Theoretisch wäre dies möglich, wenn das Gamma jedes Mal zufällig wäre und sich im Laufe der Zeit änderte. Bei Verwendung eines sich völlig zufällig ändernden Gammas wäre es jedoch schwierig, eine zuverlässige Ver- und Entschlüsselung der Nachricht sicherzustellen. Kryptographen machten sich an die Lösung dieses Problems, deren Ziel darin bestand, einen Algorithmus zu finden, der die Erzeugung eines zufälligen Gammas nach einer bestimmten Regel umsetzt; eine solche Folge sollte Nullen und Einsen an „vermeintlich“ zufälligen Positionen sowie die Anzahl der Einsen enthalten und Nullen sollten ungefähr gleich sein. Diese Zufallsfolge wurde aufgerufenpseudozufällig,da es nach einer bestimmten Regel generiert wurde und nicht zufällig.

Es wurde schnell eine Lösung gefunden. Durch die Untersuchung der Eigenschaften von Schieberegistern konnte festgestellt werden, dass rückgekoppelte Schieberegister aufgrund ihrer internen Struktur in der Lage sind, pseudozufällige Sequenzen zu erzeugen, die ausreichend resistent gegen Entschlüsselung sind.

1.Theoretische Arbeitsgrundlage

1.1.Allgemeine Informationen zu Schieberegistern mit linearer Rückmeldung

Schieberegistersequenzen werden sowohl in der Kryptographie als auch in der Codierungstheorie verwendet. Ihre Theorie ist gut entwickelt; schieberegisterbasierte Stromchiffren waren lange vor dem Aufkommen der Elektronik das Arbeitstier der militärischen Kryptographie.

Ein Schieberegister mit geschlossenem Regelkreis (im Folgenden als RGSSOC bezeichnet) besteht aus zwei Teilen: einem Schieberegister und einer Rückkopplungsfunktion.Ein Schieberegister ist eine Folge von Bits. Die Anzahl der Bits wird bestimmtSchieberegisterlängeWenn die Länge n Bit beträgt, wird das Register aufgerufenn-Bit-Schieberegister. Immer wenn ein Bit abgerufen werden muss, werden alle Bits des Schieberegisters um eine Position nach rechts verschoben. Das neue Bit ganz links ist eine Funktion aller anderen Bits im Register. Der Ausgang des Schieberegisters ist ein, normalerweise niedrigstwertiges Bit.Schieberegisterzeitraumist die Länge der resultierenden Sequenz, bevor ihre Wiederholung beginnt.

Figurenschieberegister mit Rückmeldung

Schieberegister fanden schnell Verwendung in Stromchiffren, da sie mit digitaler Hardware leicht implementiert werden konnten. Im Jahr 1965 entwickelte Ernst Selmer, Chefkryptograph der norwegischen Regierung, die Theorie der Schieberegisterfolge. Solomon Golomb, ein NSA-Mathematiker, schrieb ein Buch, in dem er einige seiner und Selmers Ergebnisse vorstellte. Die einfachste Art von Feedback-Schieberegister istSchieberegister mit linearer Rückkopplung ( lineares Rückkopplungs-Schieberegister, im Folgenden LFSR oder РгСсЛОС) . Die Rückmeldung solcher Register ist einfach ein XOR (Modulo-Zwei-Addition) einiger Registerbits, eine Liste dieser Bits, die als Abgriffsequenz bezeichnet wird. Manchmal wird ein solches Register als Fibbonacci-Konfiguration bezeichnet. Aufgrund der Einfachheit der Rückkopplungssequenz kann eine ziemlich fortgeschrittene mathematische Theorie zur Analyse von PrCsVOC verwendet werden. Durch die Analyse der resultierenden Ausgabesequenzen können Sie überprüfen, ob die Sequenzen zufällig genug sind, um sicher zu sein. RGCCLOS wird in der Kryptographie häufiger als andere Schieberegister verwendet.

Abbildung PrCsLOS Fibbonacci

Im Allgemeinen, n -bit PrCsLOS kann in einem von sein N=2n -1 interne Zustände. Das bedeutet, dass ein solches Register theoretisch eine Pseudozufallsfolge mit einer Periode von T=2 erzeugen kann N -1 Bit. (Die Anzahl der internen Zustände und die Periode sind gleich N = T max =2 n -1, weil das Füllen von PrCcLOS mit Nullen dazu führt, dass das Schieberegister eine endlose Folge von Nullen erzeugt, was absolut nutzlos ist. Nur für bestimmte Verzweigungssequenzen durchläuft PrCsLOS zyklisch alle 2 N -1 interne Zustände, wie z. B. PrCsLOSRgSsLOS mit maximaler Periode. Das resultierende Ergebnis wird aufgerufenM-Sequenz.

Beispiel . Die folgende Abbildung zeigt einen 4-Bit-PrCCLOS mit abgegriffenem ersten und vierten Bit. Wenn es mit dem Wert 1111 initialisiert wird, nimmt das Register vor der Wiederholung die folgenden internen Zustände an:

Schichtuhrnummer (interner Zustand)	Registrierungsstatus				Ausgangsbit
Ursprünglicher Wert
15 (Rückkehr zum Ausgangszustand)
16 (Wiederholungszustände)

Die Ausgabesequenz ist eine Folge niedrigstwertiger Bits: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 mit der Periode T=15, der Gesamtzahl der möglichen internen Zustände (außer Null), N =2 4 -1=16-1=15= T max , also die Ausgabesequenz M -Folge.

Damit ein bestimmtes PrCsLOS eine maximale Periode hat, muss das aus der Abgriffsequenz und der Konstante 1 gebildete Polynom primitiv modulo 2 sein. Das Polynom wird als Summe von Potenzen dargestellt, beispielsweise als Polynom vom Grad N sieht so aus:

a n x n +a n-1 x n-1 +…+a 1 x 1 +a 0 x 0 =a n x n +a n-1 x n-1 +…+a 1 x+a 0 , wobei a i =(0, 1 ) für i=1…n gibt a x i die Ziffer an.

Der Grad des Polynoms ist die Länge des Schieberegisters. Ein primitives Polynom vom Grad n ist ein irreduzibles Polynom, das ein Teiler von x ist 2n−1 +1, ist aber kein Teiler von x D +1 für alle d, die Teiler von 2 sind N -1. Die entsprechende mathematische Theorie findet sich in.

Im Allgemeinen gibt es keine einfache Möglichkeit, primitive Polynome eines bestimmten Grades Modulo 2 zu erzeugen. Die einfachste Möglichkeit besteht darin, ein Polynom zufällig auszuwählen und zu prüfen, ob es primitiv ist. Das ist nicht einfach und ähnelt ein bisschen der Prüfung, ob eine zufällig ausgewählte Zahl eine Primzahl ist – aber viele Mathe-Softwarepakete können dieses Problem lösen.

Einige, aber sicherlich nicht alle Polynome unterschiedlichen Grades, die primitiv modulo 2 sind, sind unten aufgeführt. Zum Beispiel aufzeichnen

(32, 7, 5, 3, 2, 1, 0) bedeutet, dass das folgende Polynom primitiv Modulo 2 ist: x 32 + x 7 + x 5 + x 3 + x 2 + x + 1.

Dies lässt sich leicht auf PrCsVOC mit einer maximalen Periode verallgemeinern. Die erste Zahl ist die Länge von PrCsLOS. Die letzte Zahl ist immer 0 und kann weggelassen werden. Alle Zahlen außer 0 geben eine Abgriffsequenz an, gezählt vom linken Rand des Schieberegisters. Das heißt, Terme eines Polynoms mit niedrigeren Graden entsprechen Positionen, die näher am rechten Rand des Registers liegen.

Um mit dem Beispiel fortzufahren: Das Schreiben von (32, 7, 5, 3, 2, 1, 0) bedeutet, dass für ein gegebenes 32-Bit-Schieberegister ein neues Bit durch XOR-Verknüpfung des zweiunddreißigsten, siebten, fünften, dritten, Zweites und erstes Bit, das resultierende PrCsLOS hat eine maximale Länge und durchläuft 2 32 -1 Werte.

Abbildung 4 32-Bit-PrCsLOC mit maximaler Länge

Betrachten wir den Programmcode PrCsLOS, in dem die Tap-Sequenz durch ein Polynom (32, 7, 5, 3, 2, 1, 0) gekennzeichnet ist. In C sieht es so aus:

int LFSR() (

static unsigned long ShiftRegister = 1;

/* Alles außer 0. */

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister >> 6)

^(Schichtregister >> 4)

^(ShiftRegister >> 2)

^(Schichtregister >> 1)

^ShiftRegister))

& 0x00000001)

<<31)

| (ShiftRegister >> 1) ;

return ShiftRegister & 0 x 00000001;)

Wenn das Schieberegister länger als ein Computerwort ist, wird der Code komplizierter, aber nicht viel. Im Anhang B Es wird eine Tabelle einiger primitiver Polynome Modulo 2 angegeben; wir werden sie in Zukunft verwenden, um einige Eigenschaften dieser Polynome zu identifizieren, sowie in der Softwareimplementierung, um die Abgriffsequenz anzugeben.

Bitte beachten Sie, dass alle Elemente der Tabelle eine ungerade Anzahl von Koeffizienten haben. Diese lange Tabelle wird für die weitere Arbeit mit RgCsLOC bereitgestellt, da RgCsLOC häufig für die Kryptographie mit Stream-Chiffren und in Pseudozufallszahlengeneratoren verwendet wird. In unserem Fall können wir Polynome mit einem höchsten Grad von nicht mehr als sieben verwenden.

Wenn p(x) primitiv ist, dann ist x auch primitiv N p(1/x), sodass jedes Element der Tabelle tatsächlich zwei primitive Polynome definiert. Wenn beispielsweise (a, b, 0) primitiv ist, dann ist auch (a, a-b, 0) primitiv. Wenn (a, b, c, d, 0) primitiv ist, dann ist auch (a, a-d, a-c, a-b, 0) primitiv. Mathematisch:

wenn x primitiv ist a +x b +1, dann ist x auch primitiv a +x a-b +1,

wenn x primitiv ist a +x b +x c +x d +1, dann ist x auch primitiv a +x a-d +x a-c +x a-b +1. Primitive Trinome lassen sich am schnellsten in Software implementieren, da Sie zum Erzeugen eines neuen Bits nur zwei Bits des Schieberegisters XOR-verknüpfen müssen (der Nullterm wird nicht berücksichtigt, d. h. x 0 =1, siehe Beispiel oben). Tatsächlich sind alle in der Tabelle aufgeführten Rückkopplungspolynome dünnbesetzt, das heißt, sie haben wenige Koeffizienten. Sparsity ist immer eine Quelle von Schwäche, die manchmal ausreicht, um den Algorithmus zu zerstören. Für kryptografische Algorithmen ist es viel besser, dichte primitive Polynome mit vielen Koeffizienten zu verwenden. Durch die Verwendung dichter Polynome, insbesondere als Teil eines Schlüssels, können viel kürzere PrCsLOS verwendet werden.

Die Generierung dichter primitiver Polynome Modulo 2 ist nicht einfach. Um primitive Polynome vom Grad k zu erzeugen, müssen Sie im Allgemeinen die Faktorisierung der Zahl 2 kennen k -1.

PrCsLOS sind an sich gute Generatoren für pseudozufällige Sequenzen, weisen jedoch einige unerwünschte nichtzufällige (deterministische) Eigenschaften auf. Aufeinanderfolgende Bits sind linear und daher für die Verschlüsselung unbrauchbar. Bei einem PrCcLOS der Länge n entspricht der interne Zustand den vorherigen n Ausgangsbits des Generators. Selbst wenn die Rückkopplungsschaltung geheim gehalten wird, kann sie mithilfe des hocheffizienten Berlekamp-Massey-Algorithmus aus den 2n Ausgangsbits des Oszillators ermittelt werden.

Darüber hinaus sind große Zufallszahlen, die mithilfe aufeinanderfolgender Bits dieser Sequenz generiert werden, stark korreliert und bei einigen Anwendungstypen überhaupt nicht zufällig. Dennoch wird RgCCLOS häufig zur Erstellung von Verschlüsselungsalgorithmen als Komponenten von Systemen und Verschlüsselungsalgorithmen verwendet.

1.2.Über Stream-Chiffren basierend auf RgSSLOS

Der grundlegende Ansatz zum Entwerfen eines Schlüsselstromgenerators auf Basis von RgSSLOS ist einfach. Zunächst werden ein oder mehrere PrCsLOS genommen, normalerweise mit unterschiedlichen Längen und unterschiedlichen Rückkopplungspolynomen. (Wenn die Längen teilerfremd sind und alle Rückkopplungspolynome primitiv sind, hat der generierte Generator eine maximale Länge.) Der Schlüssel ist der Anfangszustand der PrCcLOS-Register. Jedes Mal, wenn ein neues Bit benötigt wird, verschieben Sie die PrCCLOC-Register um ein Bit (dies wird manchmal als Takten bezeichnet). Das Ausgangsbit ist eine vorzugsweise nichtlineare Funktion einiger Bits der PrCsLOS-Register. Diese Funktion wird als Kombinationsfunktion bezeichnet, und der Generator als Ganzes wird als Kombinationsgenerator bezeichnet. (Wenn das Ausgangsbit eine Funktion eines einzelnen PrCCLOS ist, wird der Oszillator als Filteroszillator bezeichnet.) Ein Großteil der Theorie für diesen Gerätetyp wurde von Selmer und Neal Zierler entwickelt. Es kann zu einer Reihe von Komplikationen kommen. Einige Oszillatoren verwenden unterschiedliche Taktfrequenzen für unterschiedliche RgSsLOS, manchmal hängt die Frequenz eines Oszillators vom Ausgang eines anderen ab. Dies sind alles elektronische Versionen von Chiffriermaschinenideen aus der Zeit vor dem Zweiten Weltkrieg, sogenannte taktgesteuerte Oszillatoren ( taktgesteuerte Generatoren ). Die Taktsteuerung kann Feed-Forward sein, bei dem der Ausgang eines PrCcLOC die Taktfrequenz eines anderen PrCcLOC steuert, oder Feedback, bei dem der Ausgang eines PrCcLOC seine eigene Taktfrequenz steuert. Obwohl alle diese Generatoren zumindest theoretisch anfällig für Angriffe durch Verschachtelung und mögliche Korrelation sind, sind viele von ihnen dennoch sicher.

Ian Cassells, ehemaliger Leiter der reinen Mathematik in Cambridge und Kryptoanalytiker in Bletchly Park, sagte: „Kryptographie ist eine Mischung aus Mathematik und Verwirrung, und ohne Verwirrung kann Mathematik gegen Sie verwendet werden.“ Er meinte damit, dass bei Stromchiffren bestimmte mathematische Strukturen wie PrCcLOS erforderlich sind, um maximale Länge und andere Eigenschaften bereitzustellen, aber ein komplexes nichtlineares Chaos eingeführt werden muss, um zu verhindern, dass jemand an den Inhalt des Registers gelangt und den Algorithmus bricht. Dieser Hinweis gilt auch für Blockalgorithmen.

Die meisten echten Stromchiffren basieren auf PrCsLOS. Schon in den Anfängen der Elektronik waren sie nicht schwer zu bauen. Das Schieberegister ist nichts weiter als ein Array von Bits und die Rückkopplungssequenz ist eine Reihe von XOR-Gattern. Auch bei der Verwendung von VLSI bietet die PrCsLOC-basierte Stream-Verschlüsselung mithilfe mehrerer Logikgatter erhebliche Sicherheit. Das Problem mit PrSSLOS besteht darin, dass ihre Softwareimplementierung sehr ineffizient ist. Sie müssen Polynome mit geringer Rückkopplung vermeiden – sie erleichtern Korrelationsangriffe – und Polynome mit dichter Rückkopplung sind unwirksam.

Dieser Zweig der Kryptographie entwickelt sich rasant und steht unter der wachsamen Kontrolle der Regierung N.S.A. . Die meisten Entwicklungen sind geheim – viele heute verwendete militärische Verschlüsselungssysteme basieren auf RgSSLOS. Tatsächlich verfügen die meisten Cray-Computer (Cray 1, Cray X-MP, Cray Y-MP) über eine sehr interessante Anweisung, die üblicherweise als „Bevölkerungszählung“ bezeichnet wird. Es zählt die Anzahl der Einsen in einem Register und kann sowohl zur effizienten Berechnung der Hamming-Distanz zwischen zwei Binärwörtern als auch zur Implementierung einer vektorisierten Version von PrCcLOS verwendet werden. Diese Anweisung gilt als kanonische Anweisung der NSA und muss in fast allen Computerverträgen enthalten sein.

Andererseits wurden überraschend viele scheinbar komplexe Schieberegistergeneratoren gehackt. Und natürlich ist die Zahl solcher Generatoren, die von militärischen Kryptoanalyseagenturen wie der NSA gehackt wurden, noch größer.

1.3. Zur linearen Komplexität der generierten Folge von Pseudozufallszahlen PrCsLOC

Stromchiffren sind oft einfacher zu analysieren als Blockchiffren. Ein wichtiger Parameter zur Analyse von Generatoren auf Basis von PrCsLOS ist beispielsweise die lineare Komplexität oder das lineare Intervall. Sie ist definiert als die Länge n des kürzesten PrCsLOS, der den Ausgang des Generators simulieren kann. Jede von einem endlichen Automaten über einem endlichen Feld erzeugte Folge hat eine endliche lineare Komplexität. Lineare Komplexität ist wichtig, da es mit einem einfachen Algorithmus namens Berlekamp-Massey-Algorithmus möglich ist, diesen PrCcLOS zu bestimmen, indem nur 2n Bits des Schlüsselstroms überprüft werden. Durch die Wiederherstellung des gewünschten PrCsLOS knacken Sie die Stream-Verschlüsselung.

Diese Idee kann von Feldern auf Ringe und auf Fälle ausgeweitet werden, in denen die Ausgabesequenz als Zahlen in einem Feld mit ungeraden Eigenschaften behandelt wird. Eine weitere Erweiterung führt zur Einführung des Konzepts eines linearen Komplexitätsprofils, das die lineare Komplexität einer Sequenz bei ihrer Länge bestimmt. Es gibt auch Konzepte sphärischer und quadratischer Komplexität. Bedenken Sie auf jeden Fall, dass eine hohe lineare Komplexität nicht unbedingt die Sicherheit des Generators garantiert, eine niedrige lineare Komplexität jedoch darauf hindeutet, dass der Generator nicht sicher genug ist.

1.4. Zur Korrelationsunabhängigkeit der generierten Folge von Pseudozufallszahlen PrCsLOS

Kryptographen versuchen, eine hohe lineare Komplexität zu erreichen, indem sie die Ergebnisse einiger Ausgabesequenzen nichtlinear kombinieren. Die Gefahr besteht hier darin, dass eine oder mehrere interne Ausgabesequenzen – oft nur die Ausgaben einzelner PrCsLOS – durch einen gemeinsamen Schlüsselstrom verbunden und mithilfe der linearen Algebra geöffnet werden können. Diese Autopsie wird oft als Korrelationsautopsie oder Divide-and-Conquer-Autopsie bezeichnet. Thomas Siegenthaler zeigte, dass es möglich ist, Korrelationsunabhängigkeit präzise zu definieren, und dass es einen Kompromiss zwischen Korrelationsunabhängigkeit und linearer Komplexität gibt.

Die Hauptidee eines Korrelationsangriffs besteht darin, eine gewisse Korrelation zwischen der Ausgabe des Generators und der Ausgabe einer seiner Komponenten zu erkennen. Durch Beobachtung der Ausgabereihenfolge kann man dann Informationen über diese Zwischenausgabe erhalten. Mithilfe dieser Informationen und anderer Korrelationen können Daten zu anderen Zwischenausgängen gesammelt werden, bis der Generator kompromittiert wird.

Korrelationsangriffe und ihre Variationen, wie z. B. schnelle Korrelationsangriffe, bieten einen Kompromiss zwischen Rechenkomplexität und Effizienz und wurden erfolgreich gegen viele PrCsLOS-basierte Keystream-Generatoren eingesetzt.

1.5.Über andere Methoden zum Öffnen der generierten Folge von Pseudozufallszahlen PrCsLOS

Es gibt andere Möglichkeiten, Keystream-Generatoren zu zerstören. Bei einem linearen Konsistenztest wird versucht, mithilfe einer Matrixtechnik eine Teilmenge des Verschlüsselungsschlüssels zu finden. Es gibt auch einen „Meet-in-the-Middle-Konsistenzangriff“. Der Algorithmus des linearen Syndroms basiert auf der Fähigkeit, ein Fragment der Ausgabesequenz in Form einer linearen Gleichung zu schreiben. Es gibt einen Angriff mit der besten affinen Approximation und einen Angriff mit abgeleiteter Sequenz. Methoden der differenziellen und linearen Kryptoanalyse können auch auf Stromchiffren angewendet werden.

2. Beschreibung der Softwareimplementierung von PrCsLOS als Pseudozufallssequenzgenerator

2.1.Verallgemeinertes Diagramm des Algorithmus

2.2.Beschreibung der Softwaremodule und Schnittstelle

Unten zeigt Abbildung 3 das Programmfenster.

Abbildung Programmschnittstelle

Das Menü hat folgende Funktionen:

• Datei->Bericht speichern

Diese Funktion erstellt eine Berichtsdatei, die den Anfangszustand von PrCsLOS, die Abgriffsequenz, die Periode der empfangenen pseudozufälligen Bitsequenz, die Sequenz selbst und die Zustandstabelle aufzeichnet. Wenn die Datei erfolgreich gespeichert wurde, wird eine Meldung angezeigt, dass das Speichern erfolgreich war (Abbildung 4). Die empfohlene Berichtsdateierweiterung ist *. txt.

Zeichnung

• Datei->Beenden

Diese Funktion stellt sicher, dass die Anwendung geschlossen wird.

• Tippfolge einstellen

Diese Funktion generiert eine Tippsequenz, indem sie die Werte aus den Kästchen liest, die der Benutzer auf dem Bildschirmformular angekreuzt hat. Anschließend wird der Benutzer über die Erstellung einer Tippsequenz benachrichtigt (Abbildung 5). Die Abgriffsequenz bestimmt, welche Schieberegister-Flip-Flops Rückmeldung geben. XOR um ein Offset-Bit zu erzeugen. Standardmäßig ist immer die Rückmeldung des ersten Triggers eingestellt; wenn keine anderen Verbindungen vorhanden sind, wird eine Verschiebung nach links durchgeführt, wobei das niederwertige Bit in die höherwertige Position wandert.

Zeichnung

• Anfangswert festlegen

Diese Funktion liest den vom Benutzer bereitgestellten Anfangsregisterwert aus dem Fenster Bearbeiten 1 und prüft den eingegebenen Wert gemäß den angegebenen Bedingungen: Der eingegebene String ist nicht leer (Abbildung 6), der eingegebene String hat eine Länge von acht (8bit=1 Byte, Abbildung 7), der eingegebene String enthält nur Nullen und/oder Einsen (Abbildung 8), die eingegebene Zeichenfolge ist ungleich Null (Abbildung 9). Andernfalls werden Fehlermeldungen angezeigt, der Benutzer muss diese korrigieren und die Taste erneut drücken. Bei erfolgreicher Prüfung wird der Initialwert in die Statustabelle in der Zeile „Initial“ geschrieben und eine Benachrichtigung ausgegeben (Abbildung 10).

Zeichnung

Zeichnung

Zeichnung

Zeichnung

Zeichnung

• Schaltetui

Diese Funktion emuliert den Betrieb eines Schieberegisters. Durch die sequentielle Durchführung von 256 Verschiebungen erzeugt jede Verschiebung ein Pseudozufallssequenz-Ausgangsbit und einen neuen Registerzustand. Sobald der Registerstand dem Ausgangszustand entspricht, wird die Periode berechnet und im Feld angezeigt Memo 1 resultierende Pseudozufallsfolge.

• Hilfe->Über das Programm

Diese Funktion zeigt eine kurze Beschreibung des Programms und der Anweisungen an (Abbildung 11).

Zeichnung

• Hilfe->Über den Autor

Diese Funktion zeigt Informationen über den Autor des Programms an (Abbildung 12).

Zeichnung

2.3.Benutzerhinweise

1. Setzen Sie zunächst das Register auf seinen Ausgangszustand. Es muss acht Binärzeichen enthalten. Andernfalls wird eine Fehlermeldung angezeigt und Sie müssen den eingegebenen Wert korrigieren. Klicken Sie auf den Menüpunkt „Anfangswert festlegen“.
2. Anschließend aktivieren Sie die Kontrollkästchen für die Registerrückmeldungen (Tap Sequence). Klicken Sie auf den Menüpunkt „Tap-Reihenfolge festlegen“.
3. Klicken Sie anschließend auf den Menüpunkt „Case Shift“. Bevor Sie dies tun, stellen Sie sicher, dass Sie die Schritte 1 und 2 abgeschlossen haben, da sonst ein Softwarefehler auftritt.
4. Nachdem Sie die Ergebnisse erhalten haben, können Sie diese speichern, indem Sie auf den Menüpunkt „Datei->Bericht speichern“ klicken. Bevor Sie dies tun, stellen Sie sicher, dass Sie die Schritte 1-3 abgeschlossen haben, da sonst ein Softwarefehler auftritt.
5. Um Hilfe zu erhalten, klicken Sie auf die Menüpunkte „Datei->Über das Programm“, „Datei->Über den Autor“.
6. Um die Funktionsweise des Registers mit anderen Werten der Abgriffsequenz und dem Anfangszustand des Registers zu sehen, wiederholen Sie die Schritte in den Schritten 1 bis 3 und geben Sie andere Parameter ein.

ABSCHLUSS

In dieser Arbeit wurden PrCsLOS als Pseudozufallszahlengeneratoren betrachtet. Das Programm kann als visuelle Demonstration der Funktionsprinzipien von Schieberegistern mit linearer Rückmeldung dienen XOR . Darin können Sie das Prinzip der Bildung einer pseudozufälligen Bitfolge, die Beziehung zwischen dem Anfangswert des Registers und dem Wert der pseudozufälligen Folge, die Abgrifffolge und die Periode studieren. Das resultierende pseudozufällige Gamma kann in einer anderen Softwareanwendung verwendet werden (z. B. einer Softwareimplementierung einer Gamma-Verschlüsselung).

Derzeit werden diese Register nicht als unabhängige Generatoren von Pseudozufallszahlen verwendet, sondern sind Teil komplexerer Geräte. Sie waren es jedoch, die der Mathematik neue Wege eröffneten (Suche nach primitiven Polynomen in endlichen Körpern, mathematische Methoden zum Hacken von Pseudozufallszahlengeneratoren). Ohne Kenntnis der Funktionsprinzipien von Generatoren auf PrSSLOS-Basis ist es unmöglich, die Funktionsweise komplexerer Geräte zu verstehen. Aufgrund ihrer einfachen Hardware-Implementierung sind sie in der Technik weit verbreitet. Die Forschung von RgCCOS führte zur Entstehung neuer Chiffren – Block und Stream – basierend auf diesen Registertypen (Moving-Permutation-Chiffre, DES usw.; EDS, Hash-Funktionen).

Im Allgemeinen hat die Forschung in diesem Bereich die Entwicklung von Kryptographie und Kryptoanalytik, Computern und Geräten erheblich vorangetrieben und auch die Implementierung einer Reihe anderer nützlicher Funktionen ermöglicht (z. B. die Korrektur zyklischer Codes).

REFERENZLISTE

1. Schneier Bruce. Angewandte Kryptographie. Protokolle, Algorithmen, Quelltexte in C-Sprache. M.: Triumph, 2002
2. Babash A.V. Kryptografische und automatentheoretische Aspekte moderner Informationssicherheit. Band 1 M.: Verlag. EAOI Center, 2009. 414 S.
3. E.S. Selmer. Monographie: „Lineare Rekursion in einem endlichen Körper.“ Universität Bergen, Norwegen, 1966.
4. N. Zierler und J. Brillhart. „On primitive trinomials modulo 2“, Journal of Information and Control, Band 13, Nr. 6, Dezember 1968, S. 541–544.
5. K.H. Meyer und W. L. Tuchman. „Pseudozufallscodes können gebrochen werden“, Electronic Design Magazine, Nr. 23. November 1972.
6. J. L. Massey. „Verallgemeinerung von Schieberegistern und Dekodierung des Bose-Chowdhury-Hocquenghem-Codes“, IEEE Transactions on Information Theory, v. IT-15, n . 1, Januar 1969, S. 122-127.
7. S.U. Golomb. Shift Register Sequences, San Francisco, Golden Day, 1967 (Nachdruck von Aigean Park Press, 1982).

Anhang A

Tabelle einiger primitiver Polynome Modulo 2

(1, 0)

(2, 1, 0)

(3, 1, 0)

(4, 1, 0)

(5, 2, 0)

(6, 1, 0)

(7, 1, 0)

(7, 3, 0)

(8, 4, 3, 2, 0)

(9, 4, 0)

(10, 3, 0)

(11, 2, 0)

(12, 6, 4, 1, 0)

(13, 4, 3, 1, 0)

(14, 5, 3, 1, 0)

(15, 1, 0)

(16, 5, 3.2, 0)

(17, 3, 0)

(17, 5, 0)

(17, 6, 0)

(18, 7, 0)

(18, 5, 2, 1, 0)

(19, 5, 2, 1, 0)

(20, 3, 0)

(21, 2, 0)

(22, 1, 0)

(23, 5, 0)

(24, 4, 3, 1, 0)
(25, 3, 0)

(26, 6, 2, 1, 0)

(27, 5, 2, 1, 0)

(28, 3, 0)

(29, 2, 0)

(30, 6, 4, 1.0)

(31, 3, 0)

(31, 6, 0)

(31, 7, 0)

(31, 13, 0)

(32, 7, 6, 2, 0)

(32, 7, 5, 3, 2, 1, 0)

(33, 13, 0)

(33, 16, 4, 1, 0)

(34, 8, 4, 3, 0)

(34, 7, 6, 5, 2, 1, 0)

(35, 2, 0)

(135, 11, 0)

(135, 16, 0)

(135, 22, 0)

(136, 8, 3, 2, 0)

(137, 21, 0)

(138, 8, 7, 1, 0)

(139, 8, 5, 3, 0)

(140, 29, 0)

(141, 13, 6, 1, 0)

(142, 21, 0)

(143, 5, 3, 2, 0)

(144, 7, 4, 2, 0)

(145, 52, 0)

(145, 69, 0)

(146, 5, 3, 2, 0)

(147, 11, 4, 2, 0)

(148, 27, 0)

(149, 10, 9, 7, 0)

(150, 53, 0)

(151, 3, 0)

(151, 9, 0)

(151, 15, 0)

(151, 31, 0)

(151, 39, 0)

(151, 43, 0)

(151, 46, 0)

(151, 51, 0)

(151, 63, 0)

(151, 66, 0)

(151, 67, 0)

(151, 70, 0)

(36, 11, 0)

(36, 6, 5, 4, 2, 1, 0)

(37, 6, 4, 1, 0)

(37, 5, 4, 3, 2, 1, 0)

(38, 6, 5, 1, 0)

(39, 4, 0)

(40, 5, 4, 3, 0)

(41, 3, 0)

(42, 7, 4, 3, 0)

(42, 5, 4, 3, 2, 1, 0)

(43, 6, 4, 3, 0)

(44, 6, 5, 2, 0)

(45, 4, 3, 1, 0)

(46, 8, 7, 6, 0)

(46, 8, 5, 3, 2, 1, 0)

(47, 5, 0)

(48, 9, 7, 4, 0)

(48, 7, 5, 4, 2, 1, 0)

(49, 9, 0)

(49, 6, 5, 4, 0)

(50, 4, 3, 2, 0)

(51, 6, 3, 1, 0)

(52, 3, 0)

(53, 6, 2, 1, 0)

(54, 8, 6, 3, 0)

(54, 6, 5, 4, 3, 2, 0)

(55, 24, 0)

(55, 6, 2, 1, 0)

(56, 7, 4, 2, 0)

(57, 7, 0)

(57, 5, 3, 2, 0)

(58, 19.0)

(58, 6, 5, 1, 0)

(59, 7, 4, 2, 0)

(59, 6, 5, 4, 3, 1, 0)

(60, 1, 0)

(61, 5, 2, 1, 0)

(62, 6, 5, 3, 0)

(63, 1, 0)

(64, 4, 3, 1, 0)

(65, 18, 0)

(65, 4, 3, 1, 0)

(66, 9, 8, 6, 0)

(66, 8, 6, 5, 3, 2, 0)

(67, 5, 2, 1, 0)

(152, 6, 3, 2, 0)

(153, 1, 0)

(153, 8, 0)

(154, 9, 5, 1, 0)

(155, 7, 5, 4, 0)

(156, 9, 5, 3, 0)

(157, 6, 5, 2, 0)

(158, 8, 6, 5, 0)

(159, 31, 0)

(159, 34, 0)

(159, 40, 0)

(160, 5, 3, 2, 0)

(161, 18, 0)

(161, 39, 0)

(161, 60, 0)

(162, 8, 7, 4, 0)

(163, 7, 6, 3, 0)

(164, 12, 6, 5, 0)

(165, 9, 8, 3, 0)

(166, 10, 3, 2, 0)

(167, 6, 0)

(170, 23, 0)

(172, 2, 0)

(174, 13, 0)

(175, 6, 0)

(175, 16, 0)

(175, 18, 0)

(175, 57, 0)

(177, 8, 0)

(177, 22, 0)

(1 77, 88, 0)

(68, 9, 0)

(68, 7, 5, 1, 0)

(69, 6, 5, 2, 0)

(70, 5, 3, 1, 0)

(71, 6, 0)

(71, 5, 3, 1, 0)

(72, 10, 9, 3, 0)

(72, 6, 4, 3, 2, 1, 0)

(73, 25, 0)

(73, 4, 3, 2, 0)

(74, 7, 4, 3, 0)

(75, 6, 3, 1, 0)

(76, 5, 4, 2, 0)

(77, 6, 5, 2, 0)

(78, 7, 2, 1, 0)

(79, 9, 0)

(79, 4, 3, 2, 0)

(80, 9, 4, 2, 0)

(80, 7, 5, 3, 2, 1, 0)

(81, 4, 0)

(82, 9, 6, 4, 0)

(82, 8, 7, 6, 1, 0)

(83, 7, 4, 2, 0)

(84, 13, 0)

(84, 8, 7, 5, 3, 1, 0)

(85, 8, 2, 1, 0)

(86, 6, 5, 2, 0)

(87, 13, 0)

(87, 7, 5, 1, 0)

(88, 11, 9, 8, 0)

(88, 8, 5, 4, 3, 1, 0)

(89, 38, 0)

(89, 51, 0)

(89, 6, 5, 3, 0)

(90, 5, 3, 2, 0)

(91, 8, 5, 1, 0)

(91, 7, 6, 5, 3, 2, 0)

(92, 6, 5, 2, 0)

(93, 2, 0)

(94, 21, 0)

(94, 6, 5, 1, 0)

(95, 11, 0)

(95, 6, 5, 4, 2, 1, 0)

(96, 10, 9, 6, 0)

(96, 7, 6, 4, 3, 2, 0)

(178, 87, 0)

(183, 56, 0)

(194, 87, 0)

(198, 65, 0)

(201, 14, 0)

(201, 17, 0)

(201, 59, 0)

(201, 79, 0)

(202, 55, 0)

(207, 43, 0)

(212, 105, 0)

(218, 11, 0)

(218, 15, 0)

(218, 71, 0)

(218.83, 0)

(225, 32, 0)

(225, 74, 0)

(225, 88, 0)

(225, 97, 0)

(225, 109, 0)

(231, 26, 0)

(231, 34, 0)

(234, 31, 0)

(234, 103, 0)

(236, 5, 0)

(250, 103, 0)

(255, 52, 0)

(255, 56, 0)

(255, 82, 0)

(258, 83, 0)

(266, 47, 0)

(97, 6, 0)

(98, 11, 0)

(98, 7, 4, 3, 1, 0)

(99, 7, 5, 4, 0)

(100, 37, 0)

(100, 8, 7, 2, 0)

(101, 7, 6, 1, 0)

(102, 6, 5, 3, 0)

(103, 9, 9)

(104, 11, 10, 1, 0)

(105, 16, 0)

(106, 15, 0)

(107, 9, 7, 4, 0)

(108, 31, 0)

(109, 5, 4, 2.0)

(110, 6, 4, 1, 0)

(111, 10, 0)

(111, 49, 0)

(113, 9, 0)

(113, 15, 0)

(113, 30, 0)

(114, 11, 2, 1, 0)

(115, 8, 7, 5, 0)

(116, 6, 5, 2, 0)

(117, 5, 2, 1, 0)

(118, 33, 0)

(119, 8, 0)

(119, 45, 0)

(120, 9, 6, 2, 0)

(121, 18, 0)

(122, 6, 2, 1, 0)

(123, 2, 0)

(124, 37, 0)

(125, 7, 6, 5, 0)

(126, 7, 4, 2, 0)

(127, 1, 0)

(127, 7, 0)

(127, 63, 0)

(128, 7, 2, 1, 0)

(129, 5, 0)

(130, 3, 0)

(131, 8, 3, 2, 0)

(132, 29, 0)

(133, 9, 8, 2, 0)

(134, 57, 0)

(270, 133, 0)

(282, 35, 0)

(282, 43, 0)
(286, 69, 0)

(286, 73, 0)

(294, 61, 0)

(322, 67, 0)

(333, 2, 0)

(350, 53, 0)

(366, 29, 0)

(378, 43, 0)

(378, 107, 0)

(390, 89, 0)

(462, 73, 0)

(521, 32, 0)

(521, 48, 0)

(521, 158, 0)

(521, 168, 0)

(607, 105, 0)

(607, 147, 0)

(607, 273, 0)

(1279, 216, 0)

(1279, 418, 0)

(2281, 715, 0)

(2281, 915, 0)

(2281, 1029, 0)

(3217, 67, 0)

(3217, 576, 0)

(4423, 271, 0)

(9689, 84, 0)

Eintritt in den Ausgangszustand (IS)

Überprüfung der Richtigkeit der Eingaben

Geben Sie eine Fehlermeldung aus

Einstellen der Tippsequenz

Aufnahme eines IC in die Statustabelle

Nehmen Sie i auf Registerzustand und Ausgabebit in die Zustandstabelle

IS==Aktueller Zustand

Ergebnisse speichern

Ausgabe einer pseudozufälligen Sequenz

Ausfahrt

Start

Ja

Ja

Nein

Sequenzen auf Schieberegistern werden häufig zum Erstellen von Stream-Chiffren verwendet. Das Feedback-Schieberegister besteht aus zwei Teilen: dem Schieberegister und der Feedback-Funktion, wie in Abb. 87. Das Schieberegister selbst ist eine Folge von Bits, deren Anzahl die Länge des Registers bestimmt. Wenn ein Register also n Bits enthält, spricht man von einem n-Bit-Schieberegister. Jedes Mal, wenn ein Bit abgerufen wird, werden alle Bits im Schieberegister um eine Position nach rechts verschoben, normalerweise in Richtung der niedrigstwertigen Bits. Die Schieberegisterperiode ist die Länge der resultierenden Sequenz, bevor ihre Wiederholung beginnt.

Reis. 87.

Jede mathematische Funktion, die eine Aktion an Bits ausführt, kann als Rückmeldung dienen. Der einfachste Typ eines rückgekoppelten Schieberegisters ist ein linear rückgekoppeltes Schieberegister (LFSR). In RFLS ist die Rückmeldung einfach eine Modulo-2-Additionsoperation (XOR) für einige Registerbits; Die Liste dieser Bits wird als Folge von Abgriffen oder Aufnahmepunkten bezeichnet, wie in Abb. 88. Manchmal wird dieses Muster Fibonacci-Konfiguration genannt. Aufgrund der Einfachheit der Rückkopplungssequenz kann eine ziemlich fortgeschrittene mathematische Theorie zur Analyse von LFSR verwendet werden. In jedem Fall wird die Qualität des generierten PSP anhand eines speziellen Testsatzes beurteilt.

Reis. 88.

SFLOs werden in Form von Polynomen geschrieben. In diesem Fall gibt die Potenz des ersten Elements des Polynoms die Anzahl der Bits im Schieberegister an, und die Potenzexponenten der übrigen Elemente des Polynoms geben an, welche Abtastpunkte verwendet werden. So bedeutet beispielsweise der Eintrag x 4 + x + 1, dass ein Register mit vier Elementen verwendet wird, bei dem die Bits bi und b 0 an der Rückkopplungsbildung beteiligt sind (Abb. 89).

Reis. 89,4

Betrachten wir die Funktionsweise des in Abb. gezeigten Registers. 89. Wir initialisieren es zum Beispiel mit dem Wert 0101 (die Erstinitialisierung kann durch jede beliebige Bitfolge erfolgen, mit Ausnahme einer Folge nur von Nullen, da in diesem Fall die Rückmeldung immer den Wert Null bildet und das Register dies tut nicht die erwartete Bandbreite erzeugen). Das Register verschiebt sich also um eine Position nach rechts. Das niedrigstwertige Bit, gleich 1, wird aus dem Register verdrängt und bildet das erste Bit der Speicherbandbreite. Diejenigen Bits, die sich in den Positionen b und b 0 befanden, werden vor der Verschiebung modulo 2 addiert und bilden ein neues

das höchstwertige Bit des Registers. Ein klares Beispiel für die Funktionsweise des betrachteten LFSR ist in Abb. dargestellt. 90.

Reis. 90.

Wie aus Abb. ersichtlich ist. 90 durchläuft das Füllen des Registers das Gewicht von 15 der 16 möglichen Zustände (zuvor haben wir festgestellt, dass der sechzehnte Zustand, wenn LFSR 0000 ist, nicht berücksichtigt werden kann). Danach entspricht die Füllung des Registers wieder dem Anfangswert 0101 und die Generierung der Bitfolge beginnt sich zu wiederholen. Die Ausgabesequenz des Registers ist eine Folge niedrigstwertiger Bits (bis zur horizontalen Linie in Abb. 90): 101011110001001. Die Größe der Bitsequenz vor ihrer Wiederholung wird als Periode bezeichnet. Um die maximale Periode eines bestimmten LFSR sicherzustellen (d. h. damit das Register die Gewichtung möglicher interner Zustände durchläuft), muss das Polynom, das den Betrieb des Registers bestimmt, primitiv Modulo 2 sein. Wie bei großen Primzahlen gibt es keine Möglichkeit, solche Polynome zu erzeugen. Sie können nur ein Polynom nehmen und prüfen, ob es modulo 2 irreduzibel ist oder nicht. Im allgemeinen Fall ist ein primitives Polynom vom Grad n ein irreduzibles Polynom, das ein Teiler von x 2 "+1 ist, aber kein Teiler von x d +1 für alle d, die Teiler von 2" -1 sind. In der Arbeit von B. Schneier wird eine Tabelle einiger Polynome gegeben, die modulo 2 irreduzibel sind.

Fasst man die Erkenntnisse aus der Betrachtung eines Beispiels für die Funktionsweise des LFSR zusammen (Abb. 90), können wir sagen, dass sich ein n-Bit-LFSR in einem der internen 2-Zoll-1-Zustände befinden kann. Theoretisch kann ein solches Register eine Pseudozufallsfolge mit einer Periode von 2 n -1 Bits erzeugen. Solche Register werden LFSR-Register mit maximaler Periode genannt. Die resultierende Ausgabe wird als T-Sequenz bezeichnet.

Die einfachste Art von Rückkopplungsfunktion ist eine lineare Funktion, beispielsweise die Modulo-2-Summe des Inhalts bestimmter Bits. Dieses Register wird als lineares Rückkopplungsschieberegister (LFSR) bezeichnet. Im Allgemeinen wird die lineare Rückkopplungsfunktion durch die Formel angegeben. Hier c k= 1 wenn k Das te Bit wird in der Feedback-Funktion verwendet und c k= 0 sonst. Das Symbol Å bezeichnet die Addition Modulo 2 (exklusives ODER).

Betrachten Sie beispielsweise ein LFSR mit einer Feedback-Funktion (siehe Abbildung).

Wenn der Anfangszustand des Registers 1111 ist, nimmt es in nachfolgenden Taktzyklen die folgende Reihe von Zuständen an: 1111, 0111, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 0010, 0001, 1000, 1100, 1110, 1111, ...

Die Ausgabesequenz wird aus dem niedrigstwertigen (ganz rechten) Bit des Registers gebildet. Es sieht folgendermaßen aus: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1. Es ist ersichtlich, dass die generierte Bitfolge vollständig vom Anfangszustand des Registers und der Rückkopplungsfunktion bestimmt wird. Da die Anzahl der möglichen Registerzustände endlich ist (sie ist gleich 2). L), dann wird sich die Tastenfolge früher oder später wiederholen. Die maximale Länge eines sich nicht wiederholenden Teils einer Tastenfolge wird als Periode bezeichnet T. Der Zeitraum hängt von der Feedback-Funktion ab. Der maximal mögliche Zeitraum beträgt T max = 2 L-1 (das Register akzeptiert alle möglichen Zustände außer 0000...0). Die Ausgabesequenz des LFSR mit der maximalen Periode wird aufgerufen M-Sequenz.

Um herauszufinden, unter welchen Bedingungen das LFSR eine maximale Periode hat, weisen die Rückkopplungsfunktionen ein charakteristisches Polynom zu. Somit entspricht das oben beispielhaft angegebene Register einem Polynom. Die theoretische Analyse zeigt, dass das LFSR genau dann eine maximale Periode hat, wenn das Polynom P(X) Ist Primitive. Nachfolgend sind einige primitive Polynome aufgeführt, die für die Verwendung in der Praxis empfohlen werden. Die Tabelle zeigt die Potenzen der Variablen X in Polynomschreibweise. Beispielsweise entspricht der Eintrag (31, 3) einem Polynom.

№	P(X)	№	P(X)	№	P(X)
	(39, 16, 23, 35)		(38, 5, 6, 27)		(32, 2, 7, 16)
	(30, 6, 4, 1)		(31, 6)		(31, 7)
	(31, 13)		(31, 25, 23, 8)		(33, 13)
	(35, 2)		(47, 5)		(48, 9, 7, 4)
	(47, 11, 24, 32)		(46, 18, 31, 40)		(53, 6, 2, 1)
	(55, 24)		(57, 7)		(58, 19)
	(59, 7, 4, 2)		(41, 27, 31, 32)		(61, 5, 2, 1)
	(42, 30, 31, 34)		(51, 15, 24, 46)		(50, 17, 31, 34)

LFSRs wurden ursprünglich für die Hardware-Implementierung als Satz digitaler Schaltkreise entwickelt. Software-Implementierungen von LFSR sind in der Regel schneller als Hardware-Implementierungen. Zur Steigerung der Performance ist es vorteilhaft, den Registerzustand als Ganzzahl zu speichern L-Bit-Zahl, deren einzelne Bits den Binärbits des Registers entsprechen. Anschließend werden bitweise Operationen (Verschiebung, Maskierung usw.) verwendet, um auf einzelne Bits zuzugreifen.

In einem Schieberegister mit linearer Rückkopplung gibt es zwei Teile (Module): das Schieberegister selbst und die Schaltkreise (oder Unterprogramme), die den Wert des gedrückten Bits berechnen. Ein Register besteht aus Funktionszellen (oder Bits eines Maschinenworts oder mehrerer Wörter), die jeweils den aktuellen Zustand eines Bits speichern. Die Anzahl der Zellen wird als Registerlänge bezeichnet. Bits (Zellen) werden normalerweise mit Zahlen nummeriert, von denen jedes ein Bit speichern kann. Das berechnete Bit wird in die Zelle geschoben und das nächste generierte Bit wird aus der Zelle entfernt. Die Berechnung des zu verschiebenden Bits erfolgt normalerweise vor der Verschiebung des Registers und erst nach der Verschiebung wird der Wert des berechneten Bits in die Zelle eingefügt.

Die Schieberegisterperiode ist die Mindestlänge der resultierenden Sequenz, bevor sie sich zu wiederholen beginnt. Da ein Register aus Bitzellen nur verschiedene Zustände ungleich Null aufweist, kann die Periode des Registers diese Zahl grundsätzlich nicht überschreiten. Wenn die Registerperiode dieser Zahl entspricht, wird ein solches Register als Maximalperiodenregister bezeichnet.

Für LFSR ist die Rückkopplungsfunktion eine lineare boolesche Funktion der Zustände aller oder einiger Registerbits. Beispielsweise ist die Modulo-Zwei-Summe oder ihre logische Umkehrung eine lineare boolesche Funktion (XOR-Operation, in Formeln als bezeichnet) und wird am häufigsten in solchen Registern verwendet.

In diesem Fall werden üblicherweise diejenigen Bits aufgerufen, die Variablen der Rückkopplungsfunktion sind Kurven.

Die Registersteuerung in Hardware-Implementierungen erfolgt durch Anlegen eines Schiebeimpulses (auch „Shift Pulse“ genannt). Uhr oder Synchronimpuls) an alle Zellen, in Software – durch die Ausführung eines Softwarezyklus, einschließlich der Berechnung der Rückkopplungsfunktion und der Verschiebung von Bits in einem Wort.

Während jedes Zeitschritts werden die folgenden Vorgänge ausgeführt:

Schieberegister mit linearer Rückkopplung

Als Rückkopplungsfunktion wird also die logische Operation XOR (exklusives ODER) verwendet, also:

Eigenschaften primitiver Polynome

Eigenschaften

Die Eigenschaften der vom LFSR erzeugten Sequenz stehen in engem Zusammenhang mit den Eigenschaften des zugehörigen Polynoms. Seine von Null verschiedenen Koeffizienten werden aufgerufen Kurven, sowie die entsprechenden Registerzellen, die die Werte der Feedback-Funktionsargumente liefern.

Lineare Komplexität

Die lineare Komplexität einer Binärsequenz ist eines der wichtigsten Merkmale der Funktionsweise von LFSR. Führen wir die folgende Notation ein:

Definition

Lineare Komplexität einer unendlichen Binärfolge heißt eine Zahl, die wie folgt definiert ist:

Lineare Komplexität einer endlichen Binärfolge heißt eine Zahl, die gleich der Länge des kürzesten LFSR ist, das eine Folge erzeugt, deren erste Terme sind.

Eigenschaften der linearen Komplexität

Seien und binäre Folgen. Dann:

Korrelationsunabhängigkeit

Um eine hohe lineare Komplexität zu erreichen, versuchen Kryptographen, die Ergebnisse mehrerer Ausgabesequenzen nichtlinear zu kombinieren. In diesem Fall besteht die Gefahr, dass eine oder mehrere Ausgabesequenzen (häufig sogar die Ausgaben einzelner LFSRs) durch einen gemeinsamen Schlüsselfluss verbunden und mithilfe der linearen Algebra geöffnet werden können. Hacking, das auf einer solchen Sicherheitslücke basiert, nennt man Korrelationsautopsie. Thomas Siegenthaler zeigte, dass es möglich ist, die Korrelationsunabhängigkeit präzise zu spezifizieren, und dass es einen Kompromiss zwischen Korrelationsunabhängigkeit und linearer Komplexität gibt.

Die Hauptidee eines solchen Hacks besteht darin, eine gewisse Korrelation zwischen der Leistung des Generators und der Leistung einer seiner Komponenten zu erkennen. Durch Beobachtung der Ausgabereihenfolge können dann Informationen über diese Zwischenausgabe gewonnen werden. Mithilfe dieser Informationen und anderer Korrelationen können Daten an anderen Zwischenpins gesammelt werden, bis der Generator kompromittiert wird.

Korrelationsangriffe oder Variationen wie schnelle Korrelationsangriffe, bei denen ein Kompromiss zwischen Rechenkomplexität und Effizienz erforderlich ist, wurden erfolgreich gegen viele lineare Rückkopplungs-Schieberegister-Keystream-Generatoren eingesetzt.

Beispiel

Für SFLOS mit einem zugehörigen Polynom hat die generierte Sequenz die Form. Nehmen wir an, dass vor dem Start des Prozesses die Sequenz in das Register geschrieben wird, dann ist die Periode des generierten Bitstroms gleich 7 mit der folgenden Sequenz:

Schrittnummer	Zustand	Generiertes Bit
0		-
1		1
2		1
3		0
4		1
5		1
6		1
7		0

Da der interne Zustand im siebten Schritt in seinen ursprünglichen Zustand zurückgekehrt ist, kommt es ab dem nächsten Schritt zu einer Wiederholung. Mit anderen Worten, die Periode der Sequenz betrug 7, was auf die Primitivität des Polynoms zurückzuführen ist.

Algorithmen zur Erzeugung primitiver Polynome

Fertige Tische

Die Berechnung der Primitivität eines Polynoms ist ein ziemlich komplexes mathematisches Problem. Daher gibt es vorgefertigte Tabellen, die die Anzahl der Abgriffsequenzen anzeigen, die für die maximale Periodendauer des Generators sorgen. Für ein 32-Bit-Schieberegister gibt es beispielsweise die Sequenz . Das bedeutet, dass Sie zum Generieren eines neuen Bits das 31., 30., 29., 27., 25. und 0. Bit mithilfe der XOR-Funktion hinzufügen müssen. Der Code für ein solches RLOS in der Sprache C lautet wie folgt:

Int LFSR (void) ( static unsigned long S = 1; S = ((( (S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25 ) ^ S ) & 1 )<< 31 ) | (S>> 1); return S & 1 ; )

Softwareimplementierungen von LFSR-Generatoren sind recht langsam und arbeiten schneller, wenn sie in Assembler statt in der Sprache C geschrieben sind. Eine Lösung besteht darin, 16 RSLOS parallel zu verwenden (oder 32, abhängig von der Wortlänge in der Architektur eines bestimmten Computers). In einem solchen Schema wird ein Array von Wörtern verwendet, dessen Größe der Länge des LFSR entspricht, und jedes Bit eines Wortes im Array verweist auf sein eigenes LFSR. Vorausgesetzt, dass die gleichen Tap-Sequenznummern verwendet werden, kann dies zu einem spürbaren Leistungsgewinn führen. [brauche ein Codebeispiel] (Siehe: Bitslice).

Galois-Konfiguration

Galois-Konfiguration eines linearen Feedback-Schieberegisters

Auch die Rückkopplungsschaltung kann modifiziert werden. In diesem Fall verfügt der Generator nicht über eine größere kryptografische Stärke, lässt sich aber einfacher in Software implementieren. Anstatt das Bit ganz links der Abgriffsequenz zu verwenden, um das neue Bit ganz links zu generieren, verknüpft es jedes Bit der Abgriffsequenz mit dem Ausgang des Generators XOR und ersetzt es durch das Ergebnis dieser Aktion, dann wird der Ausgang des Generators zum neuen ganz linkes Bit. In C sieht es so aus:

Int LFSR (void) ( static unsigned long Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ); return Q & 1 ; )

Der Vorteil besteht darin, dass alle XORs in einem Vorgang ausgeführt werden.

• Es kann bewiesen werden, dass die zuerst angegebene Fibonacci-Konfiguration und die hier angegebene Galois-Konfiguration die gleichen Folgen (Länge 2 32 −1) ergeben, jedoch phasenverschoben zueinander sind
• Eine Schleife mit einer festen Anzahl von Aufrufen der LFSR-Funktion in der Galois-Konfiguration läuft ungefähr doppelt so schnell wie in der Fibonacci-Konfiguration (MS VS 2010-Compiler auf Intel Core i5).
• Beachten Sie, dass in der Galois-Konfiguration die Reihenfolge der Bits im Wort, das die Rückmeldung definiert, im Vergleich zur Fibonacci-Konfiguration umgekehrt ist

Beispiele für Generatoren

Stop-and-go-Generatoren

Wechselnder Stop-Go-Generator

Dieser Oszillator verwendet den Ausgang eines LFSR, um die Taktfrequenz eines anderen LFSR zu steuern. Der Taktausgang von RSLOS-2 wird durch den Ausgang von RSLOS-1 gesteuert, sodass RSLOS-2 seinen Zustand zum Zeitpunkt t nur ändern kann, wenn der Ausgang von RSDOS-1 zum Zeitpunkt t-1 gleich eins war. Aber dieses Schema konnte der Korrelationsanalyse nicht widerstehen.

Daher wurde ein verbesserter Generator vorgeschlagen, der auf derselben Idee basiert. Man spricht von einem alternierenden Stop-Go-Generator. Es werden drei LFSRs unterschiedlicher Länge verwendet. RSLOS-2 wird getaktet, wenn der Ausgang von RSLOS-1 gleich eins ist, und RSLOS-3 wird getaktet, wenn der Ausgang von RSLOS-1 gleich null ist. Der Ausgang des Generators ist die Modulo-2-Summe von RSLOS-2 und RSLOS-3. Dieser Generator hat eine lange Periode und eine hohe lineare Komplexität. Seine Autoren zeigten auch eine Methode zur korrelativen Öffnung von RSLOS-1, die den Generator jedoch nicht wesentlich schwächt.

Gollmann-Kaskade

Gollmann-Kaskade

Die Gollmann-Kaskade ist eine verbesserte Version des Stop-Go-Generators. Es besteht aus einer Folge von LFSRs, deren Timing jeweils vom vorherigen LFSR gesteuert wird. Wenn der Ausgang von RSLOS-1 zum Zeitpunkt t 1 ist, dann ist RSLOS-2 getaktet. Wenn der Ausgang von RSLOS-2 zum Zeitpunkt t 1 ist, wird RSLOS-3 getaktet und so weiter. Der Ausgang des letzten LFSR ist der Ausgang des Generators. Wenn die Länge aller LFSRs gleich und gleich n ist, dann ist die lineare Komplexität eines Systems von k LFSRs gleich.

Diese Idee ist einfach und kann verwendet werden, um Sequenzen mit großen Perioden, großer linearer Komplexität und guten statistischen Eigenschaften zu erzeugen. Aber leider reagieren sie empfindlich auf das Öffnen, was als „Lock-in“ bezeichnet wird. Für eine höhere Haltbarkeit wird die Verwendung von k von mindestens 15 empfohlen. Darüber hinaus ist es besser, mehr kurze SFSRs als weniger lange SFSRs zu verwenden.

Schwellenwertgenerator

Schwellenwertgenerator

Dieser Generator versucht, die Sicherheitsprobleme früherer Generatoren zu umgehen, indem er eine variable Anzahl von Schieberegistern verwendet. Theoretisch erhöht sich bei Verwendung einer größeren Anzahl von Schieberegistern die Komplexität der Verschlüsselung, was in diesem Generator durchgeführt wurde.

Dieser Generator besteht aus einer Vielzahl von Schieberegistern, deren Ausgänge der Majorisierungsfunktion zugeführt werden. Wenn die Anzahl der Einsen an den Ausgängen der Register mehr als die Hälfte beträgt, gibt der Generator eine Eins aus. Wenn die Anzahl der Nullen an den Ausgängen mehr als die Hälfte beträgt, gibt der Generator eine Null aus. Damit ein Vergleich der Anzahl der Nullen und Einsen möglich ist, muss die Anzahl der Schieberegister ungerade sein. Die Längen aller Register müssen teilerfremd sein und die Rückkopplungspolynome müssen primitiv sein, damit die Periode der generierten Sequenz maximal ist.

Für den Fall von drei Schieberegistern kann der Generator wie folgt dargestellt werden:

Dieser Generator ähnelt dem Geff-Generator, außer dass der Schwellenwertgenerator eine höhere lineare Komplexität aufweist. Seine lineare Komplexität ist:

Dabei sind , , die Längen des ersten, zweiten und dritten Schieberegisters.

Der Nachteil besteht darin, dass jedes Ausgangsbit Informationen über den Zustand des Schieberegisters liefert. Oder besser gesagt, 0,189 Bit. Daher ist dieser Generator möglicherweise nicht in der Lage, einem Korrelationsangriff zu widerstehen.

Andere Arten

Selbstverdünnend

Selbstdezimierende Generatoren sind solche, die ihre eigene Frequenz steuern. Es wurden zwei Arten solcher Generatoren vorgeschlagen. Das erste besteht aus einem Schieberegister mit linearer Rückkopplung und einigen Schaltkreisen, die das Register abhängig von den Ausgangswerten des Schieberegisters takten. Wenn der Ausgang des SFSR gleich eins ist, wird das Register d-mal getaktet. Wenn der Ausgang Null ist, wird das Register k-mal getaktet. Der zweite hat fast den gleichen Aufbau, ist aber leicht modifiziert: In der Taktschaltung ist der Eingang, als Kontrolle für 0 oder 1, nicht das Ausgangssignal selbst, sondern XOR bestimmter Bits des Schieberegisters mit linearer Rückkopplung. Leider ist dieser Generatortyp nicht sicher.

Mehrgeschwindigkeitsoszillator mit innerem Produkt

Dieser Oszillator verwendet zwei lineare Feedback-Schieberegister mit unterschiedlichen Taktfrequenzen: RSLOS-1 und RSLOS-2. Die Taktfrequenz von RSLOS-2 ist d-mal höher als die von RSLOS-1. Die einzelnen Bits dieser Register werden durch die UND-Verknüpfung verknüpft. Die Ausgaben der UND-Verknüpfung werden dann XOR-verknüpft. Die Ausgabesequenz wird diesem XOR-Block entnommen. Auch dieser Generator ist nicht fehlerfrei (er hat der Entdeckung der linearen Konsistenz nicht standgehalten. Wenn - die Länge von SFLO-1, - die Länge von SFLO-2 und d das Verhältnis der Taktfrequenzen ist, dann ist der interne Zustand des Der Generator kann aus einer Ausgabesequenz der Länge ) erhalten werden, weist jedoch eine hohe lineare Komplexität und eine hervorragende statistische Leistung auf.