Метод Фибоначчи с запаздываниями

Запаздывающие генераторы Фибоначчи (англ. lagged Fibonacci generator) — генераторы псевдослучайных чисел, также называемые аддитивными генераторами.

В отличие от генераторов, использующих линейный конгруэнтный алгоритм, фибоначчиевы генераторы можно использовать в статистических алгоритмах, требующих высокого разрешения.

В связи с этим линейный конгруэнтный алгоритм постепенно потерял свою популярность и его место заняло семейство фибоначчиевых алгоритмов, которые могут быть рекомендованы для использования в алгоритмах, критичных к качеству случайных чисел.

История

Последовательность, в которой $X_{n+1}$ зависит более, чем от одного из предшествующих значений, и которая определяется следующей формулой:

X_{n+1}=(X_{n}+X_{n-1})\mod (2^{m}),

носит название последовательность Фибоначчи.

В начале 50-х годов изучался данный алгоритм, однако, исследования показали, что этот генератор, как источник случайных чисел, был неэффективен. Грин (Green), Смит (Smith) и Клем (Klem) предложили доработанную формулу последовательности Фибоначчи в виде:

X_{n+1}=(X_{n}+X_{n-k})\mod (2^{m}).

Однако, положительный результат получался лишь при $k\geq 16$ .

В 1958 году Митчел Дж. Ж. (Mitchell G. J.) и Мур Д. Ф. (Moore D. P.) вывели последовательность[1]:

X_{n}=(X_{n-24}+X_{n-55})\mod (2^{m}),

(1)

где $n\geq 55$ , $m$ — чётное число, $X_{0},X_{1},...,X_{54}$ — произвольные целые не все чётные числа. Числа 24 и 55 выбраны так, чтобы определялась последовательность, младшие значащие двоичные разряды $(X_{n}\mod (2))$ которой имеют длину периода $2^{55}-1$ .

Очевидными преимуществами данного алгоритма являются его быстрота, поскольку он не требует умножения чисел, а также, длина периода, однако, случайность, полученных с помощью него чисел, мало исследована.

Числа 24 и 55 обычно называют запаздыванием, а числа $X_{n}$ , определённые в (1) — последовательностью Фибоначчи с запаздыванием[2].

Впоследствии, на основе этих работ было подобрано множество запаздываний, которые приводят к длинным периодам по модулю 2.

Формула

Аддитивные генераторы генерируют вместо случайных битов случайные слова.

Для работы аддитивному генератору требуется некое начальное состояние, которое является ключом — набор n-битовых слов: 16-битовых, 32-битовых, 64-битовых слов и т. д. — $X_{1},X_{2},...,X_{k}$ .

Зная начальное состояние, можно вычислить i-е слово генератора по формуле[3]:

X_{i}=(X_{i-a}+X_{i-b}+...+X_{i-k})\mod (2^{m}),

причём период генератора должен быть более или равен $2^{m}-1$ .

Примеры алгоритмов, на основе аддитивных генераторов

1) Один из широко распространённых фибоначчиевых генераторов основан на следующей итеративной формуле:

X_{k}={\begin{cases}X_{k-a}-X_{k-b},&{\text{if  }}X_{k-a}\geq X_{k-b};\\X_{k-a}-X_{k-b}+1,&{\text{if }}X_{k-a}<X_{k-b};\end{cases}}

где $X_{k}$ — вещественные числа из диапазона $[0,1)$ , $a,b$ — целые положительные числа, называемые лагами. При реализации через целые числа достаточно формулы $X_{k}=X_{k-a}-X_{k-b}$ (при этом будут происходить арифметические переполнения). Для работы фибоначчиеву генератору требуется знать $\max\{a,b\}$ предыдущих сгенерированных случайных чисел. При программной реализации для хранения сгенерированных случайных чисел используется конечная циклическая очередь на базе массива. Для старта фибоначчиевому генератору требуется $\max\{a,b\}$ случайных чисел, которые могут быть сгенерированы простым конгруэнтным методом.

Получаемые случайные числа обладают хорошими статистическими свойствами, причём все биты случайного числа равнозначны по статистическим свойствам. Период фибоначчиева генератора может быть оценён по следующей формуле:

T=(2^{\max\{a,b\}}-1)\cdot 2^{\ell },

где $\ell$ — число битов в мантиссе вещественного числа.

Выбор параметров

Лаги a и b — «магические» и их не следует выбирать произвольно. Рекомендуются следующие значения лагов: $(a,b)=(55,24)$ , $(17,5)$ или $(97,33)$ . Качество получаемых случайных чисел зависит от значения константы, a чем оно больше, тем выше размерность пространства, в котором сохраняется равномерность случайных векторов, образованных из полученных случайных чисел. В то же время, с увеличением величины константы a увеличивается объём используемой алгоритмом памяти.

Значения $(a,b)=(17,5)$ можно рекомендовать для простых приложений, не использующих векторы высокой размерности со случайными компонентами. Значения $(a,b)=(55,24)$ позволяют получать числа, удовлетворительные для большинства алгоритмов, требовательных к качеству случайных чисел. Значения $(a,b)=(97,33)$ позволяют получать очень качественные случайные числа и используются в алгоритмах, работающих со случайными векторами высокой размерности. Описанный фибоначчиев генератор случайных чисел (с лагами 20 и 5) используется в широко известной системе Matlab (автором первой версии этой системы был Д. Каханер).

В настоящее время подобрано достаточно много пар чисел a и b, приведём некоторые из них:

(24,55),(38,89),(37,100),(30,127),(83,258),(107,378),(273,607),(1029,2281),(576,3217),(4178,9689),...

2) Брюс Шнайер в своей работе «Прикладная криптография» приводит примеры 3-х алгоритмов на основе аддитивных генераторов[5]:

