Защита информации 2 5 (стр. 5 из 14)
С учетом свойств
определим понятия генератора случайной последовательности и его типов.Генератор РРСП – устройство, позволяющее по запросу получить реализацию равномерно распределенной случайной последовательности
длиной 
; элементы 
этой реализации принято называть случайными числами. Существует три типа генераторов РРСП:1. Табличный.
2. Физический.
3. Программный.
В следующем разделе мы рассмотрим программный генератор.
Программный генератор РРСП – программа имитации на компьютере реализации РРСП. Имитируемая последовательность
называется псевдослучайной, так как она вычисляется на компьютере по известному детерминированному (обычно рекуррентному) соотношению, и в то же время её статические свойства “близкие” к свойствам РРСП.В разделе “Алгоритмы генерации псевдослучайных последовательностей” мы познакомимся с основными методами генерации псевдослучайных последовательностей, а в разделе “Методы генерации истинно случайных последовательностей” мы рассмотрим различные методы повышения “случайности” генераторов РРСП.
3.2 Алгоритмы генерации псевдослучайных последовательностей.
Классификация существующих алгоритмов генерации псевдослучайных последовательностей представлена на рис. Выделяются три основных подхода к построению алгоритмов генерации:
1). Прямые методы построения элементарных рекуррентных последовательностей:
.2). Методы «улучшения элементарных последовательностей», заключающиеся в специальных функциональных преобразованиях этих последовательностей для уменьшения отклонения их статистических свойств от свойств РРСП.
3). Комбинирование алгоритмов генерации, построенных с помощью первого или второго подхода.
Линейные и мультипликативные конгруэнтные генераторы. Линейным конгруэнтным генератором (ЛКГ) с параметрами (
) называется программный генератор РРСП, порождающий псевдослучайную последовательность 
, 
, с помощью рекуррентного соотношения 
(3.2.1)Параметры этого генератора (3.2.1) имеют следующий смысл:
- начальное или стартовое значение; 
- не нулевой множитель; 
- приращение; 
- модуль, равный мощности алфавита 
.Если приращение
, то генератор ( 
) называется мультипликативным конгруэнтным генератором (МКГ), а если 
, то смешанным конгруэнтным генератором (СКГ).«Слабость» ЛКГ и МКГ заключается в том, что если рассматривать последовательные биграммы
, то точки 
, на плоскости 
будут лежать на прямых из семейства 
. Для устранения этого недостатка нелинейные конгруэнтные генераторы, среди которых известны: квадратичный конгруэнтный генератор; Генератор Эйхенауэра-Лена с обращением; конгруэнтный генератор, использующий умножение с переносом.Квадратичный конгруэнтный генератор. Этот алгоритм генерации псевдослучайной последовательности
определяется квадратичным рекуррентным соотношением 
, ( 
)где
– параметры генератора. Выбор этих параметров осуществляется на основе следующих двух свойств последовательности ( ).Свойство 
. Квадратичная конгруэнтная последовательность (
) имеет наибольший период 
, тогда и только тогда, когда выполнены следующие условия:1).
– взаимно простые числа;2).
– кратны 
, где – любой нечётный простой делитель 
;3).
– чётное число, причем 
4). Если
кратно 9, то либо 
, либо 
и 
.Свойство 
. Если
, то наибольший период 
тогда и только тогда, когда 
– нечётно, – чётно, 
– нечётное число, удовлетворяющее соотношению 
.Генератор Эйхенауэра-Лена с обращением. Псевдослучайная нелинейная конгруэнтная последовательность Эйхенауэра-Лена с обращением определяется следующим нелинейным рекуррентным соотношением
: 
( 
где
– обратный к 
элемент по модулю 
, т.е. 
- параметры генератора.Конгруэнтный генератор, использующий умножение с переносом. В этом случае нелинейная псевдослучайная последовательность определяется рекуррентным соотношением:
( 
Где в отличие от (
), «приращение» 
изменяется во времени и зависит от указанных аргументов нелинейно: 
( 
)Параметрами нелинейного конгруэнтного генератора (
), ( ) является 
.Рекуррентны в конечном поле. Обращение мультикапликативной конгруэнтной последовательности является линейная рекуррентная последовательность порядка
над конечным полем 
( 
- простое число):