Криптосистема Крамера–Шоупа ( англ. 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}$ не зависит от распределения видения взломщика.

Ссылки

• and . in proceedings of Crypto 1998, LNCS 1462, p. 13ff ( , )