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

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

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

См. также: Атака на основе подобранного шифротекста

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Шифрование

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

• Боб случайно выбирает ${\displaystyle {k}\in {Z}_{q}}$.
• Боб вычисляет следующие значения:
  • ${\displaystyle u_{1}={g}_{1}^{k},u_{2}={g}_{2}^{k}}$;
  • ${\displaystyle e=h^{k}m}$;
  • ${\displaystyle \alpha =H(u_{1},u_{2},e)}$, где ${\displaystyle 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 \alpha =H(u_{1},u_{2},e)\,}$.
• Алиса проверяет условие ${\displaystyle {u_{1}}^{x_{1}}{u_{2}}^{x_{2}}{u_{1}}^{{y_{1}}\alpha }u_{2}^{{y_{2}}\alpha }=v}$. Если условие не выполняется, то протокол завершается с отказом дешифрования. Иначе выводится сообщение ${\displaystyle m=e/{u}_{1}^{z}}$.

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

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

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

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

Для достижения безопасности к неадаптивным атакам (и только им) можно значительно упростить протокол, не использовав ${\displaystyle d,{y_{1}},{y_{2}},H()}$. При шифровании мы используем ${\displaystyle v={c}^{k}}$, а при дешифровании проверяем, что ${\displaystyle v={u_{1}}^{x_{1}}{u_{2}}^{x_{2}}}$.

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

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

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

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

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

Шифрование

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

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

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

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

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

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

Теорема

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

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

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

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

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

• На вход симулятору поступает ${\displaystyle ({g}_{1},{g}_{2},{u}_{1},{u}_{2})}$.
• Симулятор использует заданные ${\displaystyle ({g}_{1},{g}_{2})}$.
• Симулятор выбирает случайные величины ${\displaystyle ({x}_{1},{x}_{2},{y}_{1},{y}_{2},{z}_{1},{z}_{2})\in {Z}_{q}}$.
• Симулятор вычисляет ${\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}}}$.
• Симулятор выбирает случайную хеш-функцию ${\displaystyle H}$ и выдает публичный ключ ${\displaystyle ({g}_{1},{g}_{2},c,d,h,H)}$. Скрытый ключ симулятора: ${\displaystyle ({x}_{1},{x}_{2},{y}_{1},{y}_{2},{z}_{1},{z}_{2})}$.

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

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

Симуляция шифрования. Получая на вход ${\displaystyle {m}_{0},{m}_{1}}$, симулятор выбирает случайное значение ${\displaystyle b\in {0,1}}$, вычисляет ${\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 }}$и выводит ${\displaystyle ({u}_{1},{u}_{2},v,e)}$. Теперь доказательство теоремы будет следовать из следующих двух лемм.

Леммы

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

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

Ссылки

• 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)
• Протокол Камеру-Шоупа