MILP方法在轻量级密码分析中的应用研究
发布时间：2019-02-25 21:27
【摘要】：随着计算机以及互联网技术的普及,信息安全越来越得到人们的重视,密码学作为信息安全的基石,也越来越得到人们的广泛关注。分组密码的研究是当今密码学研究的一个重要领域,分组密码一般采用迭代结构,运行速度快且易于实现,因此广泛运用于各种软硬件安全系统。分组密码有多种结构,例如SPN结构,Feitesl结构等,Present算法,Lbock算法就是SPN结构和Festiel结构的代表算法,Present算法是A.Bogdanov等在CHES2007上提出的一种SPN(Substitution Permutation Network)的结构的超轻量级加密算法,一共将会进行31轮,明密文长度都是64bit,密钥有两种选择分别是80bit和128bit两个版本,主要是适用于资源受限的环境。由于其简单且高效,在物联网和射频识别技术(RFID)中得到广泛的应用。Lblock密码算法是在2011年应用密码学网络安全会议上提出的轻量级分组密码.Lblock是分组长度为64bit的Feistel结构的分组密码算法,共32轮,密钥长度为80bit。MILP全称是混合整数线性规划(Mixed-Integer Linear Programming)是一类源于线性规划的优化,目标是优化在一定约束条件下的目标函数。混合整数线性规划在学术界和工业界都得到了广泛的应用。在分组密码各个模块,MILP的模型是不一样的。孙思维教授在亚密会上提出了MILP模型在分组密码中的应用,以及Nicky Mouha,Qingju Wang等人对于MILP模型结合分组密码的差分分析,以及最近由日本人Todo提出的Division Property,结合MILP方法去搜索轻量级分组密码算法的积分区分器的平衡位置。本文的主要研究内容包括:(1)对SPN类的Present算法,结合该算法的不可能差分特征进行研究,使用两种方法,一种是活跃S盒扩散的总数和轮数,统计S盒扩散之和最少的那一种情况,即为最优的情况;另一种是借助于贪婪算法进行研究,排出不可能出现的差分特征。(2)对Feitesl类的Lblock算法进行积分攻击,核心是构造合适的积分区分器,然后根据自己总结的Lblock算法的密钥扩散规律,统计需要猜测的密钥数量,并得出积分攻击的时间复杂度和数据复杂度,并与Lblock算法其他分析方法的时间数据复杂度进行对比,基于积分攻击的Lblock算法的时间复杂度降低。(3)由Lblock算法的积分攻击,结合最新的Todo提出的Division Property理论概念,在前人的基础上对Lblock算法结合MILP模型进行研究。
[Abstract]:With the popularization of computer and Internet technology, people pay more and more attention to information security. Cryptography, as the cornerstone of information security, has been paid more and more attention. The research of block cipher is an important field of cryptography research nowadays. Block cipher generally adopts iterative structure, it runs fast and is easy to implement, so it is widely used in various hardware and software security systems. Block cipher has many kinds of structures, such as SPN structure, Feitesl structure, Present algorithm and Lbock algorithm, which are the representative algorithms of SPN structure and Festiel structure. Present algorithm is a super-lightweight encryption algorithm of SPN (Substitution Permutation Network) structure proposed by A.Bogdanov and others on CHES2007. There will be 31 rounds of ciphertext, the length of ciphertext is 64 bits, and the key has two versions: 80bit and 128bit. It is mainly suitable for resource-constrained environment. Because of its simplicity and efficiency, Lblock cryptosystem is a lightweight block cipher proposed at the 2011 Security Conference on Applied Cryptography. Lblock is a block cipher algorithm based on Feistel structure with 64bit packet length, which is widely used in the Internet of things and Radio Frequency Identification (RFID). There are 32 rounds in which the length of the key is 80bit.MILP, which is a mixed integer linear programming (Mixed-Integer Linear Programming) is a class of optimization derived from linear programming. The objective is to optimize the objective function under certain constraints. Mixed integer linear programming has been widely used in academia and industry. In each module of block cipher, the model of MILP is different. Professor Sun thought presented the application of MILP model in block cipher, the differential analysis of MILP model combined with block cipher by Nicky Mouha,Qingju Wang et al., and the recent Division Property, proposed by Japanese Todo. The MILP method is combined to search the balanced position of the product partition divider of the lightweight block cipher algorithm. The main contents of this paper are as follows: (1) the Present algorithm of SPN class is studied in combination with the impossible differential features of the algorithm. One is the total number of active S-box diffusion and the number of wheels, and the other is the number of active S-box diffusions. The case in which the sum of S-box diffusion is least is the best case; The other is that the greedy algorithm is used to remove the difference features that are impossible to appear. (2) the integral attack on the Lblock algorithm of the Feitesl class, the core of which is to construct a suitable integral partition divider. Then according to the law of key diffusion of Lblock algorithm, the number of keys that need to be guessed is counted, and the time complexity and data complexity of integral attack are obtained, and compared with the time data complexity of other analysis methods of Lblock algorithm. The time complexity of Lblock algorithm based on integral attack is reduced. (3) based on the integration attack of Lblock algorithm and the latest concept of Division Property proposed by Todo, the Lblock algorithm combined with MILP model is studied on the basis of predecessors.
【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP309
本文编号：2430551
[Abstract]:With the popularization of computer and Internet technology, people pay more and more attention to information security. Cryptography, as the cornerstone of information security, has been paid more and more attention. The research of block cipher is an important field of cryptography research nowadays. Block cipher generally adopts iterative structure, it runs fast and is easy to implement, so it is widely used in various hardware and software security systems. Block cipher has many kinds of structures, such as SPN structure, Feitesl structure, Present algorithm and Lbock algorithm, which are the representative algorithms of SPN structure and Festiel structure. Present algorithm is a super-lightweight encryption algorithm of SPN (Substitution Permutation Network) structure proposed by A.Bogdanov and others on CHES2007. There will be 31 rounds of ciphertext, the length of ciphertext is 64 bits, and the key has two versions: 80bit and 128bit. It is mainly suitable for resource-constrained environment. Because of its simplicity and efficiency, Lblock cryptosystem is a lightweight block cipher proposed at the 2011 Security Conference on Applied Cryptography. Lblock is a block cipher algorithm based on Feistel structure with 64bit packet length, which is widely used in the Internet of things and Radio Frequency Identification (RFID). There are 32 rounds in which the length of the key is 80bit.MILP, which is a mixed integer linear programming (Mixed-Integer Linear Programming) is a class of optimization derived from linear programming. The objective is to optimize the objective function under certain constraints. Mixed integer linear programming has been widely used in academia and industry. In each module of block cipher, the model of MILP is different. Professor Sun thought presented the application of MILP model in block cipher, the differential analysis of MILP model combined with block cipher by Nicky Mouha,Qingju Wang et al., and the recent Division Property, proposed by Japanese Todo. The MILP method is combined to search the balanced position of the product partition divider of the lightweight block cipher algorithm. The main contents of this paper are as follows: (1) the Present algorithm of SPN class is studied in combination with the impossible differential features of the algorithm. One is the total number of active S-box diffusion and the number of wheels, and the other is the number of active S-box diffusions. The case in which the sum of S-box diffusion is least is the best case; The other is that the greedy algorithm is used to remove the difference features that are impossible to appear. (2) the integral attack on the Lblock algorithm of the Feitesl class, the core of which is to construct a suitable integral partition divider. Then according to the law of key diffusion of Lblock algorithm, the number of keys that need to be guessed is counted, and the time complexity and data complexity of integral attack are obtained, and compared with the time data complexity of other analysis methods of Lblock algorithm. The time complexity of Lblock algorithm based on integral attack is reduced. (3) based on the integration attack of Lblock algorithm and the latest concept of Division Property proposed by Todo, the Lblock algorithm combined with MILP model is studied on the basis of predecessors.
【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP309
【参考文献】
相关期刊论文 前6条
1 于晓丽;吴文玲;李艳俊;;低轮MIBS分组密码的积分分析[J];计算机研究与发展;2013年10期
2 潘志舒;郭建胜;;LBlock算法的基于比特积分攻击[J];信息工程大学学报;2013年01期
3 詹英杰;关杰;丁林;张中亚;;对简化版LBLock算法的相关密钥不可能差分攻击[J];电子与信息学报;2012年09期
4 董乐;吴文玲;吴双;邹剑;;高阶差分视角下的积分攻击[J];计算机学报;2012年09期
5 王高丽;王少辉;;对MIBS算法的Integral攻击[J];小型微型计算机系统;2012年04期
6 ;SQUARE attack on block ciphers with low algebraic degree[J];Science China(Information Sciences);2010年10期
，本文编号：2430551
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/2430551.html
