Thema: Lineare Feedback-Shift-Register (LFSR)

Stromchiffren

• Unterscheidung der Chiffren in zwei große Klassen: Strom- und Blockchiffren
  • Bei Stromchiffre ändert sich Verschlüsselungsfkt. kontextabhängig
  • Stromchiffren haben daher einen Zustand, für den sie Speicher benötigen, Blockchiffren sind zustandslos und daher i. A. speicherlos
    • Blockchiffren können Zustand und Speicher haben, z. B. wenn im CBC, CFB oder OFB-Modus betrieben; entspricht Stromchiffre mit großer Blockgröße
  • "Blockgröße" einer Stromchiffre beträgt in der Regel ein Bit
    • Benötigen zur Laufzeit weniger Speicher als Blockchiffren, die auf großen Blöcken arbeiten: gut für Hardware-Implementierung
    • Geringere Latenzzeit bei Übertragungen, da jedes Bit sofort ver-/entschlüsselt werden kann
    • Geringe oder keine Fehler-Propagierung (Bitfehler im Chiffretext bleiben z. T. auf ein Bit im Klartext beschränkt)
      • Vorteil, falls mit Übertragungsfehlern gerechnet wird
      • Nachteil, da evtl. aktive Angriffe nicht erkannt werden, falls keine weiteren Maßnahmen ergriffen werden
• Definition Stromchiffre
  • Schlüsselraum: K (meistens K = {0, 1}^*)
  • Schlüsselstrom: e₁e₂e₃... ∈ K
  • Klartext: m₁m₂m₃... ∈ K
  • Verschlüsselung: c_i = E(e_i, m_i)
  • Entschlüsselung: m_i = D(d_i, c_i), wobei d_i = e_i^-1
• Anmerkungen
  • Meistens ist der Schlüsselstrom symmetrisch, also d_i = e_i für alle i
• Weitere Klassifizierung von Stromchiffren:
  • Synchron
    • Schlüsselstrom basiert nur auf Initialisierung (i. d. R. durch den Schlüssel) und dem daraus resultierenden Zustand
    • Kann zeitgleich für Ver-/Entschlüsselung ohne Kenntnis des Klar-/Chiffretexts berechnet werden
    • Bitfehler wirken sich nicht auf weitere Bits aus
    • Einfügen/Löschen von Bits desynchronisiert Ver-/Entschlüsselung komplett
  • Selbst-synchronisierend
    • Schlüsselstrom basiert auf Initialisierung und einer begrenzten Anzahl der letzten Chiffre-Bits
    • Kann erst nach Erhalt der Chiffre-Bits berechnet werden
    • Bitfehler wirken sich auf höchstens so viele Bits aus, wie Chiffre-Bits verwendet werden
    • Einfügen/Löschen von Bits beeinflusst nicht mehr Bits als bei einem Bitfehler
    • Bessere statistische Eigenschaften (Diffusion)

Vernam-Chiffre

• Als Vernam-Chiffre wird eine Klasse von Stromchiffren über dem Alphabet A = {0, 1} bezeichnet
• Nachricht und Schlüsselstrom sind gleich lang: m = m₁m₂...m_t, k = k₁k₂...k_t
• Ver- und Entschlüsselung wird durch XOR mit dem Schlüsselstrom realisiert:
  • c_i = k_i ⊕ m_i, mit 1 ≤ i ≤ t
  • m_i = k_i ⊕ c_i, mit 1 ≤ i ≤ t
• Wenn der Schlüsselstrom absolut zufällig und gleichverteilt gewählt wurde und der Schlüssel nur einmal verwendet wird, spricht man vom Vernam One-Time-Pad.
  • Bietet perfekte Sicherheit
  • Problem der Schlüsselverteilung, da sehr große Schlüssel nötig
  • Angreifbar, falls ein Schlüssel doppelt verwendet wird:
    • c ⊕ c' = (m ⊕ k) ⊕ (m' ⊕ k) = m ⊕ m'
    • Mit m ⊕ m' kann dann weitere Kryptoanalyse betrieben werden.

