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

стр. 30
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

ивен во многих приложениях. Кроме того, в следующих главах мы
продемонстрируем, что алгоритм RSA в том виде, в котором мы
его представили, не может устоять против атак с выбором шифро-
текста.
В криптосистемах с открытым ключом атакующий всегда имеет
возможность шифровать свои сообщения. Значит, он способен при­
менять атаку с выбором открытого текста. RSA криптостоек про­
тив таких атак, если принять во внимание наше слабое определение
стойкости и верить в трудность решения задачи RSA. ]\ля аргумен­
тации этого заявления нужно использовать прием сведения одной за­
дачи к другой, изложенный в предыдущей главе. В данной ситуации
доказательство безопасности алгоритма RSA довольно тривиально,
но мы рассмотрим этот вопрос подробно, т. к. соответствующие ар­
гументы будут применяться снова и снова в последующих главах.

Лемма 7.5. Если задача RSA является трудноразрешимой, то кри­
птосистема RSA вычислительно защищена от атак с выбором от­
крытого текста в том смысле, что атакующий не в состоянии кор­
ректно восстановить открытый текст, имея лишь шифротекст.
Доказательство. Разработаем алгоритм решения задачи RSA^
основываясь на алгоритме взлома одноименной криптосистемы. Сде­
лав это, мы покажем, что взлом криптосистемы не сложнее задачи
RSA.
Напомним, что в задаче RSA дано число iV, имеющее два не­
известных простых делителя р и q^ элементы Е^ Y Е (Z/iVZ)* и
требуется найти такой элемент х^ что х^ (modiV) = Y. С помощью
оракула дешифруем сообщение С = Y и получим соответствующий
открытый текст т , удовлетворяющий, по определению, соотноше­
нию
т^ (modN) =C = Y.
Отсюда видно, что взломав криптосистему, мы сможем решить за­
дачу RSA. Ш

7.3.2. С е к р е т н а я э к с п о н е н т а и п р о б л е м а
факторизации
Пока нам не ясно, является ли взлом криптосистемы RSA^ в смысле
обращения функции RSA^ эквивалентным проблеме факторизации.
l.S. RSA 195

решив которую, можно найти секретный ключ d по открытой ин­
формации о N и Е. Продемонстрируем взаимосвязь этих задач.

Лемма 7.6..Если известна расшифровывающая экспонента d алго­
ритма RSA^ соответствуюш;ая открытому ключу (ЛГ, Е)^ то число N
можно эффективно разложить на множители.
Доказательство. Напомним, что при некотором целом s имеет
место равенство
Ed-1 = s{p-l){q-l).
Возьмем произвольное целое число X ^ 0. Тогда
j^Ed-i ^ 1 (modiV).

