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

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

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

Шаблон:Also

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

Было хорошо известно, что многие широко используемые криптосистемы были уязвимы для такой атаки, и в течение многих лет считалось, что атака нецелесообразна и представляет лишь теоретический интерес. Все начало меняться в конце 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)\le 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)
• Протокол Камеру-Шоупа