Blum-Micali-Generator

Der Blum-Micali-Generator i​st ein v​on Manuel Blum u​nd Silvio Micali entwickelter kryptographisch sicherer Zufallszahlengenerator.[1]

Prinzip

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

Konstruktion

Bei der konkreten Konstruktion wird als Einwegpermutation die diskrete Exponentiation genutzt. Als Parameter wird zuerst eine Primzahl ${\displaystyle p}$ gewählt, die eine zyklische Gruppe ${\displaystyle \mathbb {Z} _{p}^{*}}$ festlegt. Aus dieser multiplikativen Gruppe wird ein zufälliges Element ${\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}$ ist nun die diskrete Exponentiation ${\displaystyle f(x)=g^{x}\ {\bmod {\ p}}}$. Sie ist eine Permutation, da sowohl ${\displaystyle x}$ als auch ${\displaystyle g^{x}}$ in ${\displaystyle \mathbb {Z} _{p}^{*}}$ liegen und ${\displaystyle g}$ ein Generator ist.

Ausgehend von einem zufälligen ${\displaystyle x_{0}}$ wird nun wie oben beschrieben mittels ${\displaystyle f}$ eine Folge ${\displaystyle x_{i+1}=f(x_{i})=g^{x_{i}}\ {\bmod {\ p}}}$ definiert. Das benötigte Hardcoreprädikat für ${\displaystyle f}$ ist die Funktion ${\displaystyle B(x)}$, die 1 ausgibt, falls ${\displaystyle x<{\frac {p-1}{2}}}$, und 0 sonst. Die vom Generator erzeugte pseudozufällige Bitfolge ist also ${\displaystyle 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 ${\displaystyle B(x_{i})}$ dieser Folge mit Wahrscheinlichkeit besser als ${\displaystyle 1/2}$ vorhersagen kann, so kann daraus ein Algorithmus konstruiert werden, der in der Gruppe ${\displaystyle \mathbb {Z} _{p}^{*}}$ in probabilistischer Polynomialzeit diskrete Logarithmen berechnen kann.

Einzelnachweise

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]).

Weblinks

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