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

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

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

См. также: Атака на основе подобранного шифротекста

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

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

Неадаптивная атакаПравить

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

Адаптивная атакаПравить

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

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

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

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

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

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

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

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

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

Базовая схемаПравить

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

Генерация ключаПравить

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

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

ШифрованиеПравить

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

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

ДешифрованиеПравить

Получив зашифрованный текст $(u_1,u_2,e,v)$$(u_{1},u_{2},e,v)$  и используя закрытый ключ $(x_1,x_2,y_1,y_2,z)$$(x_{1},x_{2},y_{1},y_{2},z)$ :

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

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

Проверим корректность шифровальной схемы (расшифровка зашифрованного сообщения выдает это самое сообщение). Учитывая, что $u_1=g_1^r$${u}_{1}={g}_{1}^{r}$  и $u_2=g_2^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}^{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}^{y_{1}}{u}_{2}^{y_{2}}={d}^{r}$  и $u_1^z=h^z$${u}_{1}^{z}={h}^{z}$ . Поэтому проверка дешифрования проходит успешно и выводится исходное сообщение $m=e/u_1^z$$m=e/{u}_{1}^{z}$ .

Упрощенная схемаПравить

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

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

Пример упрощенной схемыПравить

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

Генерация ключаПравить

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

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

ШифрованиеПравить

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

• Боб случайно выбирает $5\in <!--\; \in \; -->Z_q$${5}\in {Z}_{q}$ .
• Боб вычисляет следующие значения:
  • $u_1=5^5,u_2=7^5$$u_{1}=5^{5},u_{2}=7^{5}$ ;
  • $e=(5^9{)}^5\ast <!--\; \ast \; -->3$$e=(5^{9})^{5}*3$ ;
  • $v=(5^8\ast <!--\; \ast \; -->7^4{)}^5$$v=(5^{8}*7^{4})^{5}$ ;
• Боб отправляет зашифрованный текст $(u_1,u_2,e,v)=(5^5,7^5,(5^9{)}^5\ast <!--\; \ast \; -->3,(5^8\ast <!--\; \ast \; -->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\ast <!--\; \ast \; -->3,(5^9{)}^5\ast <!--\; \ast \; -->3)$$(5^{5},7^{5},(5^{9})^{5}*3,(5^{9})^{5}*3)$  и используя закрытый ключ $(8,4,9)$$(8,4,9)$ :

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

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

ТеоремаПравить

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

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

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

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

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

• На вход симулятору поступает $(g_1,g_2,u_1,u_2)$$({g}_{1},{g}_{2},{u}_{1},{u}_{2})$ .
• Симулятор использует заданные $(g_1,g_2)$$({g}_{1},{g}_{2})$ .
• Симулятор выбирает случайные величины $(x_1,x_2,y_1,y_2,z_1,z_2)\in <!--\; \in \; -->Z_q$$({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}$$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$$H$  и выдает публичный ключ $(g_1,g_2,c,d,h,H)$$({g}_{1},{g}_{2},c,d,h,H)$ . Скрытый ключ симулятора: $(x_1,x_2,y_1,y_2,z_1,z_2)$$({x}_{1},{x}_{2},{y}_{1},{y}_{2},{z}_{1},{z}_{2})$ .

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

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

Симуляция шифрования. Получая на вход $m_0,m_1$${m}_{0},{m}_{1}$ , симулятор выбирает случайное значение $b\in <!--\; \in \; -->0,1$$b\in {0,1}$ , вычисляет $e=u_1^{z_1}{u}_2^{z_2}{m}_b,\mathrm{\alpha <!--\; \alpha \; -->}=H(u_1,u_2,e,v),v=u_1^{x_1+y_1\mathrm{\alpha <!--\; \alpha \; -->}}{u}_2^{x_2+y_2\mathrm{\alpha <!--\; \alpha \; -->}}$$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)$$({u}_{1},{u}_{2},v,e)$ . Теперь доказательство теоремы будет следовать из следующих двух лемм.

ЛеммыПравить

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

Лемма 2. Если на вход симулятору подается распределение из $R$$R$ , то распределение скрытого бита $b$$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)
• Протокол Камеру-Шоупа