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

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

(1. 南京師范大學地理科學學院，江蘇 南京 210023; 2. 南京師范大學虛擬地理環境教育部重點實驗室，江蘇 南京 210023; 3. 江蘇省地理信息資源開發與利用協同創新中心，江蘇 南京 210023)

地理信息事關國家安全和社會利益，其安全防護是當前地理信息行業亟待解決的難題[1]。隨著計算機網絡、云數據等技術的迅猛發展，網絡數據傳輸的安全問題更是日益嚴峻。DEM數據作為國家空間數據基礎設施的重要內容，一旦發生泄密事件，會帶來巨大的社會安全隱患和經濟損失。因此，如何保障DEM數據在網絡傳輸時的安全性，是當前需要解決的重要問題之一。

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

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

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

1 研究方法

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

1.1 三維混沌序列生成

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

(1)

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

(2)

(3)

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

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

1.2 高程置亂

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

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

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

(4)

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

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

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

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

1.3 位置置亂

對A′進行位置置亂的主要步驟為：

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

p=mmodρ

(5)

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

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

(6)

q=nmodρ

(7)

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

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

(8)

1.4 文件頭置亂

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

表1 DEM文件頭描述

(9)

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

1.5 置亂DEM的還原處理

置亂數據還原的關鍵在于提供正確的密鑰，并按照置亂相反的流程執行還原操作，其對應的還原流程為先位置還原后高程還原。

DEM置亂數據A″還原的具體流程為：

(1) 基于還原密鑰生成混沌序列?；谟脩籼峁┑拿荑€{x0,y0,z0,ρ,σ}，根據式(1)—式(3)生成初始混沌序列X、Y、Z。

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

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

2 試驗與分析

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

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

為了評價本文算法的優越性，下面主要從混沌序列周期檢驗、安全性分析、置亂度分析和時間效率分析4個方面對算法進行分析。

2.1 不同置亂參數對混沌序列周期性的影響

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

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

表2 序列周期性檢測

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

NIST發布的STS(statistical test suite)測試包是當前國際上較為權威的對偽隨機序列進行性能測試的工具，測試結果通過P-Value體現，同時會給出多個模板的測試通過率。其中包含15項指標測試，混沌偽隨機序列的隨機性檢驗中僅需使用頻數測試、分塊頻數測試、游程測試、頻譜測試和近似熵測試這5項測試并檢驗其運算結果即可。

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

表3 STS測試結果

2.2 安全性分析

傳統的加密方法可以使用計算機暴力測試的方法求解密鑰，實現加密數據的破解。本文還原算法的核心是使用正確的還原參數生成混沌序列，實現DEM數據的還原。優秀的置亂與還原算法應當具有極高的密鑰敏感性，本文試驗體現在還原參數只要發生一點變化，便無法還原出原始DEM。

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

表4 參數與還原度

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

2.3 算法置亂度分析

對于置亂后DEM數據的置亂度，本文使用基于差分統計特性的圖像置亂度盲評價線性模型進行驗證。該模型通過計算置亂后圖像的差分圖像，統計差分圖像灰度分布直方圖，通過直方圖數值分布斜率特征，求解斜率絕對差因子，數值越大表示置亂度越好[11]。

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

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

表5 置亂參數與置亂度

2.4 算法時間效率分析

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

表6 時間復雜度檢測

3 討 論

(1) 本文DEM置亂方法主要使用三維混沌系統構建混沌序列對DEM數據進行置亂操作。同樣可以使用一維或二維混沌系統，如Logistic混沌序列，均可達到不錯的置亂效果，但混沌序列的周期性較差，置亂強度不足。

(2) 本文算法與DEM的具體格式無關。雖以ASCII格式文件進行試驗，但具體方法可應于不同格式的DEM文件。

(3) 由于異或運算的結果均為正值，即高程在海平面以下區域DEM的運算，在進行還原時所有負值會歸0，通過在轉換時記錄二進制數符號位的方式，可以有效避免負數無效的情況。本文應用符號位的概念解決了高程值為負數時異或運算產生的問題。

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

(5) 本置亂算法雖然保護了DEM數據在網絡傳輸過程中的安全性，但是沒有進行DEM版權信息的保護。可以在本置亂算法的基礎上融入DEM數字水印算法，在保證數據安全的同時保護數據版權。數字水印可以顯式添加在置亂前和置亂后的DEM數據中，也可以隱式添加在高程置亂后、位置置亂前的DEM中間數據中。攜帶隱式數字水印的置亂算法需要在還原過程中檢測并去除圖像中的水印數據。

4 結 語

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