<< Предыдущая

стр. 17
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

где X – целое число, 1? x ? N –1.
Существуют эффективные алгоритмы, позволяющие достаточно быстро вычислить значения
функции fA,N (x).
Если y = Ax, то естественно записать x = logA (у).
Поэтому задачу обращения функции fA,N(x) называют задачей нахождения дискретного лога-
рифма или задачей дискретного логарифмирования.
Задача дискретного логарифмирования формулируется следующим образом. Для известных
целых A, N, y найти целое число x, такое, что
Ax mod N = y.
Алгоритм вычисления дискретного логарифма за приемлемое время пока не найден. Поэтому
модульная экспонента считается однонаправленной функцией.
По современным оценкам теории чисел при целых числах A ? 2664 и N ? 2664 решение задачи
дискретного логарифмирования (нахождение показателя степени x для известного y) потребует
около 1026 операций, т.е. эта задача имеет в 103 раз большую вычислительную сложность, чем зада-
ча разложения на множители. При увеличении длины чисел разница в оценках сложности задач воз-
растает.
Следует отметить, что пока не удалось доказать, что не существует эффективного алгоритма
вычисления дискретного логарифма за приемлемое время. Исходя из этого, модульная экспонента
отнесена к однонаправленным функциям условно, что, однако, не мешает с успехом применять ее на
практике.
Вторым важным классом функций, используемых при построении криптосистем с открытым
ключом, являются так называемые однонаправленные функции с "потайным ходом" (с лазейкой). Да-
дим неформальное определение такой функции. Функция
f:X>Y
относится к классу однонаправленных функций с "потайным ходом" в том случае, если она является
однонаправленной и, кроме того, возможно эффективное вычисление обратной функции, если извес-
тен "потайной ход" (секретное число, строка или другая информация, ассоциирующаяся с данной
функцией).
В качестве примера однонаправленной функции с "потайным ходом" можно указать исполь-
зуемую в криптосистеме RSA модульную экспоненту с фиксированными модулем и показателем сте-
пени. Переменное основание модульной экспоненты используется для указания числового значения
сообщения М либо криптограммы С (см. § 4.3.).


