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


*Компромиссы времени/пространства для обратных функций



Pdf көрінісі
бет136/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   132   133   134   135   136   137   138   139   ...   249
Криптография Катц

5.4.3 *Компромиссы времени/пространства для обратных функций 
В этом разделе мы рассмотрим вопрос устойчивости прообраза, то есть нас 
интересуют алгоритмы для проблем инверсии функции. Итак, дан алгоритм y = 
H(x) для универсального x, целью является найти какие-либо x, чтобы H(xr) = y. 
Начнем, предполагая, что длина входных и выходных данных H одинакова, и 
вкратце рассмотрим более общий случай в конце.
Пусть h : {0, 1}A → {0, 1}A будет функцией. Без эксплуатации каких-либо 
слабостей H нахождение прообраза точки y может быть осуществлено за время 
O(2A ) посредством изнурительного поиска по области. Мы покажем, что при 
помощи предварительной обработки и относительно большого объема памяти, 
это можно сделать эффективнее.
Внесу ясность: мы рассматриваем предварительную обработку как одноразо-
вую операцию и мы не будем сильно зацикливаться на затратах на нее. Нас вме-
сто этого интересует реальное время для инвертирования H в точке y после того, 
как предварительная обработка уже осуществлена. Это обосновано, если затраты 
на предварительную обработку могут быть амортизированы через инверсию мно-
гих точек, или если у нас есть желание вкладывать в вычислительные ресурсы для 
предварительной обработки перед тем, как y станет известным для выгоды более 
быстрого последующего инвертирования. Фактически, это обычное дело - исполь-
зовать предварительную обработку для обеспечения инверсии функций за очень 
короткое время. Все, что нам нужно - определить H на каждой точке во время фазы 
предварительной обработки, а затем сохранить пары {(x, H(x))} в таблицу, отсорти-
рованную по второй записи. По достижении любой точки y прообраз y может быть 
с легкостью найден путем поиска в таблице пары со второй записью y. Недостаток 
состоит в том, что нам нужно пространство для хранения пар O(2A ) в таблице, ко-
торое может быть ограничено, если не недоступно для больших A (то есть A = 80).
Начальная атака методом «грубой силы» использует постоянный объем па-
мяти и время O(2A ), тогда как атака, описанная выше, хранит точки O(2A ) и 
осуществляет инверсию, по сути, в течение постоянного времени. А теперь 
мы представим подход, который позволит атакующему сбалансировать время 
и ппамять. В частности, мы покажем как хранить точки O(22A/3) и находить 
прообраз за время O(22A/3); другие компромиссы также возможны.


Достарыңызбен бөлісу:
1   ...   132   133   134   135   136   137   138   139   ...   249




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

    Басты бет