基于防重复嵌入双水印的DEM完整性认证算法

许 惠，任 娜，朱 长 青

(南京师范大学虚拟地理环境教育部重点实验室,江苏 南京 210023;江苏省地理信息资源开发与利用协同创新中心,江苏 南京210023)

基于防重复嵌入双水印的DEM完整性认证算法

许 惠，任 娜*，朱 长 青

(南京师范大学虚拟地理环境教育部重点实验室,江苏 南京 210023;江苏省地理信息资源开发与利用协同创新中心,江苏 南京210023)

针对脆弱水印无法证明自身存在性的问题以及为防止通过先篡改再嵌入水印的篡改抵赖行为，提出一种基于防重复嵌入双水印的DEM完整性认证算法。该算法在水印嵌入前加入鲁棒水印预检测机制，若检测到数据含有鲁棒水印则无法继续对数据进行任何水印嵌入操作；若无，则根据DEM数据特征将载体数据划分为特征区域和非特征区域两部分。其中，特征区域用于嵌入鲁棒水印，由该部分数据生成的脆弱水印嵌入至数据的非特征区域。在水印检测时，首先检测鲁棒水印的存在性，若无则直接判断水印被破坏，说明数据不完整，若存在则继续检测脆弱水印的完整性，根据脆弱水印的检测结果进一步判断数据的完整性。实验结果表明，该算法能够有效防止水印的重复嵌入，同时完整性认证准确性良好。

数字高程模型；双水印；完整性认证；防重复嵌入

0 引言

在信息技术迅速发展的大背景下，地理数据的经济和社会效益得到越来越多的关注和重视，数据的可靠性及完整性问题已然成为一个热门的研究课题。脆弱水印作为一种先进的数据完整性认证技术手段，目前已有众多学者对其在地理数据完整性认证方面的应用进行了深入研究，但主要集中在矢量和遥感影像数据[1-11]，针对DEM数据完整性认证的脆弱水印算法则鲜少见刊。

将脆弱水印技术应用于矢量地理数据的完整性认证首见于1993年Cox所发表的文章[1]，但算法抗攻击性较弱；为增强水印算法的抗攻击能力，任娜等[2]通过建立数据点之间的空间位置关系实现了能够抗要素删除的矢量地理数据脆弱水印算法。通过对数据分组、分段能够更加精确地定位篡改，郑良斌等[3,4]将矢量数据进行分块，并由对应的Hash值生成脆弱水印序列，嵌入到各分块压缩后的冗余空间中再整体替换原始序列，检测时比较生成和提取的Hash序列即可判断数据的完整性；李莎莎等[5]首先对数据进行分组，然后利用混沌系统生成脆弱水印信息嵌入到矢量数据的LSB中，有效增强了算法的安全性。王奇胜等[6]将基于数据点生成的脆弱水印信息嵌入到数据的坐标上，将鲁棒水印信息嵌入到数据的坐标上，在数据更新和数据拼接等含有版权水印信息较少的情形中有效提高了水印检测结果的可靠性和准确性。在遥感影像数据脆弱水印方面，Qin等[7]使用小波分析提出了一种基于边缘特征的遥感影像数据的完整性认证算法；丁凯孟等[8]运用感知哈希实现了同样基于边缘特征的认证算法，通过对遥感影像进行格网划分、提取单元格边缘特征、用Hash函数对边缘矩阵奇异值进行归一化得到影像的感知哈希散列，比较接收与提取的感知哈希散列完成对影像数据的完整性认证；Caldelli等[9]、Ho等[10]、易小伟等[11]分别提出了基于JPEG-LS压缩标准、固定正弦变换和图像压缩码流的卫星遥感影像完整性认证算法。

以上基于脆弱水印的完整性认证方法主要侧重于增强算法的抗攻击能力、提高篡改定位的精度和认证的准确性，且均以待检测数据已嵌入过脆弱水印为前提，在无法得知待检测数据是否含有脆弱水印时，存在将未嵌入水印的数据和嵌入水印后遭受篡改的数据均认定为认证不通过而无法区分的问题。另一方面，在实际应用中，由于DEM数据生产者和使用者两相分离，别有用心者可以通过先篡改含有脆弱水印的DEM数据，然后再次嵌入相同脆弱水印的方式抵赖其篡改行为，则使得对数据完整性认证的准确性大打折扣。

因此，本文针对DEM的数据特征，设计了一种能够防止重复嵌入的鲁棒与脆弱双水印的完整性认证算法，能够更加有效地认证DEM数据的完整性，并防止通过重复嵌入脆弱水印带来的篡改抵赖行为。

