Zufallsbits

Echte Zufallsbits lassen sich nur durch physikalische Prozesse (Münzwurf, radioaktiver Zerfall, thermisches Rauschen) erzeugen. Mithilfe mathe­matischer Methoden lassen sich jedoch Pseudo­zufalls­bits gewinnen, die ähnliche Eigen­schaften wie echte Zufallsbits haben.

Pseudozufallsbits

Zur Erzeugung einer pseudo­zufälligen Bitfolge eignen sich linear rück­gekoppelte Schiebe­register (Linear Feedback Shift Register – LFSR). Das folgende Bild zeigt ein linear rück­gekoppeltes Schiebe­register mit n = 4 Stellen; diese seien mit r₁, r₂, r₃, r₄ ∈ {0, 1} vorbesetzt. Diese Werte werden mit konstanten Werten a₁, a₂, a₃, a₄ ∈ {0, 1} multi­pliziert (logisches Und) und anschließend modulo 2 addiert (logisches Exklusiv-Oder). Das Ergebnis wird im nächsten Takt an die Stelle von r₁ übernommen; die vorherigen Werte werden alle um eine Stelle nach links weiter­geschoben, r₄ wird ausgegeben (Bild 1).

Wird das Schiebe­register mit r₁ = 1 initialisiert, so durchläuft es nacheinander die 15 Belegungen

Die Ausgabefolge 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 ist die gewünschte Pseudo­zufalls­folge.

Das charakteristische Polynom des linear rück­gekoppelten Schiebe­registers aus obigem Beispiel ist  p  =  x⁴ ⊕ x ⊕ 1; es ist primitiv, da das Schiebe­registers alle 2⁴-1 = 15 möglichen Zustände annimmt.

Pseudozufallsbits und Kryptografie

Es liegt nahe, Pseudo­zufalls­bits anstelle echter Zufallsbits zur Ver­schlüsselung von binär codierten Nachrichten zu verwenden (One-Time-Pad). Hierbei ergibt sich der Geheimtext c = c₁ ... c_k als bitweise Summe modulo 2 (Exklusiv-Oder) aus dem Klartext m = m₁ ... m_k und der Zufallsfolge r = r₁ ... r_k :

c_i  =  m_i ⊕ r_i     für i = 1, ..., k

Besteht die Folge r aus echten Zufallsbits, so ist die Ver­schlüsselung absolut sicher. Besteht die Folge r dagegen aus Pseudo­zufalls­bits, die von einem linear rück­gekoppelten Schiebe­register der Länge n erzeugt wurden, so ist die Ver­schlüsselung absolut unsicher. Bereits die Kenntnis von 2n beliebigen aufeinander­folgenden Bits reicht aus, um die Konstanten a₁, ..., a_n des linear rück­gekoppelten Schiebe­registers und damit die gesamte Pseudo­zufalls­folge zu bestimmen. Die 2n Pseudo­zufalls­bits lassen sich bestimmen, wenn 2n aufeinander­folgende Klartextbits zusammen mit den zugehörigen Geheimtext­bits bekannt sind (known plaintext attack) oder aufgrund eines im Klartext wahr­scheinlich vorkommenden Wortes erraten werden können.

Zur Bestimmung der Konstanten des linear rück­gekoppelten Schiebe­registers müssen lediglich n Gleichungen mit den n Unbekannten a₁, ..., a_n aufgelöst werden.

Anschließend ist das Schiebe­register mit r₄, ..., r₇ belegt, wobei für das rechts herein­geschobene r₄ gilt:

a₄·r₈ ⊕ a₃·r₇ ⊕ a₂·r₆ ⊕ a₁·r₅  =  r₄

Aus den Belegungen des Schiebe­registers in den nächsten drei Takten ergeben sich als weitere Gleichungen:

a₄·r₇ ⊕ a₃·r₆ ⊕ a₂·r₅ ⊕ a₁·r₄  =  r₃

a₄·r₆ ⊕ a₃·r₅ ⊕ a₂·r₄ ⊕ a₁·r₃  =  r₂

a₄·r₅ ⊕ a₃·r₄ ⊕ a₂·r₃ ⊕ a₁·r₂  =  r₁

Aus diesen 4 Gleichungen lassen sich die 4 Unbekannten a₁, ..., a₄ berechnen.

Sind die Konstanten des linear rück­gekoppelten Schiebe­registers ermittelt, lässt sich die Folge aller folgenden und, durch ent­sprechendes Zurück­rechnen, aller vorherigen Pseudo­zufalls­bits bestimmen und damit der gesamte Geheimtext ent­schlüsseln. Für krypto­grafische Anwendungen sind also durch linear rück­gekoppelte Schiebe­register erzeugte Pseudo­zufalls­bits absolut ungeeignet. In der Kryptografie werden krypto­grafisch sichere Zufallsbits benötigt, die auf andere Art und Weise erzeugt werden.

Literatur

[Wel 88]   D. Welsh: Codes and Cryptography. Oxford University Press (1988)

[PP 16]   C. Paar, J. Pelzl: Kryptografie verständlich. Springer Vieweg (2016)

[Lan 18]   H.W. Lang: Kryptografie für Dummies. Wiley (2018)

[Weitere Informationen]