許 惠，任 娜，朱 長(zhǎng) 青

(南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室,江蘇 南京 210023;江蘇省地理信息資源開(kāi)發(fā)與利用協(xié)同創(chuàng)新中心,江蘇 南京210023)

基于防重復(fù)嵌入雙水印的DEM完整性認(rèn)證算法

許 惠，任 娜*，朱 長(zhǎng) 青

(南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室,江蘇 南京 210023;江蘇省地理信息資源開(kāi)發(fā)與利用協(xié)同創(chuàng)新中心,江蘇 南京210023)

針對(duì)脆弱水印無(wú)法證明自身存在性的問(wèn)題以及為防止通過(guò)先篡改再嵌入水印的篡改抵賴行為，提出一種基于防重復(fù)嵌入雙水印的DEM完整性認(rèn)證算法。該算法在水印嵌入前加入魯棒水印預(yù)檢測(cè)機(jī)制，若檢測(cè)到數(shù)據(jù)含有魯棒水印則無(wú)法繼續(xù)對(duì)數(shù)據(jù)進(jìn)行任何水印嵌入操作；若無(wú)，則根據(jù)DEM數(shù)據(jù)特征將載體數(shù)據(jù)劃分為特征區(qū)域和非特征區(qū)域兩部分。其中，特征區(qū)域用于嵌入魯棒水印，由該部分?jǐn)?shù)據(jù)生成的脆弱水印嵌入至數(shù)據(jù)的非特征區(qū)域。在水印檢測(cè)時(shí)，首先檢測(cè)魯棒水印的存在性，若無(wú)則直接判斷水印被破壞，說(shuō)明數(shù)據(jù)不完整，若存在則繼續(xù)檢測(cè)脆弱水印的完整性，根據(jù)脆弱水印的檢測(cè)結(jié)果進(jìn)一步判斷數(shù)據(jù)的完整性。實(shí)驗(yàn)結(jié)果表明，該算法能夠有效防止水印的重復(fù)嵌入，同時(shí)完整性認(rèn)證準(zhǔn)確性良好。

數(shù)字高程模型；雙水印；完整性認(rèn)證；防重復(fù)嵌入

0 引言

在信息技術(shù)迅速發(fā)展的大背景下，地理數(shù)據(jù)的經(jīng)濟(jì)和社會(huì)效益得到越來(lái)越多的關(guān)注和重視，數(shù)據(jù)的可靠性及完整性問(wèn)題已然成為一個(gè)熱門的研究課題。脆弱水印作為一種先進(jìn)的數(shù)據(jù)完整性認(rèn)證技術(shù)手段，目前已有眾多學(xué)者對(duì)其在地理數(shù)據(jù)完整性認(rèn)證方面的應(yīng)用進(jìn)行了深入研究，但主要集中在矢量和遙感影像數(shù)據(jù)[1-11]，針對(duì)DEM數(shù)據(jù)完整性認(rèn)證的脆弱水印算法則鮮少見(jiàn)刊。

將脆弱水印技術(shù)應(yīng)用于矢量地理數(shù)據(jù)的完整性認(rèn)證首見(jiàn)于1993年Cox所發(fā)表的文章[1]，但算法抗攻擊性較弱；為增強(qiáng)水印算法的抗攻擊能力，任娜等[2]通過(guò)建立數(shù)據(jù)點(diǎn)之間的空間位置關(guān)系實(shí)現(xiàn)了能夠抗要素刪除的矢量地理數(shù)據(jù)脆弱水印算法。通過(guò)對(duì)數(shù)據(jù)分組、分段能夠更加精確地定位篡改，鄭良斌等[3,4]將矢量數(shù)據(jù)進(jìn)行分塊，并由對(duì)應(yīng)的Hash值生成脆弱水印序列，嵌入到各分塊壓縮后的冗余空間中再整體替換原始序列，檢測(cè)時(shí)比較生成和提取的Hash序列即可判斷數(shù)據(jù)的完整性；李莎莎等[5]首先對(duì)數(shù)據(jù)進(jìn)行分組，然后利用混沌系統(tǒng)生成脆弱水印信息嵌入到矢量數(shù)據(jù)的LSB中，有效增強(qiáng)了算法的安全性。王奇勝等[6]將基于數(shù)據(jù)點(diǎn)生成的脆弱水印信息嵌入到數(shù)據(jù)的坐標(biāo)上，將魯棒水印信息嵌入到數(shù)據(jù)的坐標(biāo)上，在數(shù)據(jù)更新和數(shù)據(jù)拼接等含有版權(quán)水印信息較少的情形中有效提高了水印檢測(cè)結(jié)果的可靠性和準(zhǔn)確性。在遙感影像數(shù)據(jù)脆弱水印方面，Qin等[7]使用小波分析提出了一種基于邊緣特征的遙感影像數(shù)據(jù)的完整性認(rèn)證算法；丁凱孟等[8]運(yùn)用感知哈希實(shí)現(xiàn)了同樣基于邊緣特征的認(rèn)證算法，通過(guò)對(duì)遙感影像進(jìn)行格網(wǎng)劃分、提取單元格邊緣特征、用Hash函數(shù)對(duì)邊緣矩陣奇異值進(jìn)行歸一化得到影像的感知哈希散列，比較接收與提取的感知哈希散列完成對(duì)影像數(shù)據(jù)的完整性認(rèn)證；Caldelli等[9]、Ho等[10]、易小偉等[11]分別提出了基于JPEG-LS壓縮標(biāo)準(zhǔn)、固定正弦變換和圖像壓縮碼流的衛(wèi)星遙感影像完整性認(rèn)證算法。

