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

Система Крамера–Шоупа представляет собой алгоритм шифрования с асимметричным ключом и была первой эффективной схемой, доказавшей свою безопасность против атаки с адаптивным выбранным шифротекстом с использованием стандартных криптографических предположений. Ее безопасность основана на вычислительной неразрешимости (широко принятой, но не доказанной) предположения о решении Диффи–Хеллмана . Разработанная Рональдом Крамером и Виктором Шоупом в 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 д}$ ${\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 м}$${\displaystyle (G,q,g_{1},g_{2},c,d,h)}$

• Боб преобразуется в элемент .${\displaystyle м}$${\displaystyle G}$
• Боб выбирает случайное число из , затем вычисляет:${\displaystyle к}$${\displaystyle \{0,\ldots ,q-1\}}$
  • ${\displaystyle u_{1}={g}_{1}^{k},u_{2}={g}_{2}^{k}}$
  • ${\displaystyle e=h^{k}м}$
  • ${\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}$

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