A METHOD OF CONSTRUCTING A BLOCK CIPHERS ROUND FUNCTION’S POLYNOMIAL OVER A FINITE FIELD

Abstract

The work outlines the method of construction of round function as a polynomial of one variable over the finite field. The proposed method is based on the calculation of the initial cryptographic transformation at special points of the finite field and the subsequent inversion of Vandermonde matrix. For this class of matrices, there are algorithms for calculating the inverse matrix, which are much more efficient than the standard algorithm of inversion using the Gauss method. In the proposed work, the Traub algorithm is used. The computational complexity of Traub algorithm is proportional to the square of the size of a given matrix. The method is applicable to block iterative ciphers of special type (SP-network). For this type of ciphers, mathematical evaluations of algebraic parameters of polinomials of round functions over the finite fields are provided. Quantative values of estimations are calculated for Russian encryption standard "Kuznechik". The estimates of computational complexity of the proposed method are provided. The article contains practical results of estimations of work time for polynomials notation for finite fields of varying dimensions. The proposed method is used for explicit calculation of the polynomial of one variable over the finite field of round function of block cipher PRESENT.

Keywords

• Block cipher
• PRESENT cipher
• interpolation cryptoanalysis
• Vandermonde matrix
• finite field polynomial