| The hash algorithm converts a message with arbitrary length into a fixed length digest value via multiple rounds of transformation,which has important applications in digital signatures,data integrity checks,redundancy checks and so on.In order to better resist to quantum attack,the hash algorithm based on large-size input permutations emerges as the times require.These large permutations are usually constructed by using multiple nonlinear S-boxes so that the algebraic properties of these S-boxes are closely related to the security of the hash algorithm.One of the current research difficulties is how to quickly evaluate the algebraic properties of these large-size S-boxes,for instance the input size of 16-bit S-boxes or even larger input size.Moreover,how to use these algebraic properties to evaluate the security of the large permutation hash algorithm appears to be a hot research topic.This thesis studies the algebraic properties of large state S-boxes.In addition,the nonlinear components of mainstream hash algorithms,e.g.,Keccak and PHOTON are further studied.In particular,some new algebraic properties of Keccak and PHOTON are investigated by using the characteristics of their nonlinear components.The main results are described as follows:1.A GPU-based method for evaluating the algebraic properties of S-boxes is proposed.Based on the CPU-GPU heterogeneous structure,a new method is proposed to quickly evaluate the algebraic properties of S-boxes by using the solution features such as differential uniformity.The results show that when solving the algebraic properties of the 16-bit S-box,the efficiency of the solution based on the GPU environment has been significantly improved,that is,compared with the CPU-based environment,the calculation differential uniformity,non-linearity,and transparency order are improved.The time spent on calculating differential uniformity,non-linearity,and transparency order is saved by 90.28%,80%,and66.67%,respectively.2.A new method to quickly solve the lower bound of the differential uniformity of the S-box is proposed.For given S-box,this method calculates the number of existence solutions for each cyclic differential pairs,and thus gives the lower bound of the differential uniformity.The S-boxes with different input sizes such as 4-bit,5-bit,7-bit,8-bit,and 16-bit are tested,and the experimental results illustrate that the lower bound of the differential uniformity captured by the method are completely consistent with their real differential uniformity,and the time required by this method to solve the lower bound of the differential uniformity is about 82%less than that of the traditional algorithm.3.A new method for solving the one-round PHOTON-80 probabilistic invariant is proposed.Based on the structure of the hash algorithm PHOTON-80,the probabilistic nonlinear invariant is constructed by using the cyclic characteristics of nonlinear components and linear components.The calculation of the probabilistic nonlinear invariant of PHOTON-80 is carried out,and the results show that the nonlinear bias between the reduced one-round PHOTON-80 and a random permutation is about 2-3.7495.In fact,the simulations for the bias values are consistent with the theoretical bias.4.A new 4-round differential path of the Keccak is presented.In the first place,based on the differential characteristics of the nonlinear componentX,where the componentsXare linearized.Moreover,the differential propagation characteristics of the componentXof the Keccak are used to construct two rounds differential path.By using CUDA to search all these differential paths,a new differential path is achieved,where the probability of the differential path is2-24.Compared with the previous known differential paths,this is a new4-round differential path. |
