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

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

ОГЛАВЛЕНИЕ

Следующая >>

G^ = G^' (modP) (modQ).
Препятствие — в приведении по модулю Q. Удалив последнюю опе­
рацию, мы получим возможность доказать стойкость подписи. Од-
17.2. Стойкость алгоритмов подписи 421

нако при этом теряется привлекательное свойство малого размера
подписи DSA,
17.2,1.3, EC-DSA-nodnucu. Аналогичные проблемы возника­
ют при попытках применить лемму Стерна и Пойнтчеваля к схеме
подписи EC-DSA. Однако здесь небольшое изменение схемы позво­
ляет доказать ее стойкость в определенных ситуациях. Вновь пред­
полагаем, что мы применяем хэш-функцию к М и i?, а не только
к М. Дважды вызывая подпрограмму противника и используя лем­
му Стерна и Пойнтчеваля, получаем
R = Х'КОорд.{[к]Р) (modQ), R' = х-коорд,.{[к']Р) (modQ),

S=^^-^ (modg), S' = El^L^ (modQ),

причем снова R = R' иН = Я ( М | | Л ) , Я ' = H{M\\R') — два крити­
ческих хэш-запроса. Если Q больше, чем размер конечного поля, из
равенства R = R' можно заключить, что к = ±к\ и вывести отсюда
равенство
{S4'S')k = H-H' (modQ).
Таким образом мы получим два возможных значения для /j, кото­
рые дадут нам два возможных значения х. Для правильного ответа
остается лишь проверить истинность равенства [х]Р = Y для обоих
кандидатов. Итак, мы доказали следующую теорему.

Теорема 17.2. Из предположения трудноразрешимости задачи дис­
кретного логарифмирования на эллиптической кривой Е{?р) выте­
кает (в модели случайного оракула), что успешная пассивная атака,
направленная на модифицированную схему подписи EC-DSA не­
возможна, если
Q = #Е{?р) > Р.

Обратите внимание на то, что этот результат применим лишь к
определенному подмножеству всех эллиптических кривых.

п.2.2. Активный противник
Для доказательства стойкости схем в отношении активного про­
тивника нам необходимо показать, как алгоритм В А будет отве­
чать на требования подписи со стороны алгоритма А. С этой целью
мы опять подключаем модель случайного оракула, в которой будем
использовать способность алгоритма В А выбирать значения хэш-
функции. Заметим, что аргумент хэш-функции может быть неизве-
^22 Глава 17. Доказуемая стойкость со случайным оракулом

стен вплоть до получения подписи на сообщении. Если хэш-функция
при этом применяется только к сообщению М и не зависит от дру­
гих величин (как Si в предыдущих рассуждениях), то алгоритм А
может послать запрос хэш-оракулу, входными данными которого
служит сообщение М, перед тем, как подпись будет создана. В этой
ситуации алгоритм В А не способен изменить ответ по сравнению с
предыдущим.
Процесс ответов алгоритма В А на запросы подписи нападающе­
го А без его участия и без информации о секретном ключе назы­
вается моделированием запросов подписи. Такое моделирование по
существу означает, что активный противник обладает не большими
возможностями, чем пассивное нападение в модели случайного ора­
кула, поскольку любой активный противник может быть превращен
в пассивного простым моделированием запросов подписи.
п.2.2.1. Схема подписи Шнорра. Моделирование запросов
подписи в доказательстве стойкости схемы Шнорра осуществляет­
ся довольно легко. Оно тесно связано с протоколами доказательств
с нулевым разглашением из параграфа 13.3. Мы предполагаем, что
симулятор хранит список L всех предыдущих запросов случайно­
го оракула. По введенному в него сообщению М симулятор делает
следующее:
1. Вычисляет случайные числа 5 и i/, удовлетворяющие условию:
1 ^S,H <Q.
2. Полагает R = Q^Y'^.
3. Если (jR||M, i7^) € L при Н^ ф if, то симулятор возвращается
к шагу 1.
4. Присоединяет к множеству L элемент (Д||М, if), т. е. на запрос
(jR||M) хэш-оракул теперь будет всегда выдавать ответ Н.
5. Выдает «подпись» {H^S).
Проверьте, что перечисленные шаги приводят к верной подписи и
что алгоритм А не сможет отличить моделируемые значения Н^ ге­
нерируемые случайным оракулом, от тех, которые производит ис­
тинный алгоритм подписи. Итак, мы получили теорему.

Теорема 17.3. Если задача дискретного логарифмирования в груп­
пе А трудноразрешима, то (в модели случайного оракула) не сущест­
вует успешной активной атаки на схему подписи Шнорра с группой А.
В отношении DSA аналогичных результатов пока не получено.
Доказательство стойкости известно для схемы EC-DSA., где вме­
сто моделирования хэш-функции и сведения стойкости к проблеме
17.2. Стойкость алгоритмов подписи

дискретного логарифмирования в качестве главного объекта мо­
делируется групповая операция, а стойкость сводится к проблеме
повторяюш;ихся значений реально используемой хэш-функции.

17.2.3. RSA-FDH
Следует отметить, что в нашем обсуждении схем Шнорра, DSA и
EC-DSA предполагалось, что значения хэш-функции Н принадле­
жат полю Fp. Такие хэш-функции трудно построить на практике,
хотя предыдуп1;ие рассуждения использовали именно это свойство.
Аналогичная ситуация возникает в одном из вариантов схемы
подписи RSA^ называемом RSA-FDH (от англ. full domain hash).
Хэш-функция в ней — отображение
Н : {0,1} {Z/NZ)\
где N — Д5А-модуль. Такую хэш-функцию тоже трудно реализо­
вать, но предположив, что она суш;ествует, и включив ее в модель
случайного оракула, мы сможем доказать стойкость следуюш;его ал­
горитма подписи RSA,
Пусть N — модуль алгоритма RSA^ Е — шифруюш;ая, a d —
расшифровываюш;ая экспоненты. Обозначим через / функцию, дей-
ствуюш;ую по правилу:

{Z/NZr -(Z/iVZ)*,
[
в этих терминах задача RSA заключается в определении х по дан­
ному Y = f{x). В схеме RSA-FDH подпись на сообщении имеет вид
S = Н{МУ = Г\Н{М)),
Можно доказать следующую теорему.

Теорема 17.4. Если в модели случайного оракула существует ак­
тивный противник А, способный добиться экзистенциальной фаль­
сификации в схеме RSA-FDH^ используя дн хэш-запросов и qs обра­
щений к подписывающему оракулу, то найдется алгоритм, кото­
рый по данному Y может восстановить соответствующий прообраз
функции RSA с вероятностью - ^ .
Доказательство. Опишем алгоритм В А-, который по данному
Y G (Z/iVZ)* вычисляет х = /˜^(У). Алгоритм В А сначала вы­
бирает значение Т G [1, . . . , дн] и заводит нумерованный список
всех сделанных хэш-запросов. Затем он вызывает подпрограмму А
и отвечает на сделанный противником хэш-запрос для введенного
Глава 17. Доказуемая стойкость со случайным оракулом

сообп1;ения Mi следуюш;им образом:
- если А делает хэш-запрос, совпадаюш;ий с уже сделанным ра­
нее запросом под номером Т, то ВА дает Y в качестве ответа
и модифицирует список запросов так, чтобы выполнялось ра­
венство Y = Н{МтУ-,
- если хэш-запрос противника А выглядит как М/ с / т^ Т, то
В А вычисляет случайный элемент Si Е (Z/7VZ)* и добавляет к
списку хэш-запросов H{Mj) = Sf (modAT) = iJ/, храня запись
значения «S/, а в качестве ответа выдает Hj.
Если противник А требует подписать сообш;ение М/ перед хэш-
запросом с этим сообщением, то перед ответом В А моделирует со­
ответствующий хэш-запрос вместо алгоритма А, После этого ответ
на запрос о подписи выглядит так:
- если сообщение М/ совпадает с Мг, то алгоритм останавли­
вается и сообщает о сбое;
- если М/ 7^ Мт^, то в качестве ответа на запрос подписи В А
выдает 5 / .
Допустим, что противник закончит работу и выдаст в качестве
результата подписанное сообщение (5, М). Без ограничения общ­
ности можно предполагать, что при этом алгоритм А делал хэш-
запрос для М. Если М ф Мт^ то алгоритм ВА останавливается
с сообщением о неудачной попытке обратить функцию. Если же
М = Мт-, то имеет место соотношение
/ ( 5 ) = Е{Мт) = У.
Следовательно, мы вычислили требуемый прообраз функции / .
Анализируя алгоритм ВА-> заметим, что при корректной работе
противник А создал экзистенциальную подделку (M^S)^ и поэтому
он не мог в процессе работы требовать от оракула подписать со­
общение М. Выбранное в начале работы значение Т не зависит от
вида алгоритма А, Поэтому алгоритм А не может постоянно тре­
бовать поставить подпись на сообщение Мт- Значит, грубо говоря,
вероятность успешного завершения алгоритма В А приблизительно
равна - ^ , т.е. вероятности того, что экзистенциальная подделка
была сделана именно на сообщении М^, а не на каком-то другом. •

17.2.4. RSA-PSS
Другой способ применения RSA в качестве подписывающего ал­
горитма основан на использовании так называемой RSA-PSS или
17,2. Стойкость алгоритмов подписи

вероятностной схемы подписи RSA (от англ. probabilistic signature
scheme). Ее стойкость тоже доказывается с помощью модели слу­
чайного оракула. Мы не станем давать здесь подробное доказа­
тельство, ограничившись простым описанием схемы, поскольку ее
значение постоянно возрастает. Преимущество этой схемы перед
RSA-FDH состоит в том, что в ней используется традиционная хэш-
функция, принимающая значения в битовых строках длины t, а не
в кольце вычетов по модулю составного числа.
Как обычно, фиксируем модуль N алгоритма ДЙ'Л, открытую
экспоненту Е и секретную экспоненту d. Обозначим параметр бе­
зопасности через /с, т. е. модуль N состоит из к двоичных знаков.
Определим два целых числа к^ и ki так, чтобы
к{)-\- ki ^ fe — 1.
Например, можно взять к^ = 128 или 160.
Кроме того, зададим две хэш-функции, одна из которых разво­
рачивает данные, а другая их сжимает:
G:{0,1}^^ -{0,1}^-^^-\
Я : {0,1}* {0,1}^^
Пусть
Gi : {0,1}^^ {0,1}^«
обозначает функцию, сопоставляющую строке w G {0,1}^^ первые
fco знаков числа G{w)^ а функция
G2 : {0,1}^1 {о^1}к-ко-кг-1
сопоставляет строке w G {0,1}^^ оставшиеся А — Ао — A:i — 1 знаков
: :
числа G{w),
Чтобы поставить подпись на сообщении М, делают следующее:
- генерируют случайную строку R G {0,1}^°,
- вычисляют W = Я ( М | | Д ) ,
- определяют Y = Q\\W\\{Gi{W) ® R)\\G2{W),
- выдают подпись в виде 5 = ^ ^ (modTV).
Для проверки подписи (5, М)
- вычисляют Y = S^ (modA^);
- разбивают Y на компоненты:
Вт\\а\\ъ
где В — однобитовое слово, W — ^х-битовое, а — /со-битовое,
а 7 состоит из А —fco—fci— 1 знаков;
:
Глава 17. Доказуемая стойкость со случайным оракулом

- вычисляют R = а® Gi{W)]
- подпись имеет силу, если
В = 0, С2(И^)=7 и H[M\\R) = W,

Если доверить моделирование хэш-функций G и Н случайному
оракулу, то можно показать, что изложенная схема подписи стой­
ка в том смысле, что существование успешного алгоритма, осуще­
ствляющего экзистенциальную фальсификацию, влечет обращение
функции RSA, Полное доказательство этого факта изложено в ста­
тье Белларе и Рогавей, точную ссылку на которую можно найти в
конце этой главы.


17.3. Стойкость шифрующих алгоритмов
Мы видели, что в предположениях проблемы выбора Диффи-Хелл-
мана довольно легко создать семантически стойкую схему шифро­
вания с открытым ключом, имея в виду лишь пассивного против­
ника. Например, криптосистема Эль-Гамаль обладает этим свой­
ством. Кроме того, мы убедились, что можно легко построить се­
мантически стойкие шифры, основанные на проблеме квадратич­
ных вычетов, опять-таки принимая во внимание только пассивных
противников. К сожалению, система Гольдвассера и Микали, о ко­
торой идет речь, обладает весьма неприятным свойством, сильно
увеличиваюш;им объем сообш;ений. Оказывается, создание крипто­
системы, основанной на проблеме дискретного логарифмирования,
заш;ищенной от активного противника или семантически стойкой в
предположениях RSA^ сталкивается со значительными трудностями.
В этом параграфе мы сначала остановимся на ранних попытках
конструирования криптосистемы, основанной на примитиве Эль-
Гамаль, которая была бы защиш;ена от активного противника. На
их примере удобно продемонстрировать основные принципы про­
ектирования. Затем мы перейдем к описанию главной системы, по­
строенной на ДЙ'Л-примитиве, которая в модели случайного оракула
заш;иш;ена от активного противника, а именно, системы RSA-OAEP.

17.3.1. И м м у н и з а ц и я к р и п т о с и с т е м , о с н о в а н н ы х
на Эль-Гамаль
Напомним, что шифрование Эль-Гамаль имеет вид
(G^m.У^),
17,3. Стойкость шифрующих алгоритмов

где Y = G^ — открытый ключ. Используя довольно элементарную
технику, мы уже показали в главе 15, что в предположениях про­
блемы выбора Диффи-Хеллмана шифрование Эль-Гамаль обладает
семантической стойкостью. Однако там же было продемонстриро­
вано, что такая система не стойка в отношении активного против­
ника, поскольку соответствуюпдий шифротекст не обладает жест­
костью.
Было понято, что проблема, связанная с активным противни­
ком, состоит в том, что нападаюп1;ий может слишком легко создать
корректный шифротекст. Дело в том, что если бы противнику бы­
ло трудно моделировать шифротекст, поддаюш;ийся расшифрова­
нию, то атака с выбором шифротекста не дала бы ему никаких
особых преимуп1;еств. Действительно, у него нет причин требовать
расшифрования шифротекста, который он может получить только
зашифровав самостоятельно какой-то открытый текст. Это озна­
чает, что необходима такая расшифровываюш;ая процедура, кото­
рая по введенному в нее шифротексту выдает или подлежаш;ий от­
крытый текст, или сообш;ение о несоответствии этого шифротек­
ста какому-либо открытому сообщению. Для этой цели нужно доба­

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

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

ОГЛАВЛЕНИЕ

Следующая >>