SHA-3算法的计算过程详解
SHA-3算法的计算过程详解
SHA-3算法的计算过程详解
主要参考文档SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions
1. 几个重要参数：
- 存储状态S的比特位宽为b，其中b ∈ {25，50，100，200，400，800，1600}，可以写作b = 25 × 2^l，l∈{0，1，⋯ ，6}；
- 存储状态S可以分为比特率和容量两部分，其比特位宽分别为r和c，很明显b = r+c；
2. 计算过程：
填充：
在消息M后加入1、最少个数的0和1，即：100 ⋯ 001，使填充后的消息长度是r (0≤r≤b)的整数倍。加入的比特长度至少是2比特，最多是r+1比特。
记填充后的消息为P，n = len(P)/r。即将P分成n段，记为P = P_0||P_2||\cdots ||P_{n-1}||P_{n}，每段长度为r。吸收阶段：
S_{i+1}=f(S_{i}⊕(P_i ∣∣0^c))
在吸收阶段，首先将S初始化为零，记初始状态为S_0。
每一轮运算中先将P_i后填充长度为c的0，再与长度为b的S_i进行异或运算，其结果S_i'经过f函数后作为下一轮的新状态S_{i+1}，这过程一直重复到所有的输入都用完为止，即进行n轮这样的运算。
在介绍f函数之前，先要介绍一种存储结构的转换S_i'→A：
S_i'是比特串，而状态A可以表示为一个5 × 5 × w的三维数组，其中w = b/25。
状态数组中的每一位可以用A[x,y,z]表示，则有A[i][ j][k] =S_i'[(5j + i) × w + k]，S_i'的下标索引采用小端模式，其中i表示行，j表示列，k表示比特。转换的例子如下所示：
那么，如何将状态矩阵又转换成比特串呢？按照Lane(i, j)、Plane(j)和S的顺序逐次转换；
Lane(i, j) = A[i, j, 0] || A[i, j, 1] || A[i, j, 2] || … || A[i, j, w-2] || A[i, j, w-1]，其中0 ≤ i < 5 , 0 ≤ j < 5
Plane(j) = Lane(0, j) || Lane(1, j) || Lane(2, j) || Lane(3, j) || Lane(4, j)，其中0 ≤ j < 5
S = Plane(0) || Plane(1) || Plane(2) || Plane(3) || Plane(4)
同样来举个例子吧；
SHA-3标准中共有5个映射函数，可以对状态数组A进行不同的排列，下面简要进行介绍。
θ(A)：0 ≤ x < 5, 0 ≤ y < 5, and 0 ≤ z < w
C[x, z] = A[x, 0, z] ⊕ A[x, 1, z] ⊕ A[x, 2, z] ⊕ A[x, 3, z] ⊕ A[x, 4, z]
D[x, z] = C[(x-1) mod 5, z] ⊕ C[(x+1) mod 5, (z – 1) mod w]
A'[x, y, z] = A[x, y, z] ⊕ D[x, z]
从图形上来看，就是计算某一比特对应两列的奇偶校验值，再与该比特异或的过程。
ρ(A)对25个Lane进行循环移位：
对于不同Lane的偏移量是可以预计算的，计算结果如下：
从状态矩阵上来看，图形如下所示，注意是循环移位：
π(A)对25个Slice进行固定的换位：
从状态矩阵来看，效果如下所示，注意中间点(x,y)=(0,0)
χ(A)沿row进行比特组合：
从状态矩阵来看，效果如下所示，注意这是对于x的：
ι(A, i_r)修改Lane(0,0)中的某些比特，其他24个Lane(0,0)则不受影响：
RC[z]开始被初始化为w比特的全0，然后对某些比特进行修改，修改后的比特来自于rc(t)函数。
rc(t)函数的定义如下，类似于一个反馈移位寄存器，运算结果为1比特，j + 7i_r是反馈移位寄存器动作的次数。
介绍完5个映射函数，就可以得到轮函数Rnd(A, i_r)了；
定义完Rnd(A, i_r)，进一步定义Keccak-p[b,n_r]函数，Keccak-p[b,n_r]是对状态矩阵A进行多次Rnd(A, i_r)迭代，i_r作为索引，取不同的值；
Keccak-p[b,n_r]中的n_r是可以取任意正整数的，SHA-3算法中的f函数实际上是Keccak-p[b,n_r]的一种特殊化，即n_r=12+2l；
挤压阶段：
挤压阶段和吸收阶段用的是相同的f函数。吸收阶段每一个f函数之后，将状态矩阵A转化成S，吸收r比特的消息。挤压阶段则每一个f函数之后，生成r比特的摘要。将生成的摘要进行拼接，直到生成摘要的长度大于需要的摘要长度时，进行截断。Trunc_d表示取字符串的前d比特。总结一下：
3. 需要注意的地方：
- Keccak-p[b,n_r]，Keccak-f[b]与Keccak{[c]}(N, d)三者的区别需要注意，否则不太容易理解文档中所描述的东西；
Keccak-p[b,n_r]是广义的置换函数，n_r是可以取任意正整数的；
SHA-3算法中的f函数实际上是Keccak-p[b,n_r]的一种特殊化，即n_r=12+2l，记为Keccak-f[b]；
Keccak{[c]}(N, d)则可以认为是整体的这种海绵结构，包括吸收和挤压阶段，其中b = 1600，c = 1600-r；SPONGE的三个参数分别为f函数、填充规则和r取值，填充规则用正则表达式表示。
Keccak{[c]}(N, d)进一步进行限制，则可以定义为SHA-3算法，其中容量c取摘要长度d的两倍；SHA-3在调用Keccak{[c]}(N, d)函数时，需要对消息进行填充01。