Случайности Не Случайны?

Аннотация Статья посвящена систематизации основных положений о случайных и псевдослучайных последовательностях (СП и ПСП) чисел.

Дан краткий обзор известных подходов к проверке случайности генерируемых последовательностей.

Прикладная значимость данной темы определяется тем, что ПСП широко используются в криптографических системах защиты информации для формирования ключевой и вспомогательной информации (случайных чисел, векторов инициализации и т.п.

Введение С древних времен не только математики изучали случайность.

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

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

Этот тезис легко проиллюстрировать с помощью центральной предельной теоремы (и других теорем) теории вероятностей.

Стоит отметить особенность систем случайных объектов, которая может показаться в определенном смысле парадоксальной.

Гораздо чаще удается описать или хотя бы предсказать глобальные, а не локальные закономерности больших систем.

Это определяет два безусловно популярных современных направления исследований: поиск глобальных закономерностей случайных систем и обоснование непредсказуемости локальных событий для случайной системы.

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

Случайные последовательности SP играют важную роль в криптографии; они используются для формирования ключевых и начальных параметров криптографических алгоритмов, а также последовательностей шифровальных подстановок в потоковых криптосистемах.

Случайность и криптография тесно связаны: основная цель криптографических систем — преобразовать неслучайный, содержательный открытый текст в явно случайную последовательность символов зашифрованного текста.

Это свойство криптосистем используется для генерации PSP. Наилучшие криптографические свойства криптосистемы достигаются при использовании так называемого идеальные случайные последовательности (ISP), математическая модель которой представлена реализацией последовательности независимых случайных величин, имеющих равномерное распределение вероятностей на заданном конечном алфавите.

Такие последовательности еще называют равномерно распределены (на некотором конечном множестве) случайные последовательности (РРСП).

Описанию свойств RRSP посвящено множество работ, в частности, [1], [4], [5] и [7].

Подходы к определению термина «случайность» Существуют различные подходы к формальному определению термина «случайность», основанные на понятиях вычислимости и алгоритмической сложности [2].

Исторически первый подход частота , предложенная фон Мизесом в начале XX века и развитая Чёрчем, Колмогоровым и Лавлендом.

Идея частотного подхода состоит в том, что в СП должны наблюдаться стабильность частоты встречаемости элементов .

Например, знаки 0 и 1 должны встречаться независимо и с равными вероятностями не только в самой бинарной ИП, но и в любой ее подпоследовательности, выбранной независимо от начальных условий генерации.

Другой подход сложный , предложенная независимо Колмогоровым и Чайтиным, основана на том, что любое описание реализации совместного предприятия не может быть существенно короче самой этой реализации.

То есть совместное предприятие должно иметь сложную структуру, и энтропия ее начальные элементы должно быть здорово.

С помощью этого подхода показано, что последовательность является случайной, если ее алгоритмическая сложность близка к длине последовательности.

Третий подход количественный , разработанный Мартином-Лофом.

Он заключается в разделении вероятностного пространства последовательностей на неслучайные и случайные (последних относительно много).

Последовательности, в которых наблюдаются какие-либо закономерности, считаются неслучайными.

Последовательность считается случайной, если она проходит набор определенных тестов, предназначенных для выявления закономерностей.

Однако если вы потребуете, чтобы последовательность прошла какой-либо статистический тест, окажется, что SP вообще не существует. На практике используется определенный набор тестов, где доля не удовлетворяющих им ПП стремится к 0 при неограниченном увеличении длины последовательностей.

В последние десятилетия в связи с требованиями, возникающими в криптографических приложениях, криптографический подход к определению СП, при котором последовательность считается случайной, если вычислительная сложность поиска закономерностей не меньше заданного значения.

Этот подход согласуется с существующим системным подходом к определению стойкости криптографических систем.

Эти подходы к определению случайности имеют недостатки.

Частотный подход на практике осложнен неопределенностью правил выбора подпоследовательностей; подход сложности влечет за собой необходимость уменьшения избыточности языка программирования.

Использование количественного подхода затруднено определением разнообразия тестов, которые следует применять к изучаемым последовательностям.

Нижние оценки сложности криптографического подхода ориентированы на набор известных тестов и могут со временем пополняться, что приводит к завышению оценки сложности.

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

PSP-тестирование Проверенный (Херринг, К.

, Палмор, Дж.

И.

Генераторы случайных чисел хаотичны, 1995), что любая алгоритмическая реализация последовательности несовершенна, то есть истинно случайная последовательность не может быть вычислена по какому-то правилу и, следовательно, она должна быть непериодической бесконечной последовательностью.

Последовательности, генерируемые по определенному правилу, имитирующие RRSP, называются псевдослучайные последовательности (ПСП).

Под успешной имитацией понимается близость ряда характеристик создаваемого ПСП к аналогичным характеристикам ИСП.

Генерация PSP, используемых в криптографических приложениях, основана на реализации множества итераций определенного преобразования конечного множества X (часто X представляет собой набор двоичных n-мерных векторов).

Эта выходная последовательность является периодической.

Однако продолжительность периода может быть весьма большой; это гарантируется, в частности, использованием линейных регистров сдвига с примитивными характеристическими полиномами.

Для многих генераторов PSP были доказаны хорошие статистические свойства и высокая линейная сложность, большая длина периода, но часто невозможно доказать аналитические и статистические свойства.

Затем статистические тесты используются для обоснования многих свойств.

Разнообразие критериев оценки ПСП чрезвычайно велико.

Каждый из подходов к анализу последовательностей можно отнести к одной из двух групп.

Первая группа связан с поиском закономерностей, позволяющих воспроизвести последовательность из ее короткого отрезка.

В этом случае основные требования к последовательности сводятся к отсутствию в ней относительно простых межзнаковых зависимостей.

Вторая группа Критерий связан с оценкой статистических свойств последовательности: имеется ли в исследуемой последовательности частотный дисбаланс, позволяющий аналитику предсказать следующий (предыдущий) символ из известного сегмента последовательности, то есть предположить значение следующего (предыдущего) бита с вероятностью большей, чем при случайном выборе? Основные требования к ПСП по второй группе критериев заключаются в том, чтобы ряд ее статистических свойств соответствовал свойствам ПСП; в частности, частота встречаемости как отдельных символов, так и s-грамм должна быть равномерно распределена в ПСП при достаточно больших значениях s. При системном подходе для анализа последовательности используются известные тесты, а новые тесты разрабатываются с учетом характеристик анализируемого объекта.

Если в ходе анализа в определенном классе последовательностей обнаруживается новая слабость, то разрабатывается соответствующий новый тест, расширяющий существующий набор известных тестов.

Обе группы методов анализа последовательностей представляют собой системный подход к анализу PSP, в частности, к разработке потоковых шифров.

Одну из первых формулировок основных требований к статистическим свойствам периодических бинарных ПСП дал С.

Голомб.

Эти требования к последовательности известны в криптографии как Постулаты Голомба (Голомб С.

В.

Последовательности регистров сдвига, 1967).

Постулаты Голомба изложены, в частности, в монографии [7].

Постулаты основаны на условии сохранения положительных статистических свойств, присущих линейным рекуррентным последовательностям с максимальной длиной периода.

Правила Голомба не гарантируют высокого качества PSP и скорее необходимы.

На практике использование постулатов Голомба для оценки качества ПСП затруднено из-за сложности теоретического расчета длин периодов ПСП, частот s-грамм за период, а также значений автокорреляционной функции.

Расчет на ЭVM возможен только для PSP с малой длиной периода, что ограничивает использование постулатов Голомба в криптографических приложениях.

Цель и задачи статистического тестирования ПСП Проверка PSP на случайность — это способ выявить определенные его свойства путем сравнения характеристик PSP с аналогичными характеристиками интернет-провайдера.

С помощью статистического тестирования PSP решаются следующие задачи: 1) оценка свойств выходной последовательности генератора PSP с точки зрения использования в криптографическом алгоритме (например, в качестве секретного ключа); 2) оценка качества криптографических примитивов (хеш-функций, блочных и потоковых шифров) на основе их выходных последовательностей, которые должны быть неотличимы от ICP, в частности проверка таких криптографических свойств, как лавинный эффект изменения выходных данных.

