在线导航模式随机参数插入加密算法应用研究＊

方秋水 杨敬锋 李 勇 常振廷

（1.广东岭南通股份有限公司 广州510110；2.广州市公共交通数据管理中心 广州510620；3.广州地理研究所 广州510070）

0 引 言

导航电子地图的真实坐标必须加密转换成国家测绘局要求的加密坐标才可以出版和发布，形成了以自主导航为代表的离线位置服务模式。现有模式下导航电子地图从测绘、审查、加密到发布需要耗费至少半年时间，造成导航数据现势性较差，实时交通等数据难以立即更新和发布到手持终端上，远远未能满足用户对实时数据的要求。为适应目前已经逐步形成的在线导航新模式，同时保证国家安全，有学者提出了在线模式下的电子地图坐标加密算法，刘爱龙［1－2］等提出地图数据网络分发的混合加密算法和散列组合加密算法，将坐标等数据与密钥混合后传输，增加了数据的安全性；张姗姗［3］、Zheng Liangbini［4］研究了矢量地图在异地传输的数据加密方法，并采用混合加密的方式来保证网络环境下矢量图形数据的安全性；闵连权［5］、钟尚平［6］等分别尝试了基于混沌序列的数据加密算法，并在电子地图网络传输中使用；潘伟洲［7］等利用训练后的BP网络来预测新的百度坐标所对应的GPS坐标。这些前人的研究成果一定程度上促进在线导航模式下加密算法的研究进程，但这些算法存在需要耗费大量运算时间等问题，而对于要求电子地图信息迅速更新的在线导航模式，往往难以满足实际应用的需求，为此，本文提出基于非对称加密算法的在线导航应用随机参数插入加密算法，该算法具有计算量小、加密效率高、隐秘性强等优点，适用于数据更新和发布迅速的在线导航服务。

1 非对称密码算法（RSA）

非对称密码算法是目前公钥密码的国际标准，其基础是数论的欧拉定理，安全性依赖于大数的因式分解的困难性［8－9］，其计算步骤为

1）选取2个素数p和q，计算n＝pq。

2）计算φ（n）＝（p－1）（q－1），式中：φ（n）为欧拉函数。

3）随机选取整数e，满足gcd（e，φ（n））≡1，其中1＜e＜φ（n）。

4）求出能满足ed≡1（modφ（n））的整数d，并且1＜d＜φ（n）。

通过欧几里得算法的对数运算，可求出整数d，进而求取整数e。其中：e为公开值；d为非公开值。计算可得公开密钥k＝（e，n）以及秘密密钥k′＝（d，n）。明文m满足0≤m≤n，则其加密算法为：c＝Ek（m）＝me（modn）；解密算法为：m＝Dk（Ek（m））＝cd（modn）其中加解密运算速度取决于模幂运算，安全性则取决于模n的素数分解。

2 随机参数插入算法

为避免智能手机等手持终端所安装的防火墙等网络安全工具对加密坐标信息的拦截和窜改，保证在线导航应用符合国家在电子地图应用相关规定的同时，满足在线导航实际应用中对坐标信息通信隐秘性、准确性和可靠性的需要，设计一种具有用户针对性的随机参数算法，使在线导航应用中涉及国家安全的加密坐标信息能准确传输并进行有效解密。

为了使嵌入的隐藏信息不容易被发觉，需要对待隐藏的信息进行随机化。随机后的待隐藏信息无论是在信息的内容还是信息的结构上都消除了原有的特征。攻击者就是提取出隐藏信息，也会因隐藏信息是一堆无法识别的乱码而不能确认是否存在隐藏通信，同时服务端也能够发现隐藏信息是否遭受篡改［10－12］。

随机参数的获取方法是，在线导航服务器和移动终端之间共享一个密钥种子S，在在线导航服务器向移动终端发送加密坐标的同时通过随机数函数R（x）生成隐藏的加密／解密密钥K，其中K＝R（S）。为增加加密坐标在传输和使用过程中的安全性，解密密钥的使用必须与移动终端的注册名相关，其结果是，手持终端每次使用在线导航服务请求时，将产生不同的随机密钥种子，在使用结束后，密钥种子自动失效。

3 基于非对称加密算法（RSA）的随机参数插入算法

非对称加密算法保证了加密坐标信息的安全，而随机参数算法则满足了信息通信隐秘性、准确性和可靠性的需要，将二者优点的结合，在在线导航实际应用中可满足国家政策，并保证在线导航服务的快速、准确与可靠。

基于RSA的随机参数算法的流程见图1：

图1 基于RSA的随机参数算法流程Fig.1 Process parameters based on RSA algorithm

信息点的实际坐标需要进行坐标加密从而变换成可进行商业运营的加密坐标，并在进行加密变换后将加密坐标信息变换成符合RSA加密算法要求的数据格式；在手持终端请求在线导航服务时，在线导航服务器将以密文方式，发送经过RSA加密的变换坐标信息以及随机加密信息，在与用户名相关确认后，手持终端可获取加密坐标，接受在线导航服务。

