Mathematical model of random substitution
DOI:
https://doi.org/10.30837/rt.2020.3.202.12Keywords:
symmetric cipher, algebraic immunity, non-linear replacement node, boolean function, distribution law of maxima, random substitution model.Abstract
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.References
Adams С. M. and Tavares S.E. The Structured design of cryptographically good S-boxes // Journal of Cryptology, 3(1): 27-41, 1990.
Forré R. Methods and instruments for designing S-boxes // Journal of Cryptology, 2(3): 115-130, 1990.
Nyberg K. Perfect nonlinear S-boxes // Advances in cryptology -EUROCRYPT91, volume 547, Lecture Notes in Computer Science, pp. 378-386. Springer-Verlag, Berlin, Heidelberg, New York, 1991.
Nyberg K. On the construction of highly nonlinear permutations // Advances in cryptology – Proceedings of EUROCRYPT'92 (1993) vol. 740, Lecture Notes in Computer Science Springer-Verlag, Berlin, Heidelberg, New York pp. 92-98.
Nyberg K. Differentially uniform mappings for cryptography // Advances in cryptology – Proceedings of EUROCRYPT'93 (1994) vol. 765, Lecture Notes in Computer Science Springer-Verlag, Berlin, Heidelberg, New York, pp. 55-65.
Claudia Peerez Ruisanchez A NEW ALGORITHM TO CONSTRUCT S-BOXES WITH HIGH DIFFUSION // International Journal of Soft Computing, Mathematics and Control (IJSCMC). Vol. 4, No. 3, August 2015. DOI : 10.14810/ijscmc.2015.4303 41.
Seberry J., Zhang X.-S. and Zheng Y. Nonlinearity and Propagation Characteristics of Balanced Boolean Functions // Inforsation and Cosputation. Vol. 119, No 1, pp. 1-13, 1995.
Pasalic E., Johansson T., Saitra S., Sarkar P. New constructions of resilient and correlation immune Boolean functions achieving upper bounds of nonlinearity // Workshop of Coding and Cryptography, Electronic Notes in Discrete Mathematics. Elsevier, January 2001.
Xiao G-Z and Massey J.L. A Spectral Characterization of Correlation-Immune Combining Functions // IEEE Transaction on Information Theory. Vol. 34, №.3 (1988), pp. 569-571.
Clark J., Jacob J., Stepney S., Saitra S. and Sillan W. Evolving of Boolean functions satisfying sultiple criteria”, proceedings of INDOCRYPT’02, LNCS vol 2551, pages 246-259, Springer, 2002.
Yücel M.D. IAM501-Introduction to Cryptography. Institute of Applied Mathematics METU, Ankara, Turkey (9700501), 2002, p. 1-28.
Лисицкая И.В. К вопросу построения долговременных ключей для алгоритма ГОСТ 28147-89 // Информационно-управляющие системы на железнодорожном транспорте. 1997. № 3. С. 5457.
Lysytska I.V., Koriak A.S., Golovashich S.A., Oleshko O.I., Oleinik R.V. The selection criteria of random substitution tables for symmetric enciphering algorithms // Abstracts of XXVIth General Assembly. Toronto, Ontario Canada, August 13-21, 1999. P. 204.
Горбенко И.Д., Лисицкая И.В. Критерии отбора случайных таблиц подстановок для алгоритма шифрования по ГОСТ 28147-89 //. Радиотехника. 1997. Вып 103. С. 121-130.
Лисицкая И.В. Оценка числа случайных подстановок с заданным распределением парных разностей XOR таблиц и смещений таблиц линейных аппроксимаций / И.В. Лисицкая, А.В. Широков, Е.Д. Мельничук, К.Е. Лисицкий // Прикладная радиоэлектроника. Харьков : ХНУРЭ, 2010. Т. 9, № 3. С. 341-345.
Долгов В.И. Случайные подстановки в криптографии / В.И. Долгов, И.В. Лисицкая, К.Е. Лисицкий // Радіоелектронні та комп’ютерні системи. 2010. № 5 (46). С. 79-85.
Лисицька І.В. Экспериментальная проверка работоспособности новых критериев отбора случайных подстановок / І.В. Лисицька, К.Є. Лисицкий, А.В. Широков, Е.Д. Мельничук // Радіоелектронні та комп’ютерні системи. 2010. № 6 (47). С. 87-93.
Joan Daemen, Vincent Rijmen. Probability distributions of Correlation and Differentials in Block Ciphers. April 13, 2006, pp. 138.
Лисицкий К.Е. О методике оценки законов распределения вероятностей максимумов полных дифференциалов и смещений линейных оболочек блочных симметричных шифров // Прикладная радио-электроника. Харьков : ХНУРЭ, 2015. Т. 14, № 4. С. 335-338.
Лисицкая И.В. Свойства законов распределения XOR таблиц и таблиц линейных аппроксимаций случайных подстановок // Вісник Харк. нац. ун-ту ім. В.Н. Каразіна. 2011. №960, Вип.16. С. 196-206.
Олейников Р.В. Дифференциальные свойства подстановок / Р.В. Олейников, О.И. Олешко, К.Е. Ли-сицкий, А.Д. Тевяшев // Прикладная радиоэлектроника. 2010. Т.9. № 3. С. 326-333.
Долгов В.И. Свойства таблиц линейных аппроксимаций случайных подстановок / В.И. Долгов, И.В. Лисицкая, О.И. Олешко // Прикладная радиоэлектроника. Харьков : ХНУРЭ, 2010. Т. 9, № 3. С. 334-340.
Долгов В.И. S-блоки для современных шифров. / В.И. Долгов, Е.В. Мельничук // Радиотехника. 2012. Вып.171. С. 121-133.
Dolgov V.I. The new concept of block symmetric ciphers design / V.I. Dolgov, I.V. Lisitska, K.Yе. Lisitskyi // Telecom RadEng. v. 76, 2017, i. 2. pages 157-184. DOI: 10.1615.
Downloads
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
