ПОТОЧНЫЕ ШИФРЫ

"Революционные успехи, имевшие место в прошедшие десятилетия, преобразовали криптографию из полунаучной дисциплины в респектабельный раздел теоретической компьютерной науки. Нашим намерением было написать книгу, которая представила бы базовые концепции, определения и результаты в криптографии".
(Одед Голдрайх, из Предисловия к опубликованным в Internet фрагментам недописанной книги "Основания криптографии", 1995 год)

"Данная книга предназначена в качестве справочника для профессиональных криптографов, здесь описаны заслуживающие внимания методы и алгоритмы, наряду с теоретическими концепциями и вспомогательными материалами. Книга является также обстоятельным источником криптографических сведений, полезных как студентам, так и преподавателям. Нашей целью было собрать существующие криптографические знания в единый согласованный том, приемлемый как для специалистов-практиков, так и для академических математиков. Хотя данная книга не предусматривает ее линейное чтение с начала до конца, материал подобран таким образом, чтобы и подобный подход не был бессмысленным. Двумя основными целями, мотивированными "справочной" природой книги, стали следующие - предоставить легкий доступ к самостоятельным результатам и обеспечить удобное соотнесение алгоритмов и теоретических результатов. Для облегчения доступа к материалу подразделы книги снабжены многоуровневой нумерацией."
(А. Менезес, П. Ван Оорсхот и С.Вэнстоун, "Справочник по прикладной криптографии", CRC Press, 1996 г., из Предисловия )

"Всякое сочинение, как дело человеческое, имеет свои недостатки. Я очень знаю, что мой труд более, нежели многие другие, должен, по сущности своей, подать повод к справедливым критическим замечаниям. Разнообразие предметов, которые для полноты должны входить в состав Лексикона, трудность соразмерить объем статей с относительною их важностью и не упустить из виду единства в изложении, решительная невозможность избежать в некоторых случаях повторений, необработанность нашего математического языка, - все это заставляет меня думать, что несмотря на все мои старания, книга моя далеко еще не удовлетворяет условиям хорошего лексикографического руководства. Может быть, отечественные математики найдут также, что некоторые термины и речения переданы не совсем удачно в моем Лексиконе; заранее прошу их быть снисходительными к таким недостаткам."
("Предуведомление" из "Лексикона чистой и прикладной математики" В.Я.Буняковского, 1839 год. )

"И все же я полагаю, что нечто неполное - это все-таки лучше, чем ничего" ...
(Одед Голдрайх, из Предисловия к опубликованным в Internet фрагментам недописанной книги "Основания криптографии", 1995 год)

Глава 0. Введение (*)

• 0.1 Базовая терминология и общие положения
• 0.2 Концепция Рюппеля о четырех подходах к конструированию поточных шифров
• 0.3 Классификация поточных шифров
  • 0.3.1 Синхронные поточные шифры и псевдослучайные генераторы
  • 0.3.2 Самосинхронизирующиеся поточные шифры и скрэмблеры

Глава 1. Подход теории информации (*)

• 1.1 Эпохи в криптологии
• 1.2 Шенноновская модель криптоанализа
• 1.3 Локальная рандомизация
• 1.4 Практическая стойкость

Глава 2. Строительные блоки для создания криптосхем (*)

• 2.1 Конгруэнтные генераторы
  • 2.1.1 Генераторы псевдослучайных чисел
  • 2.1.2 Комбинирование ЛКГ и программная реализация
• 2.2 Криптоанализ конгруэнтных генераторов
  • 2.2.1 Вскрытие конгруэнтных генераторов (неусеченных)
  • 2.2.2 Усеченные линейные конгруэнтные генераторы с известными параметрами
  • 2.2.3 Усеченные линейные конгруэнтные генераторы с неизвестными параметрами
• 2.3 Регистры сдвига
  • 2.3.1 Алгебраические свойства регистров сдвига с линейной обратной связью
  • 2.3.2 РСЛОС максимального периода и примитивные многочлены
  • 2.3.3 Регистры Фибоначчи и Галуа, и их программная реализация
• 2.4 Некоторые итоги

Глава 3. Статистические свойства и меры сложности последовательностей (*)

