Space-time tradeoff

Space-time tradeoff

Space-time trade-off («выбор оптимального соотношения „место-время“ (англ. space-time trade-off)», или, иначе, «выбор оптимального соотношения „время-память“» (англ. time-memory trade-off)) — компромиссный подход к решению ряда задач в информатике, при котором требуемый объем памяти может быть снижен за счет более медленного выполнения программы (или, наоборот, время вычислений может быть снижено за счет увеличения объема используемой памяти).

Благодаря уменьшению относительных расходов на объем ОЗУ (RAM) и памяти на жестком диске (в течение некоторого периода времени стоимость места на жестком диске дешевела значительно быстрее, чем стоимость других компонент ЭВМ), постепенное распространение получали приемы, использующие доступную память для уменьшения времени вычислений. В то же время, такие приемы, как архивация данных, демонстрируют альтернативный подход — экономное использование памяти за счет дополнительных преобразований данных из одного формата в другой.

Содержание

Примеры применения

Таблицы поиска

Многие задачи поиска, такие как непрерывная задача о рюкзаке, задача о дискретном логарифме или задача обращения односторонней функции, решаясь, по сути, перебором, допускают в то же время использование т. н. таблиц поиска (англ. lookup tables)[1]. Идея такова: вместо того, чтобы, не используя дополнительную память, перебирать все допустимые решения, или один развычислить их все заранее и хранить их в памяти (часто нет ни первой, ни второй возможности), можно заранее вычислить часть допустимых значений, и, организовав их в специальную структуру данных — таблицу поиска, — осуществлять с ее помощью дальнейший перебор уже непосредственно при решении задачи.

Применению данного подхода в криптографии посвящен отдельный раздел данной статьи.

Сжатие данных

Выбор оптимального соотношения место-время может быть применён и к проблеме хранения данных. Хранение данных в несжатом виде потребует большего объема памяти, но на их извлечение понадобится меньше времени, чем на извлечение данных, хранящихся в сжатом виде. В зависимости от конкретной задачи может быть предпочтителен тот или иной вариант.

Классическим примером сжатого хранения данных может служить, к примеру, формат представления формул ΤΕΧ, используемый для написания научных статей. Результатом работы пользователя является файл специального формата, который при необходимости легко может быть преобразован в гораздо более «тяжеловесный» pdf-файл, который, в свою очередь, уже может быть использован для просмотра документа.

Раскрутка цикла

Раскрутка цикла (англ. loop unwindling) является весьма популярным приемом оптимизации кода, используемым во многих компиляторах. Идея состоит в увеличении числа инструкций, исполняемых в течение одной итерации цикла. В результате уменьшается число итераций (в пределе до единицы: все инструкции исполняются одна за другой), что, в свою очередь, увеличивает эффективность работы кэша данных.

Криптография

В данном разделе рассмотрен классический пример использования подхода Space-Time Trade-Off в криптографии — применение таблиц поиска в решении криптографической проблемы обращения криптографической хеш-функции.

Криптоаналитический перебор требует значительных вычислительных затрат. В случае, если требуется многократно осуществлять взлом криптосистемы, логично было бы заранее выполнить исчерпывающий перебор и хранить вычисленные значения в памяти. Сделав это однократно, можно далее осуществлять перебор практически мгновенно[2]. Впрочем, в реальности этот метод неприменим из-за огромных затрат памяти.

Метод, предложенный Хеллманом

В 1980 году Мартин Хеллман предложил компромиссный подход к проблеме криптоанализа, позволяющий проводить анализ криптосистемы, имеющей N ключей, за N^{2/3} операций, с затратами по памяти также N^{2/3}[1]. Это становится возможным после того, как единожды будет выполнено требующее O(n) операций предварительное получение возможных ключей.

Идея заключается в следующем.

Пусть в алгоритме шифрования используется односторонняя функция ~S_{k_i}(P). По свойствам односторонней функции получение использованного ключа ~k_i по известной паре ~P_0,C_0 — трудная задача, в то время как вычисление функции от данного открытого текста — простая задача.

Криптоаналитик применяет атаку на основе подобранного открытого текста и получает единственный шифртекст ~C_0, соответствующий открытому тексту ~P_0:

~C_0 = S_k(P_0)

Задача — найти ключ ~k, которым осуществлялось шифрование. Для этого следует найти способ вычисления возможных ключей. Введем т. н. \textbf{функцию редукции} ~R(C), ставящую шифртексту ~C_i в соответствие некий ключ k_{i+1} (длина ключа, как правило, меньше длины шифртекста, отсюда и термин):

~R(C_i) = k_{i+1}

Вычисление функции редукции — простая операция.

Функция ~f = R[S_{k_i}(P_0)]

ставит в соответствие ключу ~k_i другой ключ ~k_{i+1}. Теперь мы можем получить сколь угодно длинную цепочку ключей:

~k_i \stackrel{f}{\longrightarrow} k_{i+1} \stackrel{f}{\longrightarrow} k_{i+2} \stackrel{f}{\longrightarrow} ...

Для того, чтобы построить таблицу поиска, криптоаналитик задается ~m случайными элементами пространства ключей. Из каждого ключа описанным выше методом получаем цепочку ключей длины ~t. В память записываем только начальный и конечный ключи каждой цепочки (пары ключей сортируем по конечному ключу). Таким образом, готовая таблица занимает O(m) ячеек памяти. Генерация таблицы требует ~mt операций.

Имея построенную таблицу, криптоаналитик может проводить перебор следующим образом. Исходим из того, что использованный при шифровании ключ ~k встретился при генерации таблицы. В таком случае, из него не более, чем за t операций применения функции f, можно получить один из m конечных ключей, сохраненных в памяти.

После каждого применения операции редукции криптоаналитик ищет очередной полученный ключ в таблице (найти его или убедиться в его отсутствии можно за ~log(m) операций, используя бинарный поиск, так как таблица отсортирована по конечному ключу). Встретив один из конечных ключей, можно по соответствующему ему начальному ключу восстановить всю соответствующую цепочку; искомый ключ является её предпоследним ключом.

Нахождение ключа, таким образом, занимает ~O(t\cdot log(m))[3]; пренебрегая логарифмическим множителем, имеем ~O(t). При этом затраты памяти на хранение таблицы составляют ~O(m).

Анализ алгоритма, однако, должен учитывать, что вероятность ~P_{success} удачного дешифрования на самом деле меньше единицы, а время дешифрования может получится большим объявленного, по указанным ниже причинам.

  1. Возможны слияния цепочек, когда для некоторой пары индексов i,j совпадают i-й ключ одной и j-й ключ другой цепочки.
  2. Возможны т. н. «ложные тревоги» (англ. false alarms), когда криптоаналитик находит в таблице более одного конечного ключа. В таком случае ему приходится проверять все соответствующие цепочки.

Может быть получены[1] нижняя граница для вероятности успешного дешифрования:

~P_{success} \geq \frac{1}{N} \sum\limits_{i=1}^m \sum \limits_{j=0}^{t-1} (1 - \frac{it}{N})^{j+1}

Приведенное выражение соответствует приближению, что функция ~f — случайная величина с равномерным распределением на множестве ключей. Впрочем, устойчивая криптосистема должна быть хорошим псевдослучайным генератором[1].

Оценка этой данного выражения приводит к следующему результату: произведение mt^2 не имеет смысл брать большим, чем N: в противном случае, быстро падает нижняя граница вероятности успеха.

При mt^2 = N мы получим

P_{success} \geq 0.8 \frac{mt}{N} = \frac{1}{t}

Криптоаналитик может теперь может сгенерировать не одну, а ~l таблиц, в каждой таблице использовав свою функцию редукции (что позволит избежать слияний цепочек из разных таблиц). При этом нижняя граница вероятности успешного дешифрования составит:

~P_{success,l} \geq 1 - [\frac{1}{N} \sum\limits_{i=1}^m \sum \limits_{j=0}^{t-1} (1 - \frac{it}{N})^{j+1}]^l

Выбрав l=t, криптоаналитик получает затраты mt по памяти и t^2 по времени (в каждой таблице использована своя функция редукции, поэтому при дешифровании надо получать свою цепочку для каждой таблицы) при вероятности успеха, близкой к единице[сноска, объясняющая почему будет мало и число ложных тревог и ссылка на Хеллмана]. Взяв t=m=N^{1/3}, получим требуемые затраты N^{2/3} по времени и памяти.

Другие примеры

Другие алгоритмы, которые, также, используют «выбор оптимального соотношения место-время»:

См. также

Примечания

  1. 1 2 3 4 Martin E. Hellman. A Cryptanalytic Time-Memory Trade-Off. // Transactions on Information Theory. — July 1980. — № 4.
  2. Philippe Oechslin. Making a Faster Cryptanalytic Time-Memory Trade-Off. // ISBN 3-540-40674-3.
  3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анадиз. — 2-е. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.

Ссылки


Wikimedia Foundation. 2010.

Нужно сделать НИР?

Полезное


Смотреть что такое "Space-time tradeoff" в других словарях:

  • Space-time tradeoff — In computer science, a space time or time memory tradeoff is a situation where the memory use can be reduced at the cost of slower program execution, or vice versa, the computation time can be reduced at the cost of increased memory use. As the… …   Wikipedia

  • Hubble Space Telescope — Infobox Space telescope name = Hubble Space Telescope (HST) caption = The Hubble Space Telescope as seen from Space Shuttle Discovery during its second servicing mission (STS 82) organization = NASAESASTScI alt names = nssdc id =… …   Wikipedia

  • Trade-off — A trade off (or tradeoff) is a situation that involves losing one quality or aspect of something in return for gaining another quality or aspect. It implies a decision to be made with full comprehension of both the upside and downside of a… …   Wikipedia

  • Hash table — Not to be confused with Hash list or Hash tree. Unordered map redirects here. For the proposed C++ class, see unordered map (C++). Hash Table Type unsorted dictionary Invented 1953 Time complexity in big O notation Average Worst case Space …   Wikipedia

  • Meet-in-the-middle attack — Not to be confused with man in the middle attack. The meet in the middle attack is a cryptographic attack which, like the birthday attack, makes use of a space time tradeoff. While the birthday attack attempts to find two values in the domain of… …   Wikipedia

  • Bayesian network — A Bayesian network, Bayes network, belief network or directed acyclic graphical model is a probabilistic graphical model that represents a set of random variables and their conditional dependencies via a directed acyclic graph (DAG). For example …   Wikipedia

  • Baby-step giant-step — In group theory, a branch of mathematics, the baby step giant step algorithm is a series of well defined steps to compute the discrete logarithm. The discrete log problem is of fundamental importance to the area of public key cryptography. Many… …   Wikipedia

  • Data structure alignment — is the way data is arranged and accessed in computer memory. It consists of two separate but related issues: data alignment and data structure padding. When a modern computer reads from or writes to a memory address, it will do this in word sized …   Wikipedia

  • Michael Saks (mathematician) — Michael Ezra Saks is a professor and was (2006–2010) director of the Mathematics Graduate Program at Rutgers University. Saks received his Ph.D from the Massachusetts Institute of Technology in 1980 after completing his dissertation entitled… …   Wikipedia

  • Collatz conjecture — Directed graph showing the orbits of small numbers under the Collatz map. The Collatz conjecture is equivalent to the statement that all paths eventually lead to 1 …   Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»