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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Шифрование

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

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

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

Получив зашифрованный текст $(u_{1},u_{2},e,v)$ и используя закрытый ключ $(x_{1},x_{2},y_{1},y_{2},z)$:

• Алиса вычисляет $\alpha =H(u_{1},u_{2},e)\,$.
• Алиса проверяет условие ${u_{1}}^{x_{1}}{u_{2}}^{x_{2}}{u_{1}}^{{y_{1}}\alpha }u_{2}^{{y_{2}}\alpha }=v$. Если условие не выполняется, то протокол завершается с отказом дешифрования. Иначе выводится сообщение $m=e/{u}_{1}^{z}$.

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

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

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

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

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

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

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

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

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

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

Шифрование

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

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

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

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

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

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

Теорема

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

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

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

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

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

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

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

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

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

Леммы

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

Лемма 2. Если на вход симулятору подается распределение из $R$, то распределение скрытого бита $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)
• Протокол Камеру-Шоупа