Lineare Feedback-Shift-Register (LFSR)

• Praktische Fragestellungen:
  1. Muss der Schlüssel wirklich so lang sein, wie die Nachricht?
     • Wie lang muss der Schlüssel im Vergleich zur Nachricht sein, damit die Nachricht sicher ist?
  2. Kann statt einem echt zufälligen Schlüssel auch ein pseudozufälliger Schlüssel verwendet werden?
     • Wie kann aus einem kurzen Schlüssel ein langer erzeugt werden, der trotzdem "zufällig" aussieht?
• Definition binäre additive Stromchiffre (synchrone Stromchiffre)
  • Verallgemeinerung der Vernam-Chiffre
  • Klartext: m₁m₂m₃... ∈ {0, 1}^*
  • Chiffretext: c₁c₂c₃... ∈ {0, 1}^*
  • Schlüsselstrom: z₁z₂z₃... ∈ {0, 1}^*
    • wird erzeugt von einem Schlüsselstromgenerator, welcher mit einem Schlüssel k initialisiert wird
  • Verschlüsselung: c_i = z_i ⊕ m_i
  • Entschlüsselung: m_i = z_i ⊕ c_i
• Definition LFSR
  • Ein LFSR der Länge L hat L Bit-Register s_L-1s_L-2...s₀, welches den aktuellen Zustand speichert. Die initialie Belegung der Register ist der initiale Zustand.
  • Es ist getaktet, und mit jedem Takt werden die Register-Inhalte eine Stelle nach rechts verschoben: s_i-1←s_i für 0 < i ≤ L-1
  • Das linkeste Register-Bit (Feedback-Bit) ergibt sich aus der XOR-Summe der vorherigen Bitwerte bestimmter Register
• Eigenschaften von LFSR
  • Die Wahl der rückgekoppelten Registerwerte kann als Polynom im Restklassenring (Z/2Z) aufgefasst werden:
    C(D) = 1 + c₁D + c₂D² + ... + c_LD^L ∈ (Z/2Z)[D] ist das Rückkopplungspolynom (connection polynomial)
  • Grad des Polynoms ist gleich L <=> c_L = 1 <=> LFSR ist nicht-singulär
  • Die Ausgabe des LFSRs kann als Rekursion aufgefasst werden:
    s_j = (c₁s_j-1 + c₂s_j-2 + ... + c_Ls_j-L) mod 2 für j ≥ L
  • Der Ausgabestrom eines LFSRs ist periodisch.
  • Durch den initialen Zustand der Register ist die Ausgabefolge eindeutig festgelegt.
  • Der initiale Null-Zustand erzeugt nur Nullen im Ausgabestrom.

Periodenlänge

• Einschub: Polynome über endlichen Körpern
  • Ein Polynom f in einer Variable x über einem Körper K ist ein Term der Form:
    f(x) = a_nxⁿ + a_n-1x^n-1 + ... + a₁x + a₀
  • f hat Grad n, falls a_n ≠ 0.
  • Polynome über Körpern können addiert, subrahiert, multipliziert und dividiert werden.
  • K[x] bezeichnet alle Polynome über dem Körper K in der Variablen x.
  • Ist p eine Primzahl (z. B. 2) und f ein Polynom über (Z/pZ)[x], dann heisst f irreduzibel über (Z/pZ), wenn f nicht als Produkt zweier anderer Polynome g, h ∈ (Z/pZ)[x] geschrieben werden kann.
    • Irreduzibilität vergleichbar der Definition von Primzahlen über Z
  • Sei f ein irreduzibles Polynom von Grad n in (Z/pZ)[x]. Wenn das Gruppenelement x ein Erzeuger der multiplikativen Gruppe (Z/f(x)Z)*, dann wird f als primitives Polynom bezeichnet.
    • Potenzierung von x mod (Z/f(x)Z) liefert alle pⁿ-1 von null verschiedenen Restklassen
