Blum-Micali-Generator

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Der Blum-Micali-Generator ist ein von Manuel Blum und Silvio Micali entwickelter kryptographisch sicherer Zufallszahlengenerator.[1]

Prinzip[Bearbeiten]

Der Generator basiert auf einer generischen Konstruktion von Blum und Micali, die eine Einwegpermutation f: M \to M und ein Hardcoreprädikat B für f benötigt. Ein Hardcoreprädikat ist eine Funktion B: M \to \{0,1\} mit der Eigenschaft, dass es praktisch unmöglich ist, aus f(x) das Bit B(x) zu berechnen. Aus einem zufälligen Startwert x_0 \in M wird zuerst durch die Vorschrift x_{i+1} = f(x_i) eine Folge abgeleitet. Die Folge der zufälligen Bits ist dann die Folge B(x_i).

Konstruktion[Bearbeiten]

Bei der konkreten Konstruktion wird als Einwegpermutation die diskrete Exponentiation genutzt. Als Parameter wird zuerst eine Primzahl p gewählt, die eine zyklische Gruppe \mathbb{Z}_p^* festlegt. Aus dieser multiplikativen Gruppe wird ein zufälliges Element g gewählt, das auch gleichzeitig ein Generator ist (da die Wahrscheinlichkeit, dass die 1 gewählt wird, vernachlässigbar klein ist). Die Funktion f ist nun die diskrete Exponentiation f(x) = g^x\ \bmod{\ p}. Sie ist eine Permutation, da sowohl x als auch g^x in \mathbb{Z}_p^* liegen und g ein Generator ist.

Ausgehend von einem zufälligen x_0 wird nun wie oben beschrieben mittels f eine Folge x_{i+1} = f(x_i) = g^{x_i}\ \bmod{\ p} definiert. Das benötigte Hardcoreprädikat für f ist die Funktion B(x), die 1 ausgibt, falls x < \frac{p-1}{2}, und 0 sonst. Die vom Generator erzeugte pseudozufällige Bitfolge ist also B(x_i).

Sicherheit[Bearbeiten]

Das Verfahren ist beweisbar sicher unter der Annahme, dass es schwierig ist, diskrete Logarithmen zu berechnen. Wenn ein Algorithmus ein Bit B(x_i) dieser Folge mit Wahrscheinlichkeit besser als 1/2 vorhersagen kann, so kann daraus ein Algorithmus konstruiert werden, der in der Gruppe \mathbb{Z}_p^* in probabilistischer Polynomialzeit diskrete Logarithmen berechnen kann.

Einzelnachweise[Bearbeiten]

  1.  Manuel Blum and Silvio Micali: How to Generate Cryptographically Strong Sequences of Pseudorandom Bits. In: SIAM Journal on Computing. 13, Nr. 4, 1984, S. 850–864 (http://www.csee.wvu.edu/~xinl/library/papers/comp/Blum_FOCS1982.pdf).

Weblinks[Bearbeiten]