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

Актуальность темы

*. Случайные и псевдослучайные числа широко используются в самых различных областях науки и техники. Они очень важны в математическом моделировании, в разработке численных методов, в программировании, криптографии и т. п. И если раньше ученые, нуждающиеся для своей работы в случайных числах, раскладывали карты, бросали кости или вытаскивали шары из урны, которую предварительно «как следует трясли» [10], то сейчас генератор случайных чисел встроен в любой компилятор и процессор компьютера. Например, Intel использует генератор случайных чисел в процессорах со второго полугодия 1999 года [7]. Однако, такие генераторы, как правило, недостаточно надежны для криптографических приложений. На создание удовлетворительных псевдослучайных последовательностей с помощью численных методов затрачена масса усилий. В литературе можно найти множество работ по генераторам псевдослучайных чисел, а также различные тесты на случайность (например [4], [11], [35]). Тем не менее, проблема получения псевдослучайных чисел и их тестирования все еще актуальна, особенно для криптографии [31], и поэтому находится в центре внимания многих исследователей [20], [25], [26].

В научно-технической литературе числа, полученные с помощью компьютера, называются псевдослучайными, мы же, в дальнейшем для краткости, в некоторых случаях будем называть их просто случайными или случайными последовательностями. Каждую последовательность случайных чисел, перед использованием, необходимо тщательно проверить. Для приложений и задач, в которых требуются действительно Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (колы проектов: 99−01−586, 03−01−495) и 1МТА5−00−738 «Эффективное кодирование источников информации и связанные проблемы». качественные" случайные числа, они проверяются специальным набором тестов. Формально генератор псевдослучайных чисел можно считать эффективным, если он проходит все известные статистические тесты. В связи с этим, статистические тесты важны и необходимы, также как и сами генераторы. Более того, генератор случайных чисел может считаться «идеальным» только до тех пор, пока не появится тест, доказывающий обратное и «время жизни» генератора может на этом остановиться.

Необходимо отметить что, по сравнению с другими задачами, криптографические приложения предъявляют к генераторам случайных последовательностей намного более строгие требования, чем, скажем, вычислительные задачи. «Криптографическая» случайность — это не просто статистическая случайность, хотя и включает ее. Чтобы псевдослучайная последовательность была криптографически стойкой, она должна обладать следующими свойствами: генерируемые последовательности проходят все статистические тесты и их символы должны быть непредсказуемы. В то же время, как и любой криптографический алгоритм, генераторы криптографически стойких случайных последовательностей служат объектами «вскрытия» или «взлома». Поэтому, экспериментальные исследования генераторов криптографически стойких случайных последовательностей, разработка эффективных алгоритмов и методов их тестирования, их устойчивость к «взлому», т. е. проверка качества получаемых последовательностей — важная задача криптографии [10], [23], [31].

Среди задач тестирования последовательностей «на случайность» особый интерес представляет задача различения статистическими методами зашифрованных текстов и случайных последовательностей. Разработка эффективных алгоритмов и методов распознавания, или различения зашифрованных текстов хорошо известна в криптографии (см., например, [10], [16], [34]). Решение этой задачи позволяет определить сам факт передачи по сетям связи (или хранения в информационных базах данных) зашифрованных текстов и, в силу этого, представляет несомненный интерес для разработчиков и исследователей систем защиты информации. Вместе с тем, трудность заключается в том, что современные шифры должны преобразовывать данные в последовательности, неотличимые от случайных настолько, насколько это возможно. Причем это одно из обязательных требований, предъявляемых к современным блоковым шифрам, — неотличимость зашифрованной последовательности от случайной, даже тогда, когда шифруемые данные заведомо не случайны. В частности, если на вход алгоритма шифрования подается текст на естественном языке, то на выходе он должен выглядеть как случайная последовательность. Заметим, что это условие предъявлялось Национальным институтом стандартов и технологии США (NIST) к блоковому шифру при организации конкурса на блоковый шифр 21-го века.

