Предисловие
Фактически каждый, кто умеет читать, неизбежно сталкивается с кодами или шифрами того или иного вида. Например, решая кроссворды даже эпизодически, вы обязательно познакомитесь с анаграммами, которые являются разновидностью шифра перестановки. Шифрованные сообщения встречаются в детских комиксах, в газетных частных объявлениях и во многих художественных произведениях, начиная с рассказов Конан Дойля и Эдгара Аллана По.
В наши дни многие имеют персональные компьютеры и пользуются системой Интернет. Поэтому они знают, что для отправки и получения электронной почты необходимо всякий раз вводить пароль, который шифруется и проверяется системой. В сфере бизнеса и коммерции, особенно когда перевод денежных средств производится с использованием электронной документации, решающими факторами становятся засвидетельствование подлинности содержания сообщения и подтверждение полномочий участников сделки. И наилучшим способом защиты от мошенничества в такой ситуации является шифрование.
Поэтому неудивительно, что коды и шифры в гораздо большей мере, чем раньше, входят в нашу повседневную жизнь. К тому же рассекречивание некоторых сторон деятельности дешифровальщиков из Блетчли во время войны, особенно касающихся шифрмашины "Энигма", и появление вслед за этим публикаций и телевизионных программ на эту тему привело к росту интереса со стороны широкой публики к так называемому "взламыванию кодов".
По сложности системы шифрования варьируются от самых элементарных до наиболее передовых. И если первые не требуют никаких математических познаний, то в последних часто используются понятия и методы, известные, может быть, лишь специалистам с университетским дипломом по математике, информатике и некоторым другим смежным дисциплинам. Возможно, вследствие этого большинство книг по кодам и шифрам не касается математики совершенно, другие же требуют от читателя блестящего знания всего арсенала математических концепций, методов, обозначений и языка.
Исходя из личного опыта, автор полагает, что лучше придерживаться золотой середины: вполне возможно, не вдаваясь во все подробности, объяснить неспециалистам сущность некоторых математических концепций, лежащих в основе даже наиболее современных систем шифрования. Поэтому я вижу свою задачу в том, чтобы познакомить широкого читателя с целым рядом кодов и шифров. Начав с древнейших и простейших систем, мы перейдем к описанию некоторых шифровальных машин времен войны и закончим системами шифрования, которые используются в коммерческой сфере в настоящее время. В книге даны примеры использования и методы вскрытия различных систем шифрования. Однако в тех случаях, когда описание метода дешифрования сообщения реальной длины заняло бы много страниц, оно дается в сжатом виде (промежуточные этапы опускаются).
Основной текст книги содержит только необходимый минимум математических сведений, обозначений и терминов. Тех, кто хотел бы получить более глубокие познания, отсылаем к приложению, в котором содержится детальное описание и объяснение математических вопросов. В некоторых случаях в нем дан даже больший объем сведений, нежели необходимо по ходу изложения. Автор делает это намеренно в надежде поощрить читателя в стремлении продолжить изучение одной из самых увлекательных и полезных областей математики, которая находит применение как при "взламывании кодов", так и в других сферах.
Выражаю благодарность Университету Кардиффа за разрешение воспроизвести фотографии с 9.1 по 9.4 включительно, а также 10.1 и 10.2, а моему сыну Джону за разрешение воспроизвести фото 11.1. Я также признателен доктору Крису Хигли из Информационной Службы Университета Кардиффа за предоставленный мне материал, относящийся к главе 13, а также персоналу издательства Cambridge University Press, в особенности Роджеру Эстли и Питеру Джексону за безотказную помощь в течение всего периода подготовки этой книги.
- Глава 1. Введение 10
- Глава 9. Шифрмашина "Энигма" 130
- Глава 10. Шифрмашина "Хагелин" 152
- Глава 11. После "Энигмы" 172
- Глава 12. Криптография с открытым ключом 179
- Глава 13. Шифрование и Интернет 188
- Предисловие
- Глава 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
- Литература
- Глава 1
- Глава 2
- Глава 3
- Глава 4
- Глава 5
- Глава 6
- Глава 7
- Глава 8
- Глава 9
- Глава 10
- Глава 11
- Глава 12
- Глава 13