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

Криптосистема Крамера–Шоупа (англ. Cramer–Shoup system) — алгоритм шифрования с открытым ключом. Первый алгоритм, доказавший свою устойчивость к атакам на основе адаптивно подобранного шифротекста . Разработан Рональдом Крамером и Виктором Шоупом в 1998 году. Безопасность алгоритма основана предположении Диффи–Хеллмана о различении. Является расширением схемы Эль-Гамаля, но в отличие от схемы Эль-Гамаля данный алгоритм неподатлив^[англ.] (взломщик не может подменить шифротекст на другой шифротекст, который бы расшифровывался в текст, связанный с исходным, т.е. являющийся некоторой функцией от него). Эта устойчивость достигается за счет использования универсальной однонаправленной хеш-функции и дополнительных вычислений, что приводит к получению зашифрованного текста, который в два раза больше, чем в схеме Эль-Гамаля.

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

Криптографическая атака, при которой криптоаналитик собирает информацию о шифре путем подбора зашифрованного текста и получения его расшифровки при неизвестном ключе. Криптоаналитик может воспользоваться устройством расшифрования несколько раз для получения шифротекста в расшифрованном виде. Используя полученные данные, он может попытаться восстановить секретный ключ для расшифровки. Атака на основе подобранного шифротекста может быть адаптивной и неадаптивной.

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

Неадаптивная атака

При неадаптивной атаке криптоаналитик не использует результаты предыдущих расшифровок, то есть шифротексты подбираются заранее. Такие атаки называют атаками в обеденное время (lunchtime или CCA1).

Адаптивная атака

В случае адаптивной атаки криптоаналитик адаптивно подбирает шифротекст, который зависит от результатов предыдущих расшифровок (CCA2).

Устойчивость к адаптивной атаке можно расммотреть на примере игры:

Запускается алгоритм генерации ключа в схеме шифрования с соответствующей длиной ключа, подаваемой на вход.
Противник выполняет серию произвольных запросов к оракулу дешифрования, таким образом дешифровывая шифротексты по его выбору.
Противник выбирает два сообщения [math]\displaystyle{ {m}_{0}, {m}_{1} }[/math] и отправляет их к оракулу шифрования.
Оракул шифрования случайно выбирает бит [math]\displaystyle{ b \in{0, 1} }[/math], затем шифрует [math]\displaystyle{ {m}_{b} }[/math], который передается противнику (подбрасывание монетки для выбора бита [math]\displaystyle{ b }[/math] скрыто от противника).
Противник снова выполняет серию произвольных запросов к оракулу дешифрования с одним лишь ограничением, что запрос должен отличаться от сообщения, полученного им от оракула шифрования.
Противник выдает бит [math]\displaystyle{ {b}_{1} \in {0, 1} }[/math] - предполагаемое значение бита [math]\displaystyle{ b }[/math], выбранного оракулом шифрования на шаге 4. Если [math]\displaystyle{ {P}_{r}({b}_{1} = b) \leq 1/2 + E }[/math], то превосходство противника считается равным [math]\displaystyle{ E }[/math].

Задача Диффи-Хеллмана о различении

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

Пусть [math]\displaystyle{ G }[/math]— группа порядка [math]\displaystyle{ q }[/math], где [math]\displaystyle{ q }[/math] — большое простое число. Также [math]\displaystyle{ {Z}_{q} }[/math] — [math]\displaystyle{ \{0,1,\dots,q-1\} }[/math]. И имеется два распределения:

Распределение [math]\displaystyle{ R }[/math] случайных четверок [math]\displaystyle{ ({g}_{1}, {g}_{2}, {u}_{1}, {u}_{2})\in G^4 }[/math].
Распределение [math]\displaystyle{ D }[/math] четверок [math]\displaystyle{ ({g}_{1}, {g}_{2}, {u}_{1}, {u}_{2}) \in G^4 }[/math] , где [math]\displaystyle{ {g}_{1}, {g}_{2} }[/math] - случайны, а [math]\displaystyle{ {u}_{1} = {g}_{1}^{r}, {u}_{2} = {g}_{2}^{r} }[/math] для случайного [math]\displaystyle{ r \in {Z}_{q} }[/math].

