Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| 3.1.2 Асимптотический подход
Как уже отчасти было сказано выше, существуют некоторые технические и теоретические сложности, связанные с использованием конкретного подхода в вопросах стойкости системы. Эти вопросы должны решаться на практике, но если конкретная стойкость не является безотлагательной проблемой, удобнее использовать асимптотический подход к стойкости. Именно такой подход и применяется в данной книге. Этот подход, уходящий своими корнями в теорию сложности, вводит целочисленный параметр безопасности n, который параме- тризует криптографические системы, а также задействованные стороны: чест- ных участников и перехватчика. Когда честные участники запускают систему (т.е. генерируют ключи), они выбирают некоторое значение n в качестве пара- метра безопасности. В целях настоящего обсуждения условимся, что параметр безопасности соответствует длине ключа. Допустим, что параметр безопасно- сти известен противнику, атакующему систему, теперь мы рассматриваем вре- мя работы противника, а также вероятность успеха, поскольку функции пара- метра вероятности больше функций конкретных чисел. Тогда : 1. Мы приравниваем «эффективных противников» к случайным (т.е. вероятност- ным) алгоритмам, работающим в течение полиномиального времени от n. Это зна- чит, что существует некоторый многочлен p, такой что противник работает в течение максимум p(n), когда параметр безопасности равен n. Для реальной эффективности нам также необходимо, чтобы честные участники тоже действовали в полиноми- альном времени, однако, подчеркнем, что противник может обладать большими возможностями (и действовать значительно дольше), чем честные участники. 2. Мы приравниваем понятие «малая вероятность успеха» к вероятности успеха меньше, чем любой обратный многочлен от n (см. Определение 3.4). 55 Такие вероятности называются пренебрежимо малыми. Пусть ppt означает «вероятностное полиномиальное время». Тогда определе- ние асимптотической стойкости примет следующую общую форму: Система является надежной, если любой ppt противник может взло- мать систему с пренебрежимо малой вероятностью. Такое понятие безопасности является асимптотичным, поскольку безопас- ность зависит от поведения системы при достаточно больших значениях n. По- ясним это с помощью следующего примера. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|