Блюм Блюм Шуб - Blum Blum Shub - Wikipedia

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

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

${\displaystyle x_{n+1}=x_{n}^{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. В следующей таблице показан вывод (в битах) для различных методов выбора битов, используемых для определения вывода.

Бит четности	Наименее значащий бит
0 1 1 0 1 0	1 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.

Общий

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

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

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