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

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

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

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

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

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

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

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

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

• Алиса генерирует эффективное описание циклической группы порядка с двумя отдельными случайными генераторами . ${\ 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 е = ч ^ {к} м}$
  • ${\ Displaystyle \ альфа = Н (и_ {1}, и_ {2}, е)}$ , где 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 \ альфа = Н (и_ {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}$

Рекомендации

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