• 3.0 Подходы к анализу
• 3.1 Статистические свойства последовательностей
  • 3.1.1 Постулаты Голомба
  • 3.1.2 Статистические тесты
    • 3.1.2.1 Теоретический фундамент
    • 3.1.2.2 Частотный тест
    • 3.1.2.3 Последовательный тест
    • 3.1.2.4 Тест серий
    • 3.1.2.5 Автокорреляционный тест
    • 3.1.2.6 Универсальный тест
    • 3.1.2.7 Тест повторений
    • 3.1.2.8 Сравнение тестов l-грамм
    • 3.1.2.9 Комбинирование тестов
  • 3.1.3 Отсечение слабых последовательностей
• 3.2 Линейная сложность последовательностей и преобразования
  • 3.2.1 Концепция линейной сложности
  • 3.2.2 Алгоритм линейного синтеза Берлекампа-Мэсси
  • 3.2.3 Естественная интерпретация алгоритма Берлекампа-Мэсси
  • 3.2.4 Другие методы анализа линейной сложности
  • 3.2.5 Преобразования
    • 3.2.5.1 Дискретное преобразование Фурье и линейная сложность
    • 3.2.5.2 Преобразование Уолша и булевы функции
    • 3.2.5.3 Преобразование алгебраической нормальной формы
  • 3.2.6 Профиль линейной сложности
• 3.3 Периодические последовательности
  • 3.3.1 Прагматические соображения
  • 3.3.2 Теоретический анализ периодических последовательностей
• 3.4 Суммы и произведения периодических последовательностей
  • 3.4.1 Суммы периодических последовательностей
  • 3.4.2 Произведения периодических последовательностей
  • 3.4.3 Общая нижняя граница для линейной сложности произведения
• 3.5 Другие меры сложности
  • 3.5.1 Общие результаты
  • 3.5.2 Квадратичный размах
  • 3.5.3 Деревья суффиксов
• 3.6 Вместо резюме: две стороны теоретико-системного подхода

Глава 4. Базовые схемы и их криптоанализ (*)

• 4.0 Функции от периодических последовательностей
• 4.1 Фильтрующий генератор
  • 4.1.1 Линейная сложность фильтр-генератора
  • 4.1.2 Алгоритм для оценки линейного размаха нелинейно фильтруемых последовательностей
• 4.2 Комбинирующий генератор
• 4.3 Корреляционные методы вскрытия комбинирующих генераторов
  • 4.3.0 Общий обзор
  • 4.3.1 Базовая корреляционная атака Зигенталера
  • 4.3.2 Быстрая корреляционная атака Майера и Штаффельбаха
  • 4.3.3 Метод Пенцхорна для нахождения низковесовых полиномов проверки четности
  • 4.3.4 Метод итерационного вероятностного декодирования Михалевича-Голича
  • 4.3.5 Метод Маккея: алгоритм минимизации свободной энергии
  • 4.3.6 Сравнение алгоритмов и проблема сходимости
• 4.4 Вскрытие фильтр-генераторов
  • 4.4.0 Основные результаты
  • 4.4.1 Метод Зигенталера: криптоаналитическое представление фильтр-генератора
  • 4.4.2 Модель Андерсона: на пути к "оптимальной корреляционной атаке"
  • 4.4.3 Математическая модель атаки Андерсона
  • 4.4.4 Инверсионная атака Голича
  • 4.4.5 Множества положительных разностей и корреляционный иммунитет
  • 4.4.6 Критерии обеспечения стойкости нелинейных фильтр-генераторов

Глава 5. Криптографические функции. Критерии нелинейности и методы конструирования (*)

• 5.0 Общий обзор
• 5.1 Корреляционный иммунитет порядка k
  • 5.1.1 Базовые понятия и результаты для узлов без памяти
  • 5.1.2 Конструирование корреляционно-иммунных функций
  • 5.1.3 Корреляционный иммунитет и автомат с памятью
• 5.2 Классификация Майера-Штаффельбаха для критериев нелинейности
  • 5.2.1 Расстояние до линейных функций
  • 5.2.2 Функции с линейной структурой
  • 5.2.3 Совершенные нелинейные функции
• 5.3 Бент-функции
  • 5.3.1 Конструкция Маиораны-Макфарленда и бент-отображения Нюберг
  • 5.3.2 Конструкции Карле
  • 5.3.3 Общая конструкция Доббертина
