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

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

ОГЛАВЛЕНИЕ

Следующая >>

предметов. Обычно последовательность весов содержит 250 значе­
ний. Параметры тип криптосистемы выбираются из 400-битовых
чисел. Но даже увеличив параметры, мы не получим стойкой кри­
птосистемы, поскольку она может быть взломана с помощью при­
веденных базисов решеток, используя метод, который мы сейчас
объясним.
Определим плотность множества весов {wi,.., ,Wn} в задаче о
рюкзаке формулой:
^^ ^
max{Iog2 гУг| 1 ^ i ^ п}
Покажем, что задача о рюкзаке с небольшой плотностью легко ре­
шается с помощью приведения базисов. Так как конструкция Мерк-
ля - Хеллмана всегда дает последовательность весов с низкой плот­
ностью, то соответствующую криптосистему несложно взломать.
Итак, пусть {Wi, . . . , WN} — веса предметов и S — оконча­
тельный вес рюкзака, который нужно получить. Рассмотрим N + 1-
мерную решетку L, порожденную столбцами матрицы
/1 О О ... О 1/2 \
1/2
О О
1 О
1/2
О
О 1
О


1 1/2
0 0 0
V Wi W2 Ws WN S /
Предположим, что строка бит (bi,. Ьм) — решение нашей задачи.
Вектор
у = А' X
при X — (bi, . . . , бдг, — 1) принадлежит решетке. Его координаты
Глава 16. Теоретическая сложность

имеют вид
bi-\, l^i^N,
2'
Уг =
i=N +L
О,
Значит, вектор у имеет очень маленькую длину, поскольку