1 算法思想

本文所提出的防重复双水印算法是指对数据同时嵌入具有强鲁棒性的鲁棒水印和较优脆弱性的脆弱水印相结合的水印算法，其中，鲁棒水印用来解决水印的防重复嵌入问题，脆弱水印用来解决数据的完整性认证问题，两者相得益彰。具体来说即为：一方面，在向载体数据中嵌入脆弱水印之前，首先检测该数据是否已含有鲁棒水印，若无则依次嵌入鲁棒和脆弱水印，若有则不再允许嵌入任何水印信息，保证数据能且只能被嵌入一次水印，达到防重复嵌入的目的；另一方面，脆弱水印的存在性可由鲁棒水印间接证明，两者同时嵌入，因此还可以增强脆弱水印完整性认证结果的可靠性。

综上，可对所提出的防重复嵌入双水印的算法思路进行如下描述：水印嵌入时，利用鲁棒水印的鲁棒性，首先向数据中嵌入鲁棒水印作为载体数据已嵌入过水印的标记，当尝试再次向含水印的数据中嵌入水印时，首先检测出数据中鲁棒水印的存在与否，已存在鲁棒水印则无法再次嵌入任何水印信息，从而达到防重复嵌入的效果；然后在鲁棒水印的基础上嵌入脆弱水印。水印检测时，依次检测鲁棒水印的存在性和脆弱水印的完整性，结合两者检测结果，综合判断数据的完整性。

2 算法设计与实现

2.1 水印信息生成与嵌入

水印的生成与嵌入分为脆弱水印和鲁棒水印的生成与嵌入两部分。其中，鲁棒水印选用文献[12]中基于映射和量化机制的DEM鲁棒水印算法，并在此基础上进行调整和改进。该算法不仅对各种针对DEM数据的攻击具有强鲁棒性，而且能够很好地控制水印误差，已得到了广泛应用。脆弱水印使用MD5 Hash算法生成基于原始数据内容的脆弱水印信息，其对输入的高敏感性、良好的单向性(不可逆性)和抗碰撞性的特点能够有效增强算法的安全性。

根据前文分析可知，本算法水印嵌入的顺序为先嵌入鲁棒水印后嵌入脆弱水印，且水印嵌入前采取了鲁棒水印预检测的机制。算法的具体步骤如下：

(1)提取地形特征点。使用D8算法提取待嵌入水印DEM数据S的地形特征点，得到数据的特征区域S1和非特征区域S2，两者符合如下关系式：

(1)

(2)检测鲁棒水印。由步骤(1)得到待嵌入水印DEM数据的特征区域，从该区域中检测鲁棒水印(具体检测步骤见2.2节)，若不存在鲁棒水印说明数据是还未嵌入水印的原始数据，跳至步骤(3)；若已存在鲁棒水印则跳至步骤(5)，不再对该数据进行任何水印嵌入操作，从而可以有效防止水印的重复嵌入。

(3)嵌入鲁棒水印。对还未嵌入任何水印的原始DEM数据，使用映射机制由数据的特征区域S1生成鲁棒水印W_R；然后将鲁棒水印信息W_R量化嵌入到数据的特征区域S1中，完成鲁棒水印的嵌入：

(2)

其中，⊕表示鲁棒水印嵌入规则。

(3)

提取DEM数据的非特征区域S2：

S2={S2i,i=1,2,…,64;S2i∈{0,1}}

(4)

2.2 水印检测与完整性认证

水印信息的检测是水印信息嵌入的逆过程。水印检测和完整性认证同样包括两部分，分别是用于证明水印存在性的鲁棒水印检测和用于完整性认证的脆弱水印检测。算法的具体步骤如下：

(2)鲁棒水印检测。首先，按照鲁棒水印嵌入的逆过程提取鲁棒水印信息W_R′；然后，由于本算法中水印信息无意义，故再次生成原始的鲁棒水印信息W_R，计算其与提取出的鲁棒水印信息W_R′之间的相关性，相关性检测公式如式(5)所示[12]。

(5)

若相关系数小于阈值0.5,说明待检测数据中不含鲁棒水印，可直接判断认证不通过；若相关系数大于阈值0.5,则跳至步骤(3)，进一步检测数据中脆弱水印的完整性。

3 实验与分析

