Blum-Micali-Generator

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

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

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

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

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

1. ↑ Manuel Blum and Silvio Micali: How to Generate Cryptographically Strong Sequences of Pseudorandom Bits. In: SIAM Journal on Computing. Band 13, Nr. 4, 1984, S. 850–864 (mit.edu [PDF]). 

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

• Kryptologisches Verfahren
• Pseudozufallszahlengenerator