基于三維混沌序列的DEM置亂與還原方法

仲浩宇，王中元，李安波,2,3

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

地理信息事關(guān)國家安全和社會(huì)利益，其安全防護(hù)是當(dāng)前地理信息行業(yè)亟待解決的難題[1]。隨著計(jì)算機(jī)網(wǎng)絡(luò)、云數(shù)據(jù)等技術(shù)的迅猛發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)陌踩珕栴}更是日益嚴(yán)峻。DEM數(shù)據(jù)作為國家空間數(shù)據(jù)基礎(chǔ)設(shè)施的重要內(nèi)容，一旦發(fā)生泄密事件，會(huì)帶來巨大的社會(huì)安全隱患和經(jīng)濟(jì)損失。因此，如何保障DEM數(shù)據(jù)在網(wǎng)絡(luò)傳輸時(shí)的安全性，是當(dāng)前需要解決的重要問題之一。

DEM數(shù)據(jù)的保護(hù)方式主要有數(shù)據(jù)加密[2]、數(shù)字水印[3]技術(shù)。其中，數(shù)據(jù)加密基于DEM數(shù)據(jù)的特征分為DEM數(shù)據(jù)偽裝[4]和DEM數(shù)據(jù)置亂。這兩種技術(shù)利用DEM所具有的空間和數(shù)值特征，實(shí)現(xiàn)DEM數(shù)據(jù)加密；數(shù)字水印技術(shù)雖然在DEM數(shù)據(jù)的版權(quán)保護(hù)和數(shù)據(jù)泄露溯源等方面應(yīng)用廣泛，但是DEM數(shù)據(jù)被竊取后仍可以繼續(xù)使用，沒有從根本上解決數(shù)據(jù)安全問題。

文獻(xiàn)[5]使用空間域生成的三維曲面與原始DEM數(shù)據(jù)進(jìn)行疊加，提出了一種基于模糊關(guān)系和帶參數(shù)曲面的DEM偽裝算法，具有一定的可逆性與高效性；文獻(xiàn)[6]將偽裝算法與數(shù)字水印技術(shù)相融合，實(shí)現(xiàn)了DEM數(shù)據(jù)偽裝。與數(shù)據(jù)加密、數(shù)字水印技術(shù)相比，DEM偽裝算法雖然具有一定優(yōu)勢(shì)，但也存在一定的不足。文獻(xiàn)[7]利用置亂原理有效改善了當(dāng)前DEM偽裝算法大量占用內(nèi)存空間、數(shù)據(jù)誤用等方面的問題，但是數(shù)據(jù)還原后仍存在一定的誤差。

綜上，本文擬基于三維混沌序列，在對(duì)DEM文件先后進(jìn)行高程置亂、位置置亂和文件頭置亂處理后，使置亂數(shù)據(jù)失去高程變化的空間連續(xù)性與數(shù)值連續(xù)性，實(shí)現(xiàn)置亂DEM數(shù)據(jù)的無損、盲式還原。

1 研究方法

DEM數(shù)據(jù)中每個(gè)柵格具有X坐標(biāo)、Y坐標(biāo)和高程3個(gè)基本屬性。DEM的總體置亂可以從高程和位置兩個(gè)方面進(jìn)行置亂。其中，高程置亂用于破壞DEM高程值的真實(shí)性；位置置亂用于破壞高程位置的連續(xù)性；其次，針對(duì)DEM中的3個(gè)基本屬性，基于三維混沌映射一致化進(jìn)行高程置亂和位置置亂，可提高算法處理效率和算法安全性；最后，加密DEM文件頭中的基礎(chǔ)信息，進(jìn)一步提高算法安全性(如圖1所示)。

1.1 三維混沌序列生成

混沌系統(tǒng)主要有一維Logistic映射[6]、二維Hénon映射[7]、三維Lorenz映射[8]和通過多個(gè)方程進(jìn)行升維的復(fù)合混沌系統(tǒng)。本文使用三維混沌映射生成混沌序列，三維混沌序列生成函數(shù)的定義為

(1)

