Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| 3.1.1 Конкретный подход
Конкретный подход к вычислительной стойкости измеряет стойкость крип- тографической системы, явно ограничивая максимальную вероятность успеха любого (случайного) противника, запущенного в течение некоторого указан- ного промежутка времени или, точнее, затрачивающего некоторый указанный объем вычислительных возможностей. Таким образом, конкретное определе- ние стойкости принимает приблизительно следующую форма: Система является (t, ε)-стойкой, если противник, запущенный в тече- ние максимального времени t успешно взламывает систему с максималь- ной вероятностью ε. (Конечно, вышеприведенное утверждения служит общим шаблоном и для того, чтобы оно имело смысл, нам необходимо точно определить, что значит «взломать» рассматриваемую систему.) Например, кто-то может обладать си- стемой, гарантирующей, что противник, работающий в течение максимум 200 лет и использующий самый быстрый из доступных суперкомпьютер, сумеет взломать систему с вероятностью лучше, чем 2−60. Или может быть удобнее измерять время работы в циклах центрального процессора и создать систему, которую ни один противник, использующий максимум 280 циклов централь- 53 ного процессора, сумеет взломать систему с вероятностью лучше, чем 2−60. Полезно прочувствовать большие значения t и малые значения ε, типичные для современных криптографических систем. Пример 3.1 Обычно допускается, что современные системы шифрования с закрытым ключом обеспечивают почти оптимальную надежность следующим образом: когда длина ключа составляет n (значит, пространство ключа составляет 2n), противнику, запущенному в течение времени t (измеряется, скажем, в машин- ных циклах), удается взломать систему с максимальной вероятностью ct/2n, для некоторого постоянного значения c. (Это соответствует простому перебору пространства ключа и допускает, что никакой анализ не проделывался.) Допустим для простоты, что c = 1, ключ длиной n = 60 обеспечивает необ- ходимую стойкость против противника с обычным настольным компьютером. Действительно, на процессоре с частотой 4 ГГц (выполняет 4 × 109 циклов в секунду) 260 циклов центрального процессора займут 260/(4×109) секунд, или около 9 лет. Однако самый быстрый суперкомпьютер на момент написания нами книги может выполнить 2 × 1016 операций с плавающей точкой за секун- ду, и выполнение 260 таких операций займет у него около одной минуты . Взять n = 80 было бы более благоразумным решением, поскольку даже у вышеупомя- нутого компьютера на выполнение 280 операций уйдет два года. (Вышеупомянутые числа приведены только для наглядности: на практике c > 1, а другие некоторые факторы (время, необходимое для доступа к памяти и воз- можность параллельного вычисления с помощью сетевых компьютеров) могут значительно повлиять на атаки методом перебора.) Тем не менее, сегодня рекомендуемая длина ключа может быть n = 128. Раз- ница между 280 и 2128 является мультипликативным коэффициентом, равным 248. Чтобы иметь представление о том, насколько это большое число, необхо- димо отметить, что по оценке физиков, количество секунд, прошедших после Большого Взрыва составляет порядка 258. Если вероятность того, что перехватчик успешно восстановит зашифрованное со- общение за один год, составляет самое большее 2−60, тогда такова же вероятность, что в этот же временной промежуток в отправителя и получателя ударит молния. Вероятность того, что в любую секунду произойдет событие, происходящее один раз в сто лет, составляет примерно 2−30. Нечто, происходящее каждую секунду с вероятностью 2−60, случится с вероятностью в 230 раз меньше, т.е . случается приблизительно один раз в 100 млрд лет.♦ Конкретный подход важен на практике, поскольку конкретные гарантии - это 54 именно то, что интересует пользователей криптографических систем. Тем не менее, сложно предоставить точные и конкретные гарантии. Более того, необ- ходимо очень осторожно интерпретировать заявления о конкретной стойкости. Например, заявление о том, что ни один работающий в течение 5 лет против- ник не сможет взломать данную систему с вероятностью больше ε, вызывает следующие вопросы: Какой тип вычислительной мощности (например, на- стольный ПК, суперкомпьютер, сеть из сотен компьютеров) подразумевается? Учитывает ли он возможный прогресс в области вычислительной мощности, которые по закону Мура удваиваются каждые 18 месяцев? Допускает ли оценка использование «типовых» алгоритмов или внедрение ПО, оптимизированного для атаки? Кроме того, такие гарантии ничего не говорят о вероятности успеха противника, работающего в течение 2 лет (за исключением того факта, что это может произойти с максимальной вероятностью ε), и ничего не говорится о ве- роятности успеха противника, работающего в течение 10 лет. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|