Криптосистема Крамера–Шоупа

Алгоритм шифрования с асимметричным ключом

Система Крамера–Шоупа представляет собой алгоритм шифрования с асимметричным ключом и была первой эффективной схемой, доказавшей свою безопасность против атаки с адаптивным выбранным шифротекстом с использованием стандартных криптографических предположений. Ее безопасность основана на вычислительной неразрешимости (широко принятой, но не доказанной) предположения о решении Диффи–Хеллмана . Разработанная Рональдом Крамером и Виктором Шоупом в 1998 году, она является расширением криптосистемы Эль-Гамаля . В отличие от Эль-Гамаля, который чрезвычайно податлив, Крамер–Шоуп добавляет другие элементы, чтобы гарантировать неподатливость даже против находчивого злоумышленника. Эта неподатливость достигается за счет использования универсальной односторонней хэш-функции и дополнительных вычислений, в результате чего получается шифротекст, который вдвое больше, чем в Эль-Гамале.

Адаптивные атаки на основе выбранного шифротекста

Определение безопасности, достигнутое Крамером–Шоупом, формально называется « неразличимостью при атаке с адаптивным выбранным шифртекстом » (IND-CCA2). Это определение безопасности в настоящее время является самым сильным определением, известным для криптосистемы с открытым ключом: оно предполагает, что злоумышленник имеет доступ к оракулу дешифрования, который расшифрует любой шифртекст с помощью секретного ключа дешифрования схемы. «Адаптивный» компонент определения безопасности означает, что злоумышленник имеет доступ к этому оракулу дешифрования как до, так и после того, как он наблюдает определенный целевой шифртекст для атаки (хотя ему запрещено использовать оракул, чтобы просто расшифровать этот целевой шифртекст). Более слабое понятие безопасности против атак с неадаптивным выбранным шифртекстом (IND-CCA1) позволяет злоумышленнику получить доступ к оракулу дешифрования только до наблюдения за целевым шифртекстом.

Хотя было хорошо известно, что многие широко используемые криптосистемы были небезопасны против такого злоумышленника, в течение многих лет разработчики систем считали атаку непрактичной и в основном теоретической. Это начало меняться в конце 1990-х годов, особенно когда Дэниел Блейхенбахер продемонстрировал практическую атаку с адаптивным выбранным шифротекстом против SSL- серверов, используя форму шифрования RSA . ^[1]

Cramer–Shoup не была первой схемой шифрования, обеспечивающей безопасность от атаки с адаптивным выбранным шифротекстом. Naor–Yung, Rackoff–Simon и Dolev–Dwork–Naor предложили доказуемо безопасные преобразования из стандартных схем (IND-CPA) в схемы IND-CCA1 и IND-CCA2. Эти методы безопасны при стандартном наборе криптографических предположений (без случайных оракулов), однако они опираются на сложные методы доказательства с нулевым разглашением и неэффективны с точки зрения вычислительных затрат и размера шифротекста. Различные другие подходы, включая OAEP Беллара / Рогауэя и Фудзисаки–Окамото, достигают эффективных конструкций с использованием математической абстракции, известной как случайный оракул . К сожалению, для реализации этих схем на практике требуется подстановка некоторой практической функции (например, криптографической хэш-функции ) вместо случайного оракула. ​​Растущее количество доказательств свидетельствует о небезопасности этого подхода, ^[2] хотя никаких практических атак против развернутых схем продемонстрировано не было.

Криптосистема

Крамер-Шоупа состоит из трех алгоритмов: генератора ключей, алгоритма шифрования и алгоритма дешифрования.

Генерация ключей

