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

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

ОГЛАВЛЕНИЕ

Следующая >>

влять к шифротексту некоторую дополнительную информацию, по
которой расшифровывающая процедура могла бы определять, по­
лучен ли этот шифротекст с помощью законной процедуры шифро­
вания из какого-то связного сообщения. Стоит сравнить сделанное
замечание с нашей дискуссией в главе 4, где мы аргументирован­
но показывали, что шифротекст не должен содержать избыточной
информации. Заметьте, что там мы защищались лишь от пассив­
ного нападения, в то время как здесь мы пытаемся противостоять
противнику со значительно большими возможностями.
Женг и Себерри первыми применили эту философию для созда­
ния практической криптосистемы, которая определяет современ­
ный подход к разработке шифрующих функций с открытым клю­
чом. Их работа имеет большое значение. Поэтому мы расскажем об
этих ранних попытках разработать стойкие криптосистемы с от­
крытым ключом в качестве иллюстрации такого подхода.
Первое, на что стоит обратить внимание: шифрование с откры­
тым ключом обычно используется для того, чтобы скрыть ключ,
с помощью которого будет шифроваться большое сообщение. Сле­
довательно, нет необходимости в шифровании сообщения, которое
принадлежит группе А (как в Эль-Гамаль). Однако можно восполь­
зоваться идеей Эль-Гамаль для передачи ключа, с помощью кото­
рого будет выработан сеансовый ключ, шифрующий фактическое
сообщение.
Глава 17. Доказуемая стойкость со случайным оракулом

Введем некоторые обозначения.
-А — нескрываемая группа простого порядка Q, порожденная
элементом G.
- V{H) — функция, которая по элементу Н группы генерирует
случайную строку битов. Ее часто называют функцией, про­
изводящей ключи.
- Н — хэш-функция со значением в /-битовых строках.
- Y = G^ — открытый ключ, соответствующий секретному
ключу X.

