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

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

ОГЛАВЛЕНИЕ

Следующая >>

18.S. Схемы подписи

Но любые другие запросы к НПН-оракулу противнику дозволе­
ны. Интерактивные хэш-предположения Диффи-Хеллмана состоят
в том, что противник, вооруженный таким оракулом, не сможет
найти ответ в хэш-задаче Диффи-Хеллмана.
Заметим, что в определении адаптивной атаки требуется хэш-
функция. Чтобы понять почему, допустим, что мы используем ана­
логичное определение адаптивной атаки, направленной на предпо­
ложения проблемы выбора Диффи-Хеллмана. По данным элементам
В = G^^ С = G^ и D = G^ нападаюш;ий мог мы запрашивать «нехэ-
шированный» оракул Диффи-Хеллмана
DHy{G'B) = DHy{GG''),
который бы отвечал на этот запрос


в этом случае мы могли бы разделить ответ оракула на С и прове­
рить истинность равенства


Комбинирование хэш-функции с предположениями Диффи - Хел-
лмана в одну группу предположений позволит нам (в схеме DHIES^
приведенной ниже) отказаться от участия случайного оракула в
доказательстве стойкости. Тем не менее, еще остается некоторая
странность, поскольку определенная хэш-функция, используемая в
схеме, взаимодействует с конкретной абелевой группой схемы. Это
взаимодействие может привести, вообще говоря, к более легкой хэш-
задаче Диффи-Хеллмана. Поэтому можно с уверенностью заявить,
что использование хэш-предположений Диффи-Хеллмана в противо­
вес случайному оракулу привносит некоторую философскую проблему.


18.3. Схемы подписи

Мы уже отмечали, что очень трудно создать схемы подписи, чью
стойкость можно доказать, не используя модели случайного ораку­
ла. Найденные схемы с таким свойством кажутся несколько искус­
ственными в сравнении с RSA-PSS^ DSA^ схемой Шнорра и други­
ми применяемыми на практике схемами подписи. Первая из таких
схем с доказуемой стойкостью в стандартной модели была пред­
ложена Гольдвассером, Микали и Ривестом. Правда, она была не
очень практичной, т. к. в этой схеме сообщения ассоциировались с
Глава 18. Доказуемая стойкость без случайного оракула

листьями двоичного дерева, каждый узел в котором аутентифици-
рован своим отцом^. Это делает схему слишком медлительной.
В этом параграфе мы рассмотрим две «практичные» современ­
ные схемы подписи с доказуемой стойкостью. Однако мы увидим,
что они приводят к некоторым проблемам, которых не возникает в
стандартных схемах подписи.

18.3.1. Схема подписи Дженнаро-Галеви-Рабина
В 1999 г. Дженнаро, Галеви и Рабин изобрели схему подписи с до­
казуемой стойкостью, названную GHR-cxeuoik подписи. Доказатель­
ство ее стойкости, которая основывается на сильных предположени­
ях RSA^ можно получить, не привлекая модель случайного оракула.
На стадии генерирования ключа выбирают модуль RSA
N =P'q
так, чтобы простые числа р тл q удовлетворяли дополнительному
условию:
числа —-—, —-— — простые. (18.1)

Такое требование на множители модуля означает, что найти нечет­
ное целое число, взаимно простое с
^p{N) = {p-l)iq-l),
настолько же сложно, насколько трудно разложить число на про­
стые множители. Кроме модуля N к открытому ключу добавляется
случайный элемент S G (Z/7VZ)*.
Чтобы поставить подпись на сообщение М, законный пользо­
ватель схемы, знающий простые делители числа 7V, может найти
такое число Е, что
S^W=5(modJV),
где Н — фиксированная хэш-функция. Это же уравнение работает
на стадии проверки подписи.

^Двоичным деревом называется связный граф, из каждой вершины, которого
выходит не более двух ребер. Как правило, одна из вершин дерева выделяется
и называется корнем. После этого на верпшнах дерева вводится частичный по­
рядок, согласно которому сравнимы верпп1ны, расположенные на одной ветви
дерева. Большей считается та, которая расположена ближе к корню. Минималь­
ные вершины называются листьями. Вершины, отличные от корня и листьев,
называются узлами. Из двух соседних узлов на ветви отцом считается большая
вершина, а меньшая — сыном. — Прим. перев.
18.3. Схемы подписи

Легко понять, как эта схема соотносится с сильными предполо­
жениями RSA. Однако данная схема нуждается в очень специальном
типе хэш-функции. Чтобы увидеть, почему, предположим, что ак­
тивный противник намерен подписать сообш;ение Mi, причем ему
удалось найти такое сообпдение М2, что
Я(М2) = ^ - Я ( М 1 ) .
Допустим теперь, что этот нападаюп];ий требует от оракула поста­
вить подпись на М2. Оракул выдает значение Е2, ^1,ля которого

