Построение новых статистических тестов и их применение в криптографии

• Автор: Монарев, Виктор Александрович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Новосибирск
• Количество страниц: 111 с. : ил.

СОДЕРЖАНИЕ
Введение

1. Описание тестов, структур данных, алгоритмов

1.1 Теоретические основы

1.2 Описание тестов

1.3 Структуры и алгоритмы

1.4 Применение алгоритмов сжатия для тестирования на случайность

1.5 Двуличные процессы и выбор длины блока для тестирования

1.6 Приложение

2. Тестирование генераторов случайных чисел

2.1 Сравнение эффективности методов

2.2 Анализ генераторов псевдослучайных чисел, использующихся на практике
2.2.1 Линейные конгруэнтые генераторы
2.2.2 Другие типы генераторов
2.2.3 Тестирование популярных генераторов псевдослучайных чисел
3. Новая статистическая атака на блоковые шифры
3.1 Описание метода
3.2 Эксперименты с шифром С
3.2.1 Исследования устойчивости шифра Г1С
3.2.2 Схема реализации тестов на МВС1
3.2.3 Результаты реализации атаки ЛС
3.2.4 Схема реализации атаки на МВС Заключение
Введение
Актуальность


Построены новые алгоритмы и структуры данных для эффективной реализации статистических тестов. Экспериментально исследован широкий ряд практически применяемых генераторов псевдослучайных чисел при помощи новых тестов. Разработана и экспериментально исследована новая статистическая атака на блоковые шифры. Разработанные методы тестирования позволяют эффективно проверять генераторы случайных и псевдослучайных чисел. Предложена новая атака на блоковые шифры, базирующаяся на статистических тестах, которая позволяет обнаруживать ’’слабые места“ блоковых шифров. Апробация работ и публикации: Основные результаты работы докладывались и обсуждались на следующих российских и международных конференциях: International Symposium on Information Theory (Chicago, ), Третья общероссийская конференция ’’Математика и безопасность информационных технологий“ (Москва, ), а также на семинарах Института вычислительных технологий СО РАН (Новосибирск). По теме диссертации опубликовано : 1 электронная публикация, 5 печатных работ, том числе 3 статьи. Разработаны методы эффективного тестирования генераторов случайных и псевдослучайных чисел. Показано, что мощность новых тестов выше чем у ранее известных, включая методы, рекомендуемые NIST. Разработаны алгоритмы и структуры данных для эффективной реализации новых статистических критериев. Предложена и экспериментально исследована новая статистическая атака на блоковые шифры, которая в некоторых случаях позволяет по выбранному шифротексту находить секретный ключ за время меньшее чем полный перебор ключей. Во введении обосновывается актуальность разработки новых эффективных статистических тестов, формулируются цели и задачи исследований, приводятся основные положения диссертации, выносимые на защиту. В первой главе формулируется задача тестирования (псевдослучайных последовательностей чисел. Излагаются алгоритмы новых статистических критериев. Описываются структуры данных, необходимые для эффективной реализации новых статистических тестов, и анализируется сложность вычислений. Все алгоритмы описаны (и реализованы) для многопроцессорных компьютеров. Теоретически обосновывается эффективность теста, базирующегося на алгоритмах сжатия данных. Один из самых известных статистических тестов для проверки гипотезы о том, что для некоторого источника, который порождает буквы из алфавита Л = {ау. Н, являющейся отрицанием Щ, это критерий хи-квадрат. Нй : р(аг) = р$,. Задача тестирования (псевдо)случайных последовательностей чисел формулируется следующим образом. Пусть некоторый источник, который порождает буквы из алфавита А = {аъ. ПО выборке ? Ы = . Но не выполняется. Ясно, что это частный случай и критерий хи-квадрат здесь применим. Кратко опишем вариант основного алгоритма тестирования. При тестировании в каждый момент времени t буквы алфавита А упорядочены (и занумерованы) в соответствии с убыванием (невозрастанием) частот ^(а), а € А. После анализа очередной буквы Жн-1 частота этой буквы им (х1+) увеличивается на 1, а частоты остальных букв остаются прежними. СЛИ ? Первоначальный порядок 1У°(а),а 6 А, задается произвольно, затем буквы упорядочиваются в соответствии с частотами г/+1). Обозначим через 1*(а) номер буквы а € А после обработки элементов выборки . При применении описываемого теста множество всех номеров {1,2,. А — {1,2,. Н- 1, к + 2,. Затем по выборке . При выполнении Но вероятность того, что {хг) принадлежит множеству Апропорциональна количеству его элементов, т. AjfS. Пример. Пусть А = {1,2,3,4}, первоначальный порядок {1. Рассмотрим состав множества А и частоту у после обработки каждого символа выборки (данные приведены в таблице). Делаем вывод, что данную последовательность можно считать случайной. Отметим, что для простоты была рассмотрена выборка объёмом б, в то время, как рекомендуемый объём должен быть равен Ьв/к. В таблице показано, как изменяются частоты и множество Аг после обработки каждого элемента выборки. Так, например, после обработки пятого элемента выборки частота попадания в А = {1,4} была равна двум.