e,d,n

116 Глава 9. КРИПТОСИСТЕМА RSA, ПРОТОКОЛ ДИФФИ-ХЭЛЛМАНА И ЦИФРОВАЯ ПОДПИСЬ ЭЛЬ-ГАМАЛЯ

Широко известная криптографическая система RSA, предложенная в 1978 году, является асимметричной криптосистемой, основанной на односторонней функции с лазейкой, в качестве которой выбрана степенная функция в кольце вычетов целых чисел по составному (двупростому) модулю n = pq . На основе криптосистемы RSA можно построить механизм цифровой подписи [42]. Стойкость системы основана на сложности задачи факторизации больших двупростых чисел.

Криптосистема RSA на каждом такте шифрования преобразует двоичный блок открытого текста m длины size(n)= log2 n +1, рассматриваемый как целое число, с помощью возведения в степень по модулю n: c = me (n). Показатель степени и модуль являются элементами открытого ключа.

Лазейка обеспечивается за счет секретного ключа d , построенного таким образом, что для всех m выполняется соотношение cd = med = m(n).

9.1. Построение криптосистемы RSA. Идея цифровой подписи

Построение криптосистемы обеспечивает получатель сообщений.

Сначала случайным образом выбираются два различных больших простых числа p и q . Выбранные простые числа должны удовлетворять некоторым дополнительным условиям.

Затем вычисляется модуль n = pq , функция Эйлера от модуля

ϕ(n)= (p −1)(q −1), а также выбирается случайное число e, взаимно простое с

ϕ(n).

Секретный ключ строится с помощью расширенного алгоритма Эвклида,

как число d , удовлетворяющее сравнению de ≡1(ϕ(n)). После этого все данные, кроме , включая данные промежуточных вычислений,

уничтожаются. Пара e,n объявляется в качестве открытого ключа.

Построение криптосистемы RSA. Идея цифровой подписи 117

Расшифрование обеспечивается тем, что для (m,n)=1 из теоремы Эйлера следует cd = m1+kϕ ≡ m(n) и, кроме того, для других значений m соотношение med ≡ m(n) также имеет место, вследствие свойств модуля вида n = pq .

Свойства параметров криптосистемы RSA позволяют показать принципиальную возможность построения схемы электронной цифровой подписи.

Цифровой подписью (ЦП) называется результат специального криптографического преобразования, осуществленного над электронным документом его владельцем.

Цель преобразования – доказать неоспоримость текста документа и факта преобразования данных конкретным лицом.

Основной метод – проверка факта использования секретного параметра (ключа) подписи, без знания ключа проверяющим.

Подпись представляет собой блок данных. Подписанное сообщение представляет собой исходное сообщение, передаваемое совместно с ЦП.

Владелец секретного ключа d криптосистемы RSA мог бы в качестве подписанного сообщения представить пару (m,md )= (m,c). Действительно, преобразование md может осуществить только он. Поскольку m имеется в сообщении в исходном виде, любой абонент в состоянии проверить соотношение m = ce , которое будет выполняться лишь в том случае, когда действительно c = md .

Однако подобный подход не обеспечивает стойкость подписи при передаче случайных данных. Действительно, выберем число a и построим сообщение m = ae (n). Тогда, очевидно, (m,md )= (m,a), т.е. подпись построена без знания секретного ключа.

z = h(m)= h(m1 ).

z = h(m),

118 Глава 9. КРИПТОСИСТЕМА RSA, ПРОТОКОЛ ДИФФИ-ХЭЛЛМАНА И ЦИФРОВАЯ ПОДПИСЬ ЭЛЬ-ГАМАЛЯ

По этой причине лучше вместо (m,md )использовать пару (m,h(m)d ), где h(m) - т.н. хэш-функция сообщения m: несекретное, заранее обусловленное преобразование. Значение z = h(m) называется хэш-кодом сообщения m.

Проверка подписи (m,c) начинается с вычисления h(m), затем результат сравнивается с ce (m).

