Hash

SHA-3 算法计算过程总结

哈希算法过程分析

Posted by Nicodechal on 2019-04-08

哈希算法是信息安全领域重要的组成部分，主要包括：

  1. 生成和验证数字签名
  2. 密钥导出 (key derivation)
  3. 伪随机位生成 (pseudorandom bit generation)

SHA-3 算法是第三代标准的哈希函数，基于 Keccak 算法实现。与之前的哈希算法有所不同，SHA-3 算法是基于置换 ( permutation-based ) 的加密函数。本文主要介绍 SHA-3 算法生成哈希结果的流程，下面根据 SHA-3 标准的流程进行简要介绍。本文只介绍到定长输出部分。

开始

输出长度为 X 位的 SHA-3 哈希函数表示为：

SHA3-X(M)\mathrm{SHA3\text{-}X}(M)

下面以输出长度为 256 位的函数为例。标准中，输出长度为 256 位的 SHA-3 函数的表示为

SHA3-256(M)\mathrm{SHA3\text{-}256}(M)

其中 MM 为需要进行哈希的数据。对数据哈希的过程主要基于海绵结构 ( sponge construction ) 进行，因此先介绍一下海绵结构。

海绵结构

海绵结构能够进行数据转换，将任意长的输入转换成任意长的输出。下图是一个海绵结构的示意图。

如图所示，海绵结构包含 3 个重要的组成部分：

  1. 一个对数据进行等长映射的函数 ff，即输出串长度与输入串长度相同，记为 bb。
  2. 一个参数称为比率 ( rate )，记作 rr，是指每轮要吸收的 长度为 bb 的串中数据的长度，剩余部分称为容量，记为 cc，因此，有 b=r+cb = r + c。
  3. 一个填充 ( padding ) 函数，记作 pad(x,m)\mathrm{pad}(x, m)，返回将长度为 mm 的串填充为 xx 的整数倍长度的串。例如 pad(5,2)=010\mathrm{pad}(5, 2) = 010，指将长度为 2 的串填充为 5 的整数倍长度，需要添加一个长度为 3 的串，任意长为 3 的串均可，本例中返回值为 010，其长度为 3。

给定上述组成后，可以对数据进行操作并得到映射结果。形式化定义如下：

SPONGE[f,pad,r]\mathrm{\footnotesize SPONGE}[f, pad, r]

基于该海绵结构可以定义海绵函数，用于将输入转换成指定长度的串，因此，函数有两个参数：1. 输入串 NN，2. 输出长度 dd。函数定义如下：

SPONGE[f,pad,r](N,d)\mathrm{\footnotesize SPONGE}[f, pad, r](N, d)

下面根据图，简要说明海绵函数的执行流程：

  1. 首先对输入 NN 进行填充，使其长度为 rr 的整数倍，结果为 P=N∣∣pad(r,len(N))P = N||\mathrm{pad}(r, len(N))，“∣∣||” 表示串连接。
  2. 记 n=len(P)/rn = len(P)/r，将 PP 分成 nn 段，记为 P=P0∣∣P2∣∣⋯∣∣Pn−1P = P_0||P_2||\cdots ||P_{n-1}，每段长度为 rr。
  3. 定义 S=0bS = 0^b 表示长度为 bb 的 0 串，这个 SS 也被称为状态，之后进行介绍。
  4. 定义 ii 从 00 到 n−1n - 1，对 SS 依次进行转换，S=f(S⊕(Pi∣∣0c))S = f(S\oplus (P_i||0^c))，上述过程称为吸收 (absorbing) 过程。
  5. 定义 ZZ 为空串。
  6. Z=Z∣∣Truncr(S)Z = Z || Trunc_r(S)，其中 Truncr(S)Trunc_r(S) 指 SS 前 rr 个字符组成的串。
  7. 如果此时 d≤len(Z)d\leq len(Z)，返回 Truncd(Z)Trunc_d(Z)。
  8. 令 S=f(S)S=f(S)，返回步骤 6。

KECCAK\mathrm {K\footnotesize ECCAK} 海绵函数

定义一个海绵结构需要指明海绵结构中的三个组成成分

  1. 一个对数据进行等长映射的函数 ff。
  2. 一个参数称为比率 rr。
  3. 一个填充 ( padding ) 函数，记作 pad(x,m)\mathrm{pad}(x, m)。

SHA-3 中使用的 KECCAK\mathrm {K\footnotesize ECCAK} 海绵函数的三个组件形式如下：

  1. 映射函数 KECCAK-p[b,nr](S)\mathrm {K\footnotesize ECCAK} \text{-} \normalsize{ \mathit{p}[b, n_r]}(S)，将长度为 bb 的串 SS，经过 nrn_r 轮转换输出为长度为 bb 的结果，也被称为 KECCAK-p\mathrm {K\footnotesize ECCAK} \text{-} \normalsize{ \mathit{p}} 置换函数。该函数之后会详细说明。
  2. 比率 rr 根据输出长度不同进行调整。
  3. 填充函数为 pad10∗1(x,m)\mathrm{pad10^*1}(x, m)，除了返回将长度为 mm 的串填充为 xx 的整数倍长度的串外，还保证返回的串满足表达式 10∗110^*1 形式。

KECCAK-p\mathrm {K\footnotesize ECCAK} \text{-} \normalsize{ \mathit{p}} 置换