данные алгоритмов из-за искажений, корреляции промежуточных и выходных последовательностей; 3) идентификация генераторов PSP, генерирующих «неслучайные» последовательности; разработка новых генераторов ПСП; проверка корректности реализации генераторов PSP. Суть тестирования обычно сводится к проверке так называемой «нулевой гипотезы» H0 относительно последовательности x(k)=(x_1,.

,x_k) длины k, согласно которой x был получен на основе k независимые испытания вероятностной схемы с равномерным распределением.

В общем, статистический тест T представляет собой двузначную функцию.

, где A* — множество последовательностей в алфавите A. Статистический тест T делит множество V(k) последовательностей длины k на множество V(k,0) «неслучайных» последовательностей (обычно относительно небольших) и множество V(k,1)= V(k)/V(k,0) случайных последовательностей.

Вероятность P того, что тест отклонит случайно выбранную двоичную последовательность x(k), равна V(k,0)/2^k. Как правило, в реальных испытаниях Р не превышает 0,01. Трудность точного вычисления Т-функции велика из-за громоздкой области определения.

Поэтому статистическая проверка на принятие/отвержение гипотезы H0 осуществляется с использованием статистики f_T, то есть относительно простой вычислимой функции, отображающей набор последовательностей на набор действительных чисел, и вероятностного распределения статистики для гипотезы H0, определяемого методами теории вероятностей.

