Просторово-часова домовленість: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
Рядок 19:
Криптоаналітичний перебір вимагає значних обчислювальних затрат. У випадку, якщо потрібне багаторазове злам криптосистеми, логічно було б заздалегідь виконати вичерпний перебір і зберігати обчислені значення в пам'яті. Тоді, в подальшому, можна здійснювати перебір практично миттєво.<ref name="Oechslin">''Philippe Oechslin.'' Making a Faster Cryptanalytic Time-Memory Trade-Off. // ISBN 3-540-40674-3.</ref> Втім, цей метод не застосовується в дійсності через надвеликі затрати пам'яті.
=== Метод, запропонований Геллманом ===
1980, [[Мартін Геллман]] запропонував компромісний підхід до проблеми криптоаналізу, що дозволяв аналіз криптосистеми, яка мала <math>N</math> ключів, за <math>N^{2/3}</math> операцій, із затратами по пам'яті також <math>N^{2/3}</math><ref name="Hellman"/>. Це стає можливим по тому, як одноразово буде виконане попереднє отримання можливих ключів, яке потребує <math>O(n)</math> операцій.
Ідея полягає в наступному.
Нехай в алгоритмі шифрування використовується [[одностороння функція]] <math>~S_{k_i}(P)</math>. За властивостями односторонньої функції отримання використаного ключа <math>~k_i</math> по відомій парі <math>~P_0,C_0</math> — складна задача, в той час як обчислення функції від певного відкритого тектсу — проста.
Криптоаналітик застосовує [[Атака на основі підібраного відкритого тексту|атаку на основі підібраного відкритого тексту]] і отримує один шифротекст <math>~C_0</math>, відповідний відкритому тексту <math>~P_0</math>:
<center><math>~C_0 = S_k(P_0)</math></center>
== Примітки ==
| |||