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为从F25到F25上的双射。
什么是双射？
双射是满足既是单射又是满射的映射，亦称“一一映射”。
什么是单射？
设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=M4
G1=P1⊕Q1=(M0∧F1)⊕(M1∧F0)⊕(F0∧F1)⊕F0⊕F2=M1⊕1
G2=P2⊕Q2=(M1∧F2)⊕(M2∧F1)⊕(F1∧F2)⊕F1⊕F3=0
G3=P3⊕Q3=(M2∧F3)⊕(M3∧F2)⊕(F2∧F3)⊕F2⊕F4=0
G4=P4⊕Q4=(M3∧F4)⊕(M4∧F3)⊕(F3∧F4)⊕F3⊕F0=1
G4不等于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⊕1
G1=P1⊕Q1=(M0∧F1)⊕(M1∧F0)⊕(F0∧F1)⊕F0⊕F2=M0⊕M1
G2=P2⊕Q2=(M1∧F2)⊕(M2∧F1)⊕(F1∧F2)⊕F1⊕F3=M2⊕1
G3=P3⊕Q3=(M2∧F3)⊕(M3∧F2)⊕(F2∧F3)⊕F2⊕F4=0
G4=P4⊕Q4=(M3∧F4)⊕(M4∧F3)⊕(F3∧F4)⊕F3⊕F0=1
G4不等于0，故此种情形下假设不成立。
情形②：令F=(F4,F3,F2,F1,F0)=(0,0,1,0,1)，则
G0=P0⊕Q0=(M4∧F0)⊕(M0∧F4)⊕(F4∧F0)⊕F4⊕F1=M4
G1=P1⊕Q1=(M0∧F1)⊕(M1∧F0)⊕(F0∧F1)⊕F0⊕F2=M1
G2=P2⊕Q2=(M1∧F2)⊕(M2∧F1)⊕(F1∧F2)⊕F1⊕F3=M1
G3=P3⊕Q3=(M2∧F3)⊕(M3∧F2)⊕(F2∧F3)⊕F2⊕F4=M3⊕1
G4=P4⊕Q4=(M3∧F4)⊕(M4∧F3)⊕(F3∧F4)⊕F3⊕F0=1
G4不等于0，故此种情形下假设不成立。
（3）wt(F)=3，有C(5,3)=10种可能的情形。
F=(F4,F3,F2,F1,F0)=(0,0,1,1,1) ①
F=(F4,F3,F2,F1,F0)=(0,1,0,1,1) ②
F=(F4,F3,F2,F1,F0)=(1,0,0,1,1) ③
F=(F4,F3,F2,F1,F0)=(0,1,1,0,1) ④
F=(F4,F3,F2,F1,F0)=(1,0,1,0,1) ⑤
F=(F4,F3,F2,F1,F0)=(1,1,0,0,1) ⑥
F=(F4,F3,F2,F1,F0)=(0,1,1,1,0) ⑦
F=(F4,F3,F2,F1,F0)=(1,0,1,1,0) ⑧
F=(F4,F3,F2,F1,F0)=(1,1,0,1,0) ⑨
F=(F4,F3,F2,F1,F0)=(1,1,1,0,0) ⑩
其中情形③⑥⑦⑩与情形①等价，情形④⑤⑧⑨与情形②等价，故只用考虑①和②2种情形。
情形①：令F=(F4,F3,F2,F1,F0)=(0,0,1,1,1)，则
G0=P0⊕Q0=(M4∧F0)⊕(M0∧F4)⊕(F4∧F0)⊕F4⊕F1=M4⊕1
G1=P1⊕Q1=(M0∧F1)⊕(M1∧F0)⊕(F0∧F1)⊕F0⊕F2=M0⊕M1⊕1
G2=P2⊕Q2=(M1∧F2)⊕(M2∧F1)⊕(F1∧F2)⊕F1⊕F3=M1⊕M2
G3=P3⊕Q3=(M2∧F3)⊕(M3∧F2)⊕(F2∧F3)⊕F2⊕F4=M3⊕1
G4=P4⊕Q4=(M3∧F4)⊕(M4∧F3)⊕(F3∧F4)⊕F3⊕F0=1
G4不等于0，故此种情形下假设不成立。
情形②：令F=(F4,F3,F2,F1,F0)=(0,1,0,1,1)，则
G0=P0⊕Q0=(M4∧F0)⊕(M0∧F4)⊕(F4∧F0)⊕F4⊕F1=M4⊕1
G1=P1⊕Q1=(M0∧F1)⊕(M1∧F0)⊕(F0∧F1)⊕F0⊕F2=M0⊕M1
G2=P2⊕Q2=(M1∧F2)⊕(M2∧F1)⊕(F1∧F2)⊕F1⊕F3=M2
G3=P3⊕Q3=(M2∧F3)⊕(M3∧F2)⊕(F2∧F3)⊕F2⊕F4=M2
G4=P4⊕Q4=(M3∧F4)⊕(M4∧F3)⊕(F3∧F4)⊕F3⊕F0=M4
G0和G4不同时等于0，故此种情形下假设不成立。
（4）wt(F)=4，有5种可能的情形。这5种可能等价，故只用考虑其中一种情况。
令F=(F4,F3,F2,F1,F0)=(0,1,1,1,1)，则
G0=P0⊕Q0=(M4∧F0)⊕(M0∧F4)⊕(F4∧F0)⊕F4⊕F1=M4⊕1
G1=P1⊕Q1=(M0∧F1)⊕(M1∧F0)⊕(F0∧F1)⊕F0⊕F2=M0⊕M1⊕1
G2=P2⊕Q2=(M1∧F2)⊕(M2∧F1)⊕(F1∧F2)⊕F1⊕F3=M1⊕M2⊕1
G3=P3⊕Q3=(M2∧F3)⊕(M3∧F2)⊕(F2∧F3)⊕F2⊕F4=M2⊕M3
G4=P4⊕Q4=(M3∧F4)⊕(M4∧F3)⊕(F3∧F4)⊕F3⊕F0=M4
G0与G4不同时为0，故此种情形下假设不成立。
（5）wt(F)=5，有1种可能。
令F=(F4,F3,F2,F1,F0)=(1,1,1,1,1)，则
G0=P0⊕Q0=(M4∧F0)⊕(M0∧F4)⊕(F4∧F0)⊕F4⊕F1=M4⊕M0⊕1
G1=P1⊕Q1=(M0∧F1)⊕(M1∧F0)⊕(F0∧F1)⊕F0⊕F2=M0⊕M1⊕1
G2=P2⊕Q2=(M1∧F2)⊕(M2∧F1)⊕(F1∧F2)⊕F1⊕F3=M1⊕M2⊕1
G3=P3⊕Q3=(M2∧F3)⊕(M3∧F2)⊕(F2∧F3)⊕F2⊕F4=M2⊕M3⊕1
G4=P4⊕Q4=(M3∧F4)⊕(M4∧F3)⊕(F3∧F4)⊕F3⊕F0=M3⊕M4⊕1
G0⊕G1⊕G2⊕G3⊕G4=1，故Gi(i=0,1,2,3,4)不同时为0，故此种情形下假设不成立。
综上所述，不存在Fi(i=0,1,2,3,4)不全为0，使得Gi(i=0,1,2,3,4)同时为0。
所以FFFFF为双射。