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

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

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

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

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

Крамер-Шоуп был не первой схемой шифрования, обеспечивающей защиту от атак с использованием адаптивного выбранного зашифрованного текста. Наор-Юнг, Ракофф-Саймон и Долев-Дворк-Наор предложили доказуемо безопасные преобразования стандартных схем (IND-CPA) в схемы IND-CCA1 и IND-CCA2. Эти методы безопасны при стандартном наборе криптографических предположений (без случайных оракулов), однако они основаны на сложных методах доказательства с нулевым разглашением и неэффективны с точки зрения вычислительных затрат и размера зашифрованного текста. Множество других подходов, в том числе Белларе / Рогэуэя OAEP случайный и Фудзисаки-Окамото, позволяют достичь эффективных конструкций с использованием математической абстракции, известной как оракул . какой-либо практической функцией (например, криптографической хэш-функцией К сожалению, для реализации этих схем на практике требуется замена случайного оракула ). Растущее количество данных свидетельствует о ненадежности такого подхода. ^{[ 2 ]} хотя никаких практических атак против развернутых схем не было продемонстрировано.

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

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

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

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

Шифрование

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

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

Расшифровка

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

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

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

{u}_{1}^{z}={g}_{1}^{kz}=h^{k}\,

, и

m=e/h^{k}.\,

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

Ссылки

^ Дэниел Блейхенбахер. Атаки с использованием выбранного зашифрованного текста против протоколов, основанных на стандарте шифрования RSA PKCS #1. Достижения в криптологии – КРИПТО '98. [1]
^ Ран Канетти, Одед Голдрейх , Шай Халеви. Методология случайного оракула, новый взгляд . Журнал 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)

[1] Дэниел Блейхенбахер. Атаки с использованием выбранного зашифрованного текста против протоколов, основанных на стандарте шифрования RSA PKCS #1. Достижения в криптологии – КРИПТО '98. [1]

[2] Ран Канетти, Одед Голдрейх , Шай Халеви. Методология случайного оракула, новый взгляд . Журнал ACM, 51:4, страницы 557–594, 2004 г.

[ 1 ]

[ 2 ]