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); другие компромиссы также возможны.
Достарыңызбен бөлісу: |