Computational algorithms for calculating the algebraic immunity of nonlinear nodes of replacing symmetric ciphers

Abstract

Block of nonlinear replacements (complication node, substitution block, S-box) is an important element of most modern symmetric ciphers. This is an elementary cryptographic primitive designed to mix input data and introduce non-linearity. By replacing small blocks with other blocks, mixing and scattering of data is achieved, and repeated cyclic repetition of such a procedure makes it possible to achieve the required cryptographic properties of the cipher. Many different criteria are put forward to substitution blocks (balance, high nonlinearity, low autocorrelation, correlation immunity, required avalanche properties, and many others). Each criterion expresses a formalized requirement of resistance to certain types of cryptographic analysis (differential, linear, etc.), i.e. when designing ciphers, they use an integrated approach, choosing S-blocks according to the totality of individual indicators. With the development of algebraic cryptanalysis, a new indicator of the effectiveness of substitution nodes has appeared – algebraic immunity, which is calculated as the minimum degree of the simplest (in a sense) algebraic equation describing the S-block. To search for such an equation, special methods are used, based on the construction of Gröbner bases. If you specify a knot of substitutions through a Boolean function, then to calculate algebraic immunity it is enough to find a function of the least degree from the annihilator space. This article discusses various methods of calculating algebraic immunity, analyzes their computational efficiency, discusses implementation details, substantiates methods for optimizing calculations in terms of time (in terms of number of operations) and capacitive (in terms of memory costs) of complexity. An advanced algorithm for calculating algebraic immunity is proposed, optimized for computing resources, including the necessary RAM sizes. The results of experimental studies are presented, in particular, the results of calculations of the algebraic immunity of 8x8 S-blocks for some well-known modern ciphers (AES, Kalina, Grasshopper, BelT), as well as the results obtained for random 8x8, 9x9 and 10x10 S-blocks.