Федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский ядерный университет «МИФИ», г. Москва, Россия В статье обсуждаются вопросы исследования свойств генераторов псевдослучайных чисел (ГПСЧ). Определяется роль ГПСЧ при построении компьютерных систем, в том числе защищенных. Перечисляются наиболее значимые задачи, решаемые с использованием генераторов. Приводятся требования, предъявляемые к качественным ГПСЧ, обсуждаются проблемы, возникающие при оценке их непредсказуемости. Рассматривается один из вариантов решения данных проблем, заключающийся в сведении задачи построения криптостойкого ГПСЧ к задаче построения статистически безопасного генератора. Определяются требования к статистически безопасному ГПСЧ. Показана необходимость комплексного исследования статистических свойств формируемых ГПСЧ последовательностей. Анализируются существующие наборы статистических тестов, выявляются их недостатки, не позволяющие осуществлять полнофункциональное тестирование псевдослучайных последовательностей. В частности, подвергается критике методика оценки результатов прохождения тестов, не обладающая должной гибкостью в вопросах совместного использования частных оценок конкретного теста и совокупной оценки результатов прохождения набора тестов. Формулируются требования к качественной системе оценки статистической безопасности ГПСЧ. Показана необходимость использования графических тестов наряду с оценочными. Предлагается структура полнофункциональной системы оценки статистической безопасности ГПСЧ и криптоалгоритмов, определяется назначение входящих в нее модулей, приводятся примеры работы системы. Также рассматриваются возможные пути повышения эффективности оценочных тестов, в частности, обсуждаются вопросы сокращения объемов необходимой для реализации теста памяти, а также возможность повышения быстродействия тестов и одновременного тестирования нескольких последовательностей за счет использования гибридных технологий (совместного использования вычислительных ресурсов центрального процессора и ядер графических видеокарт).
reducing the problem of cryptographically strong PRNG constructing to the task of statistically secure generator constructing is considered. Requirements to statistically secure PRNG are defined. Need of complex statistical properties assessment of sequences formed by PRNG are shown. Sets of existing statistical tests are analyzed, its disadvantages which aren’t allows to carry out full-function pseudorandom sequences testing are revealed. In particular, the passing tests estimation method without adequate flexibility in question of concrete test private estimate and tests set passing results cumulative assessment sharing are criticized. Requirements to PRNG’s quality assessment systems are formulated. The need of graph test using along with estimated is shown. The structure of full-function PRNG statistical safety assessment system is offered, the assignment of modules entered it is defined and examples of system work are proposed. Possible ways to improve assessment test are also considered. In particular, the decreasing of memory volumes needed for the test implementation as well as the possibility of test speed increasing and several sequences simultaneous testing due to hybrid technology using (sharing of central processor computing resources and graphic video cards kernels) are discussed.
Pseudo-random number generators; statistical tests; quality assessment system.
Однои из основных характеристик любои компьютернои системы, независимо от ее уровня
сложности и функционального назначения, является безопасность процессов сбора, хранения,
обработки и передачи информации. Важнеишую роль в реализации данных процессов играют
генераторы псевдослучаиных чисел (ГПСЧ), которые используются для решения следующих задач
[
Таким образом, возникает актуальная задача разработки методов и средств оценки
статистическои безопасности стохастических алгоритмов, то есть алгоритмов, основанных на
использовании ГПСЧ. Более того, данныи подход можно применять и к оценке качества
криптографических алгоритмов. Не случаино при проведении конкурса AES (Advanced Encryption
Standard), победителем которого стал Rijndael [
Можно выделить следующие активно использующиеся системы оценки статистических
своиств ГПСЧ:
A statistical test suite for random and pseudorandom number generators for cryptographic
applications Национального института стандартов и технологии США (Руководство NIST)
[
Однако, для полнофункционального исследования ГПСЧ данных систем недостаточно. Связано это с тем, что все вышеупомянутые системы имеют жестко заданные параметры тестирования. В результате, система может просто не поддерживать анализ определенного типа неслучаиности, требуемыи пользователю, или поддерживать, но не применительно к заданным параметрам генератора.
Еще однои проблемои существующих систем является ориентированность последних на генераторы определенного вида. К примеру, DIEHARD предназначен для исследования 32разрядных конгруэнтных генераторов, и большинство его тестов рассматривают наборы, состоящие именно из 32-разрядных чисел. Руководство НИСТ требует, чтобы исследуемая последовательность была битовои. Предположим, необходимо оценить статистические своиства 8разрядного генератора. Как в этом случае формировать последовательность для тестирования? Ни одна из существующих систем никаких рекомендации на этот счет не дает. В результате, при тестировании системои DIEHARD или Руководством НИСТ могут быть упущены некоторые особенности, присущие 8-разрядным генераторам и выявляемые только тестами, ориентированными именно на 8-разрядные последовательности. Разрабатывать же генераторы, формирующие последовательности, подходящие для тои или инои системы, также неправильно, так как генератор предназначен для решения других задач, и это система тестирования должна подстраиваться под структуру генератора, а не наоборот.
Таким образом, процесс создания средства для исследования ГПСЧ является чрезвычаино
сложным и требует учета разного рода нюансов и факторов. Можно сформулировать следующие
требования к системе оценки качества ГПСЧ, позволяющеи еи быть не только эффективнои, но и,
насколько это возможно, универсальнои:
наличие эмпирических и теоретических критериев. Процесс тестирования
последовательностеи занимает значительное время, особенно в случае
последовательностеи большои длины. Теоретические критерии позволяют дать
заключения о своиствах генератора еще до тестирования последовательностеи,
следовательно, их наличие позволит сразу отбраковать генераторы с параметрами,
заведомо приводящими к неудовлетворительным результатам. К сожалению,
теоретические критерии ориентированы на генераторы конкретного типа, а иногда даже и
на конкретные параметры данных генераторов, и поэтому могут быть непригодны для
тестирования остальных генераторов. Собственно говоря, именно этим фактом и
объясняется необходимость создания собственнои системы для тестирования нового
генератора. Одним из вариантов универсализации системы является создание и
пополнение базы данных теоретических критериев, а затем обмен полученными данными
с другими пользователями. Идеальным вариантом было бы создание сетевои или
распределеннои базы данных теоретических критериев, пополняемои пользователями.
При наличии двух типов критериев пользователю, наряду с непосредственно
последовательностью, необходимо будет ввести параметры генератора, ее
сформировавшего. Сначала данные параметры обрабатываются при помощи теоретических
критериев, отфильтровывая тем самым заведомо некачественные последовательности;
оставшиеся после фильтрации последовательности обрабатываются при помощи
эмпирических критериев;
наличие оценочных и графических тестов. И те, и другие тесты играют важную роль в
исследовании статистических своиств последовательности. Оценочные тесты возвращают
результат своеи работы в виде численнои статистики, позволяя тем самым
автоматизировать процесс тестирования. Кроме того, данные значения можно сопоставить
с аналогичными показателями для других последовательностеи, проведя тем самым
сравнительныи анализ генераторов. Графические же тесты позволяют увидеть общую
картину, а кроме того, как показано в ряде работ [1; 9], позволяют выявить статистические
слабости, не обнаруживаемые статистическими тестами. Также графические тесты могут
использоваться для оценки изменении, вносимых нелинеиными преобразованиями, а
также для оценки автокорреляции и корреляции между последовательностями;
градация тестов по их силе. При анализе последовательности может использоваться
несколько десятков тестов. Выполнение каждого теста требует некоторого времени,
которое для некоторых тестов (например, «Сжатие при помощи Алгоритма Лемпела-Зива»)
может быть значительным. В ряде случае для получения заключения о своиствах
генератора необходимо провести исследование сотен или тысяч последовательностеи.
Таким образом, время до получения предварительных итогов исследования может быть
значительным. Данное время можно сократить, если ввести градацию тестов по их силе.
Более того, можно вести категории для тестов, например «быстрыи», «медленныи»,
«обязательныи», «вспомогательныи». Это позволит ввести политику тестирования.
Например, вначале выполняются «быстрые обязательные» тесты, то есть тесты,
непрохождение которых однозначно свидетельствует о непрохождении других тестов
(например, если не проиден «частотныи тест», то не будут проидены «проверка серии»,
«проверка равномерности» и так далее). При успешном прохождении «быстрых
обязательных» тестов будут выполняться тесты следующеи категории и так вплоть до
самых сложных специфических тестов. Каждую категорию тестов также можно
проранжировать, останавливая тестирование в случае неудачных результатов для даннои
категории или реализую ветвящееся тестирование, когда выбор следующеи категории
зависит от результатов выполнения текущеи;
наличие средств оценки периода тестируемои последовательности. Возможны ситуации,
когда в последовательности заданнои длины содержится несколько периодов,
предпериоды, вырожденные циклы и так далее. Для генераторов, ориентированных на
использование в системах ответственного назначения, краине нежелательны повторения в
гамме, поэтому необходимо отслеживать, чтобы в формируемои последовательности не
было периодичности. Кроме того, в случае периодичности тест работает вхолостую – ведь
он фактически дублирует тут статистику, которую уже собрал в предыдущем периоде.
Поэтому основное, с чего нужно начать исследование последовательности – это
определение периода. В том случае, если система оценка качества является надстроикои
над генератором, проблем с определением периода нет – расстояние в тактах между двумя
повторяющимися внутренними состояниями генератора и будет период. Несколько
сложнее определить период, анализируя непосредственно последовательность. В качестве
одного из вариантов определения периода в данном случае можно предложить следующии.
Запоминается первыи элемент последовательности. Двигаясь по последовательности,
находим элемент, равныи первому. Анализируем следующии за ним, сравнивая со вторым и
так далее до конца последовательности. Если все соответствующие элементы совпадают,
это означает наличие периодичности. В данном случае необходимо определить значение
периода и при тестировании анализировать только элементы, входящие в период,
предварительно выдав информационное сообщение. Данныи подход может не сработать в
случае наличия предпериода или вырожденных циклов, поэтому имеет смысл сделать
несколько испытании, например, проити от конца последовательности к началу или начать
анализ с заданного элемента последовательности. Для того, чтобы сократить время
тестирования, рекомендуется включить оценку периода в один из обязательных
последовательных тестов, например, в «Проверку равномерности». Данныи тест
последовательно обрабатывает элементы последовательности, соответственно, может
заодно осуществлять определение периодичности;
определение области тестирования. В ряде случаев имеется необходимость тестировать не
всю последовательность, а ее часть (например, предпериод или период), или же отдельные
части элементов последовательности (например, младшие биты каждого элемента). Для
реализации даннои возможности в составе системы должен быть модуль, позволяющии
определять начальную и конечную точку тестирования, значения интервалов в том случае,
если элементы последовательности анализируются не последовательно, а через
определенные расстояния и так далее. Данныи модуль должен быть связан со средствами
оценки периода, чтобы иметь возможность задавать в качестве области тестирования
период или предпериод.
настроики параметров тестов. Каждыи тест анализирует число появлении/отсутствия
определенного набора, которыи, в свою очередь, может состоять из поднаборов. Кроме того,
тест для получения статистики или статистик, может оперировать несколькими такими
наборами. В системе должно быть предусмотрено средство, максимально гибко
позволяющее настраивать конфигурацию теста. Например, для теста «проверка серии»
данная конфигурация может содержать следующие поля:
разрядность серии: 1, 2, …, разрядность элемента последовательности;
серии смежные/несмежные
последовательность анализируется целиком и/или разбивается на блоки и тест
применяется к блоку, в последнем случае необходимо также определить параметры
блока;
уровень значимости теста.
расширения для проверки категории;
расширения для проверки отсутствующих наборов;
настроики параметров тестирования. Данныи блок определяет всю политику
тестирования. Указывается, в каком порядке применяются тесты, для каких областеи,
уровень значимости один для всех тестов или для каждого индивидуальныи и так далее.
Максимальная проработка блока настроек параметров тестов и параметров тестирования
обеспечит наиболее эффективное исследование генератора;
наличие тестов с проверкои категории. Большинство тестов возвращают интегральную
оценку результатов исследовании, при этом зачастую сглаживаются локальные
статистические отклонения. Для выявления этих отклонение необходимо оценивать не
только конечную статистику теста, но и промежуточные статистики. Большинство
существующих систем скрывают данные значения, чтобы не перегружать пользователя
излишнеи информациеи, однако данная статистика участвует в определении интегральнои
оценки, а, следовательно, вычисляется, так что получение данных оценок никак не скажется
на производительности тестов;
возможность получения интегральнои оценки. Данное требование решает обратную задачу.
В ходе исследовании может анализироваться сотни и тысячи последовательностеи, причем
каждая последовательность набором из нескольких десятков тестов. Для ускорения
процесса анализа желательно ввести интегральную оценку, которая оценит как
прохождение последовательностью набора тестов, так и прохождение испытания
генераторов. Каждыи тест возвращает значение P-value, равномерно распределенное на
интервале [
Структурную схему программного комплекса для оценки качества стохастических и кроптографических алгоритмов можно представить следующим образом (рис. 1).
File_1 File_N Файловый блок Блок настроек ГГГрррааафффииччеескскиииеее
ическ тттееесстсттыыы ГОГррцааеффниоиччченесысккеииее
тттееесстсттыыы Блок управления Система оценки периода Система оценки корреляции Тестовый блок Блок формирования отчета Рис. 1. Структура программного комплекса для оценки качества стохастических и криптографических алгоритмов
В состав комплекса входят следующие блоки: фаиловыи блок. Данныи блок предназначен для считывания последовательностеи из фаилов и передачи их для обработки в тестовыи блок; тестовыи блок. Данныи блок служит для анализа статистических своиств формируемых ГПСЧ последовательностеи. В его состав входят три модуля: система оценки качества – набор графических и оценочных тестов; система оценки периода. Данная программа определяет период анализируемои последовательности. Результаты работы данного модуля используются системои оценки качества для определения длины анализируемого фрагмента последовательности; система оценки корреляции. Данная программа предназначена для определения значения корреляции между фаилами; блок настроек. Данныи блок предназначен для определения имен тестируемых фаилов или директории, а также параметров тестов (границ для P-value, размеров серии и т.д.) и параметров тестирования (размера области тестирования, набора тестов и т.д.); блок отчета. Данныи блок предназначен для просмотра, записи и печати результатов тестирования; блок управления. Данныи блок служит для согласованнои работы всех блоков устроиств и для организации взаимодеиствия с пользователем.
В настоящее время реализована большая часть данного программного комплекса, а именно: система оценки качества (все тесты Руководства NIST, DIEHARD, Д.Кнута, CRYPT-X, как оригинальные, так и модифицированные, графические тесты, собственные оценочные и графические тесты), система оценки корреляции, система обнаружения периодичности. Примеры работы программного комплекса приведены на рис. 2-3. Рис. 2. Примеры графических тестов Рис. 3. Пример общего отчета о тестировании генератора
287
В качестве дальнеиших направлении исследовании можно предложить следующие:
уменьшение объема памяти, требуемои для реализации теста. Практически все оценочные
тесты производят расчет тестовои статистики на основе частоты встречаемости того или
иного вида шаблона. Соответственно, чем длиннее тестируемая последовательность, тем
большии объем памяти необходим для хранения числа появлении шаблона определенного
типа. Рано или поздно может наступить ситуация, когда размер необходимои для
реализации теста памяти превысит предельныи размер памяти вычислительнои системы,
что автоматически приведет к невозможности выполнения теста. В качестве варианта
решения даннои проблемы можно предложить вычисление промежуточных результатов,
либо подсчет числа отсутствующих шаблонов [
References