2.1. Предыстория и основные идеи

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

Первая задача — хранение паролей в компьютере. Мы знаем, что каждый пользователь в сети имеет свой секретный пароль. При входе в сеть пользователь указывает свое имя (несекретное) и затем вводит пароль. Проблема состоит в следующем: если хранить пароль на диске компьютера, то Ева может прочитать его, а затем использовать для несанкционированного доступа (особенно легко это сделать, если Ева работает системным администратором этой сети). Поэтому необходимо организовать хранение паролей в компьютере так, чтобы такой «взлом» был невозможен.

Вторая задача возникла с появлением радиолокаторов и системы ПВО. При пересечении самолетом границы радиолокатор спрашивает пароль. Если пароль верный, то самолет «свой», в противном случае — «чужой». Здесь возникает такая проблема: так как пароль должен передаваться по открытому канале (воздушной среде), то противник может прослушивать все переговоры и узнавать правильный пароль. Затем «чужой» самолет в случае запроса повторит перехваченный ранее «правильный» пароль в качестве ответа локатору и будет пропущен!

Третья задача похожа на предыдущую и возникает в компьютерных сетях с удаленным доступом, например, при взаимодействии банка и клиента. Обычно в началe сеанса банк запрашивает у клиента имя, а затем секретный пароль, но Ева может узнать пароль, так как линия связи открытая.

Сeгодня все эти проблемы решаются с использованием криптографических методов. Решение всех этих задач основано на важном понятии односторонней функции (one-way function).

Определение 2.1. Пусть дана функция

              (2.1)

определенная на конeчном множестве , для которой существует обратная функция

              (2.2)

Функция называeтся односторонней, если вычисление по формуле (2.1) — простая задача, требующая нeмного времени, а вычисление по (2.2) — задача сложная, требующая привлeчeния массы вычислительных ресурсов, напримeр, 106-1010 лет работы мощного суперкомпьютера.

Данное определение, безусловно, нeформально. Строгое определение односторонней функции может быть найдeно в [22, 23], но для наших целей достаточно и вышеприведенного.

В качестве примера односторонней функции рассмотрим следующую:

              (2.3)

где p — нeкотороe простое число (т.е. такое, которое делится без остатка только на себя и на единицу), а x — целое число из множества {1, 2,... ,р — 1}. Обратная функция обозначаeтся

              (2.4)

и называется дискретным логарифмом.

Для того чтобы обеспечить трудность вычисления по (2.4) при использовании лучших современных компьютеров, в настоящее время используются числа размером более 512 бит. На практике часто применяются и другие односторонние функции, например, так называемые хеш-функции, оперирующие с существенно более короткими числами порядка 60-120 бит (они будут рассмотрены в главе 4).

Сначала мы покажем, что вычисление по (2.3) может быть выполнено достаточно быстро. Начнем с примера вычисления числа a16 modp. Мы можем записать

т.е. значение данной функции вычисляется всего за 4 операции умножения вместо 15 при «наивном» варианте . На этом основан общий алгоритм.

Для описания алгоритма введем величину — целую часть (далее все логарифмы будут двоичные, поэтому в дальнейшем мы не будем указывать основание 2). Вычисляем числа ряда

              (2.5)

В ряду (2.5) каждое число получается путем умножения предыдущего числа самого на себя по модулю p. Запишем показатель степени x в двоичной системе счисления:

Тогда число может быть вычислено как

              (2.6)

(все вычисления проводятся по модулю p).

П р и м е р 2.1. Пусть требуется вычислить 3100 mod 7. Имеем t = [log 100] = 6. Вычисляем числа ряда (2.5):

              (2.7)

Записываем показатель в двоичной системе счисления

100 = (1100100)2

и проводим вычисления по формуле (2.6):

              (2.8)

Нам потребовалось всего 8 операций умножения (6 для вычисления ряда (2.7) и 2 для (2.8)).

В общем случае справедливо следующее

Утверждение 2.1 (о сложности вычислений (2.3)). Количество операций умножения при вычислении (2.3) по описатому методу не превосходит 2 log x.

Доказательство. Для вычисления чисел ряда (2.5) требуется t умножений, для вычисления у по (2.6) не более, чем t умножений (см. пример 2.1). Из условия t = [log x], учитывая, что [log x] log x, делаем вывод о справедливости доказываемого утверждения.

Замечание. Как будет показано в дальнейшем, при возведении в степень по модулю p имеет смысл использовать только показатели x < p. В этом случае мы можем сказать, что количество операций умножения при вычислении (2.3) не превосходит 2 log p.

Важно отметить, что столь же эффективные алгоритмы вычисления обратной функции (2.4) неизвестны. Так, один из методов вычисления (2.4), называемый «шаг младенца, шаг великана» (см. [12]), требует порядка операций. Покажем, что при больших p функция (2.3) действительно односторонняя, если для вычисления обратной функции используется метод «шаг младенца, шаг великана». Получаем следующий результат (табл. 2.1).

Таблица2.1. Количество умножений для вычисления прямой и обратной функции