• Periodizität des Ausgabestroms
  • Wenn das LFSR nicht-singulär ist (Grad des Polynoms ist L), dann beginnt die Periode immer mit dem ersten Bit, andernfalls kann der Periode eine feste Anzahl nicht-periodischer Bits vorausgehen.
  • Gegeben ein LFSR der Länge L. Sei das Rückkopplungspolynom C(D) vom Grad L eine primitives Polynom in (Z/2Z)[D]. Dann erzeugen alle 2^L-1 von null verschiedenen Initialisierungen der Register des LFSRs einen Ausgabestrom mit der maximal möglichen Periode von 2^L-1. Ein solches LFSR wird LFSR maximaler Länge genannt.
  • Bsp.: LFSR maximaler Länge mit L = 32
    • Bistrom hat Periodenlänge 2³²-1 = 4.294.967.295 Bit
    • Entspricht 512 MB nicht-periodische Bitfolge
• Zusammenfassung: Für ein gutes Rückkopplungspolynom f(x) muss gelten:
  • Grad f = L
  • f(x) ist irreduzibel in (Z/2Z)
  • x ist ein Erzeuger der multiplikativen Gruppe (Z/f(x)Z)*

Lineare Komplexität

• Begrifflichkeiten
  • Betrachtung von binären Sequenzen
    • s = s₀s₁s₂... ist ein unendlicher Bitstrom
    • sⁿ = s₀s₁...s_n-1 ist ein endlicher Bitstrom der Länge n
• Lineare Komplexität L(s) einer Sequenz s
  • L(s) ist die Länge des kürzesten LFSRs, welches die Sequenz unendliche s durch irgend einen initialen Zustand erzeugt.
  • Gibt es kein solches LFSR, dann ist L(s) = ∞
  • Per Definition ist L(000...0) = 0.
  • Analog ist L(sⁿ) die Länge des kürzesten LFSRs, welches die endliche Sequenz sⁿ bei irgend einen initialen Zustand als erste n Bits erzeugt.
• Eigenschaften der linearen Komplexität
  • Wenn s periodisch ist mit Periodenlänge N, dann gilt L(s) ≤ N.
  • Für alle n ≥ 1 gilt 0 ≤ L(sⁿ) ≤ n
  • Wenn das Rückkopplungspolynom C(D) eines LFSRs irreduzibel ist in (Z/2Z) und Grad L hat, dann erzeugen alle von null verschiedenen initialen Zustände einen Ausgabestrom, welcher die lineare Komplexität L besitzt.
• Lineares Komplexitätsprofil
  • Betrachte, wie sich die lineare Komplexität einer unendlichen Sequenz s entwickelt, wenn nur die vordersten i Bits von s betrachtet werden, wobei i schrittweise erhöht wird.
  • Sei sⁱ die Sequenz der ersten i Bits von s, also sⁱ = s₀s₁...s_i-1. Die Folge L(s⁰)L(s¹)L(s²)... der linearen Komplexitäten der Sequenzen sⁱ für i ≥ 0 bilden das lineare Komplexitätsprofil.
  • Zur Vereinfachung verwenden wir ab sofort die Schreibweise L_i := L(sⁱ)
• Eigenschaften des lineares Komplexitätsprofils
  • Wenn i > j, dann gilt L_i ≥ L_j.
    • Lineare Komplexität ist monoton steigend.
  • L_i+1 > L_i ist nur genau dann möglich, wenn L_i ≤ i/2.
    • Im Graphen ist zu sehen, dass die lineare Komplexität nur zunimmt, wenn sie zuvor unterhalb der Geraden x/2 gewesen ist.
  • Wenn L_i+1 > L_i, dann gilt Lⁱ⁺¹ + L_i = i + 1.
    • Wenn die lineare Komplexität ansteigt, dann "springt" sie symmetrisch über die Gerade x/2.
