Stromchiffren

Allgemein

[Folie 1]

Mit Stromchiffren möchte man das ONE-TIME-PAD simulieren. Das ist ein absolut sicheres Verfahren. Es wurde 1949 beweisen, dass es keine Schwächen hat. Leider ist es vollkommen unpraktikabel. Man braucht eine Zufallsquelle, die einen Bitstrom der Länge der Nachricht generiert und muss diese Zufallsbits an den Empfänger transferieren. Das Problem einer geheimen Übermittlung einer Nachricht wird dort also verlagert auf das Problem einer geheimen Übermittlung einer Zufallsbitfolge. Das ist fast dasselbe, man hat nur einen zeitlichen Gewinn, denn die Zufallsfolge kann man zu einem gewählten Zeitpunkt übermitteln, aber die zu sendenden Nachrichten entstehen aus einem bestimmten Anlass oder wegen eines Ereignisses und dies lässt sich in der Regel zeitlich nicht vorhersehen oder verschieben. Das generelle Problem, Zufallsbits zu produzieren ist für nachweislich echten Zufall ebenfalls nicht trivial.

LFSR

Allgemein

[Folie 2]

Das linear-feedback-shift-register (LFSR) ist ein hocheffizienter Schaltkreis, der auch in Software (Maschinensprache) extrem schnelle Bitfolgen mit guten statistischen Eigenschaften erzeugt

Zusätzlich erzeugt ein LFSR unter bestimmten Bedingungen, die wir gleich in der Folge klären, die maximale Periode von 2^n-1, es werden also dann alle möglichen internen Zustände aus n Bits angenommen, nur einer nicht. Welcher? Nun, wenn alle Bits auf 0 stehen, dann ist das Ergebnis wieder 0 und das LFSR würde in einer Endlosschleife nur Nullen produzieren. Also alle Zustände außer 000...0 sind möglich.

Die Arbeitsweise ist dargestellt, versuchen Sie durch direkte Rechnung auf Papier die erzeugte Folge nachzurechnen.

Hier schon gleich eine vertraute Erinnerung: Programmieren Sie!

Es ist eine simple Programmieraufgabe, die man im Bachelor, 1. Semester stellen könnte: Schreiben Sie ein Programm, dass bei Eingabe des LFSR und eines Anfangszustands die 2^n-1 Bits der Folge ausgibt. Sie können das dann vergleichen mit (s.o.) Ihrem Versuch, die 4-Bit-LFSR Folge von Hand auszurechnen.

Maximale Periodenlänge

Bezeichnungen

[Folie 2]

Wir gehen der Frage nach, wann ein LFSR wirklich einen (nirgendwo wiederholten) Bitstrom der Länge 2^n-1 produziert. Hierfür benötigen wir einige Begriffe.

Zunächst einmal benötigen wir eine Repräsentierung der LFSR-Schaltung. Wenn das Bit i verknüpft ist, setzen wir eine Variable p[i] auf 1, sonst 0. Ich verwende hier der Deutlichkeit halber die Arrayschreibweise für p[i], auf der Smartboard-Folie steht das i als Index (Subscript zu p).

[Folie 3]

Die p[0], p[1],...,p[n-1] können dann in einer Beschreibung der produzierten "Zufallsbits" s[i] benutzt werden. "Zufallsbits" in Anführungszeichen, weil die s[i] natürlich nicht zufällig, sondern berechnet sind. Sie können in Ihrer Implementierung des LFSR die p[i] auch als Beschreibung des LFSR verstehen und analog einen Startzustand des LFSR in den s[i] festlegen. Die Formel, die in einem Programm dazu benutzt werden kann, weitere Bits zu berechnen, steht unter "Iterationsformel" bei s[i]= ...

Jetzt folgt der konzeptionelle Zusammenhang, der auf die Periodenlänge eingeht.

Polynome

[Folie 4]

Wir bilden das angegebene Polynom aus den n Koeffizienten p[i] und ergänzen vorn ein X^n. Das gibt uns mit n+1 Koeffizienten ein Polynom P(X) vom Grad n. Wir nennen es das charakteristische Polynom des LFSR. Im kleinsten sinnvollen Fall, dem charakteristischen Polynom X+1 haben wir zwei Koeffizienten und das Polynom hat Grad 1, also eins weniger als die Anzahl der Koeffizienten.

Das Ergebnis sei vorweggenommen: damit wir eine maximale Periodenlänge haben können, muss das Polynom zwei Eigenschaften erfüllen, es muss

sein. Was das bedeutet, wird im folgenden ergründet.

Die Zusammenhänge, die wir gleich betrachten, können noch einmal aus einer sinngemäß ähnlichen Perspektive in diesem Stackexhange-Artikel nachvollzogen werden.

Grundsätzlich wird dieses Polynom mod 2 betrachtet, d.h. die Koeffizienten sind entweder 0 oder 1. Beim Addieren wird komponentenweise addiert, d.h.

(X^3+X+1) + (X^2+X) = X^3+X^2+1

Dort also wo zwei 1er-Koeffizienten zusammentreffen entsteht eine 0 und der Term (hier X) kann weggelassen werden.

Es gibt in diesem Kontext viele Parallelen zu den reellen Zahlen, denn diese Struktur, F2 genannt beschreibt einen Körper aus 2 Elementen, der algebraisch verwandt ist mit dem Körper der reellen Zahlen. Insbesondere kann man von Nullstellen und dem Zerlegen vom Polynom in Linearfaktoren reden. Zu jeder Nullstelle gehört ein Linearfaktor, wie Sie es von der Polynomdivision (oder vom Horner-Schema, oder vom Fundamentalsatz der Algebra) her schon kennen.

Für eine maximale Periodenlänge können wir an dieser Stelle schon ein wesentliches Kriterium notieren: das Polynom darf nicht in Faktoren zerlegbar sein. Nicht nur Linearfaktoren, sondern es darf auch keine Zerlegung mit höheren Potenzen geben. Etwa ist

X^4+X^2+1 = (X^2+X+1) * (X^2+X+1)

und X^2+X+1 hat keine Nullstellen.

Wir nennen nicht zerlegbare Polynome irreduzibel. Die Parallele zu irreduziblen Polynomen sind in der Welt der Zahlen die Primzahlen.

Zusätzlich muss ein Polynom P(X) primitiv sein. Dies ist der Fachbegriff dafür, dass das Polynom X mod P(X) maximale Ordnung hat. Der Term X ist eigentlich ein Monom, da nur ein Koeffizient dafür gebraucht wird.

Was bedeutet das Wort primitiv jetzt genau?

Wir berechnen X^j mod P(X). Hierbei darf für 1<=j<=2^n-1 nur an einer Stelle X^j = 1 mod P(X) herauskommen, nämlich für j=2^n-1.

Erleichterungen bei diesem Test:

Am Beispiel X mod (X^2+X+1) ist dies auf [Folie 4] durchgeführt.

Erst bei j=3=2^2-1 entsteht eine 1. Also ist das Polynom X^2+X+1 irreduzibel und primitiv und das zugehörige LFSR hat (maximale) Periodenlänge 3.