Вывод DES SBOX с помощью Bitslice

Оригинальный алгоритм Эли Бихама для реализации любого 6-4-битного S-блока, как описано в Статья Мэтью Квана это

• Выделите два входных бита, скажем $i_1$ и $i_2$
• Построить все $2^{(2^2)}=16$ однобитовые функции $i_1$ и $i_2$, сказать $f_0$ к $f_{15}$
• Опишите каждый из четырех выходов S-блока, какая из этих функций $f_j$ должен перейти к этому выходу для каждого из $2^4=16$ комбинации четырех других входных битов $i_3$ $i_4$ $i_5$ $i_6$ S-блока и реализовать это, используя четыре уровня цифрового мультиплексирования для каждого выхода:
  • Для каждого из $2^3=8$ комбинации $i_4$ $i_5$ $i_6$, выбираем по $i_3$ который $f_j$ нужно. Например.если для определенного выхода и определенной комбинации $i_4$ $i_5$ $i_6$ нам нужно выбрать $f_4$ когда $i_3=0$ и $f_7$ когда $i_3=1$, то мы можем сделать это как $(f_4\имя_оператора{NAND}\bar{i_3})\имя_оператора{NAND}(f_7\имя_оператора{NAND}i_3)$, стоимость $3$ ворота (без учета стоимости инвертирования $i_3$). Таким образом, этот этап будет стоить $4\times8\times3=96$ общее количество ворот (но см. оптимизацию 1 ниже).
  • Для каждого из $2^2=4$ комбинации $i_5$ $i_6$, выбираем по $i_4$ какая из двух функций более раннего этапа необходима.
  • Для каждого из $2$ ценности $i_6$, выбираем по $i_5$ какая из двух функций более раннего этапа необходима.
  • Мы подбираем в соответствии $i_6$ какая из двух функций более раннего этапа необходима.

Вышеприведенное выполняет мультиплексирование с $4\раз(8+4+2+1)\раз3=180$ $\имя_оператора{И-НЕ}$ ворота (плюс $4$ инверторы для $i_3$ $i_4$ $i_5$ $i_6$ если их нужно учитывать).

Возможны многие оптимизации, в том числе:

1. С использованием $\имя_оператора{исключающее ИЛИ}$ что позволяет мультиплексировать с двумя воротами/инструкциями вместо трех, например. мы вычисляем $((f_4\имя оператора{исключающее ИЛИ}f_7)\имя оператора{И}i_3)\имя оператора{исключающее ИЛИ} f_4$, отметив, что $f_4\имя_оператора{исключающее ИЛИ}f_7$ предоставляется бесплатно, так как это по-прежнему функция $i_1$ и $i_2$, таким образом, $f_j$, вероятно $f_3$ для некоторой натуральной нумерации; то же самое для более поздних этапов мультиплексирования, регулируя то, что вычисляют более ранние этапы. Эта оптимизация очень эффективна в программном обеспечении. Это в реализации Бихама и в аккаунте Квана.
2. Вычисления $8$ скорее, чем $16$ функции $f_j$, регулируя полярность при мультиплексировании.
3. В некоторых случаях повторное использование функции (за пределами $f_j$) через несколько выходов S-box.
4. В некоторых случаях не нужны все функции $f_j$, потому что один случается не используется.
5. В некоторых случаях можно удалить этап мультиплексирования, потому что вход мультиплексирования не влияет на желаемый результат.
6. В некоторых случаях можно упростить мультиплексор, потому что один из его входных данных является постоянным.
7. Переупорядочивание вещей, которые могут (входы $i_j$, входы данных мультиплексоров, порядок мультиплексирования битов $i_3$ $i_4$ $i_5$ $i_6$ для каждого выхода), чтобы максимизировать появление 3/4/5/6.