[原创]SHA-3(Keccak)算法5比特S盒的双射性质证明

SHA-3(Keccak)算法5比特S盒的双射性质证明SHA-3(Keccak)为美国第三代Hash算法标准，其整体结构创新性的采用了海绵结构。对Keccak的分析表明，海绵结构能够抵抗现有的各种攻击方法，比如生日攻击，碰撞攻击，原像攻击，第二原像攻击等。海绵结构的安全性久经考验，至今未发现有效的攻击方法。Keccak的置换函数Keccak-f[1600]共24轮，每轮置换Keccak-p包含以下5个步骤（顺序为θ→ρ→π→χ→ι）：     1. θ（Theta）：列间线性混合，通过异或相邻列实现扩散。     2. ρ（Rho）：对每个lane进行循环移位，增加位的混淆。     3. π（Pi）：重新排列lane的位置，打乱矩阵布局。     4. χ（Chi）：非线性的行变换，增强算法的非线性特性。     5. ι（Iota）：添加轮常数，打破对称性，每轮常数不同。轮置换Keccak-p共分为5步，除了第4步为5比特S盒(KS)变换外，其余4步均为线性变换。KS提供了Keccak算法必需的混淆性和非线性复杂度，其简单高效的设计吸引了广大密码学者的注意。由于Keccak-p为非线性置换，故该5比特S盒也为非线性置换。换种说法，KS为从F到F上的双射。什么是双射？双射是满足既是单射又是满射的映射，亦称“一一映射”。什么是单射？设f是由集合A到集合B的映射，如果所有x，y∈A，且x≠y，都有f(x)≠f(y)，则称f为由A到B的单射。什么是满射？设A和B是两个集合，如果从A到B的对应f：A→B是映射，并且集合B中的每一个元素在集合A中都有原象，那么映射f就叫做从A到B的满射。下图为KS的5个分量布尔函数表达式： 下图为KS的输入输出查找表： 下面我将通过KS的代数表达式从理论上来证明其为双射。证明：令M=M4||M3||M2||M1||M0，N=N4||N3||N2||N1||N0。其中F4=M4⊕N4，F3=M3⊕N3，F2=M2⊕N2，F1=M1⊕N1，F0=M0⊕N0。F=F4||F3||F2||F1||F0。令P=P4||P3||P2||P1||P0=FFFFF(M），Q=Q4||Q3||Q2||Q1||Q0=FFFFF(N）。其中G4=P4⊕Q4，G3=P3⊕Q3，G2=P2⊕Q2，G1=P1⊕Q1，G0=P0⊕Q0。G=G4||G3||G2||G1||G0。其中Mi(i=0,1,2,3,4)，Ni(i=0,1,2,3,4)，Pi(i=0,1,2,3,4)，Qi(i=0,1,2,3,4)，Fi(i=0,1,2,3,4)，Gi(i=0,1,2,3,4)的取值为0或1。假设存在Fi(i=0,1,2,3,4)不全为0，使得Gi(i=0,1,2,3,4)同时为0。（1）wt(F)=1，F取值有C(5,1)=5种可能的情形。这5种情形等价，故只用考虑其中一种情况。令F=(F4,F3,F2,F1,F0)=(0,0,0,0,1)，则G0=P0⊕Q0=(M4∧F0)⊕(M0∧F4)⊕(F4∧F0)⊕F4⊕F1=M4G1=P1⊕Q1=(M0∧F1)⊕(M1∧F0)⊕(F0∧F1)⊕F0⊕F2=M1⊕1G2=P2⊕Q2=(M1∧F2)⊕(M2∧F1)⊕(F1∧F2)⊕F1⊕F3=0G3=P3⊕Q3=(M2∧F3)⊕(M3∧F2)⊕(F2∧F3)⊕F2⊕F4=0G4=P4⊕Q4=(M3∧F4)⊕(M4∧F3)⊕(F3∧F4)⊕F3⊕F0=1G4不等于0，故此种情形下假设不成立。（2）wt(F)=2，有C(5,2)=10种可能的情形。F=(F4,F3,F2,F1,F0)=(0,0,0,1,1)   ①F=(F4,F3,F2,F1,F0)=(0,0,1,0,1)   ②F=(F4,F3,F2,F1,F0)=(0,1,0,0,1)   ③F=(F4,F3,F2,F1,F0)=(1,0,0,0,1)   ④F=(F4,F3,F2,F1,F0)=(0,0,1,1,0)   ⑤F=(F4,F3,F2,F1,F0)=(0,1,0,1,0)   ⑥F=(F4,F3,F2,F1,F0)=(1,0,0,1,0)   ⑦F=(F4,F3,F2,F1,F0)=(0,1,1,0,0)   ⑧F=(F4,F3,F2,F1,F0)=(1,0,1,0,0)   ⑨F=(F4,F3,F2,F1,F0)=(1,1,0,0,0)   ⑩其中情形④⑤⑧⑩与情形①等价，情形③⑥⑦⑨与情形②等价，故只用考虑①和②2种情形。情形①：令F=(F4,F3,F2,F1,F0)=(0,0,0,1,1)，则G0=P0⊕Q0=(M4∧F0)⊕(M0∧F4)⊕(F4∧F0)⊕F4⊕F1=M4⊕1G1=P1⊕Q1=(M0∧F1)⊕(M1∧F0)⊕(F0∧F1)⊕F0⊕F2=M0⊕M1G2=P2⊕Q2=(M1∧F2)⊕(M2∧F1)⊕(F1∧F2)⊕F1⊕F3=M2⊕1G3=P3⊕Q3=(M2∧F3)⊕(M3∧F2)⊕(F2∧F3)⊕F2⊕F4=0


回复或点赞可查看完整内容

---
来源: 看雪论坛
原文链接: https://bbs.kanxue.com/thread-285798.htm

哎，非要整的文绉绉的，还弄一些术语（不是针对楼主，而是说的这些算法的论文）。什么双射、满射， 不就是对  0-31、 0-255 进行类似洗牌算法打乱，然后直接取数组操作吗？

这个不是文邹邹，这是群论里面的术语
表面看是洗牌打乱，实际上是取了所有打乱排列中的1种，而这一种是为了满足某个运算公式，运算公式是能够确保这个非线性变换中的密码学安全强度。
楼主写东西，实际上是反过来的，先给出了运算公式（能有很高的安全强度），然后证明它是你说的洗牌算法打乱所有可能性的一种（满足双射）