闪存随机化

引言

在固态硬盘中，为了降低数据出错的可能性，需要将数据随机化，使0和1尽可能随机分布。本文介绍下其中的基础原理——LFSR算法。

从一个例子出发，先建立起对这个算法的总体认识，见下图：

输入是方框里的4个数字，输出是一个个0或1组成的序列（例如“10011010111”），这样的序列就是固态硬盘需要的随机数。

拆解

LFSR 全称是 Linear Feedback Shift Register，中文名称是“线性反馈移位寄存器”，下面逐个进行解释。

简单来说，寄存器就是一个存储容器，可以存储多个二进制数。

移位指每隔一个时间间隔，将寄存器中的值逐个往右移，可用下表表示：

（表格空的位置应用0代替，这里为了直观，没有补上去）

反馈指将寄存器中的值进行某种运算后，填回最左边，例如：

Clock二 中A的值是从Clock一 B⊕C 运算得到，Clock三 中A的值是从Clock二 B⊕C 运算得到。

“⊕” 表示异或运算。它的逻辑为：

• 相同为0（如 0⊕0=0, 1⊕1=0）。

• 不同为1（如 0⊕1=1, 1⊕0=1）。

LFSR只需要异或运算（XOR），满足线性要求：

1. 加法性: a⊕b=b⊕a，异或运算对交换律成立。

2. 结合性: (a⊕b)⊕c=a⊕(b⊕c)，异或运算对结合律成立。

3. 单位元: a⊕0=a，0是异或运算的单位元。

4. 自反性: a⊕a=0，同一个数异或自身结果为0。

应用

以下是一个两位LFSR的运行过程：

Clock四 与 Clock一相同，接下来Clock五会跟Clock二相同，Clock六跟Clock三相同。也就是说，每3个Clock进行循环，我们称其周期（Period）为3。另外，Clock一为初始状态（初始状态也叫种子，seed），值为 11。

该过程用python代码表示如下：

>>> state = 0b11
>>> for i in range(4):
...     print("{:02b}".format(state))
...     newbit = (state ^ (state >> 1)) & 1
...     state = (state >> 1) | (newbit << 1)
...
11
01
10
11

以下是一个三位LFSR的运行过程：

• 种子为 “101”。

• Clock八与Clock一相同，周期为7。

用python代码表示如下：

>>> state = 0b101
>>> for i in range(8):
...     print("{:03b}".format(state))
...     newbit = (state ^ (state >> 2)) & 1
...     state = (state >> 1) | (newbit << 2)
...
101
010
001
100
110
111
011
101

通过这两个例子不难发现，周期或者说所有可能状态数量是 2n−1。在固态硬盘中，可能用的是16bit数，所有可能状态数量为 216−1。其中 n 表示比特数，那这个 1 表示什么呢？

我们令初始状态为0，由于 0⊕0=0，程序运行得到的结果将始终是全0，并非固态硬盘中需要的随机序列。

因此，LFSR的初始状态，即种子的选取必须非全0。

在固态硬盘中，会将用户数据与LFSR生成的随机数进行异或，得到 1 和 0 尽可能均匀分布的数，然后写入闪存中。读过程则相反，从闪存中读取数据，然后去随机化得到用户数据。

最后

• https://commons.wikimedia.org/wiki/File:LFSR-F4.GIF

• https://medium.com/@czapfel/an-introduction-to-lfsrs-for-cryptography-bf2602640e91

• youtube 等