Статистический тест — это комбинация статистики, рассчитанной на основе исходных данных, и правила принятия решения, согласно которому значение статистики определяет, следует ли принять или отвергнуть гипотезу H0. Статистический тест является вероятностным, то есть возникают ошибки двух типов, которые являются важными характеристиками теста: 1) ошибка а первого рода, если последовательность случайная, но H0 отбрасывается; 2) ошибка b второго рода, если последовательность неслучайная, но принимается H0. Решение о прохождении статистической тестовой последовательности принимается на основе различных критериев [7].

На основе порогового значения .

Подход основан на вычислении тестовой статистики f_T(x(k)) для заданной последовательности x(k) и последующем ее сравнении с некоторым пороговым значением c(k).

Согласно критерию, двоичная последовательность x(k) не проходит статистический тест, если f_T(x(k)) На основе фиксированного доверительного интервала .

При таком подходе последовательность x(k) не проходит статистическую проверку, если f_T(x(k)) находится за пределами доверительного интервала статистики, рассчитанной для данного уровня значимости a. При более низких уровнях значимости ширина доверительного интервала больше.

Этот критерий более надежен по сравнению с первым.

На основе расчета p-значение .

Третий класс критериев основан на вычислении тестовой характеристики из отрезка [0,1], называемой p-значение.

Тестовая статистика, рассматриваемая как случайная величина с известным законом распределения, строится так, что большие значения указывают на некоторый дефект случайности последовательности.

Вероятностное значение p — это вероятность того, что статистика теста примет значение, большее, чем наблюдаемое во время эксперимента, при условии, что последовательность является случайной.

То есть малые значения p соответствуют неслучайности последовательности.

Правило принятия решения: на уровне значимости a последовательность x(k) не проходит статистический тест, если значение p a, то тест пройден.

Существующие инструменты статистического тестирования PSP Для выявления закономерностей к анализируемым ПСП (а также к их сегментам различной длины) применяется широкий спектр различных статистических тестов.

В последние десятилетия было разработано большое количество тестов для анализа ПСП.

Вот некоторые известные наборы статистических тестов: 1. 11 тестов: Дональд Кнут (Стэнфордский университет), Искусство компьютерного программирования, том.

2 получисловых алгоритма, www-cs-faculty.stanford.edu/~uno/taocp.html 2. 15 тестов: Андрей Рухин и др.

ал.

(NIST ITL), пакет статистических тестов NIST, csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html 3. 12 тестов: Джордж Марсалья (Университет штата Флорида), DIEHARD, stat.fsu.edu/pub/diehard 4. 11 тестов: Пьер Л'Экуйер, Ричард Симард (Отдел информатики и исследовательских операций Университета Монреаля), TestU01, www.iro.umonreal.ca/~simardr/testu01/tu01.html 5. 5 тестов: Хелен Густафсон и др.

al.(Технологический университет Квинсленда), Crypt-XS, коммерческая версия, www.qut.edu.au/institute-for-future-environments Существуют и другие описания и реализации статистических тестов, во многом повторяющие тесты из наборов, представленных выше: 1. Альфред Менезес и др.

, Справочник по прикладной криптографии.

2. Питер Хеллекалек (Университет Зальцбурга), Проект pLab, Random.mat.sbg.ac.at 3. Джон Уокер (Autodesk, Inc.), ЛОР, www.fourmilab.ch/random 4. Роберт Дж.

