Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
2. Алиса и Боб должны знать карты, которыми они владеют, а другие игроки не должны знать, какие карты находятся на руках их партнеров.
3. Алиса и Боб должны подозреваться в мошенничестве и нарушении правил протокола.
4. Алиса и Боб должны иметь возможность проверять, честно ли была сыграна предыдущая игра.
Идея, лежащая в основе мысленного покера, заключается в применении шифра, обладающего свойством коммутативности. Применяя такой шифр, Алиса и Боб могут дважды шифровать сообщение, используя свои секретные ключи, и должны дважды расшифровывать его. Пусть
С = ЕХ(М) и М = DX{C)
обозначают алгоритмы шифрования и расшифровки, выполняемые пользователем X. Коммутативное свойство шифра состоит в том, что для любого сообщения М выполняются следующие уравнения.
М = Da[Pb{Ea{Eb(M)))) = DB{DA(EB(EA(M)))). (14.3.1)
Иначе говоря, исходное сообщение можно восстановить путем двойной расшифровки независимо от порядка шифрования.
Для простоты предположим, что Алиса и Боб решили раздать по одной карте, используя колоду, состоящую из трех карт. Способ честной раздачи карт описывается протоколом 14.2. Совершенно очевидно, что его можно распространить на любое количество карт.
522
Часть V. Методы формального доказательства стойкости
Протокол 14.2. Протокол честной раздачи карт при игре в мысленный покер
ПРЕДВАРИТЕЛЬНЫЕ УСЛОВИЯ:
Алиса и Боб согласовали коммутативный шифр, обладающий свой^ ством (14.3.1), и сгенерировали свои секретные ключи шифрования. Колода состоит из трех карт: Mi, Мг и Мз.
ЦЕЛЬ: Честная раздача по одной карте каждому игроку по правилам 1-4.
1. Алиса шифрует три карты следующим образом: d = Ea(Mi), где г = 1,2,3. Она посылает Бобу эти три зашифрованных текста в случайном порядке. (* Передача зашифрованных текстов в случайном порядке эквивалентна перетасовке колоды. *)
2. Боб случайным образом извлекает один из зашифрованных текстов. Обозначим его через С. Затем он дважды шифрует его как СС = Ев(С), слу-| чайным образом извлекает другой текст, обозначенный как С", и отсылаем зашифрованные тексты СС и С Алисе.
(* Символы СС обозначают карту, принадлежащую Бобу, а символ С — карту, выданную Алисе. Оставшаяся зашифрованная карта игнорируется. *¦
3. Алиса расшифровывает тексты СС и С'. Результат расшифровки текста С* обозначает ее карту, а расшифровка текста СС, обозначаемая как С", -| карту Боба. Текст С" возвращается Бобу.
4. Боб расшифровывает текст С" и выясняет, какую карту он получил. (* Теперь можно приступать к игре. *)
14.3.2 Анализ стойкости с точки зрения учебной криптографии
Предположим на время, что в криптосистеме, описанной протоколом 14.2, обе операции однократного и двойного шифрования являются достаточно стойкими. Говоря, что эта криптосистема является достаточно стойкой, мы имеем в виду, что обладая заданным исходным текстом (соответственно зашифрованным текЗ стом), но не зная подлинного ключа шифрования (соответственно расшифровки]) полиномиально ограниченный Злоумышленник не может создать правильный за* шифрованный текст (соответственно не может восстановить исходное сообщение). Такое понятие стойкости полностью соответствует принципу "все или ни! чего", на котором построена учебная криптография (см. раздел 8.2). Проведем анализ стойкости протокола 14.2, придерживаясь принципов учебной криптографии и учитывая правила честной игры в мысленный покер.
Глава 14. Определения формальной и сильной стойкости криптосистем... 523
После выполнения протокола 14.2 складывается следующая ситуация.
• Поскольку на первом шаге Алиса тасует колоду, оба игрока с одинаковой вероятностью получают одну из карт, принадлежащих множеству {Mi, М2, Мз}. Обратите внимание на то, что Алиса стремится хорошо перетасовать колоду, чтобы Боб не получил преимущества. Итак, первое условие честной раздачи выполнено.
• Каждый из двух игроков после двойной расшифровки узнает свою карту, но не знает, какая карта досталась сопернику. Таким образом, второе правило честной раздачи также выполнено.
• Очевидно, что в протоколе учтена возможность мошенничества со стороны игроков. Следовательно, третье правило честной раздачи также выполнено.
Выполнение четвертого правила зависит от того, допускает ли криптосистема, использованная в протоколе, честную верификацию оконченной игры. Шамир и его соавторы предложили применить один из вариантов криптосистемы RSA (см. раздел 8.5), в котором обе стороны до завершения игры сохраняют в тайне показатели степени, использованные при шифровании и расшифровке, а после ее окончания раскрывают их для проверки.
Пусть N — общий модуль в криптосистеме RSA. Алиса и Боб знают разложение числа N на множители. Обозначим через (ел, dA) показатели степеней, использованные при шифровании и расшифровке Алисой, а через (ев, d-в) — показатели, применяемые Бобом. Знание разложения числа N на простые множители позволяет Алисе (Бобу) найти число dA по заданному числу еА (число йв — по заданному числу ев) с помощью сравнения
exdx = l(mod <}>{N)), (14.3.2)
где символ X обозначает игрока А или В. Для пользователя X получаем следующие формулы.
