РАЗДЕЛ 2
ТЕОРЕТИЧЕСКОЕ ИССЛЕДОВАНИЕ СВОЙСТВ НЕЛИНЕЙНЫХ
ФУНКЦИЙ ОБРАТНОЙ СВЯЗИ ДЛЯ СДВИГОВОГО РЕГИСТРА,
ОБЕСПЕЧИВАЮЩИХ МАКСИМАЛЬНЫЙ ПЕРИОД ПОВТОРЕНИЯ
2.1.Теоретический анализ факторов, влияющих на эффективности
использования ПСДП для защиты информации
Генераторы ПСДП являются важным элементом защиты информации компьютерных систем
и сетей. По мнению К.Шеннона [45], такие генераторы являются даже основным
средством шифрования данных при их хранении или передаче. По Шеннону,
теоретически абсолютная секретность сообщения достигается при использовании
ключа, равного по длине передаваемому сообщению [45]. Исследования последних
лет [46] показали, что широкой класс алгоритмов защиты информации в явном или
неявном виде используют генераторы РСДП, которые генерируют последовательность
псевдослучайных бит, накладываемых на шифруемое сообщение. Инициирующим
вектором для таких генераторов является задаваемый пользователем ключ.
Все современные генераторы псевдослучайных последовательностей, ориентированные
для использования в системах защиты информации стоятся на основе общих
принципов [47]:
- расходимость - понятие, пришедшее из теории динамических систем и
заключающееся в том, что алгоритм генератора должен обеспечивать расходящуюся
последовательность двоичных n-разрядных слов, то есть последовательность, цикл
повторения которой стремится к 2n [48].
- нелинейность используемых функций преобразований, которая обеспечивает
сложность распознавания функций генерации псевдослучайной последовательности
[45].
- вычислительная сложность, введенная Колмогоровым [49,50] и она означает
вычислительную несжимаемость процедур генерации псевдослучайных
последовательностей.
Указанные принципы, сформулированные на теоретическом уровне, строго не
определены и частично перекрывают друг друга [51,52]. Понятие расходимости
часто практически используется, если в основу функционального преобразования,
лежащего в основе генератора положен один из частных случаев теории чисел [53].
Для битовых преобразований проблема расходимости, то есть обеспечения периода
повторения 2n-1, теоретически решена только для линейных функций обратной
связи: они должны быть изоморфными неразложимым полиномам на полях Галуа. Для
нелинейных функций битового преобразования, реализуемого проблема расходимости
имеет решения лишь для частных случаев [54].
В качестве критериев качества генераторов ПСДП, ориентированных на
использование в задачах защиты информации чаще всего используются следующие
показатели [17]:
- статистические критерии, которые позволяют оценить вероятностные
характеристики сгенерированной последовательности [55];
- критерии расходимости работы генератора - оцениваются минимальной длиной
возникающего при работе генератора цикла;
- непредсказуемость работы генератора - оценивается сложностью специального
алгоритма-распознавателя, позволяющего отличить генерируемую
последовательность от случайной [56].
- темп генерации ПСДП.
Весьма важным при рассмотрении этих критериев является принцип,
сформулированный в [57] и постулирующий, что критерий определения
псевдослучайности всегда определяется классом задач, в котором будет
использована эта псевдослучайность, то есть: использование должно определять
целевое распределение вероятностей с указанной степенью приближения и
значимость каждого из приведенных выше критериев.
Третьим из указанных выше критериев качества генераторов псевдослучайных
последовательностей является их алгоритмическая непредсказуемость, которая
оговаривает сложность алгоритма, который по данным предшествующих выборок может
предсказывать последующие значения [52]. С точки зрения надежности защиты
данных именно третий критерий является определяющим, поскольку все нарушения
защиты, осуществляемой с использованием ПСДП сводятся к экстраполяции последних
[57]. Анализ публикаций позволяет выделить два подхода для определения критерия
непредсказуемость ПСДП.
Первый из указанных подходов основывается на следующей модели. Задана одна
псевдослучайная выборка S длиной l бит. Для нее строится воспроизводящая
(интерполирующая) модель и по ее параметрам ее сложности оценивается
возможность эффективной экстраполяции заданной последовательности S. В
качестве воспроизводящей модели стандартом [55] предусмотрено использование
сдвигового регистра с линейной функцией обратной связи, соответственно, такая
модель называется линейной воспроизводящей моделью последовательности (ЛВМП).
Существует алгоритм [58] построения линейной воспроизводящей модели по заданной
последовательности. Длина h регистра называется линейной сложностью L(S)
последовательности S (linear complexity of sequences) [59]. Теоретически
доказано [60], что последовательность длиной в l бит, не может быть
экстраполирована, если длина h сдвигового регистра с линейной функцией обратной
связи, воспроизводящего эту последовательность удовлетворяет условию:
. (2.1)
Для аналогичной оценки непредсказуемости последовательности можно
использовать нелинейную сложность N(S), которая определяется через параметры
нелинейной воспроизводящей модели последовательности (НВМП), в качестве которой
используется сдвиговый регистр с нелинейной булевой функций обратной связи
[61]. В качестве параметра РВМП выступает m сдвигового регистра с нелинейной
обратной связью. Доказано [61], что, для последовательности S, которую нельзя
предсказать, ее нелинейная сложность N(S) нормально распределена с параметрами:
математического ожидания MN(S) и средн
- Київ+380960830922