Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Пример 3.2
Скажем, у нас есть асимптотически надежная система. Тогда возможно, что противник, работающий в течение n3 минут, сумеет «взломать систему» с веро- ятностью 240 • 2−n, что является пренебрежимо малой функцией по n. При n ≤ 40 это означает, что противник работает в течение 403 минут (около 6 недель) может взломать систему с вероятностью 1, поэтому такие значения n непри- менимы. Даже при n = 50 противник, работающий в течение 503минут (около 3-х месяцев) может взломать систему с вероятностью около 1/1000, что тоже может быть недопустимо. С другой стороны, при n = 500 противник, работаю- щий в течение 200 лет, взломает систему с вероятностью около 2−500. ♦ Как следует из предыдущего примера, мы можем рассматривать параметр без- опасности в качестве механизма, позволяющего честным участникам «отрегули- ровать» безопасность системы до желаемого уровня. (С увеличением параметра безопасности увеличивается время, необходимое для работы системы, а также длина ключа. Таким образом, честные участники захотят задать настолько малый параметр безопасности, который защитит их от конкретного, вызывающего у них беспокойство класса атак.) Приравнивание параметра безопасности к длине клю- ча примерно сопоставимо с тем фактом, что время, необходимое для атаки ме- тодом перебора, увеличивается экспоненциально от длины ключа. Возможность «увеличения стойкости» посредством увеличения параметра безопасности имеет важные практические последствия, поскольку позволяет честным участникам за- щититься от роста вычислительной мощности. Следующий пример дает пред- ставление о том, как это может быть использовано на практике. Пример 3.3 Давайте рассмотрим, какое влияние может оказать на практическую безопас- ность доступность более быстрых компьютеров. Допустим, у нас есть крип- тографическая система, в которой честные участники работают в течение 106 • n2 циклов, а противник, работая в течение 108 • n4 циклов, может успешно «взломать» систему с максимальной вероятностью 2−n/2. 56 (Числа подобраны так, чтобы упростить вычисления, и не соотносятся ни с одной из существующих криптографических систем.) Скажем, все участники используют компьютеры с процессорами с частотой 2 ГГц, а честные участники задали n = 80. Затем честные участники работают в тече- ние 106 • 6400 циклов, или 3,2 секунд, а противник, работая в течение 108 • (80)4 ци- клов, или примерно 3 недель, может взломать систему с вероятностью всего 2−40. Скажем, появляются компьютеры с процессорами с частотой 8 ГГц, и все участники обновляют компьютеры. Честные участники могут увеличить n до 160 (требуется генерация нового ключа) и работают в течение 3,2 секунд (т. е. 106 • 1602 циклов при частоте 8 • 109 циклов в минуту). В то же время против- нику теперь понадобится работать в течение более 8 миллионов секунд, или более 13 недель, чтобы достичь успеха с вероятностью 2−80. Появление более быстрых компьютеров приводит к тому, что работа противники усложняется ♦ Даже при использовании асимптотического подхода важно помнить, что при разворачивании криптосистемы на практике, в конечном счете, понадобятся конкретные гарантии. (В конце концов, кто-то должен определить некоторое значение n.) Как показывают приведенные выше примеры, как правило, асим- птотические заявления безопасности могут быть переведены в ограничения конкретной стойкости для любого желаемого значения n. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|