Блюм Блюм Шуб - Википедия - Blum Blum Shub

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Сентябрь 2013) (Узнайте, как и когда удалить этот шаблон сообщения) Эта статья слишком полагается на Рекомендации к основные источники. Пожалуйста, улучшите это, добавив вторичные или третичные источники. (Сентябрь 2013) (Узнайте, как и когда удалить этот шаблон сообщения) (Узнайте, как и когда удалить этот шаблон сообщения)

Блюм Блюм Шуб (B.B.S.) это генератор псевдослучайных чисел предложенный в 1986 г. Ленор Блюм, Мануэль Блюм и Михаил Шуб^[1] это получено из Майкл О. Рабин односторонняя функция.

Блюм Блюм Шуб принимает форму

${ Displaystyle х_ {п + 1} = х_ {п} ^ {2} { bmod {M}}}$,

куда M = pq это продукт двух больших простые числа п и q. На каждом шаге алгоритма какой-то результат получается из Икс_п+1; выход обычно либо битовая четность из Икс_п+1 или один или несколько младших битов Икс_п+1.

В семя Икс₀ должно быть целым числом, взаимно простым с M (т.е. п и q не являются факторами Икс₀), а не 1 или 0.

Два простых числа, п и q, оба должны быть конгруэнтный до 3 (mod 4) (это гарантирует, что каждый квадратичный вычет есть один квадратный корень который также является квадратичным вычетом) и должен быть безопасные простые числа с небольшим gcd ((п-3)/2, (q-3)/2) (это увеличивает длину цикла).

Интересной особенностью генератора Блюма-Блюма-Шуба является возможность вычисления любых Икс_я значение напрямую (через Теорема Эйлера ):

${ displaystyle x_ {i} = left (x_ {0} ^ {2 ^ {i} { bmod { lambda}} (M)} right) { bmod {M}}}$,

куда ${ displaystyle lambda}$ это Функция Кармайкла. (Здесь у нас есть ${ displaystyle lambda (M) = lambda (p cdot q) = operatorname {lcm} (p-1, q-1)}$).

Безопасность

Есть доказательства, снижающие его безопасность до вычислительная сложность факторинга.^[1] Когда простые числа выбраны надлежащим образом, и О (бревно бревно M) младшие биты каждого Икс_п выводятся, то в пределе как M становится большим, отличить выходные биты от случайных должно быть не менее сложно, чем решение проблемы квадратичной остаточности по модулю M.

Пример

Позволять ${ displaystyle p = 11}$, ${ displaystyle q = 23}$ и ${ displaystyle s = 3}$ (куда ${ displaystyle s}$ это семя). Мы можем ожидать получения большой длины цикла для этих маленьких чисел, потому что ${ displaystyle { rm {gcd}} ((p-3) / 2, (q-3) / 2) = 2}$Генератор начинает оценивать ${ displaystyle x_ {0}}$ используя ${ displaystyle x _ {- 1} = s}$ и создает последовательность ${ displaystyle x_ {0}}$, ${ displaystyle x_ {1}}$, ${ displaystyle x_ {2}}$, ${ displaystyle ldots}$ ${ displaystyle x_ {5}}$ = 9, 81, 236, 36, 31, 202. В следующей таблице показан вывод (в битах) для различных методов выбора битов, используемых для определения вывода.

Следующее Common Lisp реализация обеспечивает простую демонстрацию генератора, в частности, в отношении трехбитовых методов выбора. Важно отметить, что требования, предъявляемые к параметрам п, q и s (семя) не проверяются.

(defun получить число-1-бит (биты)  «Подсчитывает и возвращает количество однозначных битов в БИТАХ».  (объявить (целое число биты))  (то беззнаковый байт    (петля за битовый индекс из 0 ниже (целая длина биты)          когда (logbitp битовый индекс биты) сумма 1)))(defun получить бит четности (номер)  "Возвращает бит четности ЧИСЛА."  (объявить (целое число номер))  (то кусочек (мод (получить число-1-бит номер) 2)))(defun получить наименее значимый бит (номер)  "Возвращает младший значащий бит ЧИСЛА."  (объявить (целое число номер))  (то кусочек (ldb (байт 1 0) номер)))(defun Make-Blum-Blum-Shub (&ключ (п 11) (q 23) (s 3))  "Возвращает функцию без аргументов, которая представляет собой простой   Генератор псевдослучайных чисел Блюма-Блюма-Шуба, настроенный на использование   параметры генератора P, Q и S (начальное число) и возвращающие три значения:   (1) бит четности числа,   (2) младший бит числа,   (3) число x [n + 1].   ---   Обратите внимание, что параметры P, Q и S не проверяются в   в соответствии с условиями, описанными в статье ».  (объявить (тип целое число п q s))  (позволять ((M    (* п q))       ;; М = р * д        (х [п] s))            ;; x0 = семя    (объявить (целое число M х [п]))    #'(лямбда ()        ;; x [n + 1] = x [n] ^ 2 mod M        (позволять ((х [п + 1] (мод (* х [п] х [п]) M)))          (объявить (целое число х [п + 1]))          ;; Вычислить случайные биты на основе x [n + 1].          (позволять ((бит четности       (получить бит четности       х [п + 1]))                (младший бит (получить наименее значимый бит х [п + 1])))            ;; Обновите состояние так, чтобы x [n + 1] стал новым x [n].            (setf х [п] х [п + 1])            (значения бит четности                    младший бит                    х [п + 1]))))));; Распечатайте примерные результаты.(позволять ((BBS (Make-Blum-Blum-Shub :п 11 : q 23 : s 3)))  (формат Т "~ & Ключи: E = четность, ~                     L = наименее значимый ")  (формат Т "~2%")  (формат Т "~ & x [n + 1] | E | L")  (формат Т "~&--------------")  (петля повторение 6 делать    (привязка нескольких значений (бит четности младший бит х [п + 1])        (веселье BBS)      (формат Т "~ & ~ 6d | ~ d | ~ d"        х [п + 1] бит четности младший бит))))

Рекомендации

Общий

• Блюм, Ленор; Блюм, Мануэль; Шуб, Майк (1982). «Сравнение двух генераторов псевдослучайных чисел». Достижения в криптологии: Труды CRYPTO '82. Пленум: 61–78. Цитировать журнал требует | журнал = (помощь)
• Гейслер, Мартин; Кройгард, Миккель; Даниэльсен, Андреас (декабрь 2004 г.). «О случайных битах». CiteSeerX  10.1.1.90.3779. Цитировать журнал требует | журнал = (помощь) доступно как PDF и сжатый Postscript

внешняя ссылка

• GMPBBS, реализация на языке C Марка Россмиллера
• BlumBlumShub, реализация на языке Java от Марка Россмиллера
• Реализация на Java
• Тесты на случайность