Компромисс времени и памяти: различия между версиями
[отпатрулированная версия] | [отпатрулированная версия] |
KLBot2 (обсуждение | вклад) м Перемещение 8 интервики на Викиданные, d:Q283310 |
Cherkash (обсуждение | вклад) мНет описания правки |
||
(не показано 20 промежуточных версий 17 участников) | |||
Строка 1: | Строка 1: | ||
{{значения|Компромисс (значения)}} |
|||
'''Компромисс времени и памяти''' ({{lang-en|''' |
'''Компромисс времени и памяти''' ({{lang-en|'''space–time trade-off'''}}, «выбор оптимального соотношения „место — время“», или, иначе, {{lang-en|'''time–memory trade-off'''}}, «выбор оптимального соотношения „время — память“») — компромиссный подход к решению ряда задач в [[информатика|информатике]], при котором используется обратное соотношение требуемого объёма памяти и скорости выполнения программы: время вычислений может быть увеличено за счёт уменьшения используемой памяти или, наоборот, снижено за счёт увеличения объёма используемой памяти. |
||
Благодаря уменьшению относительных расходов на |
Благодаря уменьшению относительных расходов на объём [[Оперативная память|ОЗУ (RAM)]] и памяти на жёстком диске (в течение некоторого периода времени стоимость места на жёстком диске дешевела значительно быстрее, чем стоимость других компонент [[ЭВМ]]), постепенное распространение получали приёмы, использующие доступную память для уменьшения времени вычислений. В то же время, такие приёмы, как [[Сжатие данных|сжатие]] данных, демонстрируют альтернативный подход — экономное использование памяти за счёт дополнительных преобразований данных из одного формата в другой. |
||
== Примеры применения == |
== Примеры применения == |
||
=== Таблицы поиска === |
=== Таблицы поиска === |
||
Многие задачи поиска, такие как [[Задача о рюкзаке|непрерывная задача о рюкзаке]], [[Дискретный логарифм|задача о дискретном логарифме]] или [[Односторонняя функция|задача обращения односторонней функции]], решаясь, по сути, перебором, допускают в то же время использование т. н. [[Таблица поиска|таблиц поиска]] (англ. ''lookup tables'')<ref name="Hellman">''Martin E. Hellman.'' A Cryptanalytic Time-Memory Trade-Off. // Transactions on Information Theory. — July 1980. — № 4.</ref>. Идея такова: вместо того, чтобы, не используя дополнительную память, перебирать все допустимые решения, или один |
Многие задачи поиска, такие как [[Задача о рюкзаке|непрерывная задача о рюкзаке]], [[Дискретный логарифм|задача о дискретном логарифме]] или [[Односторонняя функция|задача обращения односторонней функции]], решаясь, по сути, перебором, допускают в то же время использование т. н. [[Таблица поиска|таблиц поиска]] (англ. ''lookup tables'')<ref name="Hellman">''Martin E. Hellman.'' A Cryptanalytic Time-Memory Trade-Off. // Transactions on Information Theory. — July 1980. — № 4.</ref>. Идея такова: вместо того, чтобы, не используя дополнительную память, перебирать все допустимые решения, или один раз вычислить их все заранее и хранить их в памяти (часто нет ни первой, ни второй возможности), можно заранее вычислить ''часть'' допустимых значений, и, организовав их в специальную структуру данных — таблицу поиска, — осуществлять с её помощью дальнейший перебор уже непосредственно при решении задачи. |
||
Применению данного подхода в криптографии |
Применению данного подхода в криптографии посвящён отдельный раздел данной статьи. |
||
=== Сжатие данных === |
=== Сжатие данных === |
||
Выбор оптимального соотношения место |
Выбор оптимального соотношения «место — время» может быть применён и к проблеме хранения данных. Хранение данных в несжатом виде потребует большего объёма памяти, но на их извлечение понадобится меньше времени, чем на извлечение данных, хранящихся в сжатом виде. В зависимости от конкретной задачи может быть предпочтителен тот или иной вариант. |
||
Классическим примером |
Классическим примером компактного представления данных может служить, к примеру, формат представления формул '''[[TeX|{{TeX}}]]''', используемый для написания научных статей. Результатом работы пользователя является файл специального формата, который при необходимости легко может быть преобразован в гораздо более «тяжеловесный» [[pdf]]-файл, который, в свою очередь, уже может быть использован для просмотра документа в более популярных программах просмотра нежели специфические для '''[[TeX|{{TeX}}]]'''. |
||
=== Раскрутка цикла === |
=== Раскрутка цикла === |
||
{{main|Раскрутка цикла}} |
{{main|Раскрутка цикла}} |
||
[[Раскрутка цикла]] (англ. ''loop |
[[Раскрутка цикла]] (англ. ''loop unwinding'') является весьма популярным приёмом оптимизации кода, используемым во многих компиляторах. Идея состоит в увеличении числа инструкций, исполняемых в течение одной итерации цикла. В результате уменьшается число итераций (в пределе до единицы: все инструкции исполняются одна за другой), что, в свою очередь, увеличивает эффективность работы [[кэш]]а данных. |
||
== Криптография == |
== Криптография == |
||
Строка 25: | Строка 27: | ||
=== Метод, предложенный Хеллманом === |
=== Метод, предложенный Хеллманом === |
||
В 1980 году [[Мартин Хеллман]] предложил компромиссный подход к проблеме криптоанализа, позволяющий проводить анализ криптосистемы, имеющей <math>N</math> ключей, за <math>N^{2/3}</math> операций, с затратами по памяти также <math>N^{2/3}</math><ref name="Hellman"/>. Это становится возможным после того, как единожды будет выполнено требующее O(n) операций предварительное получение возможных ключей. |
В 1980 году [[Мартин Хеллман]] предложил компромиссный подход к проблеме криптоанализа, позволяющий проводить анализ криптосистемы, имеющей <math>N</math> ключей, за <math>N^{2/3}</math> операций, с затратами по памяти также <math>N^{2/3}</math><ref name="Hellman"/>. Это становится возможным после того, как единожды будет выполнено требующее O(n) операций предварительное получение возможных ключей. |
||
Идея заключается в следующем. |
Идея заключается в следующем. |
||
Пусть в алгоритме шифрования используется [[односторонняя функция]] <math> |
Пусть в алгоритме шифрования используется [[односторонняя функция]] <math>S_{k_i}(P)</math>. По свойствам односторонней функции получение использованного ключа <math>k_i</math> по известной паре <math>P_0,C_0</math> — трудная задача, в то время как вычисление функции от данного открытого текста — простая задача. |
||
Криптоаналитик применяет [[атака на основе подобранного открытого текста|атаку на основе подобранного открытого текста]] и получает единственный шифртекст <math> |
Криптоаналитик применяет [[атака на основе подобранного открытого текста|атаку на основе подобранного открытого текста]] и получает единственный шифртекст <math>C_0</math>, соответствующий открытому тексту <math>P_0</math>: |
||
<center><math> |
<center><math>C_0 = S_k(P_0)</math></center> |
||
Задача — найти ключ <math> |
Задача — найти ключ <math>k</math>, которым осуществлялось шифрование. Для этого следует найти способ вычисления возможных ключей. Введём т. н. '''функцию редукции''' <math>R(C)</math>, ставящую шифртексту <math>C_i</math> в соответствие некий ключ <math>k_{i+1}</math> (длина ключа, как правило, меньше длины шифртекста, отсюда и термин): |
||
<center><math> |
<center><math>R(C_i) = k_{i+1}</math></center> |
||
Вычисление функции редукции — простая операция. |
Вычисление функции редукции — простая операция. |
||
Функция <math> |
Функция <math>f = R[S_{k_i}(P_0)]</math> |
||
ставит в соответствие ключу <math> |
ставит в соответствие ключу <math>k_i</math> другой ключ <math>k_{i+1}</math>. |
||
Теперь мы можем получить сколь угодно длинную цепочку ключей: |
Теперь мы можем получить сколь угодно длинную цепочку ключей: |
||
<center><math> |
<center><math>k_i \stackrel{f}{\longrightarrow} k_{i+1} \stackrel{f}{\longrightarrow} k_{i+2} \stackrel{f}{\longrightarrow} ... </math></center> |
||
Для того, чтобы построить таблицу поиска, криптоаналитик |
Для того, чтобы построить таблицу поиска, криптоаналитик задаётся <math>m</math> случайными элементами пространства ключей. |
||
Из каждого ключа описанным выше методом получаем цепочку ключей длины <math> |
Из каждого ключа описанным выше методом получаем цепочку ключей длины <math>t</math>. В память записываем только ''начальный'' и ''конечный'' ключи каждой цепочки (пары ключей сортируем по ''конечному'' ключу). Таким образом, готовая таблица занимает <math>O(m)</math> ячеек памяти. Генерация таблицы требует <math>mt</math> операций. |
||
Имея построенную таблицу, криптоаналитик может проводить перебор следующим образом. Исходим из того, что использованный при шифровании ключ <math> |
Имея построенную таблицу, криптоаналитик может проводить перебор следующим образом. Исходим из того, что использованный при шифровании ключ <math>k</math> встретился при генерации таблицы. В таком случае, из него не более, чем за t операций применения функции <math>f</math>, можно получить один из <math>m</math> конечных ключей, сохранённых в памяти. |
||
После каждого применения операции редукции криптоаналитик ищет очередной полученный ключ в таблице (найти его или убедиться в его отсутствии можно за <math> |
После каждого применения операции редукции криптоаналитик ищет очередной полученный ключ в таблице (найти его или убедиться в его отсутствии можно за <math>log(m)</math> операций, используя [[бинарный поиск]], так как таблица отсортирована по конечному ключу). |
||
Встретив один из конечных ключей, можно по соответствующему ему ''начальному'' ключу восстановить всю соответствующую цепочку; искомый ключ является её предпоследним ключом. |
Встретив один из конечных ключей, можно по соответствующему ему ''начальному'' ключу восстановить всю соответствующую цепочку; искомый ключ является её предпоследним ключом. |
||
Нахождение ключа, таким образом, занимает <math> |
Нахождение ключа, таким образом, занимает <math>O(t\cdot log(m))</math><ref name="Cormen">''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ. — 2-е. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4. </ref>; пренебрегая логарифмическим множителем, имеем <math>O(t)</math>. При этом затраты памяти на хранение таблицы составляют <math>O(m)</math>. |
||
Анализ алгоритма, однако, должен учитывать, что вероятность <math> |
Анализ алгоритма, однако, должен учитывать, что вероятность <math>P_{success}</math> удачного дешифрования на самом деле меньше единицы, а время дешифрования может получится большим объявленного, по указанным ниже причинам. |
||
# Возможны ''слияния'' цепочек, когда для некоторой пары индексов <math>i,j</math> совпадают <math>i</math>-й ключ одной и <math>j</math>-й ключ другой цепочки. |
# Возможны ''слияния'' цепочек, когда для некоторой пары индексов <math>i,j</math> совпадают <math>i</math>-й ключ одной и <math>j</math>-й ключ другой цепочки. |
||
Строка 66: | Строка 67: | ||
Может быть получены<ref name="Hellman" /> нижняя граница для вероятности успешного дешифрования: |
Может быть получены<ref name="Hellman" /> нижняя граница для вероятности успешного дешифрования: |
||
<center><math> |
<center><math>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}</math></center> |
||
Приведённое выражение соответствует приближению, что функция <math>f</math> — случайная величина с равномерным распределением на множестве ключей. Впрочем, устойчивая криптосистема должна быть хорошим [[ГПСЧ|псевдослучайным генератором]]<ref name="Hellman" />. |
|||
Оценка |
Оценка данного выражения приводит к следующему результату: '''произведение <math>mt^2</math> не имеет смысл брать большим, чем <math>N</math>''': в противном случае, быстро падает нижняя граница вероятности успеха. |
||
При <math>mt^2 = N</math> мы получим |
При <math>mt^2 = N</math> мы получим |
||
Строка 76: | Строка 77: | ||
<center><math>P_{success} \geq 0.8 \frac{mt}{N} = \frac{1}{t}</math></center> |
<center><math>P_{success} \geq 0.8 \frac{mt}{N} = \frac{1}{t}</math></center> |
||
Криптоаналитик может теперь может сгенерировать не одну, а <math> |
Криптоаналитик может теперь может сгенерировать не одну, а <math>l</math> таблиц, в каждой таблице использовав свою функцию редукции (что позволит избежать слияний цепочек из разных таблиц). При этом нижняя граница вероятности успешного дешифрования составит: |
||
<center><math> |
<center><math>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</math></center> |
||
Выбрав <math>l=t</math>, криптоаналитик получает затраты <math>mt</math> по памяти и <math>t^2</math> по времени (в каждой таблице использована своя функция редукции, поэтому при дешифровании надо получать свою цепочку для каждой таблицы) при вероятности успеха, близкой к единице[сноска, объясняющая почему будет мало и число ложных тревог и ссылка на Хеллмана]. Взяв <math>t=m=N^{1/3}</math>, получим требуемые затраты <math>N^{2/3}</math> по времени и памяти. |
Выбрав <math>l=t</math>, криптоаналитик получает затраты <math>mt</math> по памяти и <math>t^2</math> по времени (в каждой таблице использована своя функция редукции, поэтому при дешифровании надо получать свою цепочку для каждой таблицы) при вероятности успеха, близкой к единице[сноска, объясняющая почему будет мало и число ложных тревог и ссылка на Хеллмана]. Взяв <math>t=m=N^{1/3}</math>, получим требуемые затраты <math>N^{2/3}</math> по времени и памяти. |
||
== Другие примеры == |
== Другие примеры == |
||
Другие алгоритмы, которые |
Другие алгоритмы, которые также используют «выбор оптимального соотношения „место — время“»: |
||
* [[Алгоритм Шенкса]], применяемый для |
* [[Алгоритм Шенкса]], применяемый для расчёта [[Дискретное логарифмирование|дискретных логарифмов]]. |
||
* [[Динамическое программирование]], при котором временная сложность задачи, |
* [[Динамическое программирование]], при котором временная сложность задачи, эффективно разбивающейся на подзадачи, может быть значительно снижена путём [[Мемоизация|мемоизации]] — сохранения уже вычисленных решений подзадач. |
||
* [[Радужные таблицы]] в [[криптография|криптографии]] — усовершенствованный вариант таблиц поиска для обращения криптографических хеш-функций. |
* [[Радужные таблицы]] в [[криптография|криптографии]] — усовершенствованный вариант таблиц поиска для обращения [[Криптографическая хеш-функция|криптографических хеш-функций]]. |
||
== См. также == |
== См. также == |
||
* [[Эффективность алгоритма]] |
|||
* [[Algorithmic efficiency]] |
|||
* |
* {{iw|Computational resource}} |
||
* |
* {{iw|Blum's speedup theorem}} |
||
* [[Теорема Сэвича]] |
* [[Теорема Сэвича]] |
||
* [[ |
* [[Размотка цикла]] |
||
* [[Радужные таблицы]] |
|||
== Примечания == |
== Примечания == |
||
Строка 104: | Строка 104: | ||
* [http://lasecwww.epfl.ch/pub/lasec/doc/Oech03.pdf Philippe Oechslin — Making a Faster Cryptanalytic Time-Memory Trade-Off] |
* [http://lasecwww.epfl.ch/pub/lasec/doc/Oech03.pdf Philippe Oechslin — Making a Faster Cryptanalytic Time-Memory Trade-Off] |
||
* [http://www.cs.sjsu.edu/faculty/stamp/RUA/TMTO.pdf Mark Stamp — Once Upon a Time-Memory Tradeoff.] |
* [http://www.cs.sjsu.edu/faculty/stamp/RUA/TMTO.pdf Mark Stamp — Once Upon a Time-Memory Tradeoff.] |
||
[[Категория:Информатика]] |
[[Категория:Информатика]] |
||
[[Категория:Криптография]] |
[[Категория:Криптография]] |
||
[[Категория:Оптимизация программного обеспечения]] |
Текущая версия от 18:22, 27 июля 2022
Компромисс времени и памяти (англ. space–time trade-off, «выбор оптимального соотношения „место — время“», или, иначе, англ. time–memory trade-off, «выбор оптимального соотношения „время — память“») — компромиссный подход к решению ряда задач в информатике, при котором используется обратное соотношение требуемого объёма памяти и скорости выполнения программы: время вычислений может быть увеличено за счёт уменьшения используемой памяти или, наоборот, снижено за счёт увеличения объёма используемой памяти.
Благодаря уменьшению относительных расходов на объём ОЗУ (RAM) и памяти на жёстком диске (в течение некоторого периода времени стоимость места на жёстком диске дешевела значительно быстрее, чем стоимость других компонент ЭВМ), постепенное распространение получали приёмы, использующие доступную память для уменьшения времени вычислений. В то же время, такие приёмы, как сжатие данных, демонстрируют альтернативный подход — экономное использование памяти за счёт дополнительных преобразований данных из одного формата в другой.
Примеры применения
[править | править код]Таблицы поиска
[править | править код]Многие задачи поиска, такие как непрерывная задача о рюкзаке, задача о дискретном логарифме или задача обращения односторонней функции, решаясь, по сути, перебором, допускают в то же время использование т. н. таблиц поиска (англ. lookup tables)[1]. Идея такова: вместо того, чтобы, не используя дополнительную память, перебирать все допустимые решения, или один раз вычислить их все заранее и хранить их в памяти (часто нет ни первой, ни второй возможности), можно заранее вычислить часть допустимых значений, и, организовав их в специальную структуру данных — таблицу поиска, — осуществлять с её помощью дальнейший перебор уже непосредственно при решении задачи.
Применению данного подхода в криптографии посвящён отдельный раздел данной статьи.
Сжатие данных
[править | править код]Выбор оптимального соотношения «место — время» может быть применён и к проблеме хранения данных. Хранение данных в несжатом виде потребует большего объёма памяти, но на их извлечение понадобится меньше времени, чем на извлечение данных, хранящихся в сжатом виде. В зависимости от конкретной задачи может быть предпочтителен тот или иной вариант.
Классическим примером компактного представления данных может служить, к примеру, формат представления формул ΤΕΧ, используемый для написания научных статей. Результатом работы пользователя является файл специального формата, который при необходимости легко может быть преобразован в гораздо более «тяжеловесный» pdf-файл, который, в свою очередь, уже может быть использован для просмотра документа в более популярных программах просмотра нежели специфические для ΤΕΧ.
Раскрутка цикла
[править | править код]Раскрутка цикла (англ. loop unwinding) является весьма популярным приёмом оптимизации кода, используемым во многих компиляторах. Идея состоит в увеличении числа инструкций, исполняемых в течение одной итерации цикла. В результате уменьшается число итераций (в пределе до единицы: все инструкции исполняются одна за другой), что, в свою очередь, увеличивает эффективность работы кэша данных.
Криптография
[править | править код]В данном разделе рассмотрен классический пример использования подхода Space-Time Trade-Off в криптографии — применение таблиц поиска в решении криптографической проблемы обращения криптографической хеш-функции.
Криптоаналитический перебор требует значительных вычислительных затрат. В случае, если требуется многократно осуществлять взлом криптосистемы, логично было бы заранее выполнить исчерпывающий перебор и хранить вычисленные значения в памяти. Сделав это однократно, можно далее осуществлять перебор практически мгновенно[2]. Впрочем, в реальности этот метод неприменим из-за огромных затрат памяти.
Метод, предложенный Хеллманом
[править | править код]В 1980 году Мартин Хеллман предложил компромиссный подход к проблеме криптоанализа, позволяющий проводить анализ криптосистемы, имеющей ключей, за операций, с затратами по памяти также [1]. Это становится возможным после того, как единожды будет выполнено требующее O(n) операций предварительное получение возможных ключей.
Идея заключается в следующем.
Пусть в алгоритме шифрования используется односторонняя функция . По свойствам односторонней функции получение использованного ключа по известной паре — трудная задача, в то время как вычисление функции от данного открытого текста — простая задача.
Криптоаналитик применяет атаку на основе подобранного открытого текста и получает единственный шифртекст , соответствующий открытому тексту :
Задача — найти ключ , которым осуществлялось шифрование. Для этого следует найти способ вычисления возможных ключей. Введём т. н. функцию редукции , ставящую шифртексту в соответствие некий ключ (длина ключа, как правило, меньше длины шифртекста, отсюда и термин):
Вычисление функции редукции — простая операция.
Функция
ставит в соответствие ключу другой ключ . Теперь мы можем получить сколь угодно длинную цепочку ключей:
Для того, чтобы построить таблицу поиска, криптоаналитик задаётся случайными элементами пространства ключей. Из каждого ключа описанным выше методом получаем цепочку ключей длины . В память записываем только начальный и конечный ключи каждой цепочки (пары ключей сортируем по конечному ключу). Таким образом, готовая таблица занимает ячеек памяти. Генерация таблицы требует операций.
Имея построенную таблицу, криптоаналитик может проводить перебор следующим образом. Исходим из того, что использованный при шифровании ключ встретился при генерации таблицы. В таком случае, из него не более, чем за t операций применения функции , можно получить один из конечных ключей, сохранённых в памяти.
После каждого применения операции редукции криптоаналитик ищет очередной полученный ключ в таблице (найти его или убедиться в его отсутствии можно за операций, используя бинарный поиск, так как таблица отсортирована по конечному ключу). Встретив один из конечных ключей, можно по соответствующему ему начальному ключу восстановить всю соответствующую цепочку; искомый ключ является её предпоследним ключом.
Нахождение ключа, таким образом, занимает [3]; пренебрегая логарифмическим множителем, имеем . При этом затраты памяти на хранение таблицы составляют .
Анализ алгоритма, однако, должен учитывать, что вероятность удачного дешифрования на самом деле меньше единицы, а время дешифрования может получится большим объявленного, по указанным ниже причинам.
- Возможны слияния цепочек, когда для некоторой пары индексов совпадают -й ключ одной и -й ключ другой цепочки.
- Возможны т. н. «ложные тревоги» (англ. false alarms), когда криптоаналитик находит в таблице более одного конечного ключа. В таком случае ему приходится проверять все соответствующие цепочки.
Может быть получены[1] нижняя граница для вероятности успешного дешифрования:
Приведённое выражение соответствует приближению, что функция — случайная величина с равномерным распределением на множестве ключей. Впрочем, устойчивая криптосистема должна быть хорошим псевдослучайным генератором[1].
Оценка данного выражения приводит к следующему результату: произведение не имеет смысл брать большим, чем : в противном случае, быстро падает нижняя граница вероятности успеха.
При мы получим
Криптоаналитик может теперь может сгенерировать не одну, а таблиц, в каждой таблице использовав свою функцию редукции (что позволит избежать слияний цепочек из разных таблиц). При этом нижняя граница вероятности успешного дешифрования составит:
Выбрав , криптоаналитик получает затраты по памяти и по времени (в каждой таблице использована своя функция редукции, поэтому при дешифровании надо получать свою цепочку для каждой таблицы) при вероятности успеха, близкой к единице[сноска, объясняющая почему будет мало и число ложных тревог и ссылка на Хеллмана]. Взяв , получим требуемые затраты по времени и памяти.
Другие примеры
[править | править код]Другие алгоритмы, которые также используют «выбор оптимального соотношения „место — время“»:
- Алгоритм Шенкса, применяемый для расчёта дискретных логарифмов.
- Динамическое программирование, при котором временная сложность задачи, эффективно разбивающейся на подзадачи, может быть значительно снижена путём мемоизации — сохранения уже вычисленных решений подзадач.
- Радужные таблицы в криптографии — усовершенствованный вариант таблиц поиска для обращения криптографических хеш-функций.
См. также
[править | править код]- Эффективность алгоритма
- Computational resource[англ.]
- Blum's speedup theorem[англ.]
- Теорема Сэвича
- Размотка цикла
Примечания
[править | править код]- ↑ 1 2 3 4 Martin E. Hellman. A Cryptanalytic Time-Memory Trade-Off. // Transactions on Information Theory. — July 1980. — № 4.
- ↑ Philippe Oechslin. Making a Faster Cryptanalytic Time-Memory Trade-Off. // ISBN 3-540-40674-3.
- ↑ Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.