เอาต์พุต DES SBOX พร้อม Bitslice

อัลกอริทึมดั้งเดิมของ Eli Biham เพื่อใช้ S-box ขนาด 6 ถึง 4 บิตตามที่อธิบายไว้ใน กระดาษของ Matthew Kwan คือการ

• แยกบิตอินพุตสองบิตออก $i_1$ และ $i_2$
• สร้างทั้งหมด $2^{(2^2)}=16$ ฟังก์ชันบิตเดียวของ $i_1$ และ $i_2$, พูด $f_0$ ถึง $f_{15}$
• อธิบายเอาต์พุตทั้งสี่ของ S-box แต่ละรายการว่าเป็นฟังก์ชันใด $f_j$ ต้องไปที่ผลลัพธ์นั้นสำหรับแต่ละรายการ $2^4=16$ การรวมกันของสี่บิตอินพุตอื่น ๆ $i_3$ $i_4$ $i_5$ $i_6$ ของ S-box และนำไปใช้โดยใช้ดิจิตอลมัลติเพล็กซ์สี่ชั้นสำหรับแต่ละเอาต์พุต:
  • สำหรับแต่ละ $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\operatorname{NAND}\bar{i_3})\operatorname{NAND}(f_7\operatorname{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\times(8+4+2+1)\times3=180$ $\operatorname{NAND}$ ประตู (บวก $4$ อินเวอร์เตอร์สำหรับ $i_3$ $i_4$ $i_5$ $i_6$ หากจำเป็นต้องนำมาพิจารณา)

สามารถเพิ่มประสิทธิภาพได้หลายอย่าง รวมถึง:

1. โดยใช้ $\operatorname{XOR}$ ซึ่งอนุญาตให้มีการมัลติเพล็กซ์ด้วยสองเกท/คำแนะนำแทนที่จะเป็นสาม เช่น เราคำนวณ $((f_4\operatorname{XOR}f_7)\operatorname{AND}i_3)\operatorname{XOR} f_4$สังเกตว่า $f_4\ชื่อผู้ประกอบการ{XOR}f_7$ มาฟรีเนื่องจากยังคงเป็นฟังก์ชันของ $i_1$ และ $i_2$ดังนั้น $f_j$, มีแนวโน้ม $f_3$ สำหรับจำนวนธรรมชาติ เช่นเดียวกันสำหรับขั้นตอนการมัลติเพล็กซ์ในภายหลัง โดยปรับสิ่งที่คำนวณในขั้นตอนก่อนหน้านี้ การเพิ่มประสิทธิภาพนี้มีประสิทธิภาพมากในซอฟต์แวร์ มันอยู่ในการดำเนินการของ Biham และในบัญชีของ Kwan
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