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