墨奇博客 | 生物特征密码系统之错误纠正码简介——汉明码

2022-09-16
来源：
在传统密码系统中，用户使用密钥对信息进行保护，只有当用户拥有正确的密钥时，才可以解密获得正确的原始信息。因此，密码系统的安全性建立在用户密钥无法被冒充者通过任何手段在合理时间以及合理资源下获得。同时，传统密码系统的缺点也显而易见，用户必须对密钥进行安全的管理以防泄露。

而在实际中，用户对密钥的管理通常很难做到“安全”。例如，用户通常偏爱使用对自己有意义的符号作为密钥，例如拼音缩写、纪念日日期等，或者使用简单的字母和数字组合，因为这些作为密钥更便于记忆。或者，用户通常长时间不对密钥进行更换，对所有场景使用相同的密钥，都使得用户密钥的泄露风险大大增加。无疑，目前流行的短信验证码或者优盾等多因子验证手段可以增加冒充者攻击的难度，但同时也使得用户需要额外繁琐的步骤才能获取原始信息。


生物特征密码系统介绍

我们知道，人脸、签名、指掌纹、虹膜等生物特征是每个生物个体独有且不易随时间发生变化的。如果将生物特征作为密码系统的密钥，用户便无需对“密钥”进行记忆，也不用担心普通冒充者对“密钥”进行窃取和伪造。（我们强调普通冒充者，是因为的确存在“高级”冒充者可以窃取和伪造生物特征，由此带来的损失也常有报道。今后会专门对生物特征防伪进行专题讲述，在此不做介绍。）需关注的问题是：生物特征是唯一且不变的，但用户仍希望可以修改密钥或者对不同的场景使用不同的密钥。

不用担心，我们可以将生物特征作为管理密钥的密钥。即——将传统密钥和生物特征进行绑定，用户可以更换和使用任意的密钥，但只要有正确的生物特征，就可以拿到正确的传统密钥，进而获得待保护的原始信息。这种技术也被称作生物特征密码系统（Biocryptosystem）。



被广泛运用的纠错技术


相比于传统密钥可以准确地被输入密码系统，生物特征密钥在采集时会面临着光照、角度、磨损、采集设备不同等实际情况。这会导致本次采集到的信息和库内保存的信息并不能完全做到一致。因此，纠错技术被广泛运用其中。


纠错技术最早应用在通信领域，当发送方发送一串消息时，由于通信信道的不稳定，可能在传输过程中出现噪声，导致接收方无法收到正确的消息。为了解决这个问题，发送方通常会将待发送的消息附上一定的校验及冗余信息，这样即使在传输过程中出现了噪声，也很容易从收到的冗余信息中恢复出发送方的消息。


另外，在早期的光盘，如今的 5G 通信技术，以及每天使用的二维码中，都处处包含着纠错技术。因此我们很容易直接借鉴纠错技术对生物特征进行纠错。


有了纠错技术，我们来看如何将其用于绑定密钥，构成生物特征密码系统。假设生物特征可以被编码成一个消息 m，选定一种纠错码 C = (Enc, Dec)，再给定待绑定的密钥 k，我们可以生成一份文件 v = Enc(k) + m。


这时，由于加法的混淆，冒充者既无法从文件 v 中得知密钥 k，也无法从中还原出生物特征 m。而对于用户来说，当下一次采集的生物特征被编码成另一个消息 m’ 时，我们计算 k’= Dec(v - m’)，因为 m’ 和 m 非常相似，即仅有很少的错误发生，那么 k’ = Dec(m - m’ + Enc(k)) = k，也就是说用户得到了之前绑定的密钥。进而可以拿该密钥解锁密码系统的信息。可以看到，纠错码在生物密钥系统中扮演着重要的角色。在接下来的文章中，我们将简单介绍一些纠错码的基础知识。



纠错码的基础知识


简单来说，分块纠错码是一个单射函数 ，其中 是有限字母表，将一块长度为 k 的消息映射到长度为 n 的码字。因为 C 是单射，不同的消息会被映射到不同的码字，显然有 。当然，为了纠错，我们还需要一个解码函数   ，满足 。即，或者将收到的消息正确解码，或者无法正确解码，输出 *。


图片


请看上图，每一块消息会被编码到一个码字（即图中灰色圆心）；当接收到含错的消息（如图中绿色）时，假设错误在一定范围内，我们倾向于认为该消息应是蓝色码字受到扰动产生，固可将其解码为蓝色圆心码字所对应消息；设想如果错误太多，收到的是红色的消息，则可能无法获得正确的解码。

因此纠错码的设计可以看成一个球堆积问题，球的半径越大，可以容忍的错误越多；空间内球的个数越多，则可被编码的消息越多。在相同的有限空间和球半径下，显然下图的排列方式可以编码更多消息，这是球在方盒内的最密堆积。


图片



