Kryptologie IV.4 Perfekte Zufallsgeneratoren

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Anfang der 1980-er Jahre entstand im Umkreis der Kryptologie eine Vorstellung davon, wie man die Unvorhersagbarkeit eines Zufallsgenerators modellieren könnte, nämlich komplexitätstheoretisch: Die Vorhersage soll hart sein, d. h., auf ein bekanntes hartes Problem zurückgeführt werden können. Dadurch wurde ein neuer Qualitätsstandard gesetzt, der allerdings auf der mathematisch völlig unbewiesenen Grundlage aufbaut, dass es für gewisse zahlentheoretische Probleme wie die Primzerlegung keine effizienten Algorithmen gibt. -- Die Situation ist also die gleiche wie bei der asymmetrischen Verschlüsselung.

Interessanterweise stellte sich bald heraus, dass die scheinbar viel stärkere Forderung, die erzeugte Zufallsfolge solle sich durch keinen effizienten Algorithmus von einer echten Zufallsfolge unterscheiden lassen, zur Unvorhersagbarkeit äquivalent ist (Satz von YAO). Auf der theoretischen Seite ist damit ein sehr gutes Modell für Zufallsgeneratoren vorhanden, die statistisch absolut einwandfrei und kryptologisch unangreifbar sind.

Die ersten konkreten Ansätze, von denen hier der BBS- (= BLUM/BLUM/SHUB-) Generator behandelt wird, lieferten Generatoren, die für den praktischen Einsatz noch viel zu langsam waren. Es werden auch verschiedene neuere Ansätze vorgestellt, zu einigermaßen schnellen kryptographisch sicheren Zufallsgeneratoren zu kommen.

1. Der BLUM-BLUM-SHUB-Generator [PDF]
   Mathematica-Programm als Text und als Notebook.
2. BBS-Generator und Quadratrest-Eigenschaft [PDF].
3. Perfekte Zufallsgeneratoren [PDF].
4. Beispiele und praktische Überlegungen [PDF].
5. Der MICALI-SCHNORR-Generator [PDF].
6. Der IMPAGLIAZZO-NAOR-Generator [PDF].

Und den ganzen Abschnitt am Stück als PDF-Datei.