Система Крэмера — Шупа: Криптографическая защита от адаптивных атак с выбранным шифротекстом.

Введение

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

Адаптированные атаки шифровальщиков

Определение безопасности, достигнутое Cramer–Shoup, официально называется «неразличимость при адаптивной атаке с выбранным шифротекстом» (IND CCA2). В настоящее время это самое сильное известное определение безопасности для криптосистемы с открытым ключом: оно предполагает, что злоумышленник имеет доступ к оракулу дешифрования, который будет дешифровать любой шифротекст с использованием секретного ключа дешифрования схемы. «Адаптивный» компонент определения безопасности означает, что злоумышленник имеет доступ к этому оракулу дешифрования как до, так и после наблюдения за конкретным целевым шифротекстом для атаки (хотя ему запрещено использовать оракул для простого дешифрования этого целевого шифротекста). Более слабое понятие безопасности от неадаптивных атак с выбранным шифротекстом (IND CCA1) позволяет злоумышленнику получить доступ к оракулу дешифрования только перед наблюдением за целевым шифротекстом. Хотя было хорошо известно, что многие широко используемые криптосистемы уязвимы для таких атак, в течение многих лет разработчики систем считали атаку непрактичной и в основном теоретической. Это начало меняться в конце 1990-х годов, особенно когда Дэниел Блейхенбахер продемонстрировал практическую адаптивную атаку с выбранным шифротекстом против серверов SSL, используя форму шифрования RSA. Cramer–Shoup не была первой схемой шифрования, обеспечивающей безопасность от адаптивной атаки с выбранным шифротекстом. Наор–Юнг, Раккофф–Симон и Долев–Дворк–Наор предложили доказуемо безопасные преобразования из стандартных схем (IND CPA) в схемы IND CCA1 и IND CCA2. Эти методы безопасны при стандартном наборе криптографических предположений (без случайных оракулов), однако они опираются на сложные методы доказательства с нулевым разглашением и неэффективны с точки зрения вычислительных затрат и размера шифротекста. Различные другие подходы, включая OAEP от Белларэ/Рогавея и схему Фудзисаки–Окамото, достигают эффективных конструкций с использованием математической абстракции, известной как случайный оракул. К сожалению, для практической реализации этих схем требуется замена случайного оракула на некоторую практическую функцию (например, криптографическую хеш-функцию). Растущее количество данных свидетельствует о небезопасности этого подхода, хотя практических атак на развернутые схемы пока не продемонстрировано.

The definition of security achieved by Cramer–Shoup is formally termed "indistinguishability under adaptive chosen ciphertext attack" (IND CCA2). This security definition is currently the strongest definition known for a public key cryptosystem: it assumes that the attacker has access to a decryption oracle which will decrypt any ciphertext using the scheme's secret decryption key. The "adaptive" component of the security definition means that the attacker has access to this decryption oracle both before and after he observes a specific target ciphertext to attack (though he is prohibited from using the oracle to simply decrypt this target ciphertext). The weaker notion of security against non adaptive chosen ciphertext attacks (IND CCA1) only allows the attacker to access the decryption oracle before observing the target ciphertext. Though it was well known that many widely used cryptosystems were insecure against such an attacker, for many years system designers considered the attack to be impractical and of largely theoretical interest. This began to change during the late 1990s, particularly when Daniel Bleichenbacher demonstrated a practical adaptive chosen ciphertext attack against SSL servers using a form of RSA encryption. Cramer–Shoup was not the first encryption scheme to provide security against adaptive chosen ciphertext attack. Naor–Yung, Rackoff–Simon, and Dolev–Dwork–Naor proposed provably secure conversions from standard (IND CPA) schemes into IND CCA1 and IND CCA2 schemes. These techniques are secure under a standard set of cryptographic assumptions (without random oracles), however they rely on complex zero knowledge proof techniques, and are inefficient in terms of computational cost and ciphertext size. A variety of other approaches, including Bellare/Rogaway's OAEP and Fujisaki–Okamoto achieve efficient constructions using a mathematical abstraction known as a random oracle. Unfortunately, to implement these schemes in practice requires the substitution of some practical function (e. g., a cryptographic hash function) in place of the random oracle. A growing body of evidence suggests the insecurity of this approach, although no practical attacks have been demonstrated against deployed schemes.

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

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

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

Алиса генерирует эффективное описание циклической группы порядка *n* с двумя различными случайными генераторами *g₁* и *g₂*. Алиса выбирает пять случайных значений *x₁, x₂, x₃, x₄, x₅* из *Zₙ*. Алиса вычисляет *h = g₁ˣ₁g₂ˣ₂g₁ˣ₃g₂ˣ₄g₁ˣ₅*. Алиса публикует *h*, вместе с описанием группы, в качестве своего открытого ключа. Алиса сохраняет *x₁, x₂, x₃, x₄, x₅* в качестве своего секретного ключа. Группа может быть использована всеми пользователями системы.