Алгоритмом, который решает задачу Диффи-Хеллмана, называется такой вероятностный алгоритм [math]\displaystyle{ A }[/math], который может эффективно различить перечисленные два распределения. То есть алгоритм, принимающий на вход одно из двух рапределений, должен выдать 0 или 1, а также [math]\displaystyle{ P (A(x) = 1|x \in R) - P (A(x) = 1|x \in D) }[/math] стремится к 0.

Задача Диффи-Хеллмана о различении трудна, если такого полиномиального вероятностного алгоритма не существует.

Базовая схема

Пусть у нас есть группа [math]\displaystyle{ G }[/math] порядка [math]\displaystyle{ q }[/math], где [math]\displaystyle{ q }[/math] — большое простое число. Сообщения — это элементы [math]\displaystyle{ \in G }[/math]. Также мы используем универсальное семейство односторонних хеш-функций, которое отображает длинные битовые строчки в элементы [math]\displaystyle{ {Z}_{q} }[/math], где [math]\displaystyle{ {Z}_{q} }[/math] — [math]\displaystyle{ \{0,1,\dots,q-1\} }[/math].

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

Алгоритм генерации ключей работает следующим образом:

Алиса генерирует случайные [math]\displaystyle{ g_1, g_2 \in G }[/math] и случайные элементы [math]\displaystyle{ ({x}_{1}, {x}_{2}, {y}_{1}, {y}_{2}, z) \in {Z}_{q} }[/math]
Алиса вычисляет [math]\displaystyle{ c = {g}_{1}^{x_1} g_{2}^{x_2}, d = {g}_{1}^{y_1} g_{2}^{y_2}, h = {g}_{1}^{z} }[/math].
Выбирается хеш-функция [math]\displaystyle{ H }[/math] из универсального семейства односторонних хеш-функций. Публичный ключ - [math]\displaystyle{ ({g}_{1}, {g}_{2}, {c}, {d}, {h}, {H}) }[/math], скрытый ключ - [math]\displaystyle{ ({x}_{1}, {x}_{2}, {y}_{1}, {y}_{2}, z) }[/math] .

Шифрование

Дано сообщение [math]\displaystyle{ m \in G }[/math]. Алгоритм шифрования работает следующим образом

Боб случайно выбирает [math]\displaystyle{ {k} \in {Z}_{q} }[/math].
Боб вычисляет следующие значения:
- [math]\displaystyle{ u_1 = {g}_{1}^{k}, u_2 = {g}_{2}^{k} }[/math];
- [math]\displaystyle{ e = h^k m }[/math];
- [math]\displaystyle{ \alpha = H(u_1, u_2, e) }[/math], где [math]\displaystyle{ H() }[/math] - это универсальная односторонняя хеш-функция;
- [math]\displaystyle{ v = c^k d^{k\alpha} }[/math];
Боб отправляет зашифрованный текст [math]\displaystyle{ (u_1, u_2, e, v) }[/math] Алисе.

Дешифрование

Получив зашифрованный текст [math]\displaystyle{ (u_1, u_2, e, v) }[/math] и используя закрытый ключ [math]\displaystyle{ (x_1, x_2, y_1, y_2, z) }[/math]:

Алиса вычисляет [math]\displaystyle{ \alpha = H(u_1, u_2, e) \, }[/math].
Алиса проверяет условие [math]\displaystyle{ {u_1}^{x_1} {u_2}^{x_2} {u_1}^{{y_1}\alpha} u_{2}^{{y_2}\alpha} = v }[/math]. Если условие не выполняется, то протокол завершается с отказом дешифрования. Иначе выводится сообщение [math]\displaystyle{ m = e / {u}_{1}^{z} }[/math].

Корректность протокола

Проверим корректность шифровальной схемы (расшифровка зашифрованного сообщения выдает это самое сообщение). Учитывая, что [math]\displaystyle{ {u}_{1} = {g}_{1}^{r} }[/math] и [math]\displaystyle{ {u}_{2} = {g}_{2}^{r} }[/math], имеем [math]\displaystyle{ {u}_{1}^{x_1} u_{2}^{x_2} = {g}_{1}^{{x}_{1}{r}}{g}_{2}^{{x}_{2}{r}} = {c}^{r} }[/math]. Также [math]\displaystyle{ {u}_{1}^{y_1} {u}_{2}^{y_2} = {d}^{r} }[/math] и [math]\displaystyle{ {u}_{1}^{z} = {h}^{z} }[/math]. Поэтому проверка дешифрования проходит успешно и выводится исходное сообщение [math]\displaystyle{ m = e /{u}_{1}^{z} }[/math].