Вычисляем квадратный корень Ух по модулю N:
Ed-l
Yi = Vx^rf-i = Х - т - (modTV),
что можно сделать, поскольку Ed — 1 известно и четно. Приходим
к тождеству
F i ^ - l ^ O (modiV),
которое можно использовать ^\ля определения делителей числа N с
помощью вычисления ПОД (Yi — 1,^). Однако это будет работать,
только если Y\ ф ± 1 (modiV).
Предположим, что нам не повезло и Fi — ± 1 (modiV). Если Y\ =
— —1 (modiV), вернемся к началу и выберем другое число X. Если
Y\ — \ (modTV), то можно взять еш;е один квадратный корень
.ЕР-\
У^ = ^ = Х-т- (modiV).
Опять получаем
Yi - l = Yi-l = 0 (modiV),
откуда Н0Д(У2 — ^•,Ю — делитель числа N. К сожалению, здесь
тоже может оказаться, что Y2 = ±1 (modTV). Тогда придется по­
вторить все снова.
Алгоритм необходимо повторять до тех пор, пока мы не разло­
жим N на множители или не придем к числу {ED — 1)/2*, которое
уже не будет делиться на 2. В последнем случае нам придется вер­
нуться к началу алгоритма, выбрать новое случайное значение X и
все повторить. •
Алгоритм, приведенный в этом доказательстве, — типичный
пример алгоритма Лас-Вегаса, вероятностного по своей природе,
196 Глава 7. Основные алгоритмы шифрования с открытым ключом

которая проявляется в процессе работы. Но если уж ответ отыщет­
ся, то он обязательно будет верным.
Разберем небольшой пример, иллюстрирующий изложенный ме­
тод. Рассмотрим следующие входные данные задачи RSA:
ЛГ = 1441499, Е = 17 и d = 507905.
Напомним, что мы предполагаем известной расшифровывающую
экспоненту с/, которая обычно хранится в секрете. Опираясь на пре­
дыдущий алгоритм, найдем делители числа N. Положим
Ti = ( ? ; d - l ) / 2 = 4317192,
X = 2.
Для вычисления Yi, сделаем преобразования:
у^ ^ ; ^ ( ? ; d - i ) / 2 ^ 2 ^ 1 = 1 (mod iV).
Поскольку Yi оказался равным 1, нам нужно взять
Т2 = Ti/2 = {Ed - 1)/4 = 2 158 596 и Y2 = 2^\
Теперь
У2 = х(^'^-1)/4 = 2^2 = 1 (modiV).

Снова нужно повторять предыдущие шаги, что приведет нас к
Тз = {Ed-1)/8 = 1079 298
и
Уз = Х(^^-^)/^ = 2^' = 119 533 (modAT).
Отсюда,
Yi-1 = (Уз - 1)(П + 1) = о (modiV),
И мы можем найти простой делитель числа N^ вычислив
Я0Д{Уз-1,Ю -1423.

7.3.3. З н а ч е н и е ф у н к ц и и Э й л е р а ^{N) и п р о б л е м а
факторизации
Как мы убедились, информация о секретной экспоненте d позволяет
найти простой делитель числа N, Здесь мы покажем, как знание
значения функции Эйлера Ф = <p{N) помогает решить ту же задачу.

Лемма 7.7. Значение Ф = ^{N) позволяет эффективно разложить
число N на множители.
1.3. RSA

Доказательство. Имеем
Ф = {р-1){д-1)=М-(р + д) + 1.
Следовательно, положив S = N + 1 — Ф, мы получим
S = p + q,
Нам нужно определить числа р или д, опираясь на их сумму S и
произведение 7V. Рассмотрим многочлен
f{X) = {X -р){Х -q)=X^-SX-hN.
Теперь можно найти как р, так и д, решая квадратное уравнение
f{X) = О стандартным образом:
S + VS^- 4N S˜VS^- Ш
^= 2 ' ^= 2 •

В качестве примера рассмотрим открытый модуль 7V = 18 923
криптосистемы RSA и предположим, что нам известно Ф = (p{N) =
= 18648. Вычисляем
S = p-\-q = N-\-l-Ф = 276.
Соответствующий многочлен имеет вид:
f{X) = Х'^ - SX -h N = Х^ - 276Х + 18 923,
а его корни — р = 149, q = 127.

7.3.4. Р а з д е л е н н ы й м о д у л ь
Поскольку арифметика остатков — дорогое удовольствие с точки
зрения компьютера, весьма заманчиво разработать систему шифро­
вания, в которой пользователи разделяют общий модуль 7V, но при­
меняют различные шифрующие и расшифровывающие экспоненты
(Ei^di), Одна из причин, побуждающая это делать, — ускорить ал­
горитмы шифрования и расшифровывания в аппаратных средствах,
специально настроенных на определенный модуль N, Однако это не­
удачная идея, поскольку пасует перед двумя типами нападающих:
внутреннего, т. е. законного пользователя системы, и внешнего.
Предположим, что нападающим является один из законных кли­
ентов криптосистемы, скажем пользователь номер 1. Он может най­
ти значение расшифровывающей экспоненты, которую хранит в се­
крете пользователь номер 2, а именно б?2- Сначала он вычисляет р
и q с помощью алгоритма из доказательства леммы 7.6, что он в
198 Глава 7. Основные алгоритмы шифрования с открытым ключом

состоянии сделать, зная свою расшифровывающая экспоненту di.
Затем злоумыышенник находит (p{N) = {р — l){q — I) и, наконец,
раскрывает значение ^2 по формуле

d2 = — {mod ip{N)).
h,2

Предположим теперь, что атакующий не принадлежит к пользо­
вателям криптосистемы, использующим общий модуль. Допустим,
Алиса посылает одно и то же сообщение т двум клиентам крипто­
системы, открытые ключи которых
{N,Ei) и {N,E2).
Ева, нападающая извне, видит зашифрованные сообщения Ci и С2,
где
Ci - т^' (modTV), С2 = т^^ (modTV).
Она может вычислить
Ti = Е^^ (mod?;2), Т2 - {TiEi - 1)/^2
и восстановить сообщение т по следующей схеме:




=i rn} = т.
Рассмотрим пример внешней атаки в случае
N =^Ni=N2 = l8923, El = 11 и ^2 = 5.
Предположим, что перехвачены шифротексты
Ci = 1514 и С2 = 8 189,
соответствующие одному открытому тексту т. Тогда Ева вычисля­
ет Ti = 1 и Т2 = 2, после чего раскрывает исходную информацию:
m - С^'С:^^^ - 100 (modiV).

7.3.5. И с п о л ь з о в а н и е м а л ы х хпифрующих
экспонент
Иногда в криптосистемах RSA с целью экономии затрат на шифро­
вание используются небольшие шифрующие экспоненты Е, Пока­
жем, что это тоже создает дополнительные проблемы, связанные с
l.S, RSA I

криптостойкостью. Предположим, что у нас есть три пользователя
с различными модулями шифрования
iVi, N2 и Ns
и одной шифрующей экспонентой Е = 3. Пусть некто посылает
им одно сообщение т , зашифрованное тремя разными открытыми
ключами. Нападающий видит три криптограммы:
Ci = m ^ (modATi),
С2 = т^ (modiV2),
Сз = т^ (mod TVs)
и с помощью китайской теоремы об остатках находит решение си­
стемы
{X = Ci (modiV^)l г - 1 , 2 , 3 }
в виде
X = т^ {modNiN2Ns).
Но поскольку 7п^ < NiN2Ns^ целые числа X и т^ должны совпа­
дать. Поэтому, вычисляя кубический корень из X, мы раскрываем
сообщение.
Пусть, например,
Ni = 323, N2 = 299, Ns = 341
и Ева перехватывает сообщения
Ci = 50, С2 = 299 и Сз = 1,
Чтобы восстановить исходное сообщение т , Ева находит решение
системы
X = 300 763 {modNiN2Ns),
после чего извлекает обычный кубический корень
т = Х^/^ = 67.
Обе атаки, о которых мы сейчас рассказали, представляют не­
сомненный интерес, поскольку позволяют раскрыть текст, не ре­
шая сложную задачу разложения на множители. Возможность та­
ких атак служит свидетельством (хотя и слабым) в пользу того,
что вскрытие криптосистемы RSA более легкая задача, чем пробле­
ма факторизации. Однако наиболее важный вывод, который следует
извлечь из этих атак, заключается в необходимости дополнять ори­
гинальные сообщения случайными цифрами перед шифрованием.
Глава 7. Основные алгоритмы шифрования с открытым ключом

Такая предосторожность сильно снизит вероятность шифрования
одного и того же сообщения разными пользователями. Кроме того,
следует избегать небольших шифруюш;их экспонент. Сейчас обыч­
но выбирают ?? = 65 537. Однако при использовании RSA р^ля элек­
тронной цифровой подписи (см. ниже) можно беспроблемно брать и
небольшие шифруюп1;ие экспоненты.


7.4. Криптосистема Эль-Гамаль
Простейший алгоритм шифрования, основываюш;ийся на дискрет­
ном логарифмировании, — это криптосистема Эль-Гамаль. Сейчас
мы опишем шифрование в системе Эль-Гамаль, использующее конеч­
ные поля. Суш;ествует аналогичная система эллиптических кривых.
Ее продумывание мы оставим в качестве упражнения.
В отличие от RSA^ в алгоритме Эль-Гамаль суш;ествуют некото­
рые открытые параметры, которые могут быть использованы боль­
шим числом пользователей. Они называются параметрами домена
и выглядят следуюш;им образом:
- Р — «большое простое число», т. е. число, насчитывающее око­
ло 1024 битов, такое, что Р — 1 делится на другое, «среднее
простое число» Q, лежащее неподалеку от 2^^^.
- G — элемент мультипликативной группы поля Fp, порядок
которой, как мы знаем, делится на Q, причем
G(^-i)/«(modP)7^1.

Все параметры домена, т. е. Р , Q и G, выбираются таким образом,
чтобы элемент G^^˜^^'^ был образующей абелевой группы А поряд­
ка Q, Информация об этой группе открыта и используется большим
числом пользователей.
После выбора параметров домена определяют открытый и сек­
ретный ключи. Секретным ключом может априори быть любое на­
туральное число ж, а открытый ключ получается по следующей фор­
муле:
Я ^ С ^ (modP).
Обратите внимание на то, что каждый из пользователей RSA дол­
жен генерировать два больших простых числа р^ля определения ключе­
вой пары, что является довольно громоздкой задачей, а в систе­
ме Эль-Гамаль рля построения ключевой пары достаточно найти
какое-нибудь случайное число и сделать сравнительно несложные
вычисления в арифметике остатков.
Ц, Криптосистема Эль-Гамалъ 201

Сообщение в этой системе представляется ненулевым элементом
поля т G Fp. Для его шифрования поступают следующим образом:

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

стр. 30
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>