Введение в современную криптографию
*Компромиссы времени/пространства для обратных функций
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| 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); другие компромиссы также возможны. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|