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

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

ОГЛАВЛЕНИЕ

Следующая >>

данными стадии поиска являются два открытых текста MQ И MI .
После стадии поиска алгоритм В А выбирает бит В случайным
образом и находит тестовый шифротекст (C/i, С/2, Е^ V):
Е = Мв' (U^'Up), а = F{Ui\\U2\\E), V- и^^^^'^'и^'^У''',
Заметим, что при подаче на вход алгоритма В А четверки Диффи-
Хеллмана соответствующий шифротекст будет корректно расши­
фрован. Если же на вход подавать случайную четверку элементов,
то почти наверняка шифротекст будет признан некорректным.
Тестовый шифротекст передается на стадию гипотеза против­
ника А. Если нападающий правильно определит бит В, то мы запо-
Глава 18. Доказуемая стойкость без случайного оракула

дозрим, что введенная четверка является четверкой Диффи-Хелл­
мана. В противном случае — это случайный набор элементов. По­
вторяя процесс неоднократно, придем к статистическому тесту,
определяющему, является ли данная четверка элементов четверкой
Диффи - Хеллмана, причем с увеличением количества повторений
мы увеличиваем вероятность правильного ответа.
Важно отметить, что приведенные выше рассуждения — всего
лишь набросок доказательства. Необходимо еще показать, что на­
падающий алгоритм А не сможет отличить нашей игры от реально
протекающей атаки, иначе бы он знал: что-то здесь не так. Напри­
мер, нам нужно доказать, что ответы В А на запросы нападающего
с точки зрения последнего неотличимы от ответов истинного рас­
шифровывающего оракула. Полное доказательство приведено в ра­
боте, ссылку на которую можно найти в разделе «Дополнительная
литература» в конце этой главы.
Схема шифрования Крамера-Шоупа похожа на Эль-Гамаль, но
существенно менее эффективна. Поэтому, несмотря на свойство до­
казуемой стойкости, схема Крамера-Шоупа не находит практиче­
ского применения из-за неудобств в работе. Стойкость схемы ши­
фрования DHIES^ рассматриваемой далее, тоже доказывается без
привлечения случайного оракула, хотя предположения о сложности
задачи в этой схеме изучены меньше, чем проблема выбора Диффи-
Хеллмана. Однако схема DHIES обладает лишь незначительно мень­
шей эффективностью, чем Эль-Гамаль из главы 7.

18.4.2. С х е м а ихифрования DHIES
Схема шифрования DHIES сильно напоминает иммунизационные
методы, предложенные Женгом и Себерри. Однако можно дока­
зать стойкость схемы DHIES в отношении адаптивной атаки с вы­
бором открытого текста, предполагая, что следуюш;ие три компо­
ненты стойки сами по себе:
- конечная циклическая абелева группа, в которой выполнены
интерактивные хэш-предположения Диффи-Хеллмана;
- шифруюп];ая функция с симметричным ключом, семантически
стойкая в отношении адаптивной атаки с выбором открытого
текста;
- код аутентификации сообщения или хэш-функция с переключа­
телями, для которой противник не может найти MAC «не­
прошенного сообш;ения». Об этой последней концепции имеет
смысл думать как о МА С-версии экзистенциальной фальсифи­
кации.
18.4- Алгоритмы шифрования

Схема DHIES Белларе и Рогавей включает в себя все три выпи­
санные компоненты, что объясняет ее название: интегрированная
схема шифрования Диффи-Хеллмана или DHIES (от англ. Diffie-
Hellman Integrated Encryption Scheme). Первоначально схема носи­
ла название расширенной схемы шифрования Диффи-Хеллмана или
DHAES (от англ. Diffie-Hellman Augmented Encryption Scheme), ко­
торое не прижилось ввиду возможной путаницы с AES — новым
стандартом шифрования.
Ключ в DHIES генерируется точно так же, как в криптосистеме
Эль-Гамаль. К параметрам домена относятся циклическая конечная
абелева группа А простого порядка Q, образующая этой группы G,
симметричная шифруюш;ая функция {Ek^Dk}^ функция MAC, ко­
торую мы будем обозначать символом MACk^ и хэш-функция F.
Группу и хэш-функцию нужно выбирать так, чтобы р^ля. них были
выполнены интерактивные хэш-предположения Диффи-Хеллмана.
Для создания ключевой пары генерируется случайный элемент
X G Zi/QX и вычисляется открытый ключ


