Blockchain and cryptography （区块链与密码学）学习笔记2：哈希函数

Lenis · November 25, 2022, 10:58am

Hacker Dōjo Workshop：
研究种类：密码学，哈希函数
资助金额：100 usdt
Bounty链接：Hacker Dōjo|课题研究：哈希函数 | Bounties | DoraHacks
创作者：Lynndell
本项目由Hacker Dōjo资助，文章转载请联系
Telegram: @HackerDojo0
WeChat: @HackerDojo0
E-mail: hackerdojo0@gmail.com

2哈希函数

哈希函数： 将任意长度的消息，映射为一个256bit长的随机数，称作消息摘要。

关键性质：

单项性： 已知哈希值Y，无法在多项式时间内计算出原象X；

抗碰撞性： 已知(X, Y)，无法在多项式时间找到X’，使得Y=Hash(X’)；

压缩性： 通常是将大于或等于512bit的数据压缩为256bit；

随机性： 输出的Y是256bit的0/1字符串是随机的；

可重复性： 如果输入x1=x2，则输出的哈希值Y1=Y2。

2.1 SHA2

2.1.1. 常量与基本运算

基础工具包括：8+64个初始常量、信息预处理（数据填充）、逻辑运算

2.1.1.1 常量

8 个初值常量如下：（256bit = 884）

h0 := 0x6a09e667

h1 := 0xbb67ae85

h2 := 0x3c6ef372

h3 := 0xa54ff53a

h4 := 0x510e527f

h5 := 0x9b05688c

h6 := 0x1f83d9ab

h7 := 0x5be0cd19

来源： 对自然数中前8个质数（2,3,5,7,11,13,17,19）的平方根的小数部分取前32bit。
例如：$ \sqrt{2} $小数部分约为0.414213562373095048，而

0.414213562373095048≈6∗16⁻¹+a∗16⁻²+0∗16⁻³+…
于是，质数2的平方根的小数部分取前32bit就对应出了0x6a09e667。每个参数都有来源根据，没有后门。

64 个常量如下：

428a2f98 71374491 b5c0fbcf e9b5dba5

3956c25b 59f111f1 923f82a4 ab1c5ed5

d807aa98 12835b01 243185be 550c7dc3

72be5d74 80deb1fe 9bdc06a7 c19bf174

e49b69c1 efbe4786 0fc19dc6 240ca1cc

2de92c6f 4a7484aa 5cb0a9dc 76f988da

983e5152 a831c66d b00327c8 bf597fc7

c6e00bf3 d5a79147 06ca6351 14292967

27b70a85 2e1b2138 4d2c6dfc 53380d13

650a7354 766a0abb 81c2c92e 92722c85

a2bfe8a1 a81a664b c24b8b70 c76c51a3

d192e819 d6990624 f40e3585 106aa070

19a4c116 1e376c08 2748774c 34b0bcb5

391c0cb3 4ed8aa4a 5b9cca4f 682e6ff3

748f82ee 78a5636f 84c87814 8cc70208

90befffa a4506ceb bef9a3f7 c67178f2

来源： 与8个哈希初值类似，这些常量是对自然数中前64个质数(2,3,5,7,11,13,17,19,23,29,31,37, 41,43,47,53,59,61,67,71,73,79,83,89,97…)的立方根的小数部分取前32bit而来。

2.1.1.2 基本运算

6个逻辑运算：前4个用在64轮循环中，后2个用在16个字扩展为64个字的扩展中

Ch ( x, y, z ) = ( x ∧ y ) ⊕ ( ¬x ∧ z )

Ma ( x, y, z ) = ( x ∧ y ) ⊕ ( x ∧ z ) ⊕ ( y ∧ z )

Σ 0 ( x ) = S² ( x ) ⊕ S¹³ ( x ) ⊕ S²² ( x )

Σ 1 ( x ) = S⁶( x ) ⊕ S¹¹ ( x ) ⊕ S²⁵ ( x )

σ 0 ( x ) = S⁷ ( x ) ⊕ S¹⁸ ( x ) ⊕ R³ ( x )

