Kryptologie IV.4 Perfekte Zufallsgeneratoren

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

Anfang der 80-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. 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 ersten konkreten Ansätze, von denen hier bald einer behandelt wird, lieferten Generatoren, die für den praktischen Einsatz noch viel zu langsam waren. Es werden auch verschiedene neuere Ansätze vorgestellt, zu schnellen kryptographisch sicheren Zufallsgeneratoren zu kommen.

1. Das JACOBI-Symbol.
2. Das quadratische Reziprozitätsgesetz.
3. BLUM-Zahlen.
4. Der BLUM-BLUM-SHUB-Generator.
5. BBS-Generator und Quadratrest-Eigenschaft.
6. Perfekte Zufallsgeneratoren.
7. Beispiele und praktische Überlegungen.
8. Der MICALI-SCHNORR-Generator.
9. Der IMPAGLIAZZO-NAOR-Generator.

E-Mail an Pommerening@imsd.uni-mainz.de.