对本文提出的算法进行验证，实验数据为一幅大小为509×515、分辨率为5 m、比例尺为1∶1万、浮点型的栅格DEM数据(图1)。从图1可以看出，主观视觉上很难察觉出载体DEM数据在水印嵌入前后的差异，说明本文算法嵌入双水印后具有好的不可感知性。

图1 嵌入水印前与嵌入水印后的DEM数据

Fig.1 The original and watermarked DEM data

图2给出了水印嵌入前后的实验数据在Matlab中的三维可视化效果图(以数据图像的灰度值为纵坐标填充高程值)。由图2可观察到，从主观视觉上，嵌入水印前后对DEM三维可视化效果几乎没有差别。计算嵌入前后两幅DEM数据的PSNR值为51.071，高于人眼可识别差异PSNR值范围(35～40)。由此可见，本文算法实现了水印嵌入的不可见性要求。

图2 原始DEM与含水印DEM的三维可视化效果

Fig.2 The 3D visualization renderings of the original and watermarked DEM

3.1 认证准确性与防重复嵌入实验分析

针对DEM数据的一些常见修改操作，使用本文所提出的防重复嵌入双水印算法进行完整性认证和防重复嵌入实验，嵌入水印并经修改的实验数据如表1所示。对表1中经不同篡改的含水印DEM数据进行完整性认证与防重复嵌入检测实验，结果如表2所示。从表2可以看出：1)经过一些常见攻击后，提取的鲁棒水印的相关系数均大于设置的阈值0.5，表明本文算法的鲁棒水印对一定强度的攻击具有较强的鲁棒性；2)数据修改后，能够有效鉴别出数据篡改，认证数据的完整性，表明本文算法的脆弱水印具有好的脆弱性；3)从防重复嵌入结果来看，本文算法嵌入水印后不可重复嵌入水印，说明算法能够很好地防止水印的重复嵌入，与理论分析结果保持一致。

3.2 水印嵌入精度影响分析

(1)数据精度影响分析。表3显示了水印嵌入前后DEM数据的高程最大/小值、平均高程值及高程标准差的统计结果。由表3可知，水印嵌入前后，DEM数据高程最小值没有变化，高程最大值、平均高程值和高程标准差变化均为0.01 m，变化幅度较小。如此表明，水印的嵌入所带来的数据误差较小，对DEM数据统计学精度影响较小。

(2)应用精度影响分析。数据应用精度是评价DEM数据的另一重要指标，此处选取等高线和汇水线分析本文算法对DEM数据应用精度的影响，分别如图3和图4所示。从图3 和图4可以看出，从原始DEM和含水印DEM数据中提取出的等高线与汇水线吻合程度较高，本文算法水印的嵌入对DEM等高线与汇水线提取影响不大，能够满足DEM数据在等高线与汇水线提取方面的应用精度需求。

表1 不同篡改方式下的含水印DEM数据

Table 1 The watermarked DEM data under different modify ways

DEM数据晕渲效果图

表2 认证准确性与防重复嵌入实验结果

Table 2 The experimental results of certification accuracy and preventing re-embedding analysis

DEM数据编号修改方式鲁棒水印相关系数认证结果防重复嵌入结果结果准确性图1b不做修改0.978通过不可重复嵌入正确表1a高程平移(h+9)0.803不通过不可重复嵌入正确表1b高程缩放(h*10)0.796不通过不可重复嵌入正确表1c随机噪声[-5,5]0.555不通过不可重复嵌入正确表1d数据删除(5%)0.765不通过不可重复嵌入正确表1e数据裁剪(25%)0.778不通过不可重复嵌入正确表1f部分替换(25%)0.815不通过不可重复嵌入正确

表3 水印嵌入前后DEM数据基本统计信息

Table 3 The basic statistical information of the original and watermarked DEM m

高程最小值高程最大值平均高程值标准差原始DEM894.561106.71993.8140.74含水印DEM894.561106.70993.8040.73

4 结语

本文针对DEM数据的地形特征，结合鲁棒水印与脆弱水印各自的优点，设计了一种能够防止重复嵌入的双水印完整性认证算法,利用具有强鲁棒性的鲁棒水印间接证明脆弱水印的存在性，提高了完整性认证结果的可靠性；同时，在脆弱水印嵌入前采取的鲁棒水印预检测机制实现了水印的防重复嵌入，有效避免了通过先篡改再嵌入脆弱水印的篡改抵赖行为。对算法完整性认证和防重复嵌入两方面的实验分析结果表明，该算法能够准确认证DEM数据的完整性并能有效防止水印的重复嵌入，且算法引起误差较小、性能较优。

