М.: Мир, 2006. — 471 c.: ил. — ISBN 5-03-003639-3
Книга голландского криптолога посвящена современным аспектам
криптографии и криптоанализа. Среди них можно выделить три главных
направления традиционные (симметрические) криптосистемы, системы с
публичными ключами и криптографические протоколы. Основные
результаты снабжены доказательствами. Главной же особенностью
служат многочисленные примеры, созданные на базе известного пакета
"Mathematica" компьютерной алгебры. К книге приложен CD ROM,
позволяющий (при наличии пакета "Mathematica") модифицировать
примеры, в частности, увеличивая значения параметров. Это — первая
столь многоплановая учебная книга по криптографии на русском
языке.
Книга, в первую очередь, адресована математикам, инженерам и студентам, специализирующимся в области защиты информации. Но она окажется интересной и для более широкого круга читателей, чему, в частности, могут способствовать детальные приложения, посвященные теории чисел и конечным полям, делающие книгу достаточно замкнутой в себе. Оглавление Предисловие редактора перевода
Предисловие Введение
Введение и терминология
Шенноновское описание традиционной криптосистемы
Статистическое описание источника открытых текстов
Задачи Классические криптосистемы
Шифр Цезаря, простая замена, шифр Виженера
Шифр Цезаря
Шифр простой замены
Система и ее основное слабое место
Криптоанализ методом поиска наиболее вероятных слов
Криптосисема Виженера
Подсчет числа совпадений, метод Казиски
Подсчет числа совпадений
Метод Казиски
Шифры Вернама и Плэйфэра, перестановки, машина Хагелина, "Энигма"
Одноразовый щит
Шифр Плэйфэра
Шифр перестановок
Машина Хагелина
"Энигма"
Задачи Последовательности регистров сдвига
Псевдослучайные последовательности
Линейные регистры сдвига с обратной связью
(Линейные) регистры сдвига с обратной связью
РN-последовательности
Какие характеристические многочлены задают ГN-последовательности?
Альтернативное описание П(f) для неприводимого f
Криптографические свойства РN-последовательностей
Нелинейные алгоритмы
Минимальный характеристический многочлен
Алгоритм Берлекэмпа-Масси
Несколько замечаний о нелинейных алгоритмах
Задачи Блочные Цифры
Некоторые общие принципы
Некоторые режимы блочных шифров
Режим кодовой книги
Режим сцепления блоков
Режим обратной связи с шифртекстом
Протокол проверки идентичности
DES
DES
Тройной DES
IDEA
Дополнительные замечания
Задачи Теория Шеннона
Энтропия, избыточность и расстояние единственности
Взаимная информация и безусловно безопасные системы
Задачи Техника сжатия данных
Основы кодирования источников со стационарным распределением
Коды Хаффмана
Универсальное сжатие данных, алгоритмы Лемпеля-Зива
Инициализация
Кодирование
Декодирование
Задачи Криптография с публичными ключами
Теоретическая модель
Мотивировка и общая структура
Конфиденциальность
Цифровая подпись
Конфиденциальность и цифровая подпись
Задачи Системы, основанные на дискретных логарифмах
Система дискретных логарифмов
Проблема дискретных логарифмов
Система Диффи-Хеллмана обмена ключами
Другие системы, основанные на дискретных логарифмах
Криптосистемы с публичными ключами Эль-Гамаля
Формирование системы
Секретная система Эль-Гамаля
Схема подписи Эль-Гамаля
Дальнейшие вариации
Стандарт цифровой подписи
Схема подписи Шнорра
Схема подписи Ниберга-Руппеля
Как брать дискретные логарифмы
Алгоритм Похлига-Хеллмана
Частный случай
Общий случай
Пример применения алгоритма Похлига-Хеллмана
Метод исчисления индексов
Общее обсуждение
Задачи Системы, основанные на методе RSA
Система RSA
Немного математики
Формирование системы
Шаг: вычисление модуля nv
Шаг: вычисление показателей ev и dv
Шаг: публикация ev и nv
RSA как схема шифрования
RSA как схема подписывания
RSA как схема шифрования и подписывания
Безопасность RSA: некоторые алгоритмы факторизации
Что может делать криптоаналитик
Алгоритм факторизации для специального класса целых чисел
(p - 1)-Метод Полларда
Общие алгоритмы факторизации
p-метод Полларда
Факторизация методом случайных квадратов
Квадратичное решето
Некоторые опасные режимы RSA
Малый публичный показатель
Передача одинаковых сообщений нескольким получателям, имеющим один и тот же малый публичный ключ
Передача связанных сообщений получателю с малым публичным ключом
Малый секретный показатель; атака Винера
Некоторые физические атаки
Атака по времени вычислений
Атака микроволновкой
Как генерировать большие простые числа; некоторые тесты на простоту
Испытание случайных чисел
Вероятностные тесты простоты
Тест простоты Соловэя-Штрассена
Тест Миллера-Рабина
Детерминированный тест простоты
Вариант Рабина
Функция шифрования
Дешифрование
Предвычисление
Нахождение квадратных корней по модулю простого числа
Четыре решения
Как различать решения
Эквивалентность взлома схемы Рабина и факторизации числа n
Задачи Системы, основанные на эллиптических кривых
Некоторые основные факты об эллиптических кривых
Геометрия эллиптических кривых
Прямая, проходящая через две различные точки
Касательная прямая
Сложение точек на эллиптической кривой
Криптосистемы, определяемые над эллиптическими кривыми
Проблема дискретных логарифмов над эллиптическими кривыми
Система дискретных логарифмов над эллиптическими кривыми
Безопасность систем дискретных логарифмов над эллиптическими кривыми
Задачи Системы, основанные на теории кодирования
Введение в коды Гоппы
Криптосистема Мак-Элиса
Система
Формирование системы
Шифрование
Дешифрование
Обсуждение
Резюме и предполагаемые параметры
Эвристика схемы
Отсутствие режима подписывания
Аспекты безопасности
Угадывание S в и Рв
Сравнение со всеми кодовыми словами
Декодирование по синдрому
Угадывание k верных и независимых компонент
Многократные шифрования одного сообщения
Маленький пример системы Мак-Элиса
Другая техника декодирования линейных кодов
Схема Нидеррайтера
Задачи Системы, основанные на задаче о рюкзаке
Рюкзачная система
Задача о рюкзаке
Рюкзачная система
Формирование рюкзачной системы
Шифрование
Дешифрование
Дальнейшее обсуждение
L3-атака
Введение
Решетки
Редуцированный базис
L3-атака
L3-алгоритм редукции базиса
Вариант Кора-Райвеста
Формирование системы
Шифрование
Дешифрование
Задачи Хэш-функции и техника аутентификации
Введение
Хэш-функции и МАС'и
Безусловно безопасные коды аутентификации
Основные понятия и границы
Конструкция проективной плоскости
Конечная проективная плоскость
Общая конструкция проективной плоскости
Код аутентификации, определяемый проективной плоскостью
А-коды, определяемые ортогональными массивами
А-коды, определяемые кодами, исправляющими ошибки
Задачи Протоколы с нулевым разглашением
Протокол Фиата-Шамира
Протокол идентификации Шнорра
Задачи Системы разделения секрета
Введение
Пороговые схемы
Пороговые схемы с лгунами
Схемы разделения секрета
Визуальные схемы разделения секрета
Задачи Приложение А Элементарная теория чисел
Введение
Алгоритм Эвклида
Теоремы Эйлера, Ферма и китайская теорема об остатках
Сравнения
Теоремы Эйлера и Ферма
Решение линейных сравнений
Китайская теорема об остатках
Квадратичные вычеты
Непрерывные дроби
Формула обращения Мёбиуса, принцип включения и исключения
Формула обращения Мёбиуса
Принцип включения и исключения
Задачи Приложение В Конечные поля
Алгебра
Абстрактная алгебра
Операции на множестве
Группа
Кольцо
Идеал
Поле
Отношения эквивалентности
Циклические группы
Линейная алгебра
Векторные пространства и подпространства
Линейная независимость, базисы и размерность
Скалярное произведение, ортогональность
Конструкции
Число неприводимых многочленов над GF(q)
Строение конечных полей
Циклическое строение конечного поля
Мощность конечного поля
Некоторые правила вычислений над конечными полями; сопряженные элементы
Минимальные многочлены и примитивные многочлены
Дальнейшие свойства
Многочлены деления круга
Задачи Приложение С Некоторые знаменитые математики
Эвклид из Александрии
Леонард Эйлер
Пьер де Ферма
Эварист Галуа
Иоганн Карл Фридрих Гаусс
Карл Густав Якоб Якоби
Адриен-Мари Лежандр
Август Фердинанд Мёбиус
Джозеф Генри Маклаген Ведцербарн Приложение D Новые функции
Список литературы
Список литературы, добавленной при переводе
Символы и обозначения
Предметный указатель
Книга, в первую очередь, адресована математикам, инженерам и студентам, специализирующимся в области защиты информации. Но она окажется интересной и для более широкого круга читателей, чему, в частности, могут способствовать детальные приложения, посвященные теории чисел и конечным полям, делающие книгу достаточно замкнутой в себе. Оглавление Предисловие редактора перевода
Предисловие Введение
Введение и терминология
Шенноновское описание традиционной криптосистемы
Статистическое описание источника открытых текстов
Задачи Классические криптосистемы
Шифр Цезаря, простая замена, шифр Виженера
Шифр Цезаря
Шифр простой замены
Система и ее основное слабое место
Криптоанализ методом поиска наиболее вероятных слов
Криптосисема Виженера
Подсчет числа совпадений, метод Казиски
Подсчет числа совпадений
Метод Казиски
Шифры Вернама и Плэйфэра, перестановки, машина Хагелина, "Энигма"
Одноразовый щит
Шифр Плэйфэра
Шифр перестановок
Машина Хагелина
"Энигма"
Задачи Последовательности регистров сдвига
Псевдослучайные последовательности
Линейные регистры сдвига с обратной связью
(Линейные) регистры сдвига с обратной связью
РN-последовательности
Какие характеристические многочлены задают ГN-последовательности?
Альтернативное описание П(f) для неприводимого f
Криптографические свойства РN-последовательностей
Нелинейные алгоритмы
Минимальный характеристический многочлен
Алгоритм Берлекэмпа-Масси
Несколько замечаний о нелинейных алгоритмах
Задачи Блочные Цифры
Некоторые общие принципы
Некоторые режимы блочных шифров
Режим кодовой книги
Режим сцепления блоков
Режим обратной связи с шифртекстом
Протокол проверки идентичности
DES
DES
Тройной DES
IDEA
Дополнительные замечания
Задачи Теория Шеннона
Энтропия, избыточность и расстояние единственности
Взаимная информация и безусловно безопасные системы
Задачи Техника сжатия данных
Основы кодирования источников со стационарным распределением
Коды Хаффмана
Универсальное сжатие данных, алгоритмы Лемпеля-Зива
Инициализация
Кодирование
Декодирование
Задачи Криптография с публичными ключами
Теоретическая модель
Мотивировка и общая структура
Конфиденциальность
Цифровая подпись
Конфиденциальность и цифровая подпись
Задачи Системы, основанные на дискретных логарифмах
Система дискретных логарифмов
Проблема дискретных логарифмов
Система Диффи-Хеллмана обмена ключами
Другие системы, основанные на дискретных логарифмах
Криптосистемы с публичными ключами Эль-Гамаля
Формирование системы
Секретная система Эль-Гамаля
Схема подписи Эль-Гамаля
Дальнейшие вариации
Стандарт цифровой подписи
Схема подписи Шнорра
Схема подписи Ниберга-Руппеля
Как брать дискретные логарифмы
Алгоритм Похлига-Хеллмана
Частный случай
Общий случай
Пример применения алгоритма Похлига-Хеллмана
Метод исчисления индексов
Общее обсуждение
Задачи Системы, основанные на методе RSA
Система RSA
Немного математики
Формирование системы
Шаг: вычисление модуля nv
Шаг: вычисление показателей ev и dv
Шаг: публикация ev и nv
RSA как схема шифрования
RSA как схема подписывания
RSA как схема шифрования и подписывания
Безопасность RSA: некоторые алгоритмы факторизации
Что может делать криптоаналитик
Алгоритм факторизации для специального класса целых чисел
(p - 1)-Метод Полларда
Общие алгоритмы факторизации
p-метод Полларда
Факторизация методом случайных квадратов
Квадратичное решето
Некоторые опасные режимы RSA
Малый публичный показатель
Передача одинаковых сообщений нескольким получателям, имеющим один и тот же малый публичный ключ
Передача связанных сообщений получателю с малым публичным ключом
Малый секретный показатель; атака Винера
Некоторые физические атаки
Атака по времени вычислений
Атака микроволновкой
Как генерировать большие простые числа; некоторые тесты на простоту
Испытание случайных чисел
Вероятностные тесты простоты
Тест простоты Соловэя-Штрассена
Тест Миллера-Рабина
Детерминированный тест простоты
Вариант Рабина
Функция шифрования
Дешифрование
Предвычисление
Нахождение квадратных корней по модулю простого числа
Четыре решения
Как различать решения
Эквивалентность взлома схемы Рабина и факторизации числа n
Задачи Системы, основанные на эллиптических кривых
Некоторые основные факты об эллиптических кривых
Геометрия эллиптических кривых
Прямая, проходящая через две различные точки
Касательная прямая
Сложение точек на эллиптической кривой
Криптосистемы, определяемые над эллиптическими кривыми
Проблема дискретных логарифмов над эллиптическими кривыми
Система дискретных логарифмов над эллиптическими кривыми
Безопасность систем дискретных логарифмов над эллиптическими кривыми
Задачи Системы, основанные на теории кодирования
Введение в коды Гоппы
Криптосистема Мак-Элиса
Система
Формирование системы
Шифрование
Дешифрование
Обсуждение
Резюме и предполагаемые параметры
Эвристика схемы
Отсутствие режима подписывания
Аспекты безопасности
Угадывание S в и Рв
Сравнение со всеми кодовыми словами
Декодирование по синдрому
Угадывание k верных и независимых компонент
Многократные шифрования одного сообщения
Маленький пример системы Мак-Элиса
Другая техника декодирования линейных кодов
Схема Нидеррайтера
Задачи Системы, основанные на задаче о рюкзаке
Рюкзачная система
Задача о рюкзаке
Рюкзачная система
Формирование рюкзачной системы
Шифрование
Дешифрование
Дальнейшее обсуждение
L3-атака
Введение
Решетки
Редуцированный базис
L3-атака
L3-алгоритм редукции базиса
Вариант Кора-Райвеста
Формирование системы
Шифрование
Дешифрование
Задачи Хэш-функции и техника аутентификации
Введение
Хэш-функции и МАС'и
Безусловно безопасные коды аутентификации
Основные понятия и границы
Конструкция проективной плоскости
Конечная проективная плоскость
Общая конструкция проективной плоскости
Код аутентификации, определяемый проективной плоскостью
А-коды, определяемые ортогональными массивами
А-коды, определяемые кодами, исправляющими ошибки
Задачи Протоколы с нулевым разглашением
Протокол Фиата-Шамира
Протокол идентификации Шнорра
Задачи Системы разделения секрета
Введение
Пороговые схемы
Пороговые схемы с лгунами
Схемы разделения секрета
Визуальные схемы разделения секрета
Задачи Приложение А Элементарная теория чисел
Введение
Алгоритм Эвклида
Теоремы Эйлера, Ферма и китайская теорема об остатках
Сравнения
Теоремы Эйлера и Ферма
Решение линейных сравнений
Китайская теорема об остатках
Квадратичные вычеты
Непрерывные дроби
Формула обращения Мёбиуса, принцип включения и исключения
Формула обращения Мёбиуса
Принцип включения и исключения
Задачи Приложение В Конечные поля
Алгебра
Абстрактная алгебра
Операции на множестве
Группа
Кольцо
Идеал
Поле
Отношения эквивалентности
Циклические группы
Линейная алгебра
Векторные пространства и подпространства
Линейная независимость, базисы и размерность
Скалярное произведение, ортогональность
Конструкции
Число неприводимых многочленов над GF(q)
Строение конечных полей
Циклическое строение конечного поля
Мощность конечного поля
Некоторые правила вычислений над конечными полями; сопряженные элементы
Минимальные многочлены и примитивные многочлены
Дальнейшие свойства
Многочлены деления круга
Задачи Приложение С Некоторые знаменитые математики
Эвклид из Александрии
Леонард Эйлер
Пьер де Ферма
Эварист Галуа
Иоганн Карл Фридрих Гаусс
Карл Густав Якоб Якоби
Адриен-Мари Лежандр
Август Фердинанд Мёбиус
Джозеф Генри Маклаген Ведцербарн Приложение D Новые функции
Список литературы
Список литературы, добавленной при переводе
Символы и обозначения
Предметный указатель