Криптосистема Крамера – Шупа - Википедия - Cramer–Shoup cryptosystem

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

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

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

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

Крамер-Шуп был не первой схемой шифрования, обеспечивающей защиту от атак с адаптивным выбранным зашифрованным текстом. Наор – Юнг, Ракофф – Саймон и Долев – Дворк – Наор предложили доказуемо безопасные преобразования из стандартных схем (IND-CPA) в схемы IND-CCA1 и IND-CCA2. Эти методы безопасны при стандартном наборе криптографических предположений (без случайных оракулов), однако они полагаются на сложные доказательство с нулевым разглашением методы и неэффективны с точки зрения вычислительных затрат и размера зашифрованного текста. Множество других подходов, включая Белларе /Rogaway с 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}$ $k$ из ${ displaystyle {0, ldots, q-1 }}$ ${0, ldots, q-1 }$ , затем вычисляет:
- ${ displaystyle u_ {1} = {g} _ {1} ^ {k}, u_ {2} = {g} _ {2} ^ {k}}$
- ${ Displaystyle е = ч ^ {к} м}$
- ${ Displaystyle альфа = Н (и_ {1}, и_ {2}, е)}$ , куда ЧАС() это универсальная односторонняя хеш-функция (или стойкий к столкновениям криптографическая хеш-функция, что является более сильным требованием).
- ${ 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 альфа = Н (и_ {1}, и_ {2}, е) ,}$ и подтверждает, что ${ displaystyle {u} _ {1} ^ {x_ {1}} u_ {2} ^ {x_ {2}} ({u} _ {1} ^ {y_ {1}} u_ {2} ^ {y_ {2}}) ^ { alpha} = v ,}$ . Если этот тест не пройден, дальнейшее дешифрование прерывается, и вывод отклоняется.
В противном случае Алиса вычисляет открытый текст как ${ Displaystyle м = е / ({и} _ {1} ^ {z}) ,}$ .

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

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

, и

{ Displaystyle м = е / ч ^ {к}. ,}

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