基于LDPC码的安全可靠通信方法研究

史治平，任亚军，吕凤橙



基于LDPC码的安全可靠通信方法研究

史治平1,2，任亚军1，吕凤橙1

(1. 电子科技大学通信抗干扰技术国家级重点实验室 成都 611731；2.通信网信息传输与分发技术重点实验室 石家庄 050081)

LDPC码是一类由校验矩阵确定的线性分组码，具有逼近香农限的纠错能力。该文基于纠错码的对称密码体制以及性能等价编码矩阵提出了一类基于LDPC码的安全通信方法，该方法在几乎不改变通信可靠性的情况下，极大地提高了系统的抗截获能力。编码矩阵可以使线性分组码的生成矩阵或校验矩阵。该文通过构造大量性能等价的编码矩阵，以及通信时收发双方同时随机改变编码矩阵的方法来提高通信系统的抗截获能力。另外，由于这些性能等价的编码矩阵产生的LDPC码不仅具有相同的编码参数和可靠性，而且具有非常强的纠错能力，因此该方案是一种安全可靠的一体化通信方法。

LDPC码; 线性同余; 奇偶校验矩阵; 安全通信

信道编码盲识别技术是一种根据侦收到的数据快速有效地识别出信道编码体制的方法，实现了对信源信息的获取，为通信对抗提供更多可靠的依据。这种方式是非合作信号处理从信号层向信息层的扩展，这在非合作通信领域具有重要的价值。因此，信道编码盲识别技术受到国内外研究人员的高度重视，并取得了很多研究成果。按照信道编码类型，信道盲识别技术分为卷积码参数盲估计和分组码参数盲估计，其中分组码主要是线性分组码参数的盲识别。

LDPC码是一种由稀疏校验矩阵定义的线性分组码[1]，在码长较长时其性能逼近香农限。自LDPC码被发现以来，研究人员从LDPC码的构造、编码、译码方法等方面展开了深入的研究，当前LDPC码在卫星、深空、移动、无线等通信系统中已被广泛应用，成为最有潜力的信道编码解决方案。对LDPC码的盲识别算法也逐渐成为研究热点[2-4]。LDPC码盲识别的最终目标是实现稀疏校验矩阵的正确重建。LDPC码的盲识别是为了解决误码条件下的LDPC码开集识别问题。通过综合利用列消元运算、校验向量判定准则以及渐进行变换等方法，将发现正确校验向量和剔除含误码码组作为手段，最终把原问题成功地退化为无误码条件下对LDPC码接收序列进行高斯消元，获取码字空间的一组基，即生成矩阵，进而方便地获取至少一个非稀疏校验矩阵。在此基础上，利用足够多次数的线性行变换运算，可最终实现稀疏校验矩阵的正确重建。

虽然LDPC码盲识别技术的计算难度较大，且该技术目前还存在很多亟待解决的问题，但LDPC码的盲识别技术研究给传统的保密通信方案敲响了警钟。通过保密校验矩阵(或生成矩阵)实现LDPC码的安全通信已经显得越来越脆弱，因此需要新的增强系统安全性的保密方案。

文献[5]证明了纠错码(信道编码)的一般线性分组码译码问题是一个NPC问题。文献[6]利用这一理论基础并结合Goppa码，首次提出了一类基于纠错码的公钥密码体制，称为McEliece公钥密码体制(M体制)。该体制的基本思想是首先接收方选择一个具有快速译码算法的特定码作为私钥，然后使用一个陷门函数将这个特定码隐藏起来，而敌手看到的只是一个一般的线性码。而且该密码体制具有抗量子攻击的特性，因为密码学界普遍认为量子计算机无法攻破NPC问题，所以该密码体制在量子计算机时代仍然是安全的。但该密码体制存在明显的缺点：密钥开销大、信息速率低且没有考虑有扰信道的情况。

针对M体制密钥开销大、信息速率低等缺点，研究者们相继提出了很多改进方案，其中大部分都是利用LDPC码等具有紧致生成矩阵或校验矩阵的码来代替Goppa码[7]；而针对有扰信道的情况，文献[8]对该密码体制进行了修正，使其具有一定的纠错能力，并将修正后的密码体制称为M公钥体制，但这种修正会损失一定的安全性，需要在安全性和可靠性之间进行折中。为了解决该问题，文献[9]提出了基于M公钥体制的分组加密纠错体制，但密钥开销大依旧是该方案的弱点，而且后续研究证明该方案可以被一些选择明文攻击攻破。因此，研究新的M对称密码体制改进方案来降低密钥开销、提高系统的安全性，显得非常重要。