• 5.4 Критерий распространения и эластичные функции
  • 5.4.1 Строгий лавинный критерий и критерий распространения
  • 5.4.2 Конструирование булевых функций, удовлетворяющих критериям сбалансированности, нелинейности и распространения
    • 5.4.2.1 Базовые понятия и аппарат адамаровых матриц
    • 5.4.2.2 Конкатенация и расщепление последовательностей
    • 5.4.2.3 Модификация и перемножение последовательностей
    • 5.4.2.4 Высоко нелинейные сбалансированные функции, удовлетворяющие критерию распространения большой степени
  • 5.4.3 Эластичные функции
    • 5.4.3.1 Свойства эластичных функций
    • 5.4.3.2 Конструирование новых эластичных функций из уже известных
    • 5.4.3.3 Преобразование линейных эластичных функций в нелинейные
• 5.5 Рекомендации конструкторам криптосхем

Глава 6. Схемы с неравномерным движением регистров и без памяти (*)

• 6.0 Неравномерное движение как способ достижения нелинейности
• 6.1 Общий обзор конструкций с неравномерным движением регистров
  • 6.1.1 Схемы с управляющим регистром, их период и линейная сложность
    • 6.1.1.1 Базовая схема, генераторы "стоп-вперед" и "один-два шага"
    • 6.1.1.2 Период и линейная сложность
    • 6.1.1.3 Генератор с перемежающимся шагом
    • 6.1.1.4 Каскадный генератор
    • 6.1.1.5 Сжимающий генератор
  • 6.1.2 Схемы с самоуправлением
    • 6.1.2.1 Генератор [d,k]-самоусечения
    • 6.1.2.2 Самосжимающий генератор
• 6.2 Каскадные генераторы
  • 6.2.1 Криптографические свойства "шаг_k,m"-каскадов
  • 6.2.2 Криптоанализ каскадов
  • 6.2.3 Систематическая атака Меникоччи
• 6.3 Сжимающий и самосжимающий генераторы
  • 6.3.1 Сжимающий генератор
    • 6.3.1.1 Конструкция, период, линейная сложность и статистические свойства
    • 6.3.1.2 Приложение преобразования Фурье и e-смещенных распределений в анализе регистров с переменными точками съема и СГ
    • 6.3.1.3 Криптоаналитические подходы к вскрытию схемы
    • 6.3.1.4 Аспекты аппаратной и программной реализации
  • 6.3.2 Сжимающий Фибоначчи-генератор (Fish) и его вскрытие
    • 6.3.2.1 Обобщенный сжимающий генератор и алгоритм Fish
    • 6.3.2.2 Вскрытие криптосхемы Fish
  • 6.3.3 Самосжимающий генератор
    • 6.3.3.1 Сжатие и самосжатие
    • 6.3.3.2 Период и линейная сложность, примеры и экспериментальные результаты
    • 6.3.3.3 Криптоанализ
• 6.4 Вскрытие схем с неравномерным движением
  • 6.4.1 Краткий обзор основных результатов
  • 6.4.2 Восстановление начального заполнения регистра на основе новой меры расстояния между последовательностями
  • 6.4.3 Атака встраиванием и вероятностная корреляционная атака
  • 6.4.4 Восстановление полинома обратной связи и быстрая корреляционная атака

Глава 7. Схемы с памятью (*)

• 7.1 Общий обзор
  • 7.1.1 Схемы с равномерным движением и памятью
  • 7.1.2 Схемы на регистрах сдвига с операцией переноса
  • 7.1.3 Схемы с неравномерным движением и памятью
• 7.2 Корреляционные свойства комбинирующих узлов с 1 битом памяти
  • 7.2.1 Базовая схема сумматора
  • 7.2.2 Обобщенный комбинирующий узел с 1 битом памяти
  • 7.2.3 Корреляция, обусловленная известным выходом
  • 7.2.4 Криптоанализ сумматора с двумя входами
• 7.3 Комбинирующий узел с произвольным числом бит памяти
  • 7.3.1 Обобщенный двоичный комбинирующий узел с памятью и корреляционные свойства векторных булевых функций
  • 7.3.2 Корреляционные свойства комбинирующих узлов с памятью
  • 7.3.3 Метод аппроксимации линейной последовательной схемой
  • 7.3.4 Корреляционная атака
• 7.4 Регистры сдвига с переносом и 2-адический анализ
  • 7.4.1 Обзор 2-адических чисел
  • 7.4.2 Регистры сдвига с памятью, их реализация, требования к памяти
  • 7.4.3 Анализ РСОСП
  • 7.4.4 2-адический размах и сложность
  • 7.4.5 Алгоритм рациональной аппроксимации
  • 7.4.6 2-адический криптоанализ сумматора
  • 7.4.7 Длинные последовательности и их статистические свойства
  • 7.4.8 РСОСП максимального периода и криптосхемы на их основе

