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\colon M\to M$ und ein Hardcoreprädikat $B$ für $f$ benötigt. Ein Hardcoreprädikat ist eine Funktion $B\colon 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}\ {\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

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