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

При неадаптивной атаке криптоаналитик не использует результаты предыдущих расшифровок, то есть шифротексты подбираются заранее. Такие атаки называют атаками в обеденное время (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_{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}$ не зависит от распределения видения взломщика.