- •Предисловие
- •Глава 1. Введение
- •Некоторые аспекты безопасности связи
- •Шифр Юлия Цезаря
- •Несколько основных определений
- •Коды и шифры
- •Оценка стойкости системы шифрования
- •Коды, обнаруживающие и исправляющие ошибки
- •Другие методы сокрытия содержания сообщений
- •Модульная арифметика
- •Модульное сложение и вычитание букв
- •Заключение
- •Глава 2. От Юлия Цезаря до простой замены
- •Шифры Юлия Цезаря и их вскрытие
- •Шифры простой замены
- •Вскрытие шифра простой замены
- •Частоты встречаемости букв в других языках, кроме английского
- •Сколько знаков необходимо для дешифрования простой замены?
- •Глава 3. Многоалфавитные системы
- •Усиление системы Юлия Цезаря: шифры Вижанэра
- •Вскрытие шифра Вижанэра
- •Индикаторы
- •Одноключевые сообщения
- •Распознавание одноключевых сообщений
- •Какой объем текста необходим для дешифрования шифра Вижанэра?
- •Цилиндр Джефферсона
- •Глава 4. Шифры-головоломки
- •Перестановки
- •Простая перестановка
- •Двойная перестановка
- •Другие виды перестановок
- •Регулярные перестановочные таблицы
- •Нерегулярные перестановочные таблицы
- •Оценка стойкости шифров перестановки
- •Общая концепция двойного шифрования
- •Глава 5. Двухбуквенные шифры
- •Замена "монограф-диграф"
- •МДПМ-шифры
- •Система "диграф-диграф"
- •Шифр Плейфера*)
- •Расшифрование в системе Плейфера
- •Криптоаналитические аспекты системы Плейфера
- •Двойной шифр Плейфера
- •Глава 6. Коды
- •Характеристики кодов
- •Одночастевые и двухчастевые коды
- •Код плюс аддитивное шифрование
- •Глава 7. Шифры для шпионов
- •Шифры-решетки
- •Книжные шифры
- •Использование книжного шифра
- •Частоты встречаемости букв в книжных шифрах
- •Вскрытие книжного шифра
- •Индикаторы
- •Катастрофические ошибки при использовании книжного шифра
- •Шифры "агента Гарбо"
- •Первый шифр "агента Гарбо"
- •Второй шифр "агента Гарбо"
- •Одноразовый блокнот
- •Глава 8. Получение случайных чисел и букв
- •Случайные последовательности
- •Получение случайных последовательностей
- •Бросание монеты
- •Бросание костей
- •Извлечение из урны (по типу лотереи)
- •Космические лучи
- •Шум от усилителей
- •Псевдослучайные последовательности
- •Линейные рекурренты
- •Использование последовательности двоичных знаков гаммы для шифрования
- •Двоичные линейные последовательности как генераторы гаммы
- •Криптоанализ линейной рекурренты
- •Повышение стойкости двоичной гаммы
- •Генераторы псевдослучайных чисел
- •Метод срединных квадратов
- •Линейные конгруэнтные генераторы
- •Глава 9. Шифрмашина "Энигма"
- •Историческая справка
- •Первая "Энигма"
- •Шифрование с использованием контактных колес
- •Шифрование в "Энигме"
- •Коммутатор "Энигмы"
- •Ахиллесова пята "Энигмы"
- •Цепочки индикаторов в "Энигме"
- •Выравнивание цепочек
- •Идентификация колеса R1 и его угловой установки
- •Двойное шифрование в "Энигме"
- •"Энигма" Абвера
- •Глава 10. Шифрмашина "Хагелин"
- •Историческая справка
- •Конструкция шифрмашины «Хагелин»
- •Шифрование при помощи шифрмашины "Хагелин"
- •Выбор установок барабана в шифрмашине "Хагелин"
- •Теоретический объем перебора для шифрмашины "Хагелин"
- •Вскрытие установок "Хагелина" по отрезку гаммы
- •Дополнительные возможности шифрмашины "Хагелин"
- •Смещение
- •Определение смещения по шифрованному тексту
- •Перекрытия
- •Вскрытие шифрмашины "Хагелин" только по шифрованному тексту
- •Глава 11. После "Энигмы"
- •SZ42 - предтеча электронных машин
- •Описание шифрмашины SZ42
- •Шифрование в машине SZ42
- •Вскрытие шифрмашины SZ42 и определение ее угловых установок
- •Модификации шифрмашины SZ42
- •Глава 12. Криптография с открытым ключом
- •Историческая справка
- •Вопросы безопасности
- •Защита программ и данных
- •Шифрование программ, данных и сообщений
- •Задача распределения ключей
- •Система ключевого обмена Диффи-Хеллмана
- •Стойкость системы Диффи-Хеллмана
- •Глава 13. Шифрование и Интернет
- •Обобщение шифра простой замены
- •Факторизация больших целых чисел
- •Стандартный метод факторизации
- •Малая теорема Ферма
- •Теорема Ферма-Эйлера (для случая системы RSA)
- •Ключи зашифрования и расшифрования в системе RSA
- •Процессы зашифрования и расшифрования в системе RSA
- •Каким образом хозяин ключей отвечает корреспондентам?
- •Американский Стандарт Шифрования Данных (DES)*)
- •Общие сведения
- •Процедура зашифрования
- •Процедура расшифрования
- •Стойкость DES-алгоритма
- •Зацепление
- •Реализации DES-алгоритма
- •Совместное использование алгоритмов RSA и DES
- •Полезное замечание
- •После DES-алгоритма
- •Проверка подлинности сообщения и удостоверение подлинности подписи
- •Криптография эллиптической кривой
- •Приложение. Математические вопросы
- •Глава 2
- •М1. Совпадения знаков в алфавитах замены
- •М2. Снижение стойкости при использовании взаимно-обратных алфавитов
- •M3. Парадокс дней рождения
- •Глава 3
- •М4. Евклидово доказательство бесконечности множества простых чисел
- •Глава 6
- •М5. Последовательность чисел Фибоначчи
- •Глава 7
- •М6. Частота встречаемости букв для книжного шифра
- •М7. Одноразовый блокнот дешифровать невозможно
- •Глава 8
- •М8. Частота появления случайных чисел на странице
- •М9. Комбинирование двух последовательностей двоичных знаков гаммы, имеющих отклонения
- •М10. Последовательность типа Фибоначчи
- •М11. Двоичные линейные рекурренты
- •M12. Восстановление двоичной линейной рекурренты по отрезку гаммы
- •М13. Получение псевдослучайных чисел
- •Глава 9
- •М14. Распайка колёс шифрмашины "Энигма"
- •М15. Число возможных отражателей шифрмашины "Энигма"
- •М16. Вероятность одноключевых сообщений для "Энигмы"
- •М17. Среднее число индикаторов, необходимое для построения полных цепочек
- •Глава 10
- •М18. Число возможных барабанов шифрмашины "Хагелин"
- •М19. Максимальная кратность значения зацепления, которая может встретиться при вычислении разности гаммы шифрмашины "Хагелин"
- •M20. Определение смещения шифрмашины "Хагелин" с помощью коэффициента корреляции
- •Глава 13
- •M21. (Порядок роста количества простых чисел)
- •M22. Вычисление остатка с использованием модульной арифметики
- •М23. Доказательство теоремы Ферма-Эйлера
- •М24. Нахождение чисел, "предположительно" являющихся простыми
- •M25. Алгоритм Евклида
- •М26. Эффективность возведения в степень методом последовательного возведения в квадрат
- •М27. Число ложных ответов при дешифровании DES-алгоритма методом "встречного поиска "
- •М28. Криптография эллиптической кривой
- •Решения задач
- •Глава 2
- •Глава 3
- •Глава 4
- •Глава 5
- •Глава 6
- •Глава 7
- •Глава 8
- •Глава 9
- •Глава 10
- •Глава 11
- •Глава 13
- •Литература
213
Приложение. Математические вопросы
Глава 2
М1. Совпадения знаков в алфавитах замены
Данная задача называется задачей о числе смещений элементов множества; ее решение в качестве частного случая может быть получено методом,
известным под названиями принципа включения-исключения и классического метода решета. Доказательство этого метода можно найти в книгах по комбинаторике, таких как [2.6]. Применяя принцип включения-исключения, нетрудно показать, что среди всех перестановок множества (1,2,...,n) доля тех перестановок, в которых ни одно число не стоит на "своем" месте (то есть имеется n смещений), равна
11 11! 21! 31! 41! 51! ...и т.д. до (n+1)-го слагаемого.
Эта сумма дробей очень быстро сходится к значению 0,3678... , то есть к значению, обратному числу e (известному тем, кто знаком с натуральными логарифмами). Значения этой суммы для n от 0 до 6 с точностью до трех десятичных знаков равны 1, 0, 0.5, 0.333, 0.375, 0.367 и 0.368. Поэтому для значений n, больших 5, размер этой доли практически один и тот же. Это означает, что в перестановке знаков 26-буквенного алфавита примерно в 37% случаев не будет ни одной буквы, стоящей на "своем" месте, а в 63% случаев хотя бы одна такая буква найдется.
М2. Снижение стойкости при использовании взаимно-обратных алфавитов
Для первой буквы существует
26 25
2
вариантов, так как выбрать пару A и W - это то же самое, что выбрать пару W и A. Аналогично, для второй пары букв существует
24 23
2
вариантов, и так далее. Может показаться, что отсюда следует, что общее число взаимно-обратных алфавитов равно
214
26 25 24 23 ... 4 3 2 1 , 2 2 ... 2 2
однако это не так, потому что сформированные 13 пар можно переставлять между собой в любом порядке, и сам алфавит от этого не изменится. Например, если мы сначала объединим в пару буквы A и W, а затем буквы B и K, то получим точно такой же результат, как если бы мы сначала сформировали пару B и K, а затем пару A и W. Поэтому полученное выше число необходимо разделить на
13!=13 12 11 ... 2 1
(это число превосходит 6227000000). Так как в знаменателе уже стоит число2 в 13-й степени, что уменьшает число вариантов в 8192 раза, то мы получаем сокращение числа алфавитов замены более чем в 50000000000000 раз. В итоге это означает, что теперь число возможных алфавитов замены будет не
более, чем 10 в 13-й степени, в то время как изначально их было более, чем 10 в 26-й степени.*)
Это может показаться странным, но при этом оказывается, что выгоднее объединять в пары не все 26 букв. Число вариантов будет больше, если только 22 буквы составляют пары, а оставшиеся 4 остаются без изменения. Это происходит потому, что если объединить 2k букв в пары и сохранить оставшиеся (26-2k) букв неизменными, то число вариантов будет равно
26! |
, |
k!(26 2k )!2k |
и это число достигает максимума при k=11. И если для шифров простой замены этот факт не имеет значения, то при анализе числа пар в коммутаторе "Энигмы" он становится важным, как мы увидим в главе 9.
M3. Парадокс дней рождения
Вероятность того, что два случайно выбранных человека родились в один и тот же день, равна 1/365. Мы не будем учитывать високосные годы, поскольку никакого заметного влияния на результат это не окажет.
*) При использовании взаимно-обратных алфавитов говорить о снижении стойкости можно не только как о сокращении общего числа возможных вариантов алфавитов замены, но и о непосредственном упрощении способа дешифрования. Действительно, если криптоаналитик знает, что используется именно взаимнообратный алфавит, то при вскрытии такого шифра простой замены он при любом сопоставлении пары "буква открытого текста - буква шифрованного текста" автоматически получает еще одну пару букв (например, из A W сразу следует W A). Это кардинально облегчает ему процесс вскрытия и фактически сводит 26-буквенный алфавит к "алфавиту", состоящему из 13-ти "пар букв". (прим. перев.)