Мы видим, что если использовать модули, состоящие из 50-100 десятичных цифр, то «прямая» функция вычисляется быстро, а обратная практически не вычислима. Рассмотрим, например, суперкомпьютер, который умножает два 90-значных числа за 10-14 сек. (для современных компьютеров это пока не доступно). Для вычисления (2.3) такому компьютеру потребуется

а для вычисления (2.4) —

т.е. более 1022 лет. Мы видим, что вычисление обратных функций практически невозможно при длине чисел порядка 90 десятичных цифр, и использование параллельных вычислений и компьютерных сетей существенно не меняет ситуацию. В рассмотренном примере мы предполагали, что обратная функция вычисляется за операций. В настоящее время известны и более «быстрые» методы вычисления дискретного логарифма, однако общая картина та же — количество требуемых в них операций много больше 2 log p. Таким образом, можно утверждать, что функция (2.3) действительно односторонняя, но с оговоркой. Никем не доказано, что обратная функция (2.4) не может быть вычислена столь же быстро, как и «прямая».

Используем одностороннюю функцию (2.3) для решения всех трех задач, описанных в начале данного раздела, не забывая, однако, что точно так же может быть использована и любая другая односторонняя функция.

Начнем с хранения паролей в памяти компьютера. Решение задачи основано на том, что пароли вообще не хранятся! Точнее, при регистрации в сети пользователь набирает свое имя и пароль; пусть, например, его имя — «фрукт», а пароль — «абрикос». Компьютер рассматривает слово «абрикос» как двоичную запись числа x и вычисляет (2.3), где а и p — два несекретные числа, возможно даже, всем известные. После этого в памяти компьютера заводится пара (имя, у), где у вычислено по (2.3) при x = пароль. При всех дальнейших входах этого пользователя после ввода пары («фрукт», «абрикос»), компьютер вычисляет по (2.3) новое значение унов с x = «абрикос» и сравнивает с хранящимся в памяти ранее вычисленным значением у. Если унов совпадает с хранящимся в памяти у, соответствующим данному имени, то это законный пользователь. В противном случае это Ева.

Ева могла бы попытаться найти x по у. Однако мы видели, что уже при 90-значных числах для этого потребуется более чем 1022 лет. Таким образом, представленная система хранения пароля весьма надежна и в настоящее время используется во многих реальных операционных системах.

Рассмотрим решение второй задачи (ПВО и самолет). Можно использовать следующий метод. Каждому «своему» самолету присваивается секретное имя, известное системе ПВО и летчику, точнее, бортовому компьютеру. Пусть, например, одному из самолетов присвоено секретное имя СОКОЛ, и этот самолет приближается к границе 01 февраля 2005 года в 12 час.45 мин. Тогда перед приближением к границе бортовой компьютер самолета формирует слово

Другими словами, компьютер на самолете и станция ПВО прибавляют к секретному слову сведения о текущем времени и, рассматривая полученное слово как число x, вычисляют , где а и p не секретны. Затем самолет сообщает число у стащии ПВО. Стащия сравнивает вычисленное ею число у с полученным от само¬лета. Если вычисленное и полученное значения совпали, то самолет признается как «свой».

Противник не может взломать эту систему. Действительно, с одной стороны, он не знает секретного слова СОКОЛ и не может найти его по у, так как вычисление x по у занимает, скажем, 1022 лет. С другой стороны, он не может просто скопировать у и использовать его в качестве ответа в будущем, так как время пересечения границы никогда не повторяется и последующие значения у будут отличаться от первоначального.

Рассмотренный вариант решения «задачи ПВО» требует точной синхронизации часов в самолете и в локаторе. Эта проблема достаточно легко решается. Например, служба навигации постоянно передает метки времени в открытом виде (время не секретно), и все самолеты и локаторы используют эти метки для синхронизации своих часов. Но есть более тонкие проблемы. Метка времени добавляется в слово x для того, чтобы все вычисляемые значения у были различы и противник не мог их повторно использовать. Однако противник может попытаться мгновенно повторить у в пределах текущей минуты. Как предотвратить эту возможность? Это первый вопрос. Другое затруднение возникает в ситуации, когда самолет посылает число у в конце 45-й минуты, а локатор принимает его в начале 46-й. Мы предоставляем читателю возможность самостоятельно предложить вариант решения этих проблем.

Другой способ решения «задачи ПВО» возможен если мы будем использовать дополнительный открытый канал передачи данных от локатора к самолету. Как и вьше, каждый «свой» самолет и локатор знают секретное слово (типа СОКОЛ), которое не заменяется. Обнаружив цель, локатор посылает ей случайно сгенерированное число а («вызов»). Самолет вычисляет , где x — секретное слово («СОКОЛ»), и сообщает число у локатору. Локатор воспроизводит те же вычисления и сравнивает вычисленное у и принятое. В этой схеме не нужно синхронизировать часы, но, как и ранее, противник не может повторить число у, так как локатор всякий раз посылает разные вызовы (а). Интересно, что эта задача, по-видимому, была исторически первой, при решении которой использовались односторонние функции.

