"> Поточне псевдовипадкове число Yi отримують з попереднього числа Yi - 1 множенням його на коефіцієнт а, складанням з приростом b і обчисленням залишку від ділення на модуль m. Дане рівняння генерує псевдовипадкові числа з періодом повторення, який залежить від обираних значень параметрів а, і m і може досягати значення m. Якщо a, b і m обрані правильно, то генератор буде з максимальним періодом (наприклад, b повинно бути взаємно простим з m і коефіцієнт а повинен бути непарним числом). Значення модуля m береться рівним 2n або рівним простому числу, наприклад m=231-1.
Перевагою лінійних конгруентних генераторів є їх швидкість за рахунок малої кількості операцій на біт.
Конгруентні генератори, що працюють за алгоритмом, запропонованим
Національним бюро стандартів США, використовуються, зокрема, в системах програмування. Ці генератори мають довжину періоду 224 і володіють хорошими статистичними властивостями. Однак така довжина періоду мала для криптографічних застосувань. Крім того, доведено, що послідовності, що генеруються конгруентними генераторами, не є криптографічно стійкими.
Однак лінійні конгруентний генератори зберігають свою корисність для НЕ криптографічних додатків, наприклад, для моделювання. Вони ефективні в більшості використовуваних емпіричних тестах і демонструють хороші статистичні характеристики.
2.4 Лінійні рекурентні генератори
Існує спосіб генерації послідовностей псевдовипадкових чисел на основі лінійних рекурентних співвідношень.
Розглянемо рекурентні співвідношення через їх різницеві рівняння
(2.4)
(2.5)
де і кожне hi належать полю GF (q).
Рішенням цих рівнянь є послідовність елементів поля GF (q). Співвідношення (2.5) визначає правило обчислення аk по відомим значенням величин Потім по відомим значенням знаходять ak +1 і т.д. У результаті за початковими значеннями можна побудувати нескінченну послідовність, причому кожен її наступний член визначається з k попередніх. Послідовності такого виду легко реалізуються на комп'ютері, при цьому реалізація виходить особливо простий, якщо все hi і ai значення 0 і 1 з поля GF (2).
На рис. 2.4 показана лінійна послідовна Переключательная схема, яка може бути використана для обчислення суми і, отже, для обчислення значення аk за значеннями k попередніх членів послідовності.
Вихідні величини поміщаються в розряди зсувного регістру, послідовні зрушення вмісту якого відповідають обчисленню послідовних символів, при цьому вихід після i-го зсуву дорівнює аi. Даний пристрій називають генератором послідовності чисел, побудованим на базі лінійного зсувного регістру зі зворотним зв'язком (linear feedback shift register, LFSR).
Як правило, в реальних кріптосхеми лінійний регістр зсуву зі зворотним зв'язком реалізується однієї з двох різних конструкцій, іменованих, відповідно, регістрами Фібоначчі і Галуа, але всі найбільш важливі теоретичні результати справедливі для обох типів.
Малюнок 2.4 - Генератор з регістром зсуву
.4.1 Регістри Фібоначчі
У літературі значно частіше звертаються до регістрів Фібоначчі. Функція зворотного зв'язку тут - просте додавання операцією XOR (виключає або) певних біт регістру. Пер...