式中，x0、y0、z0為混沌系統(tǒng)的初值，且x0∈(0,1),y0∈(0,1),z0∈(0,1)；x1、y1、z1和x2、y2、z2分別是根據(jù)初值和式(2)、式(3)計(jì)算出的迭代數(shù)值；xk、yk、zk和xk+1、yk+1、zk+1分別是迭代k次和k+1次后的數(shù)值；k為迭代次數(shù)，k>2；mod 1表示僅取數(shù)值的小數(shù)部分。

(2)

(3)

此三維混沌映射使用了類斐波那契數(shù)列的方式構(gòu)造基礎(chǔ)混沌序列，輸入?yún)?shù)的精度決定了混沌序列的復(fù)雜度。為此，建議使用小數(shù)位數(shù)為3以上的序列初值。首先輸入混沌序列m初始混沌參數(shù){x0,y0,z0,ρ,σ}，其中ρ∈[100,1000]內(nèi)的整數(shù)，定義為混沌序列截取長度，σ∈(0,1)為二值化序列閾值。然后計(jì)算初始參數(shù)x1,y1,z1,x2,y2,z2}，根據(jù)三維混沌方程(式(1))，生成長度為L1=(row+col+LH)的混沌序列X、Y、Z，其中row為行數(shù)，col為列數(shù)，LH為最大高程值轉(zhuǎn)為二進(jìn)制的位數(shù)(通常取14)。

初始混沌參數(shù){x,y,z,ρ,σ}是還原時(shí)重構(gòu)混沌序列的必要條件。這些參數(shù)作為本算法的還原密鑰，即使在算法已公開的情況下，如果密鑰未知，也無法還原秘密DEM數(shù)據(jù)，遵循算法的公開安全性原則。

1.2 高程置亂

高程置亂的具體處理流程如下：

(1) 將DEM數(shù)據(jù)存入大小為row×col的矩陣A中，對(duì)于浮點(diǎn)數(shù)型的高程值僅處理整數(shù)部分。

(2) 混沌序列Z的二值化處理。初始混沌序列{X,Y,Z}的數(shù)值均分布在[0,1]區(qū)間內(nèi)，通過混沌序列二值化，得到0、1序列。本文對(duì)序列Z使用式(4)進(jìn)行線性離散化，得到二值化序列Z′，即

(4)

(3) 柵格高程值Vmn的二進(jìn)制處理。將Vmn轉(zhuǎn)化為使用14位二進(jìn)制值表示的0、1序列B={b0,b1,…,b13}。若m+n為偶數(shù)，則二進(jìn)制序列不變；若m+n為奇數(shù)，則序列低7位與高7位進(jìn)行互換，得到序列B′={b7,…,b13,b0,…,b6}。

(4) 基于柵格位置的二進(jìn)制子串截取。根據(jù)m、n選取序列Z′中的14位構(gòu)成序列Zsub={z′m+n,z′m+n+1,…,z′m+n+13}。

(5) 異或運(yùn)算。按照m+n的奇偶性使用序列B或B′按位與序列Zsub異或，若Vmn為正則將第15位補(bǔ)0，否則第15位補(bǔ)1。

(7) 重復(fù)執(zhí)行步驟(3)—(6)，直至所有柵格的高程值置亂處理完畢，得到矩陣A′。

1.3 位置置亂

對(duì)A′進(jìn)行位置置亂的主要步驟為：

(1) 混沌序列X、Y的截取或補(bǔ)齊。判斷混沌序列X、Y的長度L1是否大于ρ，若大于ρ則取出該混沌序列的前ρ位；否則使用式(1)補(bǔ)足ρ位構(gòu)成序列X′、Y′。

p=mmodρ

(5)

在序列J′x中遍歷尋找與p值相等的元素，記錄其下標(biāo)為mID，并根據(jù)式(6)生成與該位置進(jìn)行對(duì)換的行號(hào)m′。若m′<0則將m′加上行數(shù)。

m′=(m-p+mID)mod row

(6)

q=nmodρ

(7)