以上基于脆弱水印的完整性認(rèn)證方法主要側(cè)重于增強(qiáng)算法的抗攻擊能力、提高篡改定位的精度和認(rèn)證的準(zhǔn)確性，且均以待檢測(cè)數(shù)據(jù)已嵌入過(guò)脆弱水印為前提，在無(wú)法得知待檢測(cè)數(shù)據(jù)是否含有脆弱水印時(shí)，存在將未嵌入水印的數(shù)據(jù)和嵌入水印后遭受篡改的數(shù)據(jù)均認(rèn)定為認(rèn)證不通過(guò)而無(wú)法區(qū)分的問(wèn)題。另一方面，在實(shí)際應(yīng)用中，由于DEM數(shù)據(jù)生產(chǎn)者和使用者兩相分離，別有用心者可以通過(guò)先篡改含有脆弱水印的DEM數(shù)據(jù)，然后再次嵌入相同脆弱水印的方式抵賴其篡改行為，則使得對(duì)數(shù)據(jù)完整性認(rèn)證的準(zhǔn)確性大打折扣。

因此，本文針對(duì)DEM的數(shù)據(jù)特征，設(shè)計(jì)了一種能夠防止重復(fù)嵌入的魯棒與脆弱雙水印的完整性認(rèn)證算法，能夠更加有效地認(rèn)證DEM數(shù)據(jù)的完整性，并防止通過(guò)重復(fù)嵌入脆弱水印帶來(lái)的篡改抵賴行為。

1 算法思想

本文所提出的防重復(fù)雙水印算法是指對(duì)數(shù)據(jù)同時(shí)嵌入具有強(qiáng)魯棒性的魯棒水印和較優(yōu)脆弱性的脆弱水印相結(jié)合的水印算法，其中，魯棒水印用來(lái)解決水印的防重復(fù)嵌入問(wèn)題，脆弱水印用來(lái)解決數(shù)據(jù)的完整性認(rèn)證問(wèn)題，兩者相得益彰。具體來(lái)說(shuō)即為：一方面，在向載體數(shù)據(jù)中嵌入脆弱水印之前，首先檢測(cè)該數(shù)據(jù)是否已含有魯棒水印，若無(wú)則依次嵌入魯棒和脆弱水印，若有則不再允許嵌入任何水印信息，保證數(shù)據(jù)能且只能被嵌入一次水印，達(dá)到防重復(fù)嵌入的目的；另一方面，脆弱水印的存在性可由魯棒水印間接證明，兩者同時(shí)嵌入，因此還可以增強(qiáng)脆弱水印完整性認(rèn)證結(jié)果的可靠性。

綜上，可對(duì)所提出的防重復(fù)嵌入雙水印的算法思路進(jìn)行如下描述：水印嵌入時(shí)，利用魯棒水印的魯棒性，首先向數(shù)據(jù)中嵌入魯棒水印作為載體數(shù)據(jù)已嵌入過(guò)水印的標(biāo)記，當(dāng)嘗試再次向含水印的數(shù)據(jù)中嵌入水印時(shí)，首先檢測(cè)出數(shù)據(jù)中魯棒水印的存在與否，已存在魯棒水印則無(wú)法再次嵌入任何水印信息，從而達(dá)到防重復(fù)嵌入的效果；然后在魯棒水印的基礎(chǔ)上嵌入脆弱水印。水印檢測(cè)時(shí)，依次檢測(cè)魯棒水印的存在性和脆弱水印的完整性，結(jié)合兩者檢測(cè)結(jié)果，綜合判斷數(shù)據(jù)的完整性。