Третья задача решается совершенно аналогично, и оба рассмотренных метода формирования пароля применимы и используются в реальных сетевых протоколах.


2.2. Первая система с открытым ключом - система Диффи-Хеллмана

Эта криптосистема была открыта в середине 70-х годов американскими учеными Диффи (Whitfield Diffie) и Хейлманом (Martin Hellman) и привела к настоящей революции в криптографии и ее практических применениях. Это первая система, которая позволяла защищать информацию без использования секретных ключей, передаваемых по защищенным каналам. Для того чтобы продемонстрировать одну из схем примeнeния таких систем, рассмотрим сеть связи с N пользователями, где N — большое число. Пусть мы хотим организовать сeкрeтную связь для каждой пары из них. Если мы будем использовать обычную систему распределения секретных ключей, то каждая пара абонентов должна быть снабжена своим секретным ключом, т.е. всего потребуется ключей.

Если абонентов 100, то требуется 5000 ключей, если же абонeнтов 104, то ключей должно быть 5 107. Мы видим, что при большом числе абонентов система снабжения их секретными ключами становится очень громоздкой и дорогостоящей.

Диффи и Хеллман решили эту проблему за счет открытого распространeния и вычисления ключей. Перейдем к описанию предложенной ими системы.

Пусть строится система связи для абонентов A, B,C,... ,У каждого абонента есть своя секретная и открытая информация. Для организации этой системы выбирается большое простое число p и некоторое число g, 1 < g < p — 1, такое, что все числа из множества {1, 2, ... , p — 1} могут быть представлены как различные степени g mod p (известны различные подходы для нахождения таких чисел g, один из них будет прeдставлeн ниже). Числа p и g известны всем абонeнтам.

Абоненты выбирают большие числа XA,XB, XC, которые хранят в секрете (обычно такой выбор рекомендуется проводить случайно, используя датчики случайных чисел). Каждый абонент вычисляет соответствующее число Y , которое открыто передается другим абонентам,

              (2.9)

В результате получаем следующую таблицу.

Т а б л и ц а 2.2. Ключи пользователей в системе Диффи-Хеллмана

Допустим, абонент A решил организовать сеанс связи с B, при этом обоим абонентам доступна открытая информация из табл. 2.2. Абонент A сообщает B по открытому каналу, что он хочет передать ему сообщение. Затем абонент A вычисляет величину

              (2.10)

(никто другой кроме A этого сделать не может, так как число XA секретно). В свою очередь, абонент B вычисляет число

              (2.11)

Утверждение 2.2. ZAB = ZBA.

Д о к а з а т е л ь с т в о. Действительно,

(Здесь первое равенство следует из (2.10), второе и четвертое — из (2.9), последнее — из (2.11).)

Отметим главные свойства системы:

1) абоненты A и B получили одно и то же число Z = ZAB = ZBA , которое не передавалось по открытой линии связи;

2) Ева не знает секретных чисел XA , XB,..., поэтому не может вычислить число ZAB (вообще говоря, она могла бы попытаться найти секретное число XA по YA (см. (2.9)), однако при больших p это практически невозможно (требуются миллионы лет)).

Абоненты A и B могут использовать ZAB в качестве секретного ключа для шифрования и дешифрования данных. Таким же образом любая пара абонентов может вычислить секретный ключ, известный только им.

Остановимся теперь на упомянутой выше задаче выбора числа g. При произвольно заданном p она может оказаться трудной задачей, связанной с разложением на простые множители числа p — 1. Дело в том, что для обеспечения высокой стойкости рассмотренной системы число p — 1 должно обязательно содержать большой простой множитель (в противном случае алгоритм Полига-Хеллмана, описанный, например, в [23], быстро вычисляет дискретный логарифм). Поэтому часто рекомендуют использовать следующий подход. Простое число p выбирается таким, чтобы выполнялось равенство

где q — также простое число. Тогда в качестве g можно взять любое число, для которого справедливы неравенства

П р и м е р 2.2. Пусть p =23 = 2 11 + 1 (q = 11). Выберем параметр g. Попробуем взять g = 3. Проверим: 311 mod 23 = 1 и значит, такое g не подходит. Возьмем g = 5. Проверим: 511 mod 23 = 22. Итак, мы выбрали параметры p = 23, g = 5. Теперь каждый абонент выбирает секретное число и вычисляет соответствующее ему открытое число. Пусть выбраны XA = 7, XB = 13. Вычисляем YA = 57 mod 23 = 17, YB = 513 mod 23 = 21. Пусть A и B решили сформировать общий секретный ключ. Для этого A вычисляет ZAB = 217 mod 23 = 10, а B вычисляет ZBA = 1713 mod 23 = 10. Теперь они имеют общий ключ 10, который не передавался по каналу связи.


2.3. Элементы теории чисел

Многие криптографические алгоритмы базируются на результатах классической теории чисел. Мы рассмотрим необходимый минимум из этой теории. Классические теоремы Ферма, Эйлера и ряд других результатов из теории чисел будут даны без доказательств, которые могут быть найдены практически в любом учебнике по теории чисел (см., например, [3]). Читатели, знакомые с теорией чисел, могут непосредственно перейти к разд. 2.4.

