Blum-Micali-Generator
Der Blum-Micali-Generator ist ein von Manuel Blum und Silvio Micali entwickelter kryptographisch sicherer Zufallszahlengenerator.<ref name="BM84" />
Prinzip
Der Generator basiert auf einer generischen Konstruktion von Blum und Micali, die eine Einwegpermutation <math>f \colon M \to M</math> und ein Hardcoreprädikat <math>B</math> für <math>f</math> benötigt. Ein Hardcoreprädikat ist eine Funktion <math>B \colon M \to \{0,1\}</math> mit der Eigenschaft, dass es praktisch unmöglich ist, aus <math>f(x)</math> das Bit <math>B(x)</math> zu berechnen. Aus einem zufälligen Startwert <math>x_0 \in M</math> wird zuerst durch die Vorschrift <math>x_{i+1} = f(x_i)</math> eine Folge abgeleitet. Die Folge der zufälligen Bits ist dann die Folge <math>B(x_i)</math>.
Konstruktion
Bei der konkreten Konstruktion wird als Einwegpermutation die diskrete Exponentiation genutzt. Als Parameter wird zuerst eine Primzahl <math>p</math> gewählt, die eine zyklische Gruppe <math>\mathbb{Z}_p^*</math> festlegt. Aus dieser multiplikativen Gruppe wird ein zufälliges Element <math>g</math> gewählt, das auch gleichzeitig ein Generator ist (da die Wahrscheinlichkeit, dass die 1 gewählt wird, vernachlässigbar klein ist). Die Funktion <math>f</math> ist nun die diskrete Exponentiation <math>f(x) = g^x\ \bmod{\ p}</math>. Sie ist eine Permutation, da sowohl <math>x</math> als auch <math>g^x</math> in <math>\mathbb{Z}_p^*</math> liegen und <math>g</math> ein Generator ist.
Ausgehend von einem zufälligen <math>x_0</math> wird nun wie oben beschrieben mittels <math>f</math> eine Folge <math>x_{i+1} = f(x_i) = g^{x_i}\ \bmod{\ p}</math> definiert. Das benötigte Hardcoreprädikat für <math>f</math> ist die Funktion <math>B(x)</math>, die 1 ausgibt, falls <math>x < \frac{p-1}{2}</math>, und 0 sonst. Die vom Generator erzeugte pseudozufällige Bitfolge ist also <math>B(x_i)</math>.
Sicherheit
Das Verfahren ist beweisbar sicher unter der Annahme, dass es schwierig ist, diskrete Logarithmen zu berechnen. Wenn ein Algorithmus ein Bit <math>B(x_i)</math> dieser Folge mit Wahrscheinlichkeit besser als <math>1/2</math> vorhersagen kann, so kann daraus ein Algorithmus konstruiert werden, der in der Gruppe <math>\mathbb{Z}_p^*</math> in probabilistischer Polynomialzeit diskrete Logarithmen berechnen kann.
Einzelnachweise
<references> <ref name="BM84">{{#invoke:Vorlage:Literatur|f}}</ref> </references>