基于QR码低复杂度信息隐藏方案

郑 东, 杨舜同, 赵庆兰

(西安邮电大学 无线网络安全技术国家工程实验室， 陕西 西安 710121)

快速响应码(quick response，QR)[1-3]是二维条码的一种,已广泛应用在印刷、在线广告、移动支付及互联网商务等各个方面[4]。但是，QR码缺乏足够的安全保护[5]，存储在后端数据库的网络链接直接暴露，会造成许多潜在的安全风险[6]。因此，QR码的信息安全隐私问题引起了越来越多学者的重视。

目前，保护秘密数据主要是利用图像隐藏[7-10]方案、水印技术[11-14]、秘密共享方案[15]及信息隐藏方案[16]。图像隐藏方案是将QR码视为秘密图像，然后将QR码隐藏到封面图像的特殊域[7-8]或频域[9-10]中，对秘密QR码进行保护。水印方案[11-14]利用离散小波变换[11]、离散余弦变换[12]和离散傅立叶变换[13]或直接调整QR模块行和列的宽度[14],将水印嵌入到QR码图像的频域或特殊域中，对秘密进行保护。秘密共享方案[15]是将秘密数据转化为QR码的形式进行存储，但是，条形码读取器扫描QR码时，很容易获得秘密数据内容。信息隐藏方案[16]利用QR特征将秘密嵌入QR码的模块中，并使用QR码本身的纠错机制将其隐藏，减少了秘密被发现的可能性。但是在被怀疑隐藏信息的场景下，存在着相同型号QR码破解难度随着隐藏秘密数量变少而降低的问题，并且当QR码被恶意篡改后无法恢复秘密。

为了保护QR码中的数据安全，本文设计一种基于QR码低复杂度信息隐藏方案。通过直接修改QR的编码模块，利用用户秘钥控制的伪随机发生器[17]生成位置序列，将秘密信息隐藏在QR码的编码过程中，再通过完成QR码的编码，得到隐藏信息的QR码。该QR码可以被扫描器正常读取，授权用户可以通过密钥恢复出隐藏信息，而未授权用户只能读取QR码的封面信息。

1 QR码

QR码[3-5]由白色和黑色两种方形模块构成，分别代表0和1，通过2D矩阵表示。QR码标准提供了40个QR版本，可编码各种数据，其中版本1容量最小，版本40容量最大。用户使用的版本取决于字母数字、二进制、汉字或其组合编码的数据量以及纠错级别。另外，QR码非常可靠性，即使条形码的部分脏污或损坏，也可以正确地读取数据。

QR码主要由功能标识区域和编码区域组成，周围由空白区域包围。以QR码的版本7为例，结构如图1所示。

图1 QR码的组成

功能标识区域由定位标识、分隔符、定时标识和校正标识组成。除右下角以外的每个角落，有3个相同的定位标识，主要识别QR码并确定QR码的旋转方向；分隔符是宽度为1的白模块构成的白色点带，用于将编码区域和定位标识分开；定时标识是宽度为1的黑白交替点带，起始和结束均为黑色模块，用于指示标识密度和确认坐标系；校正标识，用于进一步校正坐标系，只有版本2以上的QR码才有，不同的QR码版本具有不同数量的校正标识。

编码区由格式信息、版本信息及数据和纠错码组成。版本信息仅存在于版本7及以上版本，数据和纠错码是由数据码字和纠错码字组成。数据码字是消息数据编码的编码块，大小都为8位。纠错码字则是基于QR码版本和纠错级别，将码字划分为多个纠错块，再为每个块生成适当数量的纠错码字。如果部分模块脏污或损坏，纠错功能也可以正确解码消息。

QR码采用Reed-Solomon错误控制编码[17]进行错误检测和纠正。用户可以选择L、M、Q和H等4种错误纠正级别，如表1所示。每个级别提供不同的纠错能力，更高的纠错级别具有更好的纠错能力，但也会增加要编码的数据量。

表1 QR码纠错级别

QR码的编码过程主要分为以下3步。