Определение 2.2. Целое положительное число p называется простым, если оно не делится ни на какое другое число, кроме самого себя и единицы.

П р и м е р 2.3. Числа 11, 23 — простые; числа 27, 33 — составные (27 делится на 3 и на 9, 33 делится на 3 и на 11).

Теорема 2.3 (основная теорема арифметики). Любое целое положительное число может быть представлено в виде произведения простых чисел, причем единственным образом.

П р и м е р 2.4. 27 = 3 3 3, 33 = 3 11.

Определение 2.3. Два числа называются взаимно простыми, если они не имеют ни одного общего делителя кроме единицы.

П р и м е р 2.5. Числа 27 и 28 взаимно просты (у них нет общих делителей кроме единицы), числа 27 и 33 — нет (у них есть общий делитель 3).

Определение 2.4 (функция Эйлера). Пусть дано целое число . Значение функции Эйлера равно количеству чисел в ряду 1, 2, 3,..., N — 1, взаимно простых с N.

П р и м е р 2.6.

(здесь зачеркнуты числа, не взаимнопростые с аргументом).

Утверждение 2.4. Если p — простое число, то

Доказательство. В ряду 1, 2, 3,... ,p — 1 все числа взаимно просты с p, так как p — простое число и по определению не делится ни на какое другое число.

Утверждение 2.5. Пусть p и qдва различных простых числа . Тогда .

Доказательство. В ряду 1, 2,... ,pq — 1 не взаимнопростыми с pq будут числа

и

Всего таких чисел будет (q — 1) + (p — 1). Следвательто, количество чисел, взаимнопростых с pq, будет pq — 1 — (p — 1) — (q — 1) = pq — q — p + 1 = (p — 1) (q — 1).

Теорема 2.6 (Ферма). Пусть p — простое число и 0 < a < p. Тогда

П р и м е р 2.7. p = 13, a = 2;

Теорема 2.7 (Эйлер). Пусть a и b — взаимно простые числа. Тогда

Теорема Ферма является частным случаем теоремы Эйлера, когда b — простое число.

П р и м е р 2.8.

Нам понадобится еще одна теорема, близкая к теореме Эйлера.

Теорема 2.8. Если p и q — простые числа, p = q и к — произвольное целое число, то

              (2.12)

П р и м е р 2.9. Возьмем p = 5, q = 7. Тогда pq = 35, а функция Эйлера — . Рассмотрим случай к = 2, т.е. будем возводить числа в степень 2 24 + 1 = 49. Получим

Это не удивительно, так как каждое из чисел 9 и 23 взаимно просто с модулем 35, и по теореме Эйлера 924 mod 35 = 1, 2324 mod 35 = 1. Однако теорема 2.8 остается верной и для следующих чисел:

в то время как теорема Эйлера для них не применима (каждое из чисел 10 и 28 не взаимно просто с модулем 35 и 1024 mod 35 = 15, 2824 mod 35 = 21).

Определение 2.5. Пусть а и b — два целых положительных числа. Наибольший общий делитель чисел а и b есть наибольшее число c, которое делит и а и b:

(Обозначение gcd для наибольшего общего делителя происходит от английских слов greatest common divisor и принято в современной литературе.)

П р и м е р 2.10. gcd(10,15) = 5; gcd(8, 28) = 4.

Для нахождения наибольшего общего делителя можно использовать следующий алгоритм, известный как алгоритм Евклида.

Алгоритм 2.1. АЛГОРИТМ ЕВКЛИДА

ВХОД:       Положительные целые числа a, b, a b.

ВЫХОД: Наибольший общий делитель gcd(a, b).


П р и м е р 2.11. Покажем, как с помощью алгоритма Евклида вычисляется gcd(28, 8):

Здесь каждый столбец представляет собой очередную итерацию алгоритма. Процесс продолжается до тех пор, пока b не станет равным нулю. Тогда в значении переменной a содержится ответ (4).

Для многих криптографических систем, рассматриваемых в следующих разделах и главах, актуален так называемый обобщенный алгоритм Евклида, с которым связана следующая теорема.

Теорема 2.9. Пусть a и b — два целых положительных числа. Тогда существуют целые (нe обязательно положительные) числа x и y , такие, что

              (2.13)

Обобщенный алгоритм Евклида служит для отыскания gcd(a, b) и x, y, удовлетворяющих (2.13). Введем три строки U = (u1, u2, u3), V = (v1, v2, v3) и T = (t1, t2, t3). Тогда алгоритм записывается следующим образом.

Алгоритм 2.2. ОБОБЩЕННЫЙ АЛГОРИТМ ЕВКЛИДА

ВХОД:       Положительные целые числа a,b, a > b.

ВЫХОД:       gcd(a, b), x, y, удовлетворяющие (2.13).


Результат содержится в строке U.

Операция div в алгоритме — это целочисленное деление

Доказательство корректности алгоритма 2.2 может быть найдeно в [1, 9].

П р и м е р 2.12. Пусть a=28, b=19. найдeм числа x и у, удовлетворяющие (2.13).