Алгоритм Fish

«Fish — это аддитивный генератор, основанный на методах, используемых в прореживаемом генераторе. Он выдает поток 32-битовых слов, которые могут быть использованы (с помощью XOR) с потоком открытого текста для получения шифротекста или с потоком шифротекста для получения открытого текста. Название алгоритма представляет собой сокращение от Fibonacci shrinking generator — прореживаемый генератор Фиббоначи.

Во первых используйте два следующих аддитивных генератора. Ключом является начальные состояния этих генераторов.

A_{i}=(A_{i-55}+A_{i-24})\mod (2^{32})

B_{i}=(B_{i-52}+B_{i-19})\mod (2^{32})

Эти последовательности прореживаются попарно в зависимости от младшего значащего бита $B_{i}$ : если его значение равно 1, то пара используется, если 0 — игнорируется. $C_{j}$ — это последовательность используемых слов $A_{i}$ , a $D_{j}$ — это последовательность используемых слов $B_{i}$ . Для генерации двух 32-битовых слов-результатов $K_{2j}$ и $K_{2j+1}$ эти слова используются парами — $C_{2j},C_{2j+1},D_{2j},D_{2j+1}$ .

E_{2j}=C_{2j}\oplus (D_{2j}\land D_{2j+1})

F_{2j}=D_{2j+1}\oplus (E_{2j}\land C_{2j+1})

K_{2j}=E_{2j}\oplus F_{2j}

K_{2j+1}=C_{2j+1}\oplus F_{2j}

Этот алгоритм быстр, на процессоре i486/33 реализация Fish на языке С шифрует данные со скоростью 15-Мбит/с. К сожалению он также не безопасен, порядок вскрытия составляет около 2⁴⁰.»

Алгоритм Pike

«Pike — это обедненная и урезанная версия Fish, предложенная Россом Андерсоном, тем, кто взломал Fish . Он использует три аддитивных генератора. Например:

A_{i}=(A_{i-55}+A_{i-24})\mod (2^{32})

B_{i}=(B_{i-57}+B_{i-7})\mod (2^{32})

C_{i}=(C_{i-58}+C_{i-19})\mod (2^{32})

Для генерации слова потока ключей взгляните на биты переноса при сложении. Если все три одинаковы (все нули или все единицы), то тактируются все три генератора. Если нет, то тактируются только два совпадающих генератора. Сохраните биты переноса для следующего раза. Окончательным выходом является XOR выходов трех генераторов.

Pike быстрее Fish, так как в среднем для получения результата нужно 2.75 действия, а не 3. Он также слишком нов, чтобы ему доверять, но выглядит очень неплохо».

Алгоритм Mush

«Mush представляет собой взаимно прореживающий генератор. Его работу объяснить легко. Возьмем два аддитивных генератора: А и В. Если бит переноса А установлен, тактируется В. Если бит переноса В установлен, тактируется А.Тактируем А и при переполнении устанавливаем бит переноса. Тактируем В и при переполнении устанавливаем бит переноса. Окончательным выходом является XOR выходов А и В. Проще всего использовать те же генераторы, что и в Fish:

A_{i}=(A_{i-55}+A_{i-24})\mod (2^{32})

B_{i}=(B_{i-52}+B_{i-19})\mod (2^{32})

В среднем для генерации одного выходного слова нужно три итерации генератора. И если коэффициенты аддитивного генератора выбраны правильно и являются взаимно простыми, длина выходной последовательности будет максимальна.»

Примечания

Кнут Д. Искусство программирования. — том 2. — 3-е издание. — 2001 г. — гл.3.2.2.
Кнут Д. Искусство программирования. — том 2. — 3-е издание — 2001 г. — C.39.
Шнайер Б. Прикладная криптография. Протоколы, алгоритмы и исходные тексты на языке C. — 2002 г. — С. 291.
Bruce, Schneier. 16.9 Additive Generators // Applied cryptography: protocols, algorithms, and source code in C. John Wiley & Sons, Inc., New York (1996).
Шнайер Б. Прикладная криптография. Протоколы, алгоритмы и исходные тексты на языке C. — 2002 г. — гл.16.9.

Литература

Фергюсон Н., Шнайер Б. Практическая криптография. — Диалектика, 2005. — 418 с.
Лифшиц Ю. №9 // Современные задачи криптографии. - Курс лекций.. — Лаборатория мат. логики ПОМИ РАН, 2005.
Жельников В. Криптография от папируса до компьютера. — 1996. — 325 с.
William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numerical Recipes in C: The Art of Scientific Computing. — 1992.
Ross Anderson. On Fibonacci Keystream Generators. — Computer Laboratory,. Pembroke Street, Cambridge CB2 3QG.

Ссылки

http://www.phy.ornl.gov/csep/rn/node20.html Архивная копия от 30 января 2014 на Wayback Machine
Aluru, S. (1997). Lagged Fibonacci Random Number Generators for Distributed Memory Parallel Computers. Архивная копия от 26 марта 2014 на Wayback Machine JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 45, 1-12.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Кнут Д. Искусство программирования. — том 2. — 3-е издание. — 2001 г. — гл.3.2.2.

[2] Кнут Д. Искусство программирования. — том 2. — 3-е издание — 2001 г. — C.39.

[3] Шнайер Б. Прикладная криптография. Протоколы, алгоритмы и исходные тексты на языке C. — 2002 г. — С. 291.

[4] Bruce, Schneier. 16.9 Additive Generators // Applied cryptography: protocols, algorithms, and source code in C. John Wiley & Sons, Inc., New York (1996).

[5] Шнайер Б. Прикладная криптография. Протоколы, алгоритмы и исходные тексты на языке C. — 2002 г. — гл.16.9.