Блюм Блюм Шуб

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

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

$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 (по модулю 4) (это гарантирует, что каждый квадратичный остаток имеет один квадратный корень , который также является квадратичным остатком) и должны быть безопасными простыми числами с небольшим НОД (( p- 3 ) /2 , ( q-3 ) /2 ) (это делает длину цикла большой).

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

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

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

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

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

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

Пример

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

Бит четности	Младший бит
0 1 1 0 1 0	1 1 0 0 1 0

Ниже приведена реализация 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"The RNG has fallen into a loop at {len(numbers)} steps")
      return numbers
    numbers.append(seed)
  return numbers

print(blum_blum_shub(11, 23, 3, 100))

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

(defun get-number-of-1-bits (bits)
  "Returns the number of 1-valued bits in the integer-encoded BITS."
  (declare (type (integer 0 *) bits))
  (the (integer 0 *) (logcount bits)))

(defun get-even-parity-bit (bits)
  "Returns the even parity bit of the integer-encoded BITS."
  (declare (type (integer 0 *) bits))
  (the bit (mod (get-number-of-1-bits bits) 2)))

(defun get-least-significant-bit (bits)
  "Returns the least significant bit of the integer-encoded 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))
  "Returns a function of no arguments which represents a simple
   Blum-Blum-Shub pseudorandom number generator, configured to use the
   generator parameters P, Q, and S (seed), and returning three values:
   (1) the number x[n+1],
   (2) the even parity bit of the number,
   (3) the least significant bit of the number.
   ---
   Please note that the parameters P, Q, and S are not checked in
   accordance to the conditions described in the article."
  (declare (type (integer 0 *) p q s))
  (let ((M    (* p q))       ;; M  = p * q
        (x[n] s))            ;; x0 = seed
    (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]))
          ;; Compute the random bit(s) based on 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))
            ;; Update the state such that x[n+1] becomes the new x[n].
            (setf x[n] x[n+1])
            (values x[n+1]
                    even-parity-bit
                    least-significant-bit))))))

;; Print the exemplary outputs.
(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 = even parity, L = least significant")
  (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 least-significant-bit)
        (funcall bbs)
      (declare (type (integer 0 *) x[n+1]))
      (declare (type bit           even-parity-bit))
      (declare (type bit           least-significant-bit))
      (format T "~&~6d | ~d | ~d"
                x[n+1] even-parity-bit least-significant-bit))))

Ссылки

Источники

• Блюм, Ленор; Блюм, Мануэль; Шуб, Майкл (1983). «Сравнение двух генераторов псевдослучайных чисел» . Достижения криптологии . Бостон, Массачусетс: Springer US. стр. 61–78. дои : 10.1007/978-1-4757-0602-4_6 . ISBN  978-1-4757-0604-8 .
• Блюм, Л.; Блюм, М.; Шуб, М. (1986). «Простой непредсказуемый генератор псевдослучайных чисел» (PDF) . SIAM Journal по вычислительной технике . 15 (2). Общество промышленной и прикладной математики (SIAM): 364–383. дои : 10.1137/0215025 . ISSN   0097-5397 . Архивировано (PDF) из оригинала 14 августа 2021 г.
• Гейслер, Мартин; Кройгорд, Миккель; Дэниелсен, Андреас (декабрь 2004 г.), О случайных битах (PDF) , CiteSeerX   10.1.1.90.3779 , заархивировано (PDF) из оригинала 31 марта 2016 г.

Внешние ссылки

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