Ef^^^ = 5(modiV).
В этой ситуации атакуюп];ий может подделать подпись на сообще­
нии Ml, вычисляя
Si - E f (modTV),
поскольку

E f (^^^^ = ( E f ) ' ' ^ ' ' ^ ' (modiV) = S2^^(^^' (mod AT) =

= E f ^ ^ 4 m o d i V ) = 5.
Авторы схемы подписи предлагают самый простой способ пресече­
ния такого типа атак, а именно, в качестве хэш-функции Н стоит
брать те, которые принимают значение в простых числах. Можно
было бы еще потребовать от хэш-функции, чтобы она была защище­
на от повторяющихся значений. Хэш-функции, значения которых —
простые числа, спроектировать можно, но они довольно плохо изу­
чены и не выглядят «естественными».

18.3.2. Схема подписи Крамера-Шоупа
Схема подписи Крамера-Шоупа также основана на сильных предпо­
ложениях RSA и обладает доказуемой стойкостью вне модели слу­
чайного оракула. Как и в предыдущей схеме, нам необходимо ге­
нерировать простые числа, но здесь они не должны являться зна­
чениями хэш-функции. Поэтому схема Крамера-Шоупа может до­
вольствоваться стандартной хэш-функцией, например, SHA-1. Да­
лее символом F мы будем обозначать «стандартную» хэш-функцию,
значения которой — 160-битовые строки, интерпретируемые, как
обычно, 160-битовыми натуральными числами.
При выборе открытого ключа мы вновь выбираем Дб'Л-модуль
N как произведение простых чисел р и ^, удовлетворяющих свойству
Глава 18. Доказуемая стойкость без случайного оракула

