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

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

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

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

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

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

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

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

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

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

  • Запускается алгоритм генерации ключа в схеме шифрования с соответствующей длиной ключа, подаваемой на вход.
  • Противник выполняет серию произвольных запросов к оракулу дешифрования, таким образом дешифровывая шифротексты по его выбору.
  • Противник выбирает два сообщения и отправляет их к оракулу шифрования.
  • Оракул шифрования случайно выбирает бит , затем шифрует , который передается противнику (подбрасывание монетки для выбора бита скрыто от противника).
  • Противник снова выполняет серию произвольных запросов к оракулу дешифрования с одним лишь ограничением, что запрос должен отличаться от сообщения, полученного им от оракула шифрования.
  • Противник выдает бит - предполагаемое значение бита , выбранного оракулом шифрования на шаге 4. Если , то превосходство противника считается равным .

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

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

Пусть — группа порядка , где — большое простое число. Также  — . И имеется два распределения:

  • Распределение случайных четверок .
  • Распределение четверок , где - случайны, а для случайного .

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

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

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

Пусть у нас есть группа порядка , где — большое простое число. Сообщения — это элементы . Также мы используем универсальное семейство односторонних хеш-функций, которое отображает длинные битовые строчки в элементы , где  — .

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

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

  • Алиса генерирует случайные и случайные элементы
  • Алиса вычисляет .
  • Выбирается хеш-функция из универсального семейства односторонних хеш-функций. Публичный ключ - , скрытый ключ - .

Шифрование

Дано сообщение . Алгоритм шифрования работает следующим образом

  • Боб случайно выбирает .
  • Боб вычисляет следующие значения:
    • ;
    • ;
    • , где - это универсальная односторонняя хеш-функция;
    • ;
  • Боб отправляет зашифрованный текст Алисе.

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

Получив зашифрованный текст и используя закрытый ключ :

  • Алиса вычисляет .
  • Алиса проверяет условие . Если условие не выполняется, то протокол завершается с отказом дешифрования. Иначе выводится сообщение .

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

Проверим корректность шифровальной схемы (расшифровка зашифрованного сообщения выдает это самое сообщение). Учитывая, что и , имеем . Также и . Поэтому проверка дешифрования проходит успешно и выводится исходное сообщение .

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

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

Для достижения безопасности к неадаптивным атакам (и только им) можно значительно упростить протокол, не использовав . При шифровании мы используем , а при дешифровании проверяем, что .

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

Пусть у нас есть группа порядка . Соответственно  — .

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

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

  • Алиса генерирует случайные и случайные элементы
  • Алиса вычисляет .
  • Публичный ключ - , скрытый ключ - .

Шифрование

Дано сообщение . Алгоритм шифрования работает следующим образом

  • Боб случайно выбирает .
  • Боб вычисляет следующие значения:
    • ;
    • ;
    • ;
  • Боб отправляет зашифрованный текст Алисе.

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

Получив зашифрованный текст и используя закрытый ключ :

  • Алиса проверяет условие .
  • Условие выполняется, поэтому выводится зашифрованное Бобом сообщение .

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

Теорема

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

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

Доказательство: чтобы доказать теорему, мы предположим, что существует противник, который может взломать протокол, и покажем, что при выполнении условия на хеш-функцию получается противоречие с условием на задачу Диффи-Хеллмана. На вход нашему вероятностному алгоритму подается из распределения или . На поверхностном уровне конструкция будет выглядеть следующим образом: мы построим симулятор, который будет выдавать совместное распределение, состоящее из видения взломщиком криптосистемы после серии атак и скрытого бита b, генерируемого оракулом генерации (не входит в видение взломщика, скрыто от него). Идея доказательства: мы покажем, что если на вход подается распределение из , то симуляция пройдет успешно, а противник будет иметь нетривиальное превосходство в угадывании случайного бита b. Также мы покажем, что если на вход подается распределение из , то видение противника не зависит от и , и, значит, превосходство противника будет ничтожно мало (меньше обратного полинома). Отсюда можно построить различитель распределений и : запускаем симулятор криптосистемы (выводит ) и взломщика (выводит ) одновременно и выдаем , если и в противном случае.

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

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

  • На вход симулятору поступает .
  • Симулятор использует заданные .
  • Симулятор выбирает случайные величины .
  • Симулятор вычисляет .
  • Симулятор выбирает случайную хеш-функцию и выдает публичный ключ . Скрытый ключ симулятора: .

Можно заметить, что генерация ключа симулятора отличается от генерации ключа в протоколе (там ).

Симуляция дешифрования. Происходит так же, как и в протоколе, с той разницей, что

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

Леммы

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

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

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.