Development of a related key function in ARX stochastic data transformation algorithms

Abstract

In this paper an analysis of ARX stochastic algorithms based on related keys is considered. Analysis based on this approach is carried out using the selected open text and the keys linked by some function. A special case of using related keys is the analysis of an algorithm consisting only of the operations of modular addition modulo 2n, modulo 2, and cyclic shift. Such algorithms are so-called ARX stochastic algorithms. The common method of analysing the algorithms based on related keys is the rotation analysis method. This method allows formulating requirements only for the number of addition operations modulo 2n. The considered properties of the rotation analysis method demonstrated the need to develop requirements for ARX algorithms in terms of the number of cyclic shift operations. Based on the properties of the mathematical operations used in the ARX stochastic algorithms, a non-cyclic related key function was proposed. Among ARX operations, only the cyclic shift function affects the probability of such relation. The complexity of the analysis based on non-cyclic related key function has been estimated. It is proved that the complexity of relation key analysis of ARX algorithms is determined by the minimum of two numbers: the number of addition operations modulo 2n and cyclic shift operations in the algorithm.

Keywords

• related keys, arx, stochastic algorithms, lightweight algorithms.