留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于置乱-代换机制的TIN DEM信息伪装

陈令羽 宋国民 孙晨

陈令羽, 宋国民, 孙晨. 基于置乱-代换机制的TIN DEM信息伪装[J]. 武汉大学学报 ( 信息科学版), 2017, 42(7): 937-942. doi: 10.13203/j.whugis20150209
引用本文: 陈令羽, 宋国民, 孙晨. 基于置乱-代换机制的TIN DEM信息伪装[J]. 武汉大学学报 ( 信息科学版), 2017, 42(7): 937-942. doi: 10.13203/j.whugis20150209
CHEN Lingyu, SONG Guomin, SUN Chen. A Method of TIN DEM Information Disguising Based on Permutation-Substitution Theory[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7): 937-942. doi: 10.13203/j.whugis20150209
Citation: CHEN Lingyu, SONG Guomin, SUN Chen. A Method of TIN DEM Information Disguising Based on Permutation-Substitution Theory[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7): 937-942. doi: 10.13203/j.whugis20150209

基于置乱-代换机制的TIN DEM信息伪装

doi: 10.13203/j.whugis20150209
基金项目: 

国家自然科学基金 41371382

国家863计划 2013AA12A202

详细信息
    作者简介:

    陈令羽, 博士, 讲师。主要从事DEM信息伪装和战场环境仿真研究。ccllyy123456@126.com

  • 中图分类号: P208

A Method of TIN DEM Information Disguising Based on Permutation-Substitution Theory

Funds: 

The National Natural Science Foundation of China 41371382

the National High Technology Research and Development Program of China(863 Program) 2013AA12A202

More Information
    Author Bio:

    CHEN Lingyu, PhD, lecturer, specializes in DEM disguising, etc. E-mail:ccllyy123456@126.com

图(4)
计量
  • 文章访问数:  952
  • HTML全文浏览量:  128
  • PDF下载量:  311
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-07-01
  • 刊出日期:  2017-07-05

基于置乱-代换机制的TIN DEM信息伪装

doi: 10.13203/j.whugis20150209
    基金项目:

    国家自然科学基金 41371382

    国家863计划 2013AA12A202

    作者简介:

    陈令羽, 博士, 讲师。主要从事DEM信息伪装和战场环境仿真研究。ccllyy123456@126.com

  • 中图分类号: P208

摘要: 重点地区的TIN DEM数据具有重要的保护价值。根据数据的组织方式,结合密码学中的经典理论,提出一种基于置乱-代换机制的TIN DEM信息伪装方法。首先在频率域上利用Tent混沌映射生成的混沌序列对原始数据进行置乱;然后再利用中国剩余定理将置乱结果在空间域上进行数值代换处理,得到最终的伪装数据,并讨论了信息还原的方法;实验分析表明该方法的伪装效果良好,安全性能较高,能够满足TIN DEM数据的信息伪装要求,保障其安全存储和传输。

English Abstract

