Algoritmul original al lui Eli Biham pentru a implementa orice S-box de 6 până la 4 biți, așa cum este descris în lucrarea lui Matthew Kwan este să
- Evidențiază doi biți de intrare, să zicem $i_1$ și $i_2$
- Construiește totul $2^{(2^2)}=16$ funcții pe un singur bit ale $i_1$ și $i_2$, Spune $f_0$ la $f_{15}$
- Descrieți fiecare dintre cele patru ieșiri ale S-box-ului drept care dintre aceste funcții $f_j$ trebuie să meargă la acea ieșire pentru fiecare dintre $2^4=16$ combinații ale celorlalți patru biți de intrare $i_3$ $i_4$ $i_5$ $i_6$ a S-box-ului și implementați acest lucru utilizând patru straturi de multiplexare digitală pentru fiecare ieșire:
- Pentru fiecare dintre $2^3=8$ combinatii de $i_4$ $i_5$ $i_6$, selectăm în funcție de $i_3$ care $f_j$ Este nevoie. De exemplu.dacă pentru o anumită ieșire și o anumită combinație de $i_4$ $i_5$ $i_6$ trebuie să selectăm $f_4$ când $i_3=0$ și $f_7$ când $i_3=1$, atunci putem face asta ca $(f_4\operatorname{NAND}\bar{i_3})\operatorname{NAND}(f_7\operatorname{NAND}i_3)$, costând $3$ porți (reducerea costului inversării $i_3$). Astfel, această etapă va costa $4\times8\times3=96$ porți totale (dar vezi optimizarea 1 de mai jos).
- Pentru fiecare dintre $2^2=4$ combinatii de $i_5$ $i_6$, selectăm în funcție de $i_4$ care dintre cele două funcții ale etapei anterioare este necesară.
- Pentru fiecare dintre $2$ valori ale $i_6$, selectăm în funcție de $i_5$ care dintre cele două funcții ale etapei anterioare este necesară.
- Selectam in functie de $i_6$ care dintre cele două funcţii ale etapei anterioare este necesară.
Cele de mai sus face multiplexarea cu $4\times(8+4+2+1)\times3=180$ $\operatorname{NAND}$ porți (plus $4$ invertoare pentru $i_3$ $i_4$ $i_5$ $i_6$ dacă acestea trebuie luate în considerare).
Sunt posibile multe optimizări, inclusiv:
- Folosind $\operatorname{XOR}$ care permite o multiplexare cu doua porti/instructiuni in loc de trei, de ex. calculăm $((f_4\operatorname{XOR}f_7)\operatorname{ȘI}i_3)\operatorname{XOR} f_4$, observând că $f_4\operatorname{XOR}f_7$ vine gratuit, deoarece aceasta este încă o funcție a $i_1$ și $i_2$, astfel an $f_j$, probabil $f_3$ pentru o numerotare naturală; același lucru pentru etapele ulterioare de multiplexare, prin ajustarea a ceea ce calculează etapele anterioare. Această optimizare este foarte eficientă în software. Este în implementarea lui Biham și în contul lui Kwan.
- Tehnica de calcul $8$ Decat $16$ funcții $f_j$, prin reglarea polarității în multiplexare.
- În unele ocazii, reutilizarea unei funcții (dincolo de $f_j$) prin mai multe ieșiri S-box.
- În unele ocazii, nu este nevoie de toate funcțiile $f_j$, pentru că unul se întâmplă să nu fie folosit.
- În unele ocazii, posibilitatea de a elimina o etapă de multiplexare, deoarece intrarea de multiplexare nu are nicio influență asupra ieșirii dorite.
- În unele ocazii, posibilitatea de a simplifica un multiplexor, deoarece una dintre datele sale de intrare este constantă.
- Reordonarea lucrurilor care pot (intrarile $i_j$, intrările de date ale multiplexoarelor, ordinea biților de multiplexare $i_3$ $i_4$ $i_5$ $i_6$ pentru fiecare ieșire) pentru a maximiza aparițiile de 3/4/5/6.
