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

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

1. Методы эффективного кодирования для повышения расстояния единственности шифров
1.1. Введение
1.2. Теория систем с совершенной секретностью
1.3. Соотношение избыточностей по входу и выходу
1.4. Основные подходы к потроению метода эффективного кодирования
1.4.1. Быстрое кодирование с использованием скользящего окна
1.4.2. Использование мнимого скользящего окна для уменьшения объема памяти кодера и декодера
1.4.3. Кодирование марковских источников
1.4.4. Избыточность арифметического кодирования
Выводы
2. Омофонное кодирование
2.1. Обзор побуквенных омофонных кодов
2.2. Арифметическое кодирование с разделением интервала
2.2.1. Основная идея метода
2.2.2. Описание алгоритма кодирования
2.2.3. Свойства метода
2.3. Арифметическое кодирование с фиктивным символом
2.3.1. Описание алгоритма
2.3.2. Оценка избыточности по входу
2.3.3. Потребление внешних случайных бит
2.3.4. Вычислительная сложность метода
Выводы
3. Выделение случайности и генерация случайных величин
3.1. Задачи, возникающие при использовании физических генераторов случайных чисел
3.2. Эффективная нумерация множеств
3.2.1. Постановка задачи
3.2.2. Нумерация сочетаний
3.2.3. Быстрый алгоритм нумерации сочетаний
3.3. Эффективная генерация произвольно распределенных случайных величин
3.3.1. Постановка задачи
3.3.2. Быстрая генерация случайных величин для омофонных кодеров
3.3.3. Генерация случайных величин на основе омофонного декодирования
3.3.4. Уменьшение числа случайных бит, используемых в омо-фонном кодировании
3.3.5. Эффективное преобразование вероятностностных распределений
Выводы
4. Строго идеальные криптосистемы
4.1. Основные определения и постановка задачи
4.2. Конструкция идеальной криптосистемы на базе нумерационного кода
4.2.1. Основная идея и свойства метода
4.2.2. Описание общего алгоритма и его свойства

4.3. Построение строго идеальной системы на базе универсального
омофонного кода
4.3.1. Введение
4.3.2. Основная идея
4.3.3. Общая конструкция строго идеальной системы
Выводы
5. Статистические тесты и атака на блоковые шифры
5.1. Тесты для проверки генераторов случайных и псевдослучайных
чисел
5.1.1. Тест «Стопка книг»
5.1.2. Порядковый тест
5.1.3. Экспериментальные исследования
5.2. Статистическая атака на блоковые шифры
Выводы
Основные заключения и выводы
Список литературы
Работы автора, в которых изложены основные результаты
ПРИЛОЖЕНИЕ
А. Основные блоковые шифры
А.1. Шифр ГОСТ 28147
А.2. Шифр RC6
А.З. Шифр Rijndael (AES)
Глава 1. Методы эффективного кодирования
Легко видеть, что вычисление любого Qi, г = 2,3,... ,8, требует сложения самое большее трех чисел.
В общем случае при заданных счетчиках щ, с2 сдг, N = 2т, множества С1, i = 1,2,... ,m, строятся следующим образом:
С = Cl, С = С2, . . . , Сдг = Сдг,
Ci2 = ci + с2, (7| = с3 4- с4, ..., С^/2 = сдг_1 4- сдг>
Cf = Ci 4 h С4, С2 = С5 4 1- с8, ..., Сдг^4 = civ-з 4---1- cjv,
СГ = Cl 4- С2 4 Ь Сдг/2, С2т = Сдг/2+1 4- Срг/2+2 4---b Сдг.
Отметим, что не все элементы этих множеств используются в вычислениях. Фактически, достаточно хранить в памяти только элементы с нечетными индексами. Тем не менее, мы будем пользоваться вышеприведенной конструкцией для облегчения понимания.
Покажем, как можно вычислить Qk+i, к — 1,2(напомним, что Q1 = 0). Пусть к имеет двоичное разложение kmkm-i ■ ■ ■ к, где каждая цифра ki равна нулю или единице. Тогда
Qk+1 = kmC^2k/N 4“ 4- km-2Cgkjfl-^ 4" • • • 4- кСк
(заметим, что в вычислении участвуют только те С), для которых ki — 1). Данная сумма имеет не более m = log N т-битных слагаемых, так что время вычисления кумулятивных вероятностей составляет 0(т log N) битовых операций.
При включении и исключении элементов из скользящего окна необходимо увеличивать или уменьшать счетчики на единицу. При этом все элементы множеств, которые зависят от этих счетчиков, также должны быть увеличены ИЛИ уменьшены. Более ТОЧНО, увеличение (уменьшение) Cfc необходимо заменить увеличением (уменьшением)
°к> °[А;/21> ик/41! •••> ^k/{N/2ji