2 算法設(shè)計(jì)與實(shí)現(xiàn)

2.1 水印信息生成與嵌入

水印的生成與嵌入分為脆弱水印和魯棒水印的生成與嵌入兩部分。其中，魯棒水印選用文獻(xiàn)[12]中基于映射和量化機(jī)制的DEM魯棒水印算法，并在此基礎(chǔ)上進(jìn)行調(diào)整和改進(jìn)。該算法不僅對(duì)各種針對(duì)DEM數(shù)據(jù)的攻擊具有強(qiáng)魯棒性，而且能夠很好地控制水印誤差，已得到了廣泛應(yīng)用。脆弱水印使用MD5 Hash算法生成基于原始數(shù)據(jù)內(nèi)容的脆弱水印信息，其對(duì)輸入的高敏感性、良好的單向性(不可逆性)和抗碰撞性的特點(diǎn)能夠有效增強(qiáng)算法的安全性。

根據(jù)前文分析可知，本算法水印嵌入的順序?yàn)橄惹度媵敯羲『笄度氪嗳跛?，且水印嵌入前采取了魯棒水印預(yù)檢測(cè)的機(jī)制。算法的具體步驟如下：

(1)提取地形特征點(diǎn)。使用D8算法提取待嵌入水印DEM數(shù)據(jù)S的地形特征點(diǎn)，得到數(shù)據(jù)的特征區(qū)域S1和非特征區(qū)域S2，兩者符合如下關(guān)系式：

(1)

(2)檢測(cè)魯棒水印。由步驟(1)得到待嵌入水印DEM數(shù)據(jù)的特征區(qū)域，從該區(qū)域中檢測(cè)魯棒水印(具體檢測(cè)步驟見(jiàn)2.2節(jié))，若不存在魯棒水印說(shuō)明數(shù)據(jù)是還未嵌入水印的原始數(shù)據(jù)，跳至步驟(3)；若已存在魯棒水印則跳至步驟(5)，不再對(duì)該數(shù)據(jù)進(jìn)行任何水印嵌入操作，從而可以有效防止水印的重復(fù)嵌入。

(3)嵌入魯棒水印。對(duì)還未嵌入任何水印的原始DEM數(shù)據(jù)，使用映射機(jī)制由數(shù)據(jù)的特征區(qū)域S1生成魯棒水印W_R；然后將魯棒水印信息W_R量化嵌入到數(shù)據(jù)的特征區(qū)域S1中，完成魯棒水印的嵌入：

(2)

其中，⊕表示魯棒水印嵌入規(guī)則。

(3)

提取DEM數(shù)據(jù)的非特征區(qū)域S2：

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

(4)

2.2 水印檢測(cè)與完整性認(rèn)證

水印信息的檢測(cè)是水印信息嵌入的逆過(guò)程。水印檢測(cè)和完整性認(rèn)證同樣包括兩部分，分別是用于證明水印存在性的魯棒水印檢測(cè)和用于完整性認(rèn)證的脆弱水印檢測(cè)。算法的具體步驟如下：

(2)魯棒水印檢測(cè)。首先，按照魯棒水印嵌入的逆過(guò)程提取魯棒水印信息W_R′；然后，由于本算法中水印信息無(wú)意義，故再次生成原始的魯棒水印信息W_R，計(jì)算其與提取出的魯棒水印信息W_R′之間的相關(guān)性，相關(guān)性檢測(cè)公式如式(5)所示[12]。

(5)

若相關(guān)系數(shù)小于閾值0.5,說(shuō)明待檢測(cè)數(shù)據(jù)中不含魯棒水印，可直接判斷認(rèn)證不通過(guò)；若相關(guān)系數(shù)大于閾值0.5,則跳至步驟(3)，進(jìn)一步檢測(cè)數(shù)據(jù)中脆弱水印的完整性。

3 實(shí)驗(yàn)與分析

對(duì)本文提出的算法進(jìn)行驗(yàn)證，實(shí)驗(yàn)數(shù)據(jù)為一幅大小為509×515、分辨率為5 m、比例尺為1∶1萬(wàn)、浮點(diǎn)型的柵格DEM數(shù)據(jù)(圖1)。從圖1可以看出，主觀視覺(jué)上很難察覺(jué)出載體DEM數(shù)據(jù)在水印嵌入前后的差異，說(shuō)明本文算法嵌入雙水印后具有好的不可感知性。