4 实验及结果

以HTC One X手持终端结合在线导航服务器进行实验。需要说明的是，HTC One X是预装Android操作系统的智能手机，其硬件带有GPS模块，支持与服务器之间以GPRS方式进行通信，并在扩展内存卡上预装基础地图。在线导航服务器可向应用手持终端提供POI查询与定位、位置共享、自驾路径规划等服务内容。本文以自驾路径规划服务为例，通过对比RSA加密模式以及基于RSA的随机参数插入加密模式在加／解密时间、安全性、误码扩展性等方面进行对比，说明本文提出的算法的实验结果。

表1是RSA加密模式以及基于RSA的随机参数插入加密模式在HTC One X上选取相同起始点和终点的自驾路径规划的实验结果。其中在线导航应用RSA加密模式以及基于RSA的随机参数插入在线导航应用加密模式则是在在线导航服务器支持下进行的在线自驾路径规划服务，可支持实时路况下的导航服务。

表1 2种算法在自驾路径规划中的功能实验结果对比Tab.1 Comparison of the experimental results between the two algorithms in the drive path planning function

由表1可见，2种模式都可以得到准确的解密，基于RSA的随机参数插入加密模式的加／解密时间明显地要比RSA加密模式要长，但由于RSA加密模式并没有与用户注册名进行关联，解密后坐标信息实际上可以共用于不同用户，而基于RSA的随机参数插入加密模式由于采用的服务端与应用端的共享密钥种子，仅支持唯一的注册用户使用。

表2是RSA加密模式以及基于RSA的随机参数插入加密模式在同一手持终端以及服务器上的安全性实验结果对比。

表2 2种算法的安全性对比Tab.2 Safety comparison between the two algorithms

由于RSA加密模式的应用已经相当广泛，其抗穷举攻击的能力在信息技术的飞速发展下已经不断被削弱，而基于RSA的随机参数插入加密模式由于采用了与用户名相关的随机参数插入算法，使加密信息的隐秘性增强，抗穷举攻击能力得到了一定提升。

5 结束语

为保证电子地图在应用中的坐标安全问题，同时满足在线导航对实时信息的发布要求，本文提出了基于RSA的在线导航应用随机参数插入加密算法。该算法在利用经典的RSA算法对坐标信息进行加密的同时，引入与用户注册名相关的随机参数插入加密算法，手持终端每次使用在线导航服务请求时，将产生不同的随机密钥种子，增加了加密数据的隐秘性，提高了坐标的抗穷举攻击能力，在实验中得到较好的结果。本文算法效率高、保密性好、简单及具有较小的误码扩散性的特点，能满足于在线导航服务对坐标信息安全保密的实际应用需求。

［1］ 刘爱龙，张 东，陈 涛，等.地图数据网络分发的混合加密算法［J］.计算机工程，2008，34（18）：186－188.

［2］ 刘爱龙，张 东，田 雁，等.地图数据网络分发中数据加密算法的研究［J］.测绘科学，2007，32（4）：32－35.

［3］ 张姗姗.矢量图形数据的网络传输加密算法研究［D］.武汉：武汉大学，2005.

［4］ Zheng Liangbin，You Fucheng.A fragile digital watermark used to verify the integrity of vector map［J］.Conputer Engineering and Application，2010，46（26）：99－101.

［5］ 闵连权.矢量地图数据的加密算法［J］.海洋测绘，2005，25（2）：55－57.

［6］ 钟尚平，高庆狮.网络环境下地图的混沌加密实用算法［J］.计算机辅助设计与图形学学报，2004，16（2）：238－242.

［7］ 潘伟洲，陈振洲，李兴民.基于人工神经网络的百度地图坐标解密方法［J］.计算机工程与应用，2013（3）：1－4.

［8］ 杨德山，陆魁军.一种改进的RSA加密算法设计与实现［J］.计算机应用与软件，2007，24（10）：188－190.

［9］ Verma A，Srivastava A.Integrated routing protocol for opportunistic networks［J］.International Journal of Advanced Computer Science and Applications，2011，2（3）：85－92.

［10］ Scheneier B.应用密码学协议、算法与C源程序［M］.北京：机械工业出版社，2000.

［11］ 邹昕光，金海军，郝克成，等.基于HTTP协议多维随机参数插入通信隐藏算法［J］.计算机工程与应用，2006（34）：127－130.

［12］ Shikfa A，Onen M，Molva R.Bootstrapping security associations in opportunistic networks［C］∥Proceedings of the 8th IEEE International Conference on Pervasive Computing and Communications Workshops（PERCOM Workshops）.Piscataway NJ：IEEE Press，2010：147－152.