在序列J′y中遍歷尋找與p值相等的元素，記錄其下標(biāo)為nID，并根據(jù)式(8)生成與該位置進(jìn)行對(duì)換的行號(hào)n′。若n′<0則將n′加上列數(shù)。

n′=(n-q+nID)mod col

(8)

1.4 文件頭置亂

DEM的文件頭中保存了DEM的元數(shù)據(jù)(見表1)，基于這些數(shù)據(jù)，用戶可以直接定位到DEM數(shù)據(jù)所在的真實(shí)位置。如果不進(jìn)行加密處理，勢(shì)必增加DEM置亂數(shù)據(jù)被破解的風(fēng)險(xiǎn)。X方向偏移，Y方向偏移和單元格大小，是決定DEM數(shù)據(jù)真實(shí)位置的決定因素，需對(duì)這3個(gè)數(shù)值進(jìn)行置亂處理，即

表1 DEM文件頭描述

(9)

經(jīng)過上述處理，一方面置亂后的X方向偏移，Y方向偏移數(shù)值與原數(shù)值完全不同，可將DEM的空間定位轉(zhuǎn)換至另一個(gè)未知位置；另一方面，置亂后的單元格大小影響到最終DEM表示范圍的大小，將DEM的覆蓋范圍進(jìn)行了縮放處理。

1.5 置亂DEM的還原處理

置亂數(shù)據(jù)還原的關(guān)鍵在于提供正確的密鑰，并按照置亂相反的流程執(zhí)行還原操作，其對(duì)應(yīng)的還原流程為先位置還原后高程還原。

DEM置亂數(shù)據(jù)A″還原的具體流程為：

(1) 基于還原密鑰生成混沌序列。基于用戶提供的密鑰{x0,y0,z0,ρ,σ}，根據(jù)式(1)—式(3)生成初始混沌序列X、Y、Z。

(4) 文件頭還原。使用參數(shù){x，y，z，ρ，φ}，根據(jù)式(9)再進(jìn)行一次異或運(yùn)算，即可得到原始的DEM文件頭信息。

所有位置運(yùn)算完畢后即完成了置亂矩陣的所有復(fù)原工作，得到最初的高程矩陣A。本文算法的DEM還原流程中無需原始數(shù)據(jù)的參與，是一種穩(wěn)定的盲還原方式，并且還原后的DEM數(shù)據(jù)與原始DEM數(shù)據(jù)完全相同，保證了DEM數(shù)據(jù)的精度不受損失。

2 試驗(yàn)與分析

本文采用ASCII格式的1∶50 000某涉密區(qū)域DEM數(shù)據(jù)(如圖4所示)作為試驗(yàn)數(shù)據(jù)，該數(shù)據(jù)中高程數(shù)據(jù)類型為整型，存在數(shù)值為-9999的Nodata區(qū)域。

本文試驗(yàn)中，首先輸入原始DEM與混沌參數(shù)，根據(jù)混沌參數(shù)生成混沌序列；然后使用混沌序列分別對(duì)DEM的高程、位置和文件頭依次進(jìn)行置亂；最后，輸出置亂DEM。DEM的還原是置亂的逆向操作，通過還原處理，最后得到原始的DEM數(shù)據(jù)。

為了評(píng)價(jià)本文算法的優(yōu)越性，下面主要從混沌序列周期檢驗(yàn)、安全性分析、置亂度分析和時(shí)間效率分析4個(gè)方面對(duì)算法進(jìn)行分析。

2.1 不同置亂參數(shù)對(duì)混沌序列周期性的影響

通過混沌映射或混沌運(yùn)動(dòng)獲取的混沌序列密碼，由于其混沌運(yùn)動(dòng)軌道表現(xiàn)出的內(nèi)隨機(jī)性、遍歷性和初值敏感性等特性，使得混沌系統(tǒng)在使用僅有微小變化的混沌參數(shù)進(jìn)行有限次的迭代后可以得到完全不同的序列[9]，這樣的特性使得混沌序列密碼滿足了混沌序列在抗破解方面的要求。同時(shí)，混沌序列密碼在進(jìn)行大量迭代后隨機(jī)性會(huì)產(chǎn)生大幅度減弱的現(xiàn)象，即混沌密碼在序列中出現(xiàn)一定的周期性重復(fù)。這一周期性重復(fù)降低了算法的安全性，因此混沌序列密碼需要盡量減弱周期性，增強(qiáng)隨機(jī)性，選擇混沌映射時(shí)盡量選取隨機(jī)性強(qiáng)的混沌映射。

