Просторово-часова домовленість (англ. space–time, time–memory tradeoff, TMTO) — ситуація в інформатиці, коли можна зменшити використання пам'яті ціною вповільнення швидкості виконання програми (і, навпаки, можна зменшити час обчислення за рахунок використання більшого об'єму пам'яті).
Приклади використання
Таблиці пошуку
Багато задач пошуку, таких як задача пакування рюкзака, задача про дискретний логарифм або задача обернення односторонньої функції, що розв'язуються, по суті, перебором, одночасно дозволяють використання так званих таблиць пошуку. Ідея така: замість того, щоб, без використання додаткової пам'яті, перебрати всі можливі значення, зробити певні попередні обчислення і зберегти їх у таблиці, яку потім використовувати під час розв'язання задач.
Стиснуті замість нестиснутих даних
Просторово-часову домовленість можна застосувати для проблем зберігання даних. Якщо дані зберігаються нестиснутими, це потребує більше простору, але менше часу порівняно зі стиснутим варіантом (через те, що стиснення зберігає простір, що займають дані, але потребує час для виконання алгоритму стиснення даних). Залежно від конкретного прикладу використання можна використати підхожий спосіб.
Повторне промальовування замість збереження зображень
Збереження лише LaTeX-сирців і відтворення зображення кожний раз при запиті сторінки було б виграшем пам'яті за ціну збільшення часу обробки. Відтворення зображення при зміні сторінки і збереження його було б виграшем в швидкості обробки запитів за ціну пам'яті.
Менший код замість розмотування циклу
Більший розмір кода може призвести до швидшого виконання програми. коли застосовується розмотування циклу. Ця техніка для кожної ітерації циклу робить код довшим, але заощаджує час потрібний для стрибку назад на початок циклу наприкінці кожної ітерації.
Криптографія
В цьому розділі розглянемо класичний приклад використання підходу просторово-часової домовленості в криптографії — застосування таблиць пошуку в розв'язанні криптографічної проблеми обернення криптографічної геш-функції.
Криптоаналітичний перебір вимагає значних обчислювальних затрат. У випадку, якщо потрібне багаторазове злам криптосистеми, логічно було б заздалегідь виконати вичерпний перебір і зберігати обчислені значення в пам'яті. Тоді, в подальшому, можна здійснювати перебір практично миттєво. Втім, цей метод не застосовується в дійсності через надвеликі затрати пам'яті.
Метод, запропонований Геллманом
1980, Мартін Геллман запропонував компромісний підхід до проблеми криптоаналізу, що дозволяв аналіз криптосистеми, яка мала ключів, за
операцій, із затратами по пам'яті також
. Це стає можливим по тому, як одноразово буде виконане попереднє отримання можливих ключів, яке потребує
операцій.
Ідея полягає в наступному.
Нехай в алгоритмі шифрування використовується одностороння функція . За властивостями односторонньої функції отримання використаного ключа
по відомій парі
— складна задача, в той час як обчислення функції від певного відкритого тектсу — проста.
Криптоаналітик застосовує атаку на основі підібраного відкритого тексту і отримує один шифротекст , відповідний відкритому тексту
:
Задача — знайти ключ , за допомогою якого здійснювалось шифрування. Для цього треба знайти спосіб обчислення можливих ключів. Введемо функцію редукції
, яка ставить у відповідність шифротексту
деякий ключ
(довжина ключа, як правило, менша довжини шифртексту, звідси й термін):
Обчислення функції редукції — проста операція. У випадку DES це редукція від 64 до 56 біт, така як відкидання останніх 8 біт шифротексту.
Функція ставить у відповідність ключу
інший ключ
. Якщо алгоритм шифрування безпечний, то
також одностороння функція. Тепер ми можемо отримати як завгодно довгий ланцюжок ключів:
Для того, щоб побудувати таблицю пошуку, криптоаналітик вибирає випадкових елементів
із простору ключів
. З кожного ключа за описаним вище способом отримуємо ланцюжок ключів довжини
. Останній елемент
-го ланцюжку позначаємо як
, тоді очевидно
. В пам'ять записуємо лише початковий і кінцевий ключі кожного ланцюжка
(пари сортуємо за кінцевим ключем). Таким чином, готова таблиця займає
комірок пам'яті.
Утворення таблиці вимагає операцій.
По отриманні шифротексту кріптоаналітик може застосувати функцію редукції для отримання , тоді він може перевірити чи присутній
серед
.
зберігаються відсортованими, отже ця операція займе
, а з використанням геш-таблиці складність можна звести майже до константного часу.
Якщо не серед
, тоді
не в стовпчику
. Якщо
, тоді
або
має більш як один першовзір. Ми називатимемо таку ситуацію хибною тривогою (англ. false alarm). Якщо
, тоді криптоаналітик обчислює
і перевіряє чи це ключ, наприклад, через обчислення чи дешифрує він
в
. Всі проміжні стовпчики в таблиці були відкинуті для збереження пам'яті, тому криптоаналітик мусить почати в
і переобчислити
доки він не досягне
.
Якщо не кінцева точка або сталась хибна тривога, криптоаналітик обчислює
і перевіряє на кінцевість її. Якщо це не так, ключ не в
стовпчику, якщо ж так, тоді криптоаналітик перевіряє чи ключ
. І так далі до 0 стовпчика.
Віднайдення ключа таким чином займає ; нехтуючи логаріфмічним множником, маємо
. При цьому затрати пам'яті на збереження таблиці становлять
.
Якщо всі елементи в таблиці різні, тоді ймовірність успіху становить Але така ситуація не реалістична через можливість злиття ланцюжків. Якщо
є випадковою функцією, що відображає множину
в себе, і якщо ключ
вибрали рівномірно випадково з цієї множини (втім якісна криптосистема повинна бути псевдовипадковим генератором), тоді ймовірність успіху можна обмежити знизу як
Оцінка цього виразу призводить до наступного висліду: добуток не варто брати більшим від
інакше, швидко падає нижня межа ймовірності успіху.
За отримаємо
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2ZFdzdmRHaDFiV0l2Tnk4M1l5OVNMU1ZFTUNWQ1FpVkVNQ1ZDTUNWRU1DVkNSQ1ZFTVNVNE5pVkVNU1U0UlNWRU1DVkNOaVZFTUNWQ1FTVkVNQ1ZDT0Y4bFJERWxPRE5mSlVRd0pUa3pKVVF3SlVJMUpVUXdKVUpDSlVRd0pVSkNKVVF3SlVKREpVUXdKVUl3SlVRd0pVSkVKVVF3SlVJd0xuQnVaeTh5TWpCd2VDMVNMU1ZFTUNWQ1FpVkVNQ1ZDTUNWRU1DVkNSQ1ZFTVNVNE5pVkVNU1U0UlNWRU1DVkNOaVZFTUNWQ1FTVkVNQ1ZDT0Y4bFJERWxPRE5mSlVRd0pUa3pKVVF3SlVJMUpVUXdKVUpDSlVRd0pVSkNKVVF3SlVKREpVUXdKVUl3SlVRd0pVSkVKVVF3SlVJd0xuQnVadz09LnBuZw==.png)
Криптоаналітик тепер може утворити не одну, а таблиць, в кожній він може вибрати свою функцію редукції (що дозволить уникнути злиття ланцюжків з різних таблиць). При цьому межа успішності розшифрування становитиме:
Очікувана кількість хибних тривог на таблицю обмежена
Вибрав , криптоаналітик отримає затрати
по пам'яти і
по часу (у кожній таблиці використана своя функція редукції, тому при розшифруванні необхідно отримувати свій ланцюжок для кожної таблиці) при ймовірності успіху близької до одиниці. Взяв
, отримаємо потрібні затрати
по часу і пам'яті.
Примітки
- 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. // .
Посилання
- Martin Hellman — A Cryptanalytic Time-Memory Trade-Off [ 4 березня 2016 у Wayback Machine.]
- Philippe Oechslin — Making a Faster Cryptanalytic Time-Memory Trade-Off [Архівовано 27 лютого 2012 у WebCite]
- Mark Stamp — Once Upon a Time-Memory Tradeoff. [ 5 жовтня 2021 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Prostorovo chasova domovlenist angl space time time memory tradeoff TMTO situaciya v informatici koli mozhna zmenshiti vikoristannya pam yati cinoyu vpovilnennya shvidkosti vikonannya programi i navpaki mozhna zmenshiti chas obchislennya za rahunok vikoristannya bilshogo ob yemu pam yati Prikladi vikoristannyaTablici poshuku Bagato zadach poshuku takih yak zadacha pakuvannya ryukzaka zadacha pro diskretnij logarifm abo zadacha obernennya odnostoronnoyi funkciyi sho rozv yazuyutsya po suti pereborom odnochasno dozvolyayut vikoristannya tak zvanih tablic poshuku Ideya taka zamist togo shob bez vikoristannya dodatkovoyi pam yati perebrati vsi mozhlivi znachennya zrobiti pevni poperedni obchislennya i zberegti yih u tablici yaku potim vikoristovuvati pid chas rozv yazannya zadach Stisnuti zamist nestisnutih danih Prostorovo chasovu domovlenist mozhna zastosuvati dlya problem zberigannya danih Yaksho dani zberigayutsya nestisnutimi ce potrebuye bilshe prostoru ale menshe chasu porivnyano zi stisnutim variantom cherez te sho stisnennya zberigaye prostir sho zajmayut dani ale potrebuye chas dlya vikonannya algoritmu stisnennya danih Zalezhno vid konkretnogo prikladu vikoristannya mozhna vikoristati pidhozhij sposib Povtorne promalovuvannya zamist zberezhennya zobrazhen Zberezhennya lishe LaTeX sirciv i vidtvorennya zobrazhennya kozhnij raz pri zapiti storinki bulo b vigrashem pam yati za cinu zbilshennya chasu obrobki Vidtvorennya zobrazhennya pri zmini storinki i zberezhennya jogo bulo b vigrashem v shvidkosti obrobki zapitiv za cinu pam yati Menshij kod zamist rozmotuvannya ciklu Bilshij rozmir koda mozhe prizvesti do shvidshogo vikonannya programi koli zastosovuyetsya rozmotuvannya ciklu Cya tehnika dlya kozhnoyi iteraciyi ciklu robit kod dovshim ale zaoshadzhuye chas potribnij dlya stribku nazad na pochatok ciklu naprikinci kozhnoyi iteraciyi KriptografiyaV comu rozdili rozglyanemo klasichnij priklad vikoristannya pidhodu prostorovo chasovoyi domovlenosti v kriptografiyi zastosuvannya tablic poshuku v rozv yazanni kriptografichnoyi problemi obernennya kriptografichnoyi gesh funkciyi Kriptoanalitichnij perebir vimagaye znachnih obchislyuvalnih zatrat U vipadku yaksho potribne bagatorazove zlam kriptosistemi logichno bulo b zazdalegid vikonati vicherpnij perebir i zberigati obchisleni znachennya v pam yati Todi v podalshomu mozhna zdijsnyuvati perebir praktichno mittyevo Vtim cej metod ne zastosovuyetsya v dijsnosti cherez nadveliki zatrati pam yati Metod zaproponovanij Gellmanom 1980 Martin Gellman zaproponuvav kompromisnij pidhid do problemi kriptoanalizu sho dozvolyav analiz kriptosistemi yaka mala N displaystyle N klyuchiv za N2 3 displaystyle N 2 3 operacij iz zatratami po pam yati takozh N2 3 displaystyle N 2 3 Ce staye mozhlivim po tomu yak odnorazovo bude vikonane poperednye otrimannya mozhlivih klyuchiv yake potrebuye O n displaystyle O n operacij Ideya polyagaye v nastupnomu Nehaj v algoritmi shifruvannya vikoristovuyetsya odnostoronnya funkciya Ski P displaystyle S k i P Za vlastivostyami odnostoronnoyi funkciyi otrimannya vikoristanogo klyucha ki displaystyle k i po vidomij pari P0 C0 displaystyle P 0 C 0 skladna zadacha v toj chas yak obchislennya funkciyi vid pevnogo vidkritogo tektsu prosta Kriptoanalitik zastosovuye ataku na osnovi pidibranogo vidkritogo tekstu i otrimuye odin shifrotekst C0 displaystyle C 0 vidpovidnij vidkritomu tekstu P0 displaystyle P 0 C0 Sk P0 displaystyle C 0 S k P 0 Zadacha znajti klyuch k displaystyle k za dopomogoyu yakogo zdijsnyuvalos shifruvannya Dlya cogo treba znajti sposib obchislennya mozhlivih klyuchiv Vvedemo funkciyu redukciyi R C displaystyle R C yaka stavit u vidpovidnist shifrotekstu Ci displaystyle C i deyakij klyuch ki 1 displaystyle k i 1 dovzhina klyucha yak pravilo mensha dovzhini shifrtekstu zvidsi j termin R Ci ki 1 displaystyle R C i k i 1 Obchislennya funkciyi redukciyi prosta operaciya U vipadku DES ce redukciya vid 64 do 56 bit taka yak vidkidannya ostannih 8 bit shifrotekstu Funkciya f R Ski P0 displaystyle f R S k i P 0 stavit u vidpovidnist klyuchu ki displaystyle k i inshij klyuch ki 1 displaystyle k i 1 Yaksho algoritm shifruvannya bezpechnij to f displaystyle f takozh odnostoronnya funkciya Teper mi mozhemo otrimati yak zavgodno dovgij lancyuzhok klyuchiv ki fki 1 fki 2 f displaystyle k i stackrel f longrightarrow k i 1 stackrel f longrightarrow k i 2 stackrel f longrightarrow Dlya togo shob pobuduvati tablicyu poshuku kriptoanalitik vibiraye m displaystyle m vipadkovih elementiv SP1 SP2 SPm displaystyle SP 1 SP 2 SP m iz prostoru klyuchiv 1 2 N displaystyle 1 2 N Z kozhnogo klyucha za opisanim vishe sposobom otrimuyemo lancyuzhok klyuchiv dovzhini t displaystyle t Ostannij element i displaystyle i go lancyuzhku poznachayemo yak EPi displaystyle EP i todi ochevidno EPi ft SPi displaystyle EP i f t SP i V pam yat zapisuyemo lishe pochatkovij i kincevij klyuchi kozhnogo lancyuzhka SPi EPi displaystyle SP i EP i pari sortuyemo za kincevim klyuchem Takim chinom gotova tablicya zajmaye O m displaystyle O m komirok pam yati SP1 X10 fX11 fX12 f fX1t EP1SP2 X20 fX21 fX22 f fX2t EP2 SPm Xm0 fXm1 fXm2 f fXmt EPm displaystyle begin bmatrix SP 1 amp X 10 overset underset mathrm f to X 11 overset underset mathrm f to X 12 overset underset mathrm f to cdots overset underset mathrm f to X 1t amp EP 1 SP 2 amp X 20 overset underset mathrm f to X 21 overset underset mathrm f to X 22 overset underset mathrm f to cdots overset underset mathrm f to X 2t amp EP 2 vdots amp amp vdots SP m amp X m0 overset underset mathrm f to X m1 overset underset mathrm f to X m2 overset underset mathrm f to cdots overset underset mathrm f to X mt amp EP m end bmatrix Utvorennya tablici vimagaye mt displaystyle mt operacij Po otrimanni shifrotekstu kriptoanalitik mozhe zastosuvati funkciyu redukciyi dlya otrimannya Y1 R C0 f K displaystyle Y 1 R C 0 f K todi vin mozhe pereviriti chi prisutnij Y1 displaystyle Y 1 sered SP displaystyle SP SPi EPi displaystyle SP i EP i zberigayutsya vidsortovanimi otzhe cya operaciya zajme log m displaystyle log m a z vikoristannyam gesh tablici skladnist mozhna zvesti majzhe do konstantnogo chasu Yaksho Y1 displaystyle Y 1 ne sered EP displaystyle EP todi K displaystyle K ne v stovpchiku Xit displaystyle X it Yaksho Y1 EPi displaystyle Y 1 EP i todi K Xi t 1 displaystyle K X i t 1 abo EP displaystyle EP maye bilsh yak odin pershovzir Mi nazivatimemo taku situaciyu hibnoyu trivogoyu angl false alarm Yaksho Y1 EPi displaystyle Y 1 EP i todi kriptoanalitik obchislyuye Xi t 1 displaystyle X i t 1 i pereviryaye chi ce klyuch napriklad cherez obchislennya chi deshifruye vin C0 displaystyle C 0 v P0 displaystyle P 0 Vsi promizhni stovpchiki v tablici buli vidkinuti dlya zberezhennya pam yati tomu kriptoanalitik musit pochati v SP displaystyle SP i pereobchisliti Xi 1 Xi 2 displaystyle X i 1 X i 2 cdots doki vin ne dosyagne Xi t 1 displaystyle X i t 1 Yaksho Y1 displaystyle Y 1 ne kinceva tochka abo stalas hibna trivoga kriptoanalitik obchislyuye Y2 f Y1 displaystyle Y 2 f Y 1 i pereviryaye na kincevist yiyi Yaksho ce ne tak klyuch ne v t 2 displaystyle t 2 stovpchiku yaksho zh tak todi kriptoanalitik pereviryaye chi klyuch Xi t 2 displaystyle X i t 2 I tak dali do 0 stovpchika Vidnajdennya klyucha takim chinom zajmaye O t log m displaystyle O t cdot log m nehtuyuchi logarifmichnim mnozhnikom mayemo O t displaystyle O t Pri comu zatrati pam yati na zberezhennya tablici stanovlyat O m displaystyle O m Yaksho vsi elementi v tablici rizni todi jmovirnist uspihu stanovit P S mt N displaystyle P S mt N Ale taka situaciya ne realistichna cherez mozhlivist zlittya lancyuzhkiv Yaksho f displaystyle f ye vipadkovoyu funkciyeyu sho vidobrazhaye mnozhinu 1 2 N displaystyle 1 2 cdots N v sebe i yaksho klyuch K displaystyle K vibrali rivnomirno vipadkovo z ciyeyi mnozhini vtim yakisna kriptosistema povinna buti psevdovipadkovim generatorom todi jmovirnist uspihu mozhna obmezhiti znizu yak P S 1N i 1m j 0t 1 1 itN j 1 displaystyle P S geq frac 1 N sum limits i 1 m sum limits j 0 t 1 1 frac it N j 1 Ocinka cogo virazu prizvodit do nastupnogo vislidu dobutok mt2 displaystyle mt 2 ne varto brati bilshim vid N displaystyle N inakshe shvidko padaye nizhnya mezha jmovirnosti uspihu Za mt2 N displaystyle mt 2 N otrimayemo P S 0 8mtN 1t displaystyle P S geq 0 8 frac mt N frac 1 t Lancyuzhki obchisleni iz riznimi funkciyami redukciyi mozhut peretinatis ale ne zillyutsya Kriptoanalitik teper mozhe utvoriti ne odnu a l displaystyle l tablic v kozhnij vin mozhe vibrati svoyu funkciyu redukciyi sho dozvolit uniknuti zlittya lancyuzhkiv z riznih tablic Pri comu mezha uspishnosti rozshifruvannya stanovitime P S l 1 1N i 1m j 0t 1 1 itN j 1 l displaystyle P S l geq 1 frac 1 N sum limits i 1 m sum limits j 0 t 1 1 frac it N j 1 l Ochikuvana kilkist hibnih trivog na tablicyu obmezhena E F mt t 1 2N displaystyle E F leq mt t 1 2N Vibrav l t displaystyle l t kriptoanalitik otrimaye zatrati mt displaystyle mt po pam yati i t2 displaystyle t 2 po chasu u kozhnij tablici vikoristana svoya funkciya redukciyi tomu pri rozshifruvanni neobhidno otrimuvati svij lancyuzhok dlya kozhnoyi tablici pri jmovirnosti uspihu blizkoyi do odinici Vzyav t m N1 3 displaystyle t m N 1 3 otrimayemo potribni zatrati N2 3 displaystyle N 2 3 po chasu i pam yati PrimitkiMartin 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 PosilannyaMartin Hellman A Cryptanalytic Time Memory Trade Off 4 bereznya 2016 u Wayback Machine Philippe Oechslin Making a Faster Cryptanalytic Time Memory Trade Off Arhivovano 27 lyutogo 2012 u WebCite Mark Stamp Once Upon a Time Memory Tradeoff 5 zhovtnya 2021 u Wayback Machine