隐写术：在其他事物中隐藏事物的艺术与科学 – 第三部分
这是四部分系列中的第三部分。在第一部分中，我们介绍了图像格式的基础知识，并找到了在图像中隐藏数据的位置。在第二部分中，我们实际编写了代码，将数据隐写编码到图像中，然后提取它，而不使图像看起来不同。
厌倦这张图片了吗？
然而，在第二部分中我们遇到了一个问题——压缩。当图像被压缩时，我们精心隐藏的数据可能会被损坏。我们通过将消息中的每一位重复9次来解决了这个问题，但我们可以做得更好。本文将介绍如何利用一些数学方法，即纠错码，在每张图像中隐藏更多数据位。
我们的朋友维基百科给出了纠错码的一个很好的定义：
“纠错码（ECC）是一种向消息添加冗余数据的过程，使得即使引入了一定数量的错误（最多达到所用码的能力），接收方也能恢复消息。”
我们之前使用的重复是最简单的ECC——我们发送冗余数据，一遍又一遍地重复自己，这样即使某些位出错，我们仍然可以接收消息。
不过，在我们开始寻找更好的方法之前，我们需要定义我们的问题。我们知道压缩会破坏数据，但具体是如何破坏的呢？
首先，我们可以说压缩引入了噪声——换句话说，有些位不是我们期望的那样。例如，我们可能输入消息1101，但输出1100——在这种情况下，我们会说最后一位从1“翻转”到了0。既然我们知道存在一些噪声，如何定义它呢？
好吧，我们有几个选择。你可以阅读论文，比如这篇8页的论文，由舰队信息战中心的某人撰写，或者你可以做一些假设并看看它们是否有效。
让我们折中一下，做出一些基于现实的假设。它们可能不是100%正确，但足够正确。因此，就我们的目的而言，我们可以假设：
- 随机、位置无关的噪声：噪声中没有特定的模式；任何给定的位被翻转的机会与任何其他具有相同重要性的位相同。这意味着在图像中哪里编码数据并不重要；例如，图像左下角的像素与中间的像素被更改的可能性相同。
- 更重要的位噪声更少：任何像素的最低有效位最可能被翻转，因为压缩试图消除无用数据，并且位被翻转的机会随着位变得更重要而减少。
- 噪声是二进制对称的：这是一种花哨的说法，表示噪声是无偏且均匀分布的——零被翻转的可能性与一相同。
与其花大量时间从会被压缩的网站上传和下载图像，我们可以通过随机化图像中的一些位来模拟这种类型的噪声。这让我们可以使用代码，这很好且可控，因此我们可以轻松进行大量测试。
这是我们的图像在模糊之前和之后：
它可能看起来没有很大不同，但它把we’re going to hide this message in an image!变成了we’re eking to hide this message in an image（结尾没有感叹号），所以它肯定造成了一些损害。
现在的挑战是能够从模糊的图像中提取数据，即使存在噪声。第二部分的重复方法有效，但必须将每一位重复9次意味着我们无法传输足够的数据。我们可以做得更好。
不过，在我们深入纠错之前，我们需要谈谈奇偶校验位。本质上，奇偶校验位向任何给定的二进制字符串添加一个检查，告诉我们字符串中1位的数量是否为奇数。例如：字符串000没有1位，因此其奇偶校验位为0（留给我们最终的字符串0000）。相反，字符串010有奇数个1位，因此其奇偶校验位为1，留给我们0101。你会注意到，这意味着一旦添加了奇偶校验位，每个字符串都有偶数个1。
过程是：
- 根据你的消息计算奇偶校验位。如果它有奇数个
1值，奇偶校验位是1，否则奇偶校验位是0。 - 将这些奇偶校验位放入消息中；它们通常放在末尾，但只要接收方知道在哪里找到它们，它们放在哪里实际上并不重要。
我们为什么这样做？很简单——如果字符串中的某个位被翻转，我们可以通过检查奇偶校验位来发现有问题（如果上面的字符串0101变成了1101，我们知道110的奇偶校验位应该是0——但它是1，所以一定出了问题）。不幸的是，这只能告诉我们出了问题——而不是什么出了问题。我们无法知道哪个位被翻转了。
于是理查德·汉明登场，他发明了汉明码，一种结合奇偶校验位来检测和纠正错误的方法。坚持住，这即将变得非常棒（而且非常数学化）。
在下一部分中，假设你试图发送4位数据，并且你（以某种方式）知道其中不会有多于一个错误。
假设你有通常的奇偶校验位和4位数据。如果有错误，你怎么知道哪个位错了？你不能——四个中的一个被翻转了，但无法知道是哪一个。（请注意，这些图形中的圆圈每个代表一个奇偶组——一旦所有奇偶校验位被计算并添加，每个组都会有偶数个1。这意味着如果我们接收消息时一个圆圈没有偶数个1，我们就知道出了问题。）
如果你只是添加另一个奇偶校验位，那很好，但你所做的只是重复了奇偶校验位——这很有用，因为这意味着你可以通过检查另一个来告诉其中哪一个错了。但这似乎 mostly 是浪费。如果出现问题，你仍然无法判断哪些数据位被翻转了——第二个奇偶校验位没有提供新信息。
让我们尝试一些奇怪的方法。如果你从第一个奇偶校验位中排除第4个数据位会怎样？如果前三个数据位中的任何一个被翻转，第一个奇偶校验位会告诉我们，如果它们中的任何一个被翻转，第二个奇偶校验位会像往常一样告诉我们，但是……如果第一个奇偶校验位错了，可能是前三个数据位中的任何一个错了，但如果第二个奇偶校验位错了，可能是四个中的任何一个。看起来我们在这里有点缩小范围了。
如果我们再进一步，不断缩小第一个奇偶校验位覆盖的位数，我们得到下面的布局。我们在这里做了一件不可思议的事情！如果两个奇偶校验位都错了，我们知道第一个数据位错了——不仅仅是“一个位”，而是确切地知道哪个位错了！
如果你再进一步，你最终可以到这里：
说真的，花一分钟看看上面的图片。这意味着如果任何一个数据位被翻转，你可以判断是哪一个并修复它，因为你知道每个圆圈必须包含偶数个1。通过扩展这个想法，你可以玩弄奇偶校验位和数据位的数量来处理不同级别的错误—— broadly speaking，更多的奇偶校验位帮助你纠正更多错误，但这意味着你用于数据的空间更少。
如果纠错码仍然令人困惑，这样想——我们创建了一堆接收无效的潜在消息，所以如果你收到它们，你就知道出了问题（有效消息被称为“码字”——“纠错码”中的“码”）。当你收到一个你知道错误的消息时，你可以通过选择与你收到的内容最相似的有效码字来纠正错误（这意味着我们希望码字尽可能不同，以便任何给定的不正确消息应该对应哪个码字是明显的）。
这是纠正错误的数学基础，比我们之前使用的简单重复要高效得多——在我们的例子中，我们可以容纳超过四倍的数据量！下次，我们将把这些数学付诸实践。
Dakota 运营 Striker Security – 你可以在 https://strikersecurity.com/blog 找到更多他的文章