- •Предисловие
- •Глава 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
- •Литература
217
A = -B = 15 .
Для больших значений n элемент последовательности Un равен целому числу, ближайшему к A n, так что каждый элемент приблизительно в 1.6180... раз больше предыдущего. Поэтому 8-й элемент равен целому числу, ближайшему к
1.6180 8 . 5
Это значение (с точностью до трех десятичных знаков) равно 21.006; ближайшее целое число поэтому равно 21. И действительно, 8-й элемент последовательности чисел Фибоначчи равен 21.
Описание свойств последовательности чисел Фибоначчи можно найти во многих книгах по элементарной теории чисел. Эта последовательность имеет давнюю историю. Фибоначчи, также известный под именем Леонардо из Пизы, привел ее в своей книге "Liber Abaci"*) в 1207 году. Эта последовательность обладает большим количеством различных свойств: например, каждый 5-й ее элемент делится на 5, каждый 8-й ее элемент делится на 7, а каждый 10-й элемент делится на 11. Подобные свойства, хоть и красивые с математической точки зрения, делают эту последовательность совершенно непригодной с криптографических позиций. Те, кто желает подробно изучить эту последовательность, могут обратиться к [6.5]. Также выпускается журнал, посвященный изучению последовательности Фибоначчи и других линейных последовательностей (см. [6.6]). Материалы по смежной тематике можно найти также в статьях, посвященных
непрерывным дробям (см. [6.7]).
Глава 7
М6. Частота встречаемости букв для книжного шифра
В книжном шифре, если пробел и знаки препинания рассматриваются в совокупности как 27-ю буква, одна и та же буква шифрованного текста может получиться в результате сложения знака гаммы с буквой сообщения в одной из 27 возможных комбинаций. Так, например, чтобы в шифрованном тексте появилась буква D, надо, чтобы возникла одна из следующих 27
*) "Liber Abaci" (лат.) - "Книга о счете" (прим. перев.)
218
комбинаций: |
буква A в гамме и буква D в сообщении, |
|
|
или |
буква B в гамме и буква C в сообщении, |
или |
буква C в гамме и буква B в сообщении, |
или |
буква D в гамме и буква A в сообщении, |
или |
буква E в гамме и "пробел" в сообщении, |
|
и т.д. |
или |
буква Z в гамме и буква F в сообщении, |
или |
"пробел" в гамме и буква E в сообщении. |
Если для некоторой буквы # обозначить через p(#) вероятность ее появления в английском тексте, то для книжного шифра вероятность появления в шифрованном тексте буквы D будет равна
p(A)p(D) + p(B)p(C) + p(C)p(B) + p(D)p(A) + ... + p("пробела")p(E).
Используя таблицу встречаемости знаков в обычном английском тексте и считая все знаки препинания и "пробел" одной и той же 27-й буквой, можно по этой формуле подсчитать для книжного шифра предполагаемую вероятность появления в шифрованном тексте буквы D, а также, аналогичным образом, любой другой буквы.
Один частный случай относится к вычислению этих вероятностей для двух одноключевых сообщений (см. главу 3). Если случайным образом выбрать по одной букве из двух открытых сообщений, состоящих только из букв от A до Z (без знаков препинания), то вероятность совпадения этих букв равна
p(A)2 + p(B)2 + p(C)2 + p(D)2 + ... + p(Z)2,
что для английского текста составляет около 1/13. В более общем случае, для большинства обычных языков эта вероятность равна примерно
2 .
(размер алфавита)
Так, например, если взять в качестве исходных данных частоты встречаемости 27 знаков (26 букв алфавита и пунктуационный символ) из таблицы 7.4., то в данном случае вероятность совпадения двух знаков равна
. |
642 142 ... 1662 |
|
|
70678 |
|
|
1 |
. |
|
1000000 |
1000000 |
14 |
|||||||
|
|
|
|