Blum-Micali-Generator

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

Prinzip

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

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}modp$. 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}modp$ 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

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.

Weblinks

• https://crypto.stanford.edu/pbc/notes/crypto/blummicali.html