Алгоритм Блюма

Алгоритм Блюма

Алгоритм Блюм — Блюма — Шуба (англ. Algorithm Blum — Blum — Shub, BBS) — это генератор псевдослучайных чисел, предложенный в 1986 году Ленор Блюм, Мануэлем Блюмом и Майклом Шубом (Blum et al, 1986).

BBS выглядит так:

x_{n+1}=x_n^2\;\bmod\;M,

где M=pq является произведением двух больших простых p и q. На каждом шаге алгоритма выходные данные получаются из x_n путём взятия либо бита чётности, либо одного или больше наименее значимых бит x_n.

Два простых числа, p и q, должны быть оба сравнимы с 3 по модулю 4 (это гарантирует, что каждый квадратичный вычет имеет один квадратный корень, который также является квадратичным вычетом) и наибольший общий делитель НОД(\varphi(p-1),\;\varphi(q-1)) должен быть мал (это увеличивает длину цикла).

Интересной особенностью этого алгоритма является то, что для получения x_n необязательно вычислять все n-1 предыдущих чисел, если известно начальное состояние генератора x_0 и числа p и q. n-ное значение может быть вычислено «напрямую» используя формулу:

x_n=x_0^{2^n\;\bmod\;((p-1)(q-1))}\;\bmod\;M.

Надёжность

Этот генератор подходит для криптографии, но не для моделирования, потому что он недостаточно быстр. Однако, он имеет необычно высокую стойкость, которая обеспечивается качеством генератора исходя из вычислительной сложности задачи факторизации чисел. Когда простые числа выбраны осторожно, и O(\log\log M) бит каждого x_n являются выходными данными, тогда предел взятый как M быстро растёт, и вычисление выходных бит будет настолько же трудно, как и факторизация M.

Если факторизация целых чисел так трудна (как предполагается), тогда BBS с большим M будет иметь выход, свободный от любых неслучайных шаблонов, которые могут быть выявлены при достаточном объёме вычислений. Однако, возможно появление быстрого алгоритма для факторизации, и вследствие этого BBS не является гарантированно надёжным.

Литература

  • 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.
  • Pascal Junod, «Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator», August 1999. 21 page PDF file
  • Martin Geisler, Mikkel Krøigård, and Andreas Danielsen. «About Random Bits», December 2004. Available as PDF and Gzipped Postscript.
  • Randomness Recommendations for Security — RFC 1750.

Ссылки

  • GMPBBS — реализация метода Блюма — Блюма — Шуба, базирующаяся на GMP.

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Полезное


Смотреть что такое "Алгоритм Блюма" в других словарях:

  • Алгоритм Блюма — Блюма — Шуба — Алгоритм Блюма  Блюма  Шуба (англ. Algorithm Blum Blum Shub, BBS)  это генератор псевдослучайных чисел, предложенный в 1986 году Ленор Блюм, Мануэлем Блюмом и Майклом Шубом (Blum et al, 1986). BBS выглядит так: где M = pq является… …   Википедия

  • Алгоритм Блюма, Блюма и Шуба — …   Википедия

  • Алгоритм Fortuna — Fortuna это семейство криптографически стойких генераторов псевдослучайных чисел. Алгоритм разработан Брюсом Шнайером и Нильсом Фергюсоном (англ.) и впервые описан в их книге «Практическая криптография»[1]. По словам авторов, алгоритм был… …   Википедия

  • Криптосистема Блюма — Криптосистема Блюма  Гольдвассер одна из схем шифрования с открытым ключом, основанная на сложности факторизации больших целых чисел. Пусть m1, m2, … , mm  последовательность бит открытого текста. В качестве параметров криптосистемы… …   Википедия

  • Блюм-Блюм-Шуб — Алгоритм Блюма  Блюма  Шуба (англ. Algorithm Blum Blum Shub, BBS)  это генератор псевдослучайных чисел, предложенный в 1986 году Ленор Блюм, Мануэлем Блюмом и Майклом Шубом (Blum et al, 1986). BBS выглядит так: где M = pq является произведением… …   Википедия

  • Блюм, Мануэль — Мануэль Блюм Manuel Blum Дата рождения: 26 апреля 1938(1938 04 26) (74 года) Место рождения: Каракас, Венесуэла Научная сфера …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия

  • Мануэль Блюм — Manuel Blum Дата рождения: 26 апреля 1938(19380426) Место рождения:  Венесуэла, Каракас …   Википедия

  • Хронология развития вычислительной техники — Паскалина Блеза Паскаля (1640) …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»