Почему сеть Фейстеля работает? Объяснение «на пальцах»

В продолжении статьи ^[1] про blowfish хотелось бы поговорить про его основу — сеть Фейстеля. Люди «в теме» слышали про неё не одну сотню раз — эта сеть используется в подавляющем большинстве блочных шифров. Но вот вам, только честно, что нибудь понятно из картинки справа? Ну, допустим в одну сторону(шифрование) понятно, а обратно?
Если нет, то прошу под коврик

Для начала хотя бы бегло пробегитесь по викистатье ^[2], чтобы в общих чертах понять о чем речь

Для простоты будем работать с блоком, состоящим всего из двух байт. Как гласит википедия ^[2], его нужно попилить пополам и назвать левую часть L, а правую R. Да будет так.

И так, у нас есть две половинки блока, и таинственная функция F. Поехали

• Первое, что нам нужно усвоить — это то, что XOR (обозначается ⊕) — инволютивная операция. Не пинайтесь ногами, это всего лишь означает, что если поксорить одно число с другим дважды, то мы опять искомое получим. Т.е. A xor B Xor B == A.
  Отсюда следует, что можно выстраивать бесконечные цепочки A ⊕ B ⊕ C ⊕ D ⊕… и если мы перексорим всё в обратном порядке, то получим A.
  Например, ((100 ⊕ 200) ⊕ 50) ⊕ 150= 8. Отсюда 8 ⊕ 150 ⊕ 50 ⊕ 200 = 100
• Второй важный момент — в один момент времени изменяется лишь одна половинка блока
• Теперь про «черный ящик» или функцию F. Функция F по идее может быть любой выдуманной функцией (хоть сложным хэшем, хоть тупо возвращающей 0), потому что когда мы будем в обратном порядке всё перексоривать(расшифровывать), то вторым аргументом у нас всегда будет тот же результат функции, что был в процессе шифрования.

Как этот «тот же» получается?

Рассмотрим на примере трех раундов по шагам

Шифрование

0) У нас есть L и R какие то числа Пусть они будут 100 и 200. и F, какая то функция, зависящая от L и номера раунда n. Пусть, к примеру, F будет просто складывать их по модулю 256(чтоб не вылезало за байт). Т.е. F(L, n) = (L+n) % 256. ( % это остаток от деления )

Раунд первый (n =1)
1) Берем R(200) и ксорим его с результатом функции F(L, n), т.е. 200 ⊕ ((100+1) % 256) получаем 173.
2) Ставим 173 на место L, а на место R предыдущее значение L (100), т.е. меняем местами R и результат ксора R с функцией F.

Раунд 2 (n = 2)
1) Теперь L = 173, R = 100. Ксорим 100 c ((173 + 2) % 256), получаем 203
2) Ставим 203 на место L, а 173 на место R.

Раунд 3 (n = 3)
1) L = 203, R = 173. Ксорим 173 c ((203 + 3) % 256), получаем 99
2) Поскольку раунд последний, то меняем только R (чтобы потом перестановку не делать)

После шифрования L = 203, R = 99.

Расшифровка

Идем в обратном порядке, номера раундов идут с 3 и до 1

Раунд 1 (n = 3)
1) L = 203, R = 99. Ксорим 99 с ((203 + 3) % 256) получаем 173. Знакомое число?
2) Ставим 173 на место L, 203 на место R

Раунд 2 (n = 2)
1) L = 173, R = 203. Отсюда 203 ⊕ ((173 + 2) % 256) = 100. Уже почти!
2) Меняем L = 100, R = 173

Раунд 3 (n = 1)
1) L = 100, R = 173. Считаем R(перестановка, как и в случае с шифрованием, не нужна) = 173 ⊕ ((100+1) % 256) = 200 УРАААА!!!

L = 100, R = 200. Как в аптеке )

То есть, вся сеть Фейстеля по сути сводится к поочередному ксору обеих половинок блока с какими то вычисляемыми значениями, которые во время шифрования подставляются в обратном порядке.

Ну и на последок код на java, реализующий описанный выше алгоритм.

public class BlockTest
{
    private static int rounds = 3;

    public void feist(int[] a, boolean reverse)
    {
        int round = reverse ? rounds : 1;
        int l = a[0];
        int r = a[1];

        for (int i = 0; i < rounds; i++)
        {
            if (i < rounds - 1) // если не последний раунд
            {
                int t = l;
                l = r ^ f(l, round);
                r = t;
            }
            else // последний раунд
            {
                r = r ^ f(l, round);
            }

            round += reverse ? -1 : 1;
        }

        a[0] = l;
        a[1] = r;
    }

    private int f(int b, int k)
    {
        return b + k;
    }

    public void test()
    {
        int[] a = new int[2];
        a[0] = 100;
        a[1] = 200;
        feist(a, false);
        feist(a, true);
    }
}

Надеюсь, вам понравилось ;)

Автор: Scratch