相关准循环码字集方法攻击McEliece密码体制

doi:10.3969/j.issn.1001-2400.2014.02.003

J4 ›› 2014, Vol. 41 ›› Issue (2): 15-19+50.doi: 10.3969/j.issn.1001-2400.2014.02.003

Attack method against the McEliece cryptosystem based on the correlative quasic-cyclic codes set

LIU Jingmei¹;WANG Yanli¹;LIANG Bin¹;ZHAO Senlin²

(1. State Key Lab. of Integrated Service Networks, Xidian Univ., Xi'an 710071， China;
2. College of Electronic Engineering, Xi'an Univ. of Posts ＆ Telecommunications, Xi'an 710061， China)

Received:2012-12-23 Online:2014-04-20 Published:2014-05-30

摘要/Abstract

摘要：

针对基于QC-LDPC码McEliece公钥密码体制方案的安全性问题，提出一种基于相关准循环码字的攻击算法．利用相关准循环码字集内的码字在循环移位后相当于信息重发的性能，取得较好的攻击效果．并从正确解密的概率和算法复杂度两方面分析了该算法性能．仿真结果表明，该算法具有较高的正确解密概率(0.999)和较低的工作因子(2^40.7)．

关键词: McEliece公钥密码体制, QC-LDPC码, 攻击算法, 工作因子

Abstract:

Focusing on the security of McEliece public key cryptosystem based on the QC-LDPC code, a new attack algorithm based on the correlative quasi-cyclic(QC) code word is proposed. As the code word in the QC code set is shifted cyclically which is equivalent to information retransmission, the algorithm's effect is better. Performance is analyzed from probability of the correct decipher and computational complexity. Simulation results show that the proposed algorithm possesses a higher probability of the correct decipher (0.999) and a lower work factor (2^40.7).

Key words: McEliece public key cryptosystem, QC-LDPC code, attack algorithm, work factor

中图分类号:

TN918.1

刘景美;王延丽;梁斌;赵森林. 相关准循环码字集方法攻击McEliece密码体制[J]. J4, 2014, 41(2): 15-19+50.

LIU Jingmei;WANG Yanli;LIANG Bin;ZHAO Senlin. Attack method against the McEliece cryptosystem based on the correlative quasic-cyclic codes set[J]. J4, 2014, 41(2): 15-19+50.

参考文献

［1］ Baldi M, Chiaraluce F. Cryptanalysis of a New Instance of McEliece Cryptosystem Based on QC-LDPC Codes［C］//IEEE International Symposium on Information Theory. Piscataway: IEEE, 2007: 2591-2595.
［2］张国华, 王新梅. 一类围长至少为6的QC-LDPC码的存在性［J］. 西安电子科技大学学报, 2011, 38(3): 136-139.
Zhang Guohua, Wang Xinmei. On the Existence of a Class of QC-LDPC Codes with Girth at Least Six［J］. Journal of Xidian University, 2011, 38(3): 136-139.
［3］ Baldi M, Bodrato M, Chiaraluce F. A New Analysis of the McEliece Cryptosystem Based on QC-LDPC Codes［C］//Security and Cryptography for Networks. Heidelberg: Springer Verlag, 2008: 246-262.
［4］ Baldi M, Bianchi M, Chiaraluce F. Security and Complexity of the McEliece Cryptosystem Based on QC-LDPC Codes［J/OL］. ［2012-10-15］. http://arxiv.org/pdf/1109.5827v6.pdf.
［5］崔俊云, 白宝明, 郭旭东. 一种改进的准循环LDPC码环消除算法［J］. 西安电子科技大学学报, 2010, 37(4): 700-704.
Cui Junyun, Bai Baoming, Guo Xudong. Improved Cycle Elimination Algorithm for Construction of QC-LDPC Codes ［J］. Journal of Xidian University, 2010, 37(4): 700-704
［6］陈超, 白宝明, 王新梅. 一类具有低密度生成矩阵的非二元准循环LDPC码［J］. 西安电子科技大学学报, 2010, 37(3): 412-416.
Chen Chao, Bai Baoming, Wang Xinmei. A Class of Nonbinary Quasi-cyclic LDPC Codes with a Low-density Generator Matrix［J］. Journal of Xidian University, 2010, 37(3): 412-416.
［7］ Mceliece R J. A Public-Key Cryptosystem Based on Algebraic［EB/OL］. ［2012-12-01］. http://www.cs.colorado.edu/～jrblack/class/csci7000/f03/papers/mceliece.pdf.
［8］ Lee P J, Brickell E F. An Observation on the Security of McEliece's Public-key Cryptosystem［C］//Workshop on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 1988: 275-280.
［9］ Adams C M, Meijer H. Security-related Comments Regarding McEliece's Public-key Cryptosystem［J］. IEEE Transactions on Information Theory, 1989, 35(2): 454-455.
［10］ Sun H M. Improving the Security of the McEliece Public-key Cryptosystem［C］//International Conference on the Theory and Application of Cryptology and Information Security. Berlin: Springer-Verlag, 1998: 200-213.

[1]	罗芳;周学广;欧庆于. 对LBlock算法的多重零相关线性分析[J]. J4, 2014, 41(5): 173-179.
[2]	赵永斌;胡予濮;贾艳艳. 一种抵抗能量攻击的线性反馈移位寄存器[J]. J4, 2013, 40(3): 172-179+200.
[3]	孙瑾;胡予濮. 完全安全的基于属性的广播加密方案[J]. J4, 2012, 39(4): 23-28+154.
[4]	肖鹤玲;蔡宁;王骁. 量子LDPC码在量子密钥分配中的应用[J]. J4, 2012, 39(2): 8-11+23.
[5]	刘福运;肖鸿;肖国镇. 一种代数正规形快速变换的零化子算法[J]. J4, 2009, 36(5): 890-895.
[6]	李雪莲;胡予濮. 对具有高代数免疫度布尔函数的新型代数攻击[J]. J4, 2009, 36(4): 702-707.
[7]	张串绒;张玉清. 可证明安全签密方案及其混合结构[J]. J4, 2009, 36(4): 756-760.
[8]	王鑫1;孙晨2;王新梅1. MQ公钥密码体制等价密钥分析[J]. J4, 2009, 36(3): 428-432.