Поясним представленную схему. Вначалe в строку U записываются числа (28,1,0), а в строку V — числа (19,0,1) (это первые две строки на схеме). Вычисляется строка T (третья строка в схеме). После этого в качестве строки U берется вторая строка в схеме, а в качестве V — третья, и опять вычисляется строка T (четвертая строка в схеме).

Этот процесс продолжается до тех пор, пока первый элемент строки V не станет равным нулю. Тогда предпоследняя строка в схеме содержит ответ. В нашем случае gcd(28,19) = 1, x = —2, у = 3. Выполним проверку: 28 (—2)+ 19 3=1.

Рассмотрим одно важное применение обобщенного алгоритма Евклида. Во многих задачах криптографии для заданных чисел c, m требуется находить такое число d < m, что

              (2.14)

Отметим, что такое d существует тогда и только тогда, когда числа c и m взаимно простые.

Определение 2.6. Число d, удовлетворяющее (2.14), называется инверсией c по модулю m и часто обозначается c-1 mod m.

Данное обозначение для инверсии довольно естественно, так как мы можем теперь переписать (2.14) в виде

Умножение на c-1 соответствует делению на c при вычислениях по модулю m. По аналогии можно ввести произвольные отрицательные степени при вычислениях по модулю m:

П р и м е р 2.13. 3 4 mod 11 = 1, поэтому число 4 — это инверсия числа 3 по модулю 11. Можно записать 3-1 mod 11 = 4. Число 5-2 mod 11 может быть найдено двумя способами:

При вычислениях по второму способу мы использовали равенство 5-1 mod 11 = 9. Действительно, 5 9 mod 11 = 45 mod 11 = 1.

Покажем, как можно вычислить инверсию с помощью обобщенного алгоритма Евклида. Равенство (2.14) означает, что для некоторого целого k

              (2.15)

Учитывая, что c и m взаимно просты, перепишем (2.15) в виде

              (2.16)

что полностью соответствует (2.13), здесь только по-другому обозначены переменные. Поэтому, чтобы вычислить c-1 mod m, т.е. найти число d, нужно просто использовать обобщенный алгоритма Евклида для решения уравнения (2.16). Заметим, что значение переменной k нас не интересует, поэтому можно не вычислять вторые элементы строк U , V , T . Кроме того, если число d получается отрицательным, то нужно прибавить к нему m, так как по определению число a mod m берется из множества {0,1,..., m — 1}.

П р и м е р 2.14. Вычислим 7-1 mod 11. Используем такую же схему записи вычислений, как в примере 2.12 :

Получаем d = —3 и d mod 11 = 11 — 3 = 8, т.е. 7-1 mod 11 = 8.

Проверим результат: 7 8 mod 11 = 56 mod 11 = 1.

Одной из важнейших операций в криптографии с открытыми ключами является операция возведения в степень по модулю. Идея построения эффективного алгоритма возведения в степень была ранее проиллюстрирована с помощью (2.5) и (2.6). Рассмотренный алгоритм можно реализовать и без хранения в памяти ряда чисел (2.5). Дадим описание этого алгоритма в форме, пригодной для непосредственной программной реализации. В названии алгоритма отражен тот факт, что биты показателя степени просматриваются справа-налево, т.е. от младшего к старшему.

Алгоритм 2.3. ВОЗВЕДЕНИЕ В СТЕПЕНЬ (СПРАВА-НАЛЕВО)

ВХОД:       Целые числа a, x = (xt xt-1 ... x0)2, p.

ВЫХОД:       Число y = ax mod p.

Чтобы показать, что по представленному алгоритму действительно вычисляется y согласно (2.6), запишем степени переменных после каждой итерации цикла. Пусть x = 100 = (1100100)2, как в примере 2.1, тогда:

В некоторых ситуациях более эффективным оказывается следующий алгоритм, в котором биты показателя степени просмативаются слева-направо, т.е. от старшего к младшему.

Алгоритм 2.4. ВОЗВЕДЕНИЕ В СТЕПЕНЬ (СЛЕВА-НАПРАВО)

ВХОД:       Целые числа a, x = (xt xt-1 ... x0)2, p.

ВЫХОД:       Число y = ax mod p.

Приведенных в данном разделе сведений из теории чисел будет достаточно для описания основой криптографических алгоритмов и методов.


2.4. Шифр Шамира

Этот шифр, предложенный Шамиром (Adi Shamir), был первым, позволяющим организовать обмен секретными сообщениями по открытой линии связи для лиц, которые не имеют никаких защищенных каналов и секретных ключей и, возможно, никогда не видели друг друга. (Напомним, что система Диффи-Хеллмана позволяет сформировать только секретное слово, а передача сообщения потребует использования некоторого шифра, где это слово будет использоваться как ключ.)

Перейдем к описанию системы. Пусть есть два абонента A и B, соединенные линией связи. A хочет передать сообщение m абоненту B так, чтобы никто не узнал его содержание. A выбирает случайное большое простое число p и открыто передает его B. Затем A выбирает два числа cA и dA, такие, что

              (2.17)