本文使用的混沌序列僅有0和1兩種數(shù)字構(gòu)成，統(tǒng)計(jì)學(xué)中的游程檢測(cè)法是簡單且高效檢測(cè)序列中是否存在周期性子序列分布的有效方法[10]，其運(yùn)算結(jié)果為重復(fù)樣本發(fā)生的概率，計(jì)算結(jié)果越小表示周期性越弱。本試驗(yàn)使用C++編寫生成混沌序列的程序，將生成的混沌序列導(dǎo)出至文本文件，使用SPSS軟件中的游程檢驗(yàn)功能進(jìn)行序列周期性檢驗(yàn)，結(jié)果數(shù)據(jù)使用漸進(jìn)顯著性表示。構(gòu)建混沌序列總共需要4個(gè)參數(shù)，其中前3個(gè)參數(shù)控制混沌序列的生成，最后一個(gè)參數(shù)控制序列的二值化。試驗(yàn)參數(shù)見表2，其中A組為參照組，B組大幅增加了參數(shù)Y的值，C組小幅減少了參數(shù)Z的值，D組替換了參數(shù)σ的值。

表2 序列周期性檢測(cè)

通過SPSS的分析結(jié)果(見表2)可以看出，以上4組數(shù)值分布不一致的混沌參數(shù)生成的混沌序列的漸進(jìn)顯著性在序列長度為2136的情況下均為0，反映出該三維混沌映射生成的混沌序列具有很強(qiáng)的隨機(jī)性，不易產(chǎn)生“弱周期性”現(xiàn)象，符合混沌序列隨機(jī)性強(qiáng)的要求。

NIST發(fā)布的STS(statistical test suite)測(cè)試包是當(dāng)前國際上較為權(quán)威的對(duì)偽隨機(jī)序列進(jìn)行性能測(cè)試的工具，測(cè)試結(jié)果通過P-Value體現(xiàn)，同時(shí)會(huì)給出多個(gè)模板的測(cè)試通過率。其中包含15項(xiàng)指標(biāo)測(cè)試，混沌偽隨機(jī)序列的隨機(jī)性檢驗(yàn)中僅需使用頻數(shù)測(cè)試、分塊頻數(shù)測(cè)試、游程測(cè)試、頻譜測(cè)試和近似熵測(cè)試這5項(xiàng)測(cè)試并檢驗(yàn)其運(yùn)算結(jié)果即可。

首先在Linux環(huán)境下安裝STS-2.1.2測(cè)試包；其次根據(jù)上述組別A密鑰， 生成大小為1億 bit 的偽隨機(jī)0-1序列并輸出為二進(jìn)制文件；然后運(yùn)行STS工具包，本次測(cè)試中將數(shù)據(jù)分為2000組，每組數(shù)據(jù)50 000 bit，按上述5項(xiàng)指標(biāo)進(jìn)行測(cè)試；最后得到的測(cè)試結(jié)果見表3，可以看出本文使用的混沌序列通過了全部5項(xiàng)測(cè)試，整體上具有較好的隨機(jī)性。

表3 STS測(cè)試結(jié)果

2.2 安全性分析

傳統(tǒng)的加密方法可以使用計(jì)算機(jī)暴力測(cè)試的方法求解密鑰，實(shí)現(xiàn)加密數(shù)據(jù)的破解。本文還原算法的核心是使用正確的還原參數(shù)生成混沌序列，實(shí)現(xiàn)DEM數(shù)據(jù)的還原。優(yōu)秀的置亂與還原算法應(yīng)當(dāng)具有極高的密鑰敏感性，本文試驗(yàn)體現(xiàn)在還原參數(shù)只要發(fā)生一點(diǎn)變化，便無法還原出原始DEM。

