DES SBOX输出

Question

我不明白如何用DES中的位片技术计算6-4-SBOX的输出位。关马修在他的论文“减少比特切尔德的门计数”中做了一个简短的回顾，他的原始文件比汉姆。他写道：

基本上，对于每个S盒，技术是取两个输入位，将它们扩展到两个变量的所有16个可能函数，然后使用剩下的四个S-box输入从这16个函数中进行选择。然而，细节稍微复杂一些。

我相信我理解如何将两个变量扩展到16个函数(从f0到f15)。但是，现在如何选择剩下的4个输入位，全部4个输出？

关家华的论文可以在这里找到：http://fgrieu.free.fr/Mattew%20Kwan%20-%20Reducing%20the%20Gate%20Count%20of%20Bitslice%20DES.pdf

Answer 1

如关家华的论文所述，Eli Biham实现任何6到4位S盒的原始算法是：

• 挑出两个输入位，比如i_1和i_2
• 构建i_1和i_2的所有f_0单比特函数，比如D10 to f_{15}。
• 将S盒的四个输出中的每一个描述为这些函数中的哪一个，f_j需要将这些函数中的哪一个转换到S-box的其他四个输入比特的2^4=16组合的i_3 i_4 i_5 i_6中，并通过对每个输出使用四层数字复用来实现这一点：。
  • 对于每个2^3=8组合的i_4 i_5 i_6，我们根据i_3选择需要哪一个f_j。例如，如果对于特定的输出和i_4 i_5 i_6的某些组合，我们需要在i_3=0时选择f_4，当i_3=1时需要选择f_7，那么我们可以作为(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}门的多路复用(如果需要考虑这些数据，还需要为i_3 i_4 i_5 i_6添加4逆变器)。

许多优化是可能的，包括：

1. 使用\operatorname{XOR}，它允许具有两个门/指令的多路复用，而不是三个门/指令，例如，我们计算((f_4\operatorname{XOR}f_7)\operatorname{AND}i_3)\operatorname{XOR} f_4，注意到f_4\operatorname{XOR}f_7是免费的，因为这仍然是i_1和i_2的函数，因此对于一些自然编号，这是一个f_j，很可能是f_3；对于以后的多路复用阶段，也是一样的，方法是调整早期计算阶段。这种优化在软件中是非常有效的。这是在Biham的实施和关的帐户。
2. 通过调整复用器中的极性，计算8而不是16函数f_j。
3. 在某些情况下，在多个S框输出中重用一个函数(超出f_j)。
4. 在某些情况下，不需要所有的函数f_j，因为其中一个碰巧没有被使用。
5. 在某些情况下，能够移除复用级，因为复用输入对期望的输出没有影响。
6. 在某些情况下，能够简化复用器，因为它的数据输入之一是常数。
7. 重新排序可以(输入i_j、多路复用器的数据输入、每个输出的多路复用位i_3 i_4 i_5 i_6的顺序)，以最大限度地实现3/4/5/6的出现。