Research On Computing Method Of The Differential Probability Of SPS Structure

SPS structure is one of the most commonly used structures in block cipher. The study on the upper bound on the maximum differential probability and the computational aspects of the expected differential probability has practical application value to the security of SPS structure. This paper investigates the security of SPS structures against differential cryptanalysis, and we obtain the following main results in this paper:For the first direction, we deal with the upper bound on the maximum differential probability for SPS structure which P can be expressed as n-MDS (Maximum Distance Separable) matrix over the finite field GF(2). A new upper bound on the maximum differential probability for SPS structure is presented, which is tighter than the known theoretical upper bound. Under the conditions that the weight of differential being greater than the differential branch number, a necessary condition on reaching this new upper bound is proposed. Then we study a special case that the SPS structure which S-box can be expressed as inversion mapping and P being a n-MDS matrix over the finite field GF(2n). We prove that the new upper bound on the maximum differential probability is reachable, and we give out the structure of differential which attains the new upper bound. We also present the number of the differential which achieves this upper bound.For the second direction, under the conditions that the SPS structure which S-box can be expressed as inversion mapping and P being a n-MDS matrix over the finite field GF(2), we present the computing method of maximum expected differential probability of SPS structure. Based on Keliher’s algorithm, an improving algorithm is proposed to compute maximum expected differential probability of SPS structure by the method of division of equivalent in allusion to S-box. The improving algorithm can improve the searching efficiency by reducing the search tree layer and keeping the branch of node number as the same as Keliher’s algorithm for each node. With the improving algorithm, we provide that maximum expected differential probability of maximum expected differential probability of two-round AES is equal to106x2-35by computer simulation test.For the third direction, we obtain the computing method of the expected differential probability of the SPS structure which S-box can be expressed as inversion mapping and P has the maximum differential branch number m+1over the finite field GF(2n). Under the conditions that the weight of differential is m+1, we prove that the lower bound on the differential probability is2(1-n)(m+1)(2n-(m+1)-1) with m+1<m, and we present the number of impossible differentials with m+1≥> m. Under the conditions that the weight of differential is m+1, we found methods to compute the expected differential probability of the SPS structure with memory complexity O(22n) and time complexity O(m2n). More generally, under the conditions that the weight of differential is m+d (1≤d≤m), we found methods to compute the expected differential probability of the SPS structure with memory complexity O(22n) and time complexity O(2n(d-1) m2n).For the forth direction, under the conditions that S-box can be expressed as combination of inversion mapping and an affine transformation over the finite field GF(2n), we research on the design of selecting S-box for decreasing the number of impossible differentials and the maximum differential probability. Firstly, we provide a description of differential probability for selecting S-box. Necessary and sufficient conditions of impossible differentials are presented, and we proved the number of impossible differentials. Then, an upper bound and a lower bound on the maximum differential probability of selecting S-box are proved, and we present the reachability of these two bounds. In order to reducing the number of impossible differentials and the maximum differential probability, we give out some design for selecting S-box. Finally, we present the differential properties of selecting S-box with experimental method. The theoretical analysis and experimental analysis show that selecting S-box is better than single S-box in terms of the differential properties.