- •Часть I
- •Глава 1 представляет собой введение в криптографию, описывает множество терминов, в ней кратко рассматривается докомпьютерная криптография.
- •1.1 Терминология
- •1.2 Стеганография
- •1.3 Подстановочные и перестановочные шифры
- •1.4 Простое xor
- •1.5 Одноразовые блокноты
- •1.6 Компьютерные алгоритмы
- •1.7 Большие числа
- •Часть I криптографические протоколы
- •2 Элементы протоколов
- •2.1 Введение в протоколы
- •2.2 Передача информации с использованием симметричной криптографии
- •2.3 Однонаправленные функции
- •2.4 Однонаправленные хэш‑функции
- •2.5 Передача информации с использованием криптографии с открытыми ключами
- •2.6 Цифровые подписи
- •2.7 Цифровые подписи и шифрование
- •2.8. Генерация случайных и псевдослучайных последовательностей
- •3 Основные протоколы
- •3.1 Обмен ключами
- •3.2 Удостоверение подлинности
- •3.3 Удостоверение подлинности и обмен ключами
- •3.4 Формальный анализ протоколов проверки подлинности и обмена ключами
- •3.5 Криптография с несколькими открытыми ключами
- •3.6 Разделение секрета
- •3.7 Совместное использование секрета
- •3.8 Криптографическая защита баз данных
- •4 Промежуточные протоколы
- •4.1 Службы меток времени
- •4.2 Подсознательный канал
- •4.3 Неотрицаемые цифровые подписи
- •4.4 Подписи уполномоченного свидетеля
- •4.5 Подписи по доверенности
- •4.6 Групповые подписи
- •4.7 Подписи с обнаружением подделки
- •4.8 Вычисления с зашифрованными данными
- •4.9 Вручение битов
- •4.10 Подбрасывание "честной" монеты
- •4.11 Мысленный покер
- •4.12 Однонаправленные сумматоры
- •4.13 Раскрытие секретов "все или ничего"
- •4.14 Условное вручение ключей
- •5 Развитые протоколы
- •5.1 Доказательства с нулевым знанием
- •5.2 Использование доказательства с нулевым знанием для идентификации
- •5.3 Слепые подписи
- •5.4 Личностная криптография с открытыми ключами
- •5.5 Рассеянная передача
- •5.6 Рассеянные подписи
- •5.7 Одновременная подпись контракта
- •5.8 Электронная почта с подтверждением
- •5.9 Одновременный обмен секретами
- •6 Эзотерические протоколы
- •6.1 Безопасные выборы
- •6.2 Безопасные вычисления с несколькими участниками
- •6.3 Анонимная широковещательная передача сообщений
- •6.4 Электронные наличные
- •Часть II Криптографические методы
- •7 Длина ключа
- •7.1 Длина симметричного ключа
- •7.2 Длина открытого ключа
- •Табл-4. Разложение на множителя с помощью "квадратичного решета"
- •7.3 Сравнение длин симметричных и открытых ключей
- •7.4 Вскрытие в день рождения против однонаправленных хэш-функций
- •7.5 Каков должны быть длина ключа?
- •8 Управление ключами
- •8.1 Генерация ключей
- •Табл-1. Количество возможных ключей в различных пространствах ключей
- •8.2 Нелинейные пространства ключей
- •8.3 Передача ключей
- •8.4 Проверка ключей
- •8.5 Использование ключей
- •8.6 Обновление ключей
- •8.7 Хранение ключей
- •8.8 Резервные ключи
- •8.9 Скомпрометированные ключи
- •8.10 Время жизни ключей
- •8.11 Разрушение ключей
- •8.12 Управление открытыми ключами
- •9 Типы алгоритмов и криптографические режимы
- •9.1 Режим электронной шифровальной книги
- •9.2 Повтор блока
- •9.3 Режим сцепления блоков шифра
- •9.4 Потоковые шифры
- •9.5 Самосинхронизирующиеся потоковые шифры
- •9.6 Режим обратной связи по шифру
- •9.7 Синхронные потоковые шифры
- •9.8 Режим выходной обратной связи
- •9.9 Режим счетчика
- •9.10 Другие режимы блочных шифров
- •9.11 Выбор режима шифра
- •9.12 Чередование
- •9.13 Блочные шифры против потоковых
- •10 Использование алгоритмов
- •10.1 Выбор алгоритма '
- •10.2 Криптография с открытыми ключами против симметричной криптографии
- •10.3 Шифрование каналов связи
- •10.4 Шифрование данных для хранения
- •10.5 Аппаратный и программный способы шифрования
- •10.6 Сжатие, кодирование и шифрование
- •10.7 Обнаружение шифрования
- •10.8 Как прятать шифротекст в шифротексте
- •10.9 Разрушение информации
- •Часть III Криптографические алгоритмы Математические основы Теория информации
- •Энтропия и неопределенность
- •Норма языка
- •Безопасность криптосистемы
- •Практическое использование теории информации
- •Путаница и диффузия
- •Теория сложности
- •Сложность алгоритмов
- •Сложность проблем
- •Теория чисел
- •Арифметика вычетов
- •Простые числа
- •Наибольший общий делитель
- •Обратные значения по модулю
- •Решение для коэффициентов
- •Малая теорема Ферма
- •Функция Эйлера
- •Китайская теорема об остатках
- •Квадратичные вычеты
- •Символ Лежандра
- •Символ Якоби
- •Целые числа Блюма
- •Генераторы
- •Вычисление в поле Галуа
- •Разложение на множители
- •Квадратные корни по модулю n
- •Генерация простого числа
- •Практические соображения
- •Сильные простые числа
- •Дискретные логарифмы в конечном поле
- •Вычисление дискретных логарифмов в конечной группе
- •Стандарт шифрования данных des (Data Encryption Standard) Введение
- •Разработка стандарта
- •Принятие стандарта
- •Проверка и сертификация оборудования des
- •Описание des
- •Начальная перестановка
- •Преобразования ключа
- •Перестановка с расширением
- •Подстановка с помощью s-блоков
- •Перестановка с помощью p-блоков
- •Заключительная перестановка
- •Дешифрирование des
- •Режимы des
- •Аппаратные и программные реализации des
- •Безопасность des
- •Слабые ключи
- •Ключи-дополнения
- •Алгебраическая структура
- •Длина ключа
- •Количество этапов
- •Проектирование s-блоков
- •Дополнительные результаты
- •Дифференциальный и линейный криптоанализ Дифференциальный криптоанализ
- •Криптоанализ со связанными ключами
- •Линейный криптоанализ
- •Дальнейшие направления
- •Реальные критерии проектирования
- •Варианты des Многократный des
- •Des с независимыми подключами
- •Обобщенный des
- •Des с измененными s-блоками
- •Насколько безопасен сегодня des?
- •Другие блочные шифры
- •Описание Madryga
- •Криптоанализ и Madryga
- •Описание feal
- •Криптоанализ feal
- •Патенты
- •Патенты и лицензии
- •Описание loki91
- •Криптоанализ loki91
- •Патенты и лицензии
- •Патенты
- •Обзор idea
- •Описание idea
- •Скорость idea
- •Криптоанализ idea
- •Режимы работы и варианты idea
- •Патенты и лицензии
- •Безопасность mmb
- •И еще о блочных шифрах гост
- •Описание гост
- •Криптоанализ гост
- •Описание Blowfish
- •Безопасность Blowfish
- •Описание safer k-64
- •Безопасность safer k-64
- •Описание s-Way
- •Другие блочные алгоритмы
- •Теория проектирования блочного шифра
- •Сети Фейстела
- •Простые соотношения
- •Групповая структура
- •Слабые ключи
- •Устойчивость к дифференциальному и линейному криптоанализу
- •Проектирование s-блоков
- •Проектирование блочного шифра
- •Использование однонаправленных хэш-функций
- •Шифр краткого содержания сообщения
- •Безопасность шифров, основанных на однонаправленных хэш-функциях
- •Выбор блочного алгоритма
- •Объединение блочных шифров
- •15.1 Двойное шифрование
- •15.2 Тройное шифрование с двумя ключами
- •Тройное шифрование с тремя ключами
- •Тройное шифрование с минимальным ключом (temk)
- •Режимы тройного шифрования
- •Варианты тройного шифрования
- •15.3 Удвоение длины блока
- •15.4 Другие схемы многократного шифрования
- •Двойной ofb/счетчик
- •Пятикратное шифрование
- •15.5 Уменьшение длины ключа в cdmf
- •15.6 Отбеливание
- •15.7 Многократное последовательное использование блочных алгоритмов
- •15.8 Объединение нескольких блочных алгоритмов
- •Генераторы псевдослучайных последовательностей и потоковые шифры
- •16.1 Линейные конгруэнтные генераторы
- •Объединение линейных конгруэнтных генераторов
- •16.2 Сдвиговые регистры с линейной обратной связью
- •Программная реализация lfsr
- •16.3 Проектирование и анализ потоковых шифров
- •Линейная сложность
- •Корреляционная независимость
- •Другие вскрытия
- •16.4 Потоковые шифры на базе lfsr
- •Генератор Геффа
- •Обобщенный генератор Геффа
- •Генератор Дженнингса
- •Генератор "стоп-пошел" (Stop-and-Go) Both-Piper
- •Чередующийся генератор "стоп-пошел"
- •Двусторонний генератор "стоп-пошел"
- •Пороговый генератор
- •Самопрореживающие (Self-Decimated) генераторы
- •Многоскоростной генератор с внутренним произведением (inner-product)
- •Суммирующий генератор
- •Каскад Голлманна
- •Прореживаемый генератор
- •Самопрореживаемый генератор
- •16.9 Аддитивные генераторы
- •16.11 Алгоритм m
- •Безопасность pkzip
- •Другие потоковые шифры и генераторы настоящих случайных последовательностей
- •Семейство псевдо случайных функций
- •Описание seal
- •Безопасность seal
- •Патенты и лицензии
- •17.4 Сдвиговые регистры с обратной связью по переносу
- •17.5 Потоковые шифры, использующие fcsr
- •Каскадные генераторы
- •Комбинированные генераторы fcsr
- •Каскад lfsr/fcsr с суммированием/четностью
- •Чередующиеся генераторы "стоп-пошел"
- •Прореживаемые генераторы
- •17.6 Сдвиговые регистры с нелинейной обратной связью
- •17.7 Другие потоковые шифры
- •Генератор Плесса (Pless)
- •Генератор на базе клеточного автомата
- •Генератор 1/p
- •Другие схемы
- •17.8 Системно-теоретический подход к проектированию потоковых шифров
- •17.9 Сложностно-теоретический подход к проектированию потоковых шифров
- •Генератор псевдослучайных чисел Шамира
- •Генератор Blum-Micali
- •17.10 Другие подходы к проектированию потоковых шифров
- •Шифр "Рип ван Винкль"
- •Рандомизированный потоковый шифр Диффи
- •Рандомизированный потоковый шифр Маурера
- •17.11 Шифры с каскадом нескольких потоков
- •17.12 Выбор потокового шифра
- •17.13 Генерация нескольких потоков из одного генератора псевдослучайной последовательности
- •17.14 Генераторы реальных случайных последовательностей
- •Использование случайного шума
- •Использование таймера компьютера
- •Измерение скрытого состояния клавиатуры
- •Смещения и корреляции
- •Извлеченная случайность
- •Однонаправленные хэш-функции
- •18.1 Основы
- •Длины однонаправленных хэш-функций
- •Обзор однонаправленных хэш-функций
- •Криптоанализ Snefru
- •Криптоанализ n-хэш
- •Описание md5
- •Безопасность md5
- •18.7 Алгоритм безопасного хэширования (Secure Hash Algorithm, sha)
- •Описание sha
- •Безопасность sha
- •18.10 Другие однонаправленные хэш-функции
- •18.11 Однонаправленные хэш-функции, использующие симметричные блочные алгоритмы
- •Схемы, в которых длина хэш-значения равна длине блока
- •Модификация схемы Davies-Meyer
- •Loki с удвоенным блоком
- •Параллельная схема Davies-Meyer
- •Тандемная (Tandem) и одновременная (Abreast) схемы Davies-Meyer
- •Другие схемы
- •18.12 Использование алгоритмов с открытым ключом
- •18.13 Выбор однонаправленной хэш-функции
- •18.14 Коды проверки подлинности сообщения
- •Алгоритм проверки подлинности сообщения (Message Authenticator Algorithm, maa)
- •Двунаправленный mac
- •Методы Джунемана
- •Однонаправленная хэш-функция mac
- •Mac с использованием потокового шифра
- •Алгоритмы с открытыми ключами
- •19.1 Основы
- •Безопасность алгоритмов с открытыми ключами
- •19.2 Алгоритмы рюкзака
- •Сверхвозрастающие рюкзаки
- •Создание открытого ключа из закрытого
- •Шифрование
- •Дешифрирование
- •Практические реализации
- •Безопасность метода рюкзака
- •Варианты рюкзака
- •Патенты
- •Аппаратные реализации rsa
- •Скорость rsa
- •Программные Speedups
- •Безопасность rsa
- •Вскрытие с выбранным шифротекстом против rsa
- •Вскрытие общего модуля rsa
- •Вскрытие малого показателя шифрования rsa
- •Вскрытие малого показателя дешифрирования rsa
- •Полученные уроки
- •Вскрытие шифрования и подписи с использованием rsa
- •Стандарты
- •Патенты
- •Патенты
- •Подписи ElGamal
- •Шифрование ElGamal
- •Скорость
- •Патенты
- •Другие алгоритмы, основанные на линейных кодах, исправляющих ошибки
- •19.8 Криптосистемы с эллиптическими кривыми
- •19.10 Криптосистемы с открытым ключом на базе конечных автоматов
- •Алгоритмы цифровой подписи с открытым ключом
- •20.1 Алгоритм цифровой подписи (digital signature algorithm, dsa)
- •Реакция на заявление
- •Описание dsa
- •Ускоряющие предварительные вычисления
- •Генерация простых чисел dsa
- •Шифрование ElGamal с dsa
- •Шифрование rsa с dsa
- •Безопасность dsa
- •Вскрытия k
- •Опасности общего модуля
- •Подсознательный канал в dsa
- •Патенты
- •20.2 Варианты dsa
- •20.3 Алгоритм цифровой подписи гост
- •20.4 Схемы цифровой подписи с использованием дискретных логарифмов
- •Безопасность esign
- •Патенты
- •20.7 Клеточные автоматы
- •20.8 Другие алгоритмы с открытым ключом
- •Схемы идентификации
- •Упрощенная схема идентификации Feige-Fiat-Shamir
- •Улучшения
- •Улучшенная схема подписи Fiat-Shamir
- •Другие улучшения
- •Патенты
- •Несколько подписей
- •Протокол проверки подлинности
- •Протокол цифровой подписи
- •Патенты
- •Преобразование схем идентификации в схемы подписи
- •Алгоритмы обмена ключами
- •Diffie-Hellman с тремя и более участниками *
- •Расширенный Diffie-Hellman
- •Обмен ключом без обмена ключом
- •Патенты
- •Протокол "точка-точка"
- •Трехпроходный протокол Шамира
- •Обмен зашифрованными ключами
- •Базовый протокол eke
- •Реализация eke с помощью rsa
- •Реализация eke с помощью ElGamal
- •Реализация eke с помощью Diffie-Hellman
- •Усиление eke
- •Расширенный eke
- •Применения eke
- •Защишенные переговоры о ключе
- •Распределение ключа для конференции и секретная широковещательная передача
- •Распределение ключей для конференции
- •Специальные алгоритмы для протоколов Криптография с несколькими открытыми ключами
- •Алгоритмы разделения секрета
- •Векторная схема
- •Более сложные пороговые схемы
- •Разделение секрета с мошенниками
- •Подсознательный канал
- •Уничтожение подсознательного канала в dsa
- •Другие схемы
- •Неотрицаемые цифровые подписи
- •Преобразуемые неотрицаемые подписи
- •Подписи, подтверждаемые доверенным лицом
- •Вычисления с зашифрованными данными Проблема дискретного логарифма
- •Бросание "честной" монеты
- •Бросание "честной" монеты с помощью квадратных корней
- •Бросание "честной" монеты с помощью возведения в степень по модулю p
- •Бросание "честной" монеты с помощью целых чисел Блюма
- •Однонаправленные сумматоры
- •Раскрытие секретов "все или ничего"
- •Честные и отказоустойчивые криптосистемы Честная схема Diffie-Hellman
- •Отказоустойчивая схема Diffie-Hellman
- •Доказательство с нулевым знанием для дискретного логарифма
- •Доказательство с нулевым знанием для возможности вскрыть rsa
- •Доказательство с нулевым знанием того, что n является числом Блюма
- •Слепые подписи
- •Передача с забыванием
- •Безопасные вычисления с несколькими участниками
- •Пример протокола
- •Вероятностное шифрование
- •Квантовая криптография
- •Часть IV Реальный мир Примеры реализаций
- •Протокол управления секретными ключами компании ibm
- •Модификация
- •Модель Kerberos
- •Как работает Kerberos
- •Атрибуты
- •Сообщения Kerberos версии 5
- •Получение первоначального мандата
- •Получение серверных мандатов
- •Запрос услуги
- •Kerberos версии 4
- •Безопасность Kerberos
- •Лицензии
- •Общая криптографическая архитектура ibm
- •Сертификаты
- •Протоколы проверки подлинности
- •Почта с повышенной секретностью privacy-enhanced mail (pem)
- •Документы pem
- •Сертификаты
- •Сообщения pem
- •Безопасность pem
- •Протокол безопасности сообщений
- •Интеллектуальные карточки
- •Стандарты криптографии с открытыми ключами
- •Универсальная система электронных платежей
- •Безопасный телефон at&t model 3600 telephone security device (tsd)
- •Политика Агентство национальной безопасности (nsa)
- •Коммерческая программа сертификации компьютерной безопасности
- •Национальный центр компьютерной безопасности (ncsc)
- •Национальный институт стандартов и техники
- •Международная ассоциация криптологических исследований
- •Оценка примитивов целостности race (ripe)
- •Условный доступ для Европы (cafe)
- •Профессиональные и промышленные группы, а также группы защитников гражданских свобод Информационный центр по электронной тайне личности (epic)
- •Фонд электронного фронтира (eff)
- •Ассоциация по вычислительной технике (acm)
- •Институт инженеров по электричеству и радиоэлектронике (ieee)
- •Ассоциация производителей программного обеспечения (spa)
- •Шифропанки
- •Патенты
- •Экспортное законодательство сша
- •§ 120.10 Технические данные.
- •§ 120.11 Открытый доступ.
- •§ 120.17 Экспорт.
- •Часть 121- Перечень вооружений сша
- •§ 121.1 Общие положения. Перечень вооружений сша
- •§ 125.2 Экспорт несекретных технических данных.
- •Экспорт и импорт криптографии за рубежом
- •Правовые вопросы
- •Схемы идентификации
- •Упрощенная схема идентификации Feige-Fiat-Shamir
- •Улучшения
- •Улучшенная схема подписи Fiat-Shamir
- •Другие улучшения
- •Патенты
- •Несколько подписей
- •Протокол проверки подлинности
- •Протокол цифровой подписи
- •Патенты
- •Преобразование схем идентификации в схемы подписи
- •Алгоритмы обмена ключами
- •Diffie-Hellman с тремя и более участниками *
- •Расширенный Diffie-Hellman
- •Обмен ключом без обмена ключом
- •Патенты
- •Протокол "точка-точка"
- •Трехпроходный протокол Шамира
- •Обмен зашифрованными ключами
- •Базовый протокол eke
- •Реализация eke с помощью rsa
- •Реализация eke с помощью ElGamal
- •Реализация eke с помощью Diffie-Hellman
- •Усиление eke
- •Расширенный eke
- •Применения eke
- •Защишенные переговоры о ключе
- •Распределение ключа для конференции и секретная широковещательная передача
- •Распределение ключей для конференции
- •Специальные алгоритмы для протоколов Криптография с несколькими открытыми ключами
- •Алгоритмы разделения секрета
- •Векторная схема
- •Более сложные пороговые схемы
- •Разделение секрета с мошенниками
- •Подсознательный канал
- •Уничтожение подсознательного канала в dsa
- •Другие схемы
- •Неотрицаемые цифровые подписи
- •Преобразуемые неотрицаемые подписи
- •Подписи, подтверждаемые доверенным лицом
- •Вычисления с зашифрованными данными Проблема дискретного логарифма
- •Бросание "честной" монеты
- •Бросание "честной" монеты с помощью квадратных корней
- •Бросание "честной" монеты с помощью возведения в степень по модулю p
- •Бросание "честной" монеты с помощью целых чисел Блюма
- •Однонаправленные сумматоры
- •Раскрытие секретов "все или ничего"
- •Честные и отказоустойчивые криптосистемы Честная схема Diffie-Hellman
- •Отказоустойчивая схема Diffie-Hellman
- •Доказательство с нулевым знанием для дискретного логарифма
- •Доказательство с нулевым знанием для возможности вскрыть rsa
- •Доказательство с нулевым знанием того, что n является числом Блюма
- •Слепые подписи
- •Передача с забыванием
- •Безопасные вычисления с несколькими участниками
- •Пример протокола
- •Вероятностное шифрование
- •Квантовая криптография
- •Часть IV Реальный мир Примеры реализаций
- •Протокол управления секретными ключами компании ibm
- •Модификация
- •Модель Kerberos
- •Как работает Kerberos
- •Атрибуты
- •Сообщения Kerberos версии 5
- •Получение первоначального мандата
- •Получение серверных мандатов
- •Запрос услуги
- •Kerberos версии 4
- •Безопасность Kerberos
- •Лицензии
- •Общая криптографическая архитектура ibm
- •Сертификаты
- •Протоколы проверки подлинности
- •Почта с повышенной секретностью privacy-enhanced mail (pem)
- •Документы pem
- •Сертификаты
- •Сообщения pem
- •Безопасность pem
- •Протокол безопасности сообщений
- •Интеллектуальные карточки
- •Стандарты криптографии с открытыми ключами
- •Универсальная система электронных платежей
- •Безопасный телефон at&t model 3600 telephone security device (tsd)
- •Политика Агентство национальной безопасности (nsa)
- •Коммерческая программа сертификации компьютерной безопасности
- •Национальный центр компьютерной безопасности (ncsc)
- •Национальный институт стандартов и техники
- •Международная ассоциация криптологических исследований
- •Оценка примитивов целостности race (ripe)
- •Условный доступ для Европы (cafe)
- •Профессиональные и промышленные группы, а также группы защитников гражданских свобод Информационный центр по электронной тайне личности (epic)
- •Фонд электронного фронтира (eff)
- •Ассоциация по вычислительной технике (acm)
- •Институт инженеров по электричеству и радиоэлектронике (ieee)
- •Ассоциация производителей программного обеспечения (spa)
- •Шифропанки
- •Патенты
- •Экспортное законодательство сша
- •§ 120.10 Технические данные.
- •§ 120.11 Открытый доступ.
- •§ 120.17 Экспорт.
- •Часть 121- Перечень вооружений сша
- •§ 121.1 Общие положения. Перечень вооружений сша
- •§ 125.2 Экспорт несекретных технических данных.
- •Экспорт и импорт криптографии за рубежом
- •Правовые вопросы
Теория чисел
Это не книга по теории чисел, поэтому я только набросаю ряд идей, используемых в криптографии. Если вам нужно подробное математическое изложение теории чисел, обратитесь к одной из этих книг: [1430, 72, 1171, 12, 959, 681, 742, 420]. Моими любимыми книгами по математике конечных полей являются [971, 1042]. См. также [88, 1157, 1158, 1060].
Арифметика вычетов
Вы все учили математику вычетов в школе. Иногда ее называли "арифметикой часов". Если Милдред сказала, что она будет дома к 10:00, и опоздала на 13 часов, то когда она придет домой, и на сколько лет отец лишит ее водительских прав? Это арифметика по модулю 12. Двадцать три по модулю 12 равно 11.
(10 + 13) mod 12 = 23 mod 12 = 11 mod 12
Другим способом записать это является утверждение об эквивалентности 23 и 11 по модулю 12:
10 + 13 11 (mod 12)
В основном, a b (mod n), если a = b + kn для некоторого целого k. Если a неотрицательно и b находится между 0 и n, можно рассматривать b как остаток при делении a на n. Иногда, b называется вычетом a по модулю n. Иногда a называется конгруэнтным b по модулю n (знак тройного равенства, , обозначает конгруэнтность). Одно и то же можно сказать разными способами.
Множество чисел от 0 до n-1 образует то, что называется полным множеством вычетов по модулю n. Это означает, что для любого целого a, его остаток по модулю n является некоторым числом от 0 до n-1.
Операция a mod n обозначает остаток от a, являющийся некоторым целым числом от 0 до n-1. Эта операция называется приведением по модулю. Например, 5 mod 3 = 2.
Это определение mod может отличаться от принятого в некоторых языках программирования. Например, оператор получения остатка в языке PASCAL иногда возвращает отрицательное число. Он возвращает число между -(n-1) и n-1. В языке C оператор % возвращает остаток от деления первого выражения на второе, оно может быть отрицательным числом, если любой из операндов отрицателен. Для всех алгоритмов в этой книге проверяйте, что вы добавляете n к результату операции получения остатка, если она возвращает отрицательное число.
Арифметика остатков очень похожа на обычную арифметику: она коммутативна, ассоциативна и дистрибутивна. Кроме того, приведение каждого промежуточного результата по модулю n дает тот же результат, как и выполнение всего вычисления с последующим приведением конечного результата по модулю n.
(a + b) mod n == ((a mod n) + (b mod n)) mod n
(a - b) mod n == ((a mod n) - (b mod n)) mod n
(a * b) mod n == ((a mod n) * (b mod n)) mod n
(a * (b+c)) mod n == (((a*b) mod n) + ((a*c) mod n)) mod n
Вычисление mod n часто используется в криптографии, так как вычисление дискретных логарифмов и квадратных корней mod n может быть нелегкой проблемой. Арифметика вычетов, к тому же, легче реализуется на компьютерах, поскольку она ограничивает диапазон промежуточных значений и результата. Для k-битовых вычетов n, промежуточные результаты любого сложения, вычитание или умножения будут не длиннее, чем 2k бит. Поэтому в арифметике вычетов мы можем выполнить возведение в степень без огромных промежуточных результатов. Вычисление степени некоторого числа по модулю другого числа,
ax mod n,
представляет собой просто последовательность умножений и делений, но существуют приемы, ускоряющие это действие. Один из таких приемов стремится минимизировать количество умножений по модулю, другой - оптимизировать отдельные умножения по модулю. Так как операции дистрибутивны, быстрее выполнить возведение в степень как поток последовательных умножений, каждый раз получая вычеты. Сейчас вы не чувствуете разницы, но она будет заметна при умножении 200-битовых чисел.
Например, если вы хотите вычислить a8 mod n, не выполняйте наивно семь умножений и одно приведение по модулю:
(a * a * a * a * a * a * a * a) mod n
Вместо этого выполните три меньших умножения и три меньших приведения по модулю:
((a2 mod n)2 mod n)2 mod n
Точно также,
a16 mod n =(((a2 mod n)2 mod n)2 mod n)2 mod n
Вычисление ax, где x не является степенью 2, ненамного труднее. Двоичная запись представляет x в виде суммы степеней 2: 25 - это бинарное 11001, поэтому 25 = 24 + 23 + 20. Поэтому
a25 mod n = (a*a24) mod n = (a* a8*a16) mod n =
= (a*(( a2) 2) 2*((( a2) 2) 2) 2) mod n = (a*((( a*a2) 2) 2) 2) mod n
С продуманным сохранением промежуточных результатов вам понадобится только шесть умножений:
(((((((a2 mod n)* a)2 mod n)2 mod n)2 mod n)2 mod n)2 *a) mod n
Такой прием называется цепочкой сложений [863], или методом двоичных квадратов и умножения. Он использует простую и очевидную цепочку сложений, в основе которой лежит двоичное представление числа. На языке C это выглядит следующим образом:
unsigned long qe2(unsigned long x, unsigned long y, unsigned long n) {
unsigned long s, t, u;
int i;
s=1; t=x; u=y;
while (u) {
if(u&1) s=(s*t)%n;
u>>1;
t=(t*t)%n;
}
return(s)
}
А вот другой, рекурсивный, алгоритм:
unsigned long fast_exp(unsigned long x, unsigned long y, unsigned long N) {
unsigned long tmp;
if(y==l) return(x % N);
if (l^(x&l)) {
tmp= fast_exp(x,y/2,N);
return ((tmp*tmp)%N);
else {
tmp = fast_exp(x,(y-1)/2,N);
tmp = (tmp*tmp)%N;
tmp = (tmp*x)%N;
return (tmp);
}
}
Этот метод уменьшает количество операций, в среднем, до 1.5*k операций, где k - длина числа x в битах. Найти способ вычисления с наименьшим количеством операций - трудная проблема (было доказано, что последовательность должна содержать не меньше k-1 операций), но нетрудно снизить число операций до 1.1*k или даже лучше при больших k.
Эффективным способом много раз выполнять приведение по модулю для одного n является метод Монтгомери [1111]. Другой метод называется алгоритмом Баррета [87]. Эффективность описанного алгоритма и этих двух методов рассматривается в [210]: алгоритм, рассмотренный мною, является наилучшим для единичного приведения по модулю, алгоритм Баррета - наилучшим для малых аргументов, а метод Монтгомери - наилучшим для обычного возведения в степень по модулю. (Метод Монтгомери также использует преимущество малых показателей степени, используя прием, называющийся смешанной арифметикой.)
Операция, обратная возведению в степень по модулю n, вычисляет дискретный логарифм. Я дальше вкратце рассмотрю эту операцию.
