WikiSort.ru - Не сортированное

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

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