【编程】SIMD SHA指令集加速sha256计算

intel的SHA指令集提供了六个指令用于加速SHA计算

这里只实现sha256

sha256计算步骤：填充 -> 消息调度 -> 压缩

将消息长度填充到512的整倍数

一次迭代处理512比特，将512比特调度到64个32比特字，再将字压缩到状态向量(A, B, C, D, E, F, G, H)中

初始状态向量为常数，8个分量每个分量4字节大

SHA指令一次最多处理128位，所以需要按照压缩函数循环移位机制，交替更新(A, B, E, F)和(C, D, G, H)

//ABEF
_mm_set_epi32(0x6a09e667, 0xbb67ae85, 0x510e527f, 0x9b05688c);

//CDGH
_mm_set_epi32(0x3c6ef372, 0xa54ff53a, 0x1f83d9ab, 0x5be0cd19);

填充

在消息末尾添加一个1比特

添加若干个0比特，直到消息长度满足 长度 ≡ 448 mod 512

最后添加一个64位的无符号整数（大端序表示），表示原始消息的长度（以比特为单位）

添加原始消息长度的目的：防止长度扩展攻击

最后一块长度小于448比特，直接填充满就行

最后一块长度大于等于448比特，需要填充到另起一块以确保有足够的空间存放原始消息长度

消息调度

消息调度：将输入的512比特块拓展为64个32比特的字

前16个字无需计算，直接分解512比特块便是

其余的字用消息调度公式计算 $W_t = \sigma_1(W_{t-2}) + W_{t-7} + \sigma_0(W_{t-15}) + W_{t-16}$

_mm_sha256msg1_epu32实现了 $\sigma_0(W_{t-15}) + W_{t-16}$

_mm_sha256msg2_epu32实现了 $\sigma_1(W_{t-2})$

_mm_sha256msg1_epu32计算结果加上 $W_{t-7}$ 传入_mm_sha256msg2_epu32中便是最终的调度字

处理调度字时，需要对寄存器进行重拼接

_mm_alignr_epi8(a, b, imm)：拼接a和b，a在高b在低。拼接后的256位数据中，从第imm个字节开始，提取128位作为返回值

以下为示例代码

加载数据，作为前16个起始调度字

//加载数据，并进行重排运算将小端序转为大端序
const __m128i MASK = _mm_set_epi64x(0x0c0d0e0f08090a0bULL, 0x0405060700010203ULL);
// W[3:0]
__m128i MSG0 = _mm_shuffle_epi8(_mm_loadu_si128((const __m128i*)(data + 0)), MASK);
// W[7:4]
__m128i MSG1 = _mm_shuffle_epi8(_mm_loadu_si128((const __m128i*)(data + 16)), MASK);
// W[11:8]
__m128i MSG2 = _mm_shuffle_epi8(_mm_loadu_si128((const __m128i*)(data + 32)), MASK);
// W[15:12]
__m128i MSG3 = _mm_shuffle_epi8(_mm_loadu_si128((const __m128i*)(data + 48)), MASK);

调用_mm_alignr_epi8(MSG3, MSG2, 4)获取W[12:9]，并计算W[19:16]

// W[19:16]
MSG0 = _mm_sha256msg2_epu32(_mm_add_epi32(_mm_sha256msg1_epu32(MSG0, MSG1), _mm_alignr_epi8(MSG3, MSG2, 4)), MSG3);

压缩

使用字和轮常量进行计算，共计算64轮

_mm_sha256rnds2_epu32(xmm1, xmm2/m128, <XMM0>)

(C, D, G, H)由xmm1提供，(A, B, E, F)由xmm2提供

XMM0为消息字与轮常量之和

执行两轮压缩，返回更新后的(A, B, E, F)

按照压缩函数循环移位机制，调用两次交替更新(A, B, E, F)和(C, D, G, H)作为四轮

_mm_sha256rnds2_epu32只会取XMM0的低64位，高64位则被直接忽略。因此第二次调用时需要用_mm_shuffle_epi32把高64位重排到低64位

//预计算：消息 + 轮常量
__m128i MSG = _mm_add_epi32(MSG0, _mm_set_epi64x(0xE9B5DBA5B5C0FBCFULL, 0x71374491428A2F98ULL));

//执行前两轮压缩，更新CDGH
CDGH = _mm_sha256rnds2_epu32(CDGH, ABEF, MSG);

//高64位重排到低64位，执行后两轮压缩，更新ABEF
ABEF = _mm_sha256rnds2_epu32(ABEF, CDGH, _mm_shuffle_epi32(MSG, _MM_SHUFFLE(0, 0, 3, 2)));

完整实现

库（单头文件）：https://github.com/Brassinolide/SIMD-SHA256