Factorial number system for nonlinear substitutions generation

Authors

DOI:

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

Keywords:

substitution, factorial number system, S-box, cryptographic indicators, cost functions, heuristic search methods

Abstract

Modern cryptographic applications use cryptographic algorithms with a symmetric key. They provide high conversion rates and resistance to crypto-graphic attacks. To complicate the plaintext – cipher-text ratio, symmetric ciphers usually use nonlinear substitutions (S-boxes). S-boxes cryptographic metrics play a crucial role in ensuring resilience to most known attacks (differential, linear, algebraic, and other cryptanalysis methods). However, generating efficient s-boxes is a challenge. Even for small input/output sizes, there are an extremely large number of possible solutions. Usually, the substitution is represented as a set of Boolean functions. This allows you to apply discrete transformations, for example, Walsh-Hadamard, to evaluate cryptographic indicators. However, methods for generating s-boxes by selecting suitable Boolean functions are extremely complex. Therefore, it is necessary to study new mathematical methods for representing nonlinear substitutions, studying their cryptographic properties, and developing generation algorithms. In this paper, we propose applying factorial number systems to represent nonlinear substitutions. Each substitution can be represented in a unique way through a set of inversions, which, in turn, can be transformed into a factorial number. That is, we can naturally arrange all substitutions by numbering them in the factorial number system. We give examples of such numbering and investigate the cryptographic characteristics of S-boxes with their initial numbers. In particular, we show how the variable functions used in heuristic algorithms for generating non-linear substitutions change. The results obtained can be used to simplify heuristic methods in order to speed up the generation of non-linear substitutions.

References

Програмна реалізація Факторіальної системи числення від Дерев’янка Я. А. URL: https://github.com/DereviankoYaroslav/SBoxDereviankoFactorial.

Програмна реалізація алгоритму PSO з використанням факторіальної системи числення та цінової функції WHS від Дерев’янка Я. А. URL: https://github.com/DereviankoYaroslav/FactorialPSO-WHS.

Програмна реалізація алгоритму PSO з використанням факторіальної системи числення та цінової функції WCF від Дерев’янка Я. А. URL: https://github.com/DereviankoYaroslav/FactorialPSO-CUBA.

Alejandro Freyre-Echevarr ́ıa, Ismel Mart ́ınez-D ́ıaz. A new cost function to improve nonlinearity ofbijective S-boxes. URL: https://www.researchgate.net/publication/343699912_A_new_cost_function_to_improve_nonlinearity_of_bijective_S-boxes.

Alexandr Kuznetsov, Luca Romeo, Nikolay Poluyanenko, Sergey Kandiy, Kateryna Kuznetsova. Optimizing Hill Climbing Algorithm Parameters for Generation of Cryptographically Strong S-Boxes. URL: https://assets.researchsquare.com/files/rs-1657863/v1_covered.pdf?c=1653408505.

John A. Clark, Jeremy L. Jacob, Susan Stepney. The Design of S-Boxes by Simulated Annealing. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.7114&rep=rep1&type=pdf.

Published

2022-06-24

How to Cite

Derevianko, Y., Gorbenko, Y. ., & Kuznetsov О. . (2022). Factorial number system for nonlinear substitutions generation. Radiotekhnika, 2(209), 38–58. https://doi.org/10.30837/rt.2022.2.209.04

Issue

Section

Articles