本文提出的基于三維混沌映射的DEM置亂算法，在進(jìn)行置亂和還原時(shí)需要提供5個(gè)參數(shù){x0,y0,z0,ρ,σ}，其中{x0,y0,z0,σ}為(0,1)區(qū)間內(nèi)的任意位小數(shù)，ρ∈(1,+),ρ∈Z。本文試驗(yàn)使用近似的加密參數(shù)和解密參數(shù)來驗(yàn)證算法的抗破解性能(見表4)。為遵循單一變量原則，設(shè)置A組為參照組，使用相同的參數(shù)進(jìn)行置亂和還原，B、C、D、E組為對(duì)比試驗(yàn)組。由于前3個(gè)參數(shù)共同控制混沌序列的生成，體現(xiàn)的功能性相同，僅在B、C兩組進(jìn)行比對(duì)；D組修改了參數(shù)ρ的值，該值對(duì)位置置亂至關(guān)重；E組修改了參數(shù)σ的值，該參數(shù)僅控制混沌序列二值化時(shí)的初始值。5組參數(shù)的置亂與還原結(jié)果如圖5所示。其中圖5(a)為置亂后結(jié)果，圖5(b)—(f)分別為A、B、C、D、E組的還原結(jié)果。

表4 參數(shù)與還原度

通過圖5(a)可以看出，本文算法完全破壞了DEM的空間連續(xù)性；從圖5(b)可知使用相同的混沌參數(shù)可以完全復(fù)原置亂后的DEM，證明該算法具有完全的可逆性，還原出的數(shù)據(jù)沒有任何的精度損失；從圖5(c)—(f)可知還原參數(shù)只要出現(xiàn)略微的不同就無法實(shí)現(xiàn)置亂DEM的還原，所有置亂參數(shù)均具有數(shù)值敏感性，整體安全性強(qiáng)。

2.3 算法置亂度分析

對(duì)于置亂后DEM數(shù)據(jù)的置亂度，本文使用基于差分統(tǒng)計(jì)特性的圖像置亂度盲評(píng)價(jià)線性模型進(jìn)行驗(yàn)證。該模型通過計(jì)算置亂后圖像的差分圖像，統(tǒng)計(jì)差分圖像灰度分布直方圖，通過直方圖數(shù)值分布斜率特征，求解斜率絕對(duì)差因子，數(shù)值越大表示置亂度越好[11]。

由于地表高程數(shù)據(jù)具有潛在的空間連續(xù)性，大部分情況下高程變化連續(xù)且有規(guī)律，因此，DEM影像的差分圖像的灰度分布主要集中在中心區(qū)域，并且沿兩側(cè)呈快速下降的趨勢(shì)[12]。經(jīng)置亂后的圖像灰度值分布隨機(jī)，導(dǎo)致差分圖像對(duì)應(yīng)的差分值分布均勻，直方圖呈現(xiàn)出沿中心線性下降的趨勢(shì)。為了驗(yàn)證該方法在DEM數(shù)據(jù)置亂應(yīng)用中的可行性，本文試驗(yàn)使用DEM進(jìn)行測(cè)試，圖6(a)為正常的DEM圖像，其差分直方圖如圖6(b)所示，呈現(xiàn)出從中心快速下降的趨勢(shì)；圖6(c)為使用ArcMap生成的隨機(jī)柵格圖像，其差分直方圖如圖5(d)所示，沿中心向兩側(cè)呈線性緩慢下降趨勢(shì)。從圖6可見該方法適用于DEM影像置亂效果的評(píng)定。

使用兩組不同的置亂參數(shù)對(duì)DEM進(jìn)行置亂，原始圖像及置亂圖像差分直方圖如圖7所示，置亂程度見表5。本算法置亂的DEM數(shù)據(jù)，置亂度均達(dá)到0.85以上，具有較強(qiáng)的迷惑性。

表5 置亂參數(shù)與置亂度

2.4 算法時(shí)間效率分析