圖1 嵌入水印前與嵌入水印后的DEM數(shù)據(jù)

Fig.1 The original and watermarked DEM data

圖2給出了水印嵌入前后的實(shí)驗(yàn)數(shù)據(jù)在Matlab中的三維可視化效果圖(以數(shù)據(jù)圖像的灰度值為縱坐標(biāo)填充高程值)。由圖2可觀察到，從主觀視覺(jué)上，嵌入水印前后對(duì)DEM三維可視化效果幾乎沒(méi)有差別。計(jì)算嵌入前后兩幅DEM數(shù)據(jù)的PSNR值為51.071，高于人眼可識(shí)別差異PSNR值范圍(35～40)。由此可見(jiàn)，本文算法實(shí)現(xiàn)了水印嵌入的不可見(jiàn)性要求。

圖2 原始DEM與含水印DEM的三維可視化效果

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

3.1 認(rèn)證準(zhǔn)確性與防重復(fù)嵌入實(shí)驗(yàn)分析

針對(duì)DEM數(shù)據(jù)的一些常見(jiàn)修改操作，使用本文所提出的防重復(fù)嵌入雙水印算法進(jìn)行完整性認(rèn)證和防重復(fù)嵌入實(shí)驗(yàn)，嵌入水印并經(jīng)修改的實(shí)驗(yàn)數(shù)據(jù)如表1所示。對(duì)表1中經(jīng)不同篡改的含水印DEM數(shù)據(jù)進(jìn)行完整性認(rèn)證與防重復(fù)嵌入檢測(cè)實(shí)驗(yàn)，結(jié)果如表2所示。從表2可以看出：1)經(jīng)過(guò)一些常見(jiàn)攻擊后，提取的魯棒水印的相關(guān)系數(shù)均大于設(shè)置的閾值0.5，表明本文算法的魯棒水印對(duì)一定強(qiáng)度的攻擊具有較強(qiáng)的魯棒性；2)數(shù)據(jù)修改后，能夠有效鑒別出數(shù)據(jù)篡改，認(rèn)證數(shù)據(jù)的完整性，表明本文算法的脆弱水印具有好的脆弱性；3)從防重復(fù)嵌入結(jié)果來(lái)看，本文算法嵌入水印后不可重復(fù)嵌入水印，說(shuō)明算法能夠很好地防止水印的重復(fù)嵌入，與理論分析結(jié)果保持一致。

3.2 水印嵌入精度影響分析

(1)數(shù)據(jù)精度影響分析。表3顯示了水印嵌入前后DEM數(shù)據(jù)的高程最大/小值、平均高程值及高程標(biāo)準(zhǔn)差的統(tǒng)計(jì)結(jié)果。由表3可知，水印嵌入前后，DEM數(shù)據(jù)高程最小值沒(méi)有變化，高程最大值、平均高程值和高程標(biāo)準(zhǔn)差變化均為0.01 m，變化幅度較小。如此表明，水印的嵌入所帶來(lái)的數(shù)據(jù)誤差較小，對(duì)DEM數(shù)據(jù)統(tǒng)計(jì)學(xué)精度影響較小。

(2)應(yīng)用精度影響分析。數(shù)據(jù)應(yīng)用精度是評(píng)價(jià)DEM數(shù)據(jù)的另一重要指標(biāo)，此處選取等高線和匯水線分析本文算法對(duì)DEM數(shù)據(jù)應(yīng)用精度的影響，分別如圖3和圖4所示。從圖3 和圖4可以看出，從原始DEM和含水印DEM數(shù)據(jù)中提取出的等高線與匯水線吻合程度較高，本文算法水印的嵌入對(duì)DEM等高線與匯水線提取影響不大，能夠滿足DEM數(shù)據(jù)在等高線與匯水線提取方面的應(yīng)用精度需求。

表1 不同篡改方式下的含水印DEM數(shù)據(jù)

Table 1 The watermarked DEM data under different modify ways

DEM數(shù)據(jù)暈渲效果圖

表2 認(rèn)證準(zhǔn)確性與防重復(fù)嵌入實(shí)驗(yàn)結(jié)果

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