Упрощенная схема

Отличия от базовой схемы

Для достижения безопасности к неадаптивным атакам (и только им) можно значительно упростить протокол, не использовав [math]\displaystyle{ d, {y_1}, {y_2}, H() }[/math]. При шифровании мы используем [math]\displaystyle{ v = {c}^{k} }[/math], а при дешифровании проверяем, что [math]\displaystyle{ v = {u_1}^{x_1}{u_2}^{x_2} }[/math].

Пример упрощенной схемы

Пусть у нас есть группа [math]\displaystyle{ G }[/math] порядка [math]\displaystyle{ q = 13 }[/math]. Соответственно [math]\displaystyle{ {Z}_{13} }[/math] — [math]\displaystyle{ \{0,1,\dots,12\} }[/math].

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

Алгоритм генерации ключей работает следующим образом:

Алиса генерирует случайные [math]\displaystyle{ g_1 = 5, g_2 = 7 \in G }[/math] и случайные элементы [math]\displaystyle{ ({x}_{1} = 8, {x}_{2} = 4, z = 9) \in {Z}_{q} }[/math]
Алиса вычисляет [math]\displaystyle{ c = 5^8 * 7^4, h = 5^9 }[/math].
Публичный ключ - [math]\displaystyle{ ({g}_{1}, {g}_{2}, {c}, {h}) = (5, 7, 5^8 * 7^4, 5^9) }[/math] , скрытый ключ - [math]\displaystyle{ ({x}_{1}, {x}_{2}, z) = (8, 4, 9) }[/math].

Шифрование

Дано сообщение [math]\displaystyle{ 3 \in G }[/math]. Алгоритм шифрования работает следующим образом

