在$\mathbb{F}{2}$上有多少个S$-长度$3$？

Question

有一个简单的方法，如果计数的S-Boxes的长度\ell超过\mathbb{F}_{2}？S-box指的是满足雪崩条件的S-box。

我的意思是，对\ell=2来说，答案是0，这很容易看出，但我想知道是否有一个通用公式，特别是\ell=3？

Answer 1

按照定义，S盒子通常被认为是一对一的.从您的问题中，您希望它是一个固定的位长，比如n.，因此它是从\{0,1\}^n到其自身的一对一映射，即2^n点上的置换。这通常被称为n\times n S框.有2^n!这样的映射。您可以使用Stirling公式或为小型n.计算此公式

例如，2^3!=2^3(2^3-1)\cdots 2\cdot 1=40320.

如果我们从密码学的角度考虑一些S盒子是等价的，那么这个问题就变得更加有趣和复杂。例如，让我们的S盒输入是(x_1,x_2,x_3)，输出是(y_1,y_2,y_3).，人们可能会认为，重新命名这些输入会给您提供相同的S盒。一旦我们开始考虑在其他类似的情况下计算不同的S盒子，事情就变得相当复杂了。

例如，考虑到线性密码分析，人们可能会说，所有的n\times n S盒在非奇异n\times n矩阵的前后乘法和输入输出的常数相加的分析中都是相同的。

一篇很好的论文解决了很多这一点，萨里宁，密码分析的所有4\times 4 S盒可用的这里。