高维空间下的最密球堆积问题目前仍是一个未解之谜，数学家仅对1、2、3、8、24 维的情况下给出了最优方案。Maryna Viazovska 就因证明了 8、24 维下的最密球堆积而获今年的菲尔兹奖（菲尔兹奖被誉为数学界的诺贝尔奖，每4年颁发一次，仅给颁奖时不满40周岁的数学家）。

我们考虑最简单的两种纠错码：
一种是平凡码 ：
，即不进行任何改动，当然这种编码不具有任何容错能力；

另一种是重复码 ：
，个 ，即将消息重复 n 次。

当错误个数不超过 时，我们只需看重复最多次的消息便可轻易恢复出 m。这是因为两个消息之间的极小距离（指的是汉明距离   ），我们记为 d = n。一般来说，若一个纠错码的极小距离为 d，则可以容忍   个错误。我们将字母表大小为 ，消息长度为 ，码字长度为 ，极小距离为 这样的分块纠错码记作   。

当然，重复编码并不能称之为一种好的编码，这是因为会消耗极大的通信传输成本。我们定义码率   ，表示编码的通信传输效率；同时定义相对距离   ，正比于容错率。通常我们希望码率和相对距离都越高越好，但两者当然无法兼得，我们今后会讨论两者之间的关系。举例来说，对于平凡码   ，码率为 1，而相对距离为 ；对于重复码   ，码率为 ，相对距离为 1。


线性纠错码

下面我们尝试构造一类有效的编码，叫做线性纠错码。顾名思义，线性纠错码是线性空间 的一个线性子空间   （即码字空间），满足：


这里，我们使用有限域 作为字母表。有限域可以简单认为在有限的数字上可以进行基本四则运算，例如对于素数 p，我们总有素域   ，定义其上的加法和乘法为整数的加法和乘法，但结果要模掉素数 p。

例如在 上，我们有     以及   。

减法是类似的， 。

如何做除法呢，注意到   ，因此   ，故     ，这还可以写作   。

有限域还包含另一类很重要的非素域，今后若遇到会再次提及，在此暂不做讨论。

根据线性代数的基础知识，线性空间 存在一组（不唯一的）基，取其中 k 个，记为   ，就构成了其上 k 维子空间的基，亦即码字空间的基。将这组基写成矩阵形式，记为 ，则获得了一个线性变换，我们称 为生成矩阵。这个线性变换便是一个纠错码，如果我们将消息也堪称一个向量 ，那么其编码成的码字即为 。

我们可以很容易的验证上述提到的两个性质：
  • 图片
  • 图片

读者可以自行验证，之前提到的平凡码和重复码均可视为线性码的特例。

考虑从含噪信道中接收到一个可能带错的消息 ，可将其写为 ，其中 为消息 的对应码字， 为错误。如果在 的余核空间内也找一组基 ，构成校验矩阵   ，满足 ，亦即 。 我们有 ，称为伴随式（syndrome）。

可见，伴随式包含了错误信息，接收到的消息是一个码字当且仅当其伴随式为零，或者 。如果生成矩阵有标准形式 ，其中 是 k 阶单位阵， 是 的矩阵，则对应的校验矩阵为 。

图片

将校验矩阵写成 ，则有 。即伴随式是 的列向量的（错误）加权和。注意到，因为 的列向量线性相关，即存在码字 满足 。假设纠错码中任意两个不同码字间的极小距离是 ，则码字 的最小汉明重量 是 ，亦即至少有 个列向量是线性无关的，这便是所谓的辛格尔顿界： 。


汉明码（Hamming Code）

现在我们来显示地构造可以容许单个错误的纠错码。假设传输过程中仅出现一个错误，那么 。只需要从 的列向量中找出与伴随式 线性相关的一列 即可。表明错误发生在第 位，且与正确的码字相差 。为了方便，我们仅考虑二元域 。我们知道，纠正单个错误要求纠错码的极小距离 ，因此要求至少有 个 的列向量是线性无关的。在二元域中，这等价于每一列非零 ，且不同列不相同，即对于 有 。固定消息长度 ，共有 个非零且不同的列向量，将其放入校验矩阵中，有


这是一个 码，也叫汉明码（Hamming Code）。因为 ，解码时，只需逐列比较伴随式即可。

作为例子，我们观察 汉明码，对应的生成矩阵和校验矩阵（标准形式）分别为：
 
如果消息 ，则对应码字 ，假设接收到的消息 。计算伴随式 ，比较 的列向量，可发现与第四列一致，故知错误发生在第四位。可以计算汉明码的码率 ，随着消息长度增加，汉明码的传输愈加高效；但同时其相对距离 趋于 0，即相对纠错能力越低。

至此，我们已经能够构造任意长度的单错误纠错码，这在历史上已经取得了显著的成绩，加速了纠错码技术的发展，但如何构造容许双错误的纠错码技术仍然进展缓慢。最终，在 1960 年代，双错误纠错码由 Bose、Chaudhuri 和 Hocquenghem 共同发现，其与汉明码的构造有着颠覆性的差别。关于这种纠错码，我们之后再进行详细介绍，欢迎大家继续关注墨奇博客。

—End—


对外活动
阅读原文
分享