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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}$ 

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

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

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

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

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

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

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

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

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

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

Алгоритм Fish

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

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

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

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

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

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

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

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

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

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

Алгоритм Pike

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

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

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

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

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

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

Алгоритм Mush

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

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

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

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