Реальные хэш-функции представляют собой сложные алгоритмы, рекомендованные в соответствующих стандартах [17,18]. Методика их обоснования выходит за рамки данной книги.

Определение хэш-функции. Хэш-функция z = h(m) - преобразование

битовой строки произвольной длины в битовую строку (блок) фиксированной длины (обычно, 160-512 битов), обладающее следующими свойствами.

1. Восстановление m по z , исходя из соотношения вычислительно нереализуемо.

2. Исходя из m и z , вычислительно нереализуемо определение второго прообраза для z , т.е. такого сообщения m1 ≠ m , что

На практике, как правило, используются хэш-функции, удовлетворяющие более жесткому, чем последнее, условию: требуется вычислительная нереализуемость нахождения произвольной коллизии, т.е. пары сообщений x, y , таких, что h(x)= h(y).

Рассмотрим пример построения (учебной) криптосистемы RSA.

1.p = 3 , q =11, n =33, ϕ(n)= 20 .

2.e = 7 (e,ϕ(n))=1.

3.d =3 ed =1(ϕ).

Протокол Диффи-Хэллмана 119

Зашифруем сообщение из трех блоков: 3,1,2.

RSA(3)=37 = 2187 =9(33), RSA(1)=17 =1(33),

RSA(2)= 27 =128 = 29(33).

Для расшифрования возведем блоки в степень d =3 по модулю 33:

93 = 729 = 3(33) , 13 =1(33) , 293 = 24389 = 2(33).

Секретный ключ для учебной системы легко найти перебором. На практике это невыполнимо, т.к. реальный размер модуля (длина битового представления) size(n) находится в диапазоне от 512 до 4096 битов.

9.2. Смешанные криптосистемы. Протокол Диффи-Хэллмана ключевого обмена

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

Здесь возникает новый тип задач, связанный с т.н. недоверием корреспондентов друг к другу.

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

Наиболее ранний протокол обмена ключами при взаимном недоверии участников обмена предложен Диффи и Хэллманом [29]. В этом протоколе используется показательная функция в простом поле Галуа GF(p), обратной к которой является дискретный логарифм.

120 Глава 9. КРИПТОСИСТЕМА RSA, ПРОТОКОЛ ДИФФИ-ХЭЛЛМАНА И ЦИФРОВАЯ ПОДПИСЬ ЭЛЬ-ГАМАЛЯ

Пусть абонент А является инициатором обмена. Он намерен выработать общий с абонентом В секретный ключ для симметричной криптосистемы.

При этом обоим корреспондентам известен первообразный элемент

(точнее, элемент большого порядка) g поля GF(p) и простое число p .

Протокол решает задачу построения общего секретного блока данных вида g xy (p), где x, y - случайные вычеты по модулю p −1.

Абонент А случайно выбирает x, вычисляет значение g x (p) и отправляет это значение абоненту В. Абонент В действует аналогично: выбирает y ,

вычисляет значение g y (p) и отправляет это значение абоненту А. Каждый из абонентов в состоянии теперь вычислить значение общего секретного блока g xy (p). Получить это значение, исходя из перехвата, оказывается, невозможно,

вследствие свойств дискретного логарифма, а подходов, неэквивалентных дискретному логарифмированию, не найдено.

Пример системы экспоненциального ключевого обмена Диффи-Хэллмана.

1.		p =13,	g = 7 ,	поскольку	g(p−1) 2 =117649 = −1(p),
g(p−1) 3 =9 ≠1(p).
2.	Абонент А генерирует			псевдослучайное	число, например,	x =8 и
передает абоненту В значение g x = 78 =3(13).
3.	В	аналогично генерирует y =5 и			отправляет А	значение
g y = 75 =11(13).
4. А вычисляет общий секретный параметр k = (g y )x =118 =9(13).
5.	В	вычисляет	общий	секретный параметр k = (g x )y =35 =9(13).