• Bedeutung der linearen Komplexität
  • Eine folge hat eine "gute" lineare Komplexität (im Sinne der Pseudozufälligkeit), wenn die sie der Gerade x/2 einigermaßen gut folgt.
  • Mögliche verbale Beschreibung: Die Bitfolge ist so "zufällig" aufgebaut, dass man sie durch ein LFSR nicht einfacher beschreiben kann, als dem Zustandsspeicher weitere Bits hinzuzufügen und so den Zustandsraum zu vergrößern.
• Konstruktion eines LFSRs
  • Gegeben sei eine binäre Sequenz sⁿ = s₀s₁...s_n-1 der Länge n. Gesucht ist ein LFSR der minimalen Länge L = L(sⁿ), welches sⁿ erzeugt.
  • Idee: Konstruiere das LFSR iterativ, indem nach und nach LFSRs gesucht werden, welche die ersten 1, 2, 3, ..., n Bits von sⁿ erzeugen. Dabei bezeichne L_i und C_i(D) die Länge bzw. das Polynom des LFSRs der i-ten Iteration.
    • Beginne mit L₀ = 0, C₀(D) = 1
    • Wenn das aktuelle LFSR, welches sⁱ erzeugt hat, auch sⁱ⁺¹ erzeugt, dann gilt L(sⁱ) = L(sⁱ⁺¹)
    • Andernfalls muss die Länge L_i+1 evtl. erhöht werden, auf alle Fälle muss das Polynom C_i+1(D) angepasst werden:
      C_i+1(D) = C_i(D) + C_j(D)·D^i-j, wobei j die Iteration ist, bei der die Komplexität das letzte mal gestiegen war.
• Berlekamp-Massey-Algorithmus
  • Eingabe: binäre Sequenz sⁿ = s₀s₁...s_n-1 der Länge n
  • Ausgabe: Ein LFSR der minimalen Länge L = L(sⁿ), welches sⁿ erzeugt
  1. L := 0 // Aktuelle Länge des LFSRs
  2. C(D) := 1 // Akutelles Polynom
  3. i := 0 // Akutelle Iteration
  4. j := -1 // Iteration, bei zuletzt L(j-1) < L(j) war
  5. C'(D) := 1 // Polynom der Iteration j
  6. for i := 0 to n - 1 do
     1. delta := si + Σk=1L cksi-k mod 2
     2. if (delta = 1) then
        1. T(D) := C(D)
        2. C(D) := C(D) + C'(D)·Di-j
        3. if (L ≤ i/2) then // entspricht: (L < i + 1 - L)
           1. L := i + 1 - L
           2. j := i
           3. C'(D) := T(D)
  7. return (L, C(D))
  • Algorithmus hat Laufzeit O(n²)
• Erkenntnisse aus dem Berlekamp-Massey-Algorithmus
  • Wenn eine (unendliche) Bitsequenz die lineare Komplexität L hat, dann ein erzeugendes LFSR dafür gefunden werden, wenn 2L Bits der Folge beobachtet wurden.
  • Intuition dahinter:
    • Wenn L Bits der Folge beobachtet wurden, so erhält man den Zustand, in den sich das LFSR zuvor befunden hatte
    • Die nächsten L + 1 bis 2L Bits entstehen durch eine rekursive Funktion aus den vorangegangenen L Bits im Schieberegister.
    • Somit kann ein LGS aufgestellt werden, um die Koeffizienten c₀, c₁, ..., c_L-1 des Polynoms zu bestimmen:
      Σ_i=0^L-1 c_is_i - s_L = 0
      Σ_i=0^L-1 c_is_i+1 - s_L+1 = 0
      ...
      Σ_i=0^L-1 c_is_i+L-1 - s_2L-1 = 0
    • Man erhält ein LGS aus L Gleichungen mit L Unbekannten, welches gelöst werden kann.
