Генератор Фібоначчі

Генератор Фібоначчі (англ. lagged Fibonacci generator) — генератор псевдовипадкових чисел, також названий адитивний генератор.

На відмінну від генераторів, що використовують лінійний конгруентий метод, генератор Фібоначчі можна використовувати в статистичних алгоритмах, які потребують високого розширення.

У зв'язку з цим лінійний конгруентний алгоритм поступово втратив свою популярність і його місце зайняло сімейство алгоритмів Фібоначчі, які можуть бути рекомендовані для використання в алгоритмах.

Історія

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

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

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

На початку 50-х років вивчався даний алгоритм, проте, дослідження показали, що цей генератор, як джерело випадкових чисел, був неефективний. Вчені запропонували допрацьовану формулу послідовності Фібоначчі у вигляді:

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

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

У 1958 році було виведено послідовність:

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

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

Очевидними перевагами даного алгоритму є його швидкість, оскільки він не вимагає множення чисел, а також, довжина періоду.

Формула

Адитивні генератори генерують замість випадкових бітів випадкові слова.

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

Знаючи початковий стан, можна обчислити ${\displaystyle i-}$е слово генератора за формулою :

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

причому період генератора повинен бути більше або дорівнювати ${\displaystyle 2^{m}-1}$.

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

${\displaystyle (x\oplus 1)^{S},\quad \quad S={\overline {1,7}}}$

S	1	2	3	4	5	6	7
${\displaystyle f(x)}$	3	5	17	21	63	125	377
Випадкові послідовності	${\displaystyle \{1(2)\}}$	${\displaystyle \{1(4)\}}$	${\displaystyle \{2(4)\}}$	${\displaystyle \{2(8)\}}$	${\displaystyle \{4(8)\}}$	${\displaystyle \{8(8)\}}$	${\displaystyle \{16(8)\}}$
Г е н е р а т о р и Ф і б о н н а ч і	${\displaystyle (M-1)}$ 01	${\displaystyle (M-3)}$ 0011	${\displaystyle (M-3)\Pi }$ 0001, 0111	${\displaystyle (M-7)\Pi }$ 00001111, 01011010	${\displaystyle (M-7)\Pi }$ 00000101, 00011011, 00100111, 01011111	${\displaystyle (M-7)\Pi }$ 00000011, 00001001, 00010111, 00011101, 00101011, 00110101, 00111111, 01101111	${\displaystyle (M-7)\Pi }$ 00000001, 00000111, 00001011, 00001101, 00010011, 00010101, 00011001, 00011111, 00100101, 00101111, 00110111, 00111011, 00111101, 01010111, 01011011, 01111111

При ${\displaystyle S={\overline {5,7}}}$ для випадкової послідовності ${\displaystyle \{4(8)\}-\{16(8)\}}$ усі ${\displaystyle (M-7)\Pi \Pi }$ різні, причому половина їх інверсні. Жирним шрифтом виділені послідовності де Брейна.

Основне джерело:

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}<X_{k-b};\end{cases}}}$

де ${\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 збільшується обсяг використаної алгоритмом пам'яті.

Значення ${\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})}$

В середньому для генерації одного вихідного слова потрібно три ітерації генератора. І якщо коефіцієнти адитивного генератора обрані правильно і є взаємно простими, довжина вихідної послідовності буде максимальна.

Примітки

1. Кнут Д. Искусство программирования. — том 2. — 3-е издание. — 2001 г. — гл.3.2.2.
2. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы и исходные тексты на языке C. — 2002 г. — С. 291.
3. В.А.Песошин, В.М.Кузнецов, А.С.Кузнецова, А.Р.Шамеева - Генераторы псевдослучайных последовательностей немаксимальной длины на регистрах сдвига.
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.

Посилання

• 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.