DEM數(shù)據(jù)編號(hào)修改方式魯棒水印相關(guān)系數(shù)認(rèn)證結(jié)果防重復(fù)嵌入結(jié)果結(jié)果準(zhǔn)確性圖1b不做修改0.978通過(guò)不可重復(fù)嵌入正確表1a高程平移(h+9)0.803不通過(guò)不可重復(fù)嵌入正確表1b高程縮放(h*10)0.796不通過(guò)不可重復(fù)嵌入正確表1c隨機(jī)噪聲[-5,5]0.555不通過(guò)不可重復(fù)嵌入正確表1d數(shù)據(jù)刪除(5%)0.765不通過(guò)不可重復(fù)嵌入正確表1e數(shù)據(jù)裁剪(25%)0.778不通過(guò)不可重復(fù)嵌入正確表1f部分替換(25%)0.815不通過(guò)不可重復(fù)嵌入正確

表3 水印嵌入前后DEM數(shù)據(jù)基本統(tǒng)計(jì)信息

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

高程最小值高程最大值平均高程值標(biāo)準(zhǔn)差原始DEM894.561106.71993.8140.74含水印DEM894.561106.70993.8040.73

4 結(jié)語(yǔ)

本文針對(duì)DEM數(shù)據(jù)的地形特征，結(jié)合魯棒水印與脆弱水印各自的優(yōu)點(diǎn)，設(shè)計(jì)了一種能夠防止重復(fù)嵌入的雙水印完整性認(rèn)證算法,利用具有強(qiáng)魯棒性的魯棒水印間接證明脆弱水印的存在性，提高了完整性認(rèn)證結(jié)果的可靠性；同時(shí)，在脆弱水印嵌入前采取的魯棒水印預(yù)檢測(cè)機(jī)制實(shí)現(xiàn)了水印的防重復(fù)嵌入，有效避免了通過(guò)先篡改再嵌入脆弱水印的篡改抵賴行為。對(duì)算法完整性認(rèn)證和防重復(fù)嵌入兩方面的實(shí)驗(yàn)分析結(jié)果表明，該算法能夠準(zhǔn)確認(rèn)證DEM數(shù)據(jù)的完整性并能有效防止水印的重復(fù)嵌入，且算法引起誤差較小、性能較優(yōu)。

圖3 原始DEM與含水印DEM提取等高線結(jié)果對(duì)比

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

圖4 原始DEM與含水印DEM提取匯水線結(jié)果對(duì)比

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] 任娜,吳維,朱長(zhǎng)青.一種點(diǎn)約束分塊的矢量地理數(shù)據(jù)精確認(rèn)證算法[J].地球信息科學(xué)學(xué)報(bào),2015,17(2):166-171.

[3] 鄭良斌,賈玉祿,王群.用于矢量地圖完整性驗(yàn)證的脆弱數(shù)字水印算法[J].計(jì)算機(jī)工程與應(yīng)用,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] 李莎莎,王海榮,周衛(wèi),等.基于易碎水印的GIS矢量數(shù)據(jù)完整性認(rèn)證方法[J].測(cè)繪通報(bào),2013(11):101-105.

[6] 王奇勝,朱長(zhǎng)青,符浩軍.利用數(shù)據(jù)點(diǎn)定位的矢量地理數(shù)據(jù)數(shù)字水印算法[J].測(cè)繪學(xué)報(bào),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] 丁凱孟,朱長(zhǎng)青.一種用于遙感影像完整性認(rèn)證的感知哈希算法[J].東南大學(xué)學(xué)報(bào)(自然科學(xué)版),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] 易小偉,馬恒太,鄭昌文,等.基于有向圖構(gòu)造的衛(wèi)星遙感圖像認(rèn)證算法[J].宇航學(xué)報(bào),2014,35(5):581-589.

[12] 王志偉.DEM數(shù)字水印模型與算法研究[D].鄭州:解放軍信息工程大學(xué),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

國(guó)家社科基金重大項(xiàng)目(11&ZD162)；國(guó)家自然科學(xué)基金青年項(xiàng)目(41301413)；江蘇省自然科學(xué)基金青年項(xiàng)目(BK20130903);國(guó)家測(cè)繪地理信息公益性行業(yè)科研專項(xiàng)(201512021、201512019)

許惠(1991-)，女，碩士研究生，研究方向?yàn)榭臻g數(shù)據(jù)安全。*通訊作者E-mail:renna1026@163.com

10.3969/j.issn.1672-0504.2016.01.007

P208

A

1672-0504(2016)01-0034-05