• Weiteres mögliches Komplexitätsmaß: Turing-Kolmogorov-Chaitin-Komplexität
  • TKC-Komplexität ist die Länge des kürzesten Turing-Programms, welches eine Sequenz sⁿ als Ausgabe produzieren kann.
  • Dieses Komplexitätsmaß soll leicht berechenbare Pseudo-Zufälligkeit aufdecken
  • Praktisch kaum verwendbar, da kein effizientes Verfahren bekannt ist, um TKC-Komplexität zu berechnen (genauer: die TKC-Komplexität ist nicht berechenbar).

Statistische Eigenschaften

• Die lineare Komplexität alleine ist kein gutes Maß für die "Zufälligkeit" einer Sequenz.
  • Bsp.: Für sⁿ = 000...01 ist L(sⁿ) = n, die Folge ist aber keineswegs zufällig.
• Deshalb Durchführen von statistischen Tests, um die Verteilung der Nullen und Einsen in der Sequenz zu überprüfen
  • Diese Tests sind nur ein Ausschlusskriterium für schlechte Sequenzen und garantieren noch keine gute Sequenz (notwendige aber nicht hinreichende Bedingungen)!
• Es gibt viel statistische Tests für Zufallszahlenfolgen, hier werden nur die Golomb-Kriterien vorgestellt
• Im folgenden betrachten wir periodische Sequenzen s = s₀s₁s₂... mit Periodenlänge n.
• Definitionen
  • Ein Run ist ein Abschnitt von Nullen oder Einsen der Sequenz, der keine Nullen bzw. Einsen mehr voran oder hinterher gehen (maximal mögliche Länge)
  • Ein Run aus Nullen wird Lücke genannt.
  • Ein Run aus Einsen wird Block genannt.
• Korrelation
  • Untersuche den Zusammenhang zwischen der Sequenz s und der um t Bits verschobenen Sequenz s' = s_ts_t+1s_t+2..., 0 ≤ t < n
  • Die Anzahl der Übereinstimmungen zwischen s und s' wird mit A(t) bezeichnet:
    A(t) = Σ_i=0^n-1 1 - (s_i ⊕ s_i+t)
  • Die Anzahl der Nicht-Übereinstimmungen zwischen s und s' wird mit D(t) bezeichnet:
    D(t) = n - A(t)
  • Die Autokorrelationsfunktion C(t) ist wie folgt definiert:
    C(t) = (A(t) - D(t)) / n
  • Wenn s eine Zufallsfolge ist, dann wird erwartet, dass die Anzahl der Übereinstimmungen und der Nicht-Übereinstimmungen nahezu gleich ist, so dass C(t) für 0 < t < n null oder zumindest sehr klein ist.
• Golomb-Kriterien für periodische Zufallsfolgen s mit Periodenlänge n
  1. In jedem Zyklus der Folge s unterscheidet sich die Anzahl der Nullen von der Anzahl der Einsen höchstens um eins.
  2. In jedem Zyklus der Folge s haben mindestens 1/2ⁱ aller Runs die Länge i (solange es zwei oder mehr Runs dieser Länge gibt). Für jede dieser Längen i ist die Anzahl der Lücken und der Blöcke fast gleich.
  3. Die Autokorrelationsfunktion C(t) ist konstant für 1 ≤ t < n.
  • Genügt eine Sequenz den Golomb-Kriterien, so wird sie als Pseudo-Rauschen (pseudo-noise, PN) bezeichnet.
