На рисунке ниже представлена иллюстрация к алгоритму. Сначала опишу алгоритм, а потом что требуется сделать и какие вопросы. На предварительном этапе для нелинейного преобразования S составляется таблица DDT размером 256 * 256. В ячейку (i, j) этой таблицы записывается число пар с входной разностью i и выходной разностью j. При этом разность оценивается с помощью побитового сложения по модулю 2.
Вот алгоритм сложность которого интересует:
1) выбираем случайно 3 ненулевых байта для состояния 4 (на рисунке выделены желтым цветом);
2) применяем преобразования L и T к этому состоянию и получаем значения байтов для состояния 3;
3) для каждой строки состояния 1 выполняем следующие шаги:
3.1) установить значение желтого байта равным 0;
3.2) увеличить значение желтого байта на 1;
3.3) умножаем строку состояния 1 на матрицу линейного преобразования и получаем строку в сост-ии 2;
3.4) с помощью ранее заготовленной таблицы проверяем, есть ли пары байтов у которых входная
разность определяется состоянием 2, а выходная разность состоянием 3. Если да, то переходим к
обработке следующей строки.
3.5) если значение байта < 255, то переходим к шагу 3.2. В противном случае переходим к шагу 1.
Вот как я пытаюсь получить теоретическую оценку сложности. Пусть p - это вероятность того, что для выходной разности (байт) в строке состояния 3, есть входная разность в соответствующей позиции состояния 2. Значение p можно получить из анализа DDT. Тогда вероятность того, что для данной строки состояния 3 существует входная строка равна
. Следовательно, вероятность того, что для всех строк состояния 3 существуют входные строки в состоянии 2 равна
. Значение p примерно равно 0.5. Следовательно, средняя трудоемкость равна
. В чем здесь ошибка? На практике получаю, что сложность значительно меньше.
18.08.2014, 10:13 
ом, текст на картинке