為檢驗(yàn)在不同數(shù)據(jù)量下的算法時(shí)間消耗，本文試驗(yàn)中使用ArcMap的創(chuàng)建隨機(jī)柵格功能構(gòu)建大小不同的隨機(jī)柵格，大小分別為200×200、400×400、600×600、800×800、1000×1000。編寫程序獲取算法開始執(zhí)行和運(yùn)算結(jié)束的系統(tǒng)時(shí)間并相減，得到算法執(zhí)行的總時(shí)間。不同數(shù)量的柵格在本文算法下進(jìn)行置亂的時(shí)間消耗見表6。進(jìn)行函數(shù)擬合后，發(fā)現(xiàn)本文算法的時(shí)間消耗與DEM中的柵格數(shù)量近似呈線性關(guān)系，算法時(shí)間復(fù)雜度較低(如圖8所示)，說明本文算法適用于大數(shù)據(jù)量DEM的置亂處理。

表6 時(shí)間復(fù)雜度檢測(cè)

3 討 論

(1) 本文DEM置亂方法主要使用三維混沌系統(tǒng)構(gòu)建混沌序列對(duì)DEM數(shù)據(jù)進(jìn)行置亂操作。同樣可以使用一維或二維混沌系統(tǒng)，如Logistic混沌序列，均可達(dá)到不錯(cuò)的置亂效果，但混沌序列的周期性較差，置亂強(qiáng)度不足。

(2) 本文算法與DEM的具體格式無關(guān)。雖以ASCII格式文件進(jìn)行試驗(yàn)，但具體方法可應(yīng)于不同格式的DEM文件。

(3) 由于異或運(yùn)算的結(jié)果均為正值，即高程在海平面以下區(qū)域DEM的運(yùn)算，在進(jìn)行還原時(shí)所有負(fù)值會(huì)歸0，通過在轉(zhuǎn)換時(shí)記錄二進(jìn)制數(shù)符號(hào)位的方式，可以有效避免負(fù)數(shù)無效的情況。本文應(yīng)用符號(hào)位的概念解決了高程值為負(fù)數(shù)時(shí)異或運(yùn)算產(chǎn)生的問題。

(4) 本文算法的置亂流程為首先進(jìn)行高程置亂，然后進(jìn)行位置置亂，最后進(jìn)行文件頭置亂。在實(shí)際的應(yīng)用中這3個(gè)置亂步驟的順序可以任意調(diào)換，最終的運(yùn)算結(jié)果無較大差異，但是在DEM數(shù)據(jù)還原時(shí)需要按照置亂順序的逆序進(jìn)行操作。

(5) 本置亂算法雖然保護(hù)了DEM數(shù)據(jù)在網(wǎng)絡(luò)傳輸過程中的安全性，但是沒有進(jìn)行DEM版權(quán)信息的保護(hù)?？梢栽诒局脕y算法的基礎(chǔ)上融入DEM數(shù)字水印算法，在保證數(shù)據(jù)安全的同時(shí)保護(hù)數(shù)據(jù)版權(quán)。數(shù)字水印可以顯式添加在置亂前和置亂后的DEM數(shù)據(jù)中，也可以隱式添加在高程置亂后、位置置亂前的DEM中間數(shù)據(jù)中。攜帶隱式數(shù)字水印的置亂算法需要在還原過程中檢測(cè)并去除圖像中的水印數(shù)據(jù)。

4 結(jié) 語

本文主要采用基于三維混沌系統(tǒng)的DEM置亂算法和還原算法，實(shí)現(xiàn)了以ASCII格式存儲(chǔ)的柵格地理數(shù)據(jù)的置亂與無損還原處理，并通過差分圖像的統(tǒng)計(jì)特征驗(yàn)證了該算法的置亂強(qiáng)度。試驗(yàn)表明，本文方法可以有效地保證DEM數(shù)據(jù)的傳輸安全，并且具有較好的抗暴力破解能力和自動(dòng)化特性。試驗(yàn)數(shù)據(jù)在置亂前和還原后的一致性達(dá)到100%，基本滿足了以ASCII格式存儲(chǔ)的柵格數(shù)據(jù)在網(wǎng)絡(luò)安全傳輸、封裝存儲(chǔ)等方面應(yīng)用的需求。