SHA3浅记

作者: 0HP | 来源:发表于2019-11-30 20:03 被阅读0次

写在前面：
本文思路及部分图片来自《密码编码学与网络安全——原理与实践（第七版）》

零、基本概念

SHA3：一种HASH函数标准。
输入可变长度n bits消息数据，输出固定长度 $\mathcal l$ bits 数据

一、算法步骤

输入n bits数据 $\rightarrow$ 填充(padding) $\rightarrow$ 分组 $\rightarrow$ 吸水(absorbing)（分组丢进 $f$ 函数里后得出的结果与下一分组 $XOR$ 运算以此迭代） $\rightarrow$ 挤压(squeezing) $\rightarrow$ 输出 $l$ bits数据

注：以上过程亦称为海绵结构

海绵结构图解

二、具体过程

0.填充+分组

(0). 首先定好分组长度 $r$ （一般取 $r=576$ ）
(1). 对数据向后填充，使填充后的数据长度可整除 $r$ ;填充的位数 $(0,r]$
注意区间开闭：即若原先 $r\ |\ n$ ，也应填充 $r$ 位数据
(2). 填充后得到 $n'$ 数据，且 $r\ |\ n'$ 。分为 $k=n/r$ 个分组，每个分组有 $r$ bits 数据

其中填充的方法：

简单填充：n+"10...0"
多重位速率填充：n+"10..1"
（其实就是最后一位不同）

1.吸水

(0). 每个分组内， $r$ bits数据向后扩充 $c$ bits (填充“0”即可)，一般 $c=1024$ ,得 $b=r+c$ 位的数据
(1). 第一个分组与全零 $XOR$ 运算后 $\rightarrow f$ 函数 $\rightarrow$ 得到 $s$
(2). 第二个分组与 $s \ XOR$ 运算 $\rightarrow f$ 函数 $\rightarrow$ 迭代 $s$
$\vdots$
以此迭代
(3). 得到 $s$ (b bits)

2.挤压

若 $l\leq r$ ,取 $s$ 前 $l$ bits 作为输出数据
若 $l>r$ 时
(0). 取 $s$ 前 $r$ bits 数据 $Z_0$
(1). 将 $s$ 丢进 $f$ 函数迭代以更新 $s$
(2). 重复步骤(1)(2),产生数据 $Z_0Z_1...Z_n$
直到数据 $Z_0Z_1...Z_n$ 长度大于或等于 $l$ ,取前 $l$ bits 数据作为输出结果
吸水与挤压过程

这个图不科学: $r=576,c=1024$ , 应该画 $c$ 比 $r$ 长(不要被误解)。

三、吸水挤压过程中的 $f$ 函数

作用：输入 $s=1600$ bits数据，输出 $s'=1600$ bits数据
过程：共有五个过程；执行顺序依次是 $\theta, \rho, \pi, \chi, \iota$ 。以此循环24轮，输出。

f函数框架

0. 执行前

执行算法前，将 1600bits数据构建成一个 $5*5*64$ 的三维矩阵 $a$ , 其中 $5*5$ 称为行和列，64个位合起来称为一纵。用记 $x$ 为列， $y$ 为行， $z$ 为纵里的bit坐标，
用 $a[x,y,z]$ 标记为一个bit的坐标号，且以左下角为0向上向右坐标标号递增

看以下以 $3*3*3$ 魔方为例子：

绿色对面蓝色，红色对面橙色，黄色对面白色
黄红绿+红绿+红绿白构成一列
黄红蓝+黄红+黄红绿构成一行
黄红绿+黄绿+黄橙绿构成一纵
记红蓝白（左下角）为坐标 [0,0,0],向上行数增加，向右列数增加，从里向外纵内值增加；例如：红绿块记为 a[2,1,0],即第二列第一行第零块。同理：纯绿块记为 a[2,1,1]...以此类推。

此步骤的思路可借鉴魔方盲拧构建坐标的方法

注意：计算时所有值应该 $mod$ 5，加法也是 $XOR$ 运算

1. $\theta$ 过程(基于列的位代换)

公式: $a[x,y,z]=a[x,y,z]XOR \sum^4_{y'=0}a[(x-1),y',z] XOR \sum^4_{y=0}a[(x+1),y',(z-1)]$

以魔方为例：

绿色对面蓝色，红色对面橙色，黄色对面白色

纯黄块=纯黄块 $XOR$ (黄蓝+纯蓝+蓝白) $XOR$ (黄红绿+红绿+红绿白)

2. $\rho$ 过程(纵内循环位移)

公式：
$a[x,y,z]=a[x,y,(z-\displaystyle\frac{(t+1)(t+2)}{2})]$
$t\in [0,24)$在$GF(5)^{2*2}上有 \begin{bmatrix} 0 & 1\\ 2 & 3 \\ \end{bmatrix}^t \begin{bmatrix} 1\\ 0\\ \end{bmatrix} = \begin{bmatrix} x\\ y\\ \end{bmatrix}（实际上查表可得）$
t表如下：

t表

3. $\pi$ 过程（纵间混淆）

公式： $a[x',y']=a[x,y]$
$\begin{bmatrix} x'\\ y'\\ \end{bmatrix} = \begin{bmatrix} 0 & 1\\ 2 & 3\\ \end{bmatrix} \begin{bmatrix} x\\ y\\ \end{bmatrix} (mod\ 5)$

此步与纵内无关，仅是行和列的计算，可当成二维的运算。计算后结果：

结果

4. $\chi$ 过程（基于行的位代换）

公式：
$a[x,y,z]=a[x,y,z]XOR(NOT(a[(x+1),y,z))AND(a[(x+2),y,z])$
以魔方为例：

绿色对面蓝色，红色对面橙色，黄色对面白色
黄红蓝=黄红蓝XOR非黄红XOR黄红绿

5. $\iota$ 过程（第一纵变换）

公式：
$a[0,0]=a[0,0]XOR\ RC[i_r]$
其中RC为轮常量，查表可得; $i_r$ 为轮序数。
即每一轮计算时，用该轮次的 $RC$ 值与该轮第一纵计算。

轮常量RC表

5个步骤，循环24次（24轮）后输出 $s$

SHA3浅记

零、基本概念

一、算法步骤