CRC 算法原理

CRC 算法的基本原理是将数据看作一个大数，与一个预定义的除数使用特殊的除法相除，所得的余数即为数据的 CRC 校验值。

生成多项式

算法的数学原理与多项式相关，用到的除法也基于多项式除法，预定义的除数也叫“生成多项式”，这里的多项式都是只有一个未知数并且各项系数只能是 0 或 1 的多项式（更多的信息可以参考维基百科：有限域算术，这里不多讲）。

我们以 CRC-4/ITU 为例，其生成多项式是 $x^4 + x + 1$，也即:

$$1x^4 + 0x^3 + 0x^2 + 1x^1 + 1x^0$$

如果我们令 $x = 2$，则多项式中每一项的系数可以看作一个二进制数的对应位，即 $(10011)_2$，是一个 5 位的二进制数，那么用它来做除数，最后可以得到 4 位的余数，也就是 CRC-4/ITU 中的 4。由此可见，生成多项式的首位必然是 1，在一般表示生成多项式的时候我们都省略最高位，再写成十六进制就是 0x03。

模二多项式除法

我们先看多项式乘法：

$$ (x^4 + x^1 + x^0) \times (x^4 + x^3 + x^0) = x^8 + x^7 + x^4 + x^5 + x^4 + x^1 + x^4 + x^3 + x^0 $$

这里我们没有合并同类项，如果按照常规的方式合并同类项，即

$$ x^8 + x^7 + x^5 + 3x^4 + x^3 + x^1 + x^0 $$

那就是普通的多项式乘法；对于 CRC 算法，加减法采用模二运算，也就是最后的系数除以 2 取余数，不产生进位，所以最后的结果是：

$$ x^8 + x^7 + x^5 + x^4 + x^3 + x^1 + x^0 $$

- 阅读剩余部分 -

出于了解 SHA-256 算法及学习 Rust 的目的，用纯 Rust 实现了一个 SHA-256 库。

SHA-256 算法简介

首先简单介绍一下 SHA-256 算法，SHA-256 是 SHA-2 系列算法中的一种，关于 SHA-2 的相关介绍可以查看其维基百科，其中也详细介绍了 SHA-256 的算法。

简单的说， SHA-256 算法分为以下几步：

1. 对消息进行填充预处理，先附加 bit 1，然后填充可变数量（0-511）的 bit 0，最后附加 u64（big-endian, 64 bits）类型的原始消息长度的 bit 数，使填充后的消息长度为 512 bits 即 64 bytes）的整数倍
2. 对预处理后的消息进行分片，每 512 bits 为一个分片
3. 对每个分片进行迭代处理，每次迭代以该分片及 8 个 u32 为输入，并输出 8 个 u32 作为下一个迭代的输入
4. 最后一个分片处理完成输出的 8 个 u32 既是最后的结果

要用到的两组常量

其中第 3 步对各个分片的迭代处理又要用到两组常量：

一是对第一个分片进行处理时作为输入的 8 个初始的 u32：

const H: [u32; 8] = [
    0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19,
];

它们是自然数中前 8 个质数 2、3、5、7、11、13、17、19 平方根的小数部分取前 32 bits。

- 阅读剩余部分 -