Đầu ra DES SBOX với Bitslice

Thuật toán ban đầu của Eli Biham để triển khai bất kỳ hộp S-box 6 đến 4 bit nào như được mô tả trong Bài viết của Matthew Kwan là để

• Tách ra hai bit đầu vào, giả sử $i_1$ và $i_2$
• Xây dựng tất cả $2^{(2^2)}=16$ chức năng bit đơn của $i_1$ và $i_2$, Nói $f_0$ đến $f_{15}$
• Mô tả từng đầu ra trong số bốn đầu ra của S-box là chức năng nào trong số này $f_j$ cần phải đi đến đầu ra đó cho mỗi $2^4=16$ sự kết hợp của bốn bit đầu vào khác $i_3$ $i_4$ $i_5$ $i_6$ của S-box và thực hiện điều đó bằng cách sử dụng bốn lớp ghép kênh kỹ thuật số cho mỗi đầu ra:
  • Đối với mỗi $2^3=8$ sự kết hợp của $i_4$ $i_5$ $i_6$, chúng tôi chọn theo $i_3$ cái mà $f_j$ là cần thiết. Ví dụ.nếu đối với một đầu ra nhất định và sự kết hợp nhất định của $i_4$ $i_5$ $i_6$ chúng ta cần chọn $f_4$ khi nào $i_3=0$ và $f_7$ khi nào $i_3=1$, sau đó chúng ta có thể làm điều này như $(f_4\operatorname{NAND}\bar{i_3})\operatorname{NAND}(f_7\operatorname{NAND}i_3)$, chi phí $3$ cổng (chiết khấu chi phí đảo ngược $i_3$). Như vậy công đoạn này sẽ tốn $4\times8\times3=96$ tổng số cổng (nhưng xem tối ưu hóa 1 bên dưới).
  • Đối với mỗi $2^2=4$ sự kết hợp của $i_5$ $i_6$, chúng tôi chọn theo $i_4$ chức năng nào trong hai chức năng của giai đoạn trước là cần thiết.
  • Đối với mỗi $2$ giá trị của $i_6$, chúng tôi chọn theo $i_5$ chức năng nào trong hai chức năng của giai đoạn trước là cần thiết.
  • Chúng tôi chọn theo $i_6$ chức năng nào trong hai chức năng của giai đoạn trước là cần thiết.

Ở trên thực hiện ghép kênh với $4\times(8+4+2+1)\times3=180$ $\operatorname{NAND}$ cổng (cộng với $4$ biến tần cho $i_3$ $i_4$ $i_5$ $i_6$ nếu những điều này cần phải được tính đến).

Nhiều tối ưu hóa là có thể, bao gồm:

1. sử dụng $\operatorname{XOR}$ cho phép ghép kênh với hai cổng/lệnh thay vì ba, ví dụ: chúng tôi tính toán $((f_4\operatorname{XOR}f_7)\operatorname{AND}i_3)\operatorname{XOR} f_4$, ghi chú điều đó $f_4\operatorname{XOR}f_7$ miễn phí vì đây vẫn là một chức năng của $i_1$ và $i_2$, do đó một $f_j$, rất có thể $f_3$ cho một số số tự nhiên; tương tự cho các giai đoạn ghép kênh sau này, bằng cách điều chỉnh tính toán của các giai đoạn trước đó. Việc tối ưu hóa này rất hiệu quả trong phần mềm. Đó là trong quá trình thực hiện của Biham và trong tài khoản của Kwan.
2. Tin học $8$ còn hơn là $16$ chức năng $f_j$, bằng cách điều chỉnh phân cực trong ghép kênh.
3. Trong một số trường hợp, việc sử dụng lại một chức năng (ngoài $f_j$) trên nhiều đầu ra S-box.
4. Trong một số trường hợp, không cần tất cả các chức năng $f_j$, bởi vì một cái xảy ra không được sử dụng.
5. Trong một số trường hợp, có thể loại bỏ giai đoạn ghép kênh vì đầu vào ghép kênh không ảnh hưởng đến đầu ra mong muốn.
6. Trong một số trường hợp, có thể đơn giản hóa bộ ghép kênh vì một trong các dữ liệu đầu vào của nó là không đổi.
7. Sắp xếp lại những thứ có thể (đầu vào $i_j$, đầu vào dữ liệu của bộ ghép kênh, thứ tự các bit ghép kênh $i_3$ $i_4$ $i_5$ $i_6$ cho mỗi đầu ra) để tối đa hóa số lần xuất hiện 3/4/5/6.