Блюм Блюм Шуб

В этой статье есть несколько проблем. Помогите улучшить ее или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти сообщения ) В статье содержится список общих ссылок , но в ней отсутствуют соответствующие встроенные цитаты .Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Сентябрь 2013 )( Узнайте, как и когда удалить это сообщение ) В статье чрезмерно много ссылок на первоисточники .Пожалуйста, улучшите эту статью, добавив вторичные или третичные источники . Найти источники:  "Blum Blum Shub" – новости  · газеты  · книги  · ученый  · JSTOR ( Сентябрь 2013 )( Узнайте, как и когда удалить это сообщение ) ( Узнайте, как и когда удалить это сообщение )

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

Blum Blum Shub принимает форму

${\displaystyle x_{n+1}=x_{n}^{2}{\bmod {M}}}$,

где M = pq — произведение двух больших простых чисел p и q . На каждом шаге алгоритма из x _{n +1} выводится некоторый вывод ; вывод обычно представляет собой либо битовую четность x _{n +1} , либо один или несколько младших битов x _{n +1} .

Начальное число x 0 _должно быть целым числом, взаимно простым с M (т.е. p и q не являются множителями x ₀ ), а не 1 или 0.

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

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

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

где — функция Кармайкла . (Здесь мы имеем ).${\displaystyle \лямбда}$${\displaystyle \lambda (M)=\lambda (p\cdot q)=\operatorname {lcm} (p-1,q-1)}$

Существует доказательство, сводящее его безопасность к вычислительной сложности факторизации. ^[1] Когда простые числа выбраны надлежащим образом и выводится O ( log log M ) младших битов каждого x _n , то в пределе, когда M становится большим, отличить выходные биты от случайных должно быть по крайней мере так же сложно, как решить задачу квадратичного остатка по модулю M .

Производительность генератора случайных чисел BBS зависит от размера модуля M и количества бит на итерацию j . Хотя уменьшение M или увеличение j ускоряет алгоритм, это также снижает безопасность. В статье 2005 года дается конкретное, а не асимптотическое, доказательство безопасности BBS для заданных M и j . Результат также можно использовать для руководства выбором двух чисел путем балансирования ожидаемой безопасности и вычислительных затрат. ^[2]

Пусть , и (где — начальное число). Мы можем ожидать получить большую длину цикла для этих малых чисел, потому что . Генератор начинает оценку , используя и создает последовательность , , , = 9, 81, 236, 36, 31, 202. В следующей таблице показаны выходные данные (в битах) для различных методов выбора битов, используемых для определения выходных данных.${\displaystyle p=11}$${\displaystyle q=23}$${\displaystyle s=3}$${\displaystyle с}$${\displaystyle {\rm {НОД}}((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}}$

Ниже приведена реализация Python , которая проверяет простоту числа.

import  sympy def  blum_blum_shub ( p1 ,  p2 ,  seed ,  iterations ) :  assert  p1  %  4  ==  3  assert  p2  %  4  ==  3  assert  sympy.isprime ( p1 // 2 ) assert sympy.isprime ( p2 // 2 ) n = p1 * p2 numbers = [] for _ in range ( iterations ) : seed = ( seed ** 2 ) % n if seed in numbers : print ( f " ГСЧ зациклился на { len ( numbers ) } шагах " ) return numbers numbers.append ( seed ) return numbers                               печать ( blum_blum_shub ( 11 ,  23 ,  3 ,  100 ))

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

( defun get-number-of-1-bits ( bits ) "Возвращает количество битов со значением 1 в целочисленном коде BITS." ( declare ( type ( integer 0 * ) bits )) ( the ( integer 0 * ) ( logcount bits )))               ( defun get-even-parity-bit ( bits ) "Возвращает бит четности целочисленно закодированных БИТОВ." ( declare ( type ( integer 0 * ) bits )) ( the bit ( mod ( get-number-of-1-bits bits ) 2 )))               ( defun get-least-significant-bit ( bits ) "Возвращает младший бит целочисленно закодированного BITS." ( declare ( type ( integer 0 * ) bits )) ( the bit ( ldb ( byte 1 0 ) bits )))                ( defun make-blum-blum-shub ( &key ( p 11 ) ( q 23 ) ( s 3 )) "Возвращает функцию без аргументов, которая представляет собой простой  генератор псевдослучайных чисел Блюма-Блюма-Шуба, настроенный на использование  параметров генератора P, Q и S (начальное число) и возвращающий три значения:  (1) число x[n+1],  (2) бит четности числа,  (3) младший значащий бит числа.  ---  Обратите внимание, что параметры P, Q и S не проверяются в  соответствии с условиями, описанными в статье." ( declare ( type ( integer 0 * ) p q s )) ( let (( M ( * p q )) ;; M = p * q ( x[n] s )) ;; x0 = начальное число ( declare ( type ( integer 0 * ) M x[n] )) #' ( lambda () ;; x[n+1] = x[n]^2 mod M ( let (( x[n+1] ( mod ( * x[n] x[n] ) M ))) ( declare ( type ( integer 0 * ) x[n+1] )) ;; Вычислить случайный бит(ы) на основе x[n+1]. ( let (( even-parity-bit ( get-even-parity-bit x[n+1] )) ( least-significant-bit ( get-least-significant-bit x[n+1] ))) ( declare ( type bit even-parity-bit )) ( declare ( type bit least-significant-bit )) ;; Обновить состояние так, чтобы x[n+1] стало новым x[n]. ( setf x[n] x[n+1] ) ( values ​​x[n+1] even-parity-bit least-significant-bit ))))))                                                                         ;; Распечатайте примерные результаты. ( let (( bbs ( make-blum-blum-shub :p 11 :q 23 :s 3 ))) ( declare ( type ( function () ( values ​​( integer 0 * ) bit bit )) bbs )) ( format T "~&Keys: E = четность, L = младший значащий" ) ( format T "~2%" ) ( format T "~&x[n+1] | E | L" ) ( format T "~&--------------" ) ( loop repeat 6 do ( multiple-value-bind ( x[n+1] even-parity-bit less-significant-bit ) ( funcall bbs ) ( declare ( type ( integer 0 * ) x[n+1] )) ( declare ( type bit even-parity-bit )) ( declare ( type bit less-significant-bit )) ( format T "~&~6d | ~d | ~d" x[n+1] бит-четности младший-значимый-бит ))))                                                             

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