Математична модель випадкової підстановки

Автор(и)

  • К.Е. Лисицкий
  • И.В. Лисицкая

DOI:

https://doi.org/10.30837/rt.2020.3.202.12

Ключові слова:

симетричний шифр, алгебраїчний імунітет, нелінійний вузол заміни, булева функція, закон розподілу максимумів, модель випадкової підстановки.

Анотація

Обговорюються підходи до відбору випадкових підстановок, засновані на застосуванні системи критеріїв, побудованих з використанням оцінок близькості законів розподілу XOR таблиць і таблиць зміщень лінійних апроксимацій підстановок теоретичним законам, притаманним випадковим підстановкам. Відзначається їх неконструктивність. Неясно, які ж показники відбору є кращими.

Викладається сутність уточненої нами методики визначення законів розподілу максимумів для великих за обсягом вибірок незалежних однаково розподілених випадкових величин. Відзначається, що розподіл максимумів великих за обсягом вибірок незалежних однаково розподілених випадкових величин добре вивчено в теорії ймовірностей і описується розподілом екстремальних значень Фішера – Тіппета або log-Вейбула. Методика застосовується для визначення законів розподілів максимумів XOR таблиць і максимумів зсувів таблиць лінійних апроксимацій вибірки з байтових випадкових підстановок. Результати розрахунків порівнюються з результатами експериментів. Результати розрахунків і експериментів свідчать про те, що в обох випадках розподілу концентруються навколо досить виражених максимумів з цілком певними одними і тими ж найбільш ймовірними значеннями, що дозволяють вважати, що випадково згенеровані підстановки з великою ймовірністю будуть за значеннями максимумів мало відрізнятися один від одного.

На основі отриманих результатів пропонується уточнене визначення випадкової підстановки, яке будується на властивостях вибірки випадкових підстановок.

Відзначається, що застосування випадкових підстановок призводить до збільшення числа циклів приходу шифрів до стану випадкової підстановки на один цикл.

Робиться висновок, що випадкові підстановки, взяті з виходу генератора випадкових підстановок без всяких обмежень, цілком можуть конкурувати з кращими відомими конструкціями S-блоків, що використовуються в сучасних шифрах. Збільшені в порівнянні з граничними значення максимумів, до яких прагнуть автори більшості робіт з пошуку S-блоків з поліпшеними показниками, можуть бути компенсовані використанням в шифрі циклових функцій зі збільшеним числом S-блоків, що активізуються, на перших циклах.

Посилання

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. С. 5457.

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. 138.

Лисицкий К.Е. О методике оценки законов распределения вероятностей максимумов полных дифференциалов и смещений линейных оболочек блочных симметричных шифров // Прикладная радио-электроника. Харьков : ХНУРЭ, 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.

##submission.downloads##

Номер

Розділ

Статті