Просторово-часова домовленість: відмінності між версіями

[перевірена версія][перевірена версія]
Вилучено вміст Додано вміст
Рядок 58:
 
Якщо <math>Y_1</math> не серед <math>EP</math>, тоді <math>K</math> не в стовпчику <math>X_{it}</math>. Якщо <math>Y_1=EP_i</math>, тоді <math>K=X_{i,t-1}</math> або <math>EP</math> має більш як один першовзір. Ми називатимемо таку ситуацію хибною тривогою ({{lang-en|false alarm}}). Якщо <math>Y_1 = EP_i</math>, тоді криптоаналітик обчислює <math>X_{i,t-1}</math> і перевіряє чи це ключ, наприклад, через обчислення чи дешифрує він <math>C_0</math> в <math>P_0</math>. Всі проміжні стовпчики в таблиці були відкинуті для збереження пам'яті, тому криптоаналітик мусить почати в <math>SP</math> і переобчислити <math>X_{i,1}, X_{i,2}, \cdots</math> доки він не досягне <math>X_{i,t-1}</math>.
 
Якщо <math>Y_1</math> не кінцева точка або сталась хибна тривога, криптоаналітик обчислює <math>Y_2=f(Y_1)</math> і перевіряє на кінцевість її. Якщо це не так, ключ не в <math>t-2</math> стовпчику, якщо ж так, тоді криптоаналітик перевіряє чи ключ <math>X_{i,t-2}</math>. І так далі до 0 стовпчика.
 
Віднайдення ключа таким чином, займає <math>~O(t\cdot log(m))</math>; нехтуючи логаріфмічним множником, маємо <math>~O(t)</math>. При цьому затрати пам'яті на збереження таблиці становлять <math>~O(m)</math>.
 
Якщо всі елементи в таблиці різні, тоді ймовірність успіху становить <math>P(S) = mt/N.</math> Але така ситуація не реалістична через можливість злиття ланцюжків.
 
== Примітки ==