2A02:810D:93C0:A00:DDE2:15D5:87B3:55C1: /* Weblinks */

2018-07-21T15:04:58Z

Weblinks

Neue Seite

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 [[Einwegfunktion|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 [[Erzeuger (Algebra)|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 [[Beweisbare Sicherheit|beweisbar sicher]] unter der Annahme, dass es schwierig ist, [[Diskreter Logarithmus|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 [[Probabilistische Polynomialzeit|probabilistischer Polynomialzeit]] diskrete Logarithmen berechnen kann.

== Einzelnachweise ==
<references>
<ref name="BM84">{{Literatur
| Autor=Manuel Blum and Silvio Micali
| Titel=How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
| Sammelwerk= SIAM Journal on Computing
| Band=13
| Nummer=4
| Jahr=1984
| Seiten=850–864
| Online=https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Pseudo%20Randomness/How_To_Generate_Cryptographically_Strong_Sequences_Of_Pseudo-Random_Bits.pdf
}}</ref>
</references>

== Weblinks ==
*https://crypto.stanford.edu/pbc/notes/crypto/blummicali.html

[[Kategorie:Kryptologisches Verfahren]]
[[Kategorie:Pseudozufallszahlengenerator]]

Blum-Micali-Generator - Versionsgeschichte

2A02:810D:93C0:A00:DDE2:15D5:87B3:55C1: /* Weblinks */