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

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

ОГЛАВЛЕНИЕ

Следующая >>

Поэтому нам надо переставить вектора исходного базиса и вновь
применить процесс ортогонализации Грама-Шмидта. Новый базис
решетки имеет вид:

6l=(l), Ь2=(о),
а его ортогонализация записывается как

4 = 0)- ч-(-!)•
Снова проверяем первое условие. На этот раз //2,1 = 1^ ^то проти­
воречит (14.1). Чтобы его подправить, вычтем bi из ^2 и получим
М2,1 = 0. Теперь базис решетки выглядит как

.. = (}). ».=(_;),
причем соответствуюш;ий базис Грама-Шмидта совпадает с ним:

4 = (J). ^ = (-1)-
Проверяем второе условие. Имеем



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



является приведенным базисом решетки L.
Закончим введение в теорию решеток замечанием, что суш;еству-
ет непосредственная связь между непрерывными дробями и приве­
дением решеток. Разложение веш;ественного числа а в непрерывную
дробь позволяет найти такие целые числа р и g с не очень большим д,
что величина
\qa - р\
будет достаточно маленькой. Аналогичный эффект может быть до­
стигнут, если применить LLL-алгоритм к решетке L, порожденной
362 Глава Ц- Атаки на схемы с открытым ключом

столбцами матрицы



с некоторой константой С. Он обеспечивается наличием «кратчай­
шего» вектора

Ч
C{qa-p)

в решетке L. Таким образом, LLL-алгоритм можно рассматривать
как обобщение непрерывных дробей на многомерный случай.


14.4. Атаки на RSA, основанные на решетках
в этом параграфе мы узнаем, как можно использовать решетки
в атаках на криптосистемы, если нападающему известна какая-то
дополнительная информация о них. Эти атаки, по существу, ана­
логичны атаке Винера, рассмотренной ранее, которая взламывает
RSA при условии, что нападающий осведомлен о небольшом раз­
мере расшифровывающей экспоненты. Многие работы на эту тему
инициированы начальной работой Копперсмита, которая позже бы­
ла упрощена Хоугрэйв-Грэхемом.
В основе атаки лежит один из способов решения следующей за­
дачи. Пусть дан многочлен
F{x) = Fo-\-Fix + '" + + х^
FD-IX^˜^

степени D с целыми коэффициентами, причем известно, что он обла­
дает малым корнем XQ ПО модулю N (т.е. F{xo) = О (modAT)), на­
пример, \хо\ < N^. Можно ли эффективно найти этот корень? От­
вет на этот вопрос неожиданно положителен и влечет множество
интересных следствий для криптографии.
Идея решения задачи состоит в том, чтобы найти многочлен
h{x) G Z[rr], имеющий тот же корень по модулю АГ, что и F{x), но с
малой нормой, т.е. число
deg/i

= E^i
г!
г=0
ДОЛЖНО быть небольшим. Если такой многочлен h{x) найден, то
можно применить следующую лемму.
14'4- Атаки на RSA, основанные на решетках 363

Л е м м а 14.2. Пусть h{x) G Ъ[х] — многочлен, степень которого не
превосходит п^ а. N и X — натуральные числа. Предположим, что

\\НхХ)\\ < ^ .

Тогда если |а:о| < X и /i(^o) = О (modJV), то равенство h(x{)) — О
имеет место и в кольце целых чисел, а не только в кольце вычетов.
Вернемся к исходному многочлену F{pc) степени D и заметим,
что если ^(жо) = о (modiV), то {F{xu)f = О (modiV'=). Более ТОГО,
если мы возьмем натуральное число М и рассмотрим


ТО

9u,vixo) = OimodN^)
ДЛЯ всех O ^ U < D H O ^ V ^ M . Попытаемся теперь найти такие
аиу G Z, при которых многочлен
м
^(^) = X l X l ^uy9u,v{x)
u^ov=o
с фиксированным М будет удовлетворять предположениям преды-
дуп];ей леммы.
Иначе говоря, мы хотим найти такие целые числа ацуч при ко­
торых норма многочлена h{x) подчиняется неравенству