4.3. Криптосистема шифрования данных RSA
Алгоритм RSA предложили в 1978 г. три автора: Р.Райвест (Rivest), А.Шамир (Shamir) и
А.Адлеман (Adleman). Алгоритм получил свое название по первым буквам фамилий его авторов. Ал-
горитм RSA стал первым полноценным алгоритмом с открытым ключом, который может работать как
в режиме шифрования данных, так и в режиме электронной цифровой подписи [118].
Надежность алгоритма основывается на трудности факторизации больших чисел и трудности
вычисления дискретных логарифмов.
В криптосистеме RSA открытый ключ Кв, секретный ключ kв, сообщение М и криптограмма
С принадлежат множеству це-лых чисел
ZN = {0, 1, 2, ..., N –1}, (4.5)
где N – модуль:
N = P?Q. (4.6)
Здесь P и Q – случайные большие простые числа. Для обеспечения максимальной безопасности вы-
бирают P и Q равной длины и хранят в секрете.
Множество ZN с операциями сложения и умножения по модулю N образует арифметику по
модулю N.
Открытый ключ Кв выбирают случайным образом так, чтобы выполнялись условия:
1< Кв ? ? (N), НОД (Кв, ? (N)) =1, (4.7)
? (N)=(P –1) (Q –1), (4.8)
где ? (N) – функция Эйлера.
Функция Эйлера ? (N) указывает количество положительных целых чисел в интервале от 1
до N, которые взаимно про-cты с N.
Второе из указанных выше условий означает, что открытый ключ Кв и функция Эйлера ? (N)
должны быть взаимно простыми.
Далее, используя расширенный алгоритм Евклида, вычисляют секретный ключ kв, такой, что
kв ? Кв ? 1 (mod ? (N)) (4.9)
или
kв = Кв–1 (mod (P –1)(Q –1)).
Это можно осуществить, так как получатель В знает пару простых чисел (P,Q) и может легко
найти ? (N). Заметим, что kв и N должны быть взаимно простыми.
Открытый ключ Кв используют для шифрования данных, а секретный ключ kв – для расшиф-
рования.
Преобразование шифрования определяет криптограмму С через пару (открытый ключ Кв, со-
общение М) в соответствии со следующей формулой:
C = EK B (M) = EВ (M) = MK B (mod N). (4.10)
В качестве алгоритма быстрого вычисления значения C используют ряд последовательных
возведений в квадрат целого M и умножений на M с приведением по модулю N.
Обращение функции C = MK B (mod N), т.е. определение значения M по известным значениям
C, Кв и N, практически не осуществимо при N ? 2 512.
Однако обратную задачу, т.е. задачу расшифрования криптограммы С, можно решить, ис-
пользуя пару (секретный ключ kв, криптограмма С) по следующей формуле:
М = DkB (С) = DВ (C) = CkB (mod N). (4.11)
Процесс расшифрования можно записать так:
DВ(EВ (М)) = М. (4.12)
Подставляя в (4.12) значения (4.10) и (4.11), получаем:
(MK B ) k B = М (mod N)
или
MK BkB = M (mod N). (4.13)
Величина ? (N) играет важную роль в теореме Эйлера, которая утверждает, что если НОД (x,
N) =1, то
x?(N) ? 1 (mod N),
или в несколько более общей форме
xn??(N)+1 ? x (mod N). (4.14)
Сопоставляя выражения (4.13) и (4.14), получаем
Кв ? kв = n ? ? (N) +1
или, что то же самое,
Кв ? kв ?1 (mod ? (N)).
Именно поэтому для вычисления секретного ключа kв используют соотношение (4.9).
Таким образом, если криптограмму
C = MK B (mod N)
возвести в степень kв, то в результате восстанавливается исходный открытый текст М, так как
(MK B ) k B = MK BkB = Mn??(N)+1 ? M (mod N).
Таким образом, получатель В, который создает криптосистему, защищает два параметра: 1)
секретный ключ kв и 2) пару чисел (P,Q), произведение которых дает значение модуля N. С другой
стороны, получатель В открывает значение модуля N и открытый ключ Кв.
Противнику известны лишь значения Кв и N. Если бы он смог разложить число N на множи-
тели P и Q, то он узнал бы "потайной ход" – тройку чисел {P,Q,Кв}, вычислил значение функции
Эйлера
? (N) = (P –1) (Q –1)
и определил значение секретного ключа kв.
Однако, как уже отмечалось, разложение очень большого N на множители вычислительно не
осуществимо (при условии, что длины выбранных P и Q составляют не менее 100 десятичных зна-
ков).

Процедуры шифрования и расшифрования в криптосистеме RSA
Предположим, что пользователь А хочет передать пользователю В сообщение в зашифро-
ванном виде, используя криптосистему RSA. В таком случае пользователь А выступает в роли отпра-
вителя сообщения, а пользователь В – в роли получателя. Как отмечалось выше, криптосистему RSA
должен сформировать получатель сообщения, т.е. пользователь В. Рассмотрим последовательность
действий пользователя В и пользователя А.
1. Пользователь В выбирает два произвольных больших простых числа P и Q.
2. Пользователь В вычисляет значение модуля N = P * Q.
3. Пользователь В вычисляет функцию Эйлера
? (N) = (P –1) (Q –1)
и выбирает случайным образом значение открытого ключа Кв с учетом выполнения условий:
1< Кв ? ? (N), НОД (Кв, ? (N)) =1.
4. Пользователь В вычисляет значение секретного ключа kв, используя расширенный алгоритм
Евклида при решении сравнения
kв ? Кв–1 (mod ? (N)).
5. Пользователь В пересылает пользователю А пару чисел (N, Кв) по незащищенному каналу.
Если пользователь А хочет передать пользователю В сообщение М, он выполняет следующие
шаги.
6. Пользователь А разбивает исходный открытый текст М на блоки, каждый из которых может
быть представлен в ви-де числа
Мi = 0, 1, 2, ..., N –1.
7. Пользователь А шифрует текст, представленный в виде последовательности чисел Мi по фор-
муле
KB
Ci = M (mod N)
i
и отправляет криптограмму
С1, С2, С3, ..., Ci, ...
пользователю В.
8. Пользователь В расшифровывает принятую крип-тограмму
С1, С2, С3, ..., Ci, ...,
используя секретный ключ kв, по формуле
kB
Мi = C (mod N).
i
В результате будет получена последовательность чисел Мi, которые представляют собой ис-
ходное сообщение М. Чтобы алгоритм RSA имел практическую ценность, необходимо иметь возмож-
ность без существенных затрат генерировать большие простые числа, уметь оперативно вычислять
значения ключей Кв и kв.
Пример. Шифрование сообщения САВ. Для простоты вычислений будут использоваться небольшие числа. На прак-
тике применяются очень большие числа (см. следующий раздел).
Действия пользователя В.
1. Выбирает P = 3 и Q = 11.
2. Вычисляет модуль N = P?Q = 3?11 = 33.
3. Вычисляет значение функции Эйлера для N = 33:
? (N) = ? (33) = (P –1)(Q –1) = 2?10 = 20.
Выбирает в качестве открытого ключа Кв произвольное число с учетом выполне-ния условий:
1< Кв ? 20, НОД (Кв, 20) = 1.
Пусть Кв= 7.
4. Вычисляет значение секретного ключа kв, используя расширенный алгоритм Евклида (см. приложение) при решении
сравнения
kв ? 7 (mod 20).
–1

