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

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

ОГЛАВЛЕНИЕ

Следующая >>

14-2. Атака Винера на RSA 355

предположений следует существование такого целого А;, ч т о
Ed-kip = 1.
Следовательно,
Е__к\_ )_
(р d\ dip
Поскольку ip ^ N^ получаем, ч т о
\N-ip\ = \p + q-l\ KSVN.

довольно хорошее прибли-
Отсюда можно сделать вывод, ч т о ^
жение в | . Действительно,
Ed-kip - Nk + kip
Ed-Nk
Е^
7V dN dN
3kVN 3k
l-k{N- ip)
^
dVN'
dN dN
Поскольку E < ip^ очевидно, к < d. Кроме того, по предположению
d < jN^. Значит,
Е^
< 2^2*
AT
Поскольку п о д (k^d) = 1, мы видим, что | — подходящая дробь в
разложении дроби ^ в непрерывную. Таким образом, раскладывая
число ^ в непрерывную дробь, можно узнать расшифровывающую
экспоненту, поочередно подставляя знаменатели подходящих дро­
бей в выражение:
(М^У = М (modiV)
А^ля некоторого случайного числа М. Получив равенство, найдем d.
Общее число подходящих дробей, которое нам придется при этом
проверить, оценивается как O(lniV). Таким образом, изложенный
метод дает линейный по сложности алгоритм определения секрет­
ного ключа в системе RSA^ если последний не превосходит ^N^,
В качестве примера рассмотрим модуль RSA^ равный
А = 9449 868410449.
Г
Пусть открытый ключ криптосистемы задан как
^ = 6792 605 526025,
а секретный ключ удовлетворяет неравенству d < ^N'^ ^ 584. Раз­
ложим число а = ^ в непрерывную дробь и проверим знаменатель
356 Глава Ц- Атаки на схемы с открытым ключом

каждой подходящей дроби: не является ли он секретным ключом.
Подходящие дроби разложения а имею вид:
2 3 5 18 23 409 1659
' 3 ' 4' 7' 25' 32' 569' 2308' **
Поочередно проверяя знаменатели, убедимся, что d = 569, т. е. зна­
менатель седьмой подходящей дроби — искомый секретный ключ.


14.3. Решетки и приведенные базисы
Позже в этой главе мы увидим, что приведение базиса решетки дает
инструмент нападения на ряд криптосистем с открытым ключом.
Поэтому здесь дается обзор этой важной области. Прежде всего
необходимо напомнить некоторые сведения из линейной алгебры.
Пусть X = (^1,^27 • • • 5^п) — п-мерный вещественный векторе,
т.е. Xi Е Ш при каждом г. Множество всех таких векторов обо­
значается символом R^. Для пары векторов определено скалярное
произведение:
(ж, у) = Xiyi + Х2У2 + •"+ ХпУп,
являющееся вещественнозначной функцией от двух векторных ар­
гументов. Вероятно Вам известно, что векторы х иу ортогональны
(т. е. пересекаются под прямым углом) тогда и только тогда, когда
{х,у) = 0.
С помощью скалярного произведения можно определить абсолют­
ную величину, или длину, вектора:

Ы\ = \/{х^= ^Jxl+xl-h•••+xl,
Это определение соответствует интуитивному понятию длины, при
котором выполнены следующие свойства:
- неотрицательность: \\х\\ ^ О, причем \\х\\ = О тогда и только
тогда, когда ж = 0;
- неравенство треугольника: любая пара векторов удовлетво­
ряет неравенству:

1к + у||^1к11 +
^Довольно часто (и в этой книге, в частности) векторы записывают в виде столб-

цов I . I. — Прим. перев.
\хп/
14-S. Решетки и приведенные базисы

- пропорциональность: для любого вектора х и числа А G М име­
ет место равенство:
||А:г|| = | А | . | И | .

Множество векторов {bi,... ,Ьт} в R^ называется линейно неза­
висимым^ если уравнение
Aibi + A2b2 Н 1 ^щЬт = О
-
относительно чисел А имеет только нулевое решение. Для линейно
^
независимой системы векторов справедлива оценка: т ^ п.
Имея систему линейно независимых векторов { b i , . . . , 6^} в R^,
можно изучать множество всех их веш;ественных линейных комби­
наций:

V = < Х ^ а А | аг е м 1 .

Такое множество образует векторное подпространство в М^ раз­
мерности ш, а система {bi,.., ^bm} называется базисом этого под­
пространства. Если из векторов базиса составить матрицу 5 , чей
j-ый столбец совпадает с вектором 6^, то подпространство V можно
описать как множество всевозможных произведений матрицы В на
вектора из R^, т.е.
V = {В'х\хе W^}.
Такую матрицу В называют матрицей базиса.
В любом подпространстве V суш;ествует бесконечно много раз­
личных базисов. Как в научных, так и в технических приложениях
довольно часто требуется выбор базиса со специальными свойства­
ми. Одно из полезных свойств — попарная ортогональность базис­
ных элементов:
{bj.bj) = 0 при г 7^ j .
Такие базисы называют ортогональными, К счастью, существует
хорошо известный процесс ортогонализации Грама-Шмидта^ по­
зволяющий по произвольному базису {6i, . . . , bm} построить орто­
гональный {6*, . . . , bj^} с помощью преобразований:


b\ = bi, Hij = у Y для 1 < j < г < m, b* = b i - ^ щ^Ь*.
[b*,b*) j=.
Пусть, например,

bi = ( o ) и b2={\).
Глава 14' Атаки на схемы с открытым ключом

Тогда


поскольку

^^'^ {bl.bl) 4 2*
Теперь (Ь*,Ь2) = О '^^^ ^'^^ построенный базис Грама-Шмидта ор­
?
тогонален.
Решетка очень похожа на векторное подпространство F , о ко­
тором шла речь вьппе, но ее рассматривают не над веш;ественными,
а над целыми числами. Зафиксировав линейно независимую систе­
му векторов {&!,...,6п} в М^, решеткой считают множество всех
целочисленных комбинаций базисных векторов:

L= < Y^aibil ai eZ> = {B'a\ae
22aibi\ aieZ\ Ъ^}.
<г=1 J
В этой ситуации, как и в случае векторных подпространств, век­
торы Ь{ называют базисными векторами решетки, а матрицу В —
базисной матрицей. Чтобы понять, почему множество L называют
именно решеткой, рассмотрим L, порожденную парой векторов

bi = (o) и Ь2=(}).
Множество L состоит из всех векторов вида



Если изобразить точки с такими координатами на координатной
плоскости, то можно легко увидеть, что они будут располагаться в
узлах сетки, или решетки.
Решетки — дискретный аналог векторных пространств. Ввиду
их дискретности корректно определен наименьший элемент данной
решетки, например, как ненулевой вектор с наименьшей длинной.
Множество трудных вычислительных задач, особенно тех, которые
возникают в криптографии, можно свести к нахождению наимень­
шего вектора в решетке. Далее мы разберем некоторые из приложе­
ний этой теории. Поиск наименьшего ненулевого вектора в обш;ей
многомерной решетке считается трудной задачей. Для маломерных
решеток она не представляет серьезных проблем, чем мы и будем
пользоваться.
Вернемся к обш;ей теории решеток. Как и в случае векторных
пространств, имея какой-то базис решетки, можно задаться вопро-
Ц'З. Решетки и приведенные базисы

сом о поиске лучшего. Пусть В — матрица базиса решетки L. Един­
ственный способ получения другой матрицы базиса В^ состоит в
умножении В на унимодулярную целочисленную матрицу U:
В' ^ви,
т. е. целочисленную матрицу, определитель которой равен плюс или
минус единице: det t/ = ± 1 . Следовательно, модуль определителя
матрицы базиса является инвариантом решетки, т. е. не зависит от
выбора базиса. Поэтому уместен термин дискриминант решетки^
который по матрице базиса определяется как
А= y/\det{B^B)\.
Если L — решетка полного ранга, т.е. В — квадратная матрица, то
А = |detB|.
Возникает вопрос о существовании ортогонального базиса в данной
решетке L. В общем случае ответ отрицателен. Если внимательно
посмотреть на процесс ортогонализации Грама-Шмидта, то легко
увидеть, что если начать даже с целочисленного базиса, коэффици­
енты /jLij почти никогда не будут целыми числами. Следовательно,
полученный таким способом набор ортогональных векторов будет
образовывать базис векторного подпространства F , но решетка, ко­
торую он порождает, будет отлична от исходной. Дело в том, что
переходя от одного базиса решетки к другому, мы не можем исполь­
зовать нецелые коэффициенты. Тем не менее, можно попытаться
выбрать новый базис решетки, который будет «близок» к ортого­
нальному, т.е.
IWjl ^ - для 1 ^ j < г ^ п .

Эти соображения натолкнули Ленстру, Ленстру и Ловаса на опреде­
ление приведенного базиса решетки, который часто называют LLL-
приведенным базисом в честь изобретателей.

Определение 14.1. Базис {bi, . . . , bm} решетки называют LLL-
приведенным^ если для соответствующего ортогонализованного ба­
зиса Грама-Шмидта {б^? • • • ? Ь^} выполнены условия:

Iwjl ^ 2 '^•^^ 1 < i < г ^ т , (14.1)

1|Ьг*11' ^ ( i - / ^ L ) \\bU\\' Д Я К г ^ m.
Л (14.2)
Глава 14- Атаки на схемы с открытым ключом

Поистине удивительно, что
- LLL-приведенный базис можно найти за полиномиальное вре­
мя (метод приведения описан ниже);
- первый вектор приведенного базиса самый короткий — фак­
тически, он близок к наименьшему ненулевому вектору, в том
смысле, что
||6i||^2=^||a;|| Va:GL\{0};
- \\bi\\ < 2 т Д т .
-1
Константа 2 ^ ˜ , появляющаяся во втором свойстве, возникает из-за
наиболее неблагоприятного случая. Практически, после применения
LLL-алгоритма к базису большинства решеток разумной размерно­
сти получается LLL-приведенный базис, первый вектор которого
имеет наименьшую из возможных положительных длин в решетке.
LLL-алгоритм работает следующим образом. Мы храним копию
как текущего базиса решетки S , так и ассоциированного с ним бази­
са Грама-Шмидта Б*. В каждый момент времени исследуется фик­
сированный столбец с номером /с, начиная с А = 2.
;
- Если условие (14.1) не выполнено А,ЛЯ fXkj при 1 ^ j < А;, то мы
меняем матрицу базиса так, чтобы оно стало верным.
- Если условие (14.2) не выполнено р^ля столбцов с номерами к
и А — 1, то переставляем эти столбцы и уменьшаем значение
;
к на единицу (если, конечно, к ф 2). Если же условие (14.2)
выполняется, мы увеличиваем значение к на единицу.
В какой-то момент мы получим А = т , и алгоритм остановится.
;
Можно показать, что число шагов алгоритма, при котором пони­
жается номер А:, ограничено. Это гарантирует, что алгоритм оста­
навливается. Ясно, что в результате работы описанного алгоритма
получится LLL-приведенный базис.
В качестве примера рассмотрим базис двумерной решетки в М^,
с которым мы уже встречались:

^. = (о). <- = i\)-
Соответствующий ортогональный базис Грама-Шмидта уже вычислен:

ч = ©\ .
'2 г.*
ч = /0^
(»).
Но эти векторы не образуют базиса соответствующей решетки, по­
скольку не могут быть получены из {61,62} унимодулярным пре­
образованием.
14'S, Решетки и приведенные базисы 361

Применяем LLL-алгоритм с к = 2. Видно, что первое условие
(14.1) выполнено, поскольку /i2,i =^ ^' Однако второе соотношение
(14.2) ложно, т.к.

к*1|2 ^ (^ ..2 \ ||L*||2 1


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

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

ОГЛАВЛЕНИЕ

Следующая >>