где
м
h{xX) = ^ ^аиу9иу{хХ),
и^о v=o
Задача о поиске таких коэффициентов называется задачей миними­
зации, и ее можно решить с помош;ью приведения базиса решетки,
что мы сейчас продемонстрируем на простом примере.
Пусть
F{x) =х'^ -\-Ax-\-B,
Найдем такой жо, что
F{xo) = 0 (mod AT).
364 Глава Ц- Атаки на схемы с открытым ключом

Положим в описанной выше конструкции М = 2 и вычислим
доМ^Х) = N\
9,,о{хХ) = XN^x,
go,i{xX) = BN + AXNx + NX^x'^,
gi,i{xX) = BNXx + ANX^x'^ + NX^x^,
5о,2(жХ) = B^ + 2BAXx + {A^ + 2B)X^x'^ + 2AX^x^ + X'^x'^,
9i,2{xX) = B^Xx + 2BAX^x'^ + {A^ + 2B)X^x^ + 2AX'^x^ + X^x^.
Поищем линейную комбинацию этих шести многочленов с наимень­
шими коэффициентами результируюш;его многочлена. Фактически
нам нужно найти наименьший вектор в решетке, порожденной столб­
цами матрицы, которые образованы коэффициентами этих много­
членов:
О BN О В^ п \
о
О XN^ AXN BNX 2АВХ
о О NX^ ANX^ {А^ + 2В)Х^ 2АВХ'^
С=
о О О NX^ 2АХ^
о 0 0 0 X'^ 2АХ^
Х^
0 0 0 0

Определитель этой матрицы равен
d e t C = iV^X^^
и применяя к ней LLL-алгоритм, мы получим новую матрицу базиса
С, первый столбец которой


Ci =




будет удовлетворять неравенству
II4II <2t(detC)^ =2iiVxt.
Следовательно, для многочлена
Ф) = c'i,i5o,o(a;) + c^,igi,oi^) + ••• + 4д</1,2(ж)
выполнено неравенство
||/г(жХ)|| ^22NXl.
14-4' Атаки на RSA, основанные на решетках 365

Чтобы воспользоваться леммой 14.2, нам необходимо потребовать:

21ЛГХ1 < ^.

Значит, определяя целый корень многочлена h{x), мы найдем малый
корень жо многочлена F{x) по модулю iST, если
NI
|а;о|^Х-—г.
485
В частности, метод будет работать, когда |жо| ^ N^^^^.
Аналогичные рассуждения можно применить к любому много­
члену степени D и получить следующую теорему:

Т е о р е м а 14.3. ( К о п п е р с м и т . ) Пусть / G Z[x] — приведенный
многочлен^ степени D, а 7V — натуральное число. Если у многочлена
/ по модулю N есть корень жо, удовлетворяющий неравенству |а;о| ^
1
X = N D-e ^ ТО этот корень можно найти за полиномиальное от 1пЛ^
и J время при фиксированном значении D.
Сформулируем аналог леммы 14.2 р^ля многочлена от двух пере­
менных.

Л е м м а 14.4. Пусть h{x^ у) G Z[a;, у] — сумма не более чем W моно­
мов и
(а) h{xO',yo) = О (modTV^) для некоторых натуральных чисел N и
Е, причем целые хо и уо подчиняются неравенствам: |а;о| < ^
и |уо| <Y,
(б) | | М ^ Х , у У ) | | < ^ .
Тогда соотношение h{xo^yo) = О имеет место и в кольце Z.
А вот аналог теоремы 14.3 в случае многочленов от двух пере­
менных носит эвристический характер.
Теперь будем применять теорему 14.3 и ее обобщения для опи­
сания атак, направленных на RSA,

