Blum-Micali-Generator

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

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\ \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₀ 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.

Einzelnachweise

1. ↑ Manuel Blum and Silvio Micali: How to Generate Cryptographically Strong Sequences of Pseudorandom Bits. In: SIAM Journal on Computing. 13, Nr. 4, 1984, S. 850–864 (http://www.csee.wvu.edu/~xinl/library/papers/comp/Blum_FOCS1982.pdf).

Weblinks

• http://crypto.stanford.edu/pbc/notes/crypto/blummicali.xhtml