Чтобы зашифровать сообщение ттг, генерируется случайный эфе­
мерный ключ к (свой для каждого сообщения) и вычисляется
v = P^ и [/ = G^.
Подставив это в хэш-функцию, мы получим два ключа: один р^ля
симметричного алгоритма шифрования, а другой — ^\ля функции
MAC:
[kiM) = F{U\\v),
После этого вычисляем

C = EkM). T = MACk,{C)-
Шифротекст передается в виде тройки
и\\с\\т.
Обратите внимание на то, что эта система дает возможность эф­
фективно шифровать сколь угодно длинные сообщения с помощью
алгоритма шифрования с открытым ключом. Величина U подменя­
ет собой механизм передачи ключей, шифрование осуществляется
симметричной функцией шифрования, а предотвращение адаптив­
ных атак на всю схему обеспечивается дополнительным значением
Т функции MAC,
450 Глава 18. Доказуемая стойкость без случайного оракула

Чтобы расшифровать шифротекст С/||С||Г, законный облада­
тель секретного ключа может вычислить


и определить эфемерные ключи fci, /^2 с помоп];ью хэш-функции:
[kiM) = F{U\\v).
Шифротекст корректен, если выполнено равенство:

T = MACkAC)^
В этом случае сообш;ение восстанавливается вычислением
m = Dk,{C),

Объясним основную идею доказательства стойкости DHIES в
отношении адаптивного противника при условии правильного вы­
бора симметричной системы шифрования, функции MAC и истин­
ности интерактивных хэш-предположений Диффи-Хеллмана. Пусть
А — алгоритм успешной атаки на DHIES. Покажем, как его мож­
но использовать для решения интерактивной хэш-задачи Диффи-
Хеллмана или для взлома симметричной системы шифрования, или
для фальсификации функции MAC.
Сконструируем алгоритм J5^, предназначенный ^\ля решения ин­
терактивной хэш-задачи Диффи-Хеллмана. На его вход подается
три элемента
G^, СУ и Н.
Цель алгоритма — определить, выполнено ли равенство
Н = FiGyWC^y). (18.2)
В алгоритм В А встроен оракул О, который по секретному числу х
вычисляет
HDH:,{X)=F{XW).
Алгоритм В А фиксирует открытый ключ


и вызывает стадию поиска противника А, на которой генерируются
два сообш;ения MQ И M I . Затем В А выбирает случайный бит J9 и по
элементу Н производит ключи Ki и JFC2*
Ki\\K2 = H.
18.4' Алгоритмы шифрования

