Algorithmisch kann man nur deterministische Folgen erzeugen. Dennoch lässt sich der Zufall algorithmisch approximieren.

Pseudozufallsfolgen (-zahlen, -bits) sind algorithmisch erzeugte Folgen (Zahlen, Bits), die sich von zufälligen Folgen (Zahlen, Bits) nach bestimmten Kriterien nicht unterscheiden lassen.

Ein Algorithmus, der Pseudozufallsfolgen (-zahlen, -bits) erzeugt, heißt Zufallsgenerator.

1. Bei den »klassischen« Zufallsgeneratoren verlangt man, dass sie übliche statistische Tests bestehen. Beispiele:
   • lineare Kongruenz-Generatoren,
   • lineare Schieberegister.
2. Bei den »perfekten« Zufallsgeneratoren verlangt man, dass sich ihr Output durch keinen effizienten Algorithmus von echtem Zufall unterscheiden lässt. Beispiele:
   • der Blum-Blum-Shub-Generator (BBS),
   • der Micali-Schnorr-Generator,
   • der Rucksack-Generator,
   • Yarrow von Bruce Schneier und John Kelsey.

Lineare Kongruenz-Generatoren

Verfahren

Eine Folge (x_i) von Zufallszahlen im ganzzahligen Intervall [0 .. m-1] wird durch folgende Iterationsformel erzeugt:

x_i = a * x_i-1 + b mod m

Eigenschaften

Bei geschickter Wahl der Parameter hat die Folge eine Periode » m und ist durch statistische Tests praktisch nicht von einer gleichverteilten Zufallsfolge zu unterscheiden.

Mit zahlentheoretischen Methoden ist aber leicht eine Kryptoanalyse möglich: Aus einem kurzen bekannten Stück der Folge lässt sich der weitere Folgenverlauf vorhersagen, auch wenn die Parameter sämtlich unbekannt sind. Ein Programm dazu gibt's hier.

===> Diese Zufallszahlen sind kryptographisch nicht sicher!

Lineare Schieberegister

Verfahren

Eine Folge (u_i) von Zufallsbits wird durch folgende Iterationsformel erzeugt:

Eigenschaften

Bei geschickter Wahl der Parameter hat die Folge eine Periode » 2^l und ist durch statistische Tests praktisch nicht von einer gleichverteilten Zufallsfolge zu unterscheiden.

Mit linearer Algebra über dem endlichen Körper F₂ ist aber leicht eine Kryptoanalyse möglich: Aus einem kurzen bekannten Stück der Folge lässt sich der weitere Folgenverlauf vorhersagen, auch wenn die Parameter sämtlich unbekannt sind.

===> Diese Zufallsbits sind kryptographisch nicht sicher!

Kryptographische Sicherheit

Nach einem Satz von YAO sind folgende Eigenschaften eines Zufallsgenerators äquivalent:

1. Unvorhersagbarkeit: Aus einem Stück der Output-Folge lässt sich kein weiteres Bit der Folge effizient berechnen.
2. Perfektheit: Es gibt kein effizientes Verfahren, das die Output-Folge von einer Zufallsfolge unterscheiden kann. Insbesondere besteht die Folge jeden effizienten statistischen Test.

Solche Zufallsgeneratoren werden kryptographisch sicher genannt; sie sind also geeignet, um eine sichere Bitstrom-Verschlüsselung durchzuführen. Leider ist ihre Existenz unbewiesen - sie hängt vom ungelösten Grundproblem der Komplexitätstheorie ab: Wie beweist man, dass ein Problem nicht effizient lösbar ist?

Mathematische Behandlung im Kapitel Perfekte Zufallsgeneratoren der Kryptologie-Vorlesung.

Im folgenden werden drei Zufallsgeneratoren vorgestellt, die vermutlich perfekt sind - unter der Annahme, dass bestimmte zahlentheoretische Probleme nicht effizient lösbar sind.

Der BBS-Generator

[L. Blum, M. Blum, M. Shub]

Eine Blum-Zahl m ist (wie beim RSA-Verfahren) ein Produkt zweier (großer) Primzahlen p und q, wobei hier noch p und q kongruent 3 mod 4 sein sollen.

Verfahren

Eine Folge (u_i) von Zufallsbits wird durch folgende Iterationsformel erzeugt:

x_i = x_i-1² mod m;
ausgegeben wird aber nur das letzte Bit b_i = x_i mod 2.

Eigenschaften

• Wenn der BBS-Generator nicht perfekt ist, lässt sich effizient entscheiden, ob eine ganze Zahl mod m Quadratrest ist. Dies ist (für zusammengesetzte Moduln) aber vermutlich ein hartes Problem (»Quadratrest-Vermutung«).
• Wenn sich der Modul m faktorisieren lässt, ist die Quadratrest-Vermutung falsch; ob die Umkehrung gilt, ist nicht bekannt.
• Ein effizientes Vorhersageverfahren für den BBS-Generator führt zur Faktorisierung des Moduls.
• Also: BBS unsicher ===> Modul effizient faktorisierbar ===> QR-Eigenschaft effizient entscheidbar.
• Der BBS-Generator ist extrem langsam.

Der Micali-Schnorr-Generator

Der Rucksack-Generator (Impagliazzo/Naor)

Der Rucksack-Generator ist perfekt, wenn das »Rucksack-Problem« (Knapsack Problem, Subset Sum Problem) nicht effizient lösbar ist. Dieses ist NP-vollständig.