Схема Cramer-Shoup

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

История

Схема Cramer-Shoup была разработана в ответ на потребность в криптосистемах, устойчивых к атакам на основе подобранного шифротекста (CCA). До её появления существовали схемы, такие как RSA-OAEP, которые доказывали стойкость в модели случайного оракула, но не были полностью адаптивными. Крамер и Шуп, работая в IBM Research, представили свою конструкцию на конференции Eurocrypt 1998. Она стала первой схемой, которая не требовала модели случайного оракула для доказательства стойкости, а опиралась на стандартные предположения теории сложности — в частности, на задачу Диффи-Хеллмана (CDH) и задачу принятия решения Диффи-Хеллмана (DDH). В 2001 году авторы опубликовали расширенную версию, включающую оптимизации для практического использования.

Основные понятия

Криптосистема с открытым ключом

Схема Cramer-Shoup относится к асимметричным криптосистемам, где для шифрования используется открытый ключ, а для расшифрования — секретный. Она обеспечивает семантическую безопасность, то есть противник не может получить никакой информации о сообщении, даже если он может запрашивать расшифрование произвольных шифротекстов (кроме целевого).

Стойкость к атакам на основе подобранного шифротекста (CCA)

Схема доказуемо устойчива к CCA-атакам, что означает, что даже при наличии доступа к оракулу расшифрования (кроме целевого шифротекста) злоумышленник не может получить информацию о сообщении. Это достигается за счёт использования неинтерактивного доказательства с нулевым разглашением, встроенного в шифротекст.

Гибридное шифрование

В схеме Cramer-Shoup используется гибридный подход: часть шифротекста генерируется с помощью асимметричного шифрования (на основе DDH), а часть — с помощью симметричного шифрования (например, AES). Это позволяет эффективно шифровать сообщения произвольной длины.

Устройство схемы

Схема Cramer-Shoup использует конечную циклическую группу \( G \) простого порядка \( q \), в которой задача DDH является трудноразрешимой. Обычно в качестве \( G \) выбирается подгруппа мультипликативной группы конечного поля или группа точек эллиптической кривой.

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

1. Выбираются два случайных генератора \( g_1, g_2 \in G \).
2. Выбираются пять случайных чисел \( x_1, x_2, y_1, y_2, z \in \mathbb{Z}_q \).
3. Вычисляются:

• \( c = g_1^{x_1} g_2^{x_2} \)
• \( d = g_1^{y_1} g_2^{y_2} \)
• \( h = g_1^{z} \)

1. Открытый ключ: \( (g_1, g_2, c, d, h) \).
2. Секретный ключ: \( (x_1, x_2, y_1, y_2, z) \).

Шифрование

Для шифрования сообщения \( m \in G \) (или его хэша) выполняются следующие шаги:

1. Выбирается случайное число \( k \in \mathbb{Z}_q \).
2. Вычисляются:

• \( u_1 = g_1^k \)
• \( u_2 = g_2^k \)
• \( e = h^k \cdot m \)
• \( \alpha = H(u_1, u_2, e) \), где \( H \) — криптографическая хэш-функция.
• \( v = c^k d^{k \alpha} \)

1. Шифротекст: \( (u_1, u_2, e, v) \).

Расшифрование

Для расшифрования шифротекста \( (u_1, u_2, e, v) \) выполняются следующие шаги:

1. Вычисляется \( \alpha = H(u_1, u_2, e) \).
2. Проверяется условие: \( u_1^{x_1 + y_1 \alpha} \cdot u_2^{x_2 + y_2 \alpha} \stackrel{?}{=} v \). Если условие не выполняется, шифротекст считается недействительным и расшифрование отвергается.
3. Если условие выполнено, вычисляется \( m = e / u_1^z \).

Классификация

Схема Cramer-Shoup относится к следующим категориям:

• Асимметричные криптосистемы — использует пару ключей.
• Гибридные схемы — комбинирует асимметричное и симметричное шифрование.
• Доказуемо стойкие схемы — безопасность доказана в стандартной модели (без случайного оракула).
• Схемы на основе задачи DDH — опирается на сложность задачи принятия решения Диффи-Хеллмана.

Применение

Схема Cramer-Shoup нашла применение в следующих областях:

• Защищённая передача данных — используется в протоколах, требующих высокой стойкости к атакам, например, в системах электронной почты с шифрованием.
• Криптографические библиотеки — реализована в некоторых библиотеках, таких как OpenSSL (в экспериментальном режиме) и Crypto++.
• Научные исследования — служит эталоном для разработки новых криптосистем с доказуемой стойкостью.

Примеры

Пример на малых числах (для иллюстрации)

Пусть \( G \) — группа порядка \( q = 7 \), генераторы \( g_1 = 2, g_2 = 3 \). Выберем случайные числа: \( x_1 = 1, x_2 = 2, y_1 = 3, y_2 = 4, z = 5 \). Тогда:

• \( c = 2^1 \cdot 3^2 = 2 \cdot 9 = 18 \mod 7 = 4 \)
• \( d = 2^3 \cdot 3^4 = 8 \cdot 81 = 648 \mod 7 = 4 \)
• \( h = 2^5 = 32 \mod 7 = 4 \)

Открытый ключ: \( (2, 3, 4, 4, 4) \). Секретный ключ: \( (1, 2, 3, 4, 5) \). Сообщение \( m = 6 \). Выберем \( k = 2 \):

• \( u_1 = 2^2 = 4 \)
• \( u_2 = 3^2 = 9 \mod 7 = 2 \)
• \( e = 4^2 \cdot 6 = 16 \cdot 6 = 96 \mod 7 = 5 \)
• \( \alpha = H(4, 2, 5) \) — для простоты пусть \( \alpha = 1 \).
• \( v = 4^2 \cdot 4^{2 \cdot 1} = 16 \cdot 16 = 256 \mod 7 = 4 \)

Шифротекст: \( (4, 2, 5, 4) \). Расшифрование: проверка \( 4^{1+3} \cdot 2^{2+4} = 4^4 \cdot 2^6 = 256 \cdot 64 = 16384 \mod 7 = 4 \) — совпадает с \( v \). Затем \( m = 5 / 4^5 = 5 / 1024 \mod 7 = 5 \cdot 1024^{-1} \mod 7 \). \( 1024 \mod 7 = 2 \), обратный к 2 по модулю 7 — 4, так как \( 2 \cdot 4 = 8 \equiv 1 \). Тогда \( m = 5 \cdot 4 = 20 \mod 7 = 6 \).

Интересные факты

• Схема Cramer-Shoup была первой практической криптосистемой, доказуемо стойкой к CCA-атакам в стандартной модели, что сделало её важным теоретическим достижением.
• Несмотря на свою стойкость, схема не получила широкого распространения из-за сложности реализации и больших размеров шифротекста (четыре элемента группы плюс хэш) по сравнению с более простыми схемами, такими как RSA-OAEP.
• В 2004 году Крамер и Шуп предложили модификацию схемы для использования на эллиптических кривых, что снизило размеры ключей и шифротекста.
• Схема Cramer-Shoup является основой для многих современных криптосистем, включая некоторые варианты шифрования на основе решёток.

Критика

Основные недостатки схемы Cramer-Shoup:

• Вычислительная сложность — шифрование и расшифрование требуют нескольких экспоненцирований в группе, что делает их медленнее по сравнению с RSA или ElGamal.
• Размер шифротекста — шифротекст состоит из четырёх элементов группы, что увеличивает накладные расходы на передачу.
• Отсутствие широкой поддержки — схема не включена в большинство стандартов шифрования (например, TLS, PGP) из-за сложности и наличия более простых альтернатив.