(1)生成数据块。数据码字使用交错的方式编码，纠错码字附加到数据码字序列的末尾，可以尽量减少因局部损坏而导致QR码变得不可解码的可能性。

(2)填充QR码图像，并根据QR码标准[3]计算掩码类型并添加掩码。在对数据码字进行编码之后，将平衡白和黑模块的掩码应用于编码区域。掩码类型总共有8种(0～7)，选择合适掩码类型能减少可能会混淆QR码阅读器的不良图案。

(3)添加格式信息和版本信息。

2 信息隐藏与秘密共享

利用QR码的特征，可以将秘密信息隐藏在QR码模块中，从而实现秘密共享，隐私保护等应用。

2.1 信息的隐藏

秘密信息隐藏容量由QR码的版本和纠错级别控制，并且根据隐藏的信息加上纠错码后的最大长度确定QR码的版本和纠错级别。信息隐藏就是根据随机位置信息序列LN，确定QR码中秘密信息的隐藏位置，而位置信息序列LN则由用户设置的密钥确定。信息隐藏的具体步骤如下。

步骤1 使用用户密钥生成随机种子key。

步骤2 根据种子key生成范围为(0,c)且长度为2c的随机序列，c为码字总数。

步骤3 删除随机序列中的重复项并获取前r个数据，r为纠错能力。

步骤4 遍历所有(r,i)项，i为大小为8的QR码单个编码块中的位置，0≤i≤7。