Эти числа A держит в секрете и передавать не будет. B тоже выбирает два числа cB и dB , такие, что

              (2.18)

и держит их в секрете.

После этого A передает свое сообщение m, используя трехступенчатый протокол. Если m < p (m рассматривается как число), то сообщение m передается сразу , если же m p, то сообщение предствляется в виде m1, m2, . . . , mt , где все mi < p, и затем передаются последовательно m1, m2, ... ,mt. При этом для кодирования каждого mi лучше выбирать случайно новые пары (cA, dA) и (cB,dB) — в противном случае надежность системы понижается. В настоящее время такой шифр, как правило, используется для передачи чисел, например, секретных ключей, значения которых меньше p. Таким образом, мы будем рассматривать только случай m < p. Дадим описание протокола.

Шаг 1. A вычисляет число

              (2.19)

где m — исходное сообщение, и пересылает х1 к B.

Шаг 2. B, получив х1, вычисляет число

              (2.20)

и передает x2 к A.

Шаг 3. A вычисляет число

              (2.21)

и передает его B.

Шаг 4. B, получив х3, вычисляет число

              (2.22)


Утверждение 2.10 (свойства протокола Шамира).

1) х4 = m, т.е. в результате реализации протокола от A к B действительно передается исходное сообщение;

2) злоумышленник не может узнать, какое сообщение было передано.

Доказательство. Вначалe заметим, что любое целое число может быть представлено в виде , где r = e mod (p — 1).

Поэтому на основании теоремы Ферма

              (2.23)

Справедливость первого пункта утверждения вытекает из следующей цепочки равенств:

  

(прeдпослeднee равенство следует из (2.23), а послeднee выполняeтся в силу (2.17) и (2.18)).

Доказательство второго пункта утвeрждeния основано на предположении, что для злоумышленника, пытающегося определить m, нe существует стратегии более эффективной, чем следующая. Вначалe он вычисляет cB из (2.20), затем находит dB и, наконeц, вычисляет x4 = m по (2.22). для осущeствлeния этой стратегии злоумышленник должeн решить задачу дискретного логарифмирования (2.20), что практически нeвозможно при больших p.

Опишем метод нахождeния пар cA,dA и cB, dB, удовлетворяющих (2.17) и (2.18). Достаточно описать только действия для абонeнта A, так как действия для B совершенно аналогичны. Число CA выбираем случайно так, чтобы оно было взаимно простым с p — 1 (поиск целесообразно вести среди нeчeтных чисел, так как p — 1 четно). Затем вычисляем dA с помощью обобщенного алгоритма Евклида, как это было объяснено в разд. 2.3.

П р и м е р 2.15. Пусть A хочет передать B сообщение m = 10. A выбирает p = 23, cA = 7 (gcd(7, 22) = 1) и вычисляет dA = 19.

Аналогично, B выбирает параметры cB = 5 (взаимно простое с 22) и dB = 9. Переходим к протоколу Шамира.

Таким образом, B получил передаваемое сообщение m =10.


2.5. Шифр Эль-Гамаля

Пусть имеются абоненты A, B, C, ..., которые хотят передавать друг другу зашифрованные сообщения, не имея никаких защищенных каналов связи. В этом разделе мы рассмотрим шифр, предложенный Эль-Гамалем (Taher ElGamal), который решает эту задачу, используя, в отличие от Шифра Шамира, только одну пересылку сообщения. Фактически здесь используется схема Диффи-Хеллмана, чтобы сформировать общий секретный ключ для двух абонентов, передающих друг другу сообщение, и затем сообщение шифруется путем умножения его на этот ключ. Для каждого следующего сообщения секретный ключ вычисляется заново. Перейдем к точному описанию метода.

Для всей группы абонентов выбираются некоторое большое простое число p и число g, такие, что различные степени g суть различные числа по модулю p (см. разд. 2.2). Числа p и g передаются абонентам в открытом виде (они могут использоваться всеми абонентами сети).

Затем каждый абонент группы выбирает свое секретное число ci, 1 < ci < p - 1 , и вычисляет соответствующее ему открытое число di,

              (2.24)

В результате получаем таблицу 2.3.


Т а б л и ц а 2.3. Ключи пользователей в системе Эль-Гамаля

Покажем теперь, как A передает сообщение m абоненту B. Будем предполагать, как и при описании шифра Шамира, что сообщение представлено в виде числа m < p.

Шаг 1. A формирует случайное число k, 1 < k < p — 2, вычисляет числа

              (2.25)

              (2.26)

и передает пару чисел (r, e) абоненту B.

Шаг 2. B, получив (r, e ), вычисляет

              (2.26)

Утверждение 2.11 (свойства шифра Эль-Гамаля).

1) Абонент B получил сообщение, т.е. m' = m;

2) противник, зная p, g, dB, r и e, не может вычислить m.

Доказательство. Подставим в (2.27) значение e из (2.26):

Теперь вместо r подставим (2.25), а вместо dB — (2.24):

По теореме Ферма

и, таким образом, мы получаем первую часть утверждения.

