Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
2. Если (<7i,<72jm1i^2) ^ D, то оклик С* шифрует текст mj, в теоретико-информационном смысле по Шеннону (т.е. с помощью идеального шифрования (см. раздел 7.5)). Иначе говоря, зашифрованный текст равномерно распределяется по всему пространству зашифрованных текстов. Идеальное шифрование по Шеннону рассматривается в разделе 15.3.3.5. Более того, в разделе 15.3.3.5 будет показано, что качество идеального шифрования по Шеннону невозможно скомпрометировать с помощью обучения атакующего алгоритма. Итак, в этом случае атакующий алгоритм А не имеет никакого преимущества!
586
Часть V. Методы формального доказательства стойкости
Именно разница между преимуществом атакующего алгоритма Л в указанных двух случаях позволяет ему помочь Саймону решить задачу принятия решений Диффи-Хеллмана.
Перейдем к алгоритму редукции.
15.3.3.2 Редукция
Алгоритм редукции состоит из следующих этапов.
1. Получив четверку (д\, д%, щ, и2) Е G4, Саймон создает открытый ключ криптосистемы Крамера-Шоупа и посылает его атакующему Л. Метод создания открытого ключа описан в разделе 15.3.3.3.
2. Саймон проводит для атакующего Л курс обучения криптоанализу, который необходимо пройти до получения оклика. Метод, с помощью которого Саймон имитирует процедуру расшифровки, выполняемую оракулом О, описан в разделе 15.3.3.5.
3. Саймон получает от атакующего алгоритма Л пару подобранных открытых текстов то и mi, подбрасывает идеальную монету Ъ Е с/{0,1}, шифрует текст ть, необходимый для создания зашифрованного оклика С*, и посылает этот оклик атакующему Л. Метод, с помощью которого Саймон имитирует процедуру шифрования, выполняемую оракулом О, описан в разделе 15.3.3.5.
4. Имитируя процедуру расшифровки, выполняемую оракулом О, Саймон продолжает курс обучения атакующего Л, который необходимо пройти после получения оклика. Метод, с помощью которого Саймон имитирует процедуру расшифровки, выполняемую оракулом О, описан в разделе 15.3.3.5.
5. В заключение Саймон получает от атакующего алгоритма Л результат осмысленного угадывания бита Ъ. Теперь Саймон способен ответить на вопрос: (si,р2,«ъ t/г) 6D или (ffi,fl2,wi,w2) ? D?
Процесс редукции продемонстрирован на рис. 15.3.3.3. Он представляет собой / игровую атаку IND-CCA2, разыгранную между Саймоном и атакующим алгоритмом Л. Саймон контролирует все линии связи алгоритма Л с внешним миром, поэтому атакующий может общаться только с Саймоном. Со стороны Саймона игровая атака является имитацией. Однако, как будет показано в дальнейшем, эта имитация имеет идеальное качество, и, следовательно, атакующий алгоритм Л не может отличить ее от реальной атаки.
15.3.3.3 Создание открытого ключа
Используя четверку (gi,g2jUi,U2) Е G4, Саймон создает открытый ключ. Для j этого он генерирует случайные числа
ж2,3/1, У2, zx, z2 Е с/[0, q)
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
587
Схема шифрования и открытый ключ
Курс обучения криптоанализу
С*
Курс обучения криптоанализу
Осмысленное угадывание
Схема шифрования и открытый ключ
А
Имитация курса обучения
т01.т С
С* А
И
Имитация курса обучения криптоанализу и О н
Осмысленное
угадывание
[g,.g2.Ul-u2)
Да,
является четверкой Диффи-Хеллмана Нет.
(8,.e,."j.«2)
не является четверкой Диффи-Хеллмана
Рис. 15.4. Редукция задачи DDH к атаке на криптосистему Крамера-Шоупа
и вычисляет значения
с^9Х19?, d^gfaf, h+-g?g?. (15.3.2)
Кроме того, Саймон выбирает криптографическую функцию хэширования Н. Открытый ключ, предназначенный для атакующего алгоритма Л, имеет вид
92, с, d,h, Н).
588
Часть V. Методы формального доказательства стойкости
Закрытый ключ, который использует Саймон, имеет вид
(ЖЬ Ж2, 2/1, У2,-21,22)-
Читатель мог уже заметить, что часть открытого ключа, а именно, компонент h, отличается от компонента, указанного в алгоритме 15.3.2.1. Однако это не проблема. Сначала убедимся, что число h является абсолютно корректным компонентом открытого ключа.
Заметим, что в выражении h = gZlg22, где д\ ф 1, элемент д\ является порождающим элементом группы G (следствие 5.3). Таким образом, существует число w Е [0, q), такое что д2 = д\". Следовательно, для z = z\ + wz2(mod q)
h = gZl+WZ2=gl (15.3.3)
Итак, действительно, число h полностью соответствует процедуре создания ключа в алгоритме 15.3.2.1.
Читатель может задать вопрос:
"Как Саймон может использовать число z = z\ + wz2(moa\q) в процедуре расшифровки, если ему неизвестно число w = logffl g2(mod q)T\
В главе 15.3.3.5 будет показано, что для любого корректно зашифрованного текста, соответствующего указанному открытому ключу, Саймон может применять число z = z\ + wz2(modq) для расшифровки текста как "правильный" показатель степени, даже не зная его.
15.3.3.4 Имитация процедуры шифрования
Получив от атакующего алгоритма Л два подобранных открытых сообщения то и mi, Саймон подбрасывает идеальную монету Ьб[/{0,1} и шифрует текст тъ'-
е = uZluZ2mb, а = Я (ui, из, е), v = иХ1+У1аиХ2+У2а.
Зашифрованным окликом С* является четверка (ui,u2,e,v).
Отметим, что эта процедура шифрования также отличается от обычной, в которой значение е вычисляется по формуле