σ 1 ( x ) = S¹⁷( x ) ⊕ S¹⁹ ( x ) ⊕ R¹⁰ ( x )

∧ 按位“与”

¬ 按位“补”

⊕ 按位“异或”

Sⁿ 循环右移n个bit

Rⁿ右移n个bit

2.1.2 数据预处理(pre-processing)

数据填充使整个消息长度和结构满足规定。

信息的预处理分为2步：附加填充比特和附加长度。

2.1.2.1 STEP1：填充比特

填充规则：先补第一个比特为 1 ，然后都补 0 ，直到长度满足对 512 取模后余数是 448 。

需要注意的是，信息必须进行填充，也就是说，即使长度已经满足对 512 取模后余数是 448 ，补位也必须要进行，这时要填充 512 个比特。

因此，填充是至少补一位，最多补 512 位。

例：以信息“abc”为例显示补位的过程。

ASCII码分别是97,98,99

二进制编码为：01100001，01100010，01100011

补位第一步，首先补一个”1” ： 0110000101100010 01100011 1

补位第二步,补423个“0”：01100001 01100010 01100011 10000000 00000000 … 00000000

补位完成后的数据如下（为了简介用16进制表示）：

61626380 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000

在第一步的预处理后，第二步会再附加上一个64bit的数据，用来表示原始报文的长度信息。而448+64=512，正好拼成了一个完整的结构。

综上：

01100001 01100010 01100011 10000000 00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

2.1.2.2 STEP2：附加长度值

用一个 64 位的数据来表示原始消息的长度。

因此，通过SHA256计算的消息长度必须要小于2^64，当然绝大多数情况这足够大了。

长度信息的编码方式为 64-bit big-endian integer

关于Big endian的含义，文末给出了补充

回到刚刚的例子，消息“abc”，3个字符，占用24个bit

因此，在进行了补长度的操作以后，整个消息就变成下面这样了（十六进制18 = 十进制24）

61626380 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000018

最终的二进制编码为：

01100001 01100010 01100011 10000000 00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00011000

2.1.3. 计算摘要

现在来介绍SHA256算法的主体部分，即消息摘要是如何计算的。

首先：将消息分解成512-bit大小的块，不足512则根据上一节方法填充。

假设消息M可以被分解为n个块，于是整个算法需要做的就是完成n次迭代，n次迭代的结果就是最终的哈希值，即256bit的数字摘要。

一个256-bit的摘要的初始值H0，经过第一个数据块进行运算，得到H1，即完成了第一次迭代H1经过第二个数据块得到H2，……，依次处理，最后得到Hn，Hn即为最终的256-bit消息摘要将每次迭代进行的映射用Map(H_{i-1})= H_i表示，于是迭代可以更形象的展示为：

图中256-bit的Hi被描述8个小块，这是因为SHA256 算法中的最小运算单元称为 “ 字 ” （ Word ），一个字是 32 位。

第一次迭代中，映射的初值设置为前面介绍的8个哈希初值，如下图所示：

下面开始介绍每一次迭代的内容，即映射Map(H_{i-1}) = H_i的具体算法

Map 映射

STEP1 ：扩展函数：输入： 512bits ，输出 2048bits ； 16 个字扩展为 64 个字（ word=32bits ）

对于每个块 M (512bits=16*32)，分解为16个32-bit的big-endian的字w[0], …, w[15];

前 16 个字直接由消息的第1个块分解得到：512bit= w[0], …, w[15]

其余的 48 个字由如下迭代公式得到：W_t=σ₁(W_t−2)+W_t−7+σ₀(W_t−15)+W_t−16

W_t−16=σ₁(W₁₄)+W₁₁+σ₀(W₁)+W₀

W₁₇=σ₁(W₁₅)+W12+σ0(W2)+W1

,…,

W₆₄

STEP2 ：压缩函数：进行 64 次循环；输入 64 个字和 64 个常量 k_i

映射Map(H_{i-1}) = H_i包含64次循环

即进行64次循环即可完成一次迭代