Глава 8. Конкретные схемы криптогенераторов и самосинхронизирующиеся шифры (*)

• 8.1 Обзор ранних схем
  • 8.1.1 Генератор Геффе
  • 8.1.2 Генератор Плесса
  • 8.1.3 Генератор-мультиплексор Дженнингса
  • 8.1.4 Пороговый генератор
  • 8.1.5 Генератор скалярного перемножения
  • 8.1.6 Генератор Вольфрама
  • 8.1.7 Генератор "1/p"
  • 8.1.8 Генератор суммирования
  • 8.1.9 Ранцевый генератор
  • 8.1.10 Аддитивный генератор
  • 8.1.11 Генератор Гиффорда
• 8.2 Алгоритм А5
  • 8.2.1 Описание криптосхемы
  • 8.2.2 Криптоанализ шифра
• 8.3 Алгоритм RC4
  • 8.3.1 Описание криптосхемы
  • 8.3.2 Криптоанализ
• 8.4 Алгоритм SEAL
  • 8.4.1 Семейство псевдослучайных функций
  • 8.4.2 Особенности SEAL
  • 8.4.3 Описание алгоритма
  • 8.4.4 Стойкость SEAL
• 8.5 Обзор криптосхем 1990-х годов
  • 8.5.1 Фильтр-генератор на основе алгоритма сжатия данных Зива-Лемпела
  • 8.5.2 Модифицированный линейный конгруэнтный генератор (Чамберса)
  • 8.5.3 Каскад с неравномерным движением (Чамберса)
  • 8.5.4 Алгоритм WAKE
  • 8.5.5 Алгоритм PIKE
  • 8.5.6 Алгоритм GOAL
  • 8.5.7 Алгоритм ORYX
  • 8.5.8 Генератор ISAAC
  • 8.5.9 Chameleon - новое приложение криптографии
• 8.6 Самосинхронизирующиеся шифры
  • 8.6.1 Концептуальная схема
  • 8.6.2 Рекурсивная архитектура Маурера
  • 8.6.3 Схема Дэмена на регистре сдвига с условным дополнением

Глава 9. Новые методы криптоанализа (*)

• 9.1 Метод "встреча посередине"
• 9.2 Криптографические слабости ресинхронизаций
  • 9.2.1 Типы ресинхронизаций и их интерпретация
  • 9.2.2 Общая атака нелинейно фильтруемых систем
  • 9.2.3 Атака мультиплексор-генератора
• 9.3 Дифференциальный криптоанализ
  • 9.3.1 Аддитивный естественный поточный шифр
  • 9.3.2 Дифференциальная атака
  • 9.3.3 Теоретический базис атаки
• 9.4 Линейный криптоанализ
  • 9.4.1 Линейные модели поточных шифров
  • 9.4.2 Линейный анализ генераторов на основе регистров сдвига
• 9.5 Методы дискретной оптимизации: симулятор отжига и генетический алгоритм
  • 9.5.1 Симулятор отжига и алгоритм Метрополиса
  • 9.5.2 Корреляционная атака, модифицированная симулятором отжига
  • 9.5.3 Генетические алгоритмы
• 9.6 Оптимизация тотального перебора ключей
• 9.7 О существовании стойких регистров сдвига
  • 9.7.1 Концептуальная модель
  • 9.7.2 Определения
  • 9.7.3 Существование стойких РСОС
  • 9.7.4 Атаки линейного синтеза

Глава 10. Альтернативные конструкции (*)

• 10.0 Взгляды на теорию стойкости
• 10.1 Подход с позиций теории сложности
  • 10.1.1 Базовые идеи и концепции
  • 10.1.2 Генераторы
    • 10.1.2.1 Псевдослучайный генератор Шамира
    • 10.1.2.2 Генератор Блюма-Микали
    • 10.1.2.3 Генераторы RSA
    • 10.1.2.4 Генератор квадратичных вычетов
• 10.2 Рандомизированные шифры
  • 10.2.1 Шифр Диффи
  • 10.2.2 Шифр "Рип ван Винкль"
  • 10.2.3 Шифр Маурера
• 10.3 Хаотические шифры
• 10.4 Система гаммирования POTP

Глава последняя. Заключение (*)

• I. Современная ситуация в открытой криптографии
• II. Критерии для сравнения алгоритмов
• III. Программные и аппаратные шифры
• IV. Развитие теории
• V. Жизнь в реальном мире