- •Предисловие
- •Глава 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
- •Литература
10
Глава 1. Введение
Некоторые аспекты безопасности связи
На протяжении последних двух тысяч лет (по крайней мере) всегда находились люди, желающие посылать сообщения, прочитать которые могут лишь те, кому эти сообщения адресованы. Если письмо доставляет получателю посыльный (раб, как это было в Древней Греции или Риме) или современная почтовая служба, всегда есть риск того, что письмо попадет в чужие руки. Раба могли схватить, а почтальон может доставить письмо не по адресу. И если письмо написано открытым текстом, то есть, выражаясь обычным языком, не сделано никаких попыток скрыть его содержание, то любой, к кому оно попадет, сможет прочесть его и понять, если он знает язык, на котором оно написано.
В наше время сообщения можно посылать по телеграфу, по радио, по телефону, по факсу, по электронной почте, однако возможности перехвата сообщений не только не исчезли, но значительно расширились. Например, радиопередачу может прослушивать любой человек, находящийся в зоне сигнала, если он настроился на нужную частоту; электронная почта, в свою очередь, вполне может попасть в руки огромному числу лиц, которым она не предназначается, если на клавиатуре компьютера нажата не та клавиша, или если в нем притаился компьютерный вирус.
Не исключено, что мое утверждение покажется очень пессимистичным, но тем не менее, следует всегда предполагать, что любое конфиденциальное сообщение обязательно попадет в руки того, кто не должен его видеть. И следовательно, благоразумно предпринять такие шаги, которые гарантируют, что прочтение этого сообщения окажется для него, по меньшей мере, очень трудным, а лучше всего, и вовсе невозможным делом. Степень ущерба от случайного прочтения послания посторонним человеком может существенно зависеть от времени, прошедшего с момента перехвата до момента прочтения сообщения. Бывают ситуации, когда задержка в прочтении сообщения на один день и даже на несколько часов сводит ущерб к нулю. Примерами таких ситуаций могут быть: решение акционера купить или продать одномоментно большое количество акций; или же, в военное время, приказ командующего армией атаковать противника в определенном направлении на рассвете следующего дня. В других случаях сообщаемая информация может иметь ценность в течение длительного периода и должна как можно дольше держаться в секрете, как например, сообщение, которое касается планирования крупномасштабной военной операции.
Поэтому большое значение приобретает объем работы, которую необходимо проделать конкуренту, противнику или врагу для прочтения сообщения. Если даже с применением наилучшей методики из всех
11
известных и самых быстродействующих компьютеров из всех существующих, нелегальный получатель не сможет прочесть сообщения, прежде чем его секретность или конфиденциальность перестанет быть актуальной, то отправитель может быть более-менее спокоен. Однако, абсолютно спокойным отправитель не может быть никогда, поскольку успешное прочтение противником предыдущих сообщений может способствовать ускорению дешифрования последующих. Возможна и такая ситуация, когда противником разработан метод вскрытия, о котором отправитель и не подозревает. В таком случае его сообщения будут прочитаны противником гораздо быстрее, чем он полагает. Именно это произошло с германской шифрмашиной "Энигма" во время войны 1939-45 гг., о чем рассказано в главе 9.
Шифр Юлия Цезаря
Проблему обеспечения тайны переписки осознавали еще древние греки, а также, в числе прочих, и Юлий Цезарь. Греки нашли необычное решение: они брили наголо голову раба и выцарапывали на ней свое послание. Когда волосы на голове раба отрастали вновь, его посылали доставить сообщение. Получатель брил голову раба и прочитывал текст. Ясно, что способ этот очень ненадежен, и вдобавок неэффективен. Всякий осведомленной о таком способе связи мог схватить раба, побрить ему голову и прочесть послание. Более того, на отправку сообщения и получение ответа таким способом уходило несколько недель.
Юлий Цезарь придумал способ получше. Каждую букву сообщения он заменял на другую, которая в латинском алфавите отстояла от исходной на три позиции дальше. Таким образом, буква A латинского алфавита заменялась на D, B на E, и так далее вплоть до буквы W, которая заменялась на Z, затем X на A, Y на B и, наконец, Z на C. Если бы он проделал это со своим знаменитым посланием
VENI.VIDI.VICI
(Пришел.Увидел.Победил.)
с помощью 26-буквенного алфавита, которым пользуются в англо-говорящих странах (чего он, разумеется, не делал), то отправленное сообщение выглядело бы так:
YHQL.YLGL.YLFL.
Это не очень сложный метод, тем более что сразу становится очевидным, что сообщение состоит из трех слов, и в каждом из них четыре
12
буквы, причем некоторые буквы повторяются. В такой немудреной системе сложно избавиться от этих слабостей. Тем не менее, расширение алфавита с 26 до 29 знаков и более за счет включения знаков препинания и пробелов слегка замаскировало бы длину каждого слова. Тем не менее, Цезарь вошел в историю криптографии, а "шифр Юлия Цезаря", как его до сих пор называют, служит примером одной из первых систем шифрования и является частным случаем шифра простой замены, как мы увидим в главе 2.
Несколько основных определений
Поскольку в дальнейшем мы неоднократно будем употреблять такие слова, как диграф, криптография и шифрование, следует дать им определения сейчас.
Монограф - это одиночная буква любого алфавита, который мы используем. Диграф - это любая пара рядом стоящих букв. Так, например, AT - это диграф. Триграф состоит из трех рядом стоящих букв; так, например, THE - это триграф; и так далее. Полиграф состоит из произвольного числа последовательно записанных букв. Под полиграфом совсем не обязательно надо понимать слово какого-либо языка. Однако, если при попытке дешифровать сообщение, написанное предположительно поанглийски, нам встречается гептаграф MEETING, то это выглядит гораздо более правдоподобно, нежели если мы получим гептаграф вроде DKRPIGX.
Символ - это любой знак, в том числе буква, цифра или знак препинания; строка - это любое множество слитно записанных символов. Длиной строки называется количество символов в ней. Например, A3?%$ представляет собой строку длины 5.
Система шифрования, или криптографическая система - это любая система, которую можно использовать для изменения текста сообщения с целью сделать его непонятным для всех, кроме тех, кому оно предназначено.
Процесс применения системы шифрования к исходному сообщению называется зашифрованием.
Исходный текст сообщения, до зашифрования, называется открытым текстом, а текст, полученный в результате зашифрования - шифрованным текстом.
Процесс, обратный зашифрованию, то есть восстановление исходного текста сообщения по шифрованному тексту называется расшифрованием или дешифрованием. Эти термины, пожалуй, не являются полными синонимами. Легальный получатель сообщения посчитает, что он занимается его расшифрованием, а тот, кому оно не предназначено, пытаясь понять смысл послания, наверняка считает, что занимается дешифрованием.
Криптография изучает построение и использование систем шифрования, в том числе их стойкость, слабости и степень уязвимости относительно различных методов вскрытия. Криптограф - это лицо,
13
занимающееся криптографией.
Криптоанализ изучает методы вскрытия систем шифрования.
Криптоаналитик (жаргонное "взломщик шифров") -это лицо, занимающееся
криптоанализом.
Криптографы и криптоаналитики - соперники; они стремятся перехитрить друг друга. Каждый ставит себя на место противника и задет себе вопрос: "Если бы я был на его месте, что бы я сделал, чтобы оказаться победителем?". Оба соперника, которые наверняка никогда не встретятся, вовлечены в захватывающий интеллектуальный поединок, в котором ставки могут быть чрезвычайно высоки.
Три этапа дешифрования:
идентификация, взлом системы и вскрытие ключей.
Когда шифрованное сообщение впервые попадает в руки криптоаналитика, то его первый шаг состоит в том, чтобы определить, какой тип системы шифрования был использован. Это может оказаться один из известных типов, или совершенно новый. В любом случае криптоаналитику приходится решать задачу идентификации. Для этого сначала нужно непременно собрать все дополнительные сведения, имеющие отношение к делу. Например, информацию о типе системы, которую отправитель использовал ранее (если это известно), или обо всех новых системах, появившихся где-либо за последнее время. Затем следует изучить преамбулу сообщения. В преамбуле могут содержаться сведения, предназначенные для получателя, но и криптоаналитику они тоже могут оказаться полезными. И наконец, криптоаналитик приступает к анализу самого сообщения. Если оно очень короткое, дальнейшее продвижение может оказаться невозможным, и придется дожидаться поступления новых сообщений. Если сообщение достаточно длинное, или же если уже набралось несколько довольно длинных сообщений, то, применив ряд математических тестов, криптоаналитик непременно определит, использована ли здесь кодовая книга, или довольно простая система шифрования, или какой-нибудь более сложный тип шифра.
Идентифицировав систему, криптоаналитик, вероятно, сможет оценить количество материала (например, число знаков в шифрованном тексте), которое ему нужно иметь, чтобы появился реальный шанс взломать систему, то есть точно установить, как именно шифруются сообщения в данной системе. Если система простая, и способ шифрования мало меняется от сообщения к сообщению, как, например, в кодовой книге, шифрах простой замены и перестановки (см. главы 2-6), то возможно, криптоаналитику удастся дешифровать сообщение (сообщения) без особого труда. Если же, что гораздо более вероятно, в системе присутствуют некоторые части, меняющиеся от сообщения к сообщению, то прежде всего необходимо