Blum Blum Shub

Blum Blum Shub

Blum Blum Shub

Blum Blum Shub (BBS) es un generador pseudoaleatorio de números propuesto por Lenore Blum, Manuel Blum y Michael Shub en 1986.

El algoritmo BBS es:

xn+1 = (xn)2 mod M

donde M=pq es el producto de dos números primos muy grandes p y q. En cada paso del algorimo, se obtiene un resultado para xn; el resultado es por lo general o bien el bit de paridad de xn ó uno ó más de los bits menos significativos de xn.

Los dos números primos, p y q, deben ser ambos congruentes a 3 (mod 4) (esto asegura que cada residuo cuadrático posee una raíz cuadrada que también es un residuo cuadrático) y mcd(φ(p-1), φ(q-1)) debe ser pequeña (esto hace que la longitud del ciclo sea extensa).

Una característica interesante del generador BBS generator es la posibilidad de calcular todo valor xi en forma directa:

 x_i = \left( x_0^{2^i \bmod (p-1)(q-1)} \right) \bmod M.

Contenido

Seguridad

El generador es apropiado para ser utilizado en criptografía, aunque no en simulaciones, ya que no es muy rápido. Sin embargo, es muy resistente desde el punto de vista de su seguridad, lo que se relaciona con la calidad del generador en cuanto a la complejidad computacional de la factorización de enteros. Cuando se eligen los primos en forma adecuada, y los bits menos significativos O(log log M) de cada xn se eligen como resultado, entonces en el límite cuando M se hace muy grande, distinguir los bits resultado de una secuencia aleatoria será por lo menos tan difícil como factorizar M.

Si la factorización de enteros es difícil (como es de esperar) entonces BBS con grandes M tendrán un resultado libre de todo patrón no aleatorio que puede ser descubierto mediante una cantidad razonable de cálculos. Esto hace que el método sea tan seguro como otras tecnologías de cifrado asociadas al problema de factorización, como por ejemplo la cifrado RSA.

Ejemplo

Sea p=11, q=19 y s=3. Podemos esperar obtener un ciclo largo para estos números pequeños, porque mcd(φ(p-1), φ(q-1))=2. El generador comienza a evaluar x0 utilizando x -1=s y crea la sucesión x0, x1, x2,... x5= 9, 81, 82, 36, 42, 92. Si se utiliza el bit de paridad para definir el resultado, entonces los bits resultados son 0 1 1 0 1 0.

Referencias

  • Lenore Blum, Manuel Blum, and Michael Shub. "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing, volume 15, pages 364–383, May 1986.
  • Lenore Blum, Manuel Blum, and Michael Shub. "Comparison of two pseudo-random number generators", Advances in Cryptology: Proceedings of Crypto '82. Available as PDF.
  • Martin Geisler, Mikkel Krøigård, and Andreas Danielsen. "About Random Bits", December 2004. Available as PDF and Gzipped Postscript.

Enlaces externos

Obtenido de "Blum Blum Shub"

Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • Blum Blum Shub — (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et al, 1986).Blum Blum Shub takes the form:: x n +1 = ( xn )2 mod M where M=pq is the product of two large primes p and q . At each… …   Wikipedia

  • Blum Blum Shub — Pour les articles homonymes, voir BBS. Blum Blum Shub (BBS) est un algorithme capable de produire des nombres pseudo aléatoires. Il fut proposé en 1986 par Lenore Blum, Manuel Blum et Michael Shub, d où son nom. On calcule la sortie de BBS en… …   Wikipédia en Français

  • Blum-Blum-Shub — Der Blum Blum Shub Generator (BBS Generator; auch „s² mod n Generator“) ist ein Pseudozufallszahlengenerator, entwickelt 1986 von Lenore Blum, Manuel Blum und Michael Shub. Anwendung findet das System u. a. in der Kryptologie im Entwurf… …   Deutsch Wikipedia

  • Blum-Blum-Shub-Generator — Der Blum Blum Shub Generator (BBS Generator; auch „s² mod n Generator“) ist ein Pseudozufallszahlengenerator, entwickelt 1986 von Lenore Blum, Manuel Blum und Michael Shub. Anwendung findet das System u. a. in der Kryptologie im Entwurf… …   Deutsch Wikipedia

  • Blum-Shub-Smale machine — In computation theory, the Blum Shub Smale machine, or BSS machine, is a model of computation introduced by Lenore Blum, Michael Shub and Stephen Smale, intended to describe computations over the real numbers. Essentially, a BSS machine is a… …   Wikipedia

  • Machine de Blum-Shub-Smale — Une machine de Blum Shub Smale (ou machine BSS) est une machine de Turing calculant sur les nombres réels (autrement dit, son alphabet de bande est ). Elle manipule les réels comme des entités atomiques (c est à dire sans s intéresser à leur… …   Wikipédia en Français

  • Shub — ist der Familienname von Esfir Schub (1894–1953), sowjetische Regisseurin und Drehbuchautorin Michael Shub, Entwickler des Blum Blum Shub Generator Peter Shub (* 1957), US amerikanischer Clowndarsteller Diese Seite ist eine Be …   Deutsch Wikipedia

  • Blum-Goldwasser-Kryptosystem — Der Blum Blum Shub Generator (BBS Generator; auch „s² mod n Generator“) ist ein Pseudozufallszahlengenerator, entwickelt 1986 von Lenore Blum, Manuel Blum und Michael Shub. Anwendung findet das System u. a. in der Kryptologie im Entwurf… …   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

  • Blum — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.  Pour les articles homophones, voir Bloom et Blume. Patronyme Blum est un nom de famille notamment porté par : Alain Blum (1958 ), historien et… …   Wikipédia en Français

Compartir el artículo y extractos

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