1

Коды и шифры

Построение систем кодирования и шифрования претерпело в нынешние времена значительные изменения. Появление мощных персональных компьютеров привело к бурному развитию электронной почты, электронной торговли и электронных банковских операций. Как следствие, шифрование средств связи ради обеспечения безопасности стало важным вопросом, являющимся предметом общественного интереса. Эта книга посвящена описанию и анализу многих систем шифрования, начиная с наиболее ранних и элементарных и заканчивая самыми современными и сложными, такими как RSA и DES, и, кроме того, шифрмашин времен войны (таких, как "Энигма" и "Хагелин"), а также шифров, применяемых шпионами. Обсуждаются вопросы стойкости систем шифрования и возможные методы их дешифрования,

которые иллюстрированы примерами. Построение многих систем основано на передовых математических теориях, детальное изложение которых содержится в основном приложении. Эта книга предназначена для всех, интересующихся использованием кодов и шифров частными лицами, шпионами, правительствами и в отраслях экономики в течение всей истории человечества вплоть до нашего времени.

Роберт Чёрчхаус является Заслуженным Профессором вычислительной математики Кардиффского Университета, в настоящее время находится в отставке. Читал лекции по математике и криптоанализу в более чем 50-ти университетах и институтах по всему миру. Является также соавтором книг по применению компьютеров в математике, литературных и лингвистических исследованиях, а также по численному анализу.

Роберт Чёрчхаус

Коды и шифры

(Юлий Цезарь, "Энигма" и Интернет)

Предисловие 8

Глава 1. Введение 10

Некоторые аспекты безопасности связи 10

Шифр Юлия Цезаря 11

Несколько основных определений 12

Три этапа дешифрования: идентификация, взлом системы и вскрытие ключей. 13

Коды и шифры 14

Оценка стойкости системы шифрования 16

Коды, обнаруживающие и исправляющие ошибки 17

Другие методы сокрытия содержания сообщений 18

Модульная арифметика 19

Модульное сложение и вычитание букв 20

Род 21

Заключение 21

Глава 2. От Юлия Цезаря до простой замены 23

Шифры Юлия Цезаря и их вскрытие 23

Шифры простой замены 24

Вскрытие шифра простой замены 27

Частоты встречаемости букв в других языках, кроме английского 34

Сколько знаков необходимо для дешифрования простой замены? 36

Глава 3. Многоалфавитные системы 39

Усиление системы Юлия Цезаря: шифры Вижанэра 39

Вскрытие шифра Вижанэра 41

Индикаторы 45

Одноключевые сообщения 45

Распознавание одноключевых сообщений 46

Какой объем текста необходим для дешифрования шифра Вижанэра? 49

Цилиндр Джефферсона 49

Глава 4. Шифры-головоломки 52

Перестановки 52

Простая перестановка 52

Двойная перестановка 56

Другие виды перестановок 60

Регулярные перестановочные таблицы 60

Нерегулярные перестановочные таблицы 63

Оценка стойкости шифров перестановки 64

Общая концепция двойного шифрования 64

Глава 5. Двухбуквенные шифры 67

Замена "монограф-диграф" 67

МДПМ-шифры 69

Система "диграф-диграф" 71

Шифр Плейфера) 72

Расшифрование в системе Плейфера 73

Криптоаналитические аспекты системы Плейфера 74

Двойной шифр Плейфера 75

Глава 6. Коды 78

Характеристики кодов 78

Одночастевые и двухчастевые коды 79

Код плюс аддитивное шифрование 81

Глава 7. Шифры для шпионов 87

Шифры-решетки 88

Книжные шифры 89

Использование книжного шифра 90

Частоты встречаемости букв в книжных шифрах 94

Вскрытие книжного шифра 95

Индикаторы 103

Катастрофические ошибки при использовании книжного шифра 104

Шифры "агента Гарбо" 106

Первый шифр "агента Гарбо" 106

Второй шифр "агента Гарбо" 106

Одноразовый блокнот 110

Глава 8. Получение случайных чисел и букв 112

Случайные последовательности 112

Получение случайных последовательностей 113

Бросание монеты 113

Бросание костей 114

Извлечение из урны (по типу лотереи) 115

Космические лучи 115

Шум от усилителей 116

Псевдослучайные последовательности 116

Линейные рекурренты 117

Использование последовательности двоичных знаков гаммы для шифрования 118

Двоичные линейные последовательности как генераторы гаммы 120

Криптоанализ линейной рекурренты 123

Повышение стойкости двоичной гаммы 123

Генераторы псевдослучайных чисел 125

Метод срединных квадратов 125

Линейные конгруэнтные генераторы 127

Глава 9. Шифрмашина "Энигма" 130

Историческая справка 130

Первая "Энигма" 132

Шифрование с использованием контактных колес 134

Шифрование в "Энигме" 136

Коммутатор "Энигмы" 139

Ахиллесова пята "Энигмы" 139

Цепочки индикаторов в "Энигме" 143

Выравнивание цепочек 146

Идентификация колеса R1 и его угловой установки 147

Двойное шифрование в "Энигме" 150

"Энигма" Абвера 151