KECCAK-p\mathrm {K\footnotesize ECCAK} \text{-} \normalsize{ \mathit{p}} 置换将输入串进行多轮重新排列得到长度相同的输出串。设输入串 SS 长度为 bb，置换进行 nrn_r 轮重新排列，则进行的 KECCAK-p\mathrm {K\footnotesize ECCAK} \text{-} \normalsize{ \mathit{p}} 置换函数记为

KECCAK-p[b,nr](S)\mathrm {K\footnotesize ECCAK} \text{-} \normalsize{ \mathit{p}[b, n_r]}(S)

其中，b∈{25,50,100,200,400,800,1600}b\in \{25, 50, 100, 200, 400, 800, 1600\}

置换函数也可以认为是在进行状态转移，前面提到，这个函数的输入 SS 又称为状态，KECCAK-p\mathrm {K\footnotesize ECCAK} \text{-} \normalsize{ \mathit{p}} 置换，就是对 SS 进行状态转移。下面简要介绍一下状态的概念。

状态 ( state )

一个一直被更新的位数组称为一个状态。一个状态可以表示成一个位串或一个状态数组。位串就是指状态的二进制串，记为 SS，长度记为 bb；状态数组将状态表示为一个 5×5×w5\times 5\times w 的三维数组，其中 w=b/25w = b/25，记为 AA。SS 和 AA 都表示状态，可以互相转换。这里不详细描述有兴趣可以参看文末链接。

状态数组中的每一位可以用 A[x,y,z]A[x, y, z] 表示，状态数组的坐标系统如下所示：

其中，xx，yy 方向都以中心点为原点。下面是状态数组中不同子数组的命名。

阶段映射 ( step mappings )

SHA-3 标准中共有 5 个映射函数，可以对状态数组 AA 进行不同的排列，下面简要进行介绍。

  1. θ(A)\theta(\mathbf{A})，对 columncolumn 进行重排列。
  2. ρ(A)\rho(\mathbf{A})，对 lanelane 进行重排列。
  3. π(A)\pi(\mathbf{A})，对 sliceslice 进行重排列。
  4. χ(A)\chi(\mathbf{A})，对 rowrow 进行重排列。
  5. ι(A,ir)\iota(\mathbf{A}, i_r)，对 A[0,0,z]A[0,0,z] 部分进行重排列。

对于 nrn_r 轮转换，每一轮使用函数 Rnd\mathrm{Rnd} 进行转换：

Rnd(A,ir)=ι(χ(π(ρ(θ(A)))),ir)\mathrm{Rnd}(\mathbf{A},i_r) = \iota(\chi(\pi(\rho(\theta(\mathbf{A})))),i_r)

其中，每轮转换的 ir∈[12+2ℓ−nr,12+2ℓ−1]i_r\in[12+2\ell-n_r,12+2\ell-1]

置换过程

置换过程总结如下：

  1. 将 SS 转换为 A\mathbf{A}
  2. 对于 iri_r，从 12+2ℓ−nr12+2\ell-n_r 到 12+2ℓ−112+2\ell-1 取值，得到 A=Rnd(A,ir)\mathbf{A} = \mathrm{Rnd}(\mathbf{A}, i_r)
  3. 将 A\mathbf{A} 转换为 S′S'，并返回 S′S'

定义 SHA-3

SHA-3 中的哈希函数基于 Keccak 海绵结构实现，并将一些参数设置为常量：

  1. 设置 KECCAK-p\mathrm {K\footnotesize ECCAK} \text{-} \normalsize{ \mathit{p}} 置换输入长度为 1600 bit，也是状态的长度。
  2. 设置 KECCAK-p\mathrm {K\footnotesize ECCAK} \text{-} \normalsize{ \mathit{p}} 置换进行 24 轮。

参数 r=1600−cr = 1600 - c，且其值取决于需要输出的哈希结果的长度。因此，SHA-3 中使用的海绵函数定义为：

KECCAK[c](N,d)=SPONGE[KECCAK-p[1600,24],pad10∗1,1600−c](N,d)\mathrm {K\footnotesize ECCAK} \normalsize{[c]}(N, d) = \mathrm{\footnotesize SPONGE}[\mathrm {K\footnotesize ECCAK} \text{-} \normalsize{ \mathit{p}[1600, 24]}, \mathrm{pad10^*1},1600-c](N, d)

参数 cc 取决于输出长度。

基于上述定义，SHA-3 哈希函数定义如下：

SHA3-224(M)=KECCAK[448](M∣∣01,224)\mathrm{SHA3\text{-}224}(M) = \mathrm {K\footnotesize ECCAK} \normalsize{[448]}(M||01,224)

SHA3-256(M)=KECCAK[512](M∣∣01,256)\mathrm{SHA3\text{-}256}(M) = \mathrm {K\footnotesize ECCAK} \normalsize{[512]}(M||01,256)

SHA3-384(M)=KECCAK[768](M∣∣01,384)\mathrm{SHA3\text{-}384}(M) = \mathrm {K\footnotesize ECCAK} \normalsize{[768]}(M||01,384)

SHA3-512(M)=KECCAK[1024](M∣∣01,512)\mathrm{SHA3\text{-}512}(M) = \mathrm {K\footnotesize ECCAK} \normalsize{[1024]}(M||01,512)

其中，cc 被设为输出长度的 2 倍，输入串还需要添加后缀 0101 作为海绵函数的输入。SHA-3 系列函数最终分别得到给定长度的哈希结果。

参考资料

SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions

FEATURED TAGS
Hash
FRIENDS