Для доказательства второй части заметим, что противник не может вычислить k в равенстве (2.25), так как это задача дискретного логарифмирования. Следовательно, он не может вычислить m в равенстве (2.26), так как m было умножено на неизвестное ему число. Противник также не может воспроизвести действия законного получателя сообщения (абонента B), так как ему не известно секретное число cB (вычисление cB на основании (2.24) — также задача дискретного логарифмирования).

П р и м е р 2.16. Передадим сообщение m = 15 от A к B. Выберем параметры аналогично тому, как это было сделано в примере 2.2 стр. 24. Возьмем p = 23, g = 5. Пусть абонент B выбрал для себя секретное число cB = 13 и вычислил по (2.24)

Aбонент A выбирает случайно число k, например k = 7, и вычисляет по (2.25), (2.26):

Теперь A посылает к B зашифрованное сообщение в виде пары чисел (17, 12). B вычисляет по (2.27)

Мы видим, что B смог расшифровать переданное сообщение.

Ясно, что по аналогичной схеме могут передавать сообщения все абоненты в сети. Заметим, что любой абонент, знающий открытый ключ абонента B, может посылать ему сообщения, зашифрованные с помощью открытого ключа dB. Но только абонент B, и никто другой, может расшифровать эти сообщения, используя известаый только ему секретный ключ cB. Отметим также, что объем шифра в два раза превышает объем сообщения, но требуется только одна передача данных (при условии, что таблица с открытыми ключами заранее известна всем абонентам).


2.6. Односторонняя функция с "лазейкой" и шифр RSA

Названный в честь его разработчиков Ривеста (Ron Rivest), Шамира (Adi Shamir) и Адлемана (Leonard Adleman), этот шифр до сих пор является одним из самых широко используемых.

Мы видели, что шифр Шамира полностью решает задачу обмена сообщениями, закрытыми для прочтения, в случае, когда абоненты могут пользоваться только открытыми линиями связи. Однако при этом сообщение пересылается три раза от одного абонента к другому, что является недостатком. Шифр Эль-Гамаля позволяет решить ту же задачу за одно пересылку данных, но объем передаваемого шифротекста в два раза превышает объем сообщения. Система RSA лишена подобных недостатков. Интересно то, что она базируется на другой односторонней функции, отличной от дискретного логарифма. Кроме того, здесь мы встретимся с еще одним изобретением современной криптографии - односторонней функцией с «лазейкой» (trapdoor function).

Эта система базируется на следующих двух фактах из теории чисел:

1) задача проверки числа на простоту является сравнительно легкой;

2) задача разложения чисел вида n = pq (p и q — простые числа) на множители является очень трудной, если мы знаем только n, а p и q — большие числа (это так называемая задача факторизации).

Пусть в нашей системе есть абоненты A, B, C, .... Каждый абонент выбирает случайно два больших простых числа P и Q. Затем он вычисляет число

              (2.28)

(Число N является открытой информацией, доступной другим абонентам.) После этого абонент вычисляет число и выбирает некоторое число , взаимно простое с , и по обобщенному алгоритму Евклида находит число c, такое, что

              (2.29)

Вся информация, связанная с абонентами и являющаяся их открытыми и секретными ключами, представлена в табл. 2.4.

Т а б л и ц а 2.4. Ключи пользователей в системе RSA

Опишем протокол RSA. Пусть Алиса хочет передать сообщение m Бобу, причем сообщение m рассматривается как число, удовлетворяющее неравенству m < NB (далее индекс B указывает на то, что соответствующие параметры принадлежат Бобу).

Шаг 1. Алиса шифрует сообщение по формуле

              (2.30)

используя открытые параметры Боба, и пересылает e по открытой линии.

Шаг 2. Боб, получивший зашифрованное сообщение, вычисляет

              (2.31)

Утверждение 2.12. Для описанного протокола m' = m, т.е. абонент B получает исходящее от A сообщение.

Д о к а з а т е л ь с т в о. По построению протокола

Равенство (2.29) означает, что для некоторого k

Согласно утверждению 2.5

где — функция Эйлера. Отсюда и из теоремы 2.8 следует


Утверждение 2.13 (свойства протокола RSA).

1) Протокол шифрует и дешифрует информацию корректно;

2) злоумышленник, перехватывающий все сообщения и знающий всю открытую информацию, не сможет найти исходное сообщение при болъших P и Q.

Д о к а з а т е л ь с т в о. Первое свойство протокола следует из утверждения 2.12. Для доказательства второго свойства заметим, что злоумышленник знаeт только открытые параметры N и d. Для того чтобы найти c, он должeн знать значeниe , а для этого, в свою очередь, ему требуется знать P и Q. Вообще говоря, он может найти P и Q, разложив N на множители, однако это трудная задача (см. пункт 2 в началe раздела). Отметим, что выбор больших случайных P и Q возможeн за приемлемое время, так как справедлив пункт 1.

