【理论学习】【科研点子】【NUS游记】Exploring Steganagraphy : From LSB to ZKP

发表于 2023-07-28 更新于 2023-08-01 分类于理论学习

这段时间去NUS了，进了安全相关的课堂，小组project是数字隐写。最后我们做了对最简单的LSB算法的鲁棒性和安全性的改进，还蛮有意思。

最后完成了结业论文(click to see the small version)：

简单来讲，我们研究的是数字水印和隐写术，即将信息写入到图片中且肉眼察觉不出来。

基础算法是LSB (Least Significant Bit) 算法：每个像素由RGB三个通道组成，每个通道8位，我们把每个通道的最低位作为我们可以用来保存信息的信息位。

例如：某像素的RGB原始值为(00000000,01100100,11101011)，看起来是这个颜色——

color1

我们可以利用这个像素存储三位的信息，比方说100。则我们将这个RGB修改为(00000001,01100100,11101010)，现在看起来是这个颜色——

color2

肉眼上没有什么不同。因此我们将100这段信息成功隐藏了。

LSB是个很简单的算法，它的读写都很容易，1/8的信息率也很高。但是LSB的鲁棒性很差，也就是说，如果将嵌入了信息的图片进行剪裁、压缩、添加噪声等操作，信息是非常容易丢失的。

我们的主要工作之一就是针对各种图像变换都提出了相应的鲁棒方案。

对于剪裁，方法是把信息在图片的多处进行重复，这样无论如何剪裁总还是会剩下一些完整的信息。

对于噪音，我们把信息换成纠错码即可。队友采用的是Reed–Solomon纠错码，最后发现可以抵抗18%的概率噪声（每一位信息都有18%的概率翻转，已经是一个很严重的噪声了）。

对于旋转和缩放，LSB非常难以通过改进产生对这两者的鲁棒性。最后相当于直接用了另一个算法。先把原图（空域图）进行傅里叶变换，产生频域图，在频域图上直接写上信息（写得很小，但是是人眼看得见的信息），然后再傅里叶逆变换回来，对原图的影响也很小。然后原图在经过旋转和缩放等变换后，再傅里叶变换得到频域图，会发现原来写的字还在（当然会变模糊）。

对于灰度，这是我负责的主要工作。

接下来直接将我论文里的内容机翻（人工稍许修改）：

在sRGB(standard RGB color space)中，原始图像的灰度是指保持原始图像相同的感知亮度和RGB组合的图像。局部灰度是原始图像和其灰度的一些线性组合，保持感知亮度不变，且介于原始图像和灰度之间。下图显示了灰度和部分灰度的示例。

原图：

ori

50%灰度（左）和100%灰度（右）：

50 and 100

具体地说，我们假设所有图像都由RGB像素组成，对于RGB的每个通道，都取中的整数值。对于一个像素，它的线性亮度定义为：(实际上，RGB系数的定义是多样的，这里我们只考虑这个特定的线性组合，称为Rec.709标准。但我们即将提出的算法将很容易扩展到其他线性组合)。保持不变，使，我们便得到原始像素的灰度像素。显然，此时，其中位于(因此一个灰度像素只需要一个通道来存储)。设

，

则是原始像素的k灰度像素，其中k介于 $，$ 之间。

形式化地，

，

缩写为，

。

因此，

。

特别地，

。

对于原始图像，将所有像素转换为它们的灰度像素，这样我们就得到了一个灰度图像，并将所有像素转换成它们的k灰度像素，这样我们就得到了一个k灰度图像(部分灰度图像)。

可以注意到，对于任何像素，它具有的不变性；对于所有像素，它具有的不变性。这促使我们利用该属性来存储信息。

当时，k灰度图像实际上可以通过的一种反函数来反转。(不严格地说，我们仍然称它为)。
也就是说，

显然我们知道R’G’B’。根据Y公式，我们可以很容易地计算出Y。对于k，我们需要一个小把戏。我们引入了信息像素，它可以是第一个像素，也可以从灰度化前后都很容易检测到的任何其他像素中选择。原始图像中信息像素的RGB被强制定义为 $，$ 。因此，经过灰度变换后，信息将变成 $，，$ 。所以我们在灰度中检查这个像素，我们就可以计算出。然后，我们可以恢复嵌入在原始图像中的消息，因为我们已经知道了计算 $，，$ 公式所需的所有值。

但要注意，一般有约100个k（即0%~99%），但是只有74种情形（G从255到(255-73)），这意味着有多个k会映射到同一个G’，因此我们在解码时根据所有可能的k解出多套结果，统一检视即可。这一点也说明，该算法对于RGB通道长度越长（即色彩更为细致）的图效果越好。

现在，最困难的部分是的情况，也就是说，一个完全灰度图。首先，我们不能还原它，因为它以非常粗糙的方式将三维信息压缩到一维，每个通道只能贡献很小的影响。

因此，我们只能通过修改原始图像，尝试以某种可预测的方式影响最终的灰度图像，从而保留一些信息。

首先，我们要从信息论的角度证明它是可行的。现在的问题是，无论对三个通道的最后一位做什么修改，是否有一个在灰度化后无法区分的RGB组合？数学化地，如果代表按位异或(这与C等编程语言中的情况一致)，那么问题就是

如果答案是肯定的，那么我们的隐写目标就不能实现，因为一旦作为上述命题的肯定示例的这些RGB组合出现，他们在灰度图像中的表现就是被锁定的，无法在其中嵌入任何消息。

幸运的是，答案是否定的。我们可以编程检查每一个可能的组合，看看是否有影响灰度结果的修改，结果证明是正确的。（通过数学方法也很容易证明）

这意味着：
设(即LSB)，

因此，我们可以根据需要操作所有像素，以便每个像素在灰度化后的最后一位可以显示我们想要的信息。

以上就是有关灰度的部分。

此外，我们还把隐写术和密码学结合了一下。同时使用了对称加密和非对称加密，最终能够实现证明图片的归属人是谁。

我还写了最后一个部分，就是跟零知识证明结合，其实就是往图片里加两张同构图。而证明两张图同构or不同构是很困难的。而它是存在一个零知识证明的。具体请看论文。这样子，当法庭需要你证明这张图是你的的时候，你只需要零知识地证明你隐藏的这两张图是同构的即可。

与图同构这种零知识证明结合有个额外的好处，那就是我们可以往电影之类的大媒体中直接画出你想镶嵌的两张图（用之前说的傅里叶变换频域图的方法）（每一帧都画出图的一部分）。这样，即使图受到一定的破坏，即使一些边和顶点失去了，这大概率仍是原图的近似图。我们给出的原始同构模式对当前的两张近似图仍可给出一个近似的同构，而“给出近似解”在近似度比较大的时候，仍然是一个困难的问题，因此仍可作为所有权证据采信。