SHA256加密算法的硬件实现
29 Feb 2024 4526字 16分 次 Hardware Algorithm Verilog HDL打赏作者 CC BY 4.0 (除特别声明或转载文章外)
1 前言
网上讲SHA256算法的文章很多,大多数都是从算法角度或软件角度分析的。所以我们从硬件角度分析和设计一下SHA256算法。
1.1 SHA概述
由文档可知,SHA256算法分为以下几步:
- 预处理
- 填充比特
- 填充长度值
- 哈希计算
- 消息块分解
- 计算消息摘要
- 计算哈希值
1.2 常数
由文档可知,SHA256要用到以下8个1字节(32bit)的初始哈希值~:
以及64个1字节(32bit)的常量~,它们是对自然数中前64个质数的立方根的小数部分的前32bit:
1.3 函数
由文档可知,SHA256要用到以下6个函数
其中:
逻辑运算 | 含义 |
---|---|
按位与 | |
按位补 | |
异或 | |
循环右移n位 | |
逻辑右移n位 |
因此,转换成HDL伪代码:
2 预处理
2.1 算法分析
需要对原始消息进行填充,假如原始消息长度为,填充分为三步:
- 填充1:在原始消息末尾填充1,此时消息长度为;
- 填充0:如果此时的消息长度再加64可以被512整除,则不填充;否则在当前消息末尾填充n个0,直到可以被512整除;
- 填充消息长度:把消息长度(位数)转换成64bit的数,填充到末尾,这样就得到了长度可以被512整除的预处理之后的消息。
简单说就是原始消息长度为,预处理之后的消息长度,原始消息后面填充1,再填充n个0,再填充64bit的消息长度,n的大小要使得m能够被512整除,n为非负自然数。
2.2 硬件设计
原始消息长度在输入时宽度是不固定的,但处理后的消息长度是512的倍数,这是因为在后续的哈希计算是要将预处理的消息分解为n个大小为512bit的块。
考虑到上述输入输出位宽的情况,使用输入输出位宽不等的FIFO来对原始消息进行预处理。输入的消息长度以及输入消息的位宽能够通过parameter设定,但有以下要求:
- 输入的位宽必须为1/2/4/8/16/32/64,目前不支持大于64是因为考虑到最后填充的消息长度是64bit,降低设计难度,之后可能会添加支持;
- 输入的消息长度必须为所设定的输入位宽的倍数,方便计数并填充。
输入信号就是写使能和写入的消息,以及读取预处理之后数据的使能,其中写入信号为Big-endian模式。
输出信号是预处理之后的数据,也为Big-endian模式,另外就是写入完成和读取有效信号。
根据上一小节的预处理步骤,可以设计如下状态机来实现:
以消息宽度为8,消息长度为800举例,时序图如下:
写入使能置1后启动写入流程。消息宽度是8,消息长度为800,因此使用8bit写宽度的FIFO需要写入原始消息100个cycle,既计数器从0,计数到799,每次加8。紧接着写入0x128到FIFO,既写入了1个1bit和7个0bit,然后补8bit的0,直到总长度还差64bit就能被512整除,最后把长度分为8个8bit的数据以大端模式写入FIFO,这样就完成了消息的Preprocess。
需要取出处理完的消息,只需要给读出使能上升沿,就能以512bit从FIFO中读出消息,读完之后状态机恢复IDEL状态,准备好下一次预处理。
3 哈希计算
3.1 分解与设定初始哈希值
在上一章里因为使用了512bit输出的FIFO,所以直接把预处理后的消息分解为n个512bit的块了。
SH256的初始哈希值是固定的,在文中1.2出可以找到,它们用于下一步计算。
3.2 计算消息摘要
3.2.1 算法分析
消息摘要的计算需要用到上一步产生的512bit的块,每一个512bit(拆成16个32bit的字)计算一次,产生64个32bit的字作为一组消息摘要。有几个512bit的块,就有几组消息摘要。
计算过程以一个512bit的块为例。把这个块拆分为16个32bit的字,标记为~,最终要产生64个32bit的字,标记为,它们通过以下公式计算:
#<!–
\[W_t= \begin{cases} M_t, 0\le t \le 15\\ \sigma_1(W_{t-2})+W_{t-7}+\sigma_0(W_{t-15})+W_{t-16}, 16\le t \le 63\\ \end{cases}\]#–>
#![img3][img3]
其中的和函数的含义和伪代码在1.3中介绍过了。
这样就完成了当前512bit块的消息摘要计算,其它块同理。每个块的消息摘要计算相互独立。
3.2.2 硬件设计
构造函数。通过可综合的function来构造和函数,代码片段如下:
由上一小节的公式可知,之后的字都需要它前面的某4个字来决定,所以需要这4个字计算出来才能得到,因此64个字全部计算完是需要一些cycle的。
由波形可以看出,需要26个以上的cycle才可以把64个字的消息摘要全部更新完,此时valid信号拉高,表示结束。
3.3 计算哈希值
从算法角度看,哈希值的计算分为内外两层循环。
先说内循环。内循环的循环次数是固定的64。输入为8个32bit的哈希值,1.2节中介绍的常数,还有消息摘要,输出为计算后的8个32bit的哈希值,计算用到了1.3节介绍的、、、四个函数,计算方法如下公式:
RTL设计很简单:
单次内循环消耗一个cycle,总共消耗64个cycle出最终的结果。最终的内循环模块就是集成64个上述模块,和首尾连接,上述模块的接1.2接介绍的常量,就是本块的64个消息摘要。模块图如下:
外循环的循环次数等于512bit块的数量,每次外循环都会有一组新的消息摘要。外循环的输入是8个32bit的哈希值,和消息摘要,输出是最后计算出的哈希值。第一次外循环的输入哈希值为1.2节中介绍的初始哈希值。
最后一次外循环输出的256位的数就是最终的SHA256哈希值。
[img3]: