当我们谈论隐写术时，人们会想到恐怖分子、恋童癖、间谍，或者充其量是密码无政府主义者和其他科学家。 真的，还有谁可能需要 隐藏 来自外眼的东西？ 这对于一个普通人来说能有什么好处呢？
事实证明有一个。 这就是为什么今天我们将使用隐写术方法来压缩数据。 最后，读者甚至可以使用 JPEG 格式的珍贵照片档案来增加文件系统上的可用 GB 数量。
什么？
如果读者还记得的话，隐写术是一种非常奇怪的算法，可以将一种信息的存在隐藏在另一种信息中。 用更简单的语言来说：图片+文件==大致相同的图片，但不完全相同（除了图片之外，还可以有任何东西，但通常其中的所有内容都更清晰）。 应该没有一个简单的方法来确定里面是否有东西。
但如果两者无法区分，那还有什么区别吗？ 从消费者的角度来看，用户并不关心数学精度（由一组特定的位反映），只关心他所感知的内容。
例如，让我们看三张可爱的狗的图像：
当心，JPEG！
尽管尺寸差异巨大，但很少有人会选择第三个版本。 另一方面，前两张照片之间的差异并不那么明显，并且它们中的信息量（从我的角度来看）可以是相等的。
这个原理本身已经很古老了，多年来一直被有损信息压缩方法积极利用。 但打破并不意味着建设；我们对问题更先进的一面感兴趣。 是否可以嵌入额外的尺寸信息 N 到文件，使其大小增加 M < N，但用户没有注意到这些变化？
当然可以。 但值得立即进行一些预订：
- 首先，该方法必须是通用的，并对大多数输入数据给出积极的结果。 也就是说，平均而言，对于随机输入，存储的信息量应该实际减少。 “平均”意味着相反的情况可能会发生，但不应占主导地位。
- 其次，嵌入信息之前的压缩容器的大小必须大于以类似方式压缩的修改后的大小。 使用 LSB 方法简单地将一堆位嵌入到 BMP 图像中并不是隐写压缩，因为经过某种 DEFLATE 处理后，原始图像很可能会明显变小。
- 第三，必须将结果与已经通过经典方法压缩的数据进行比较。 这将消除冗余差异的概率影响，并在一般情况下提供更有效的压缩。
在哪里？
隐写术的使用意味着，除了压缩信息之外，我们还需要嵌入信息的容器。 嵌入信息的最大数量很大程度上取决于各个属性，但随着其数量的增加而扩展要容易得多。 因此，容器格式必须是通用的，以便用户有足够的容器格式从“压缩”过程中获得任何好处。
在这种情况下，图形、音频和视频文件都是不错的选择。 但是，由于各种不同的格式、编解码器等，实际上我们的选择并不多。
考虑到这一切，我的选择落在了 JPEG 上。几乎每个人都有它，它广泛用于个人和商业目的，几乎是大多数图像的事实上的格式。
这取决于？
接下来是近技术图表和描述，没有太多解释，因此感兴趣的人可以滚动到“高科技”部分来跳过它们。
共同特点
要将数据嵌入某处，您必须首先确定在哪里。 文件系统上可以有任意数量的不同照片，用户可能只想使用其中的几个。 我们将这样一组所需的容器称为库。
它在两种情况下形成：压缩前和解压前。 在第一种情况下，您可以简单地使用文件的一组文件名（或者更好的是，它们的正则表达式），但在第二种情况下，需要更可靠的东西：用户可以在文件系统中复制和移动它们，从而阻止它们被正确识别。 因此，在所有修改完成后，有必要存储它们的哈希值（md5就足够了）。
在这种情况下，使用正则表达式在整个文件系统中进行初始搜索是没有意义的；指定某个根目录就足够了。 其中将保存一个特殊的存档文件，其中将包含这些哈希值以及后续恢复压缩信息所需的其他元信息。
所有这些同样适用于任何隐写数据压缩算法的任何实现。 数据压缩和恢复的过程本身可以称为打包和解包。
F5
现在我们已经清楚了我们在做什么以及为什么这样做，剩下的就是描述实现目标的算法。 让我们回忆一下编码 JPEG 文件的过程（感谢鲍曼国家图书馆的 wiki）：
看完了，不如赶紧发表几句评论：
- JPEG 文件的大小可以被认为是最佳的，甚至无需尝试使用某种 Winrar 对其进行压缩；
- 只有存储的信息（从离散余弦变换，DCT 输出的信息）可以被修改以提供至少可接受的性能。
- 为了不丢失用户注意到的工业规模的数据，有必要对每个单独的图像进行最少的修改；
一整套算法都符合这些条件，您可以熟悉一下 。 其中最先进的是算法 由 Andreas Westfeld 设计，使用亮度分量的 DCT 系数（人眼对其变化最不敏感）。 使用现有 JPEG 文件时其总体布局如下所示：
F5 块使用基于矩阵编码的高级嵌入技术。 读者可以在上面的链接中了解有关它和算法本身的更多信息，但我们主要感兴趣的是，在它的帮助下，在嵌入相同量的信息时，所使用的容器的大小越大，您可以进行的更改越少，并且为了执行算法只需要执行简单的霍夫曼和RLE（解码）编码操作。
这些更改本身是针对整数系数进行的，归根结底是将其绝对值减一，一般来说，这允许使用 F5 进行数据压缩。 关键是，由于 JPEG 中值的统计分布，霍夫曼编码后绝对值减少的系数很可能会占用更少的比特。
在形成零的情况下（所谓的减少），存储的信息数量将根据其大小减少，因为以前的独立系数将成为 RLE 编码的零序列的一部分：
修改
数据保护和压缩是正交问题，因此可以忽略原始算法的秘密密码排列。 此外，我们需要确切地知道如何提取数据，因此所有必要的信息（使用了哪些容器，以什么顺序等）都应该记录在一个单独的文件中，并开放供归档器免费读取。
最初的算法旨在传输秘密消息，因此它一次仅适用于一个容器，假设用户自己会在必要时将其分解成多个部分（如果有的话）。 此外，当独立嵌入到每个容器中时，您需要提前知道每个容器中要放入多少位数据。 因此，库中每个元素的系数应该组合成一个抽象的大系数，并根据原始算法对其进行处理。
由于原来的F5允许最多12%的容器大小，因此这次修改也会增加最大容量：“最多12%”整个库大小的总和大于或等于“最多12%” ”从它的每个元素。
编码后的总体方案如下：
算法本身
现在是时候从头到尾描述算法本身了，以免让读者蒙在鼓里：
- 用户使用正则表达式和搜索根目录定义二进制可压缩数据M和库L；
- 按照它们在 FS 上出现的顺序，库元素形成 MC：
- 从文件数据中解码出一系列系数C；
- MC <- MC | C;
- 参数k是根据可怕的不等式确定的：
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - 接下来拍摄
n = (1 << k) - 1来自 MC 的非零元素的最低有效位并写入a:- 考虑了神奇的哈希函数
f，代表一个n位字a到 k 位s; - 如果
s == 0，则无需更改任何内容，算法将继续处理下一个系数； - 减少负责的系数的绝对值
s-嘿，这个词有点a; - 如果减少的结果出现减少（系数变为0），则从头开始重复该步骤；
- 考虑了神奇的哈希函数
- 所有系数均经过RLE和Huffman编码，写入源文件；
- 将参数k写入归档文件；
- 根据每个文件 L 的原始位置顺序计算 MD5 哈希值并将其写入存档文件。
高科技
该算法的幼稚形式和其他高级（尤其是垃圾收集）语言的实现会带来糟糕的性能，因此我用纯 C 实现了所有这些复杂性，并在执行速度和性能方面进行了许多优化。内存（即使在 DCT 之前，您也不知道这些图片在没有压缩的情况下有多重）。 但即便如此，一开始执行速度还差强人意，所以我就不描述整个过程和使用的方法了。
跨平台是通过结合 libjpeg、pcre 和tinydir 库来实现的，为此我们感谢他们。 默认情况下，一切都通过正常编译 make，所以Windows用户想要自己安装一些Cygwin，或者自己处理Visual Studio和库。
该实现以控制台实用程序和库的形式提供。 有兴趣的人可以在 Github 存储库的自述文件中找到有关使用后者的更多信息，我将在帖子末尾附加该链接。 在这里我们继续对这项工作进行描述和演示。
如何使用？
小心。 使用过的图像可以根据需要移动、重命名和复制。 但是，您应该非常小心，不要以任何方式更改其内容。 更改一位会破坏哈希值并导致无法恢复信息。
假设编译后我们得到可执行文件f5ar。 您可以分析库的大小，以使用标志计算其使用的可能性 -a: ./f5ar -a [папка поиска] [Perl-совместимое регулярное выражение]。 包装由团队完成 ./f5ar -p [папка поиска] [Perl-совместимое регулярное выражение] [упаковываемый файл] [имя архива]，并使用解包 ./f5ar -u [файл архива] [имя восстановленного файла].
工作示范
为了展示该方法的有效性，我从该服务上传了 225 张完全免费的狗照片集 。 每张照片的质量都比普通用户照片稍高，但仍然如此。 它们中的每一个都使用 libjpeg 重新编码，以抵消库的编码功能对整体大小的影响。 为了指示可压缩数据的最差示例，使用 dd 生成随机 36 米（略大于总大小的 5%）均匀分布文件。
测试过程非常简单：
$ ls
binary_data dogs f5ar
$ du -sh dogs/
633M dogs/
$ du -h binary_data
36M binary_data
$ ./f5ar -p dogs/ .*jpg binary_data dogs.f5ar
Reading compressing file... ok
Initializing the archive... ok
Analysing library capacity... done in 16.8s
Detected somewhat guaranteed capacity of 48439359 bytes
Detected possible capacity of upto 102618787 bytes
Compressing... done in 32.6s
Saving the archive... ok
$ ./f5ar -u dogs/dogs.f5ar unpacked
Initializing the archive... ok
Reading the archive file... ok
Filling the archive with files... done in 1.2s
Decompressing... done in 17.5s
Writing extracted data... ok
$ sha1sum binary_data unpacked
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 binary_data
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 unpacked
$ du -sh dogs/
563M dogs/或者截图给粉丝
正如您所看到的，从硬盘上原始的 633 + 36 == 669 MB 数据，我们最终得到了更好的 563，压缩比约为 1,188。 这种根本性的差异可以通过极小的损失来解释，类似于使用经典方法（例如tinyjpg）优化 JPEG 文件时获得的损失。 当然，当使用隐写压缩时，信息不会简单地“丢失”，而是被用来编码其他数据，而且，由于使用F5，“优化”系数的数量比传统优化要少得多。
无论有什么修改，它们都是肉眼绝对看不见的。 在下面的剧透中，读者可以通过肉眼和从原始值中减去更改组件的值来评估差异（颜色越柔和，差异越小）：
链接到不适合 habrastorage 的图像
原来的 -
修改的 -
不同之处 -
取而代之的是结论
我希望我能够让读者相信这种方法是可行的并且具有生命权。 然而，购买硬盘或额外的通道（用于网络传输）似乎比试图通过这种方式省钱要简单得多。 一方面，这是事实；广泛的开发往往更简单、更可靠。 但另一方面，我们也不应该忘记激烈的事情。 毕竟，不能保证明天您就能到商店再购买一个 XNUMX TB 的硬盘，但您始终可以使用家里已有的硬盘。
->
资料来源：www.habr.com