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

В криптографии преимущество противника - это мера того, насколько успешно он может атаковать криптографический алгоритм , отличая его от идеализированной версии этого типа алгоритма. Обратите внимание, что в этом контексте « противник » - это сам алгоритм, а не человек . Криптографический алгоритм считается безопасным, если ни один противник не имеет существенного преимущества с учетом определенных ограничений вычислительных ресурсов противника (см. Конкретную безопасность ). «Незначительный» обычно означает «в пределах O (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 ⁵⁶ перестановок на 2 ⁶⁴ возможных 64-битных блоках. «Случайный экземпляр DES» означает, что наш оракул F вычисляет DES с использованием некоторого ключа K (который неизвестен противнику), где K выбирается из 2 ⁵⁶ возможных ключей с равной вероятностью.

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

Обратите внимание: поскольку оракулы, которые нам предоставлены, шифруют открытый текст по нашему выбору, мы моделируем атаку с выбранным открытым текстом или 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 ₀ . Затем он выполняет исчерпывающий поиск ключей. Алгоритм выглядит так:

E 0 = oracle_query (0) для к в 0,1, ..., 2 56 -1: если DES k (0) == E 0 : возврат 1 возврат 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 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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