Русская Википедия:Криптосистема Крамера – Шоупа

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

Шаблон:Also

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Шифрование

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

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

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

Получив зашифрованный текст <math>(u_1, u_2, e, v)</math> и используя закрытый ключ <math>(x_1, x_2, y_1, y_2, z)</math>:

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

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

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

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

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

Для достижения безопасности к неадаптивным атакам (и только им) можно значительно упростить протокол, не использовав <math>d, {y_1}, {y_2}, H() </math>. При шифровании мы используем <math> v = {c}^{k}</math>, а при дешифровании проверяем, что <math> v = {u_1}^{x_1}{u_2}^{x_2}</math>.

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

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

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

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

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

Шифрование

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

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

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

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

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

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

Теорема

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

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

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

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

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

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

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

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

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

Леммы

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

Лемма 2. Если на вход симулятору подается распределение из <math>R</math>, то распределение скрытого бита <math>b</math> не зависит от распределения видения взломщика.

Ссылки

Шаблон:Криптосистемы с открытым ключом

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Криптосистема_Крамера_–_Шоупа&oldid=10198142