面向深空通信的纠错密码研究

二〇一〇国防空天信息技术前沿论坛集 收稿日期：2010-07-17 基金项目：国家自然科学基金(60773074，60902042)，博士后专项基金（20090006110014)，国家 863 资助项目（2009AA062705）和北京市自然科学 基金(4102042)资助课。 作者简介：丁颜（1981-），男，河南周口人，博士生，研究方向为通信安全.E-mail:dingyan020213@163.com 王超(1978-)，男，博士，主要研究领域为自组织网络、移动通信、宽带通信网与安全技术、认知无线电和通信中的调度理论、通信中的博 弈论、容迟容断网络。 面向深空通信的纠错密码研究 丁 颜，王 超 （北京科技大学 信息工程学院，北京 100083） 摘 要：深空通信时延长、误码率大、上下行链路不对称、信息容易被偷听和链路易中断等特 点，决定了纠错密码技术成为深空通信的一个重要和困难的问题。信息在传输过程中，不仅要有很 好的安全性，还要有一定的容错能力。通常，先对信息加密，再将加密信息送到编码信道，借助纠 错编码使密码具有纠错能力，增加了系统的复杂性，同时产生了一定的时延。将纠错和加密结合起 来提高了系统的效率。大部分纠错密码体制从变换的角度是基于明文的线性变换，容易被攻击。介 绍了 LDPC 码的特点，提出了加密和纠错相结合的基于 LDPC 码的分组加密纠错体制，引入了非线 性变换，具有很好的安全性。 关键词：纠错密码； LDPC 码； 深空通信 中图分类号：TP393 A method of error-correction cipher in deep space communication DING Yan, WANG Chao (School of Information Engineering, University of Science and Technology of Beijing, Beijing 100083) Abstract：In deep communication, the characteristics of long delay, great error rate and packet loss, eavesdropping, asymmetric bandwidth between uplink and downlinks easily interrupted determine that the technology of error-correction cipher is important and difficulty. In transmission process, some important information needs not only security but also error resilience. Usually, encryption followed by error correction increasing the system complexity while producing some delay. So jointing error correction and encryption will make the system more efficiency. Most of the proposed error-correct ciphers are based on linear transformation, they are weak in resisting cryptanalysis because of the lack of nonlinear transformation in cryptosystems. The basic concept and characteristic of LDPC codes are introduced. The error-correction cipher that joint LDPC codes and cipher with high security because of nonlinear transformation. Key words：Error-correction cipher; LDPC code; Deep space communication 0 引 言 按照国际电信联盟（ITU）的规定[1]：以宇宙飞 行体为对象的无线电通信称为宇宙无线电通信，简称 2 专题六：空间信息安全与防护 为宇宙通信。包括地球站与宇宙站的通信、宇宙站之 间的通信和通过宇宙站的转发或反射来进行的地球 站相互间的通信。宇宙通信也称为空间通信。它分为 近空通信与深空通信。近空通信指地球上的实体与地 球卫星轨道上的飞行器之间的通信，这些飞行器的轨 道高度为数百至数万公里，如各种应用卫星、载人飞 船和航天飞机等。深空通信通常指地球上的实体与离 开地球卫星轨道进入太阳系的飞行器之间的通信，通 信距离达几十万、几亿至几十亿公里。 空间通信技术发展的目标之一是实现太阳系内 任何时间、任何地点的连续通信[1]。与近空通信相比， 深空通信的特点主要表现在巨大的路径损失和时延、 断续通信；网络拓扑不固定，需要建立自组网；深空 环境复杂，需要开发智能探测器和超视距通信；天基 段和地面段带宽不对称、采用不同的网络技术等。 随着数字通信特别是深空通信的飞速发展，如何 提高传输数据的可靠性和安全性，已成为日益重要的 研究课题[2]。无论是对称密码体制还是公钥密码体 制，在讨论密码体制时，都没有考虑到密文通过有扰 信道时的情况[3]。事实上，密文通过各种信道特别是 深空通信信道时，会受到不同程度的各种噪声干扰， 从而接收端对密文不能正确解密。对纠错编码解决此 问题的常用方法之一，但是这种把加密和编码分别考 虑的方法使整个系统的速率降低，设备复杂性增加 [3]。纠错密码有很多优势，例如纠错密码都具有概率 密码体制的优点，若干密文对应一个明文，从而增加 了破译的难度。从应用和实现的角度，特别在深空探 测器资源受限的设备，纠错密码将显示更大优势。 LDPC（Low-Density Parity-Check）码以强大的纠错 能力、低复杂度的快速译码算法和良好的码结构特性 成为解决恶劣信道环境条件下高速、高质量通信的一 项关键技术[4]。同时，LDPC 码已经被欧洲 DVB-S2 卫星通信采用 , 美国 NASA 的 JPL 已经向 CCSDS（the Consultative Committee for Space Data Systems）提交了基于 LDPC 码的。因此，对 LDPC 码的研究具有非常重要的现实意义 [5]。1978 年 Berlekamp、McEliece 和 Tilbrog 等证明了纠错码理论 中一般线性码问题是 NP 问题[6],同年 McEliece 根据 一般线性分组码的译码问题上一个 NP 问题，利用 Goppa 码构造了第一个公钥密码体制，简称 McEliece 体制[7]。自此以后，有关密码学和纠错码相结合的研 究，利用纠错码构造各种密码系统研究得到快速发 展。 McEliece 体制实际上并没有将纠错和加密性能 结合，因为它不能对信道产生的任何错误码进行纠 错。McEliece 体制提出后，其他研究者对该体制进行 了攻击和改进，其中，Berson[8]提出了对 McEliece 体 制的两种攻击方法，使得攻击者很容易破坏该密码体 制。 1984 年，T.R.N.Rao 提出了一个 Rao 私钥密码 体制[9]，基本思想是将 McEliece 公钥用作私钥密码体 制，并对生成矩阵保密。王新梅在文献[3]中提出了 具有纠错密码能力的 MC 分组加密纠错体制。该体制 的思想建立在 McEliece 公钥密码体制基础之上，基 本思想是对明文先进行纠错编码，在进行分组加密。 但是这些纠错密码算法从变换的角度是将明文和一 个矩阵相乘产生密文，算法没有引进非线性变换，不 能抵抗线性密码分析和差分密码分析，导致了巨大的 安全隐患。文献[10]给出了一个纠错密码算法，引入 了非线性变换，其整体结构类似于 Rijdal 算法，将列 变换替换为具有纠错功能的 MDS 码。杨敏等在文献 [11]中引入了非线性变换，从而使纠错密码具有更高 的安全性。我们利用 LDPC 纠错编码适合深空通信的 优点，引进非线性变换设计纠错密码体制，使纠错和 安全于一体，提高了信息处理的效率，同时增强了密 码的安全性，使其更适合深空通信的复杂环境。 1 基于 LDPC 纠错密码的构造 1.1 LDPC 纠错码 LDPC 码[5]是一类线性分组码，通常用一个 m 行 n 列的奇偶校验矩阵 H 表示，H 矩阵的对偶空间就是 它所有 LDPC 码字，设码长为 n, 信息位为 k，校验 位为 n-k, 码率为 r=k/n。则二元 LDPC 码校验矩阵 H 满足以下四个条件： (1)每一行含有 a 个 1； (2)每一列含有 b 个 1； (3)任意两列之间位置相同的 1 的个数不大于 1。 (4)与码长和 H 相比，a 和 b 都较小。 相对于深空通信以前使用的 Turbo 码，LDPC 码 具有以下优点[5]：1）不需要深度交织以获得好的误 码性能；2）具有更好的分组误码性能；3）误码平台 处的误码率大大降低；4）误码不基于网格。LDPC 码传统编码算法与一般的线性分组码类似，利用生成 矩阵构造码字。若已知长度为 m 的输入信息向量 M, 丁 颖等：面向深空通信的纠错密码研究 3 以及m n× 的生成矩阵 G，可得码字 C: C M G= × , 获得校验矩阵后，利用 H 和 G 之间的正交性可用高 斯消元法得到生成矩阵 G。由线性分组码理论可知， 对于任意的汉明重量不大于 t 的错误图样 z，当接收 端收到mG z+ ，译码算法总可以正确的恢复出原信 息向量 m。 1.2 多变量公钥密码体制 基于 MQ 问题的多变量二次密码体制，与传统公 钥密码体制相比，具有加解密速度快，安全性强，是 研究抵御未来量子计算机攻击方法的方向之一[11]，其 依赖的困难问题是有限域上非线性方程组的求解问 题。 设 GF(2)为有限域，MQ 密码体制 [11]的公钥 ' uP T P S= D D ，其中 S 和 T 为有限域 GF(2)的可逆线 性变换，该方程由 n 个变量 m 个二次方程所组成的 方程组： 1 2 , , , 1 1 ( , , , ) n i n i j k j k i j j i j k n i p x x x x x x ≤ ≤ ≤ = = + +∑ ∑" γ β α 其中1 i m≤ ≤ ，系数 , , ,, , (2)i j k i j i GF∈γ β α 。多项式向 量 1 1 1( ) ( ( , , ), , ( , , ))n m np x p x x p x x= " " " 为公钥，三 元组 '( , , )T P S 为私钥。 1.3 纠错密码的构造 为了增强纠错密码的安全性，同时发挥 LDPC 纠 错码的纠错特点，构造纠错密码时，引入非线性变换 [11]。 设（n, k, 2t+1）是某一 LDPC 码[4]，k 为信息组 的位数，2t+1 为该码的最小距离，该码能纠 t 个错误， 它的生成矩阵为 G，P 为 GF(2)上的一个 n n× 阶的置 换矩阵，B 为 n n× 阶的可逆非线性变换布尔矩阵， 设 m 为长为 k 的二进制明文，则基于 LDPC 纠错密 码的加密运算为 E(m)=(mGB+Z)P=mGBP+ZP=C Z 为二进制伪随机序列，式中的 G、B、Z 和 P 保密，作为私钥，只有收发双方知道。 当密文经过深空信道传输到接收端时，由于深空 中噪声的干扰，密文 C 变为 R=C+E, E 为错误图样。 接收端收到 R 后，进行如下的解密运算。 （1）左乘 1P− ， 1 1 1 1 1( )D R RP CP EP MGB Z EP − − − −= = + = + + （2）模 2 加 Z 序列 1 1 2 1( ( ))D D R MGB EP Z Z MGB EP − −= + + + = + （3）右乘 1B− 1 1 1 1 1 2 1( ( )) ( )D D R B MGB EP B MG EP B − − − − −= + = + （4）最后送入纠 t 个错误的 LDPC 码译码电路， 得到明文 M。 1 1 3 ( )D MG EP B M − −+ = 从上述解密过程可知，如深空信道产生的错误图 样 E 的重量小于 t，即 ( )W E t≤ ，则 1 1( )W EP B t− − ≤ ， 因而 LDPC 码译码器能正确译码，得到正确的明文。 2 性能分析 由 LDPC 纠错密码的加密过程可知，该纠错加密 体制的密钥有四部分组成，(n, k, 2t+1)的 LDPC 码生 成矩阵 G，可逆多变量非线性变换布尔矩阵 B,置换矩 阵 P, 和伪随机序列 Z。与单纯的基于线性变换的纠 错密码相比较，由于可逆多变量非线性变换布尔矩阵 的引入，构造的基于 LDPC 纠错密码能够抵抗线性密 码分析和差分攻击，具有更高的安全性[11]。对于深空 有扰信道，没有与纠错密码结合的密码体制，密文在 传输过程中的任何一个错误，必将使接收端解密得到 的明文发生错误，产生不正确的解密。对于深空通信， 安全可靠有效的通信系统特别重要。有加解密过程可 知，对于错误图样的重量小于等于 t 的密文，都能正 确译码，同时具有较高的安全性。 3 结 论 纠错密码结合了纠错码和密码的功能，不仅提高 了深空通信系统处理信息的效率，而且纠错密码具有 概率加密的特性，提高了密码的安全性。基于 LDPC 码的加密和解密算法运算，相对而言仍较复杂，如何 减小加密和解密的复杂性，增强纠错密码的安全性， 使其更适合深空通信的特殊环境，仍是进一步研究的 课题。 致谢：感谢周贤伟教授在百忙之中给予的指导和 意见以及在文章完成过程中提供的良好科研条件。 4 专题六：空间信息安全与防护 参考文献： [1] ZHANG Geng-xin, XIE zhi-dong, SHEN Zhi-qiang. Current situation and development of deep space communication [J]. Oigital communication word (张更新，谢智东，沈志强. 深空通信的现状与 发展. 数字通信世界)，2010，（04）：82-87. [2] Wang Xin-mei. Generalization of M public key system and analysis of its performance on noisy channel [J]. Chinese Journal of electronics (王 新梅. M公钥的推广及通过有扰信道时的性能分析.电子学报)，1986, 8(04): 84-90. [3] Wang Xin-mei. MC error correcting block cipher systems[J]. Journal on Communications (王新梅, MC分组加密纠错机制.通信学报), 1986,: 1-6. [4] Gallager R G. Low Density parity Check Codes[M].Cambridge, Mass; MIT Press, 1963. [5] LI Mao-Pei, Chou Ting-xian. Channel coding in deep space telemetry systems [J]. Journal of telemetry, tracking, and command (李茂沛，周 廷显. 深空遥测系统中信道编码简述.遥测遥控)，2006，27(1): 25-27. [6] Berlekamp E R, McEliece R J, Van Tilborg H C A, On the inherent intractability of certain coding problems[J]. IEEE Trans Inform Theory, 1978, 24: 384-386. [7] McEliece R J. A public-key cryptosystem based on algebraic coding theory. DSN Progress Rep 42-44. January and February 1978,: 114-116. [8] T.a. Berson. Failure of the McEliece public-key cryptosystem under message-resend and related-message attack. Advances In Cryptology—Proceedings of Crypto’97, Lecture notes in computer science, 1997, 1294,:213-220. [9] Rao. T R N. Cryptosystems using algebraic codes. Int Conf on Computer Systems&Signal Processing, Bangalore, India, 1984. [10] Mathur C. N, Narayan K, Subbalakshmi K. P. High diffusion cipher: encryption and error correction in a single cryptographic primitive[c]. Applied Cryptography and Network Security, Lecture Notes Computer Science, 2006, 3989,: 309-324. [11] Yang Min, Meng Qing-shu, Zhang Huan-guo.Construction of error-correction cryptosystem based on ECC and HFE[J]. Computer Engineering and Applications (杨敏，孟庆国，张焕国, 基于ECC和HFE 的纠错密码构造,计算机工程与应用), ,2008,44(27):31-32. 面向深空通信的纠错密码研究 作者： 丁颜， 王超 作者单位： 北京科技大学信息工程学院,北京,100083 本文读者也读过(10条) 1. 宋宁宁.王超 基于组合公钥技术的深空通信密钥管理方案[会议论文]-2010 2. 郭继文.王超 深空通信中基于数字签名的低延迟安全接入研究[会议论文]-2010 3. 陈磊 空间信息对抗相关理论与技术研究[会议论文]-2010 4. 范超.张红旗.杜学绘.张传富 高安全级因特网协议加解密器的分析与仿真[会议论文]-2010 5. 韦博.赵悦.陈钧.梁心东 可信多域安全系统框架研究[会议论文]-2010 6. 李洪鑫.苏锦海.张传富.范超 空间信息网络安全协议建模方法研究[会议论文]-2010 7. 胡桂章.尹铨 虚拟化技术在空间信息系统指挥平台的应用研究[会议论文]-2010 8. 陈鹏.景志宏.刘振霞 军用综合移动通信网络分布式管理[会议论文]-2010 9. 张志强.王宇.卢昱 基于行为建模的卫星网络安全协议成本度量[会议论文]-2010 10. 魏靓.张串绒.郑连清 空间Adhoc信息系统安全研究[会议论文]-2010 本文链接：http://d.g.wanfangdata.com.cn/Conference_7396641.aspx