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 лет.
Достарыңызбен бөлісу: