- •Предисловие
- •Глава 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
- •Литература
23
Глава 2. От Юлия Цезаря до простой замены
Шифры Юлия Цезаря и их вскрытие
В шифре, которым пользовался Юлий Цезарь, каждая буква алфавита сдвигается на три позиции по циклу, так что A заменяется на D, B - на E,..., W - на Z, X - на A, Y - на B, и Z - на C. И хотя Юлий Цезарь сдвигал буквы только на три позиции, он вполне мог бы (по своему желанию) сдвигать их на любое число позиций от 1 до 25. Поэтому шифр Юлия Цезаря имеет 25 вариантов. Отсюда вытекает, как такой шифр можно вскрыть: запишем шифрованное сообщение, а под ним на 25 строчках выписываем 25 вариантов, которые получаются сдвигом каждой буквы на 1, 2, 3, ... ,25 позиций соответственно. Одна из этих 25 строк будет содержать исходное сообщение.
Пример 2.1 Текст сообщения, зашифрованного по системе Юлия Цезаря, имеет вид
VHFX TM HGVX
Требуется дешифровать сообщение.
Решение Запишем шифрованное сообщение и 25 его сдвигов в столбик, проставив
значения сдвигов слева от каждой строчки (см. таблицу 2.1).
Таблица 2.1
Сдвиг Сообщение
0VHFX TM HGVX
1WIGY UN IHWY
2XJHZ VO JIXZ
3YKIA WP KJYA
4ZLJB XQ LKZB
5AMKC YR MLAC
6BNLD ZS NMBD
7COME AT ONCE
Мы видим, что в шифре использован сдвиг на 19 позиций, поскольку шифрованный текст, будучи сдвинутым на 7 позиций вперед, дает открытый текст. Это означает, что для получения шифрованного текста открытый текст нужно сдвинуть на (26-7)=19 позиций. Весьма вероятно (если предполагать,
24
что ни при каком другом сдвиге не получается осмысленного сообщения), что мы правильно дешифровали это сообщение, и поэтому нет необходимости выписывать оставшиеся варианты. Такое допущение о единственности решения вполне обоснованно, когда шифрованное сообщение содержит более пяти-шести знаков; но если сообщение очень короткое, возможных решений может быть несколько. Так, например, если получено шифрованное сообщение вида
DSP
то возможны три решения, как показано в таблице 2.2.
Таблица 2.2
Сдвиг |
Сообщение |
2 |
FUR |
8 |
LAX |
15 |
SHE |
|
|
Они не имеют особого смысла как сообщения, хотя можно вообразить ситуации, в которых они могут содержать важную информацию. Например, это могут быть имена лошадей, которым предстоит победить на скачках. Этот пример приведен главным образом для иллюстрации важного и часто возникающего вопроса: какой длины должно быть шифрованное сообщение, чтобы решение было единственным? Ответ на этот вопрос зависит от системы шифрования и может быть практически любым числом от "примерно четырех-пяти букв" (для шифра Юлия Цезаря) до "бесконечности" (для системы с одноразовым блокнотом, как мы увидим в главе 7).
Заканчивая рассказ о шифре Юлия Цезаря, приведем довольно забавный пример неоднозначного решения. Пусть шифрованный текст выглядит так:
MSG
(это похоже на аббревиатуру английского слова "message" - "сообщение"). В таблице 2.3 даны два возможных решения, но отсюда вовсе не следует, что данный шифр является простым способом перевода французского текста на английский язык.
Таблица 2.3
Сдвиг |
Сообщение |
2 |
OUI |
12 |
YES |
|
|
25
Шифры простой замены
В шифре простой замены обычный алфавит заменяется переставленным ("перетасованным"). Это означает, что каждая буква обычного алфавита заменяется на букву, имеющую тот же порядковый номер в переставленном алфавите.
Вот пример перестановки алфавита: первая строчка - обычный латинский алфавит, вторая - переставленный.
AáBáCáDáEáFáGáHáIáJáKáLáMáNáOáPáQáRáSáTáUáVáWáXáYá
Z
YáMáIáHáBáAáWáCáXáVáDáNáOáJáKáUáQáPáRáTáFáEáLáGáZá
S
Если использовать шифр простой замены с этим алфавитом шифрования для зашифрования открытого сообщения
COME AT ONCE,
которое мы приводили ранее, то получится шифрованный текст
IKOB YT KJIB.
Попытка дешифровать его как шифр Юлия Цезаря к успеху не приведет. Допустим, криптоаналитик решил, что перед ним шифр простой замены.
Сможет ли он дешифровать его? Он наверняка заметит, что сообщение состоит из трех слов из 4-х, 2-х и 4-х букв соответственно, что буквы 1 и 9, 2 и 7, 4 и 10 совпадают. Таким образом, хотя всего здесь десять букв, различных среди них только семь. Отсюда следует, что любое множество из трех слов на английском, или любом другом языке, которое удовлетворяет этим условиям, является возможным решением. Поэтому, наряду с другими возможностями, решениями в равной степени могут оказаться следующие сообщения:
GIVE TO INGE
HAVE TO ACHE
или
SECT IN EAST.
Ни один из этих текстов не выглядит достаточно правдоподобным, но каждый из них является решением. Это показывает, что короткое сообщение, зашифрованное простой заменой, может быть дешифровано неоднозначно. И снова мы возвращаемся к очевидному вопросу, который уже ставился нами ранее: "Из скольких знаков должно состоять сообщение, зашифрованное
26
таким способом, чтобы решение было единственным?" В случае шифра простой замены нужно, по-видимому, иметь не меньше 50 знаков, чтобы гарантировать единственность решения в большинстве случаев, но дешифрование столь короткого сообщения - это отнюдь не простая задача. Как показывает опыт, чтобы решение было не только единственным, но и его было бы нетрудно получить, необходимо около двухсот знаков текста. К этому вопросу мы еще вернемся позднее.
Есть еще два незначительных замечания по поводу последнего примера и приведенного выше алфавита простой замены. Первое замечание состоит в том, что задача дешифрования сообщения в данном случае оказалась значительно легче, чем могла бы быть, поскольку шифрованный текст был записан с сохранением пробелов между словами. Тем самым становятся известны длины слов исходного сообщения. Есть два стандартных способа устранения этой слабости. Первый способ заключается в том, чтобы, игнорируя пробелы и знаки препинания, записать сообщение в виде строки знаков латинского алфавита. Тогда открытый и шифрованный тексты последнего примера будут выглядеть так:
COMEATONCE IKOBYTKJIB
В результате криптоаналитик не будет знать, состоит ли сообщение из одного слова из 10-ти букв или из нескольких слов меньшей длины, и следовательно, число возможных вариантов решения значительно возрастает. Недостаток такого подхода состоит в том, что получателю сообщения приходится вставлять в него пробелы и знаки пунктуации в те места, которые он сочтет для этого подходящими, а это иногда может привести к двусмысленности*) . Таким образом, получение открытого текста усложняется и для криптоаналитика, и для адресата.
Второй способ, который применяется гораздо чаще, состоит в том, чтобы вместо пробела использовать какую-нибудь редкую букву, например X. В тех редких случаях, когда встречается реальная буква X, ее заменяют на другую комбинацию букв, например KS. Если проделать это с нашим примером, то само сообщение и соответствующий шифрованный текст запишутся так:
COMEXATXONCE
IKOBGYTGKJIB,
поскольку буква X переходит в G в алфавите шифрования, а в исходном сообщении X не встречается.
Криптоаналитик может догадаться, что G обозначает пробел, и после этого найти длины слов. Как мы вскоре убедимся, с текстом большей длины
*) Для иллюстрации этой ситуации как нельзя лучше подходит известная фраза КАЗНИТЬНЕЛЬЗЯПОМИЛОВАТЬ,
где от постановки запятой смысл приговора меняется на противоположный (прим. перев.)