• Statistische Eigenschaften von LFSR-erzeugten Folgen
  • Erinnerung:
    • Ein primitives Polynom ist ein irreduzibles Polynom, dessen multiplikative Gruppe vom Gruppenelement x erzeugt wird.
    • Ein LFSR maximaler Länge ist ein LFSR der Länge L, welches ein primitives Rückkopplungspolynom vom Grad L hat.
  • Der Ausgabestrom eines LFSRs maximaler Länge erfüllt die Golomb-Kriterien, ist also ein PN-Folge.
  • Die Verteilung der Bitmuster fester Länge in einem solchen Ausgabestrom ist nahezu uniform.
    • D. h. die Verteilung aller Kombinationen von einzelnen Bits, Bitpaaren, -trippel, usw. in jeder Teilfolge kommt nahezu gleich oft vor.

Komposition von Stromchiffren

• LFSRs in Kryptosystemen
  • Vorteile:
    • Einfaches Konzept
    • leicht in Hardware zu implementieren, besonders in eingebetteten Systemen
    • Schnelle Berechnung
  • Nachteile:
    • Durch lineares Verhalten sehr einfach für Kryptoanalyse (Known-Plaintext der Länge 2L genügt)
  • Anforderungen an ein LFSR
    1. lange Periode
    2. hohe lineare Komplexität
    3. gute statistische Eigenschaften
• Komposition von Kryptosystemen aus LFSRs
  • Es gibt mehrere Möglichkeiten, die Linearität von LFSR zu zerstören:
    1. Verknüpfung der Ausgaben mehrerer LFSR über eine nicht-linearen Funktion (nicht-lineare Kombination)
    2. Eine nicht-lineare Filterfunktion auf die Ausgabe eines LFSRs anwenden
    3. Verwende die Ausgabe eines LFSRs als Taktgeber für ein oder mehrerer andere LFSR
  • Dabei werden folgende Anforderungen an ein auf LFSR basierendes Kryptosystem gestellt:
    1. Eine möglichst lange Periode
    2. Eine möglichst hohe lineare Komplexität
    3. Gute statistische Eigenschaften
    4. Erfüllung all dieser Eigenschaften für alle möglichen geheimen Schlüssel
• Geheimer Schlüssel und Rückkopplungspolynom
  • Das Rückkopplungspolynom eines LFSR-basierten Kryptosystems kann entweder geheim oder öffentlich sein.
    • Geheimes Polynom
      • Polynom ist Teil des geheimen Schlüssels
      • Wird i. A. zufällig und gleichverteilt aus der Menge aller primitiven Polynome mit Grad L gewählt
    • Öffentliches Polynom
      • Polynom ist im Kryptosystem festgelegt
      • Der geheime Schlüssel besteht i. d. R. aus dem initialen Zustand des/der LFSR.
      • Anfälliger gegen bestimmte statistische Analysen
      • Kryptoanalyse wird durch mögliche Vorberechnungen erleichtert

Nicht-lineare Kombinationen

• Man verwendet mehrere LFSR parallel, deren Ausgänge über eine nicht-lineare Funktion verknüpft werden. Der Ausgang dieser Funktion bilden den Schlüsselstrom.
• Es kann gezeigt werden:
  • Gegeben sind n LFSR maximaler Periodenlänge mit paarweise verschiedenen Längen L₁, L₂, ..., L_n. Ihre Ausgänge sind über eine nicht-lineare Funktion f(x₁, x₂, ..., x_n) verknüpft. Dann beträgt die lineare Komplexität des Ausgabestroms von f genau f(L₁, L₂, ..., L_n) in Z (nicht in Z/2Z)
• Beispiel: Geffe-Generator
  • f(x₁, x₂, x₃) = x₁x₂ ⊕ x₂x₃ ⊕ x₃ hat die lineare Komplexität L₁L₂ + L₂L₃ + L₃
  • Ist anfällig für Korrelationsattacken, soll aber nicht weiter vertieft werden.