Решение дает kв= 3.
5. Пересылает пользователю А пару чисел (N = 33, Кв= 7).
Действия пользователя A.
6. Представляет шифруемое сообщение как последовательность целых чисел в диапазоне 0 ... 32. Пусть буква А пред-
ставляется как число 1, буква В – как число 2, буква С – как число 3. Тогда сообщение САВ можно представить как последова-
тельность чисел 312, т.е. М1 = 3, М2 = 1, М3 = 2.
7. Шифрует текст, представленный в виде последовательности чисел М1, М2 и М3, используя ключ Кв= 7 и N = 33, по фор-
муле
K
Ci = Mi в (mod N) = Mi7 (mod 33).
Получает
7
С1 = 3 (mod 33) = 2187 (mod 33) = 9,
7
С2 =1 (mod 33) =1 (mod 33) =1,
7
С3 = 2 (mod 33) =128 (mod 33) = 29.
Отправляет пользователю В криптограмму
С1, С2, С3 = 9, 1, 29.
Действия пользователя В.
8. Расшифровывает принятую криптограмму С1, С2, С3, используя секретный ключ kв= 3, по формуле
k
Mi = Ci в (mod N) = Ci3 (mod 33).
Получает
3
М1 = 9 (mod 33) = 729 (mod 33) = 3,
3
М2 =1 (mod 33) =1 (mod 33) =1,
3
М3 = 29 (mod 33) = 24389 (mod 33) = 2.
Таким образом, восстановлено исходное сообщение: С А В
312

