Blum Blum Shub

Blum Blum Shub
Page d'aide sur l'homonymie 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 itérant la suite :

x_{n+1} = (x_n)^2 \!\mod M

où "mod" est l'opérateur reste lors de la division par M = p\,q, le produit de deux grands nombres premiers p et q, et la sortie de l'algorithme est le bit le moins significatif de xn. Alternativement, la sortie peut être plusieurs des derniers bits de xn

Les deux nombres premiers, p et q, devraient tous deux être congruents à 3 modulo 4 (cela garantit que chaque résidu quadratique possède une racine carrée qui soit également un résidu quadratique) et \operatorname{pgcd}(\phi(p-1),\phi(q-1)) doit être petit (ce qui fait que le cycle est long).

Sécurité de l'algorithme

Le générateur n'est pas approprié aux simulations, mais plutôt à la cryptographie, car il est assez lent.

Cependant, il possède une sécurité inhabituelle, puisqu'il a été démontré, tout d'abord, qu'il était cryptographiquement sûr sous l'hypothèse qu'il soit difficile de déterminer si, modulo un entier composé, un nombre est un carré ou non (problème de la résiduosité quadratique). Par la suite, il a été prouvé qu'il était cryptographiquement sûr, sous l'hypothèse que le problème de la factorisation soit difficile, et qu'au plus log(log(M)) bits de poids faible de chaque xn soient sortis à chaque itération. Dans ce cas, il n'est pas possible de différencier la suite produite d'une suite réellement aléatoire.

Références

  • Lenore Blum, Manuel Blum, et Michael Shub. "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing, volume 15, pages 364–383, mai 1986.
  • Pascal Junod, "Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator", août 1999. PDF de 21 pages
  • Martin Geisler, Mikkel Krøigård, et Andreas Danielsen. "About Random Bits", décembre 2004. Disponible en PDF et Gzipped Postscript.
  • Umesh V. Vazirani, Vijay V. Vazirani. "Efficient and Secure Pseudo-Random Number Generation", Crypto'84, Lecture Notes in Computer Science Volume 196, p. 193--202, Springer-Verlag (1985)

Liens externes

  • GMPBBS - une implémentation GNU de l'algorithme Blum Blum Shub.
v · Générateurs de nombres pseudo-aléatoires
Rapide Générateur congruentiel linéaire • Mersenne Twister • RANDU
Cryptographiques Blum Blum Shub • Fortuna • ISAAC • Yarrow
Briques Congruence sur les entiers • Fonction de hachage • LFSR

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Blum Blum Shub de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Blum Blum Shub — Saltar a navegación, búsqueda 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… …   Wikipedia Español

  • 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 — 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

Share the article and excerpts

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