Optimization On The Implementation Of Two Types Of Cryptographic Components

With the rapid development of the Internet and the Internet of Things,information carriers have shown a trend of mobilization and miniaturization.Demands on information security under resource-constrained conditions are becoming more and more intense.In order to meet the need for higher speed and finer encryption,it is of great significance to design small and fast encryption and decryption circuits for cryptographic ciphers.Although the details can be different,many of the components are similar or even identical in different ciphers.For example,S-boxes are used to achieve the purpose of confusion and linear transformations are used to achieve the purpose of diffusion.If a general method for optimizing these components is given,then most of the current cryptographic ciphers can be implemented easily.In this paper,two types of components in cryptographic ciphers,linear components and AES-like S-boxes,are studied.From the aspects of algorithm and algebra,many of the current optimization tools in this field have been improved and the results are summarized as follows:1.A more applicable heuristic for finding shorter linear straight-line program(SLP heuristic)is proposed.The BP heuristic proposed by Boyar and Parelta is the main tool to find shorter linear straight-line program for large-scale binary linear systems.This paper improves the classical BP heuristic by adopting a new k-step bundling updating strategy.The proposed strategy is of high adaptability because the parameter k can be adjusted depending on the scale of the problem.Meanwhile,a new technique is presented to simplify the calculation of the distance function by using the zero-sum relation of nodes,which improves the overall efficiency of the algorithm.Finally,the improved algorithm is applied to some common linear components and better results are obtained,among which an implementation of 103 XOR at depth 3 for AES MixColumn is provided.2.The structure of the transfer functions in the composite field arithmetic is solved and the general formula is given.The basic process of implementing multiplicative inversion in finite field by using composite field arithmetic is:convert the input from the original finite field to the newly constructed composite field by input transfer function;computing inversion in the composite field;use the output function to convert it back to the original finite field to obtain the output.The structure of the pairs of transfer functions preserving multiplicative inversion between two fields withp~n elements are studied in this paper.It's proved that there are n(p~n-1)transfer function pairs between the original finite field and the composite field.Also,the constructions of those pairs are detailed.3.Optimizing methods(or algorithms)for reducing the depth complexity of circuits are proposed.Firstly,depth-first search algorithm supporting MUX/NMUX operation is designed for small-scale non-linear components.By imposing certain restrictions on the set of nodes and operations,redundancy of the searching space is effectively avoided.Secondly,a method of module fusion is proposed,that is,the common variables among two contiguous modules should be synthesized together to avoid the unnecessary delay caused by"optimizing each sub-module and then generating the whole circuit through simple cascade"to a certain extent.4.A series of better implementations of AES-like S-boxes are given.By utilizing the techniques proposed in this paper synthetically,including the SLP heuristic,the multiple choices of transfer functions,the depth-first search algorithm and the method of module fusion etc.,circuits of higher efficiency for AES-like S-boxes,especially AES S-box,are designed.On the one hand,following the work of Boyar et al.,we design the circuit of AES S-box on the basis of{XOR,AND,NOT}and an implementation with smaller depth and fewer gates is obtained.Similar methods are used to give a better implementation of SMS4 S-boxes.On the other hand,to design more practical compact and fast circuits of AES S-box,other logic gates are allowed.Firstly,we manage to improve the GF(256)inversion circuit proposed by Ueno et al.by using the depth-first search algorithm supporting MUX/NMUX.Then by applying the improved smaller and faster GF(256)inversion circuit,a more efficient AES S-box circuit is obtained.Moreover,we also utilize the inversion circuit to design circuits for the combined AES S-box.