• Beispiel: Summationsgenerator
  • Es werden n verschiedene LFSR verwendet, deren Längen L₁, L₂, ..., L_n zueinander paarweise prim sind.
  • Generator hat zusätzlich einen Speicher für einen Carry C ∈ Z.
  • Der Schlüssel besteht dann aus den n initialen Zuständen sowie der Anfangsbelegung C₀ des Carrys.
  • Der Generator durchläuft immer folgenden Zyklus. z_i ist das i-te Ausgabebit, C_i ist der Carry in der i-ten Iteration:
    1. Die LFSR werden einen Takt weitergeschaltet.
    2. In Iteration i werden die Ausgabebits x₁, ... x_n zusammen mit dem vorherigen Carry zur Summe S_i in Z aufaddiert:
       S_i = x₁ + x₂ + ... + x_n + C_i-1, S_i ∈ Z
    3. Es wird z_i = S_i mod 2 berechnet.
    4. Es wird C_i = floor(S_i / 2) berechnet ("floor()" rundet auf die nächst kleinere ganze Zahl ab.
  • Die Periode des Ausgabestroms beträgt Π_i=1ⁿ (2^L_i - 1)
  • Die lineare Komplexität ist nahezu genauso groß

Nicht-lineare Filterfunktionen

• Hier wird ein einzelnes LFSR verwendet. Die Bits aller L Register werden in einer nicht-linearen Funktion f(x₁, x₂, ..., x_L) kombiniert.
• Sei m die nicht-lineare Ordnung von f. Das ist die maximale Anzahl Terme, die in f miteinander multipliziert werden.
• Die maximale lineare Komplexität eines solchen Systems ist L_m = Σ_i=1^m (L über i) < 2^L.

Taktgesteuerte Kombinationen von LFSR

• Idee: Ein LFSR steuert durch seine Ausgabesequenz den Takt von anderen LFSR. Damit ist der lineare Zusammenhang zwischen Zustand eines LFSRs und der Ausgabesequenz zerstört.
• Beispiel: Alternating-Step-Generator
  • Drei LFSR R₁, R₂, R₃ maximaler Länge, deren Längen L₁, L₂ und L₃ paarweise teilerfremd sind.
  1. R₁ wird regulär getaktet und steuert den Takt von R₂ und R₃:
     • Wenn das Ausgabebit von R₁ null ist, dann wird R₂ einmal getaktet.
     • Wenn das Ausgabebit von R₁ eins ist, dann wird R₃ einmal getaktet.
  2. Die Ausgaben von R₂ und R₃ werden mit XOR verknüpft und bildet den Schlüsselstrom.
  • Der Schlüsselstrom s des Alterning-Step-Generator hat
    • eine Periode von 2^L₁-1 · (2^L₂ - 1) · (2^L₂ - 1)
    • eine lineare Komplexität L(s) von (L₂ + L₃) · 2^L₁-1 < L(s) ≤ (L₂ + L₃) · 2^L₁.
    • eine fast uniforme Verteilung von Bitmustern der gleichen Länge.
• Beispiel: Shrinking-Generator
  • Zwei LFSR R₁, R₂ maximaler Länge, deren Längen L₁ und L₂ teilerfremd sind.
  1. Beide LFSR werden gleich getaktet.
  2. Wenn das Ausgabebit von R₁ eins ist, dann wird das aktuelle Ausgabebit von R₂ als Zeichen für den Schlüsselstrom verwendet.
  3. Wenn das Ausgabebit von R₁ null ist, dann wird das aktuelle Ausgabebit von R₂ verworfen.
  • Muss ca. 2n mal iteriert werden, um einen Schlüsselstrom der Länge n zu erzeugen, da nur etwa die Hälfte der Bits von R₂ verwendet wird.
  • Der Schlüsselstrom s des Shrinking-Generators hat
    • eine Periodenlänge von (2^L₂ - 1) · 2^L₁-1
    • eine lineare Komplexität L(s) von L₂ · 2^L₁-2 < L(s) ≤ L₂ · 2^L₁-1.
    • eine fast uniforme Verteilung von Bitmustern der gleichen Länge.

Algorithmen basierend auf LFSR

A5 (GSM)

E0 (Bluetooth)