|
|
Статьи Соросовского Образовательного журнала в текстовом формате
Изложены основные алгебраические аспекты криптологии.
ЭЛЕМЕНТЫ КРИПТОЛОГИИВ. А. АРТАМОНОВ
Московский государственный университет им. М.В. Ломоносова
ВВЕДЕНИЕ
Криптологией называется раздел математики, занимающийся изучением возможных способов шифрования информации (сокрытия от незаконного пользователя) и способов вскрытия шифров. В статье излагаются некоторые известные способы шифрования и дается их математическое объяснение. Подробнее с затрагиваемыми вопросами можно познакомиться в приведенной в конце статьи библиографии.
ШИФРЫ ПОДСТАНОВКИ
Потребность в сокрытии информации возникла в глубокой древности и связана с развитием государственности. Один из наиболее старых способов скрытия и передачи информации известен из истории Древнего Востока. На бритой голове раба писали сообщение. Выждав время, когда волосы на голове вырастут и сделают сообщение невидимым, раба посылали гонцом для передачи информации адресату. Ясно, что этот способ передачи информации крайне ненадежен и требует много времени для его реализации. Более прогрессивный способ сокрытия и передачи информации применялся в Спарте в IV веке до н.э. (Ксенофонт. Греческая история. СПб.: Алетейя, 1996. С. 97). Вот как объясняет это изобретение Плутарх (Сравнительные жизнеописания. М.: Наука, 1994. Т. 1: Лисандр, 19. С. 496): "Отправляя к месту службы начальника флота или сухопутного войска, эфоры берут две круглые палки совершенно одинаковой длины и толщины. Одну оставляют себе, другую передают отъезжающему. Эти палки и называют скиталами. Когда эфорам нужно сообщить какую-нибудь важную тайну, они вырезают длинную и узкую вроде ремня полосу папируса, наматывают ее на свою скиталу, не оставляя на ней ни одного промежутка, так чтобы вся поверхность палки была охвачена этой полосой. Затем, оставляя папирус на скитале в том виде, как он есть, пишут на нем то, что нужно, а написав, снимают полосу и без палки отправляют ее военачальнику. Так как буквы на ней стоят без всякой связи, но разбросаны в беспорядке, прочитать написанное он может только взяв свою скиталу и намотав на нее вырезанную полосу, располагая ее извивы в прежнем порядке, чтобы, водя глазами вокруг палки и переходя от предыдущего к последующему, иметь перед собой связное сообщение. Полоса папируса называется, как и деревянная палка, скиталой, подобно тому как измеряемый предмет называется по мере".
С математической точки зрения шифр скитал (или сцитал) представляет собой следующий способ шифрования. Предположим для простоты, что полоса является объединением трех непересекающихся частей, каждая из которых содержит по восемь букв и обвивает скиталу по диаметру. Тогда выражение бМАТЕМАТИКА И КРИПТОЛОГИЯс записывается вдоль скиталы последовательно в восемь столбцов высоты 3. При разматывании полосы на ней возникает надпись: бМЕТА ИОГАМИ КПЛИТАКИРТОЯс.
Следующий интересный шифр принадлежит Г.Ю. Цезарю. Он предложил записывать сообщение, написанное на латинском языке, в котором 26 букв, используя сдвиг букв в латинском алфавите на 3 (по модулю 26). В этом случае слово бMATHEMATICSс преобразуется в слово бPDWKHPDWLFVс.
Оба способа шифрования укладываются в следующую математическую конструкцию. Пусть X - алфавит открытого и шифрованного текстов. Предположим, что задано биективное отображение F множества X в себя. При этом сообщение xy _ z переходит в F (x)F (y)_F (z). Далее можно считать, что текст разбивается на k блоков одинаковой длины m. Поэтому для большей скрытности полученные блоки переставляются в соответствии с заданной перестановкой степени k. Разумеется, можно и далее усложнять приведенные способы шифрования. Отметим, что при всех этих способах используется один алфавит, причем в процессе шифрования разные буквы переходят в разные.
Для описания этого способа шифрования нам необходимо привлечь соответствующий математический аппарат. Пусть m - фиксированное натуральное число. Для любого целого числа d через [d ] обозначим остаток от деления числа d на m. Обозначим через Zm множество [0], [1], _, [m - 1] всех остатков от деления целых чисел на m. Тогда на Zm можно ввести операцию сложения и умножения. Положив [a][b] = [ab], [a] + [b] = [a + b], где ab и a + b - произведение и сумма a, b как целых чисел. Несложная проверка показывает, что эти операции определены корректно, причем они обладают следующими свойствами:
([a][b])[c] = [a]([b][c]),
[a][b] = [b][a], [a][1] = [a],
([a] + [b]) + [c] = [a] + ([b] + [c]),
[a] + [b] = [b] + [a], [a] + [0] = [a],
([a] + [b])[c] = [a][c] + [b][c].
Таким образом, можно производить с элементами Zm обычные алгебраические вычисления, учитывая лишь, что [ml ] = [0] для всех целых чисел l. Множество Zm с введенными операциями сложения и умножения называется кольцом вычетов по модулю m.
Теорема 1. Пусть a, n - целые числа, причем n > 0. Следующие условия эквивалентны:
1) числа a, n взаимно просты;
2) существует такое целое число d, что ad - 1 делится на n;
3) отображение, переводящее каждый элемент [x] из Zn в [a][x], является взаимно однозначным.
Вернемся теперь к шифру Цезаря. Пусть, например, мы работаем в латинском алфавите, состоящем из 26 букв. Записав этот алфавит и отождествив букву алфавита с номером i с элементом [i], можно отождествить буквы алфавита с элементами кольца вычетов Z26 . Тогда процесс шифрования можно понимать как отображение, переводящее произвольный элемент [x] в [a][x] + [b], где [a], [b] - элементы Z26 , причем число a взаимно просто с 26 в силу теоремы 1. Так при a = 1, b = 3 получается шифр Цезаря.
Нетрудно указать способ взламывания этих шифров. Предположим, что вы зафиксировали достаточно большое количество шифрованных сообщений. Кроме того, предположим, что вы знаете, что в сообщениях используется русский алфавит. В этом случае необходимо воспользоваться таблицами частот букв (в процентах) в русском алфавите (табл. 1).
Таким образом, мы видим, что практически все буквы имеют разные частоты. Следовательно, анализируя текст, вы можете по частоте использования каждого символа в зашифрованном сообщении определить, какая буква зашифрована этим символом. Аналогичная таблица частот букв в английском алфавите приведена в [2, c. 263]. Отметим, что работа по анализу и прочтению текстов, зашифрованных с помощью перестановок букв (и с использованием другого алфавита), широко отражена в художественной литературе (см., например, Э. По "Золотой жук", А. Конан Дойль "Пляшущие человечки").
ИСПОЛЬЗОВАНИЕ КЛЮЧЕВОГО СЛОВА
Следующий важный этап развития теории шифрования связан с именами Блеза де Виженера (Франция, XVI век) и Джероламо Кардано (Италия, XVI век). Виженер предложил использовать для шифрования ключевое слово. Поясним его идею на примере. Пусть слово КНИГУ является ключевым, и нам предстоит зашифровать слово МАТЕМАТИКА. Ключевое слово состоит из пяти букв. Поэтому шесть раз запишем русский алфавит. Первый раз в естественном порядке, затем циклически его переставляя и начиная последовательно с каждой из букв ключевого слова. Получаем табл. 2.
Начинаем процесс шифрования. Берем i-ю букву слова МАТЕМАТИКА и находим ее в строке *. Вычисляем остаток [ j] = [i] при делении числа i на пять, j = 0, 1, 2, 3, 4. Находим в столбце под i-й буквой строки * букву, стоящую в j-й строке. Именно на эту букву заменяем шифруемую i-ю букву. Таким образом, получаем слово бХНЪИЯКЯСНУс.
Из приведенного примера видно, что разным буквам исходного слова могут соответствовать одинаковые буквы (это зависит от положения буквы в слове) в зашифрованном слове и, наоборот, одной букве могут соответствовать в зависимости от положения буквы разные буквы в зашифрованном слове. Таким образом, приведенный шифр можно понимать как обобщенный шифр Цезаря с переменным сдвигом. Отметим, что, зная ключевое слово, нетрудно расшифровать ваше сообщение.
Изложенный процесс шифрования можно перевести на алгебраический язык. Ключевое слово состоит из пяти букв. Поэтому шифруемое сообщение записываем в одно слово без пробелов и затем разбиваем его на слова, состоящие из пяти букв. Заменим каждую букву на число i = 0, 1, _, 32, обозначающее номер его места в русском алфавите. Тем самым возникает набор векторов (x1 , x2 , _, x5) длины 5 с координатами x1 , x2 , _, x5 из кольца вычетов Z33 . Таким образом, шифруемое сообщение представляет собой некоторое множество векторов X = {(x1 , x2 , _, x5)}. Процесс шифрования состоит в применении ко всем элементам заданного множества векторов преобразования, переводящего каждую строку (x1 , x2 , _, x5) в строку
(x1 , x2 , _, x5)A + (b1 , b2 , _, b5),
где A = (ai j) - фиксированная квадратная матрица размера 5 с элементами ai j из Z33 , а (b1 , b2 , _, b5) - фиксированный вектор с коэффициентами из Z33 . Напомним, что (x1 , x2 , _, x5)A является вектором длины 5, i-я координата которого равна x1a1i + x2a2i + x3a3i + x4a4i + x5a5i . Ключом в этом случае являются матрица A и вектор b = = (b1 , b2 , _, b5). Для того чтобы каждое сообщение однозначно расшифровалось, необходимо и достаточно, чтобы матрица A была обратима над кольцом Z33 . Это означает, что ее определитель detA должен быть обратимым в кольце Z33 . Мы всегда можем понимать A как квадратную матрицу с целыми коэффициентами. Поэтому условие обратимости A в силу теоремы 1 означает, что detA как целое число должно быть взаимно просто с числом 33, то есть не делиться на 3 и 11. Для расшифровки сообщения необходимо совершить обратное преобразование, которое переводит строку Y в строку
YA -1 - bA -1.
В известной мере сложность расшифровки диктуется сложностью вычисления обратной матрицы и решения квадратных систем линейных уравнений.
Долгое время шифры Виженера и их модификации считались невзламываемыми. Политические деятели Франции XVI - XVII веков постоянно применяли эти шифры в своей переписке. Примечателен в этом отношении следующий абзац из мемуаров активного политического деятеля Фронды, парижского архиепископа кардинала де Реца, середина XVII века (Кардинал де Рец. Мемуары. М.: Наука, 1997. С. 581-582. (Литературные памятники)): "Мы с принцессой Пфальцской пользовались шифром, который прозвали непроницаемым, уверенные, что его нельзя прочесть, не зная слова, служащего к нему ключом. Мы полагались на него настолько безоглядно, что с его помощью не обинуясь сообщали друг другу самые важные и сокровенные тайны, доверяя их простым гонцам. _Принц де Конде, у которого на службе состоял один из самых искусных в мире отгадчиков тайнописи - его, помнится, звали Мартен, - шесть недель продержал у себя в Брюсселе этот шифр и вернул мне его, признав, что Мартен подтвердил: прочитать его нельзя. Вот, казалось бы, неоспоримое доказательство достоинств шифра, но недолго спустя он был разгадан. Жоли, который, хотя и не знал шифровального ремесла, поразмыслил, нашел в нему ключ и представил его мне в Утрехте, где я находился. Простите мне это маленькое отступление, быть может небесполезное".
Лишь в 1863 году прусским офицером Ф.В. Касисским был найден простой способ поиска ключа для шифра Виженера. Более подробно об этом см. [2, параграф 4.2.1].
Для повышения стойкости шифров можно периодически менять ключевое слово. Опишем современный способ открытого распределения ключей. Он основан на следующем принципе. Пусть n - произвольное натуральное число и
- его разложение в произведение степеней различных простых чисел p1 , p2 , _, pk с показателями m(1), m(2), _ _, m(k). Функцией Эйлера называется число j(n) всех натуральных чисел, меньших n и взаимно простых с n. Другими словами, j(n) - это число элементов a из кольца вычетов Zn , удовлетворяющих всем условиям теоремы 1.
Теорема 2. Пусть n - натуральное число из (3). Тогда
Теорема 3. Пусть n - натуральное число из (3). Тогда для любого целого числа d разность d j(n) - 1 делится на n.
Теорема 4. Пусть p - простое число. Тогда существует такое число a = 1, 2, _, p - 1, что для любого целого числа b, не делящегося на p, найдется такое натуральное число m, что am - b делится на p.
Другими словами, учитывая теорему 3, получаем, что Zp состоит из элементов {[0], [1], [a], [a2], _, [a p - 1]}. Элемент а из теоремы 4 называется примитивным (порождающим). Отметим, что примитивный элемент a по p определен неоднозначно. Можно показать, что если элемент a является примитивным в Zp , то этим же свойством обладает и элемент a p - 2. Укажем примеры примитивных элементов для малых простых чисел p. Например, если p = 2, то a = 1. Если p = 3, то a = 2. Если p = 5, то в качестве a можно брать либо 2, либо 3. Действительно, 21 = 2, 22 = 4, 23 = 8, и 8 сравнимо с 3 по модулю 5. Наконец, 24 = 1 (mod 5). В случае p = 7 в качестве a можно брать либо 3, либо 5. В общем случае задача о нахождении элемента a является одной из трудных в теории чисел.
В связи с теоремой 4 возникает следующая интересная задача дискретного логарифмирования, то есть по заданным a, b из теоремы 4 найти такое целое неотрицательное число n < q, что an - b делится на p, то есть [a]n = b в Zp . Для этой задачи, разумеется, можно осуществить полный перебор всех элементов из Zp и проверки этого условия. Но это требует больших вычислительных ресурсов и неприемлемо с практической точки зрения при больших p. Поэтому возникла идея использовать данный факт в криптографии для открытого распределения ключей. Пусть p - достаточно большое простое число и Zp - вычеты по модулю p. Выберем некоторым образом порождающий элемент a в Zp . Пусть два абонента A, B обмениваются по открытому каналу связи числами a, p. Далее абоненты A, B выбирают числа x, y = 1, 2, _, p - 1 соответственно, которые они держат в секрете. Затем по открытому каналу связи они обмениваются числами ax, ay. Абонент A, получив число ay, возводит его в степень x и получает число ayx. Ту же операцию проводит B и получает число axy, которое и берется в качестве ключа. Посторонний наблюдатель знает числа a, p, ax, ay, но не знает чисел x, y. Для нахождения этих чисел и вычисления ключа axy необходимо решить задачу дискретного логарифмирования.
СИСТЕМА RSA
Все рассмотренные выше криптосистемы носили линейный характер, поскольку системы шифрования (1) и дешифрования (2) сводятся к линейному преобразованию и решению систем линейных уравнений над кольцом вычетов. Принципиально новая система была предложена в конце 70-х годов XX века У. Диффи, М.Э. Хеллмэном, а также Р. Ривестом, А. Шамиром, Л. Адлеманом. По имени последних трех авторов эта система названа RSA-системой. Предположим, что достаточно большое натуральное число n разлагается в произведение двух простых чисел: n = pq. Предположим, что e, d - два натуральных числа, причем de - 1 делится на j(n), где j(n) = (p - 1)(q - 1) - значение функции Эйлера. Будем рассматривать шифруемое сообщение x как элемент кольца вычетов Zn , то есть x = = [1], [2], _, [n - 1], причем x не делится ни на p, ни на q. Это означает в силу теоремы 3, что x j(n) = [1] в Zn . Процесс шифрования состоит в применении отображения возведения в степень, то есть x заменяется на x e в кольце вычетов Zn . В этом случае процесс дешифровки также состоит в применении отображения возведения в степень, то есть x заменяется на x d в кольце вычетов Zn . Так как de = 1 + mj(n) для некоторого целого числа m, то по теореме 3 в кольце вычетов Zn получаем
x de = x1 + mj(n) = x " x mj(n) = x[1] = x.
Процесс возведения произвольного числа x в степень d не является сложным. Достаточно многократно возводить числа в квадрат и затем перемножать результаты. Этот алгоритм требует не более 3[log2 n] умножений [4, c. 13]. Кроме того, поскольку вычисления осуществляются в кольце вычетов Zn , то требуется брать остаток при делении на n. К тому же требуется находить разложения из теоремы 2, которое требует O(log2 n) времени [4, c. 11].
Напомним, что в математике принята следующая терминология. Пусть f (n), g(n) - две последовательности. Говорят, что последовательность f (n) растет как O(g(n)), если существует такая ненулевая константа C, что отношение f (n)/ g(n) стремится к C вместе с ростом n. Таким образом, процесс шифрования и дешифрования представляется несложной процедурой, не требующей больших вычислительных ресурсов, поскольку рост O(log2 n) представляется довольно медленным. Для начала работы с этим шифром всем абонентам по открытому каналу передается справочник с набором пар чисел ni , ei , соответствующих i-му абоненту сети для любого i. При этом каждое число ni является произведением двух различных простых чисел ni = piqi . Числа di являются секретными. Для передачи сообщений x от i-го абонента j-му необходимо x преобразовать в x f, f = = ej , в Zn и переслать его по открытому каналу связи. j-й абонент, получив x f, возводит его в степень dj и получает x в силу (4). При этом i-й абонент может подписать свое сообщение. Для этого он посылает текст mg, где g = diej , причем все вычисления mg происходят в Zk , k = nj . j-й абонент дешифрует это сообщение, возводя его в степень djei , и получает m. При этом если он возводит его в другую степень djes , где s отлично от i, то получает бессмысленное сообщение. Другими словами, j-й абонент точно уверен, что он получил сообщение от i-го абонента.
Посторонний наблюдатель знает числа x f, ej , nj . Для нахождения x ему необходимо знать dj . Для этого в силу равенства dj = 1 + mj(nj) нужно уметь вычислять число j(nj) = (pj - 1)(qj - 1) = nj - (pj + qj) + 1. Поскольку число nj известно из справочника, то для решения задачи дешифровки нужно уметь вычислять pj + qj . Число nj = pjqj , как известно, включено в справочник. Но тогда в силу теоремы Виета наша задача сводится к нахождению самих чисел pj , qj , то есть к задаче о разложении числа nj в произведение двух простых чисел pj , qj .
RSA-система требует для большого числа абонентов построения достаточно больших простых чисел и разработки быстрых критериев проверки простоты заданного большего числа n. Обзор литературы по этому вопросу можно найти в [1; 4, гл. 2, ╕ 3].
Значительно сложнее оказался вопрос о разложении заданного большого числа на простые множители, даже если известно, что их всего два. В 1977 году Р. Ривестом, А. Шамиром, Л. Адлеманом была составлена таблица с указанием машинного времени, необходимого для существовавших тогда компьютеров, чтобы разложить наугад взятое натуральное число с данным количеством десятичных знаков на множители (табл. 3).
Хотя за прошедшие годы вычислительные возможности возросли, характер табл. 3 принципиально не изменился. Обзор попыток решить поставленную задачу теоретико-числовыми методами изложен в [5]. Скорее всего, решение этой задачи будет найдено при построении квантового компьютера, теоретические обоснования для которого были изложены на математическом конгрессе в Берлине в августе 1998 году. По замыслу создателей этот компьютер будет решать задачу разложения числа с n десятичными знаками за время O(nk) для некоторого натурального k, не зависящего от n. Построение физической и математической модели такого компьютера - это задача будущего столетия. Подробнее с этими применениями и деталями обоснования RAS-системы можно познакомиться в статье В.А. Успенского [3], в книгах [1, 2]. Таким образом, исследования в указанном направлении находят и будут находить широкое применение. Можно выразить надежду, что новые поколения математиков смогут внести достойный вклад в развитие этих областей.
ЛИТЕРАТУРА
1. Введение в криптографию / Под ред. В.В. Ященко. М.: МЦНМО-Черо, 1998. 272 с.
2. Акритас А. Основы компьютерной алгебры с приложениями. М.: Мир, 1994. 544 с.
3. Успенский В.А. Как теория чисел помогает в шифровальном деле // Соросовский Образовательный Журнал. 1996. ╧ 6. С. 122-127.
4. Манин Ю.И., Панчишкин А.А. Введение в теорию чисел // Современные проблемы математики: Фундаментальные направления. М.: ВИНИТИ, 1990. Т. 49: Теория чисел 1. 348 с.
5. Boeneh Dan. Twenty Years of Attacks on the RSA Cryptosystem // Not. Amer. Math. Soc. 1999. Vol. 46, ╧ 2. P. 203-213.
Рецензент статьи Ю.П. Соловьев
* * *
Вячеслав Александрович Артамонов, доктор физико-математических наук, профессор кафедры высшей алгебры механико-математического факультета МГУ. Область научных интересов - кольца, универсальная алгебра и их приложения. Автор 90 научных работ и двух книг.
