Преимущество (криптография) - Advantage (cryptography)

В криптография, противник преимущество это мера того, насколько успешно он может атаковать криптографические алгоритм, отличая его от идеализированной версии этого типа алгоритма. Обратите внимание, что в этом контексте "противник "сам по себе алгоритм, а не человек. Криптографический алгоритм считается безопасным, если ни один противник не имеет существенного преимущества, с учетом указанных ограничений вычислительных ресурсов противника (см. конкретная безопасность ). «Незначительный» обычно означает «в пределах О (2^−p) "где p - параметр безопасности связанный с алгоритмом. Например, p может быть количеством битов в блочном шифре. ключ.

Описание концепции

Пусть F - оракул для изучаемой функции, и пусть G - оракул для идеализированной функции этого типа. Противник A представляет собой вероятностный алгоритм, которому на входе даны F или G и который выдает 1 или 0. Задача A - отличить F от G на основе запросов к заданному оракулу. Мы говорим:${displaystyle Adv (A) = | Pr [A (F) = 1] -Pr [A (G) = 1] |}$

Примеры

Пусть F - случайный экземпляр DES блочный шифр. Этот шифр имеет 64-битные блоки и 56-битный ключ. Таким образом, ключ выбирает одну из двух⁵⁶ перестановки на 2⁶⁴ возможные 64-битные блоки. «Случайный экземпляр DES» означает, что наш оракул F вычисляет DES с использованием некоторого ключа K (который неизвестен противнику), где K выбирается из 2⁵⁶ возможные ключи с равной вероятностью.

Мы хотим сравнить экземпляр DES с идеализированный 64-битный блочный шифр, то есть перестановка, выбранная случайным образом из (2⁶⁴)! возможные перестановки на 64-битных блоках. Назовите эту случайно выбранную перестановку G. Примечание от Приближение Стирлинга что (2⁶⁴)! вокруг ${displaystyle 10 ^ {3,47 imes 10 ^ {20}}}$, поэтому даже указание того, какая перестановка выбрана, требует записи числа, слишком большого для точного представления на любом реальном компьютере. С другой стороны, G - это экземпляр «шифра», длина ключа которого составляет около 10²¹ бит, который опять-таки слишком велик, чтобы поместиться в компьютере. (Однако мы можем реализовать G с пространством хранения, пропорциональным количеству запросов, используя случайный оракул ).

Обратите внимание, что поскольку оракулы, которые нам предоставлены, шифруют открытый текст по нашему выбору, мы моделируем атака с выбранным открытым текстом или же CPA, а вычисляемое нами преимущество можно назвать CPA-преимуществом данного противника. Если бы у нас также были доступны оракулы дешифрования, мы бы сделали атака по выбранному зашифрованному тексту или же CCA и нахождение CCA-преимущества противника.

Пример 1: предположение наугад

Назовите этого противника A₀. Он просто подбрасывает монету и возвращает 1 или 0 с равной вероятностью и без каких-либо вызовов оракула. Таким образом, Pr [A₀(F) = 1] и Pr [A₀(G) = 1] равны 0,5. Разница между этими вероятностями равна нулю, поэтому Adv (A₀) равен нулю. То же самое применимо, если мы всегда возвращаем 0 или всегда возвращаем 1: вероятность одинакова для F и G, поэтому преимущество равно нулю. Этот противник не может отличить F и G. Если мы разработчики шифров, наше желание (возможно, неосуществимое) - сделать так, чтобы вычислительно невыполнимый за любой противник сделать значительно лучше, чем это. Мы добьемся успеха, если сможем создать шифр, для которого нет отличителя, быстрее, чем поиск методом грубой силы.

Пример 2: Поиск грубой силы

Этот противник (назовите его A₁) попытается криптоанализовать свой ввод с помощью грубая сила. Имеет собственную реализацию DES. Он отправляет один запрос своему оракулу, требуя зашифровать 64-битную строку всех нулей. Назовем полученный зашифрованный текст E₀. Затем выполняется исчерпывающий поиск ключей. Алгоритм выглядит следующим образом:

 E0 = oracle_query (0) для k в 0,1, ..., 256-1: если DESk(0) == E0: return 1 return 0

Это просматривает все 56-битное пространство ключей DES и возвращает "1", если возможно найдет подходящий ключ. На практике для подтверждения ключа требуется несколько открытых текстов, поскольку два разных ключа могут привести к одной или нескольким совпадающим парам открытый текст-зашифрованный текст. Если ключ не найден, возвращается 0.

Если входным оракулом является DES, этот исчерпывающий поиск обязательно найдет ключ, поэтому Pr [A₁(F) = 1] = 1. Если входной оракул представляет собой случайную перестановку, имеется 2⁶⁴ возможные значения E₀, и не более 2⁵⁶ из них будут изучены в поиске ключей DES. Таким образом, вероятность A₁ возврат 1 - не более 2⁻⁸. То есть:

${displaystyle Pr [A_ {1} (G) = 1] leq 2 ^ {- 8}}$, так

${displaystyle Adv (A_ {1}) = | Pr [A_ {1} (F) = 1] -Pr [A_ {1} (G) = 1] | geq 1-2 ^ {- 8}}$

так что преимущество составляет по крайней мере около 0,996. Это почти несомненный отличительный признак, но это не сбой безопасности, потому что он не быстрее, чем поиск методом грубой силы, в конце концов, он является поиск грубой силы.

Смотрите также

• Преимущество псевдослучайной функции
• Преимущество восстановления ключа
• PR-CPA преимущество

Рекомендации

Эта статья включает Список ссылок, связанное чтение или внешняя ссылка, но его источники остаются неясными, потому что в нем отсутствует встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Январь 2015) (Узнайте, как и когда удалить этот шаблон сообщения)

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

• Филип Рогавей и Михир Белларе, Введение в современную криптографию
• Одед Гольдрайх, Основы криптографии