На следующем шаге В А вычисляет
С = ЕкЛМв), Т = МАСкЛС)
И получает шифротекст
{СУ,С,Т),
который передается на стадию гипотезы алгоритма А. В результа­
те работы противник А должен определить скрываемый бит В.
Если А правильно найдет этот бит, В А делает вывод о том, что
равенство (18.2) истинно; в противном случае это равенство скорее
всего ложно. Доказывая стойкость схемы, показывают, что с помо-
П1;ью успешной атаки А алгоритм ВА способен достичь одной из
следующих целей:
- установить истинность или ложность равенства (18.2);
- взломать семантическую стойкость привлеченной к схеме сим­
метричной функции шифрования;
- фальсифицировать функцию MAC.
Детали доказательства очень интересны, но мы оставим их лю­
бознательному читателю для самостоятельной проработки. Един­
ственное, что мы обсудим, это ответы алгоритма ВА на запросы
дешифрования со стороны противника, да и то в упрощенном виде.
Напомним, что В А имеет доступ к оракулу О, который решает хэш-
задачу Диффи-Хеллмана для скрытого ключа х. Получив в качестве
запроса шифротекст
Ui\\Ci\\Ti,
алгоритм В А вызывает оракул О для вычисления
{h,k2) = 0{Ui) = F{Ui\\Un-
После этого алгоритм В А способен проверить корректность шифро-
текста и расшифровать его так же, как это сделала бы подлинная
расшифровывающая функция. Проблема возникнет в том случае,
когда от противника поступит запрос на расшифрование шифро-
текста с Ui — G^ ^ поскольку он фактически является запросом на
решение интересующей нас хэш-проблемы, что недопустимо по пра­
вилам игры. Методы преодоления этой проблемы освещены в ори­
гинальной работе, содержащей полное доказательство.
Заметим, что интерактивная природа хэш-предположений Диф-
фи - Хеллмана требует моделирования расшифровывающего ораку­
ла, что дает простор для критики доказательства, поскольку оно
сводит стойкость схемы DHIES к полностью нестандартным пред-
Глава 18. Доказуемая стойкость без случайного оракула

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

К р а т к о е с о д е р ж а н и е главы

- Схемы подписи, чью стойкость удается доказать без случайно­
го оракула, менее естественны, чем те, стойкость которых по­
лучается в рамках случайного оракула. Происходит это, види­
мо, потому, что подписи существенно используют хэш-функции,
легко моделируюш;иеся случайным оракулом.
- Сильные предположения RSA — естественное ослабление стан­
дартных Д*5Л-предположений.
- Интерактивные хэш-предположения Диффи - Хеллмана счита­
ются более слабыми, чем обычные предположения Диффи - Хел­
лмана. Они учитывают взаимодействие хэш-функции, исполь­
зуемой в задаче Диффи-Хеллмана, с соответствующей абе-
левой группой. Интерактивная природа этих предположений
делает их полностью нестандартными.
- Схема шифрования Крамера-Шоупа в предположении сложно­
сти проблемы выбора Диффи - Хеллмана доказуемо стойка вне
модели случайного оракула. Работает она примерно в три раза
медленнее, чем обычный алгоритм шифрования Эль-Гамаль.
- Схема шифрования DHIES тоже доказуемо стойка без модели
случайного оракула. Однако ее стойкость основывается на ин­
терактивных хэш-предположениях Диффи-Хеллмана. К пре­
имуществам этой схемы относится высокая эффективность.


Дополнительная литература
Схемы, упомянутые в этой главе, можно найти в следуюпщх статьях.
М. Abdalla, М. Bellare and P. Rogaway. DHAES: An encryption scheme
based on the Diffie-Hellman problem. Submission to IEEE P1363a stan­
dard.
R. Cramer and V. Shoup. A practical public key cryptosystem provably
18.4- Алгоритмы шифрования

secure against adaptive chosen ciphertext attack. In Advances in Cryp-
tology — CRYPTO '98, Springer-Verlag LNCS 1462, 13-25, 1998.
R. Cramer and V. Shoup. Signature schemes based on the strong RSA
assumption. ACM Transactions on Information and Systems Security,
3, 161-185, 2000.
R. Gennaro, S. Halevi and T. Rabin. Secure hash-and-sign signatures
without the random oracle. In Advances in Cryptology — EuroCrypt
'99, Springer-Verlag LNCS 1592, 123-139, 1999.

Упражнения
18.1.1. Попытайтесь изобрести эффективную хэш-функцию, кото­
рую можно было бы использовать в схеме Дженнаро-Галеви-
Рабина. Существуют ли какие-нибудь вычислительные пред­
положения, позволяющие доказать, что Ваша хэш-функция
защищена от повторений?

18.1.2. При моделировании подписей в схеме Крамера-Шоупа нам
нужно случайным образом вычислять значения из Q^v, не
зная простых делителей модуля N. С другой стороны, слож­
ность определения принадлежности элемента множеству QN
совпадает с трудностью задачи факторизации. Покажите,
как эффективно реализовать эту стадию моделирования.

18.1.3. Покажите, что корректный пшфротекст в криптосистеме Кра­
мера-Шоупа выдерживает тест на справедливость соотно­
шения
ТтХ1-\-у1атгХ2+У20с _ у



18.1.4. Проверьте, что тестовый шифротекст, подающийся на ста­
дию гипотезы в доказательстве стойкости схемы шифрова­
ния Крамера-Шоупа, будет корректен, если входные данные
алгоритма В А — четверка Диффи - Хеллмана.
Приложение А
Основная математическая терминология

Здесь собраны математические понятия и термины, необходимые
для чтения основного текста книги. Материал в приложении пода­
ется в более формализованной манере, нежели в первой части.


А. I. Множества
Начнем с самых основных определений, вошедших сюда д^ля полноты
картины.

Определение А Л . Для двух множеств А и В определены опе­
рации объединения (U), пересечения (П), разности (\) и прямого
произведения (х):
АиВ = {х\ X е А или X е В},
АпВ = {х\хеАихе В},
А\В = {х\х еАихфВ},
Ах в = {{х,у)\ X е Аи X е В}.
Запись А С В означает, что А является подмноэюеством в 5 , т.е.
Xе А ^ X е В.

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

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

ОГЛАВЛЕНИЕ

Следующая >>