每次加密循环可以由下图描述：

256 = 8 * 32

图4：64次循环
图中，ABCDEFGH这8个字（word）在按照一定的规则进行更新，其中深蓝色方块 是事先定义好的非线性逻辑函数；

红色田字方块代表的是：相加后mod2³²，其中一个红色方框是字与常量的模加Wt +K_t (mod2³²)；

ABCDEFGH一开始的初始值分别为H_{i-1}(0),H_{i-1}(1),…,H_{i-1}(7)。

K_t是64个常量，每次循环使用1个常量。

W_t是本区块产生第t个word。原消息被切成固定长度512-bit的区块，对每一个区块，产生64个word，通过重复运行循环n次对ABCDEFGH这八个字循环加密。

Add the compressed chunk to the current hash value:

h0 := h0 + a

h1 := h1 + b

h2 := h2 + c

h3 := h3 + d

h4 := h4 + e

h5 := h5 + f

h6 := h6 + g

h7 := h7 + h

最后一次循环所产生的八个字合起来即是第i个块对应到的哈希值H_i。

hash:= h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7

2.2 SHA3

2.2.1.Keccak

采用海绵结构（sponge construction），在预处理（padding并分成大小相同的块）后，海绵结构主要分成两部分：

吸入阶段（absorbing phase）：将块x_i传入算法并处理。
挤出阶段（squeezing phase）：产生一个固定长度的输出。

Keccak算法的整体结构如图：

在这两个阶段要是使用同一个压缩函数Keccak-f，下图展示了算法“吸入”一个块x_i并处理，最后挤出输出的过程：

2.2.1.1 吸入和挤出阶段

从图中我们可以归纳出大致的流程：

数据填充： 对输入串x做padding，使其长度能被r=1088整除，将padding后分割成长度为r=1088bits的块，即x=x0||x1||x2||…||xt-1。
初始化 ：一个长度为b=r+c bit的全零向量。b=1088+512=1600bits
输入：块x_i，将x_i和向量的前r个异或运算，然后输入到Keccak-f函数中处理。重复上一步，直至处理完x中的每个块。
输出：长为r的块作为y_0 ，并将向量输入到Keccak-f函数中处理，输出y_1，以此类推。得到的Hash序列即为y=y_0||y_1||y_2||…||y_u。在Keccak-224/256/384/512中，只需要在y_0中取出对应长度的前缀即可。

针对图中的参数，做出如下定义：

r：比特率（bit rate），其值为每个输入块的长度。
c：容量（capacity），其长度为输出长度的两倍。
b：向量的长度，b=r+c。b的值依赖于指数L，即b=25*(2^L),L=6，b=1600。
b = 1600; r = 1088 ; c = 512;

在Keccak-224/256/384/512中，b、r、c及输出长度的取值见下表。

2.1.1.2 Padding

填充规则：添加1,000,…,000,1，|M|+2+d(modr)=0

按照官网的描述，padding伪代码如下：

P = M || 1 || 0x00 || … || 0x00

P = P xor (0x00 || … || 0x00 || 0x80)

Mbytes为输入串，“||”符号表示比特串串联。**在SHA3的标准中，d为0x06。**由于Keccak中按照字节序为小端，以上描述相当于在输入比特串后接0110*1以将长度补齐到能被r整除。关于Keccak中字节序的问题可以参考官网中的Bits and bytes in Keccak。

2.2.2.压缩函数

对称加密中的轮函数，对应此处的压缩函数。

压缩函数以b比特作为输入，b比特作为输出。内部结构如下：

Keccak-f 包含n_r轮。n_r的取值与我们之前计算b时用到的指数L有关，具体地，n_r=12+2*L。Keccak-224/256/384/512中**，取L=6，因此n_r=24 rounds**。在每一轮中，要以此执行五步，即θ(theta) 、ρ(rho)、π(pi)、χ(chi)、ι(iota) 。在处理过程中，把b=1600个比特排列成一个5564的矩阵，其中w=2^L=64比特，如图：(x,y,z)=(5,5,64)