陈令羽, 宋国民, 孙晨. 基于置乱-代换机制的TIN DEM信息伪装[J]. 武汉大学学报 ( 信息科学版), 2017, 42(7): 937-942. doi: 10.13203/j.whugis20150209
引用本文: 陈令羽, 宋国民, 孙晨. 基于置乱-代换机制的TIN DEM信息伪装[J]. 武汉大学学报 ( 信息科学版), 2017, 42(7): 937-942. doi: 10.13203/j.whugis20150209
CHEN Lingyu, SONG Guomin, SUN Chen. A Method of TIN DEM Information Disguising Based on Permutation-Substitution Theory[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7): 937-942. doi: 10.13203/j.whugis20150209
Citation: CHEN Lingyu, SONG Guomin, SUN Chen. A Method of TIN DEM Information Disguising Based on Permutation-Substitution Theory[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7): 937-942. doi: 10.13203/j.whugis20150209
  • 数字高程模型(digital elevation model, DEM)作为一种基础地理空间数据,是现实世界地形起伏特征的缩影,在军事和经济领域应用广泛。不规则三角网(triangulated irregular network, TIN)通过连接离散的高程采样点,将地形表达成不重叠的连续三角面,具有数据量小、地形细节表达详细等优点,特别适用于高精度的地形建模与仿真。开放的网络环境中,用户可以在数据共享的机制下获取到各种精度的DEM数据,但是重点地区特别是这些地区的高精度数据,仍具有重要的保护价值。

    目前, 针对TIN模型的信息保护主要有信息加密和数字水印两种[1]。信息加密能够为所有数据提供一种通用的保护模式,结果一般是无法理解的数据流,更易引起攻击者的注意,仅依赖于算法的安全性。随着高性能计算机运算速度的不断提高,任何密码学方法都存在被破解的可能[2]。数字水印技术在格网DEM数据中的研究较多,成果显著,部分方法效果良好[3]。不规则三角网的数字水印技术是在三维网格水印的基础上发展而来的,最早由Ohbuchi提出,通过在空间域或频率域上进行修改网格的几何特征或拓扑特征嵌入水印[4-6]。近年来,根据数据的具体特点,出现了多种更具有针对性的TIN水印算法[7-9]。但由于处理的数据量较小,数字水印更注重数据的版权信息保护,很少用于保护数据内容本身,在一定程度上限制了水印技术的应用领域。

    信息伪装是一种主动式的信息隐藏,可以将原始数据转换成另一种相同格式的虚假数据,不仅隐藏了数据,更隐藏了隐藏技术的存在,兼具安全性和迷惑性,在数字图像[10]和格网DEM数据中逐渐引起关注[11-13],而专门针对TIN数据的信息伪装还没有相关报道。在进行格网数据的信息伪装时,由于数据间具有较大的冗余性,一般不能忽略数据间的相关性,仅针对单个高程数据进行处理;而由于存储结构优化,TIN数据间的相关性大幅度减少,可以考虑单个数据伪装后的叠加处理,为信息伪装的处理方式提供了更多的选择空间。置乱-代换机制是密码学设计中的一种重要方法,具有较高的安全性能。结合TIN数据的特点,按照置乱-代换机制的相关原理,本文提出了一种基于混沌映射和中国剩余定理的信息伪装算法,同时修改三角网结点的位置和高程值,保障TIN数据的安全存储和传输。

    • 混沌映射是一种确定性的非线性伪随机系统,可以利用相同的初始参数重复产生,但是对初值表现出极端的敏感性,极小的差异所形成的混沌序列大不相同。由于产生的混沌序列结构极其复杂,很难进行重构和解析,因此, 特别适用于信息加密和保密通信[14]。目前, 常用的一维混沌映射主要有Logistic、Tent、ICMIC、Bernouilli shift、Chebyshev和Sine映射等,其中Tent映射和Bernouilli shift映射在所有映射中具有较快的搜索效率[15-16]。这里采用计算简单的Tent映射进行一维高程数值的置乱。

    • Tent映射又称帐篷映射,是一种分段的一维映射,其表达式为:

      $$ {x_{n + 1}} = \left\{ \begin{array}{l} \mu {x_n},{\rm{ }}0 < {x_n} < 0.5\\ \mu (1 - {x_n}),{\rm{ }}0.5 \le {x_n} \le 1 \end{array} \right. $$ (1)

      式中,μ∈(0, 2),xn∈(0, 1) 可以产生一个序列,其分岔图如图 1所示。

      图  1  Tent映射分岔图

      Figure 1.  Bifurcation of Tent-map

      图 1可知,当大约μ>1.4,式(1) 进入混沌状态。图 2μ=1.7时,分别取x0=0.8(蓝线)和x0=0.801(红线)迭代100次,得到的结果(大不相同)。事实上,即使有很小的扰动,当迭代次数足够多时,结果仍有很大区别,符合混沌映射的基本特征。

      图  2  Tent映射的初值敏感性

      Figure 2.  Sensitivity to Initial of Tent-map

    • 不同于格网数据,TIN模型中的高程数据分布没有特定规律,难以直接进行处理。因此,在进行信息伪装之前,需要先进行数据规范化,将三维空间中不规则排列的高程结点规范成能够直接进行处理的形式。TIN模型中结点数据至少包含两个坐标值和一个高程值,坐标排列不规则,很难归化到类似格网数据的二维空间中,但规范到一维空间中十分简单,方便采用一维Tent映射对其进行处理。因为需要重点伪装是TIN模型中的高程信息,可按照高程结点的横坐标大小进行排序,横坐标相同时以纵坐标大的为先,可以将所有结点规范到只含有高程数据的一维序列中。

    • 基于Tent映射进行的高程数值置乱可以在空间域上进行,也可以在其频率域上进行。空间域上的数据置乱方法简单,但不能改变数据的统计特性,容易受到统计分析的攻击;频率域上单点位置的变化可以引起整个数据集在空间域上数值的改变,得到的置乱效果更好。因此,采用如下方法进行TIN模型的高程置乱。

      1) 给定Tent映射的参数a和初值x0,作为置乱密钥,将其带入到式(1) 中迭代N次(大于200) 产生混沌序列X={xi|i=1, 2, 3, …, N};

      2) 比较X中各要素的大小,将其从小到大依次排列形成X′={x′i|i=1, 2, 3, …, N},并记录其中各要素在序列X中的原始地址,形成置换序列P={pi|i=1, 2, 3, …, Npi}表示X′中第i个元素在原始序列X中的位置;

      3) 利用一维离散余弦变换将规范化后的高程数值转换到频率域中,形成频率系数序列W={wi|i=1, 2, 3, …, L},其中L表示TIN中高程结点的数量。将其分成n=[L/N]组,对每一组中的频域系数按照置换序列P进行变换,将其第i个位置的数据置换到第pi个位置上,组合得到置乱频率系数集合W′;

      4) 利用一维离散余弦逆变换将W′转换到空间域上,完成数据置乱。

    • 置乱后的TIN数据已经达到了信息伪装的效果,但是一维混沌映射的密钥空间有限,安全性不高;而且即使在频率域上进行系数置乱,在形成的伪装数据中仍能够得到原始数据的某些统计特征。因此,需要进行进一步的数据代换,最大程度地保证高程信息的安全。

    • 中国剩余定理又称孙子定理,是求解同余方程组的经典方法,在密码学中的群签名和公钥设计中得到了广泛的应用[17]。具体描述如下[18]

      设正整数m1m2m3、…、mk两两互素,m=m1m2m3mkMi=m/miMi-1Mimi的乘法逆元,满足Mi-1Mi=1(modmi),其中i=1, 2, 3, …, k。则对于任意k个整数a1, a2, a3, …, ak(k≥2) 构成的同余方程:

      $$ \left\{ {\begin{array}{*{20}{c}} {x \equiv {a_1}\left( {{\rm{mod}}{m_1}} \right)}\\ {x \equiv {a_2}({\rm{mod}}{m_2})}\\ \vdots \\ {x \equiv {a_k}({\rm{mod}}{m_k})} \end{array}} \right. $$ (2)

      在模m下有唯一解:

      $$ \begin{array}{*{20}{c}} {x = {M_1}M_1^{-1}{a_1} + {M_2}M_2^{-1}{a_1} + \ldots + }\\ {{M_i}M_i^{-1}{a_i}({\rm{mod}}m)} \end{array} $$ (3)

      其证明可以参见文献[19],Mi-1在其对应的模中存在并唯一,可根据扩展Euclidean算法求得[19]

    • 根据中国剩余定理的解算过程可知,利用互素的正整数可以将若干个整数转换成一个大数。同时,根据式(2) 可知:xai(modmi),当mi>ai时,ai有唯一解,ai=x(modmi)。由此可以推定,利用中国剩余定理加密正整数集合Ai={ai|i=1, 2, 3, …, k}时,选用k个大于max(Ai)两两互素的整数,可以得到唯一结果,并可以在实数域中将其完整还原。

      根据高程数据的特征,利用中国剩余定理进行TIN模型的高程代换时,按照以下步骤进行。

      1) 将经过置乱的所有高程值转换成cm级后取整数,根据陆地高程的取值范围,保留到cm级整数时正整数的位数最多为6(小于884 443 cm)。将每个高程值hi分为bi=[hi/1 000]和ci=hi(mod 1 000) 两部分,形成数据集合Bi=bi|i=1, 2, 3, …, LCi={ci|i=1, 2, 3, …, L},其中L表示TIN中高程结点的数量。将高程数据转换成cm级不仅可以增加数据伪装的精度,还尽量减少bi等于0的可能性,避免代换过程中0值的参与,使得计算结果趋于合理;

      2) 选择4个素数m1m2m3m4>1 000,作为代换密钥。利用中国剩余定理,按照规范化后形成的顺序,利用m1m2依次转换B2n-1C2n-1得到D2n-1,利用m3m4依次转换B2nC2n得到D2n,其中n=1, 2, 3, …, [L/2],D为转换后的数值集合。即每次利用密码可以加密两个高程值,得到两个新的整数。同时密钥的个数可以根据实际情况选择,数量越多,计算的复杂度就越高,安全性也越强;

      3) 归化加密的数值到合理的高程取值范围。通过中国剩余定理转换得到的数值diD的取值范围为[0, Hm),其中Hm=max(m1m2, m3m4)。为了增加伪装数据的迷惑性,避免不符合该坐标范围内高程数值的出现,将其数据归化到原始数据的取值范围内,采用方法如下:

      $$ {{d'}_i} = {H_{{\rm{min}}}} + \frac{{({d_i}-{D_{{\rm{min}}}}) \times ({H_{{\rm{max}}}}-{H_{{\rm{min}}}})}}{{{D_{{\rm{max}}}}-{D_{{\rm{min}}}}}} $$ (4)

      式中,HmaxHmin分别表示原始高程数据的最大值和最小值;DmaxDmin表示经中国剩余定理处理后得到代换数组中的最大值和最小值。记录DmaxDmin作为密钥的一部分;

      4) 将得到的d′i形成最终的数据集合D′,即得到了经过中国剩余定理伪装的TIN数据。

      将经过置换和代换的一维离散高程数据按照数据规范化的逆过程依次分配给TIN模型数据中对应的各个高程结点,就完成了整个信息伪装过程。

    • 数据还原是TIN模型信息伪装的逆过程,包括代换还原和置乱还原两部分。

    • 代换还原是指将伪装数据在空间域在利用中国剩余定理还原到代换伪装之前的状态,是伪装代换的逆过程。步骤如下。

      1) 首先按照§1.2中的方法将伪装数据进行规范化,方便进行还原处理;

      2) 利用密钥DmaxDmin,将伪装数据中所有的高程数值利用下式进行转换:

      $$ {d_i} = {D_{{\rm{min}}}} + \frac{{({{d'}_i}-{{H'}_{{\rm{min}}}}) \times ({D_{{\rm{max}}}}-{D_{{\rm{min}}}})}}{{({{H'}_{{\rm{max}}}}-{{H'}_{{\rm{min}}}})}} $$ (5)

      其中,HmaxHmin分别表示伪装数据中的最大值和最小值,得到转换后的数据集合D

      3) 利用代换密钥m1m2m3m4,按照中国剩余定理,对得到的集合D中的每一个元素进行处理,根据式(3),每一个元素解密可以得到两个原始数据,依次加入数据集合E

      4) 对E中的元素,作如下处理:

      $$ \left\{ \begin{array}{l} {F_{2n-1}} = 1{\rm{ }}000{E_{4n-3}} + {E_{4n-1}}\\ {F_{2n}} = 1{\rm{ }}000{E_{4n - 2}} + {E_{4n}} \end{array} \right. $$ (6)

      组合得到集合F,为TIN伪装数据进行数据代换前、高程置乱后的结果。

    • 置乱还原是指将伪装数据在频率域中利用Tent映射还原到原始位置,是伪装置乱的逆过程。其步骤如下。

      1) 利用置乱密钥ax0N,根据式(1) 生成混沌序列X,按照置乱步骤2) 的方法得到置乱序列P

      2) 利用一维离散余弦变换将代换还原后的高程集合F转换到频率域中,得到频率系数集合W′,利用P对其进行反置乱,得到原始频率系数集合W

      3) 利用一维离散余弦逆变换将W转换到空间域上,完成置换还原,得到原始的高程数据集合,并将其一一对应于原始的空间坐标,得到最终还原后的TIN数据。

    • 选择一组TIN DEM数据进行实验,其中包含853个离散高程点。从伪装效果和安全性能两个方面对该方法进行分析。

    • 按照置乱-代换的步骤对实验数据进行伪装和还原处理,其中混沌映射的初始值分别选择μ=1.7,x0=0.8;代换密钥(m1, m2, m3, m4)为(1 021, 4 597, 1 039, 2 351)。得到高程值的结果利用点集显示,如图 3

      图  3  TIN DEM信息伪装和还原效果比较

      Figure 3.  Effect Comparison of Disguising and Restoring for TIN DEM

      图 3可知,仅经过频率域上的混沌置乱处理就可以得到信息伪装的目的,但结果具有一定的规律性,与原始数据存在隐含关系;而通过混沌置乱和中国剩余定理代换共同处理后得到的数据和原始数据有很大的不同,说明达到了信息伪装的要求;同时,虽然在利用中国剩余定理时舍去了数据的部分精度,但本实验中利用密钥得到的还原数据与原始数据几乎相同,最大误差仅为0.010 7 m, 平均误差0.002 3 m,不影响还原数据的正常使用,完全可以满足伪装还原的要求。

    • TIN DEM的信息伪装除了能够达到预期的伪装效果,具有一定的迷惑性外,更应该具有足够高的安全性能。为了保证伪装数据的绝对安全,设计的伪装算法应当具有尽可能的大密钥空间,能够抵抗高速度计算机的穷举分析。这里设计的伪装算法中最主要的密钥分别是Tent映射的初始参数a0μ以及中国剩余定理中选用的4个素数(m1, m2, m3, m4)。为了能够产生理想的混沌序列,通常μ∈(1.4, 2)、x0∈(0, 1),大于1 000的素数很多,但因为选择过大的素数作为密钥时,归化处理会损失更多的精度,通常不予考虑。一般情况下,只有密钥空间大于2100时,才认为该算法是安全的[20]。表面上看,利用Tent映射和中国剩余定理密钥的选择范围很小,但是其具有极大的敏感性。当其他条件不变,仅将图 3实验中的密钥改为x0=0.800 001时,得到的结果如图 4所示。

      图  4  x0=0.800 001时实验数据的伪装效果

      Figure 4.  Effect of Disguising When x0=0.800 001

      分析图 3图 4可以发现,即使密钥发生极小的变化,得到的伪装数据就有极大的不同,说明设计的算法对密钥具有极大的敏感性,虽然取值范围有限,但仍具有很大的密钥空间。

参考文献 (20)

目录

    /

    返回文章
    返回