- •Предисловие
- •Глава 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
- •Литература
56
становится строкой открытого текста
M E E T I.
Аналогично, вторая строка шифрованного текста
G I N L W
превращается в
NG W I L,
иполучение оставшейся части сообщения подтверждает правильность дешифрования.
Мы привели очень простой пример: ключ был короткий, его длина была очевидна и найдена с первой попытки. Однако это хорошая иллюстрация метода вскрытия. Этим примером мы также показали, что наличие таблицы частот диграфов, хотя и не является непременным условием, но способно значительно облегчить решение задачи. Если бы длина шифрованного текста не была кратна 5, то для длины ключа возможное равенство 5 (или 7, как в данном случае) не так бросалось бы в глаза, и пришлось бы перебирать и другие значения длины ключа. Для ключей, имеющих длину не больше 5, возможно даже применение метода "грубой силы", так как число возможных перестановок столбцов весьма невелико (всего 120 для длины ключа 5). Если длина ключа превышает число 5, то использование метода полного перебора становится весьма трудоемким, и вручную практически невыполнимо, тогда как описанный выше "метод диграфов" можно реализовать для любой длины ключа, которая может встретиться на практике. Зная все это, криптограф попытается как можно тщательнее замаскировать длину ключа. Он может также прибегнуть и к другим мерам, таким как
Двойная перестановка
Слабость метода простой перестановки заключается в следующем. Когда шифрованное сообщение выписано в столбцы "по ширине ключа", то есть когда число букв в строке задается длиной ключа, то буквы, стоящие рядом в открытом тексте, обычно попадают в одну и ту же строку; поиск "хороших" диграфов может выявить порядок перестановки столбцов.
Последнее становится весьма очевидным, если в приведенном выше примере заменить открытый текст на числа 1,2,3,...,35, подчеркнуть первые пять чисел (чтобы было легче их идентифицировать) и применить ключ
57
перестановки, которым мы до этого пользовались. Тогда (см. таблицу 4.4) мы получаем "шифрованный" текст:
á2á7á12á17á22áá27á32áá4á9á14áá19á24á29á34á1áá6á11á16á21á26 31á5á10á15á20áá25á30á35á3áá8áá13á18á23á28á33
Таблица 4.4
|
Ключ |
3 |
1 |
5 |
2 |
4 |
|
|
1 |
2 |
3 |
4 |
5 |
|
|
6 |
7 |
8 |
9 |
10 |
|
|
11 |
12 |
13 |
14 |
15 |
|
|
16 |
17 |
18 |
19 |
20 |
|
|
21 |
22 |
23 |
24 |
25 |
|
|
26 |
27 |
28 |
29 |
30 |
|
|
31 |
32 |
33 |
34 |
35 |
|
|
|
|
|
|
|
Если рассмотреть интервалы между подчеркнутыми числами, мы обнаружим, что
1 и 2 отстоят на 14 позиций,
2 и 3 отстоят на 28 позиций,
3 и 4 отстоят на 21 позицию,
и наконец,
4 и 5 отстоят на 14 позиций,
то есть, интервалы между подчеркнутыми числами кратны 7. Таким образом, если мы выпишем "текст" в 7 строк по 5 знаков, то эти числа все попадают в одну строку.
Однако, если мы к этому "шифрованному" тексту снова применим эту же перестановку (см. таблицу 4.5),
Таблица 4.5
Ключ |
3 |
1 |
5 |
2 |
4 |
|
2 |
7 |
12 |
17 |
22 |
|
27 |
32 |
4 |
9 |
14 |
|
19 |
24 |
29 |
34 |
1 |
|
6 |
11 |
16 |
21 |
26 |
|
31 |
5 |
10 |
15 |
20 |
|
25 |
30 |
35 |
3 |
8 |
|
13 |
18 |
23 |
28 |
33 |
|
|
|
|
|
|
58
то получится следующий "шифрованный" текст
á7á32á24á11áá5áá30á18á17á9á34áá21á15á3á28á2áá27á19á6á31á25 13á22á14áá1á26áá20áá8á33á12á4áá29á16á10á35á23.
Видно, что пары, первоначально стоявшие рядом в "открытом" тексте, теперь неравномерно разбросаны по "шифрованному" тексту:
1 и 2 отстоят на 9 позиций,
2 и 3 отстоят на 2 позиции,
3 и 4 отстоят на 17 позиций,
и наконец,
4 и 5 отстоят на 25 позиций,
поэтому использованный ранее метод диграфов здесь больше не работает. Стойкость шифра двойной перестановки можно еще усилить, если
использовать два различных ключевых слова (а не дважды одно и то же), особенно если эти ключевые слова имеют разную длину. Однако в такой системе значительно возрастает риск того, что отправитель ошибочно применит эти два ключевых слова в обратной последовательности. Вообще говоря, в этом случае получится другой шифрованный текст, который получатель не сможет расшифровать, и сообщение придется зашифровать правильно и послать снова. Тогда криптоаналитик будет иметь в своем распоряжении два варианта одного и того же текста, зашифрованного на тех же ключах, но в обратном порядке. Этой ситуацией он, вероятно, сможет воспользоваться. Ошибками такого типа чревата любая система двойного шифрования. Так, на шифр-машине "Энигма" для повышения стойкости некоторые сообщения зашифровывались дважды на различных ключевых установках, и произошел по крайней мере один случай, когда шифрование было выполнено не в том порядке (см. [4.1]).
Пример 4.2 Зашифруйте методом двойной перестановки следующий текст
A B C D E F G H I J K L M N O,
используя пару ключей
3-1-5-2-4 и 3-1-2 a) в заданном порядке;
59
b) в обратном порядке.
Удостоверьтесь, что получаются разные шифрованные тексты.
Проверка
a) Применим ключ 3-1-5-2-4 (см. таблицу 4.6),
Таблица 4.6
|
3 |
1 |
5 |
2 |
4 |
|
A |
B |
C |
D |
E |
|
F |
G |
H |
I |
J |
|
K |
L |
M |
N |
O |
|
|
|
|
|
|
и получаем
B G L D I N A F K E J O C H M.
Теперь применим ключ 3-1-2 (см. таблицу 4.7),
Таблица 4.7
|
3 |
1 |
2 |
|
B |
G |
L |
|
D |
I |
N |
|
A |
F |
K |
|
E |
J |
O |
|
C |
H |
M |
|
|
|
|
и получаем шифрованный текст
G I F J H L N K O M B D A E C.
b) Применим ключ 3-1-2 (см. таблицу 4.8),
Таблица 4.8
|
3 |
1 |
2 |
|
A |
B |
C |
|
D |
E |
F |
|
G |
H |
I |
|
J |
K |
L |
|
M |
N |
O |
|
|
|
|
и получаем