Как известно, для создания и хранения текстовой информации используются различные цифровые форматы (такие как «txt», «tex», «html», «doc», rtf" pdf'). В связи с этим, возникает вопрос о зависимости результата шифрования текста от формата, в котором он был представлен. Решение этой задачи представляет несомненный интерес для практической криптографии, разработчиков и исследователей систем защиты информации. Поэтому исследование влияния исходного формата шифруемых данных на возможность их различения в зашифрованном виде от случайных последовательностей важно с практической точки зрения.

Генерация «истинно» случайных чисел — одна из главных проблем возникающих при реализации любой криптосистемы. Огромное количество приложений уязвимо из-за предсказуемости генерируемых чисел. Однако уже более двадцати лет назад было опубликовано множество научной литературы по датчикам случайных чисел (например, [И], [17]). Позднее Дж. Клейнен в [12] приходит, однако, к выводу, что «все еще нет высококачественного генератора псевдослучайных чисел». Одновременно с ним известные специалисты Льюис [5] и Марсалья [21] указывают: «Многие широко распространенные генераторы фактически непригодны». Предостережение о распространенности плохих генераторов делает также И. М. Соболь в [6].

Вместе с тем, любое тестирование генераторов криптографически стойких случайных последовательностей остается частичным. Поэтому Ермаков С. М. и Михайлов Г. А. в [1] отмечают, что кроме специального статистического тестирования «. чрезвычайно важна проверка с помощью решения типовых задач, допускающих независимую оценку результатов аналитическими или численными методами. Можно сказать, что представление о надежности псевдослучайных чисел создается в процессе их использования с тщательной проверкой результатов всегда, когда это возможно» .

Последние десятилетия характеризуются переходом развитых стран к так называемому информационному обществу, что, в частности, характеризуются широким использованием компьютерных, а точнее, информационных сетей в финансовой сфере, бизнесе, производстве да просто в личной жизни граждан (вспомним только Интернет, в путешествии по которому миллионы «обычных» людей проводят миллиарды часов). Наряду с огромным положительным влиянием на экономику и социальную жизнь, глобальная информатизация общества приводит и к появлению принципиально новых проблем, и угроз, начиная от «невинных» забав с вирусами до атак информационных террористов, потенциальный вред которых вполне сопоставим с техногенными катастрофами. Поэтому задачи разработки эффективных средств защиты информационных систем приобретают все большую роль и находятся в центре внимания многих исследователей и разработчиков.

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

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

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

3. Экспериментальное исследование влияния формы представления данных на возможность их различения в зашифрованном виде.

Методы исследования. В работе были использованы вычислительные эксперименты на ЭВМ, моделирование, математическая статистика и теория построения эффективных алгоритмов и программ.

Научная новизна результатов работы. В диссертации получены следующие новые результаты:

1. Проведены экспериментальные исследования нового статил стического критерия — «адаптивный критерий % показана целесообразность его применения для статистической проверки случайных последовательностей и даны практические рекомендации по его применению.

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

3. Впервые предложен метод различения зашифрованных текстов на естественных языках от случайных последовательностей, позволяющий, с помощью разработанного комплекса программ, различать зашифрованные тексты при сравнительно небольших объемах данных (от 100 килобайт и выше). Отметим, что для популярного статистического критерия %2 требуется для решения этой задачи в тысячи раз больший объем данных.

4. Исследовано влияние формата цифровых текстов (txt, rtf, doc, pdf) и их предварительного сжатия на возможность различения в зашифрованном виде на русском, английском и итальянском языках.

Практическая ценность.

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

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

3. Исследовано влияние формата цифровых текстов на естественных языках на возможность их различения в зашифрованном виде.

Апробация работы. Основные результаты диссертации докладывались на международных научных мероприятиях: международная конференция по теории информации ISIT-2003 (Yokohama, Japan, 2003), Китайско-российский форум молодых ученых в Пекине — 2003 г. (Пекин, НаиьЦзин, У си, Шан Хай, Китай, 2003), международная конференция Вычислительные технологии и математическое моделирование в науке, технике и образовании ВТММ-2002 (Алматы, Казахстан, 2002), Четвертое международное совещание по электронным публикациям Е1-РиЬ-99 (Новосибирск, 1999), а также на объединенных семинарах института вычислительных технологий СО РАН, кафедры математического моделирования НГУ, кафедры вычислительных технологий НГТУ.

Публикации. По теме диссертации автором опубликованы работы [38] - [43].

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

Объем и структура диссертации. Диссертационная работа изложена на 119 страницах и состоит из введения, трех глав и заключения. Иллюстрационный материал включает 10 рисунков.

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

состоит из 43 наименований.

Заключение

.

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

Проведенные исследования статистического критерия — «адапл тивный критерий % «показали целесообразность его применения для статистической проверки случайных последовательностей. Показано, что мощность нового метода — адаптивный критерий существенно выше, чем у традиционного критерия Пирсона и, что он более эффективен во многих приложениях, в частности связанных с криптографией, где объем доступной выборки, может быть ограничен.

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

В работе найдено решение актуальной задачи различения зашифрованных текстов от случайных последовательностей, передаваемых по сетям связи (или хранимых в информационных базах данных), а именно: — в диссертации разработан и исследован метод различения зашифрованных текстов на естественных языках от случайных последовательностей, при небольших объемах данных. По сравнению с существующими аналогами, предложенный метод и алгоритмы позволяют решить эту задачу при длине последовательности от 100 килобайт.

Исследовано влияние формата цифровых текстов (txt, rtf, doc, pdf) на возможность их различения в зашифрованном виде на русском, английском и итальянском языках.

Исследованы датчики псевдослучайных чисел созданные на базе современных криптографических алгоритмов шифрования AES, Mars, RC6 и RC5. Показано, что алгоритм шифрования RC5 (без подбора входных данных) нельзя использовать для получения псевдослучайных чисел. Остальные три алгоритма шифрования можно использовать как генераторы псевдослучайных чисел для получения «качественной» криптографически стойкой случайной последовательности.

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