Безопасность и быстродействие криптосистемы RSA
Безопасность алгоритма RSA базируется на трудности решения задачи факторизации боль-
ших чисел, являющихся произведениями двух больших простых чисел. Действительно, криптостой-
кость алгоритма RSA определяется тем, что после формирования секретного ключа kв и открытого
ключа Кв "стираются" значения простых чисел Р и Q, и тогда исключительно трудно определить сек-
ретный ключ kв по открытому ключу Кв, поскольку для этого необходимо решить задачу нахождения
делителей Р и Q модуля N.
Разложение величины N на простые множители Р и Q позволяет вычислить функцию ? (N) =
(P –1)(Q –1) и затем определить секретное значение kв, используя уравнение
Кв ? kв ?1 (mod ? (N)).
Другим возможным способом криптоанализа алгоритма RSA является непосредственное вы-
числение или подбор значения функции ? (N) = (P –1)(Q –1). Если установлено значение ? (N), то со-
множители Р и Q вычисляются достаточно просто. В самом деле, пусть
x = P + Q = N +1 – ? (N),
y = (P – Q)2 = (Р + Q)2 – 4?N.
Зная ? (N), можно определить x и затем y; зная x и y, можно определить числа Р и Q из сле-
дующих соотношений:
P = 1/2 (x + y ), Q = 1/2 (x – y ).
Однако эта атака не проще задачи факторизации модуля N [28].
Задача факторизации является трудно разрешимой задачей для больших значений модуля N.
Сначала авторы алгоритма RSA предлагали для вычисления модуля N выбирать простые
числа P и Q случайным образом, по 50 десятичных разрядов каждое. Считалось, что такие большие
числа N очень трудно разложить на простые множители. Один из авторов алгоритма RSA, Р.Райвест,
полагал, что разложение на простые множители числа из почти 130 десятичных цифр, приведенного
в их публикации, потребует более 40 квадриллионов лет машинного времени. Однако этот прогноз не
оправдался из-за сравнительно быстрого прогресса компьютеров и их вычислительной мощности, а
также улучшения алгоритмов факторизации.
Ряд алгоритмов факторизации приведен в [45]. Один из наиболее быстрых алгоритмов, из-
вестных в настоящее время, алгоритм NFS (Number Field Sieve) может выполнить факторизацию
большого числа N (с числом десятичных разрядов больше 120) за число шагов, оцениваемых вели-
чиной
1/ 3 (ln(ln n ))2 / 3
e 2(ln n ) .
В 1994 г. было факторизовано число со 129 десятичными цифрами. Это удалось осуществить
математикам А.Ленстра и М.Манасси посредством организации распределенных вычислений на 1600
компьютерах, объединенных сетью, в течение восьми месяцев. По мнению А.Ленстра и М.Манасси,
их работа компрометирует криптосистемы RSA и создает большую угрозу их дальнейшим примене-
ниям. Теперь разработчикам криптоалгоритмов с открытым ключом на базе RSA приходится избегать
применения чисел длиной менее 200 десятичных разрядов. Самые последние публикации предлага-
ют применять для этого числа длиной не менее 250 – 300 десятичных разрядов.
В [121] сделана попытка расчета оценок безопасных длин ключей асимметричных криптоси-
стем на ближайшие 20 лет исходя из прогноза развития компьютеров и их вычислительной мощности,
а также возможного совершенствования алгоритмов факторизации. Эти оценки (табл.4.1.) даны для
трех групп пользователей (индивидуальных пользователей, корпораций и государственных организа-
ций), в соответствии с различием требований к их информационной безопасности. Конечно, данные
оценки следует рассматривать как сугубо приблизительные, как возможную тенденцию изменений
безопасных длин ключей асимметричных криптосистем со временем.
Таблица 4.1
Оценки длин ключей для асимметричных криптосистем, бит
Государственные
Отдельные
Год Корпорации
организации
пользователи

1995 768 1280 1536
2000 1024 1280 1536
2005 1280 1536 2048
2010 1280 1536 2048
2015 1536 2048 2048

Криптосистемы RSA реализуются как аппаратным, так и программным путем.
Для аппаратной реализации операций зашифрования и расшифрования RSA разработаны
специальные процессоры. Эти процессоры, реализованные на сверхбольших интегральных схемах
(СБИС), позволяют выполнять операции RSA, связанные с возведением больших чисел в колоссаль-
но большую степень по модулю N, за относительно короткое время. И все же аппаратная реализация
RSA примерно в 1000 раз медленнее аппаратной реализации симметричного криптоалгоритма DES.
Одна из самых быстрых аппаратных реализаций RSA с модулем 512 бит на сверхбольшой
интегральной схеме имеет быстродействие 64 Кбит/с. Лучшими из серийно выпускаемых СБИС яв-
ляются процессоры фирмы CYLINK, выполняющие 1024-битовое шифрование RSA.
Программная реализация RSA примерно в 100 раз медленнее программной реализации DES.
С развитием технологии эти оценки могут несколько изменяться, но асимметричная криптосистема
RSA никогда не достигнет быстродействия симметричных криптосистем.
Следует отметить, что малое быстродействие криптосистем RSA ограничивает область их
применения, но не перечеркивает их ценность.

<< Предыдущая

стр. 17
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>