Браун (Университет Дьюка), Дихардер, www.phy.duke.edu/~rgb/General/dieharder.php 5. Джордж Марсалья (Университет штата Флорида), Вай Ван Цанг (Университет Гонконга), «Дистиллированная» версия Дихарда, www.jstatsoft.org/v07/i03 Несмотря на значительное количество существующих реализаций статистических тестов PSP, это направление постоянно развивается, и в настоящее время активно появляются новые проекты, предлагающие новые реализации рассматриваемых тестов, в том числе в условиях распределенных вычислительных систем.

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

Пакет NIST STS более гибок, расширяем и эффективен (с точки зрения времени тестирования) и является наиболее полным пакетом, доступным для статистического тестирования двоичных последовательностей (более подробно см.

[5], [8], [9]).

Тесты пакета NIST STS подробно рассмотрены в статье «Статистические тесты случайных чисел с использованием методов NIST».

habrahabr.ru/company/securitycode/blog/237695 [3].

На основе пакета NIST STS могут быть разработаны методы более полного статистического и структурного анализа последовательностей с учетом того, что для достоверной оценки качества генерируемой генератором PSP целесообразно проводить не один , но несколько тестов.

Все тесты направлены на выявление различных дефектов случайности.

Более подробную информацию об обнаруженных дефектах случайности можно найти в [8].

На практике принятие или отклонение нулевой гипотезы основывается на результатах нескольких независимых тестов.

Когда независимые тесты приводят к разным выводам, используется комбинация результатов тестов с использованием статистики, учитывающей совокупность результатов всех использованных тестов.

Когда количество объединяемых тестов невелико, используется статистика Фишера-Пирсона и сравнивается с распределением хи-квадрат. Если количество комбинированных тестов велико, то рекомендуется использовать критерий Колмогорова-Смирнова.

В таблице 1 показаны некоторые тесты, рекомендуемые для тестирования PSP различной длины.

Таблица 1. Статистические тесты для PSP различной продолжительности

Случайности не случайны?

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

Список использованной литературы 1. Агибалов Г.

П.

Избранные теоремы начального курса криптографии.

Руководство.

Томск: Издательство НТЛ, 2005. – 116 с.

2. Архангельская А.

В.

Построение высокоскоростных квантовых генераторов случайных чисел для систем информационной безопасности.

Диссертация на соискание ученой степени кандидата технических наук, Москва, 2008. – 182 с.

3. Блог о кодах безопасности: Статистические тесты случайных чисел с использованием методов NIST. – habrahabr.ru/company/securitycode/blog/237695 4. Варфоломеев А.

А.

, Жуков А.

Е.

, Пудовкина М.

А.

Потоковые криптосистемы.

Основные свойства и методы анализа устойчивости.

Учебник, М.

: ПАИМС, 2000. – 272 с.

5. Вильданов Р.

Р.

, Мещеряков Р.

В.

, Бондарчук С.

С.

Тесты псевдослучайных последовательностей и программное обеспечение, их реализующее // Математическое обоснование и теоретические аспекты информационной безопасности.

– www.tusur.ru/filearchive/reports-magazine/2012-25-2/108.pdf 6. Потий А.

В.

, Орлова С.

Ю.

, Гриненко Т.

А.

Статистическое тестирование генераторов случайных и псевдослучайных чисел с использованием набора статистических тестов NIST STS. 7. Фомичев В.

М.

Методы дискретной математики в криптологии, М.

: Диалог-МИФИ, 2010. – 424 с.

8. Рухин А.

, Сото Дж.

, Нечватал Дж.

, Смид М.

, Баркер ?.

, Ли С.

, Левенсон М.

, Вангель М.

, Бэнкс Д.

, Хеккерт А.

, Дрей Дж.

, Во С.

Набор статистических тестов для генераторов случайных и псевдослучайных чисел для криптографических приложений.

– www.csrc.nist.gov/publications/nistpubs/800-22/sp-800-22-051501.pdf .

9. Сото Хуан, Статистическое тестирование генераторов случайных чисел, Национальный институт стандартов и технологий.

– csrc.nist.gov/groups/ST/toolkit/rng/documents/nissc-paper.pdf Теги: #Криптография #статистика #тестирование #последовательности #критерии #случайные числа #шаблоны #Криптография #Системное программирование #Алгоритмы #Функциональное программирование