ФУ? + • • • + У%^1 =
Решетка, построенная по задаче о рюкзаке с низкой плотностью,
как правило, обладает относительно большим детерминантом. По­
этому у — хороший кандидат на наименьший вектор в решетке.
Применив LLL-алгоритм к матрице А, получим матрицу А' приве­
денного базиса. Ее первый столбец А[ тоже обычно имеет наимень­
шую длину. Следовательно, вероятность равенства А^ = у весьма
высока. Получив у, мы сможем найти х и решить исходную задачу
о рюкзаке.
В качестве простого примера дешифруем сообщение, приведен­
ное на стр.400, т.е. найдем последовательность битов {6^}, удовле-
творяюшую соотношению

bi62 + ЬзЭЗ + 6з81 + ^488 + ЬаЮг + Ье37 = 174.

Сформируем матрицу
0 0 0 0 0
/1 1/2 \
1 1/2
0 0 0 0 0
1
0 0 0 0 0 1/2
1
0 0 0 0 0 1/2
А=
1
0 0 0 0 0 1/2
1 1/2
0 0 0 0 0
\ 62 93 81 88 102 37 174 /
Применив к ней LLL-алгоритм, построим новый базис решетки с
матрицей
1 -2 2 3 2 0\
/
0 -2 -1 -2 0
3
-2
1 2 -1 20
^=
'i 1 -2 0 -1 -2 -2
1 0 2 -3 04
1 0 -2 1 2 01
-2 0 0 -2 2 /
0

16.3. Битовая стойкость 403

Обозначим ее первый столбец через у.
\
/


У=2



И найдем х по формуле
/ о\
-1
-1
1
х = А-^у = ^\ О
О
О
V 1/
Таким образом, последовательность битов
(Ьь ^2, 6з, 64, Ьб, 6б) = (О, 1, 1, О, О, 0)
является решением задачи о рюкзаке и совпадает с первым блоком
открытого текста.


16.3. Битовая стойкость

Ранее (см. стр. 393) мы ввели понятие проблемы выбора как задачи
с односложным ответом: «да» или «нет». Мы показали, что некото­
рые другие задачи, например, задача о рюкзаке, сводится к такой
проблеме. Аналогичная ситуация возникает в криптографии, где хо­
телось бы знать, является ли задача вычисления одного бита сооб­
щения столь же сложной, как и задача вычисления всего сообщения.
Предположим, что используется Дб'Л-функция
x^Y = х^ (modN).
Может возникнуть ситуация, когда противника волнует лишь вы­
числение В = X (mod 2), а не полное восстановление х. Нам хотелось
бы, чтобы решение этого уравнения было бы сравнимо по сложности
с полным восстановлением сообщения. Другими словами, нам нужно
исследовать так называемую битовую стойкость функции RSA.
Легко убедиться, что битовая стойкость тесно связана с семан­
тической: если нападающий сможет определить четность открыто
Глава 16. Теоретическая сложность

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

Определение 16.5. Пусть / : S • Г — одностороннее отобра­
жение конечных множеств S иТ^ а. В : S • {О? 1} — булева функ­
ция (называемая предикатом). Предикат В{х) называется сильным
для / , если по данному х Е S значение В{х) вычисляется легко, а по
f{x) — очень трудно.
Один из способов проверки этого свойства предиката В в отно­
шении односторонней функции / заключается в том, чтобы пред­
положить существование оракула, вычисляющего В{х) по данному
элементу /(ж), и показать, что соответствующий оракул фактиче­
ски обращает функцию / .
Понятие fe-битового предиката и сильного /с-предиката опреде­
ляется аналогично, только значения он принимает в строках битов
длины А;, а не 1, как это было в предыдущем определении. Мы хо­
тели бы показать, что различные предикаты, которые можно опре­
делить для полезной с точки зрения криптографии односторонней
функции / , фактически являются сильными.

1 6 . 3 . 1 . Сильные п р е д и к а т ы для д и с к р е т н ы х
логарифмов
Пусть А — конечная абелева группа простого порядка Q, порожден­
ная элементом G, Рассмотрим предикат
В2 : X • X ( m o d 2)

и докажем следующую теорему.

Теорема 16.6. Предикат В2 является сильным А^ЛЯ функции х ь^

Доказательство. Символом 0{Н^ G) обозначим оракула, опреде­
ляющего наименьший значащий бит дискретного логарифма от Н
по основанию G, т.е. вычисляющего В2{х)^ где х = logQH. Пока­
жем, как использовать О для решения проблемы дискретного лога­
рифмирования.
Пусть дано значение Н = G^, Вычислим Т = ^ (modQ) и по­
ложим У = О, Z = 1. Теперь, пока Н не станет равным 1, будем
осуществлять следующие шаги:
- B= 0{H,G);
16.3. Битовая стойкость

- если 5 = 1, то положим Y = Y + ZHH = ^;
- переопределим Н = Н^ и Z = 2 • Z.
Как только Н станет равным 1, мы получим, что У = log^^ Н, Ш
Проследим за работой алгоритма на примере, взяв элемент G =
64 G Feo? порядка Q = 111. Предположим, что нам нужно вычи­
слить log64 56. Руководствуясь алгоритмом из доказательства тео­
ремы, заполняем табл.16.1.
Таблица 16.1. Таблица промежуточных значений алгоритма вычисления
дискретного логарифма
0{H,G) Z
Я Y
0
56 1 0
451 1 2 2
1
201 4 6
0
288 6
8
1 22
100 16
454 22
0 32
86
64 1 64

Можно убедиться в верности найденного решения, проверив равен­
ство:
64^^ = 56 (mod 607).

16.3.2. Сильные п р е д и к а т ы для з а д а ч и RSA
Задача RSA^ а именно, уравнение С = т^ (mod JV), обладает следу­
ющими сильными предикатами:
- Bi{m) = т (mod2);
- Bh{m) = О, если ш < у , В^{т) = 1 в противном случае;
- Bk{m) = т (mod2^), где к = O(lnlniV).
Обозначим соответствующие оракулы через Oi{C,N), Oh{C^N) и
Ok{C,N), Мы не будем исследовать последний из них, но отметим,
что первые два взаимосвязаны:
Oh{C,N)=Oi{C-2^ (modiV),7V),
Oi{C,N)=Oh{C-2-^ (modiV),iV).
Покажем, как используя оракулы Од и Oi, можно обратить функ­
цию RSA при помощи алгоритма, основанного на стандартном дво­
ичном поиске. Положим Y = C^L^OHH = N, Затем, до тех пор,
пока iJ — L > 1, делаем следующее:
Глава 16. Теоретическая слооюность

- B = Oh{Y,N);
- У = У - 2 ^ (modTV);
- М = {Н + L)/2;
- если В = 1^ то положим L = М; в противном случае положим
Н = М.
При выходе из цикла значение [if J должно совпадать с прообразом
С относительно функции RSA,
Разберем пример, в котором N = 10 403 и Е = 7 — открытая ин­
формация, а мы хотим найти прообраз элемента С = 3 относитель­
но функции RSA^ опираясь на оракул Oh{Y^N). Шаги алгоритма
занесены в табл. 16.2.
Таблица 16.2. Таблица промежуточных значений алгоритма обращения
функции RSA

1Y 0{Y, N) L Я
3 0 0 10403
1 0
3-2^ 5201,5
1 2600,7
3-4^ 5201,5
1
3-8^ 3901,1 5201,5
0
3-16^ 4551,3 5201,5
0
3-32^ 4876,4
4551,3
1
3-64^ 4551,3 4713,8
0
3-128^ 4632,5 4713,8
1 4673,2
3-256^ 4632,5
1
3-512'^ 4673,2
4652,9
1
3-1024^ 4673,2
4663,0
1 4673,2
3-2048^ 4668,1
1 4673,2
3-4096^ 4670,7
0 4673,2
3-8192^ 4671,9
4672,5 1

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

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

ОГЛАВЛЕНИЕ

Следующая >>