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



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

Пример 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.


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




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

    Басты бет