Mathematical model of random substitution - Лисицкий, К.Е.; Лисицкая, И.В. (Radiotekhnika, 2020)
Approaches to the selection of random substitutions based on the application of a system of criteria constructed using estimates of the proximity of distribution laws of XOR tables and tables of displacements of linear approximations of substitutions to theoretical laws inherent in random substitutions are discussed. Their non-constructiveness is noted. It is not clear which selection rates are preferred. The essence of our refined methodology for determining the laws of distribution of maxima for large samples of independent identically distributed random variables is stated. It is noted that the distribution of the maxima of large samples of independent identically distributed random variables is well studied in probability theory and is described by the distribution of Fisher-Tippett or log-Weibull extreme values. The technique is used to determine the laws of distribution of the maximums of XOR tables and the maximum of displacements of tables of linear approximations of a sample from byte random substitutions. The calculation results are compared with the experimental results. The results of calculations and experiments indicate that, in both cases, the distributions are concentrated around sufficiently pronounced maxima with quite definite and the same most probable values, which make it possible to assume that randomly generated substitutions with a high probability will differ little from each other in the values of the maxima. Based on the results obtained, a refined definition of random substitution is proposed, which is based on the properties of a sample of random substitutions. It is noted that the use of random substitutions leads to an increase in the number of cycles of arrival of ciphers to the state of random substitution by one cycle. It is concluded that random substitutions taken from the output of a random substitution generator without any restrictions can compete with the best known S-box constructions used in modern ciphers. The maxima that are increased in comparison with the limiting values, which the authors of most works on the search for S-boxes with improved indicators strive for, can be compensated for by using cyclic functions in ciphers with an increased number of activated S-boxes in the first cycles.