(18.1). Фиксируются два квадратичных вычета
Я , X G QN,
где, как обычно, QN обозначает множество всех квадратичных выче­
тов по модулю N. Кроме того, генерируется случайное 160-значное
двоичное простое число Е', Открытый ключ состоит из четверки
{N,H,X,E'),
а соответствующий секретный ключ — это простые числа р is. q.
Чтобы подписать сообщение, необходимо генерировать еще одно
160-значное двоичное простое число Е и дополнительный случайный
квадратичный вычет У G QN- После этого законный пользователь,
зная делители модуля А/", может найти решение Y уравнения

Г = ( Х Я ^ ( ^ ' ) ) * (modiV),

где Х^ определяется формулой
X' = Y'^'H-^^^\
Подпись выглядит следующим образом:
{E,YX)-
На этапе проверки прежде всего необходимо убедиться, что Е' —
нечетное число, не совпадающее с Е. Затем нужно вычислить
X' = Y'^'H-^^^^
и проверить, что
X= уЕн-^^^'\
Исходя из предположения о том, что хэш-функция F защищена
от повторений, а сильные ДЙ'Л-предположения верны, можно пока­
зать, что эта схема подписи стойка в отношении активного про­
тивника. Приведем наиболее важные моменты доказательства, но
опустим все детали, оставив их любознательному читателю р^ля са­
мостоятельного восполнения.
Предположим, что противник делает t запросов подписывающе­
му оракулу. Встроим алгоритм нападения А в новый алгоритм ВА^
который взламывает сильные Д5Л-предположения при фиксирован­
ном модуле N, Перед тем как ввести в алгоритм А открытый ключ,
алгоритм В А должен решить, какое именно простое число Ei будет
выдаваться в качестве ответа на запросы подписи. Затем, зная JS^,
алгоритм В А подбирает такие значения ^1,ля Н и X из открытого
ключа, чтобы ему были известны корни степени Ei из Н и X.
18.4' Алгоритмы шифрования

Итак, получив запрос о подписи на сообщении М^, (в качестве
подписывающего оракула) В А может вычислить имеющую силу под­
пись, не обращаясь к разложению числа N на множители, а генери­
руя У/ G QN случайным образом и вычисляя

Х; = Г / ^ ' я - ^ ( ^ ^ ) (modTV), Yi = Х^1{Н'к)Пх'^ (modiV).
Подпись будет иметь вид
(МьУ„У/).
в полном доказательстве этот основной алгоритм, моделирую­
щий подписывающего оракула, должен быть несколько изменен в
зависимости от типа фальсификации, производимой алгоритмом А.
По основная идея доказательства состоит в том, что алгоритм В А
создает открытый ключ, позволяющий ему правдоподобно ответить
на любой запрос подписи противника А.


18.4. Алгоритмы шифрования
в отличие от схем подписи, можно создать практичные близкие к
применяемым в реальной жизни шифрующие системы, обладающие
свойством доказуемой стойкости вне модели случайного оракула.
Фактически, вторая из схем, рассматриваемых нами в этом пара­
графе, а именно, DHIES^ шифрующий алгоритм с открытым клю­
чом, основанный на проблеме дискретного логарифмирования в ко­
нечных полях или на эллиптической кривой, приводится в различ­
ных стандартных документах.
Недостаток системы DHIES заключается в том, что ее стой­
кость частично опирается на предположение о трудности решения
хэш-задачи Диффи-Хеллмана. К сожалению, эта задача не так хо­
рошо изучена, как обычная проблема выбора Диффи-Хеллмана. По­
этому мы начнем с представления доказуемо стойкой схемы, чья
стойкость зиждется на обычной проблеме выбора Диффи-Хеллмана.

1 8 . 4 . 1 . С х е м а гпифрования К р а м е р а - Ш о у п а
Параметры домена схемы шифрования Крамера-Шоупа состоят из
конечной абелевой группы А простого порядка Q, Кроме того, фик­
сируется универсальное одностороннее семейство хэш-функций. На­
помним, что это такое семейство {Fi} хэш-функций, при котором
противнику трудно выбрать число X и функцию Fi, для которых
можно было бы подобрать другое число у, удовлетворяющее соот-
446 Глава 18. Доказуемая стойкость без случайного оракула

ношению
Fi{X) = Рг{у).
Ц^ля открытого ключа схемы выбираются случайные элементы
Gi,G2 е А, xi,x2,yi,y2,z е Z/QZ.
По ним законный пользователь может вычислить
С = Gl'Gl^ D = GfGf, Н = Gl
Затем выбирается хэш-функция F из универсального односторон­
него семейства {Fi} и публикуется открытый ключ в виде набора
{GuG2,C,D,H,F).
Соответствующий секретный ключ имеет вид:
{xi,X2,yi,y2,z).
Процедура шифрования в этой схеме напоминает аналогичный
процесс в криптосистеме Эль-Гамаль. Сообщение т отождествля­
ется с элементом абелевои группы А, Выбирается случайный эфе­
мерный ключ г G Z/QZ, и производятся вычисления:
Ui=G[, a = F{Ui\\U2\\E),
U2 = Gl, V = C'D^'^.


Шифротекстом служит четверка
{Ui,U2,E,V).
Получив шифротекст, обладатель секретного ключа восстанав­
ливает соответствующий открытый текст по следующей схеме. Сна­
чала вычисляется а = F{Ui\\U2\\E) и проверяется равенство


Если ЭТО равенство ложно, то шифротекст признается некоррект­
ным. Если оно истинно, то получатель расшифровывает шифро­
текст вычислением:
Е

Ц^ля проверки доказуемой стойкости схемы в предположениях
о сложности проблемы выбора Диффи-Хеллмана и принадлежно­
сти функции F к универсальному одностороннему семейству хэш-
функций допустим, что у нас есть алгоритм Л, атакующий нашу
18.4- Алгоритмы шифрования

схему, и покажем, как его встроить в другой алгоритм В А-, пытаю­
щийся решить проблему выбора Диффи-Хеллмана.
Одна из формулировок проблемы выбора Диффи-Хеллмана име­
ет следующий вид: по данному набору элементов (Gi, С?2^ С^ь ^^2) ct6e-
левой группы А определить, является ли он случайным или образу­
ет четверку Диффи-Хеллмана, т.е. найдется такой г G Z/QZ, что
Ui = Gi и U2 = G2- Таким образом, алгоритм В А будет получать
на входе набор элементов (Gi,G2, C/i, С/2) группы и пытаться опре­
делить, случаен он или является четверкой Диффи-Хеллмана.
Прежде всего, алгоритм ВА должен выбрать открытый ключ.
Делает он это нестандартным образом. Сначала алгоритм выбирает
случайные элементы
xi,X2,yi,y2,zi,Z2 е Z/QZ,
затем производит вычисления
С = Gl'Gl\ D = GfGf, Н = G\'Gl\
В последнюю очередь алгоритм В А выбирает хэш-функцию F из
универсального одностороннего семейства и получает открытый
ключ:

Обратите внимание на то, часть ключа, соответствующая if, в ал­
горитме выбирается не так, как в реальной схеме, но с условием,
что А не сможет заметить это изменение.
Выбрав открытый ключ, алгоритм В А вызывает стадию поис­
ка противника, отвечая на запрос по расшифровке шифротекста
{U[^U2^E'^V) вычислением
Е'

проверив предварительно корректность шифротекста. Выходными

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

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

ОГЛАВЛЕНИЕ

Следующая >>