17.3.1.1, Схема Женга-Себерри 1, Чтобы зашифровать сооб­
щение т , вычисляют
1. A ; G { 1 , . . . , Q - 1 } .
2. z = V{Y^).
3. t - Н{т).
4. Ci = GK
5. C2 = z®{m\\t).
6. Шифротекст — (Ci,C2).
При расшифровании предпринимают такие шаги.
1. z' = V{Cf).
2. w = z' ® C2.
3. t^ — последние I битов строки w.
4. m' — первые i^w — I знаков строки w,
5. Если Н{т') = t', то m' — расшифрованное сообщение.
6. В противном случае алгоритм выдает сообщение о некоррект­
ности шифротекста.
Особенность криптосистемы состоит в добавлении к шифротексту
Эль-Гамаль специальной информации, а именно, зашифрованного
хэш-значения от открытого текста. Поскольку (предположительно)
хэш-функцию обратить трудно, практически невозможно написать
корректный шифротекст не зная соответствующий открытый. До­
писывание дополнительного хэш-значения вносит требуемую ши­
фротексту избыточность, которая тестируется расшифровывающей
функцией.
17.3.1.2, Схема Женга-Себерри 2, Вторая система использу­
ет универсальную одностороннюю хэш-функцию, которая является,
по существу, параметрическим набором хэш-функций Щ ci ^ i. Ее
17,3. Стойкость шифрующих алгоритмов

можно представлять себе как функцию, снабженную переключате­
лями, или как MAC.
Говоря более формально, универсальная односторонняя хэш-функ­
ция — это функция Hki снабженная переключателями, обладающая
следующим свойством: если противнику дан X и выбран наугад се­
кретный ключ fc, то противнику должно быть крайне сложно подо­
брать такой элемент у, что
Hk{y) = Нк{Х).
Чтобы зашифровать сообщение т во второй схеме Женга-Себерри,
мы вычисляем
1. fcG{l,...,Q-l}.
2. Z — # m левых знаков числа У(У^).
3. S — ? правых знаков числа У(У^).
4. Ci = G^.
5. С2 = Hs{m).
6. С^ = z®m,
7. Шифротекст — (Ci, Сг, Сз).
Оставим читателю выписать шаги расшифровывающей процедуры
в качестве полезного упражнения. Эта система аналогична первой,
но здесь хэш-значение сообщения не шифруется, а пересылается в
открытом виде. Эта система сложнее предыдущей, т. к. мы не зна­
ем, какой конкретно хэш-функцией или ключом получено соответ­
ствующее хэш-значение. Вторая схема Женга-Себерри очень близ­
ка системе DHIES^ которая на данный момент считается наилучшей
практической реализацией функции шифрования Эль-Гамаль.
17.3.1.3. Схема Женга-Себерри 3. В третьей и последней схе­
ме Женга и Себерри эксплуатируется /^й'Л-подобная подпись, или
«символ» шифруемого сообщения. Схема работает, комбинируя ши­
фрование Эль-Гамаль с Х^й'Л-подписью, однако открытый ключ схе­
мы подписи DSA носит эфемерный характер и составляет часть
шифротекста. Здесь мы также ограничимся шагами процедуры ши­
фрования, оставив читателю продумывание противоположного про­
цесса.

1. A ; , ^ G { 1 , . . . , Q - 1 } .
2. г = Y^˜^K
г. z = G(r).
4. Ci = G^.
430 Глава 17. Доказуемая стойкость со случайным оракулом

5. С2 = GK
6. Съ = {Н{т)-^хг)/к (modQ).
7. С4 = Z -\- т.
8. Шифротекст — (Ci,(^2,С3,(74).
Женг и Себерри доказали стойкость своих схем при очень силь­
ных предположениях, а именно, они считали, что пространство ши-
фротекстов взаимно однозначно соответствует пространству сооб-
ш;ений, что является близким предположению о текстозависимости
алгоритма шифрования. Однако можно показать, что первая из схем
не стойка. Предположим, что на стадии поиска противник выда­
ет два сообш;ения Mi и М2. Затем выбирают скрываемый бит b и
предлагают противнику сообщение Мь в зашифрованном виде, т. е.
шифротекст

С = (СьСз) = (с>',гф{Мь\\Н{Мь))) .
Противник на стадии гипотезы может предпринять следуюш;ие опе­
рации. Сначала он генерирует новое сообщение Мз, отличное от Mi
и М2, но совпадающее с ними по длине. Затем нападающий требует
от оракула расшифровать шифротекст
(Ci,C2 Ф (MillH(Mi)) ф (Мз||Я(Мз))).
Если Ъ = 1, то этот шифротекст — корректная шифрованная версия
сообщения Мз. Поэтому оракул, расшифровав его, должен получить
Мз. А если Ь = О, то шифротекст с очень малой долей вероятности
будет шифрованной версией хоть какого-то сообщения, не говоря
уже о Мз. Таким образом мы получаем алгоритм, который за поли­
номиальное время определяет значение скрываемого бита Ь.

17.3.2. RSA-OAEP
Напомним, что необработанная RSA-фуакция не дает семантически
стойкой шифрующей системы даже в отношении пассивного про­
тивника. Для создания стойкой системы нам нужно или добавлять
избыточную информацию к открытому тексту перед шифровани­
ем, или вставлять лишние данные в сам шифротекст. Кроме того, в
целях получения недетерминированного процесса, добавляемые кус­
ки должны выбираться случайным образом. В RSA это достигается
использованием специальной пополняющей схемы, и за последние
годы было предложено много таких схем. Однако некоторые из са­
мых ранних предложений на сегодняшний день считаются слишком
слабыми.
17.3. Стойкость шифрующих алгоритмов

Одна из наиболее удачных на данный момент пополняющих схем
была изобретена Белларе и Рогавей. Она называется оптимизиро­
ванным асимметричным пополнением шифрования или ОАЕР (от
англ. Optimized Asymmetric Encryption Padding). ОАЕР— пополня­
ющая схема, которую можно использовать с любой односторонней
функцией с секретом, в частности, с Д5Л-функцией. Когда ее ис­
пользуют совместно с RSA., то обозначают RSA-OAEP.
В первое время после создания RSA-OAEP считалось, что эта
система является текстозависимой, но вскоре стало ясно, что это
не так. Однако с помощью модели случайного оракула можно пока­
зать, что RSA-OAEP семантически стойка в отношении адаптивной
атаки с выбором шифротекста.
Расскажем сначала в общем виде о процедуре шифрования ОАЕР.
Пусть / — односторонняя функция с секретом, которая отобража­
ет fc-битовые строки в ^-битовые строки. Если к = 1024, то такой
функцией можно считать Д5Л-функцию С = т^. Пусть ко и ki
такие числа, что нереализуемо (например, ko^ki > 128).
Положим п = к — ко — ki и обозначим через
G : {0,1}^« {0,1Г+^1, Я : {0,1}^+^^ {0,1}^«
хэш-функции. Пусть т — сообщение, состоящее из п битов. Заши­
фруем его, используя функцию
е ( т ) = /({ш||0^^ е а ( г ) } | | { г е Я ( т 0 ^ 1 e G ( r ) ) } ) ,
где
- т||0^^ означает ш, за которым стоит ki нулей,
- г — случайная строка битов длины fco,
- знак 1 означает конкатенацию строк.
1
Можно представлять себе ОАЕР как двухэтапную сеть Фейстеля
(см. рис. 17.1).
Чтобы расшифровать сообщение е{т)^ мы вычисляем

А = {Т\\{г е Н{Т)}} = {{т\\0^' в G{r)}\\{r 0 Н{т\\0^' 0 G(r))}} .
Таким образом, мы знаем
Т = т\\0^' ®G{r).
Следовательно, можно вычислить Н{Т) и найти г, зная г © Н{Т).
По г получаем G{r) и восстанавливаем сообщение т. Заметим, что
нам необходимо проверить, действительно ли строка T®G{r) окан­
чивается fci нулями. Если это не так, то мы должны сделать вывод,
что соответствующий шифротекст некорректен.
Глава 17. Доказуемая стойкость со случайным оракулом


Сформулируем и докажем основной результат, посвященный си­
стеме RSA^OAEP.

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

(Z/iVZ)*,
/:
{s\\t)^ (modTV).
Заметим, что такую функцию невозможно выразить математиче­
ской формулой^, но предположим, что мы можем это сделать и опре­
делим RSA-OAEP как
S = {т\\0^') е G{r), t = r® H{s),



Можно доказать, что предположения
RSA эквивалентны частичной односто­
ронности функции / в том смысле, что
задача восстановления s по значению
т\\о^^фО(г)] f{s^t) так же сложна, как и вычисле­
ние всего прообраза (s^t) по f{s^t). По­
этому мы попытаемся встроить алго­
ритм Л, взламывающий функцию RSA-
m II 0^1 ФС(г) I гф Н(т \\ Ф® G(r))\ OAEP^ в алгоритм ВА-, восстанавли­
вающий частичный прообраз функции
Р и с . 1 7 . 1 . ОА ЕР как сеть
RSA, В частности, фиксировав модуль
Фейстеля
j?V, на вход алгоритма В А подают эле­
мент С* = f{s*^t*) и требуют опреде­
лить S*.
Алгоритм В А вызывает стадию поиска противника А для гене­
рирования двух сообщений MQ И Ml. После этого В А выбирает бит
^Не очень ясно, что тут автор имеет в виду, поскольку элементы множества
{0,1}"^ можно воспринимать как двоичную запись натуральных чисел, лежащих
от О до 2^+^ - 1. Запись {s\\t) с s е {О, l}^+*i и t е {О,!}*'^ означает число
5 . 2*^0 + t. Поэтому формула для функции / — f{s, t) = (s - 2^^ Н-1)^ (modAT). —
Прим. перев.
17.3. Стойкость шифрующих алгоритмов

b и предполагает, что С* — шифрованная версия сообщения М^. За­
тем шифротекст С* передается на стадию гипотезы нападающего
алгоритма А, и тот пытается определить значение Ь, Во время ра­
боты А алгоритм В А обязан отвечать на хэш-запросы в отношении
хэш-функций G и Н и подменять собой расшифровывающий оракул.
Для последовательности ответов В А ведет два списка — Я-список
и G-список, — занося туда все хэш-запросы относительно значений
функций Н и G соответственно. На запросы противника алгоритм
В А отвечает по определенной схеме.
Запрос G(r). Для каждого А из Н-сииска, проверяется истин­
ность равенства
С* = / ( А , Г е Я ( А ) ) .
- Если оно верно, то мы частично обратили функцию / , что нам
и было нужно. Мы все еще можем моделировать функцию G и
положим
G(r) = А е ( М б | | 0 ^ 0 .

- Если равенство ложно д^ля всех А из Я-списка, то мы произ­
вольно выбираем 0{Г) из области значений, соблюдая равно­
мерную плотность распределения вероятности выбора.
Запрос Н{А). Выбирается произвольное случайное значение Н{А)
из множества значений функции Н^ и для всех Г из G-списка про­
веряется равенство
С* = / ( Д , Г ф Я ( Д ) ) .
Если для какого-нибудь Г получится верное равенство, то мы до­
стигнем своей цели.
Запрос о расшифровании С. Ищем в наших G- и iJ-cnncKax та­
кую пару Г, А, что числа
Е-А, в = Г©Я(А) и Л = С(Г)еА
удовлетворяют следующим условиям: С = / ( Е , в ) и fci наименьших
значащих бит числа Л равны нулю. Найдя такую пару, мы даем в
качестве соответствующего открытого текста п старших значащих
цифр числа Л. Если наш поиск окончится неудачей, то мы ответим,
что шифротекст некорректен.
Заметим, что передав шифротекст, полученный корректным пу­
тем (т. е. с помощью вызова функций G и Н ис применением закон­
ного шифрующего алгоритма), описанному выше расшифровываю­

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

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

ОГЛАВЛЕНИЕ

Следующая >>