• Алиса генерирует эффективное описание циклической группы порядка с помощью двух различных случайных генераторов . ${\displaystyle G}$ ${\displaystyle q}$ ${\displaystyle g_{1},g_{2}}$
• Алиса выбирает пять случайных значений из . ${\displaystyle ({x}_{1},{x}_{2},{y}_{1},{y}_{2},z)}$ ${\displaystyle \{0,\ldots ,q-1\}}$
• Алиса вычисляет . ${\displaystyle c={g}_{1}^{x_{1}}g_{2}^{x_{2}},d={g}_{1}^{y_{1}}g_{2}^{y_{2}},h={g}_{1}^{z}}$
• Алиса публикует , вместе с описанием , как свой открытый ключ . Алиса сохраняет как свой секретный ключ . Группа может быть разделена между пользователями системы. ${\displaystyle (c,d,h)}$ ${\displaystyle G,q,g_{1},g_{2}}$ ${\displaystyle (x_{1},x_{2},y_{1},y_{2},z)}$

Шифрование

Чтобы зашифровать сообщение для Алисы с помощью ее открытого ключа , ${\displaystyle m}$ ${\displaystyle (G,q,g_{1},g_{2},c,d,h)}$

• Боб преобразуется в элемент . ${\displaystyle m}$ ${\displaystyle G}$
• Боб выбирает случайное число из , затем вычисляет: ${\displaystyle k}$ ${\displaystyle \{0,\ldots ,q-1\}}$
  • ${\displaystyle u_{1}={g}_{1}^{k},u_{2}={g}_{2}^{k}}$
  • ${\displaystyle e=h^{k}m}$
  • ${\displaystyle \alpha =H(u_{1},u_{2},e)}$, где H () — универсальная односторонняя хеш-функция (или устойчивая к коллизиям криптографическая хеш-функция , что является более строгим требованием).
  • ${\displaystyle v=c^{k}d^{k\alpha }}$
• Боб отправляет зашифрованный текст Алисе. ${\displaystyle (u_{1},u_{2},e,v)}$

Расшифровка

Чтобы расшифровать зашифрованный текст с помощью секретного ключа Алисы , ${\displaystyle (u_{1},u_{2},e,v)}$ ${\displaystyle (x_{1},x_{2},y_{1},y_{2},z)}$

• Алиса вычисляет и проверяет, что . Если этот тест не пройден, дальнейшее расшифровывание прерывается и вывод отклоняется. ${\displaystyle \alpha =H(u_{1},u_{2},e)\,}$ ${\displaystyle {u}_{1}^{x_{1}}u_{2}^{x_{2}}({u}_{1}^{y_{1}}u_{2}^{y_{2}})^{\alpha }=v\,}$
• В противном случае Алиса вычисляет открытый текст как . ${\displaystyle m=e/({u}_{1}^{z})\,}$

На этапе расшифровки правильно расшифровывается любой правильно сформированный шифртекст, поскольку

${\displaystyle {u}_{1}^{z}={g}_{1}^{kz}=h^{k}\,}$, и ${\displaystyle m=e/h^{k}.\,}$

Если пространство возможных сообщений больше размера , то Крамера–Шоупа можно использовать в гибридной криптосистеме для повышения эффективности при работе с длинными сообщениями. ${\displaystyle G}$

Ссылки

1. Дэниел Блейхенбахер. Атаки с использованием выбранного шифротекста против протоколов, основанных на стандарте шифрования RSA PKCS #1. Достижения в криптологии – CRYPTO '98. [1]
2. Ран Канетти, Одед Голдрайх , Шай Халеви. Методология случайного оракула, пересмотр. Журнал ACM, 51:4, страницы 557–594, 2004.

• Рональд Крамер и Виктор Шоуп . «Практическая криптосистема с открытым ключом, доказуемо защищенная от атаки с адаптивным выбранным шифротекстом». в трудах Crypto 1998, LNCS 1462, стр. 13ff (ps,pdf)
• Игрушечные реализации Крамера–Шоупа в Emacs Lisp и Java
• Репортаж 1998 года о публикации Крамера и Шупа в Wired News и в Crypto-Gram Брюса Шнайера
• Рональд Крамер и Виктор Шоуп : «Универсальные доказательства хэширования и парадигма для выбранного шифротекста, безопасного шифрования с открытым ключом». в трудах Eurocrypt 2002, LNCS 2332, стр. 45–64. Полная версия (pdf)