14.4.1. Атака Хастада
В главе 7 мы рассмотрели следующую атаку на систему RSA. Пусть
даны три открытых ключа {Ni^Ei) с одной и той же шифрующей
экспонентой Ei = 3. Если пользователь посылает одно сообщение.
^Приведенным называется многочлен с единичным старшим коэффициентом.
Прим. перев.
366 Глава 14- Атаки на схемы с открытым ключом

зашифрованное этими ключами, то нападающий легко дешифрует
сообщение, применив китайскую теорему об остатках.
Предположим теперь, что мы приняли меры против такой ата­
ки, добавив к сообщению т перед шифрованием некоторые специ­
фические для пользователя данные. Пусть, например, шифротекст,
отправляемый г-му пользователю имеет вид
Ci = {i'2" + mf {modNi).
Но и здесь сообщение все еще можно дешифровать, использовав ме­
тод, изобретенный Хастадом. Атака имеет непосредственное отно­
шение к теореме Копперсмита, т. к. сценарий атаки с К пользова­
телями и шифрующей экспонентои Е можно интерпретировать как
набор из К многочленов степени Е:
дг{х) = {i'2" + xf -Сг, 1 ^ г ^ К,
При этом нам известно, что существует такое т, что
gi{m) = О (modiV^).
Наша цель — найти т. Можно считать, что т меньше каждого
из модулей Ni. Положив N = NiN2- - • Nj^^ с помощью китайской
теоремы об остатках можно найти такие Г^, что многочлен
к
9{^) = ^Tigi{x)
г=1

будет удовлетворять соотношению
д{т) = 0 (modAT).
Теперь, если у нас есть достаточно много шифротекстов, т.е. К > Е^
то опираясь на теорему 14.3, мы узнаем т за полиномиальное время.
Действительно, д — приведенный многочлен степени Е и
т < minNi < N^'^ < N^'^.
г


14.4.2. А т а к а Ф р а н к л и н а - Р е й т е р а и о б о б щ е н и е
Копперсмита
Предположим, что у нас есть открытый ключ RSA^ принадлежаш;ий
Алисе. Атака Франклина-Рейтера применяется в следуюп1;ей ситу­
ации. Боб хочет отправить Алисе два шифрованных сообш;ения mi
и т 2 , связанных друг с другом с помош;ью следуюп];его открытого
многочлена:
^ 2 — / ( ^ i ) (modА/').
14'4- Атаки на RSA, основанные на решетках 367

По соответствующим шифротекстам С\ и С2 нападающий имеет
хорошие шансы раскрыть сообщения mi и т 2 при любой небольшой
шифрующей экспоненте Е. Атака наиболее проста, если
f = Ах + В и ?" = 3,
причем А VL В фиксированы и известны атакующему. Нападающий
знает, что т 2 — корень по модулю N многочленов
дг{х)=х^-С2 и д2{х) = {f{x)f - С^
Поэтому линейная функция х — 7П2 делит как gi{x)^ так и 92{х).
Найдем наибольший общий делитель многочленов gi{x) и 52(^)-
Строго говоря, это невозможно сделать в общей ситуации, посколь­
ку кольцо {Z/NZ)[x] не является евклидовым. Однако если алгоритм
Евклида при вычислении НОД (^i, ^2) нарушается, то мы определим
множители N и вскроем секретный ключ Алисы. Можно показать,
что в случае
f = Ах + В и Е = 3
искомый наибольший общий делитель (если таковой существует)
должен быть линейным множителем многочлена х — т 2 , т. е. совпа­
дать с ним. Значит, нападающий найдет т 2 , а затем mi.
Обобщение Копперсмита атаки Франклина и Рейтера строит­
ся по пути, на котором можно получить дополнительный результат
из атаки Хастада. Предположим, что сообщение т перед шифро­
ванием пополняется некоторыми случайными данными. Например,
если N — п-битовый модуль RSA, a m — А;-битовое сообщение, то
можно добавить п — к случайных битов либо в начало, либо в конец
сообщения. Пусть
ш' = 2''˜^т + г,

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

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

ОГЛАВЛЕНИЕ

Следующая >>