Программный комплекс �«Энтропийный анализ дискретных последовательностей»
Белорусский государственный университет
НИИ прикладных проблем математики и информатики
Генераторы случайных и псевдослучайных последовательностей являются одним из элементов систем криптографической защиты информации (СКЗИ). Стойкость СКЗИ зависит от того, насколько близка генерируемая последовательность по своим свойствам к равномерно распределённой случайной последовательности (РРСП), которая на практике называется «чисто случайной» последовательностью.
Для проверки качества криптографических генераторов используются статистические тесты, в которых проверяется гипотеза H* = {{xt} является РРСП}} о том, что наблюдаемая последовательность {xt} является равномерно распределённой случайной последовательностью. В качестве тестовой статистики целесообразно использовать статистические оценки функционалов энтропии, среди которых одними из самых распространённых являются функционалы Шеннона, Реньи и Тсаллиса. Представленный программный комплекс позволяет вычислять оценки указанных функционалов энтропии дискретной последовательности и на их основе принимать или отклонять гипотезу о «чистой случайности» анализируемой последовательности, в т.ч. сложную нулевую гипотезу с помощью оценок энтропии Тсаллиса.
Актуальность разработки
Пусть на вероятностном пространстве (Ω, F, P) с множеством состояний Ω = {ω1, …, ωN} определена случайная величина x = x(ω) = ω с дискретным распределением вероятностей
Тип энтропии | Формула |
Энтропия Шеннона | |
Энтропия Реньи | |
Энтропия Тсаллиса | |
Функционалы энтропии
Математический аппарат
Оценка энтропии Шеннона на основе частотных статистик:
Параметры асимптотически нормального распределения при гипотезе H*:
Оценка энтропии Шеннона
Оценка энтропии Реньи на основе частотных статистик и факториальных степеней:
Параметры асимптотически нормального распределения при гипотезе H*:
Оценка энтропии Тсаллиса на основе частотных статистик и факториальных степеней:
Параметры асимптотически нормального распределения при гипотезе H*:
Оценки энтропии Реньи и Тсаллиса
Оценка энтропии Реньи на основе частотных статистик и факториальных степеней:
Параметры асимптотически нормального распределения при гипотезе H*:
Оценка энтропии Тсаллиса на основе частотных статистик и факториальных степеней:
Параметры асимптотически нормального распределения при гипотезе H*:
Оценки энтропии Реньи и Тсаллиса
На практике возможны незначительные отклонения распределения вероятностей тестируемой последовательности от s-мерной равномерности. Определим сложную нулевую гипотезу :
Параметры асимптотически нормального распределения оценки энтропии Тсаллиса при сложной нулевой гипотезе:
Сложная гипотеза для энтропии Тсаллиса
Решающее правило (простая гипотеза)
Решающее правило (простая гипотеза)
Решающее правило (сложная гипотеза)
Энтропийный профиль
В НИИ ППМИ разработан программный комплекс, который позволяет вычислять оценки энтропии Шеннона, Реньи и Тсаллиса, их асимптотические параметры распределений вероятностей при гипотезе H*, p-значения и энтропийные профили для двоичных файлов. Помимо вывода самих значений, программа выводит графики зависимостей этих величин от длины фрагмента s.
В начале работы необходимо выбрать файл с последовательностью, порядок Big Endian или Little Endian, диапазон s и функционалы энтропии. Вычисляемые значения добавляются на экран в режиме реального времени. Имеется возможность изменять уровень значимости α без пересчёта оценок энтропии и переключаться на различные режимы отображения: непосредственно оценки энтропии , нормированные значения χ, p-значения. В случае выбора оценки энтропии Тсаллиса и сложной гипотезы необходимо задать значение ε+.
Программный комплекс
Научно-исследовательский институт прикладных проблем математики и информатики
Белорусский государственный университет
☏ +375 17 209 51 04, +375 17 209 55 49
🖂 apmi@bsu.by
Контакты