本文基于纠错码的对称密码体制以及性能等价矩阵的概念，提出了一类基于LDPC码的安全通信方法，设计了大量等价的编码矩阵，通过通信双方随机改变编码矩阵，在不改变LDPC码纠错能力的前提下，提高了非合作方识别或破获信息的难度。同时针对密钥开销问题，给出了一种低复杂度密钥控制的同步实现方案。

1 系统模型

1.1 LDPC码

对于LDPC码矩阵的生成，主要有以下几种方法：1) 随机生成后经过仿真挑选[10]，这种方式是早期取得最佳性能LDPC码所采用的方式；2) 通过PEG等方法[11]，从双边图的角度构造矩阵，可以得到性能比较稳定的矩阵。以上两种方法都是从性能的角度出发构造矩阵，通常情况下硬件实现复杂度较高。目前使用较多的是结构化矩阵[12]，如准循环LDPC码(QC-LDPC码)。这种类型的LDPC码从实现角度出发，结构特殊，利于编码或译码实现。

1.2 系统模型

1) 发送端编码和加密算法为：

接收端的接收向量为：

2) 解密与解码的具体步骤如下：

该模型与基于纠错编码的公钥密码体制[13-14]类似，但与之不同的是，这里的矩阵、、、都是随机可变的，它们既可以单独变化，也可以联合改变。本文只考虑两种变化方式(和)，通信时基于性能等价的海量编码矩阵随机改变，提高破解难度。

1) 海量置换矩阵在收发双方同时跳变

2) 基于海量校验矩阵跳变的安全通信

本文采用随机循环差集(RDF)的方法构造大量等价的LDPC码的校验矩阵，通信双方通过随机选择编码矩阵，提高系统的抗截获能力。

研究显示，基于RDF的LDPC码在相同的参数下可以形成大量的等价码[13]，根据RDF构造的校验矩阵的特性，发送端和接收端可以同步改变校验矩阵，有效地提高破译的难度。另外，RDF-LDPC码的奇偶校验矩阵为准循环结构，且可以由基组向量唯一确定，因此，基于RDF-LDPC码构造的安全体制可以减少密钥存储量。

为降低密钥开销和同步难度，基于线性同余思想产生置换矩阵和校验矩阵。发送端和接收端都不用存储矩阵和矩阵，只选用线性同余方法产生的密钥便可使和同步变化，这样能够有效地降低密钥量。

2 基于LDPC码的安全通信方案

下面给出两种基于LDPC码的安全可靠的通信方案，一种是随机改变置换矩阵，另外一种是改变校验矩阵。两种方案都不降低LDPC码的纠错性能，同时具有很高的安全性。

2.1 海量置换矩阵P的生成与同步

下面基于线性同余思想，给出收发双方同步产生置换矩阵的方法。

2.1.1 密钥生成

将基于线性同余方法(linear congruence, LCG)产生的伪随机序列作为通信双方的密钥，然后基于这个密钥同步控制编码矩阵的变化。下面给出密钥的生成过程。

线性同余产生器的递推公式为：

LCG的最大周期为，但大部分情况都会小于。为了确保LCG达到最大周期，式(5)中的参数应满足以下5个条件：

2)的所有质因子的积能整除-1；

3) 若是4的倍数，则-1也应该是4的倍数；

若式(5)的参数满足以上条件，则该递推公式在重复之前可以产生0～之间的所有整数。

根据以上线性同余的思想，本文方案的密钥选取步骤如下：

2) 可信第三方随机选取大随机数作为密钥分发到通信双方；

3) 可信第三方随机选择一个密集的可逆矩阵作为密钥分发给通信双方；

①通信双方统一选取模数，是LDPC码的码长；

②收发双方根据随机数密钥，计算0=mod，得到初始值0；

③收发双方根据线性同余产生器的递推公式得到长度为的整数序列为：

2.1.2 生成同步置换矩阵

基于上述方法产生密钥后，通信双方每次通信时得到同步置换矩阵的步骤如下：

邻位对换法可以由已知序列以非递归的方式，依次得到该序列的全排列序列。

邻位对换法得到全排列的主要思想：

