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

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

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

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

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

Крамер-Шоуп был не первой схемой шифрования, обеспечивающей защиту от атак с использованием адаптивного выбранного зашифрованного текста. Наор-Юнг, Ракофф-Саймон и Долев-Дворк-Наор предложили доказуемо безопасные преобразования стандартных схем (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. Достижения в криптологии – КРИПТО '98. [1]
2. Ран Канетти, Одед Голдрейх , Шай Халеви. Возвращение к методологии случайного оракула. Журнал ACM, 51:4, страницы 557–594, 2004 г.

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