slice(x,y)平面平移；plane(x,z)平面平移；sheet(y,z)平面平移；

lane z轴平移；row x轴平移；column y轴平移

2.2.2.1 Theta (θ)

C[x] = A[x,0] xor A[x,1] xor A[x,2] xor A[x,3] xor A[x,4], for x in 0 …4

D[x] = C[x-1] xor rot(C[x+1],1), for x in 0…4

A[x,y] = A[x,y] xor D[x], for (x,y) in (0…4,0…4)

该步骤的输入输出均存在A矩阵中。

rot(num, offset) 表示将w比特的num向z轴正方向循环移动offset位。

等价表达为

2.2.2.2 Rho (ρ) and Pi (π)

二者结合，等价表达为

该步的输入为A数组，输出为B数组。rot含义同上一步，其中作为offset的r数组定义如下：

	x=3	x=4	x=0	x=1	x=2
y=2	25	39	3	10	43
y=1	55	20	36	44	6
y=0	28	27	0	1	62
y=4	56	18	14	2	61
y=3	21	8	41	45	15

代码中定义如下：

```
 const int R_CONS[MAT][MAT] = {
```
```
     {0, 36, 3, 41, 18}, 
```
```
     {1, 44, 10, 45, 2}, 
```
```
     {62, 6, 43, 15, 61},
```
```
     {28, 55, 25, 21, 56},
```
```
     {27, 20, 39, 8, 14}};
```

2.2.2.3 Chi (χ) 唯一的非线性变换

该步骤中，输入为B矩阵，输出为A矩阵。等价于5*5的S盒子非线性变换。
等价表达为

2.2.2.4 iota (ι)

A[0,0] = A[0,0] xor RC
异或运算，就是二进制加法运算。
等价表达为

该步骤输入和输出均为A矩阵。RC值与轮数有关，RC在24轮中的定义如下：

2.2.3输出

通过海绵结构中的挤出阶段，可以获得任意长度的输出。在Keccak-224/256/384/512中，我们只需要获得y0中的前224/256/384/512个bit作为输出即可。

输出长度为1088 bits的y0，取前256bit就是哈希值。

2.3 MiMC

伪代码

Ci是322个随机数常量

function (xL : Fp, xR : Fp) {

for i from 0 up to 321 {

  xL, xR := xR + (xL + Ci)^3 modp, xL

  }

  return xL 128

}

类似DES：每次只处理一半的数据；

Rust 代码

二层：大量的账户；

唯一原因：二层的任意状态改变，只能是正确改变。

想要错误改变的难度等价于攻破zk。

侧链技术：

zk技术：双线性映射正确，电路正确，提供了正确的数据。

2.3 Rescue

An example for a sponge hash function is proposed in Fig. 1, where the construction is used to compute the hash output h1 || h2 of the 4-block message m1 || m2 || m3 || m4, where mi and hi are r-bit values. The initial state I contains all zeros, i.e., I = 0^r || 0^c for an r-bit rate and a c-bit capacity

I=r+c

|mi|=|hi|=r

|Msg|+2+k=nr

Extention=Msg10000001

2.4 Poseidon

2.5 随机数生成算法

分布均有性：0 和1 出现概率相等。

独立性：不能根据一个子序列，计算出其他子序列。

图a是真随机数生成器

图b是伪随机数生成器

图c是随机函数

对种子通常要求来自真随机数，然后进行伪随机数生成器，生成随机流。

可以使用哈希函数和对称加密五种工作模式构造伪随机数生成器，生成随机流，实现流密码，对加密加密和解密。

2.6 哈希函数的应用

2.6.1 消息认证码

图a使用对称密加密算法Enc加密消息M和哈希值H。发送方和接收方共享对称密钥K。所以仅接收方能够解密获得消息和哈希值。然后校验H==hash(M)。
图b使用对称加密算法Enc对哈希值H进行加密。发送明文消息和密文C。接收方均可获得明文消息，并使用解密算法Dec对密文解密获得哈希值H’，校验H==H’。
图c双方共享秘密值S，计算H:=hash(M,S)，发送M和H。接收方获得M后，也能计算H’:=hash(M,S)，然后校验H==H’。
图d双方共享S和K。对图c的基础上的数据进行加密。接收方需要解密获得M，然后进行校验H==H’。

