Тестирование псевдослучайных криптографических генераторов на основе энтропийных статистик Тсаллиса

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Тестирование псевдослучайных криптографических генераторов на основе энтропийных статистик Тсаллиса

В.Ю. Палуха, Ю.С. Харин

НИИ прикладных проблем математики и информатики

Белорусского государственного университета

Минск, 220030, Беларусь

Введение

Выходные последовательности генераторов псевдослучайных чисел, которые используются в криптосистемах, должны быть неотличимы по своим вероятностным свойствам от равномерно распределённой случайной последовательности (РРСП). Для проверки качества криптографических генераторов в смысле близости к РРСП используются статистические тесты, суть которых заключается в следующем. Наблюдается выходная последовательность криптографического генератора и вводится гипотеза H* о том, что последовательность является РРСП. Вычисляется некоторая статистика, распределение вероятностей которой при истинной гипотезе H* известно. На основании значения статистики гипотеза H* принимается либо отклоняется.

Криптографические генераторы делятся на два основных типа: физические и программные. Последовательности физических генераторов, как правило, являются непредсказуемыми, что является необходимым условием для использования в криптосистемах, однако скорость работы физического генератора ограничивает их применение. Зачастую с помощью физического генератора вырабатывается лишь стартовое значение для программного генератора псевдослучайной последовательности. Поэтому задача тестирования псевдослучайных генераторов является актуальной [1]. В данном докладе рассматривается применение статистической оценки энтропии Тсаллиса в качестве тестовой статистики для анализа близости выходных последовательностей криптографических генераторов псевдослучайных последовательностей к модели РРСП.

Метод статистического тестирования

криптографический генератор псевдослучайный

Пусть на вероятностном пространстве (Щ, F, P) с множеством состояний Щ = {щ1, …, щN} определена случайная величина x = x(щ) = = щ с дискретным распределением вероятностей k = 1, …, N. Энтропия Тсаллиса определяется формулой [2]

(1)

Пусть имеется случайная последовательность объёма n из распределения вероятностей {pk}. Построим частотные оценки распределения вероятностей {pk: k = 1, …, N} с использованием факториальных степеней:

(2)

где s(r, i) - число Стирлинга первого рода [3]; по определению, при x < r полагают . Введём в рассмотрение гипотезу H* = {{xt} является РРСП} = {{xt} - н.о.р.с.в., , k = 1, …, N} и альтернативу . Статистическая оценка энтропии Тсаллиса (1) , построенная по подстановочному принципу с использованием частотных оценок вероятностей (2), записывается следующим образом:

 (3)

Рассмотрим асимптотику, в которой длительность наблюдения n и число значений N растут синхронно:

(4)

Справедлива теорема, доказанная в [2], об асимптотическом распределении вероятностей статистики (3).

Теорема. В асимптотике (4) статистика (3) является состоятельной асимптотически несмещённой оценкой энтропии Тсаллиса и при истинной гипотезе H* имеет асимптотически нормальное распределение :

где S(r, i) - число Стирлинга второго рода [3].

Следствие. При r = 2 для математического ожидания и дисперсии асимптотического распределения оценки (4) справедливы выражения:

(5)

Знание асимптотического распределения точечной оценки (3) позволяет построить интервальную оценку энтропии Тсаллиса: с вероятностью 1 - е энтропия

 , (6)

где Ц(·) - функция распределения стандартного нормального закона. Решающее правило, основанное на интервальной оценке (5), имеет вид:

принимается

(7)

Энтропийный анализ двоичных последовательностей. Для демонстрации применения решающего правила (7) проведены компьютерные эксперименты по вычислению оценок энтропии Тсаллиса при r = 2. Рассматривались последовательности нелинейного регистра сдвига (G1) с функцией обратной связи [4] 24-го порядка , прореживающего генератора (G2) с порождающим линейным регистром сдвига [1] с многочленом x13 + x8 + x5 + x3 + 1 и управляющим линейным регистром сдвига с многочленом x11 + x2 + 1, самосжимающего генератора (G3) на основе линейного регистра сдвига [1] с многочленом x24 + x11 + x5 + x2 + 1, последовательность алгоритма ГОСТ 28147-89, работающего в режиме гаммирования (G4), с нулевыми ключом и синхропосылкой. Все выходные последовательности «разрезаются» на непересекающиеся подряд идущие фрагменты длины s (s-граммы): . Из полученных s-грамм формируется новая последовательность {xt} из алфавита мощности N = 2s по правилу

Первая серия экспериментов проводилась на выходных последовательностях фиксированной длины T = 1Мбайт. Таким образом, при фиксированном T и с ростом s меняется значение л. На рисунках 1-4 для указанных выше четырёх псевдослучайных генераторов представлены графики зависимости нормированных отклонений оценки энтропии Тсаллиса (3) от асимптотического математического ожидания (5): , на уровне значимости е = 0.05 в зависимости от s. Зависимость л от s приведена на рисунке 5. Как видно из рисунков, статистические оценки энтропии Тсаллиса генераторов G1, G2, G3 выходят за границы интервала (-1; 1), что означает отклонение гипотезы о том, что наблюдаемая последовательность является РРСП. Возвращение внутрь доверительного интервала при больших значениях порядков s объясняется недостаточной длиной последовательности T. Что касается генератора G4, то выходы за границы доверительного интервала незначительны и позволяют принять гипотезу H* при s ? 23.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 1 - Нормированное отклонение оценки энтропии нелинейного регистра сдвига

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 2 - Нормированное отклонение оценки энтропии прореживающего генератора

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 3 - Нормированное отклонение оценки энтропии самосжимающего генератора

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 4 - Нормированное отклонение оценки энтропии алгоритма ГОСТ 28147-89

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 5 - Зависимость л от s в логарифмической шкале

Вторая серия экспериментов проводилась при фиксированном значении л = 2 (при каждом значении s совпадал начальный фрагмент рассматриваемой последовательности); результаты экспериментов представлены на рисунках 6-9. Как видно из рисунков, статистические оценки энтропии Тсаллиса генераторов G1, G2, G3 выходят за границы интервала (-1; 1), что означает отклонение гипотезы о том, что наблюдаемая последовательность является РРСП. Возвращение внутрь доверительного интервала при больших значениях порядков s объясняется недостаточной длиной последовательности T. Что касается генератора G4, то выходы за границы доверительного интервала незначительны и позволяют принять гипотезу H* при s ? 23.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 6 - Нормированное отклонение оценки энтропии нелинейного регистра сдвига

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 7 - Нормированное отклонение оценки энтропии прореживающего генератора

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 8 - Нормированное отклонение оценки энтропии самосжимающего генератора

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 9 - Нормированное отклонение оценки энтропии алгоритма ГОСТ 28147-89

Заключение

Разработанный тест на основе статистической оценки энтропии Тсаллиса позволяет обнаруживать отклонения выходных последовательностей псевдослучайных криптографических генераторов от модели РРСП, что обосновывает его применимость для оценки качества псевдослучайных генераторов.

Список литературы

1. Криптология / Ю. С. Харин [и др.]. - Минск: БГУ, 2013. - 512 с.

2. Палуха, В. Ю. Статистические тесты на основе оценок энтропии для проверки гипотез о равномерном распределении случайной последовательности / В. Ю. Палуха // Весці НАН Беларусі. Серыя фізіка-матэматычных навук. - 2017. - № 1. - С. 79-88.

3. Энвин, А. Ю. Дискретная математика: Конспект лекций / А. Ю. Энвин. - Челябинск: Издательство ЮУрГУ, 1998. - 176 с.

Размещено на Allbest.ru