Односторонняя функция , примeняeмая в системе RSA, обладает так называeмой «лазейкой», позволяющей легко вычислить обратную функцию , если известно разложение N на простые множители. (Действительно, легко вычислить , а затем .) Если P и Q нeизвeстны, то вычисление значeния обратной функции практически нeвозможно, а найти P и Q по N очень трудно, т.е. знаниe P и Q — это «лазейка» или «потайной ход»). Такие односторонние функции с лазейкой находят примeнeниe и в других разделах криптографии.

Отметим, что для схемы RSA важно, чтобы каждый абонeнт выбирал собствeнную пару простых чисел P и Q, т.е. все модули NA, NB, NC, ... должны быть различны (в противном случае один абонeнт мог бы читать зашифрованные сообщения, прeдназначeнныe для другого абонeнта). Однако этого нe требуется от второго открытого параметра d. Параметр d может быть одинаковым у всех абонeнтов. Часто рекомендуется выбирать d = 3 (при соответствующем выборе P и Q, см. [23]). Тогда шифрование выполняeтся максимально быстро, всего за два умножения.

П р и м е р 2.17. Допустим, Алиса хочет передать Бобу сообщение m =15. Пусть Боб выбрал следующие параметры:

(3 взаимно просто с = 20). Найдем cB с помощью обобщенного алгоритма Евклида: cB = 7

(проверим: 3 7 mod 20 = 1). Кодируем m по формуле (2.30)

Число 9 Алиса передает Бобу по открытому каналу связи. Только Боб знает cB = 7, поэтому он декодирует принятое сообщение, используя (2.31):

Таким образом, Боб расшифровал сообщение Алисы.

Рассмотренная система невскрываема при больших P и Q, но обладает следующим недостатком: A передает сообщение B, используя открытую информацию абонента B (числа NB и dB). Злоумышленник не может читать сообщения, предназначенные для B, однако он может передать сообщение к B от имени A. Избежать этого можно, используя более сложные протоколы, например, следующий.

A хочет передать B сообщение m. Сначала A вычисляет число . Злоумышленник не может этого сделать, так как СА секретно. Затем A вычисляет число и передает f к B. B получает f и вычисляет последовательно числа NB и .

В результате абонент B получает сообщение . Как и в исходной схеме RSA, злоумышленник не может прочитать переданное сообщение, но здесь, в отличие от RSA, он не может также послать сообщение от имени A (поскольку не знает секретного СА ).

Здесь мы встречаемся с новой ситуацией. B знает, что сообщение пришло от A, т.е. A как бы «подписал» его, зашифровав своим секретным СА. Это пример так называемой электронной или цифровой подписи. Она — одно из широко используемых на практике изобретений современной криптографии и будет систематически изучаться в главе 5.


Задачи и упражнения

2.1. Привести результат выражений 5, 16, 27, -4, -13, 3 + 8, 3 — 8,

3 8, 3 8 5:

       а. по модулю 10,

       б. по модулю 11.

См. ответ.

2.2. Вычислить, используя быстрые алгоритмы возведения в степень, 28 mod 10, 37 mod 10, 719 mod 100, 757 mod 100.

См. ответ.

2.3. Разложить на простые множители числа 108, 77, 65, 30, 159.

См. ответ.

2.4. Определить, какие из пар чисел (25, 12), (25, 15), (13, 39), (40, 27) взаимно просты.

См. ответ.

2.5. Найти значения функции Эйлера (14), (20).

См. ответ.

2.6. Используя свойства функции Эйлера, вычислить (53), (21), (159).

См. ответ.

2.7. Используя теорему Ферма, вычислить 313 mod 13, 522 mod 11, 317 mod 5.

См. ответ.

2.8. Используя теорему Эйлера, вычислить 39 mod 20, 214 mod 21, 2107 mod 159.

См. ответ.

2.9. С помощью алгоритма Евклида найти gcd(21,12), gcd(30,12), gcd(24, 40), gcd(33, 16).

См. ответ.

2.10. С помощью обобщенного алгоритма Евклида найти значения x и y в уравнениях

См. ответ.

2.11. Вычислить 3-1 mod 7, 5-1 mod 8, 3-1 mod 53, 10-1 mod 53.

См. ответ.

2.12. Выписать все простые числа, меньшие 100. Какие из них соответствуют виду p = 2q + 1, где q также простое?

См. ответ.

2.13. Найти все допустимые варианты выбора параметра g в системе Диффи-Хеллмана при p = 11.

См. ответ.

2.14. Вычислить открытые ключи YA, YB и общий ключ ZAB для системы Диффи-Хеллмана с параметрами:

См. ответ.

2.15. Для шифра Шамира с заданными параметрами p, cA, cB найти недостающие параметры и описать процесс передачи сообщения m от A к B: 

См. ответ.

2.16. Для шифра Эль-Гамаля с заданными параметрами p, g, cB, k найти недостающие параметры и описать процесс передачи сообщения m пользователю B:

См. ответ.

2.17. В системе RSA с заданными параметрами PA, QA, dA найти недостающие параметры и описать процесс передачи сообщения m пользователю A:

См. ответ.

2.18. Пользователю системы RSA с параметрами N = 187, d = 3 передано зашифрованное сообщение e = 100. Расшифровать это сообщение, взломав систему RSA пользователя.

См. ответ.