Запреты двоичных функций: статья

УДК - 004021

Запреты двоичных функций

Бабаш А.В.

Известно (см., например, [1]), что в науке и технике и, в частности,
в
различных
системах
обеспечения
безопасности
широко
применяются
генераторы
псевдослучайных
последовательностей.
Так,
например,
эти
генераторы используются в синхронных поточных криптосхемах в качестве
управляющих блоков поточных криптосхем. Основные требования к таким
генераторам сформулированы в [2, стр. 247]. Одно из этих требований
состоит
в
том,
что
последовательность,
вырабатываемая
генератором,
должна
иметь
большой
период.
Другое,
не
менее
важное,
требование
состоит в том, что статистические свойства выходной последовательности
генератора должны приближаться к свойствам случайной равновероятной
последовательности.
В
частности,
последовательности
таких
генераторов
должны содержать любые возможные k-граммы выходного алфавита при
небольших значениях k. Имеет определенный смысл решение вопроса о
принципиальной возможности получения заданных мультиграмм в выходных
последовательностях
генераторов
псевдослучайных
чисел
или
решение
обратной
задачи
о
том,
какие
мультиграммы
в
принципе
не
могут
быть получены на выходе генератора, какова минимальная длина таких
мулътиграмм. Как показано в [2] может оказаться, что число различных
мультиграмм,
снимаемых
с
управляющих
блоков
шифратора,
которые
участвуют в образовании шифра шифрующего блока, мало. Это, очевидно, в
худшую сторону отразится на криптографической стойкости рассматриваемого
шифратора. Исследование поставленных вопросов стимулируется и другими
соображениями. Например, зная мультиграммы, которые не могут быть
получены с некоторого блока генератора псевдослучайных чисел, можно, при
применении методов определения ключей такого генератора, отбраковывать эти
ключи, что может повысить эффективность этих методов.
Если
моделировать
функционирование
генераторов
псевдослучайных
чисел автоматами, то естественно возникает задача описания автоматов,
позволяющих выработать любую конечную последовательность элементов
выходного алфавита. Такие автоматы называются автоматами генераторами.
Слова, составленные из выходного алфавита автомата, которые не могут
присутствовать в выходных последовательностях автомата обычно называют
запретами. Минимальную длину запретов называют длиной запрета автомата.
В [3, 4] доказано, что если перечисляющий автомат имеет |S| состояний,
то существует распознающий автомат имеющий не более 2|S| состояний. Из
этого утверждения следует, что каждый автомат, не являющийся автоматом
генератором, таков, что длина его запрета ограничена величиной 2|S| − 1.

1