图3 原始DEM与含水印DEM提取等高线结果对比

Fig.3 The comparison of extracted contours of the original and watermarked DEM

图4 原始DEM与含水印DEM提取汇水线结果对比

Fig.4 The comparison of extracted stream networks of the original and watermarked DEM

[1] COX G S,DE JAGER G.A survey of point pattern matching techniques and a new approach to point pattern recognition[A].Proc.of South African Symposium on Communications and Signal Processing[C].1993.243-248.

[2] 任娜,吴维,朱长青.一种点约束分块的矢量地理数据精确认证算法[J].地球信息科学学报,2015,17(2):166-171.

[3] 郑良斌,贾玉禄,王群.用于矢量地图完整性验证的脆弱数字水印算法[J].计算机工程与应用,2010,46(26):99-101.

[4] ZHENG L,YOU F.A Fragile digital watermark used to verify the integrity of vector map[A].E-Business and Information System Security,EBISS′09[C].International Conference on.IEEE,2009.1-4.

[5] 李莎莎,王海荣,周卫,等.基于易碎水印的GIS矢量数据完整性认证方法[J].测绘通报,2013(11):101-105.

[6] 王奇胜,朱长青,符浩军.利用数据点定位的矢量地理数据数字水印算法[J].测绘学报,2013,42(2):310-316.

[7] QIN Q,WANG W,CHEN S,et al.Research of digital semi-fragile watermarking of remote sensing image based on wavelet analysis[A].IGARSS′04.2004 IEEE International Conference on Geoscience and Remote Sensing Symposium[C].2004,4:2542-2545.

[8] 丁凯孟,朱长青.一种用于遥感影像完整性认证的感知哈希算法[J].东南大学学报(自然科学版),2014,44(4):723-727.

[9] CALDELLI R,MACALUSO G,BARNI M,et al.Joint near-lossless watermarking and compression for the authentication of remote sensing images[A].IGARSS′04.2004 IEEE International Conference on Geoscience and Remote Sensing Symposium[C].2004,1:297-300.

[10] HO A T S,ZHU X,WOON W M.A semi-fragile pinned sine transform watermarking system for content authentication of satellite images[A].IGARSS′05.2005 IEEE International Conference on Geoscience and Remote Sensing Symposium[C].2005,2:737-740.

[11] 易小伟,马恒太,郑昌文,等.基于有向图构造的卫星遥感图像认证算法[J].宇航学报,2014,35(5):581-589.

[12] 王志伟.DEM数字水印模型与算法研究[D].郑州:解放军信息工程大学,2011.

An Integrity Authentication Algorithm for DEM Based on the Preventing Re-embedded Double Watermarking

XU Hui,REN Na,ZHU Chang-qing

(Key Laboratory of Virtual Geographic Environment of Ministry of Education,Nanjing Normal University,Nanjing 210023;2.Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application,Nanjing 210023,China)

In this paper,a double watermarking based integrity authentication algorithm is proposed to prevent watermark being embedded repeatedly.The aim is to solve the problem that fragile watermarking cannot prove the existence of itself,and prevent the tampering repudiation behavior by tampering the watermarked data first and then embedding the same watermarking information again.The pre-detection mechanism of robust watermarking is performed before the watermarking is embedded,so that any kind of watermarking cannot be embedded if the robust watermarking is already detected in the carrier data.Otherwise,the carrier data was divided into two parts according to the data features,namely the feature region and the non-feature region.The feature region is used to embed robust watermarking and generate the fragile watermarking,which will be embedded into the non-feature region.During the watermarking detection,the existence of the robust watermarking is detected at first.If there is no the robust watermarking,it shows the watermarking is destroyed and the data is incomplete.Otherwise,the integrity of the fragile watermarking will be detected.The integrity of the data will be further determined by the detecting result of fragile watermarking.The experimental results show that the proposed algorithm is able to prevent the watermarking being embedded repeatedly and has good performance for the integrity certification.

digital elevation model;double watermarking;integrity authentication;preventing re-embedded

2015-06-15；

2015-12-21

国家社科基金重大项目(11&ZD162)；国家自然科学基金青年项目(41301413)；江苏省自然科学基金青年项目(BK20130903);国家测绘地理信息公益性行业科研专项(201512021、201512019)

许惠(1991-)，女，硕士研究生，研究方向为空间数据安全。*通讯作者E-mail:renna1026@163.com

10.3969/j.issn.1672-0504.2016.01.007

P208

A

1672-0504(2016)01-0034-05