Blum-Micali-Generator

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

Inhaltsverzeichnis

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 xi + 1 = f(xi) eine Folge abgeleitet. Die Folge der zufälligen Bits ist dann die Folge B(xi).

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 gx in \mathbb{Z}_p^* liegen und g ein Generator ist.

Ausgehend von einem zufälligen x0 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(xi).

Sicherheit

Das Verfahren ist beweisbar sicher unter der Annahme, dass es schwierig ist, diskrete Logarithmen zu berechnen. Wenn ein Algorithmus ein Bit B(xi) 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


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Blum-Micali algorithm — The Blum Micali algorithm is used as a pseudo random generator in cryptography. The algorithm gets its security from the difficulty of computing discrete logarithms.Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C …   Wikipedia

  • Blum — steht für: Blum (Familienname), siehe dort zu Namensträgern Blum (Texas), Stadt in den USA Julius Blum (Unternehmen), Julius Blum GmbH, ein Beschlägehersteller in Vorarlberg Siehe auch: Blum Micali Generator, kryptographisch sicherer… …   Deutsch Wikipedia

  • Blum-Goldwasser cryptosystem — The Blum Goldwasser (BG) cryptosystem is an asymmetric key encryption algorithm proposed by Manuel Blum and Shafi Goldwasser in 1984. Blum Goldwasser is a probabilistic, semantically secure cryptosystem with a constant size ciphertext expansion.… …   Wikipedia

  • Cryptographically secure pseudorandom number generator — A cryptographically secure pseudo random number generator (CSPRNG) is a pseudo random number generator (PRNG) with properties that make it suitable for use in cryptography. Many aspects of cryptography require random numbers, for example: Key… …   Wikipedia

  • Manuel Blum — (* 26. April 1938 in Caracas, Venezuela) ist ein venezolanischer Informatiker, der 1995 „in Anerkennung seiner Beiträge zu den Grundlagen der algorithmischen Komplexitätstheorie sowie deren Anwendung in der Kryptographie und der Fehlerüberprüfung …   Deutsch Wikipedia

  • Manuel Blum — Born April 26, 1938 (1938 04 26) (age 73) Caracas, Venezuela Residence Pittsburgh …   Wikipedia

  • Pseudorandom number generator — A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG),[1] is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. The sequence is not truly random in… …   Wikipedia

  • Pseudorandom generator theorem — In computational complexity a distribution is considered pseudorandom if no efficient computation can distinguish it from the true uniform distribution by a non negligible advantage. Formally, a family of distributions Dn is pseudorandom if for… …   Wikipedia

  • Schlüsselstromgenerator — Ein Schlüsselstromgenerator ist der Kernbestandteil einer Stromverschlüsselung. Er erzeugt aus dem Schlüssel den Schlüsselstrom, der auf die Nachricht addiert wird, um sie zu verschlüsseln. Die gängigsten Konstruktionen basieren auf linear… …   Deutsch Wikipedia

  • Криптографически стойкий генератор псевдослучайных чисел — (англ. Cryptographically secure pseudorandom number generator, CSPRNG)  это генератор псевдослучайных чисел с определенными свойствами, позволяющими использовать его в криптографии. Многие прикладные задачи криптографии требуют случайных… …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”