Порівняльний аналіз правил елементарних клі-тинних автоматів для модифікації деревоподіб-ної геш-функції

Abstract

У роботі розглянуто правила елементарних клітинних автоматів як інструмент формування складної бітової динаміки, що може бути використана для модифікації деревоподібних геш-функцій. Увагу дослідження зосереджено на порівнянні правил елементарних клітинних автоматів як дискретних динамічних систем. Аналіз здійснюється з урахуванням таких властивостей, як схильність до виродження або періодичності, швидкість поширення локальних збурень, баланс нулів та одиниць, ентропійні характеристики, наявність просторово-часових кореляцій і загальна складність поведінки. Окремий інтерес становлять правила, що демонструють хаотичну або близьку до хаотичної динаміку, оскільки саме вони можуть бути найбільш придатними для використання як додатковий шар перетворення в ієрархічних структурах обробки даних. Порівняльний підхід дає змогу встановити, які з правил мають найкраще поєднання нелінійності, дифузії та статистичної збалансованості, а отже можуть розглядатися як найбільш перспективні для подальшого застосування в модифікації деревоподібних геш-функцій.

The paper examines the rules of elementary cellular automata as a tool for generating complex bit dynamics that can be used to modify tree-based hash functions. The study focuses on comparing elementary cellular automaton rules as discrete dynamical systems. The analysis is carried out with regard to such properties as the tendency toward degeneration or periodicity, the rate of propagation of local perturbations, the balance of zeros and ones, entropy characteristics, the presence of spatiotemporal correlations, and the overall complexity of behavior. Particular interest is devoted to rules that demonstrate chaotic or near-chaotic dynamics, since they may be the most suitable for use as an additional transformation layer in hierarchical data processing structures. The comparative approach makes it possible to determine which rules provide the best combination of nonlinearity, diffusion, and statistical balance and therefore can be considered the most promising for further application in the modification of tree-based hash functions.