1) 邻位对换法中下一个排列总是上一个排列中某相邻的两位对换得到的，以4个元素的排列1 3 4 2为例，将第一个元素1逐次与其后面的元素交换，可以生成3个新的排列：3 1 4 2，3 4 1 2，3 4 2 1；

2) 将最后一个排列的前面的两个元素交换，再逐次将末尾的1与其前面的元素交换，又生成4个新排列：4 3 2 1，4 3 1 2,，4 1 3 2，1 4 3 2；

3) 将最后一个排列的末尾的两个元素交换，将1从前往后移：1 4 2 3，4 1 2 3，4 2 1 3，4 2 3 1；

4) 如此循环即可求出已知序列的全排列。

本通信方案中的置换矩阵由线性同余参数控制变化，因此在进行LDPC译码前需要根据每次通信的矩阵进行反交织，然后再进行LDPC译码。由于本文方案中的校验矩阵始终不发生变化，因此可以使用相同的译码器实现。

2.2 基于海量校验矩阵H的LDPC安全通信

本文基于RDF生成的性能等价校验矩阵数量巨大的特点，设计了基于海量校验矩阵随机变化的LDPC码安全通信方案。下面介绍该方法的基本原理与通信过程。

为了方便叙述，先给出模的差的定义。

2.2.1 基于RDF算法生成校验矩阵

假设QC-LDPC的奇偶校验矩阵的形式为：

由此可见，该方法构造的LDPC码的校验矩阵由基本块组唯一决定。因此通信双方只需要存储便可以唯一确定出该LDPC码的校验矩阵，基于这种结构进行安全可靠通信，可以大大降低密钥量。

2.2.2 QC-LDPC码校验矩阵的数量分析

则由矩阵便可生成一类QC-LDPC码。

2.2.3 基于海量校验矩阵的安全通信方案

本文通信方案中，因为校验矩阵每间隔一定时间发生改变，所以译码器也应随之改变，这在一定程度上增加了系统的复杂度。由于校验矩阵是根据密钥参数，，动态生成的，因此在密钥参数发生变化后，可以使用软件定义的方式，动态同步改变LDPC译码器。为了权衡系统的复杂度和安全性，可以考虑选择合适的校验矩阵变化频率。

3 性能仿真与安全性分析

下面通过具体实例对以上算法进行说明和性能分析。

3.1 置换矩阵随机改变

图1 置换矩阵变化与不变时的误码曲线对比图

3.2 改变校验矩阵H

在仿真参数设置、加密编码方案与3.1节相同的情况下，为了模拟校验矩阵的变化，仿真时，对于每个信噪比校验矩阵改变20次，置换矩阵始终不变，结果如图2所示。

图2 校验矩阵H变化与H不变时的误码曲线对比图

3.3 校验矩阵和置换矩阵都随机改变

在仿真参数设置、加密编码方案与3.1节相同的情况下，为了模拟校验矩阵的变化，仿真时每个信噪比校验矩阵改变20次；仿真过程中每一帧都采用不同的置换矩阵，仿真结果如图3所示。

图3 置换矩阵P和校验矩阵H同时变化时的误码曲线图

4 结束语

综上所述，本文提出的基于LDPC码的海量编码矩阵传输方案是一种高效的安全可靠传输方法。通过通信双方在海量编码矩阵中的随机选取，极大地增加了系统的安全性，提高了系统抗截获能力；另一方面，由于海量编码矩阵的性能等价性，通信系统的纠错性能不受影响，保证了系统的可靠性和高效性；最后，给出了一种降低开销密钥的编译码矩阵同步控制方案，与直接传递和存储编码矩阵相比，该方案大大降低了密钥开销。

本文建议的基于LDPC码的安全可靠通信方法是一种编码域的抗干扰、抗截获通信方式，它通过信道编码矩阵的随机改变，在保证系统可靠性的同时，提高了编码被攻击者破译的难度。这对于提高基于LDPC码通信系统的安全性具有重要意义。

本文研究工作得到了通信网信息传输与分发技术重点实验室开放课题(KX152600018/ITD-U15009)的资助，在此表示感谢。

[1] MACKAY D J C, NEAL R M. Near Shannon limit performance of low density parity check codes[J]. Electronics Letters, 1996, 18(32): 1645-1646.

[2] 包昕, 周磊砢, 何可, 等. LDPC码稀疏校验矩阵的重建方法[J]. 电子科技大学学报, 2016, 45(2): 191-196.

