Heuristic Construction Of Boolean Functions And Pseudo-random Number Generation

Pseudo-random numbers have been widely used in various fields of cryptography,and their random performance directly affects the security of data encryption,digital signatures,and identity authentication.The generator includes driving part and nonlinear part.The driving part is mainly composed of a linear feedback shift register,due to its inherent linear characteristics,it is vulnerable to attack.The parallel,concise and interactive features of cellular automata have received widespread attention in recent years.The non-linear component consists of one or several Boolean functions,and its performance influences the security of the pseudo-random number generator.At present,Boolean functions are constructed through theoretical construction and computer search.Although the theoretical structure has a rigorous proof,it can only be optimized for a certain property,and it is difficult to obtain the optimization of each property.Computer search algorithms can balance multiple cryptographic properties.Therefore,in this thesis,heuristic algorithms in computer search algorithms are used to construct Boolean functions that have a good compromise between cryptographic properties.The heuristic algorithm is applied to a pseudo-random number generator based on cellular automata.The details are as follows:On the one hand,the existing two-stage hybrid algorithm based on the simulated annealing algorithm and the hill-climbing algorithm is optimized.And the parameters of the algorithm are improved.Parameters such as initial temperature,attenuation factor,early stopping cycle conditions,and simulated annealing length were reset based on experimentally measured data.Use a polynomial with parameters for the cost function.In the end,the entire algorithm can reach the global optimal solution area probabilistically in the early stage and can also approximate the optimal solution quickly in the later stage.Computer software is used to simulate the final constructed Boolean functions of 8 to 14 arguments.Based on the original high degree of non-linearity and autocorrelation,the functions also have the optimal algebraic degree,first-order resiliency,high algebraic immunity,and high resistance to fast algebraic attacks.Therefore,these Boolean functions have achieved a good compromise in the cryptographic properties.On the other hand: the constructed Boolean function is applied as a filter function to a pseudo-random number generator.A new reconfigurable pseudo-random number generator based on cellular automata is designed.The pseudo-random number generator includes three parts,a linear module,a non-linear module,and a filter function module.In the linear module,a linear cellular automata with a maximum period is used as a cryptographic device.In the nonlinear module,a reconfigurable nonlinear cellular automata's synthesis algorithm is designed.This algorithm can synthesize different nonlinear cellular automata based on different initial keys.The synthetic nonlinear cellular automata are used as the device of the nonlinear part.In the filter function module,a two-stage hybrid algorithm is used to generate a better compromise Boolean function.The pseudo-random number generator is reconfigurable,and the entire structure can be determined based on the users' key.The structure can effectively resist correlation attacks,linear analysis,algebraic attacks,and MS attacks.The output random number sequence can successfully pass the statistical performance test of NIST and GM.