Боб случайно выбирает [math]\displaystyle{ {5} \in {Z}_{q} }[/math].
Боб вычисляет следующие значения:
- [math]\displaystyle{ u_1 = 5^5, u_2 = 7^5 }[/math];
- [math]\displaystyle{ e = (5^9)^5 * 3 }[/math];
- [math]\displaystyle{ v = (5^8 * 7^4)^5 }[/math];
Боб отправляет зашифрованный текст [math]\displaystyle{ (u_1, u_2, e, v) = (5^5, 7^5, (5^9)^5 * 3,(5^8 * 7^4)^5 }[/math] Алисе.

Дешифрование

Получив зашифрованный текст [math]\displaystyle{ (5^5, 7^5, (5^9)^5 * 3, (5^9)^5 * 3) }[/math] и используя закрытый ключ [math]\displaystyle{ (8, 4, 9) }[/math]:

Алиса проверяет условие [math]\displaystyle{ (5^5)^8 * (7^5)^4 = (5^5)^8 * (7^5)^4 }[/math].
Условие выполняется, поэтому выводится зашифрованное Бобом сообщение [math]\displaystyle{ 3 = ((5^9)^5 * 3) / (5^5)^9 }[/math].

Доказательство безопасности

Теорема

Криптосистема Крамера-Шоупа устойчива к атакам на основе адаптивно подобранного шифротекста при выполнении следующих условий:

Хеш-функция [math]\displaystyle{ {H} }[/math] выбирается из универсального семейства односторонних хеш-функций.
Задача Диффи-Хеллмана о различении трудна для группы [math]\displaystyle{ {G} }[/math].

Доказательство: чтобы доказать теорему, мы предположим, что существует противник, который может взломать протокол, и покажем, что при выполнении условия на хеш-функцию получается противоречие с условием на задачу Диффи-Хеллмана. На вход нашему вероятностному алгоритму подается [math]\displaystyle{ ({g}_{1}, {g}_{2}, {u}_{1}, {u}_{2}) }[/math] из распределения [math]\displaystyle{ R }[/math] или [math]\displaystyle{ D }[/math]. На поверхностном уровне конструкция будет выглядеть следующим образом: мы построим симулятор, который будет выдавать совместное распределение, состоящее из видения взломщиком криптосистемы после серии атак и скрытого бита b, генерируемого оракулом генерации (не входит в видение взломщика, скрыто от него). Идея доказательства: мы покажем, что если на вход подается распределение из [math]\displaystyle{ D }[/math], то симуляция пройдет успешно, а противник будет иметь нетривиальное превосходство в угадывании случайного бита b. Также мы покажем, что если на вход подается распределение из [math]\displaystyle{ R }[/math], то видение противника не зависит от [math]\displaystyle{ b }[/math]и [math]\displaystyle{ a }[/math], и, значит, превосходство противника будет ничтожно мало (меньше обратного полинома). Отсюда можно построить различитель распределений [math]\displaystyle{ R }[/math] и [math]\displaystyle{ D }[/math]: запускаем симулятор криптосистемы (выводит [math]\displaystyle{ b }[/math]) и взломщика (выводит [math]\displaystyle{ {b}_{1} }[/math]) одновременно и выдаем [math]\displaystyle{ 1 }[/math], если [math]\displaystyle{ b = {b}_{1} }[/math] и [math]\displaystyle{ 0 }[/math]в противном случае.

Построение симулятора

Схема симуляции генерации ключа выглядит следующим образом:

На вход симулятору поступает [math]\displaystyle{ ({g}_{1}, {g}_{2}, {u}_{1}, {u}_{2}) }[/math].
Симулятор использует заданные [math]\displaystyle{ ({g}_{1}, {g}_{2}) }[/math].
Симулятор выбирает случайные величины [math]\displaystyle{ ({x}_{1}, {x}_{2}, {y}_{1}, {y}_{2}, {z}_{1}, {z}_{2}) \in {Z}_{q} }[/math].
Симулятор вычисляет [math]\displaystyle{ c = {g}_{1}^{{x}_{1}} {g}_{2}^{{x}_{2}}, d = {g}_{1}^{{y}_{1}}{g}_{2}^{{y}_{2}}, h = {g}_{1}^{{z}_{1}}{g}_{2}^{{z}_{2}} }[/math].
Симулятор выбирает случайную хеш-функцию [math]\displaystyle{ H }[/math] и выдает публичный ключ [math]\displaystyle{ ({g}_{1}, {g}_{2}, c, d, h, H) }[/math]. Скрытый ключ симулятора: [math]\displaystyle{ ({x}_{1}, {x}_{2}, {y}_{1}, {y}_{2}, {z}_{1}, {z}_{2}) }[/math].

Можно заметить, что генерация ключа симулятора отличается от генерации ключа в протоколе (там [math]\displaystyle{ {z}_{2} = 0 }[/math]).

Симуляция дешифрования. Происходит так же, как и в протоколе, с той разницей, что [math]\displaystyle{ m = e/({u}_{1}^{{z}_{1}}+{u}_{2}^{{z}_{2}}) }[/math]

Симуляция шифрования. Получая на вход [math]\displaystyle{ {m}_{0}, {m}_{1} }[/math], симулятор выбирает случайное значение [math]\displaystyle{ b \in {0, 1} }[/math], вычисляет [math]\displaystyle{ e = {u}_{1}^{{z}_{1}}{u}_{2}^{{z}_{2}}{m}_{b}, \alpha = H({u}_{1},{u}_{2}, e, v), v = {u}_{1}^{{x}_{1}+{y}_{1}\alpha}{u}_{2}^{{x}_{2}+{y}_{2}\alpha} }[/math]и выводит [math]\displaystyle{ ({u}_{1}, {u}_{2} ,v , e) }[/math]. Теперь доказательство теоремы будет следовать из следующих двух лемм.

Леммы

Лемма 1. Если на вход симулятору подается распределение из [math]\displaystyle{ D }[/math], то совместное распределение видения взломщиком криптосистемы и скрытого бита [math]\displaystyle{ b }[/math] статистически неразличимо от настоящей атаки криптосистемы.

Лемма 2. Если на вход симулятору подается распределение из [math]\displaystyle{ R }[/math], то распределение скрытого бита [math]\displaystyle{ b }[/math] не зависит от распределения видения взломщика.

Ссылки

Cramer–Shoup cryptosystem
Ronald Cramer and Victor Shoup. "A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack." in proceedings of Crypto 1998, LNCS 1462, p. 13ff (ps,pdf)
Протокол Камеру-Шоупа