BAO Xin, ZHOU Lei-ke, HE Ke, et al. A method of restructuring LDPC parity-check matrix[J]. Journal of University of Electronic Science and Technology of China, 2016, 45(2): 191-196.

[3] 包昕, 周磊砢, 何可, 等. 误码条件下的LDPC码盲识别算法[J]. 西安交通大学学报, 2015, 12(49): 53-58.

BAO Xin, ZHOU Lei-ke, HE Ke, et al. A recognition algorithm for LDPC codes of blind in a noisy environment[J]. Journal of Xi’an Jiaotong University,2015, 12(49): 53-58.

[4] 刘海达, 李静, 彭华. 利用最大偏差比的LDPC码识别算法[J]. 信号处理, 2014, 8(30): 908-913.

LIU Hai-da, LI Jing, PENG Hua.Identification algorithm for LDPC codes using maximum deviation ratio[J].Journal of Signal Processing, 2014, 8(30): 908-913.

[5] BERLEKAMP E R, MCELIECE R J, VAN TILBURG H C A. On the inherent intractability of certain coding problems[J]. IEEE Transactions on Information Theory, 1978, 24(3): 384-386.

[6] MCELIECE R J. A public-key cryptosystem based on algebraic coding theory[J]. DSN Progress Report, 1978, 1(9): 114-116.

[7] SHOOSHTARI M K, AHMADIAN M, PAYANDEH A. Improving the security of McEliece-like public key cryptosystem based on LDPC codes[C]//11th International Conference on Advanced Communication Technology. PhoenixPark, Korea: IEEE, 2009: 1050-1053.

[8] 王新梅. M公钥的推广及通过有扰信道时的性能分析[J].电子学报, 1986, 1(4): 86-92.

WANG Xin-mei.Generalization of M public key system and analysis of its performance on noisy[J]. Acta Electronica Sinica, 1986, 1(4): 84-91.

[9] RAO T N R. Joint encryption and error correction schemes [C]//Proceedings of the 11th Annual International Symposium on Computer Architecture. New York, USA: ACM Sigarch Computer Architecture News, 1984, 12(3): 240-241.

[10] RICHARDSON T J, RUDIGER L. Urbanke, effcient encoding of low-density parity check codes[J]. IEEE Trans Inf Theory, 2001, 47(2): 638-656.

[11] HU X Y, ELEFTHERIOU E. Regular and irregular progressive edge-growth tanner graphs[J]. IEEE Transactions on Information Theory, 2005, 1(51): 386-398.

[12] LEI C, IVANA D, JUN X, et al. Construction of quasi-cyclic ldpc codes based on the minimum weight codewords of reed-solomon codes[J]. ISIT, 2004, 1(1): 239.

[13] MARCO B. QC-LDPC code-based cryptography[M]. [S.l.]: Springer, 2014: 23-64.

[14] 蒋定顺, 金力军. 高速跳频通信系统同步技术研究[J].电子科技大学学报, 2005, 34(1): 48-52.

JIANG Ding-shun, JIN Li-jun.Research on synchronization technique for a high-speed FH communication system[J]. Journal of University of Electronic Science and Technology of China, 2005, 34(1): 48-52.

编 辑 叶 芳

Research on Secure and Reliable Communications Method Based on LDPC Codes

SHI Zhi-ping1,2, REN Ya-jun1, and LÜ Feng-cheng1

(1. National Key Laboratory of Science and Technology on Communications, University of Electronic Science and Technology of China Chengdu 611731; 2. Science and Technology on Information Transmission and Dissemination in Communication Networks Laboratory Shijiazhuang 050081)

Low-density parity-check (LDPC) codes are a class of linear block codes defined by the check matrix, which have the error-correcting capability of approaching Shannon limit. Based on the symmetric cryptosystem with error correcting codes as well as performance equivalent coding matrix, this paper proposes a secure communication method based on LDPC codes. This method greatly improves the anti-intercept capability of system and keeps the reliability almost unchanged by constructing a large number of performance equivalent coding matrixes and by simultaneously and randomly shifting the coding matrixes by the sender and receiver. Thus the proposed method has better error-correcting capability and can be applied as a secure and reliable integrated communication solution.

LDPC codes; linear congruence; parity check matrix; secure communication

TN911.22

A

10.3969/j.issn.1001-0548.2017.05.001

2016-10-27；

2017-05-09

国家863项目(2014AA01A704)

史治平(1972-)，女，博士，教授，主要从事无线通信与纠错编码的研究.