2.6.2 应用到数字签名

图a发送方输入私钥sk和哈希值H，调用加密算法Enc，输出密文C。发送M和密文C。接收方输入公钥PK和密文C，输出明文哈希值H。接收方计算M的哈希值H，校验H==H’。注释：私钥对数据加密，本质上就是数字签名。
图b是输入图a的数据M和密文C，输出对称加密结果。接收方进行对称解密后，再执行图a的计算哈希值和校验过程。

2.6.3 构造方法

哈希函数： 将任意长度的消息，映射为一个固定长的随机数，称作消息摘要。

关键性质：

单项性： 已知哈希值Y，无法在多项式时间内计算出原象X；

抗碰撞性： 已知(X, Y)，无法在多项式时间找到X’，使得Y=Hash(X’)；

压缩性： 通常是将大于或等于512bit的数据压缩为256bit；

随机性： 输出的Y是256bit的0/1字符串是随机的；

可重复性： 如果输入x1=x2，则输出的哈希值Y1=Y2。

可以基于对称加密DES、AES、非对称密码算法等构造哈希函数，满足定义和性质即可。

关于Dorahacks
DoraHacks 是一个全球范围内的极客运动、全球黑客马拉松组织者，也是全球最活跃的多链 Web3 开发者平台之一。DoraHacks.io平台使得世界各地的Hacker和开源开发者可以参与黑客马拉松、Bounty、Grant、Grant DAO，以及公共物品质押等加密原生协议和基础设施进行协作并获得资助。到目前为止，DoraHacks 社区的 4000 多个项目已经获得了来自全球行业支持者超过 3000 万美元的资助。大量开源社区、DAO 和超过50个主要区块链生态系统正在积极使用 Dora 的基础设施（DoraHacks.io）进行开源融资和社区治理。

关于Dorahacks DAO Bounty
Dorahacks DAO Bounty，为各类DAO和组织赋能！
Bounty计划为DAO和组织提供了一个强大的平台，通过社区激励的形式，发布问题，协调任务，鼓励用户积极参与。
作为Bounty发布者，您可以根据我们的指南，发布社区相关的悬赏任务，解决问题的同时，提升社区活跃度：How to publish a bounty and easily fund bounty hunters
作为赏金猎人，您可以在DAO Bounty计划中发挥自己的专长和能力，认领悬赏，解决问题，获得酬金：DAO Bounties | DoraHacks

关于Hacker Dōjō
Hacker Dōjō是由Hacker共建的加密、Web3前沿技术开源知识社区。Dōjō会以直播/音频/文字等形式定期组织分享session，内容包括Web3领域前沿技术论文解读、技术研讨、工作坊、技术领袖研讨会等。欢迎在Hacker Dōjo社区讨论、学习和交流：Dora Dōjo - Dora Community Forum

目前Hacker Dōjō已分享的主题有：

密码学：基础专题（对称加密算法、哈希函数、群和公钥加密、数字签名和KZG承诺、零知识证明、非对称密码算法、分布式密码学）
密码学：算法代码专题（Halo、Halo2、Plonk、Groth16、分布式密钥生成）
密码学：抗量子计算破解算法专题
Layer1架构：Move系列、模块化公链、共识协议Bullshark、内存池协议Narwhal和共识协议Tusk、Aptos共识与交易并行执行
Layer2架构：zkSync研究、Layer2的支付通道扩容方法、Polygon Hermez、Optimism、StarkWare技术与生态梳理
IRS系列：Interest Rate Swap and DeFi Platforms、Interest Rate Swap and Perpetual Swap、The Future Dencentralized Interest Rate Swap
量子计算系列：量子计算基础、Qiskit专题（Qiskit入门、Deutsch-Jozsa算法、Bernstein-Vazirani算法、Simon算法、量子卷积神经网络、量子傅里叶变换、量子相位）、Pennylane专题（利用变分量子电路拟合傅里叶级数）、实验法观测宏观量子叠加态
AIGC系列：ChatGPT比较语料评测、GPT-4论文解读

