- •Предисловие
- •Глава 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
- •Литература
239
существует никакого достаточно быстрого метода проверки простоты заданного большого числа N. Если N достаточно велико, чтобы рассматривать его в качестве кандидата для использования в методе RSA (например, порядка 1050), то для точного доказательства его простоты потребуется непомерно большое время. В свете этого факта в 1976 г. Рабин (см. [12.8]), а в 1977 г. - в несколько другой форме - Соловей и Штрассен (см. [12.9]) предложили иной подход. В его основе заложена идея проверки некоторого условия относительно какого-либо числа, меньшего N. Это условие должно
(1)никогда не выполняться, если N является простым;
(2)выполняться чаще, чем не выполняться, если N не является простым. Условие, предложенное Рабином, для составных N выполняется более чем в 75% случаев. Возьмем много чисел, меньших N (к примеру, m штук), и для каждого из этих m чисел проверим это условие. Если оно ни разу не
выполнилось, то вероятность простоты числа N оценивается величиной (0.25)m. Взяв m достаточно большим, эту вероятность можно сделать сколь угодно близкой к единице.
Описание условия Рабина можно найти в работе [1.2], в главе 9. Список научных работ по смежной тематике см. в [13.12].
M25. Алгоритм Евклида
Этот алгоритм используется для отыскания наибольшего общего делителя (н.о.д.) двух целых чисел, x1 и x2. Если обозначить н.о.д. через h, то этот алгоритм можно также использовать для нахождения таких целых чисел m и n, что
m x1 - n x2=h,
которые используются в системе зашифрования/расшифрования RSA. Алгоритм Евклида формулируется следующим образом.
Можем предположить, что оба числа x1 и x2 положительны, и что x1 больше x2 (если это не так, поменяем их местами).
Разделим x1 на x2; пусть в остатке получается число x3:
x1 = a1x2+x3, где a1 - целое число, а 0 x3< x2.
Если x3 0, то разделим x2 на x3; пусть в остатке получается x4:
x2 = a2x3+x4, где a2 - целое число, а 0 x4< x3.
240
Продолжаем таким образом до тех пор, пока в остатке не получится ноль, то есть, пока мы не получим
x(n-1) = a(n-1)xn.
Тогда наибольший общий делитель чисел x1 и x2 (h) будет равен xn. Если h=1, то целые числа x1 и x2 называются взаимно-простыми.
Пример Найти н.о.д. чисел 1001 и 221.
Решение
1001=4 221+117, 221=1 117+104, 117=1 104+13, 104=8 13+0.
Таким образом, н.о.д. чисел 1001 и 221 равен 13. (Проверка: 1001=13 91, 221=13 17; числа 91 и 17 взаимно-простые.)
В математической литературе принято обозначать н.о.д. пары целых чисел m и n через (m,n). Так, (1001,221)=13, а (91,17)=1.
Следующий пример иллюстрирует использование алгоритма Евклида в рамках метода RSA, как описано в главе 13.
Пример
Найти целые числа m и n, такие что 91m-17n=1.
Решение Имеем:
91=5 17+6, 17=2 6+5, 6=1 5+1, 5=5 1,
что подтверждает взаимную простоту чисел 91 и 17 (если это было бы не так, то у нашего уравнения не существовало бы решения). Возвращаемся по шагам алгоритма в обратном порядке, начиная с предпоследней строки:
1=6-1 5 и 5=17-2 6,
поэтому
1=6-1 (17-2 6)=3 6-17,
но
6=91-5 17,
241
следовательно, 1=3 (91-5 17)-17=3 91-16 17.
Итак,
m=3 и n=16.
(Проверка: 3 91=273 и 16 17=272.)
Альтернативный метод
Значения m и n можно также найти с помощью непрерывных дробей (см. [6.7]). При этом метод отыскания остается тем же самым, что и в алгоритме Евклида, хотя все это и выглядит по-другому.
В качестве иллюстрации метода снова вычислим значения m и n, такие
что
91m-17n=1.
91 |
5 |
|
6 |
, |
|
17 |
17 |
||||
|
|
||||
17 |
2 |
5 , |
|
||
6 |
|
6 |
|
65 1 15 .
Таким образом, для данной непрерывной дроби частичные отношения будут равны (5, 2, 1, 5), а последовательные приближения, соответственно
15 , 112 , 163 и 1791 .
Числа m и n совпадают с числителем и знаменателем предпоследнего приближения: они, как и ранее, оказываются равны 16 и 3.
М26. Эффективность возведения в степень методом последовательного возведения в квадрат
Если задано число X, которое мы хотим возвести в n-ю степень, то мы могли бы вычислить Xn, просто умножив X на себя n-1 раз. Если n невелико, то так и следует поступить, но в случае большого n этот способ неэффективен. Пусть число k таково, что
2k<n<2k+1;
тогда k=[log2n], где [z] обозначает, как принято в математике, целую часть числа z.
242
При вычислении значений X2, X4, X8,... методом последовательного возведения в квадрат для возведения числа в степень 2k необходимо выполнить k операций возведения в квадрат, то есть k умножений. Двоичное представление числа n содержит не более (k+1) единицы, поэтому для вычисления величины Xn надо перемножить между собой не более k+1 чисел из множества X, X2, X4,... . Это означает, что понадобится выполнить не более k дополнительных операций. В итоге получаем, что общее число умножений не превосходит 2k.
Поскольку k<(log2n+1), то отсюда следует, что для вычисления Xn методом последовательного возведения в квадрат требуется не более 2(log2n+1) умножений, в то время как при вычислении "в лоб" их потребуется n-1. Для малых значений n разница не так уж велика. Например, для n=7 при вычислении "в лоб" нужно 6 умножений, а для метода последовательного возведения в квадрат их потребуется 4. Однако с ростом n разница очень быстро становится существенной. Например, для n=127 для вычислений "в лоб" нужно выполнить 126 умножений, а при последовательном возведении в квадрат - только 12. Для действительно больших значений порядков, которые чаще всего и применяются в методе зашифрования-расшифрования RSA, вместо астрономического числа умножений нужно выполнить всего несколько сотен.
М27. Число ложных ответов при дешифровании DES-алгоритма методом "встречного поиска "
При зашифровании текста на 256 различных ключах мы получим 256 различных шифрованных текстов. Поскольку общее количество различных 64-разрядных двоичных векторов равно 264, то в списке шифрованных текстов окажется примерно лишь каждый 256-й вектор (256=28). То же самое будет справедливо при расшифровании текста на 256 различных ключах. Если теперь сравнить оба списка, то вероятность того, что какой-либо вектор из списка зашифрования будет содержаться также и в списке расшифрования, составляет 1 шанс из 256.
Всего в списке зашифрования 256 векторов, и из них примерно каждый 256-й должен встретиться в списке расшифрования. Таким образом, всего таких совпадений должно быть 248. Все эти ответы, кроме одного, будут ложными, и для нахождения истинного решения понадобится проводить еще одну или несколько проверок.
М28. Криптография эллиптической кривой
Несмотря на свое название, рассматриваемые кривые не являются эллипсами, а относятся к типу
243
Y2 = X3 + aX + b,
где a и b - целые числа. Нас интересуют пары (X,Y), также являющиеся целыми числами. Все вычисления модульные, и выполняются относительно некоторого (очень большого) модуля p. Кривые этого типа могут быть параметризованы с помощью эллиптических функций Вейерштрасса, откуда и происходит данное название.
Так, например, точки (1, 5) являются целочисленными точками, лежащими на кривой
Y2 = X3 + 2X + 3 (mod 19).
По любой точке (или паре точек) на кривой можно построить новую точку на кривой с использованием касательной (для случая одной точки) или хорды (соединяющей пару точек). Касательная или хорда пересекает кривую в третьей точке, которая должна иметь рациональные координаты. Эти координаты преобразуются в целые числа над GF(p), полем Галуа по модулю p. Так, например, для приведенной выше кривой и p=19 уравнение касательной в точке (1,5) составляет
2Y = X + 9.
Мы находим, что эта касательная снова пересекается с кривой в точке X=-7/4. Это число можно преобразовать в целое число над полем GF(19): поскольку знаменатель этой дроби равен 4, то нам нужно найти такое целое число n, что
4n 1(mod 19).
Отсюда мы получаем, что n=5, поскольку 20=1 19+1; поэтому -7/4 (-7) 5=-35 3(mod 19), и поэтому дробь -7/4 эквивалентна целому значению 3 над полем GF(19). В качестве целого значения X получаем 3, а соответствующее значение Y, получаемое из приведенного выше уравнения касательной, равно 6. Так как
Y2=36, а X3+2X+3=27+6+3=36,
то мы убедились в том, что точки (3, 6) действительно лежат на вышеупомянутой кривой. (Нам необходимо только показать, что они лежат на этой кривой над GF(19); на самом деле они лежат на этой кривой (mod p) для всех значений p, но это чистая случайность; обычно это вовсе не так).
Итак, мы нашли на кривой еще одну целочисленную точку. Поскольку
244
все вычисления выполняются по модулю p, то существует лишь конечное число возможных точек (X,Y) с целочисленными координатами. Отсюда вытекает, что данный метод построения новых точек должен в конце концов исчерпать себя. Если начать с некоторой (целочисленной) точки Q(X,Y) на кривой, то можно построить конечное множество точек <Q>, элементы которого мы обозначим через 2Q, 3Q, 4Q,... и т.д. (не следует смешивать их с точками типа (2X,2Y) и т.д.). Например, начиная с точки Q(1,5) на вышеупомянутой кривой, мы с помощью касательной в точке Q только что вычислили следующую точку, 2Q. Продолжая вычисления таким же образом, получим следующие точки:
2Q=(3, 6), 4Q=(10, 4), 8Q=(12, 8), и так далее
(другой пример можно найти в [13.9]).
Допустим, задана точка R(X',Y'), и от нас требуется выяснить, существует ли целое n, такое что R=nQ для некоторой точки из множества <Q>. В этом случае (если только значение простого модуля p не является маленьким) перед нами стоит очень трудная задача. Если R не принадлежит множеству <Q>, то такого значения n не существует. Применяемые значения p обычно превосходят 1050, а число опробований, которые необходимо выполнить (за исключением нескольких редких случаев), имеет порядок квадратного корня из p. Благодаря этому данная вычислительная задача становится не по силам даже самому мощному компьютеру.
Метод использования Q, R и n для выработки подписи к сообщению довольно сложный, и поэтому здесь не описан. Сжатое и понятное описание можно найти в [13.9].
Любой, кто желает подробнее изучить эти аспекты теории Галуа, может обратиться к книгам по теории конечных полей. Сам Галуа был в 1832 году убит на дуэли в возрасте 20 лет. Будучи уверенным в том, что его почти наверняка убьют, он в ночь перед дуэлью не спал и написал работу, в которой изложил свои идеи, в надежде, что ее опубликуют. В конце концов эта работа действительно была опубликована в 1848 году. Подробности его жизни и научной работы можно найти в книгах по истории математики, например [13.13].