Введение в современную криптографию



Pdf көрінісі
бет33/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   29   30   31   32   33   34   35   36   ...   249
Криптография Катц

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 лет.


Достарыңызбен бөлісу:
1   ...   29   30   31   32   33   34   35   36   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет