Компромисс времени и памяти

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

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

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

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

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

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

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

Пусть в алгоритме шифрования используется односторонняя функция ${\displaystyle S_{k_{i}}(P)}$. По свойствам односторонней функции получение использованного ключа ${\displaystyle k_{i}}$ по известной паре ${\displaystyle P_{0},C_{0}}$ — трудная задача, в то время как вычисление функции от данного открытого текста — простая задача.

Криптоаналитик применяет атаку на основе подобранного открытого текста и получает единственный шифртекст ${\displaystyle C_{0}}$, соответствующий открытому тексту ${\displaystyle P_{0}}$:

${\displaystyle C_{0}=S_{k}(P_{0})}$

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

${\displaystyle R(C_{i})=k_{i+1}}$

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

Функция ${\displaystyle f=R[S_{k_{i}}(P_{0})]}$

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

${\displaystyle k_{i}{\stackrel {f}{\longrightarrow }}k_{i+1}{\stackrel {f}{\longrightarrow }}k_{i+2}{\stackrel {f}{\longrightarrow }}...}$

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

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

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

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

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

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

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

${\displaystyle P_{success}\geq {\frac {1}{N}}\sum \limits _{i=1}^{m}\sum \limits _{j=0}^{t-1}\left(1-{\frac {it}{N}}\right)^{j+1}}$

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

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

При ${\displaystyle mt^{2}=N}$ мы получим

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

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

${\displaystyle P_{success,l}\geq 1-\left[{\frac {1}{N}}\sum \limits _{i=1}^{m}\sum \limits _{j=0}^{t-1}\left(1-{\frac {it}{N}}\right)^{j+1}\right]^{l}}$

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