类SHA-3(Keccak)5比特S盒变换的非双射性质证明

什么是单射？

   对于映射f，当x1不等于x2，有f(x1)不等于f(x2)。

什么是满射？

   对于映射f，对所有的y，都存在x使得f(x)=y。

什么是双射？

   对于映射f，满足既是单射又是满射。

SHA-3(Keccak)5比特S盒变换F如下图所示：

类SHA-3(Keccak)5比特S盒变换G如下图所示：

关于SHA-3(Keccak)算法5比特S盒的双射性质证明详见https://bbs.kanxue.com/thread-285798.htm。

双射性质在密码学中的应用

   在分组密码中：对于SPN结构的密码算法，在不考虑其它的安全要求之外，最基本的要求就是算法必须可逆(保证算法既可以加密又可以解密)，也即S盒和P盒都可逆，也即混淆层和扩散层都是置换(双射)。对于Feistel结构的密码算法，由于其加解密的一致性，通常不要求其轮函数为双射，但是为了加密和解密过程中输出比特的平衡性，在设计Feistel结构的密码算法时，最好是选择满足双射性质的轮函数。

   在序列密码中：对于基于LFSR或NFSR结构的序列密码算法，应该选择平衡的反馈函数，过滤函数和密钥流生成算法作为基本部件。如果这些基本部件不是平衡函数，意味着最终输出的密钥流不是平衡的，这会导致致命的弱点使得敌手可以根据相关的密码分析方法对该算法进行攻击。

   在杂凑密码中：由于消息扩展算法的存在，密码杂凑算法通常不是双射，但是其压缩函数基本都是双射。因为双射意味着输出比特的0-1平衡性，这说明该密码算法的统计特性较好，更加接近随机变换，这增加了敌手破解该算法的困难程度。一般来说，若压缩函数是双射，则更易证明杂凑算法的安全性。

   根据双射性质的定义可知，如果映射f为双射，那么f同时满足单射和满射的性质，也就是说二者缺一不可。如果可以证明映射f不满足单满射二者中的一个性质，那么就可以证明f不是双射。

以下我将通过给出反例的方式来证明类SHA-3(Keccak)5比特S盒变换不是双射。

证明：类SHA-3(Keccak)5比特S盒变换不是双射。

   记A=(a0,a1,a2,a3,a4)和B=(b0,b1,b2,b3,b4)为二元域上的5维向量，其中ai和bi的取值为0或1。

   令a0=a1=a2=a3=a4=0，b0=b1=b2=b3=b4=1，分别计算G(A)和G(B)的值。

   记C=(c0,c1,c2,c3,c4)=G(A)=G(a0,a1,a2,a3,a4)

c0=a4∧a0⊕a1=0

c1=a0∧a1⊕a2=0

c2=a1∧a2⊕a3=0

c3=a2∧a3⊕a4=0

c4=a3∧a4⊕a0=0

则C=(c0,c1,c2,c3,c4)=0

传播安全知识、拓宽行业人脉——看雪讲师团队等你加入！