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

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

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

,

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

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

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

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

,

куда это Функция Кармайкла. (Здесь у нас есть ).

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

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

Пример

Позволять , и (куда это семя). Мы можем ожидать получения большой длины цикла для этих маленьких чисел, потому что Генератор начинает оценивать используя и создает последовательность , , , = 9, 81, 236, 36, 31, 202. В следующей таблице показан вывод (в битах) для различных методов выбора битов, используемых для определения вывода.

Бит четностиНаименее значащий бит
0 1 1 0 1 01 1 0 0 1 0

Следующее 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] бит четности младший бит))))

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

  1. ^ а б Блюм, Ленор; Блюм, Мануэль; Шуб, Майк (1 мая 1986 г.). «Простой генератор непредсказуемых псевдослучайных чисел». SIAM Журнал по вычислениям. 15 (2): 364–383. Дои:10.1137/0215025.
Общий

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