Просторово-часова домовленість: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
Рядок 32:
<center><math>~C_0 = S_k(P_0)</math></center>
Задача — знайти ключ <math>~k</math>, за допомогою якого здійснювалось шифрування. Для цього треба знайти спосіб обчислення можливих ключів. Введемо функцію редукції
<center><math>~R(C_i) = k_{i+1}</math></center>
Рядок 43:
Для того, щоб побудувати таблицю пошуку, криптоаналітик вибирає <math>~m</math> випадкових елементів <math>SP_1, SP_2, ..., SP_m</math> із простору ключів <math>\{1, 2, ..., N\}</math>. З кожного ключа за описаним вище способом отримуємо ланцюжок ключів довжини <math>~t</math>. Останній елемент <math>i</math>-го ланцюжку позначаємо як <math>EP_i</math>, тоді очевидно <math>EP_i = f^t(SP_i)</math>. В пам'ять записуємо лише ''початковий'' і ''кінцевий'' ключі кожного ланцюжка <math>\{SP_i, EP_i\}</math> (пари сортуємо за кінцевим ключем). Таким чином, готова таблиця займає <math>O(m)</math> комірок пам'яті. Утворення таблиці вимагає <math>~mt</math> операцій.
<math>
\begin{bmatrix}
SP_1 & = 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} = & EP_1 \\
SP_2 & = 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} = & EP_2 \\
\vdots & & \vdots \\
SP_m & = 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} = & EP_m \\
\end{bmatrix}
</math>
== Примітки ==
| |||