加入Dōjō的Hacker可以提出自己的学习期望，主动提案自己擅长的技术话题，由Dōjō组织分享。同时，Hacker Dōjō推出Web3前沿课题研究计划，定期选题，由Hacker进行研究和讲解，并以bounty形式奖励研究贡献者。欢迎各位Hacker认领Bounty：DAO Bounties | DoraHacks

联系我们：

Telegram: @DoraDojo0

WeChat: @HackerDojo0

E-mail: hackerdojo0@gmail.com

Lenis · November 26, 2022, 1:49pm

笔记更新1

对称加密/哈希函数的核心思想：

线性变换：线性运算关系，作用：让每bit输入影响50%输出；

非线性变换：S盒子，非线性变换，抵抗解方程组攻击；

轮密钥加：添加常量或密钥，提高信息商。

哈希函数： 将任意长度的消息，映射为一个固定长（256bit）的随机数。这段随机数称为消息摘要。

关键性质：

【1】单项性： 已知哈希值 Y ，无法在多项式时间内计算出原象 X ；

【2】弱抗碰撞性：已知(X, Y)，无法在多项式时间找到X’，使得Y=Hash(X’)；

【3】强抗碰撞性 ： 攻击者无法寻找 ，满足 ；

【4】压缩性： 通常是将大于或等于 512bit 的数据压缩为 256bit ；

【5】随机性： 输出的 Y 是 256bit 的 0/1 字符串是随机的；

【6】可重复性： 如果输入 x1=x2 ，则输出的哈希值 Y1=Y2 。

Lenis · November 26, 2022, 1:59pm

笔记更新2

2.1.3. 计算摘要

…
Map 映射函数

也就是对称加密中的轮函数function

STEP1 ： 扩展函数：输入：512bits，输出2048bits； 16 个字扩展为 64 个字，每个字 32bit

对于每个块 M (512bits=16*32)，分解为16个32-bit的big-endian的字w[0], …, w[15];

起始状态：前16个字直接由消息的第1个块分解得到：512bit= w[0], …, w[15]
其余的48个字由如下迭代公式 得到：W_t= σ₁ ( W_t − 2 )+W_t-7+ σ₀ ( W_t-15) **+W_t-16

W₁₆=σ₁(W₁₄)+W₁₁+σ₀(W₁)+W₀

W₁₇=σ₁(W₁₅)+W₁₂+σ₀(W₂)+W₁

,…,

W64

σ0(x) = S⁷(x) ⊕ S¹⁸(x) ⊕ R³(x)

σ1(x) = S¹⁷(x) ⊕ S¹⁹(x) ⊕ R¹⁰(x)

∧ 按位“与”

¬ 按位“补”

⊕ 按位 “ 异或 ”

Sn 循环右移n个bit

Rn 右移n个bit

STEP2 ：压缩函数：进行 64 次循环；输入 64 个字和 64 个常量 k_i

映射函数包含64次循环

即进行64次循环即可完成一次迭代

每次加密循环可以由下图描述：

256 = 8 * 32

图4：64次循环

Ch(x, y, z) = (x ∧ y) ⊕ (¬x ∧ z)

Ma(x, y, z) = (x ∧ y) ⊕ (x ∧ z) ⊕ (y ∧ z)

Σ0(x) = S²(x) ⊕ S¹³(x) ⊕ S²²(x)

Σ1(x) = S⁶(x) ⊕ S¹¹(x) ⊕ S²⁵(x)

图中，ABCDEFGH这8个字（word）在按照一定的规则进行更新，其中

深蓝色方块 是事先定义好的非线性逻辑函数；

红色田字方块 代是：相加后mod232，其中一个红色方框是字与常量的模加

K_t+K_t (mod2³²)

其中，是Kt 是64个常量。