步骤5 使用种子key控制的伪随机发生器，混淆r×8个条目，得到位置信息序列LN={L1,L2,…,Ln}(0

步骤6 对QR码的封面数据m执行QR码编码程序，直到生成数据码MQR为止。

步骤7 根据需要隐藏的秘密信息长度，利用Reed-Solomon纠错码标准[18]分别为每个隐藏信息计算纠错码，并加到每个秘密信息后得到秘密序列SN。

步骤8 根据位置信息序列LN，在数据码MQR中嵌入秘密序列SN。

步骤9 将隐藏秘密数据块继续QR码的编码过程，根据QR码标准计算掩码类型并添加掩码，完成QR码的生成。

根据QR码的编码过程，由步骤1～步骤5生成的随机位置信息序列LN，将信息嵌入QR码块中，进行QR码的正常编码，最后计算掩码模式类型并添加掩码，完成QR码生成。生成的隐藏QR码更加自然，可避免引起攻击者的怀疑。

2.2 隐藏信息的恢复

相同的伪随机发生器使用相同的种子key，生成的位置信息序列LN也是相同的。因此，只要用户知道密钥就可以在本地生成随机位置序列LN。在扫描和解码过程中，根据位置信息序列LN可以简单的实现秘密信息的读取，在QR码扫描器中，计算复杂度低。隐藏信息恢复的具体步骤如下。

步骤1 扫描QR码得到数据块纠错之前的信息。

步骤2 根据信息隐藏的步骤1～步骤5，计算随机位置信息序列LN。

步骤3 通过位置信息序列LN中每一项的(r,i)，直接读取隐藏后的QR码编码块，获得秘密序列SN。例如LN第1项为(8,1)，即读取QR码第8块的第2位。

步骤4 根据秘密序列SN进行纠错，并获取隐藏的秘密信息。

隐藏的信息会被QR码本身的纠错功能纠错，因此，需要使用QR码纠错之前的数据，对隐藏信息进行读取，然后使用隐藏信息内部的纠错码进行纠错得到正确的秘密信息。

2.3 秘密共享

秘密共享[19]是将秘密划分为n个秘密份额[20]。任何人都无法从自己的秘密份额中解密原始秘密。只有当n个秘密份额中的任意k个或以上(k≤n)秘密份额在一起时，才能恢复秘密。秘密共享的过程如图2所示。

图2 秘密共享过程

秘密共享实现分为计算秘密份额和秘密份额恢复两个步骤。

根据(k,n)门限方案[19]，选择k(k≤n)作为门限，即有k个及以上用户聚集可恢复秘密。设a0为秘密数据，p(p≥a0)为大质数。选择参与者x1,x2,…,xn，其中n为参与者个数，也是隐藏的QR码标签的数量。构造(k-1)次多项式，秘密份额[19]可表示为

f(x)=a0+a1x+a2x2+
…+ak-1xk-1(modp),

其中a1,a2,…,ak-1∈Zp，Zp为有限域。因此，每个参与者的秘密份额可表示为(xi,f(xi)=yi)。

在秘密恢复的过程中，任何从n个秘密份额中获得的k个秘密份额，通过拉格朗日多项式插值[19]

恢复秘密数据ao。参与者x1,x2,…,xn中任意k个参与者的秘密份额为(x1,y1),(x2,y2),…,(xk,yk)。

得到秘密份额后，将n个秘密份额通过信息隐藏步骤隐藏到n个QR码中，只有持有其中k个及以上QR码并持有各自秘密份额的情况下，才可以通过秘密恢复步骤恢复秘密S。

3 仿真结果分析

利用PYTHON语言，基于LINUX操作系统的仿真环境进行实例仿真。使用Mersenne twister算法[21]作为伪随机发生器，并均使用版本1纠错级别H的QR码作为仿真对象，实现QR码的信息隐藏及恢复的过程和秘密共享，验证方案的可行性和适用性。

3.1 实例仿真及结果分析

以(3,4)为例，实现秘密共享。假设多项式f(x)=1+2x+x2(mod 13)，秘密S为1，则得到秘密份额为(1,4)，(2,9)，(3,3)，(4,12)。将秘密份额分别发给Alice、Bob、Tom和Jack等4个人，原始QR码如图3所示。

图3 原始QR码

图3(a)为Alice的秘密份额(1，4)，用户秘钥为Alice，掩码类型为5。根据信息隐藏步骤，生成的位置序列LN为{(12, 3), (20, 6), (12, 5), (2, 7), (20, 5), (1, 7), (2, 2), (0, 4), (0, 7), (25, 7), (20, 7), (2, 0), (15, 4), (2, 5), (12, 7), (15, 3), (0, 0), (15, 0), (12, 2), (0, 3), (15, 5), (20, 0), (0, 6), (11, 0), (1, 3), (0, 1), (15, 2), (11, 5), (1, 5), (11, 2), (12, 1), (1, 6), (20, 4), (11, 1), (2, 4), (25, 5), (11, 4), (25, 3), (0, 2), (2, 6), (2, 3), (25, 4), (1, 0), (2, 1), (11, 6), (20, 3), (25, 1), (0, 5), (1, 4), (12, 0), (1, 2), (25, 2), (11, 7), (1, 1), (15, 7), (12, 6), (20, 2), (25, 6), (12, 4), (11, 3), (25, 0), (15, 1), (15, 6), (20, 1)}。生成的数据码MQR为{64, 84, 22, 198, 150, 54, 80, 236, 17, 23, 150, 138, 92, 36, 196, 194, 252, 186, 128, 157, 143, 101, 155, 141, 213, 206}。生成的带纠错码的秘密序列SN为{26, 0, 13, 128, 5, 175, 61}。生成的隐藏QR码数据码为{4, 240, 51, 198, 150, 54, 80, 236, 17, 23, 150, 131, 10, 36, 196, 70, 252, 186, 128, 157, 148, 101, 155, 141, 213, 242}，其中下划线数据为隐藏的数据块。

图3(b)为Bob的秘密份额(2,9)，用户秘钥为Bob，掩码类型为3。根据信息隐藏步骤，生成的位置序列LN为{(22, 4), (21, 1), (0, 1), (6, 7), (25, 4), (25, 6), (25, 2), (22, 2), (22, 5), (24, 3), (25, 3), (2, 4), (0, 6), (6, 1), (22, 1), (24, 2), (24, 7), (21, 0), (2, 7), (15, 6), (15, 3), (22, 6), (6, 6), (24, 1), (0, 5), (21, 4), (0, 3), (21, 7), (2, 3), (0, 0), (2, 0), (15, 1), (0, 7), (24, 6), (25, 1), (15, 5), (21, 6), (0, 2), (2, 2), (22, 7), (25, 0), (21, 5), (6, 3), (6, 2), (21, 3), (2, 5), (6, 0), (22, 3), (6, 5), (0, 4), (15, 0), (25, 5), (24, 0), (22, 0), (24, 4), (2, 1), (15, 4), (21, 2), (25, 7), (24, 5), (2, 6), (6, 4), (15, 7), (15, 2)}。生成的数据码MQR为{64, 52, 38, 246, 32, 236, 17, 236, 17, 167, 12, 73, 145, 3, 124, 135, 248, 0, 32, 209, 179, 251, 124, 124, 200, 134}。生成的带纠错码的秘密序列SN为{25, 0, 130, 226, 33, 55, 111}。隐藏QR码数据码为{28, 52, 198, 246, 32, 236, 179, 236, 17, 167, 12, 73, 145, 3, 124, 129, 248, 0, 32, 209, 179, 40, 177, 124, 137, 72}，其中下划线数据为隐藏的数据块。

图3(c)为Tom的秘密份额(3,3),用户秘钥为123456，掩码类型为4。根据信息隐藏步骤，生成的位置序列LN为{ (3, 3), (8, 6), (4, 7), (16, 4), (6, 3), (6, 0), (16, 1), (0, 7), (16, 5), (19, 4), (19, 6), (8, 7), (0, 0), (0, 2), (19, 1), (23, 0), (6, 4), (6, 6), (23, 4), (16, 3), (0, 5), (4, 6), (19, 3), (6, 7), (3, 6), (8, 2), (23, 3), (6, 1), (8, 0), (4, 2), (19, 2), (0, 3), (19, 5), (19, 0), (23, 6), (16, 2), (3, 2), (3, 5), (4, 4), (19, 7), (4, 3), (3, 7), (6, 5), (8, 4), (8, 1), (23, 5), (0, 6), (23, 2), (4, 1), (16, 0), (8, 3), (23, 7), (4, 5), (8, 5), (0, 1), (4, 0), (23, 1), (16, 6), (3, 0), (0, 4), (3, 4), (3, 1), (6, 2), (16, 7)}。生成的数据码MQR为{64, 53, 70, 246, 208, 236, 17, 236, 17, 1, 43, 123, 49, 5, 31, 241, 110, 193, 0, 1, 153, 226, 212, 17, 232, 102}。生成的带纠错码的秘密序列SN为{25, 1, 157, 36, 30, 164, 27}。生成的隐藏QR码数据码为{69, 53, 70, 228, 190, 236, 29, 236, 0, 1, 43, 123, 49, 5, 31, 241, 58, 193, 0, 0, 153, 226, 212, 149, 232, 102}，其中下划线数据为隐藏的数据块。

图3(d)为Jack的秘密份额(4,12),用户秘钥为1q2w3e4r,掩码类型为0。根据信息隐藏步骤，生成的位置序列LN为{(6, 1), (20, 7), (20, 3), (11, 1), (22, 4), (11, 7), (12, 6), (9, 0), (9, 1), (18, 0), (20, 1), (22, 0), (12, 3), (11, 3), (12, 5), (9, 5), (16, 7), (20, 0), (16, 5), (18, 5), (6, 4), (18, 4), (16, 1), (22, 6), (16, 2), (20, 2), (18, 3), (22, 3), (16, 0), (22, 7), (9, 7), (6, 6), (6, 0), (11, 6), (16, 6), (18, 6), (6, 5), (9, 4), (11, 0), (22, 1), (12, 0), (20, 6), (9, 6), (18, 1), (20, 5), (11, 2), (6, 3), (9, 3), (11, 4), (12, 7), (20, 4), (12, 1), (22, 5), (22, 2), (12, 2), (9, 2), (12, 4), (16, 4), (16, 3), (6, 2), (6, 7), (18, 7), (18, 2), (11, 5)}。生成的数据码MQR为{64, 68, 166, 22, 54, 176, 236, 17, 236, 76, 220, 200, 18, 29, 214, 39, 239, 223, 220, 24, 71, 225, 7, 229, 239, 218}。生成的带纠错码的秘密序列SN为{24, 153, 0, 113, 88, 42, 137, 11}。生成的隐藏QR码数据码为{64, 68, 166, 22, 54, 176, 23, 17, 236, 102, 220, 78, 16, 29, 214, 39, 0, 223, 50, 24, 36, 225, 156, 229, 239, 218}，其中下划线数据为隐藏的数据块。

通过信息隐藏，将秘密份额隐藏在各个QR码中。经过隐藏后的QR码如图4所示。

图4 隐藏后的QR码

图3(a)隐藏后的QR码如图4(a)所示，掩码类型为5，因为隐藏后构造QR码的掩码类型并未发生变化，所以QR码整体变化很小。图3(b)隐藏后的QR码如图4(b)所示，隐藏后掩码类型为7，原始QR码掩码类型为3，掩码类型发生改变，QR码整体变化大。图3(c)隐藏后的QR码如图4(c)所示，隐藏后掩码类型为7，原始QR码掩码类型为4，掩码类型发生改变，QR码整体变化大。图3(d)隐藏后的QR码如图4(d)所示，隐藏后掩码类型为2，原始QR码掩码类型为0，掩码类型发生改变，QR码整体变化大。

以上QR码使用扫描器均可正常读取封面信息，通过隐藏信息的恢复步骤可以读取隐藏信息。任意选取其中3个QR码输入各自用户秘钥后即可恢复秘密，如图5所示。

图5 秘密恢复

实例仿真结果表明，秘密信息可以被正确的扫码读取，并通过秘密共享步骤进行恢复，证明了方案的可行性。

3.2 相关方案比较

将本文方案分别与文献[7-15]方案进行应用领域、作用域、是否对QR码进行操作、计算复杂度和能否抵抗篡改等5个方面进行对比，结果如表2 所示。

表2 相关方案比较

由表2可以看出，文献[7-10]方案的应用领域为图像隐藏，计算复杂度高，且秘密存储容量等于隐藏QR码的图片的大小。文献[11-14]方案的应用领域为水印技术，作用域为频域，计算复杂度高，且最大数据容量取决于QR码图像的大小。文献方案[7-14]均不能直接修改QR码模块。文献[15-16]方案的应用领域为秘密共享，文献[15]仅利用了QR码作为介质，安全性很低。文献[16]使用信息隐藏方案，但是存在大量矩阵运算，计算复杂度高，并且根据秘密长短改变隐藏块数量，在隐藏秘密很短并被攻击者了解存在隐藏的情况下安全性无法达到理想状态。而本文方案应用领域为利用信息隐藏的秘密共享，通过秘钥直接得到位置信息序列，再通过位置序列直接嵌入秘密信息。秘密恢复时通过位置序列直接读取对应位置信息。因此，计算复杂度低，仅与随机位置序列的生成有关。直接利用QR码版本和纠错等级对应的最大纠错能力数量的块，不会因为隐藏秘密的长短而损失安全性。在隐藏的秘密信息中加入纠错机制可有效预防隐藏QR码被恶意损坏或篡改造成的隐藏信息丢失，无法恢复等问题。

4 结语

利用QR码的纠错特征，使用用户设置秘钥控制，通过伪随机发生器，设计了直接修改QR码编码模块信息的秘密隐藏方案。该方案可读性强，且秘密容量可调节，实现了信息的隐藏及秘密共享应用。实例仿真结果表明，该方案可以正常读取QR码封面信息，并且仅在拥有用户密钥时可以正常读取QR码中的隐藏信息。与其他相关方案比较，本方案计算复杂度低，可以有效预防隐藏QR码被恶意损坏或篡改造成的隐藏信息丢失、无法恢复等问题。